Editing Memory management unit (section)

== Types of address translation ==
Early systems used [[base and bounds]] addressing that further developed into [[segmentation (memory)|segmentation]], or used a fixed set of blocks instead of loading them on demand. The difference between these two approaches is the size of the contiguous block of memory; paged systems break up main memory into a series of equal sized blocks, while segmented systems generally allow for variable sizes.<ref name=Zehr>{{cite magazine |first=Gregg |last=Zehr |title=Memory Management Units For 68000 Architectures |magazine=Byte |date=November 1986 |pages=127–135 |url=http://marc.retronik.fr/motorola/68K/68000/Memory_Management_Units_for_68000_Architectures_%5BBYTE_1986_9p%5D.pdf |archive-url=https://web.archive.org/web/20200502144651/http://marc.retronik.fr/motorola/68K/68000/Memory_Management_Units_for_68000_Architectures_[BYTE_1986_9p].pdf |archive-date=2020-05-02 |url-status=dead}}</ref>

=== Segmented translation ===
In segmented translation, a memory address contains a segment number and an offset within the segment. [[Memory segmentation|Segments]] are variable-length, and may have permissions, such as read, write, and execute, associated with them.<ref name="glaser1965">{{cite conference
|title=System Design of a Computer for Time Sharing Applications
|last1=Glaser
|first1=Edward L.
|first2=John F.
|first3=G. A.
|last2=Couleur
|last3=Oliver
|date=1965
|conference=1965 Fall Joint Computer Conference
|url=https://multicians.org/fjcc2.html}}
</ref> A segment is loaded into a contiguous area of physical memory. Typically, the segment number is used as an index into a ''segment table''; each entry in the segment table holds the address of the area of physical memory, the length of the segment, and other information such as permission flags.

This style has the advantage of simplicity; the memory blocks are continuous and thus only the two values, base and limit, need to be stored for mapping purposes.

The disadvantage of this approach is that it leads to an effect known as ''[[external fragmentation]]''. This occurs when memory allocations are released but are non-contiguous. In this case, enough memory may be available to handle a request, but this is spread out and cannot be allocated to a single segment. On systems where programs start and stop over time, this can eventually lead to memory being highly fragmented and no large blocks remaining; in this case, segments would need to be moved in memory, and their segment table entries modified to reflect the new physical address, to make a contiguous space large enough for a segment available.

Some models of the [[PDP-11]] [[16-bit computing|16-bit]] [[minicomputer]] have a segmented memory management unit with a set of ''page address registers'' (PARs) and ''page description registers'' (PDRs); this maps an 16-bit virtual address to an 18-bit physical address. The [[PDP-11/70]] expands that to produce a 22-bit physical address.<ref>{{cite book |title=PDP-11/70 Processor Handbook |publisher=DEC |date=1977 |url=https://bitsavers.org/pdf/dec/pdp11/1170/PDP-11_70_Handbook_1977-78.pdf |chapter=6}}</ref>

Segmenting was widely used on [[microcomputer]] platforms of the 1980s. Among the MMUs that used this concept were the [[Motorola 68451]]<ref name=Zehr/> and the [[Zilog Z8010]], but many other examples exist.

The [[Intel 8086]], [[Intel 8088]], [[Intel 80186]], and [[Intel 80188]] provide crude memory segmentation and no [[memory protection]]. (Every byte of every segment is always available to any program.) The 16-bit segment registers allow for 65,536 segments; each segment begins at a fixed offset equal to 16 times the segment number; the segment starting address granularity is 16 bytes. Each segment grants read-write access to 64&nbsp;KiB (65,536 bytes) of address space (this limit is set by the 16-bit PC and SP registers; the processor does no bounds checking). Offset+address exceeding 0xFFFFF wraps around to 0x00000. Each 64&nbsp;KiB segment overlaps the next 4,095 segments; each physical address can be denoted by 4,096 segment–offset pairs. This scheme can address only 1&nbsp;MiB (1024&nbsp;KiB) of physical memory (and memory-mapped i/o). (Optional [[expanded memory]] hardware can add bank-switched memory under software control.) Later [[x86]] processors, starting with the [[Intel 80286]], supported real segmented mapping, with a segment table.

=== 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/>

=== Segmentation plus paging ===
Some systems, such as the [[GE 645]] and its successors, used both segmentation and paging.  The table of segments, instead of containing per-segment entries giving the physical base address and length of the segment, contains entries giving the physical base address of a page table for the segment, in addition to the length of the segment.  Physical memory is divided into fixed-size pages, and the same techniques used for purely page-based demand paging are used for segment-and-page-based demand paging.

The [[Signetics]] 68905 MMU, designed for the [[Motorola]] [[Motorola 68000|68000]], [[Motorola 68010|68010]], and [[Motorola 68012|68012]] microprocessors, supported segmentation and paging.<ref name="signetics 68905">{{cite book |url=http://www.bitsavers.org/components/signetics/_dataBooks/1986_Signetics_Microprocessor.pdf#page=579 |title=Microprocessor Data Manual 1986 |pages=2{{hyp}}568-2{{hyp}}598 |publisher=[[Signetics]]}}</ref> Both Signetics and [[Philips]] produced a version of the 68000 that combined the 68905 on the same physical chip as the processor, the [[Philips 68070|68070]].<ref name=Zehr/>