Inside Memory Management, Part 1

Nevertheless, the three-step translation process would cause a system's performance to be unbearably poor if the process occurred on every memory access. Therefore, x86 and Alpha processors come with an address translation cache such as the one Figure 2 shows, which stores the most recent virtual page to physical page translations. When a process makes a memory reference, the MMU takes the virtual page number and simultaneously compares it with the virtual page number of every translation pair stored in the cache (this type of simultaneous-compare memory is known as associative memory). If there's a match, the MMU can bypass the page directory and page table lookups because it has already obtained the page frame number from the simultaneous compare. Address translation caches are known as Translation Look-aside Buffers (TLBs) or Translation Buffers (TBs). One of the costs associated with the scheduler switching from one thread to another is that, if a newly scheduled thread is from a different process, the TLB must clear the mappings that belong to the old process. Then, the three-step translation is required to fill the TLB with mapping pairs for the new process.

Paging
What I've described so far is the address translation that occurs when a process references a valid virtual mem-ory address. A process can also make several types of invalid memory references. I'll review error cases first, then I'll discuss situations in which NT considers an invalid memory reference legal and correct--this type of reference is necessary to implement true virtual memory.

Not many processes today require 4GB of address space. Therefore, the address map of most processes is almost entirely empty or undefined. When a process references undefined parts of its virtual memory map, the MMU detects the undefined space by finding, in the first step of translation, a PDE marked invalid in the page directory, or by finding in the second step of translation a PTE marked invalid in a page table. PDEs and PTEs contain enough space in addition to the indexes they store to keep several bits that serve as bookkeeping information. One bit of a PDE and PTE is the valid bit, which is set only when the translation through the PDE or PTE is configured as legal. If this bit is not set (i.e., it's off), the MMU will stop translation and raise a processor exception called a page fault.

Besides actively playing a role in defining the contents of PDEs and PTEs to define address spaces, NT must respond to page faults and react to them appropriately. When the MMU invokes NT's page-fault handling code, the Memory Manager must check to see if the reference that raised the exception is to an undefined address. If the reference is to an undefined address, the reference raises an access violation (which usually results in the termination of the process) if the processor was executing in user mode, or the blue screen if it was executing in kernel mode. (See my column "Inside the Blue Screen," December 1997, for more information about the difference between user mode and kernel mode).

Because the MMU raises a page fault when a process references an invalid PDE or PTE, paged virtual memory can rely on a nifty trick. To support the illusion that an application process has access to more data and code than physical memory can hold, NT's Memory Manager will move parts of the application to a file on disk called a paging file. NT marks as invalid the PTEs that would otherwise map the pages in the process' address space that correspond to the paged-out data. Thus, when a process tries to reference a paged-out part of its virtual memory, the MMU generates a page-fault. The Memory Manager's page-fault handler then looks into its internal data structures and discovers that the reference that triggered the page fault was not to an undefined address but rather to an address whose data is stored temporarily in the paging file. The Memory Manager then makes room in physical memory for the page from the paging file that the process is requesting. This operation often means that another page of data from the current process or from another process is sent out to the paging file (a page-out operation). Once the Memory Manager creates space in physical memory for the requested page, the process reads the requested page from the paging file (a page-in operation).

After the page-in operation completes, NT updates the page table of the process that raised the page fault, and the page table points at the new page frame. The processor instruction that caused the memory reference restarts, and on the second time through, the translation succeeds without a page fault and accesses the requested physical data. For both page-in and page-out operations, the Memory Manager works with a disk driver to perform the I/O.

Thus using invalid bits to its advantage, the Memory Manager makes a computer appear to have a total amount of memory that is equal to the size of physical memory plus the sizes of all the paging files. You can create up to 16 paging files in NT, placing each on a separate logical drive.