Inside Memory Management, Part 1

Computers never seem to have enough memory, no matter how much memory is installed. One of the most complex and difficult tasks Windows NT faces is managing the limited physical memory present on a computer. This challenge is heightened by the fact that NT must divide physical memory among many processes that might be running simultaneously, giving each process an appropriate memory share. Further, NT must be able to adjust its behavior within a wide range of memory sizes, from as little as 16MB to as much as 1GB or more.

This month I'll introduce the concept of virtual memory, which is based on hardware-supported memory paging. This column will lay a foundation for understanding how NT defines process address spaces. I'll discuss how NT allocates virtual-memory addresses and the internal data structures that record allocation. I'll also describe two powerful features of NT memory management: memory sharing and copy-on-write. Next month, I'll describe more internal data structures, how NT implements shared memory, and working set tuning.

Virtual Memory
As do almost all modern operating systems (OSs), including Windows 3.x, Windows 95, Win98, and UNIX, NT relies on hardware support to provide processes with the illusion that a computer has more memory than it actually has. The mechanism that implements this illusion is known as paged virtual memory. The Memory Manager (or Virtual Memory Manager) executive subsystem is the NT component responsible for NT's paged virtual memory and for exporting functions that other subsystems and applications can use to interact with paged virtual memory. Processes access memory through their virtual memory address space. In NT, the size of a process' address space is defined by the number of bytes that can be described in 32 bits, which is 2³², or 4GB (64-bit NT, which will be available on Alpha and Intel Merced--Deschutes--processors, will have 2⁶⁴ bytes of addressibility). Thus, barring other resource limitations, a process can theoretically allocate 4GB of code and data. However, most computers today have less than 128MB of physical memory. The 4GB address space of a process is therefore known as virtual memory, because it doesn't directly correspond to physical memory.

Before I describe how a computer's OS and hardware collude to trick processes into thinking they have 4GB of memory, I'll review memory address translation. The memory management unit (MMU) on Alpha and x86 processors manages physical and virtual memory in blocks called pages. On x86 processors, the size of a page is 4KB, whereas Alpha processors maintain 8KB pages. A computer's physical memory pages are known as page frames, which the processor numbers consecutively with page frame numbers (PFNs).

When a process references its virtual memory, it does so with a 32-bit pointer, and the MMU's job is to determine the location in physical memory to which the virtual address maps. The MMU determines this location by dividing the address into three separate indexes, as Figure 1, page 68, shows: page directory index, page table index, and page byte offset. The MMU uses each index in a three-step address resolution process.

The first step begins with the MMU locating a table known as the page directory. The MMU locates the page directory by reading the contents of a special hardware processor register. On the x86 this register is the Control Register 3 (CR3), and on the Alpha the register is the Page Directory Register (PDR). Each process has its own private page directory, and the address of that directory is stored in the process' control block data structure. Whenever the scheduler switches from one process to another, NT updates the page directory register with the value stored in the control block of the process that takes over the CPU. The first step in the resolution process continues with the MMU using the page directory index from the virtual address to index to the page directory table. The MMU retrieves from the page directory the page frame number of the location of another table, the page table. Entries in a page directory table are called page directory entries (PDEs) and are 32 bits in size.

In the second step of the resolution process, the MMU uses the page table index from the virtual address on the page table the MMU located. The entry the MMU finds at the page table index identifies a page frame in physical memory. Finally, in the third step, the MMU uses the page byte offset as an index into the physical page and isolates the data that the process wants to reference. Entries in a page table are called page table entries (PTEs). Similar to a PDE, a PTE is 32 bits wide.

You might wonder why the MMU goes through this three-step gyration. It does so to save memory. Consider a one-step translation in which a virtual address is divided into two components, one locating a PTE in a page table and the other serving as a page offset. To map a 4GB address space, the page table would have to consist of 1,048,576 entries. Four bytes (32 bits equals four 8-bit bytes) per entry would mean that the page table would require 4MB of physical memory to map each process' address space. With a two-level scheme such as the one the x86 and Alpha use, only a process' page directory must be fully defined--page tables are defined only as necessary. Thus, if the majority of a process' 4GB address space is unallocated, a significant saving in memory results because page tables are not then allocated to define the unused spaces.