Editing Memory management unit (section)

=== Paged translation ===

[[Image:MMU principle updated.png|thumb|325px|Schematic of the operation of an MMU<ref name="TanenMOS">{{cite book |author=Tanenbaum, Andrew S. |title=Modern operating systems |publisher=Prentice-Hall |location=Upper Saddle River (New Jersey) |year=2009 |isbn=978-0-13-600663-3 }}</ref>{{Rp|186 ff.}}]]

In paged translation, the [[address space]] (the range of addresses used by the processor) is divided into [[page (computer science)|pages]], each having a size which is a power of 2, usually a few [[kilobyte]]s, but they may be much larger. Programs reference memory using the natural address size of the machine, typically 32 or 64 bits in modern systems. The bottom bits of the address (the offset within a page) are left unchanged. The upper address bits are the virtual page numbers.<ref name="ucsd-lecture">{{cite web
 | url = http://cseweb.ucsd.edu/classes/su09/cse120/lectures/Lecture7.pdf
 | title = Lecture 7: Memory Management
 | work = CSE 120: Principles of Operating Systems
 | year = 2009 | access-date = 2013-12-04
 | author = Frank Uyeda | publisher = UC San Diego
 }}</ref>

Most MMUs use an in-memory table of items called a [[page table]], containing one [[page table entry]] (PTE) per virtual page, to map virtual page numbers to physical page numbers in main memory. Multi-level page tables are often used to reduce the size of the page table. An associative cache of PTEs is called a [[translation lookaside buffer]] (TLB) and is used to avoid the necessity of accessing the main memory every time a virtual address is mapped.<ref name=Zehr/>

Other MMUs may have a private array of memory,<ref>{{cite book|url=http://bitsavers.trailing-edge.com/pdf/rca/spectra70/model46/70-46-601_70-46_RefMan_Mar68.pdf|title=Spectra 70 70/46 Processor Reference Manual|pages=5–6,12-13|publisher=[[RCA]]|date=March 1968|access-date=August 15, 2013}}</ref> a set of registers,<ref>{{cite book|url=http://bitsavers.org/pdf/sds/9xx/940/900640A_940_RefMan_Aug66.pdf|title=Reference Manual, SDS 940 Computer|date=1966|pages=8–10|publisher=[[Scientific Data Systems]]}}</ref> or a one-or-more-level array of static RAM<ref>{{cite book|url=http://bitsavers.org/pdf/sun/sun3/3-100/800-1386-13_2060_CPU_Engineering_Manual.pdf|title=Hardware Engineering Manual for the 2060 CPU Board|date=10 May 1987|pages=121–129|publisher=[[Sun Microsystems]]}}</ref> to store a set of mapping information.

The MMU splits the virtual address into a virtual page number and an offset within the page. The virtual page number is used to select a page table entry; if the page table entry is found, and the page is marked as being in memory, the physical page number in the page table entry is combined with the offset to construct the physical address corresponding to the virtual address.<ref name="ucsd-lecture" />

The virtual page number may be directly used as an index into the page table or other mapping information, or it may be further divided, with bits at a given level used as an index into a table of lower-level tables into which bits at the next level down are used as an index, with two or more levels of indexing.

One issue with paged translation is that as the virtual address space expands, the amount of memory needed to hold the mapping increases as well.
For instance, in the [[68020]] the addresses are 32 bits wide, meaning the virtual page number for an 8&nbsp;kB page size is the upper 19 bits of the address, and a single-level page table would be 512&nbsp;kB in size.<ref name=Zehr/> In the 1980s, for an in-memory page table, this might be a significant fraction of the main memory of the machine, and, for an MMU that holds the page map in static RAM, might require a costly amount of static RAM.
This problem can be reduced by making the pages larger, say 64&nbsp;kB instead of 8.
Now the page index uses 16 bits and the resulting page table is 64&nbsp;kB, which is more tractable.
Moving to a larger page size leads to the second problem: increased internal fragmentation.
A program that generates a series of requests for small blocks will be assigned large blocks and thereby waste large amounts of memory.<ref name=Zehr/>

If the address space is sparse, so that not all regions of it are allocated, the problem can be reduced by using a multi-level page table or static RAM map, and not allocate all the page table entries that would be needed for an empty region.

The paged translation approach was widely used by microprocessor MMUs in the 1970s and 1980s, including the 68020's [[Motorola 68851|68851]] and the on-chip MMU of the [[Motorola 68030|68030]], the [[Zilog Z8000]]'s Z8015, and the [[NS32000]] series's NS16082.

A page table entry or other per-page information may also include information about whether the page has been written to (the ''[[dirty bit]]''), when it was last used (the ''accessed bit'', for a [[least recently used]] (LRU) [[page replacement algorithm]]), what kind of processes ([[user mode]] or [[supervisor mode]]) may read and write it, and whether it should be [[cache (computing)|cached]].<ref name="FOLDOC">{{FOLDOC|Memory+management+unit}}</ref>

Sometimes, a page table entry or other per-page information prohibits access to a particular virtual page, perhaps because no physical [[random-access memory]] (RAM) has been allocated to that virtual page.  In this case, the MMU signals a [[page fault]] to the CPU. The [[operating system]] (OS) then handles the situation, perhaps by trying to find a spare frame of RAM and set up the page map to map it to the requested virtual address.  If no RAM is free, it may be necessary to choose an existing page (known as a ''victim''), using some replacement [[algorithm]], and save it to disk (a process called ''[[paging]]''). With some MMUs, there can also be a shortage of PTEs, in which case the OS will have to free one for the new mapping.<ref name="FOLDOC" /><ref name="ucsd-lecture" />

The MMU may also generate illegal access error conditions or [[invalid page fault]]s upon illegal or non-existing memory accesses, respectively, leading to [[segmentation fault]] or [[bus error]] conditions when handled by the operating system.

Paged translation mitigates the problem of external fragmentation of memory.  After blocks of memory have been allocated and freed, the free memory may become fragmented (discontinuous) so that the largest contiguous block of free memory may be much smaller than the total amount.  With virtual memory, a contiguous range of virtual addresses can be mapped to several non-contiguous blocks of physical memory; this non-contiguous allocation is one of the benefits of [[paging]].<ref name="FOLDOC" /><ref name="ucsd-lecture" />

However, paged translation causes another problem, ''[[internal fragmentation]]''. This occurs when a program requests a block of memory that does not cleanly map into a page, for instance, if a program requests a 1&nbsp;KB buffer to perform file work. In this case, the request results in an entire page being set aside even though only 1&nbsp;KB of the page will ever be used; if pages are larger than 1&nbsp;KB, the remainder of the page is wasted. If many small allocations of this sort are made, memory can be used up even though much of it remains empty.<ref name=Zehr/>