View source for Memory management unit

{{short description|Hardware translating virtual addresses to physical address}}
[[Image:MC68451 p1160081.jpg|thumb|A [[Motorola 68451|68451]] MMU, which could be used with the [[Motorola 68010]]|300x300px]]
A '''memory management unit''' ('''MMU'''), sometimes called '''paged memory management unit''' ('''PMMU'''),<ref>{{foldoc|memory+management+unit|Memory Management Unit|new=yes}}</ref> is a [[computer hardware]] unit that examines all [[computer memory|memory]] references on the [[memory bus]], translating these requests, known as [[virtual memory address]]es, into [[physical address]]es in [[main memory]].
In modern systems, programs generally have addresses that access the theoretical maximum memory of the [[computer architecture]], 32 or 64&nbsp;bits. The MMU maps the addresses from each program into separate areas in physical memory, which is generally much smaller than the theoretical maximum. This is possible because programs rarely use large amounts of memory at any one time.
Most modern [[operating system]]s (OS) work in concert with an MMU to provide [[virtual memory]] (VM) support. The MMU tracks memory use in fixed-size blocks known as ''pages'', and if a program refers to a location in a page that is not in physical memory, the MMU will cause an [[interrupt]] to the [[operating system]]. The OS will then select a lesser-used block in memory, write it to [[backing store|backing storage]] such as a [[hard drive]] if it has been modified since it was read in, read the page from backing storage into that block, and set up the MMU to map the block to the originally requested page so the program can use it. This is known as [[demand paging]].
Modern MMUs generally perform additional memory-related tasks as well. [[Memory protection]] blocks attempts by a program to access memory it has not previously requested, which prevents a misbehaving program from using up all memory or malicious code from reading data from another program. They also often manage a [[processor cache]], which stores recently accessed data in a very fast memory and thus reduces the need to talk to the slower main memory. In some implementations, they are also responsible for [[computer bus|bus]] [[Arbiter (electronics)|arbitration]], controlling access to the memory bus among the many parts of the computer that desire access.
Prior to VM systems becoming widespread in the 1990s, earlier MMU designs were more varied. Common among these was paged translation, which was similar to modern demand paging in that it used fixed-size blocks, but had a fixed-size list of pages that divided up memory; this meant that the block size was a function of the number of pages and the installed memory. Another common technique, found mostly on larger machines, was segmented translation, which allowed for variable-size blocks of memory that better mapped onto program requests. This was efficient but did not map as well onto virtual memory. Some early systems, especially [[8-bit]] systems, used very simple MMUs to perform [[bank switching]].
== Overview ==
[[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.}}]]
Modern MMUs typically divide the virtual [[address space]] (the range of addresses used by the processor) 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 Manual|pages=5–6|publisher=[[RCA]]|date=March 1968|access-date=August 15, 2013}}</ref> 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 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> that holds a set of mapping information.
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.
The physical page number is combined with the page offset to give the complete physical address.<ref name="ucsd-lecture" />
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.
=== Benefits ===
[[Image:VLSI VI475 HMMU chip from an Apple Macintosh II - front.jpg|thumb|VLSI VI475 MMU Apple HMMU from the [[Macintosh II]] used with the [[Motorola 68020]]]]
In some cases, a page fault may indicate a [[software bug]], which can be prevented by using [[memory protection]] as one of key benefits of an MMU: an operating system can use it to protect against errant programs by disallowing access to memory that a particular program should not have access to. Typically, an operating system assigns each program its own virtual address space.<ref name="ucsd-lecture" />
A paged MMU also 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 mapping 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/>
In some early [[microprocessor]] designs, [[memory management]] was performed by a separate [[integrated circuit]] such as the [[VLSI Technology]] VI475 (1986), the [[Motorola 68851]] (1984) used with the [[Motorola 68020]] CPU in the [[Macintosh II]], or the Z8010<ref>{{cite web|url=http://www.bitsavers.org/components/zilog/z8000/z8000DataSheets/z8010_mmu.pdf|title=Z8010 Z8000 MMU Memory Management Unit Product Specification|date=April 1985|publisher=[[Zilog]]}}</ref> and Z8015 (1985)<ref>{{cite web |url=http://www.bitsavers.org/components/zilog/_dataBooks/1983_84_Components_Data_Book.pdf |title=1983/84 Data Book |pages=215–234 |publisher=Zilog |access-date=2021-04-27}}</ref><ref>{{cite magazine|url=https://archive.org/details/byte-magazine-1983-04/page/n235/mode/2up?q=z8015|title=Virtual Memory for Microcomputers |first=Stephen|last=Schmidt |magazine=[[Byte (magazine)|Byte]]|volume=8|issue=4|date=April 1983|pages=234–235}}</ref> used with the [[Zilog Z8000]] family of processors.  Later microprocessors (such as the [[Motorola 68030]] and the [[Zilog Z280]]) placed the MMU together with the CPU on the same integrated circuit, as did the [[Intel 80286]] and later [[x86]] microprocessors.
===Older concepts===
While this article concentrates on modern MMUs, commonly based on demand paging, 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}}</ref>
====Segmented translation====
Early memory management systems, often implemented in software, set aside a portion of memory to hold a series of mappings. These consisted of pairs of values, the ''base'' and ''limit'', although many other terms have been used. When the operating system requested memory to load a program, or a program requested more memory to hold data from a file for instance, it would call the memory handling [[Library (computing)|library]]. This examined the mappings to look for an area in main memory large enough to hold the request. If such a block was found, a new entry was entered into the table. From then on, when that program accessed memory, all of its addresses were offset by the base value. When the program is done with the memory it requested and releases, or the program exits, the entries associated with it are released.<ref name=Zehr/>
This style of access, over time, became common in the [[mainframe]] market{{cn|date=July 2023}} and was known as ''segmented translation'', although a variety of terms are used here as well. 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. Each entry corresponds to a block of memory used by a single program, and the translation is invisible to the program, which sees main memory starting at address zero and extending to some fixed value.<ref name=Zehr/>
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. On systems where programs start and stop over time, this can eventually lead to memory being highly fragmented and no large blocks remaining. A number of algorithms were developed to address this problem.<ref name=Zehr/>
Segmenting was widely used on [[microcomputer]] platforms of the 1980s. Among the MMUs that used this concept were the [[Motorola 68451]] and Signetics 68905,<ref name=Zehr/> but many other examples exist. It was also supported in software implementations; one example is Apple's [[MultiFinder]], released in 1987 for the [[Macintosh]] platform. Each program was allocated an amount of memory that was pre-selected in the [[Finder (software)|Finder]] and translation from virtual to physical was accomplished within the programs using [[handle (computing)|handles]].<ref>{{cite book |title=MultiFinder User's Guide |publisher=Apple |date=1987 |pages=20–22, 24}}</ref>
A more common example is the [[Intel 8088]] used in the [[IBM PC]]. This implemented a very simple MMU inside the CPU, with four [[processor register]]s holding base values accessed directly by the program. These mapped only the upper 4 bits of the 20-bit address, and there was no equivalent of a limit, which was simply the lower 16-bits of the address and thus a fixed 64&nbsp;kB.<ref>{{cite tech report |publisher=University of New Mexico |date=1996 |title=Memory Address Decoding |url=https://ece-research.unm.edu/jimp/310/slides/8086_memory2.html}}</ref> Later entries in the [[x86 architecture]] series used different approaches.
====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.
====Paged translation====
Another approach to memory handling is to break up main memory into a contiguous series of fixed-sized blocks. This is similar to the modern demand paging system in that the result is a series of pages, but in these earlier systems the list of pages is fixed in size and normally stored in some form of fast memory like [[static RAM]] to improve performance. In this case, the two parts of the address stored by the MMU are known as the ''segment number'' and ''page index''.<ref name=Zehr/>
Consider a processor design with 24-bit addressing, like the original [[Motorola 68000]]. In such a system, the MMU splits the virtual address into parts, for instance, the 13 least significant bits for the page index and the remaining 11 most significant bits as the segment number. This results a list of 2048 pages of 8&nbsp;kB each.<ref name=Zehr/> In this approach, memory requests result in one or more pages being granted to that program, which may not be contiguous in main memory. The MMU maintains a list of page number originally expressed by the program and the actual page number in main memory. When it attempts to access memory, the MMU reads the segment number from the processor's memory bus, finds the corresponding entry for that program in its internal memory, and expresses the mapped version of the value on the memory's bus while the lower bits of the original address are passed through unchanged. Like the segmented case, programs see its memory as a single contiguous block.<ref name=Zehr/>
There are two disadvantages to this approach. The first 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 segment number for the same 8&nbsp;kB page size is now the upper 19 bits and the mapping table expands to 512&nbsp;kB in size,<ref name=Zehr/> far beyond what could be implemented in hardware for reasonable cost in the 1980s. 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 block will be assigned large blocks and thereby waste large amounts of memory.<ref name=Zehr/>
The paged translation approach was widely used by microprocessor MMUs in the 1970s and early 80s, including the Signetics 68905 (which could operate in either mode). Both Signetics and [[Philips]] produced a version of the 68000 that combined the 68905 on the same physical chip, the 68070.<ref name=Zehr/>
Another use of this technique is to expand the size of the physical address when the virtual address is too small. For instance, the [[PDP-11]] originally had a 16-bit address that made it too small as memory sizes increased in the 1970s. This was addressed by expanding the physical memory bus to 18-bits, and using an MMU to add two more bits based on other pins on the [[processor bus]] to indicate which program was accessing memory.<ref>{{cite web |url=https://gordonbell.azurewebsites.net/Digital/Bell_Retrospective_PDP11_paper_c1998.htm |first=Gordon |last=Bell |title=A Retrospective on What We Have Learned From the PDP-11}}</ref>
Another use of this same technique, although not referred to as paging but [[bank switching]], was widely used by early 8-bit [[microprocessor]]s like the [[MOS 6502]]. For instance, the [[Atari MMU]] would express additional bits on the address bus to select among several ''banks'' of [[DRAM]] memory based on which of the chips was currently active, normally the CPU or [[ANTIC]]. This was used to expand the available memory on the [[Atari 130XE]] to 128&nbsp;kB.<ref>{{cite tech report |publisher=Atari |title=MCU, Memory Control Unit, FREDDIE |date=1983}}</ref> The [[Commodore 128]] used a similar approach.
==Examples==
Most modern systems divide memory into pages that are {{nowrap|4–64 [[Kilobyte|KB]]}} in size, often with the capability to use so-called huge pages of {{nowrap|2 [[Megabyte|MB]]}} or {{nowrap|1 GB}} in size (often both variants are possible).  Page translations are cached in a [[translation lookaside buffer]] (TLB).  Some systems, mainly older [[RISC]] designs, [[Trap (computing)|trap]] into the OS when a page translation is not found in the TLB.  Most systems use a hardware-based tree walker.  Most systems allow the MMU to be disabled, but some disable the MMU when trapping into OS code.
=== IBM System/360 Model 67, IBM System/370, and successors ===
The [[IBM System/360 Model 67]], which was introduced August, 1965, included an MMU called a dynamic address translation (DAT) box.<ref>{{cite web|url=http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainframe_FS360.html |archive-url=https://web.archive.org/web/20050116150036/http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainframe_FS360.html |url-status=dead |archive-date=January 16, 2005 |title=IBM Archives: System/360 Dates and characteristics |website=03.ibm.com |date=23 January 2003 |access-date=2017-05-03}}</ref><ref name=IBM-S360-67-FuncChar>{{cite web|url=http://www.bitsavers.org/pdf/ibm/360/functional_characteristics/GA27-2719-2_360-67_funcChar.pdf|title=IBM System/360 Model 67 Functional Characteristics, Third Edition|id=GA27-2719-2|date=February 1972|access-date=October 29, 2021}}</ref>  It has the unusual feature of storing accessed and dirty bits outside of the page table (along with the four bit [[Memory_protection#Protection_keys|protection key]] for all S/360 processors).  They refer to physical memory rather than virtual memory, and are accessed by special-purpose instructions.<ref name=IBM-S360-67-FuncChar/>  This reduces overhead for the OS, which would otherwise need to propagate accessed and dirty bits from the page tables to a more physically oriented data structure.  This makes [[OS-level virtualization]], later called [[paravirtualization]], easier.
Starting in August, 1972, the [[IBM System/370]] has a similar MMU, although it initially supported only a 24-bit virtual address space rather than the 32-bit virtual address space of the System/360 Model 67.  It also stores the accessed and dirty bits outside the page table.  In early 1983, the System/370-XA architecture expanded the virtual address space to 31 bits, and in 2000, the [[64-bit]] [[z/Architecture]] was introduced, with the address space expanded to 64 bits; those continue to store the accessed and dirty bits outside the page table.
=== VAX ===
[[VAX]] pages are 512 bytes,<ref name="vax-ref-manual">{{Cite book |url=http://bitsavers.org/pdf/dec/vax/archSpec/EY-3459E-DP_VAX_Architecture_Reference_Manual_1987.pdf |chapter=Chapter 4 Memory Management |title=VAX Architecture Reference Manual |date=1987 |publisher=[[Digital Equipment Corporation]] |id=EY-3459E-DP |isbn=0-932376-86-X}}</ref>{{rp|page=199}} which is very small. An OS may treat multiple pages as if they were a single larger page. For example, [[Linux]] on VAX groups eight pages together. Thus, the system is viewed as having {{nowrap|4 KB}} pages. The VAX divides memory into four fixed-purpose regions, each {{nowrap|1 [[Gigabyte|GB]]}} in size. They are:<ref name="vax-ref-manual" />{{rp|pages=200-201}}
;P0 space: Used for general-purpose per-process memory such as heaps.
;P1 space: (Or control space) which is also per-process and is typically used for supervisor, executive, [[kernel (operating system)|kernel]], user [[Stack (abstract data type)|stacks]] and other per-process control structures managed by the operating system.
;S0 space: (Or system space) which is global to all processes and stores operating system code and data, whether paged or not, including pagetables.
;S1 space: Which is unused and "Reserved to [[Digital Equipment Corporation|Digital]]".<ref name="vax-ref-manual" />{{rp|pages=200-201}}
Page tables are big linear arrays.<ref name="vax-ref-manual" />{{rp|pages=209-215}} Normally, this would be very wasteful when addresses are used at both ends of the possible range, but the page tables for P0 and P1 space are stored in the paged S0 space.<ref name="vax-ref-manual" />{{rp|pages=211-212}} Thus, there is effectively a two-level [[Tree (data structure)|tree]], allowing applications to have sparse memory layout without wasting a lot of space on unused page table entries. Unlike page table entries in most MMUs, page table entries in the VAX MMU lack an [[accessed bit]].<ref name="vax-ref-manual" />{{rp|pages=203-205}} OSes which implement paging must find some way to emulate the accessed bit if they are to operate efficiently. Typically, the OS will periodically unmap pages so that page-not-present faults can be used to let the OS set an accessed bit.
=== ARM ===
[[ARM architecture]]-based application processors implement an MMU defined by ARM's virtual memory system architecture.  The current architecture defines [[Page table entry|PTEs]] for describing {{nowrap|4 KB}} and {{nowrap|64 KB}} pages, {{nowrap|1 MB}} sections and {{nowrap|16 MB}} super-sections; legacy versions also defined a {{nowrap|1 KB}} tiny page.  ARM uses a two-level page table if using {{nowrap|4 KB}} and {{nowrap|64 KB}} pages, or just a one-level page table for {{nowrap|1 MB}} sections and {{nowrap|16 MB}} sections.
TLB updates are performed automatically by page table walking hardware.  PTEs include read/write access permission based on privilege, cacheability information, an [[NX bit]], and a non-secure bit.<ref>{{cite web|url=http://infocenter.arm.com/help/topic/com.arm.doc.ddi0344i/DDI0344I_cortex_a8_r3p1_trm.pdf |title=Cortex-A8 Technical Reference Manual |website=Infoventer.arm.com |access-date=2017-05-03}}</ref>
=== DEC Alpha ===
[[DEC Alpha]] processors divide memory into {{nowrap|8 KB}}, {{nowrap|16 KB}}, {{nowrap|32 KB}}, or {{nowrap|64 KB}}; the page size is dependent on the processor.<ref name="alpha-axp-arch-manual-openvms">{{cite book |url=http://bitsavers.org/pdf/dec/alpha/Sites_AlphaAXPArchitectureReferenceManual_2ed_1995.pdf |title=Alpha AXP Architecture |chapter=Part II-A / OpenVMS AXP Software |year=1995 |edition=Second |id=EY-TI32E-DP |publisher=[[Digital Press]] |isbn=1-55558-145-5}}</ref>{{rp|pages=3{{hyp}}2}}<ref name="alpha-axp-arch-manual-osf1">{{cite book |url=http://bitsavers.org/pdf/dec/alpha/Sites_AlphaAXPArchitectureReferenceManual_2ed_1995.pdf |title=Alpha AXP Architecture |chapter=Part II-B / DEC OSF/1 Software |year=1995 |edition=Second |id=EY-TI32E-DP |publisher=[[Digital Press]] |isbn=1-55558-145-5}}</ref>{{rp|pages=3{{hyp}}2}} pages.  After a TLB miss, low-level [[firmware]] machine code (here called [[PALcode]]) walks a page table.
The [[OpenVMS]] AXP PALcode and [[DEC OSF/1]] PALcode walk a three-level tree-structured page table.  Addresses are broken down into an unused set of bits (containing the same value as the uppermost bit of the index into the root level of the tree), a set of bits to index the root level of the tree, a set of bits to index the middle level of the tree, a set of bits to index the leaf level of the tree, and remaining bits that pass through to the physical address without modification, indexing a byte within the page.  The sizes of the fields are dependent on the page size; all three tree index fields are the same size.<ref name="alpha-axp-arch-manual-openvms" />{{rp|pages=3{{hyp}}2-3{{hyp}}3}}<ref name="alpha-axp-arch-manual-osf1" />{{rp|pages=3{{hyp}}1-3{{hyp}}2}} The OpenVMS AXP PALcode supports full read and write permission bits for user, supervisor, executive, and kernel modes, and also supports fault on read/write/execute bits are also supported.<ref name="alpha-axp-arch-manual-openvms" />{{rp|pages=3{{hyp}}3-3{{hyp}}6}} The DEC OSF/1 PALcode supports full read and write permission bits for user and kernel modes, and also supports fault on read/write/execute bits are also supported.<ref name="alpha-axp-arch-manual-osf1" />{{rp|pages=(II-B) 3{{hyp}}3-3{{hyp}}6}}
The [[Windows NT]] AXP PALcode can either walk a single-level page table in a virtual address space or a two-level page table in physical address space.  The upper 32 bits of an address are ignored.  For a single-level page table, addresses are broken down into a set of bits to index the page table and remaining bits that pass through to the physical address without modification, indexing a byte within the page. For a two-level page table, addresses are borken down into a set of bits to index the root level of the tree, a set of bits to index the top level of the tree, a set of bits to index the leaf level of the tree, and remaining bits that pass through to the physical address without modification, indexing a byte within the page.  The sizes of the fields are dependent on the page size.<ref name="alpha-axp-arch-manual-nt">{{cite book |url=http://bitsavers.org/pdf/dec/alpha/Sites_AlphaAXPArchitectureReferenceManual_2ed_1995.pdf |title=Alpha AXP Architecture |chapter=Part II-C / Windows NT AXP Software |year=1995 |edition=Second |id=EY-TI32E-DP |publisher=[[Digital Press]] |isbn=1-55558-145-5}}</ref>{{rp|pages=3{{hyp}}2-3{{hyp}}4}} The Windows NT AXP PALcode supports a page being accessible only from kernel mode or being accessible from user and kernel mode, and also supports a fault on write bit.<ref name="alpha-axp-arch-manual-nt" />{{rp|page=3{{hyp}}5}}
===MIPS===
{{Unreferenced section|date=June 2023}}
The [[MIPS architecture]] supports one to 64 entries in the TLB.  The number of TLB entries is configurable at CPU configuration before synthesis.  TLB entries are dual.  Each TLB entry maps a virtual page number (VPN2) to either one of two page frame numbers (PFN0 or PFN1), depending on the least significant bit of the virtual address that is not part of the page [[Mask (computing)|mask]].  This bit and the page mask bits are not stored in the VPN2.  Each TLB entry has its own page size, which can be any value from {{nowrap|1 KB}} to {{nowrap|256 MB}} in multiples of four.  Each PFN in a TLB entry has a caching attribute, a dirty and a valid status bit.  A VPN2 has a global status bit and an OS assigned ID which participates in the virtual address TLB entry match, if the global status bit is set to zero.  A PFN stores the physical address without the page mask bits.
A TLB refill exception is generated when there are no entries in the TLB that match the mapped virtual address.  A TLB invalid exception is generated when there is a match but the entry is marked invalid.  A TLB modified exception is generated when a store instruction references a mapped address and the matching entry's dirty status is not set.  If a TLB exception occurs when processing a TLB exception, a double fault TLB exception, it is dispatched to its own [[exception handler]].
MIPS32 and MIPS32r2 support 32 bits of virtual address space and up to 36 bits of physical address space.  MIPS64 supports up to 64 bits of virtual address space and up to 59 bits of physical address space.
===Sun MMU===
The original [[Sun-1]] is a [[single-board computer]] built around the [[Motorola 68000]] microprocessor and introduced in 1982. It includes the original Sun 1 memory management unit that provides address translation, memory protection, memory sharing and memory allocation for multiple processes running on the CPU.  All access of the CPU to private on-board RAM, external [[Multibus]] memory, on-board [[I/O]] and the Multibus I/O runs through the MMU, where address translation and protection are done in a uniform fashion. The MMU is implemented in hardware on the CPU board.
The MMU consists of a context register, a [[Memory segmentation|segment]] map and a page map.  Virtual addresses from the CPU are translated into intermediate addresses by the segment map, which in turn are translated into physical addresses by the page map.  The page size is {{nowrap|2 KB}} and the segment size is {{nowrap|32 KB}} which gives 16 pages per segment.  Up to 16 contexts can be mapped concurrently.  The maximum logical address space for a context is {{nowrap|1024 pages}} or {{nowrap|2 MB.}}  The maximum physical address that can be mapped simultaneously is also {{nowrap|2 MB.}}
The context register is important in a multitasking operating system because it allows the CPU to switch between processes without reloading all the translation state information.  The 4-bit context register can switch between 16 sections of the segment map under supervisor control, which allows 16 contexts to be mapped concurrently.  Each context has its own virtual address space.  Sharing of virtual address space and inter-context communications can be provided by writing the same values in to the segment or page maps of different contexts.  Additional contexts can be handled by treating the segment map as a context cache and replacing out-of-date contexts on a least-recently used basis.
The context register makes no distinction between user and supervisor states.  Interrupts and traps do not switch contexts, which requires that all valid interrupt vectors always be mapped in page 0 of context, as well as the valid supervisor stack.<ref>Sun 68000 Board User's Manual, Sun Microsystems, Inc, February 1983, Revision B</ref>
The [[Sun-2]] workstations are similar; they are built around the [[Motorola 68010]] microprocessor and have a similar memory management unit, with {{nowrap|2 KB}} pages and {{nowrap|32 KB}} segments.  The context register has a 3-bit system context used in supervisor state and a 3-bit user context used in user state.<ref>{{cite web|url=http://bitsavers.org/pdf/sun/sun2/Sun-2_Architecture_Manual_Dec83.pdf|title=Sun-2 Architecture Manual|publisher=[[Sun Microsystems]]|date=15 December 1983|pages=9–12}}</ref>
The [[Sun-3]] workstations, except for the Sun-3/80, Sun-3/460, Sun-3/470, and Sun-3/480, are built around the [[Motorola 68020]], and have a similar memory management unit.  The page size is increased to {{nowrap|8 KB}}.  (The later models are built around the [[Motorola 68030]] and use the 68030's on-chip MMU.)
The [[Sun-4]] workstations are built around various [[SPARC]] microprocessors, and have a memory management unit similar to that of the Sun-3 workstations.
=== PowerPC ===
{{Unreferenced section|date=June 2023}}
In [[PowerPC]] G1, G2, G3, and G4 pages are normally {{nowrap|4 KB.}}  After a TLB miss, the standard PowerPC MMU begins two simultaneous lookups.  One lookup attempts to match the address with one of four or eight data block address translation (DBAT) registers, or four or eight instruction block address translation registers (IBAT), as appropriate.  The BAT registers can map linear chunks of memory as large as {{nowrap|256 MB,}} and are normally used by an OS to map large portions of the address space for the OS kernel's own use.  If the BAT lookup succeeds, the other lookup is halted and ignored.
The other lookup, not directly supported by all processors in this family, is via a so-called [[inverted page table]], which acts as a hashed off-chip extension of the TLB. First, the top four bits of the address are used to select one of 16 [[memory segmentation|segment]] registers. Then 24 bits from the segment register replace those four bits, producing a 52-bit address.  The use of segment registers allows multiple processes to share the same [[hash table]].
The 52-bit address is hashed, then used as an index into the off-chip table. There, a group of eight-page table entries is scanned for one that matches. If none match due to excessive [[hash collision]]s, the processor tries again with a slightly different [[hash function]]. If this, too, fails, the CPU traps into OS (with MMU disabled) so that the problem may be resolved. The OS needs to discard an entry from the hash table to make space for a new entry.  The OS may generate the new entry from a more normal tree-like page table or from per-mapping data structures which are likely to be slower and more space-efficient.  Support for [[NX bit|no-execute]] control is in the segment registers, leading to {{nowrap|256 MB}} granularity.
A major problem with this design is poor [[cache locality]] caused by the hash function.  Tree-based designs avoid this by placing the page table entries for adjacent pages in adjacent locations.  An operating system running on the PowerPC may minimize the size of the hash table to reduce this problem.
It is also somewhat slow to remove the page table entries of a process.  The OS may avoid reusing segment values to delay facing this, or it may elect to suffer the waste of memory associated with per-process hash tables.  G1 chips do not search for page table entries, but they do generate the hash, with the expectation that an OS will search the standard hash table via software.  The OS can write to the TLB.  G2, G3, and early G4 chips use hardware to search the hash table.  The latest chips allow the OS to choose either method.  On chips that make this optional or do not support it at all, the OS may choose to use a tree-based page table exclusively.
=== IA-32 / x86 ===
{{Unreferenced section|date=June 2023}}
The [[x86]] architecture has evolved over a very long time while maintaining full software compatibility, even for OS code. Thus, the MMU is extremely complex, with many different possible operating modes.  Normal operation of the traditional [[80386]] CPU and its successors ([[IA-32]]) is described here.
The CPU primarily divides memory into {{nowrap|4 KB}} pages.  Segment registers, fundamental to the older [[8088]] and [[80286]] MMU designs, are not used in modern OSes, with one major exception: access to [[thread (computer science)|thread]]-specific data for applications or CPU-specific data for OS kernels, which is done with explicit use of the FS and GS segment registers. All memory access involves a segment register, chosen according to the code being executed. The segment register acts as an index into a table, which provides an offset to be added to the virtual address. Except when using FS or GS, the OS ensures that the offset will be zero.
After the offset is added, the address is masked to be no larger than 32 bits.  The result may be looked up via a tree-structured page table, with the bits of the address being split as follows: 10 bits for the branch of the tree, 10 bits for the leaves of the branch, and the 12 lowest bits being directly copied to the result.  Some operating systems, such as [[OpenBSD]] with its [[W^X]] feature, and Linux with the [[Exec Shield]] or [[PaX]] patches, may also limit the length of the code segment, as specified by the CS register, to disallow execution of code in modifiable regions of the address space.
Minor revisions of the MMU introduced with the [[Intel P5|Pentium]] have allowed very large {{nowrap|4 MB}} pages by skipping the bottom level of the tree (this leaves 10 bits for indexing the first level of page hierarchy with the remaining 10+12 bits being directly copied to the result).  Minor revisions of the MMU introduced with the [[Pentium Pro]] introduced the [[physical address extension]] (PAE) feature, enabling 36-bit physical addresses with 2+9+9 bits for three-level page tables and 12 lowest bits being directly copied to the result.  Large pages ({{nowrap|2 MB}}) are also available by skipping the bottom level of the tree (resulting in 2+9 bits for two-level table hierarchy and the remaining 9+12 lowest bits copied directly). In addition, the [[page attribute table]] allowed specification of cacheability by looking up a few high bits in a small on-CPU table.
[[NX bit|No-execute]] support was originally only provided on a per-segment basis, making it very awkward to use.  More recent x86 chips provide a per-page no-execute bit in the PAE mode.  The [[W^X]], [[Exec Shield]], and [[PaX]] mechanisms described above emulate per-page non-execute support on machines x86 processors lacking the NX bit by setting the length of the code segment, with a performance loss and a reduction in the available address space.
=== x86-64 ===
[[File:HSA-enabled virtual memory with distinct graphics card.svg|thumb|right|upright=1.8|[[Heterogeneous System Architecture]] (HSA) creates a unified virtual address space for CPUs, GPUs and DSPs, obsoleting the mapping tricks and data copying.]]
[[x86-64]] is a 64-bit extension of x86 that almost entirely removes segmentation in favor of the [[flat memory model]] used by almost all operating systems for the 386 or newer processors.  In long mode, all segment offsets are ignored, except for the FS and GS segments.  When used with {{nowrap|4 KB}} pages, the page table tree has four levels instead of three.
The virtual addresses are divided as follows: 16 bits unused, nine bits each for four tree levels (for a total of 36 bits), and the 12 lowest bits directly copied to the result.  With {{nowrap|2 MB}} pages, there are only three levels of page table, for a total of 27 bits used in paging and 21 bits of offset.  Some newer CPUs also support a {{nowrap|1 GB}} page with two levels of paging and {{nowrap|30 bits}} of offset.<ref name=amd-volume2>{{cite web
| url = http://support.amd.com/TechDocs/24593.pdf
| title = AMD64 Architecture Programmer's Manual Volume 2: System Programming
| date = March 2017
| access-date = 2017-12-05
}}</ref>
[[CPUID]] can be used to determine if {{nowrap|1 GB}} pages are supported.  In all three cases, the {{nowrap|16 highest}} bits are required to be equal to the 48th bit, or in other words, the low {{nowrap|48 bits}} are [[sign extension|sign extended]] to the higher bits. This is done to allow a future expansion of the addressable range, without compromising backwards compatibility.  In all levels of the page table, the page table entry includes a [[NX bit|no-execute]] bit.
==Alternatives==
===Burroughs B5000 series, B6x00/B7x00/B5900/A-series/Unisys MCP systems===
The [[Burroughs B5000]] from 1961 was the first commercial system to support [[Virtual memory#Segmented_virtual_memory|virtual memory]] (after the [[Atlas Computer (Manchester)|Atlas]]), has no need for an external MMU.<ref>{{cite journal |last1=Tanenbaum|first1=Andrew S.|last2=Herder|first2=Jorrit N. |last3=Bos|first3=Herbert |date=May 2006 |title=Can We Make Operating Systems Reliable and Secure?|url=https://www.computer.org/csdl/mags/co/2006/05/r5044-abs.html |journal=Computer|volume=39 |issue=5 |pages=44–51 |doi=10.1109/MC.2006.156 |citeseerx=10.1.1.112.3028|s2cid=99779 }}</ref> The B5000 and its successors up to current Unisys ClearPath MCP (Libra) systems provide the two functions of an MMU — virtual memory addresses and memory protection — with a different architectural approach. Rather than add virtual memory onto a processor not designed for virtual memory, it is integrated in the core design of the processor/system so there is no requirement for an external unit to add functionality of address translation or bounds checking, resulting in unprecedented memory safety and security.
First, in the mapping of virtual memory addresses, instead of needing an MMU, the machines are [[Burroughs large systems descriptors|descriptor]]-based.<ref name="MCP Descriptor">{{cite web |title=The Descriptor |url=http://www.bitsavers.org/pdf/burroughs/LargeSystems/B5000_5500_5700/5000-20002-P_The_Descriptor_-_A_Definition_of_the_B_5000_Information_Processing_System_196102.pdf |website=Bitsavers}}</ref><ref name="Unisys-descriptor">{{cite web |title=Unisys Descriptor |url=https://public.support.unisys.com/aseries/docs/ClearPath-MCP-20.0/86000387-514/section-000023204.html |website=Unisys}}</ref> The uppermost bit of a 48-bit memory word in the Burroughs B5000 series systems indicate whether the word is an user data or a descriptor/control word; descriptors were read-only to user processes and could only be updated by the system (hardware or operating system). Memory words in the B6x00/B7x00/B5900/A-series/Unisys MCP systems have 48 data bits and 3 tag bits (and later systems to current have 4 tag bits) words whose tag is an odd number are read-only to user processes – descriptors have a tag of 5 and code words have a tag of 3.
Each allocated memory block is given a master descriptor with the properties of the block — physical address, size, and whether it is present in main memory or not, in which case on first access the block must be allocated, or if there is an address, it is an address on secondary storage and must be loaded to main memory.  All references to code and data are made using a descriptor. When a request is made to access the block for reading or writing, the hardware checks its presence via the presence bit (pbit) in the descriptor.
A pbit<ref name="pbit">{{cite web |title=Pbits |url= https://public.support.unisys.com/aseries/docs/ClearPath-MCP-20.0/86000387-514/section-000023194.html |website=Unisys}}</ref> of 1 indicates the presence of the block.  In this case, the block can be accessed via the physical main-memory address in the descriptor.  If the pbit is zero, a pbit interrupt<ref name="Pbit-interrupt">{{cite web |title=Pbit interrupt |url=https://public.support.unisys.com/aseries/docs/ClearPath-MCP-20.0/86000387-514/section-000023193.html |website=Unisys}}</ref> is generated for the [[Burroughs MCP|MCP]] (operating system) to make the block present.  If the address field is zero, this is the first access to this block, and it is allocated (an init (initial) pbit).  If the address field is non-zero, it is a disk address of the block, which has previously been rolled out — the block is fetched from disk, the pbit is set to one and the physical memory address updated to point to the block in memory.  This makes descriptors equivalent to a page-table entry in an MMU system, but descriptors are free of a table.
System performance can be monitored through the number of pbit interrupts, which is the count of accesses to descriptors with a zero bit.  'Init' pbits indicate initial allocations or new memory blocks, but a high level of 'other' pbits indicate that the system had to load a block from virtual memory secondary storage. In normal operation this will not occur very much. If there are above average number of other pbits occurring the system might be thrashing, indicating system overload. In production systems, the machine load will be more constant and thus the system configured or tuned to avoid thrashing.
All memory allocation is therefore completely automatic (one of the features of modern systems<ref>{{cite magazine|url=http://users.ipa.net/~dwighth/smalltalk/byte_aug81/design_principles_behind_smalltalk.html |title=Design Principles Behind Smalltalk |author=Daniel H. H. Ingalls |author-link=Daniel Henry Holmes Ingalls Jr. |magazine=[[Byte Magazine]] |date=August 1981 |url-status=dead |archive-url=https://web.archive.org/web/20070927190743/http://users.ipa.net/~dwighth/smalltalk/byte_aug81/design_principles_behind_smalltalk.html |archive-date=2007-09-27 }} </ref>) and there is no way to allocate blocks other than this mechanism.  There are no such calls as [[malloc]] or dealloc, since memory blocks are also automatically allocated on pbit interrupt or discarded.  The scheme is also [[lazy allocation|lazy]], since a block will not be allocated until it is actually referenced.  When memory is nearly full, the MCP examines the working set, trying compaction (since the system is segmented, not paged), deallocating read-only segments (such as code-segments which can be restored from their original copy) and, as a last resort, rolling dirty (that is updated) data segments out to disk.
Another way these systems provide a function of a MMU is in protection.  Since all accesses are via the descriptor, the hardware can check that all accesses are within bounds and, in the case of a write, that the process has write permission.  The MCP system is inherently secure and thus has no need of an MMU to provide this level of memory protection.
Blocks can be shared between processes via copy descriptors in process stacks (a stack is a special system structure representing the execution state of a process).  Thus, some processes may have write permission, whereas others do not.  Code segments are read-only, thus reentrant and shared between processes.  Copy descriptors contain a 20-bit address field giving index of the master descriptor in the master descriptor array.  This also implements a very efficient and secure Interprocess Communication (IPC) mechanism.  Blocks can easily be relocated, since only the master descriptor needs update when a block's status changes.
Another aspect is performance{{snd}} do MMU-based or non-MMU-based systems provide better performance?  MCP systems may be implemented on top of standard hardware that does have an MMU (for example, a standard PC).  Even if the system implementation uses the MMU in some way, this will not be at all visible at the MCP level.
==See also==
* [[Burroughs large systems descriptors]]
* [[Memory controller]]
* [[Memory protection unit]]
==References==
{{Reflist}}
{{CPU technologies}}
{{Operating System}}
{{Memory management navbox}}
{{DEFAULTSORT:Memory Management Unit}}
[[Category:Central processing unit]]
[[Category:Digital circuits]]
[[Category:Memory management]]
[[Category:Virtual memory]]