The Future of Memory Management

Solaris is moving towards a future of virtual memory support of multiple page sizes. I am unsure whether this has been implemented or not, however.

Technological and architectural trends are leading towards larger main memory sizes and programs with larger working sets, but with the TLB size remaining relatively small. The TLB size is not expected to increase at the same rate as main memory size, yet the amount of memory mapped by the TLB is an important factor in determining performance. Therefore, there is a need to make the TLB map larger working sets. Otherwise, TLB miss handling may become a performance bottleneck.

One way to increase the amount of memory mapped by the TLB is to increase the page size. This approach may be feasible for modest increases in page sizes (e.g., from 4K to 8K or even 16K bytes). In general, however, this approach causes more internal fragmentations, larger protection boundaries, and forces the system to do all operations, such as copy-on-write, zero-fill on demand, and paging I/O at the new large page size.

Another way to increase TLB coverage is by using multiple page sizes, where each TLB entry may map a page of variable size. For example, large contiguous regions in a process' address space, such as program text, may be mapped using a small number of large pages (e.g., 64K byte pages) rather than a large number of small pages (e.g., 4K byte pages), while thread stacks may continue to be mapped using the small page size.

In general, there are two classes of applications that can benefit from multiple page sizes:

The operating system kernel and devices such as frame buffers. In addition to the microprocessors listed above, many other architectures have some limited support for handling these specialized cases.

General applications, including multiprogrammed job mixes, and applications with large working sets such as numerical analysis code.

Mapping the kernel, or specialized devices such as frame buffers using large mappings, is relatively straightforward. Moreover, adding such functionality to existing systems is a simple engineering exercise that affects limited portions of the operating system. In this note, we are interested in providing multiple page size support for general application code.

Current VM systems are not suited for supporting multiple page sizes as the knowledge of one page size is ingrained in the virtual memory code. Adding support for multiple page sizes raises many new issues regarding how physical memory is managed, as well as affecting common VM and file system optimizations such as read-ahead, clustering, and copy-on-write. Supporting multiple page sizes affects both the machine dependent and independent portions of the system.

Current VM interfaces do not have the notion of multiple page sizes. In general, the system can use large pages to map any mapped region that is big enough. However, as we will show below, in many cases the system may not be able to satisfy a request for a large page mapping, and instead may resort to using a number of small mappings. Therefore, at best, the notion of multiple page sizes should be exported to the user/compiler as a hint only. Introducing support for multiple page sizes complicates many VM data structures. Consider, for instance, the basic page frame descriptor. Traditionally, VM systems represent each physical page with a descriptor. The descriptor is normally linked on a number of lists, contains the page frame number, and includes other state information.

With multiple page sizes, a particular page frame descriptor may represent one of several page sizes. Moreover, at any point in time, a page frame may need to be viewed simultaneously as a distinct small page and as part of a larger page. Traditionally, a hash list of all page frames in the system is built and is accessed by some page frame. With multiple page sizes, arranging and accessing the hash list can become very complex.

Microprocessors that support multiple page sizes normally impose the following alignment restriction: a mapping of size B bytes is defined to start at a virtual address that is a multiple of B and a physical address that is a multiple of B, where B is a power of 2. Note that the physical address specifies a contiguous physical page of size B. These constraints are due to what the hardware can support efficiently in TLBs. Defining a page, as above, allows the hardware to be based on bit-selection. Supporting unaligned virtual/physical addresses requires hardware adders/comparators that are more complicated. All existing microprocessor TLBs that we are familiar with require these alignment restrictions. Therefore, to support multiple page sizes, there is now a need for managing physical memory. For example, the VM system will need to structure its "free" and "clean" page lists into several lists of the supported page sizes. A physical memory allocator, is needed to maintain these lists. When a particular mapping to a large page is requested, clean page of the required size must be located. If a page of the appropriate size is not found, the system may opt for using smaller mappings, or may attempt somehow to coalesce smaller pages into a big page.