CST334 Week 4

The fourth week of CST 334 expanded on how memory is virtualized.

Paging is how modern OSes virtualize memory. Instead of keeping track of each segment’s base and bound, the OS maintains a page table. A “page” is a small block of memory that is allocated in same-size chunks. For example, a page on Windows is typically 4KB. Breaking memory up into identically sized pieces greatly simplifies the allocation process; though, paging’s greatest strength is the memory footprint reduction it brings. The old method of tracking base and bounds had some massive flaws: virtual address spaces had to completely fit into memory, and segments had to stay contiguous. To understand how paging fixes these issues, let us briefly detail how paging works.

The upper bits of a virtual address represent a virtual page number (VPN), with the lower bits acting as an offset into that page. Now, to translate a virtual address into a physical one, the VPN must be translated into its corresponding physical page number (PPN). This is done using a “page table” instance, which the OS maintains for every process. Page tables are stored in memory, as their size prevents them from being stored on the CPU in cache. However, as you might imagine, having to access the page table every time a memory access occurs is prohibitively expensive. So, the CPU’s MMU provides what is known as the TLB cache. Instead of querying the page table every time a memory access occurs, the CPU first checks if the TLB cache contains a mapping for the VPN being accessed. If it does, the CPU can continue without having to query the page table. However, if the TLB does not contain a mapping, the CPU must trap into the OS to have the TLB filled with the required value.

This mechanism — trapping into the OS on a TLB miss — is what makes paging so powerful. In essence, the OS can now react to a memory access to currently unloaded memory. This enables some powerful behaviors, such as loading pages on-demand instead of all at once. This also makes it possible for the OS to implement a swap file. When memory pressure is being applied, the OS can now unload pages from memory and copy them to disk. If a process attempts to access a deloaded page and incurs a TLB miss, the OS reloads the page from disk and the process continues, oblivious to the fact that its memory access just caused IO.