TDT09 Topic 10

New approaches to virtual memory - when a page is too big

Virtual memory is an essential component of isolation (protection) and flexibility in today's desktop and server operating systems. However, current approaches to virtual memory are rather inflexible and wasteful. Small pages (typical 4kB in size) in large 64-bit address spaces require large page tables and, in turn, sparsely populated address spaces can lead to page tables with mostly empty entries. Accordingly, there is a trend towards the use of larger page sizes (e.g., 1 MB) which can be even more wasteful. With modern object-oriented systems, developers would benefit from approaches that can protect single objects on a fine-grained basis, quite the opposite of current trends.

Several approaches have been invented to provide fine-grained isolation. All these approaches require knowledge from the software side about object sizes and allocation patterns and support from the hardware side to actually protect memory ranges. Early pure software-based approaches, such as overlays [1] in address-space constrained systems and object-based virtual memory management in Smalltalk [2] required delicate handling on the software side and had significant performance overheads. More recent approaches, such as Liedtke's guarded page tables [3] have been implemented on architectures such as MIPS and Alpha that perform page-table walks in software in case of a page fault [4,5]. A refined approach to guarded page tables are variable radix page tables [6] and the memory management systen in Mondrian [7]. A general overview of different approaches to memory management can be found in [8]. Modern approaches to compiler-codesigned virtual memory are described in [9].

Virtual memory is an essential, performance-critical part of modern computer systems. Implementing virtual memory functinality in hardware is performant, but requires simple structures that are not well suited to the requirement of modern software systems, whereas a completely software-based implementation suffers from bad performance. Approaches to handle virtual memory with a joint hard- and software approach can provide good compromises between performance and granularity here.


  1. Thomas R. Spacek. A proposal to establish a pseudo virtual memory via writable overlays. CACM June 1972. link
  2. Ted Kaehler. Virtual Memory for an Object-Oriented Language. In Byte, the Smalltalk issue, 1981, p. 378ff. link
  3. Jochen Liedtke. Page Table Structures For Fine-Grain Virtual Memory. IEEE Technical Committee on Computer Architecture Newsletter, 1994 link
  4. Jochen Liedtke and Kevin Elphinstone. 1996. Guarded page tables on Mips R4600 or an exercise in architecture-dependent micro optimization. SIGOPS Oper. Syst. Rev. 30, 1 (Jan. 1996), 4–15 pdf
  5. Sebastian Schönberg. Guarded Page Tables for Alpha. TU Dresden 1998. pdf
  6. Cristan Szmajda and Gernot Heiser. Variable Radix Page Table: A Page Table for Modern Architectures. Proc. of ACSAC 2003 pdf
  7. Emmett Witchel, Josh Cates, and Krste Asanović. 2002. Mondrian memory protection. SIGARCH Comput. Archit. News 30, 5 (December 2002), 304–316 pdf
  8. Bruce L. Jacob and Trevor N. Mudge. 1998. A look at several memory management units, TLB-refill mechanisms, and page table organizations. SIGPLAN Not. 33, 11 (Nov. 1998), 295–306 pdf
  9. Brian Suchy, Simone Campanoni, Nikos Hardavellas, and Peter Dinda. 2020. CARAT: a case for virtual memory through compiler- and runtime-based address translation. In Proceedings of PLDI 2020 link