Operating Systems: Three Easy Pieces Ch. 20

Paging: Smaller Tables

Page tables are too big and thus consume too much memory.

• 32-bit address space (2^32 bytes), with 4KB (2^12 bytes) and 4-byte page-table entry
  • Simple array-based page tables are too big, taking up far too much memory on typical systems
  • We are in search of some techniques to reduce
• Simple solution: Bigger pages
  • Increasing the page size may decrease the page table size
  • But internal fragmentation will occur
• Hybrid approach: Paging and Segments
  • Instead of having a single-page table for the entire address space of the process, why not have one per logical segment?
  • We still have MMU → hold the physical address of the page table of that segment
  • Three base/bound pairs, one each for code, heap, and tack
    • When the process is running, the base register for each of these segments contains the physical address of a linear page table for that segment
    • each process in the system now has a three-page table associated with it
    • On a context switch, these registers must be changed to reflect the location of the page tables of the newly-running process
  • On the TLB miss → hardware uses the segment bits to determine which base and bound pair to use
    • Hardware takes the physical address and combines it with VPN to form an address of the page table entry
    • The critical difference in our hybrid scheme is the presence of a bounds register per segment
    • But…
      • if we have a sparsely-used heap, we can still end up with a lot of page table waste
      • since most of the memory is managed in page-sized units, page tables can be of arbitrary size, and finding free space is complicated
  • Multi-level page tables
    • chop up the page table into page-sized units, then if an entire page of page-table entries is invalid, don’t allocate that page of the page table at all
    • Page directory
    • The page directory, in a simple two-level table, contains one entry per page of the page table
    • consists of a number of page directory entries (PDE)
    • A PDE (minimally) has a valid bit and a page frame number (PFN), similar to a PTE.
      • But the meaning of valid bit is different, if it is valid, it means at least one of the pages of the page table that the entry points to is valid
    • the multi-level table only allocates page-table space in proportion to the amount of address space you are using
    • each portion of the page table fits neatly within a page, making it easier to manage memory
    • level of indirection using the page directory, which points to pieces of the page tables
    • In the case of miss
      • two loads from memory will be required
        • one for the page directory, one for PTE itself
      • time-space tradeoff
      • complexity
    • To build a two-level page table for this address space, we start with our full linear page table and break it up into page-sized units.
    • As a result, we need four bits of the VPN to index into the directory; we use the top four bits of the VPN
    • page-directory entry (PDE) with a simple calculation: PDEAddr = PageDirBase + (PDIndex * sizeof(PDE)).
  • More than two-levels
  • Translation process
    • the physical address is formed directly without accessing the page table at all, as before. Only upon a TLB miss does the hardware need to perform the full multi-level lookup.
  • Inverted Page Tables
    • Even more extreme space saving in the world of page tables is found with inverted page tables
• some systems place such page tables in kernel virtual memory, allowing the system to swap some page tables to disk when memory pressure gets a little tight.

In summary, it also introduces increased complexity, potential memory overhead, challenges in address translation and memory protection, and fragmentation concerns, which need to be carefully considered and managed in the design and implementation of such a memory management scheme.

PTE → bit의 순서와 optimization