• memory-intensive programs can spend as much as 30%-40% of their instructions on memory access, and in most cases (unless cache is virtually tagged), the physical address must be determined before any actual data can be accessed

• so, many common-case operations for address translation are implemented in dedicated hardware (e.g. TLBs)
• less performance critical and more sophisticated management functions are left to OS

1. A Typical Paging-Based Virtual Memory Subsystem

• small granularity
• flexible on where to locate data and access permission for each data structure
• overhead on metadata to track VM states

• large granularity
• inflexible to manage data structure
• ❓memory fragmentation
• ❓why paging can solve fragmentation problem by allow pages to be swapped between primary and secondary storage
• less overhead on metadata to track VM states

• virtual address space is divided into pages and page frames
• page: contiguous region of VM managed as single unit
• page frame: contiguous region of physical memory managed as single unit

• demand paging
• pages brought into primary memory by OS when requested by the user

• page size
• base page size
• x86, ARM: 4KB
• SPARC: 8KB
• VAX11: 512B
• superpage
• any page size supported in architecture that is larger than the base page size, may be as gigabyte
• if page size is bits, then lower N bits of input virtual address are unmodified to be physical address, the upper bits are translated.

2. Page Table Basics

• if only one level page table, for 48bit VA with 4KB page size, need for page table.

• few application uses entire virtual address space, multi-level page table can reduce page table size
• for level N, if the process not access the page, then the corresponding page table entry can be empty, and the related lower level page table entry no need to be allocated

• page table walk: traversing the levels of page table (walk means pointer chasing to access different levels of page table)

• how multi-level page table work
• page table walk starts from PT_BASE (page table base address), which is unique to each process
• [47:39] as an offset from the PT_BASE for 1st level page table entry
• entries in 1st level page table entry is the base address of 2nd level page table entry
• [38:30] as an offset for 2nd level page table entry
• repeats the procedure until final page table entry which holds the physical page number, permissions, status bits etc.

• page table level number
• 32-bit x86: 2/3 levels to translate 32-bit VA to 40/52 bit PA
• 64-bit x86 and ARM: 4 levels to translate 48-bit VA to 52 bit PA

• multi-level page table is convenient for mixed page size
• an intermediate page table entry can points directly to physical address if page size is larger than 4KB

3. Translation Lookaside Buffers (TLBs)

• “lookaside”: TLB is accessed in parallel with cache

• if no TLB, then each memory access need table walk and require more memory bandwidth
• x86-64 is generally a four-level page table, if no TLB, each memory access will become five accesses
• and the access cannot be paralleled to reduce overall latency because page table walk is pointer chasing

• many processor uses a hierarchy of TLBs to cache translation, the lowest latency but smallest TLBs are placed directly next to each CPU, and larger (but higher-latency) TLBs are placed farther away
• Intel Skylake server cpu: 64 entries for L1 TLBs, 1536 entries for L2 TLBs
• Cortex A73: 48 entries for L1 TLBs (micro TLB), 1024 entries for L2 TLBs (main TLB)

4. Page and Segmentation Faults

• minor page fault
• the page frame is present in physical memory, but the translation was not present (or not with sufficient permissions) in the page table (a page is allocated but not yet accessed)
• ❓already mapped page frame is being given a second mapping
• ❓handling writes to copy-on-write pages

• major page fault
• the desired data is not present in memory and it must be fetched from backing storage

• when page fault occurs, CPU assists the OS to diagnose the problem
• e.g. CPU provides some control/status register to indicate fault address, the access type (read/write/instruction fetch), user-level/kernel-level
• after page fault is resolved, the memory access that triggers the page fault is replayed
• when replay, the page table walk will lookup the newly inserted page table entry

• the requested virtual address is illegal
• the VA is not allocated, try to write to a page with no write permission
• buffer overflows, dereference a null or already-deallocated pointer
• the only safe thing after a segmentation fault is to simply terminate the process

5. Segmentation

• virtual address is split into several logical segments
• typical segments: code, data, stack, heap
• virtual address is formed by combining a segment number and an offset within the segment

• OS maintains a segment table to map the segment number to segment information (e.g. base physical address of the segment, the limit of the segment, protection bits and permission bits). Each memory access will consult segment table for physical address.
• lookup failure results in segmentation fault (this term persists even in paging-based VM)

• metadata overhead
• Segmentation is one segment for an entire region, paging is one page table for each page, so segmentation is much lower overhead than paging

• fine-grained memory protection
• a region of memory cannot be shared with another process with different permissions if using segmentation

• memory fragmentation
• inefficient arrangement of the segments in memory can lead to wasted space
• segments can grow size dynamically(so cannot packing several segments tightly), and spacing segments too far leads to memory between two segments wasted

6. Summary