Conceptually, the MMU contains a page table which is simply an array of entries indexed by page number. Each entry contains some flags (such as the valid bit mentioned earlier) and a frame number. The physical address is formed by concatenating the frame number with the offset, which are the low-order bits of the virtual address.

There are two problems with this conceptual view. First, the lookup in the page table has to be fast, since it is done on every single memory reference–at least once per instruction executed (to fetch the instruction itself) and often two or more times per instruction. Thus the lookup is always done by special-purpose hardware. Even with special hardware, if the page table is stored in memory, the table lookup makes each memory reference generated by the CPU cause two references to memory. Since in modern computers, the speed of memory is often the bottleneck (processors are getting so fast that they spend much of their time waiting for memory), virtual memory could make programs run twice as slowly as they would without it. We will look at ways of avoiding this problem in a minute, but first we will consider the other problem: The page tables can get large.

Suppose the page size is 4K bytes and a virtual address is 32 bits long (these are typical values for current machines). Then the virtual address would be divided into a 20-bit page number and a 12-bit offset (because 2¹² = 4096 = 4K), so the page table would have to have 2²⁰ = 1,048,576 entries. If each entry is 4 bytes long, that would use up 4 megabytes of memory. And each process has its own page table. Newer machines being introduced now generate 64-bit addresses. Such a machine would need a page table with 4,503,599,627,370,496 entries!

Fortunately, the vast majority of the page table entries are normally marked “invalid.'’ Although the virtual address may be 32 bits long and thus capable of addressing a virtual address space of 4 gigabytes, a typical process is at most a few megabytes in size, and each megabyte of virtual memory uses only 256 page-table entries (for 4K pages).

There is several different page table organizations use in actual computers. One approach is to put the page table entries in special registers. This was the approach used by the PDP-11 minicomputer introduced in the 1970’s. The virtual address was 16 bits and the page size was 8K bytes. Thus the virtual address consisted of 3 bits of page number and 13 bits of offset, for a total of 8 pages per process. The eight page-table entries were stored in special registers. [As an aside, 16-bit virtual addresses mean that any one process could access only 64K bytes of memory. Even in those days that was considered too small, so later versions of the PDP-11 used a trick called “split I/D space.'’ Each memory reference generated by the CPU had an extra bit indicating whether it was an instruction fetch (I) or a data reference (D), thus allowing 64K bytes for the program and 64K bytes for the data.] Putting page table entries in registers helps make the MMU run faster (the registers were much faster than main memory), but this approach has a downside as well. The registers are expensive, so it works for very small page-table size. Also, each time the OS wants to switch processes, it has to reload the registers with the page-table entries of the new process.

A second approach is to put the page table in main memory. The (physical) address of the page table is held in a register. The page field of the virtual address is added to this register to find the page table entry in physical memory. This approach has the advantage that switching processes is easy (all you have to do is change the contents of one register) but it means that every memory reference generated by the CPU requires two trips to memory. It also can use too much memory, as we saw above.

A third approach is to put the page table itself in virtual memory. The page number extracted from the virtual address is used as a virtual address to find the page table entry. To prevent an infinite recursion, this virtual address is looked up using a page table stored in physical memory. As a concrete example, consider the VAX computer, introduced in the late 70’s. The virtual address of the VAX is 30 bits long, with 512-byte pages (probably too small even at that time!) Thus the virtual address a consists of a 21-bit page number p and a nine-bit offset o. The page number is multiplied by 4 (the size of a page-table entry) and added to the contents of the MMU register containing the address of the page table. This gives a virtual address that is resolved using a page table in physical memory to get a frame number f₁. In more detail, the high order bits of p index into a table to find a physical frame number, which, when concatenated with the low bits of p give the physical address of a word containing f. The concatenation of f with o is the desired physical address.

As you can see, another way of looking at these algorithms is that the virtual address is split into fields that are used to walk through a tree of page tables. The SPARC processor (which you are using for this course) uses a similar technique, but with one more level: The 32-bit virtual address is divided into three index fields of 8, 6, and 6 bits and a 12-bit offset. The root of the tree is pointed to by an entry in a context table, which has one entry for each process. The advantage of these schemes is that they save on memory. For example, consider a VAX process that only uses the first megabyte of its address space (2048 512-byte pages). Since each second level page table has 128 entries, there will be 16 of them used. Adding to this the 64K bytes needed for the first-level page table, the total space used for page tables is only 72K bytes, rather than the 8 megabytes that would be needed for a one-level page table. The downside is that each level of page table adds one more memory lookup on each reference generated by the CPU.

A fourth approach is to use what is called an inverted page table. (Actually, the very first computer to have virtual memory, the Atlas computer built in England in the late 50’s used this approach, so in some sense all the page tables described above are “inverted.'’) An ordinary page table has an entry for each page, containing the address of the corresponding page frame (if any). An inverted page table has an entry for each page frame, containing the corresponding page number. To resolve a virtual address, the table is searched to find an entry that contains the page number. The good news is that an inverted page table only uses a fixed fraction of memory. For example, if a page is 4K bytes and a page-table entry is 4 bytes, there will be exactly 4 bytes of page table for each 4096 bytes of physical memory. In other words, less that 0.1% of memory will be used for page tables. The bad news is that this is by far the slowest of the methods, since it requires a search of the page table for each reference. The original Atlas machine had special hardware to search the table in parallel, which was reasonable since the table had only 2048 entries.