Notes based on Operating Systems: Three Easy Pieces by Remzi & Andrea Arpaci-Dusseau

Virtualizing the Memory: Memory Management

Apart from virtualizing the CPU, an OS must also be able to enable sharing of another important resource across processes - the memory. Processes require memory space to hold all of their runtime data, and it would be way too slow if we save/restore the entire memory content upon every context switch, especially when we are time-sharing the CPU (frequent switches). Hence, the OS must be able to do space-sharing of the memory: put all processes’ in-memory data in the physical memory, and somehow let a process know how to address a byte it wants. Upon a context switch, we just switch the registers so that they point to correct addresses for the switched process. The OS must provide protection, efficiency in addressing, and a way to handle insufficient space if the physical memory is running out.

Abstraction of Address Space

To enable the space-sharing of memory, we again turn to virtualization. We give each process an illusion of the ability to address across its own memory space, which could be huge and sparse. This abstraction is called the address space of the process - it is the running program’s view of memory (virtual memory, VM) and is completely decoupled with what the DRAM chip actually provides (physical memory). A program uses virtual address to locate any byte in its address space.

Address Space Layout

An OS must give a clear definition of the address space layout it expects. Conventionally, an address space contains the following segments and is structured in the following way:

Code: the program’s machine code (the instruction); PC always points to somewhere in this segment Static data: holding global static data, could be further separated into initialized region (so read-only) and uninitialized region (so writes allowed) Stack: the function call stack of the program to keep track of where it is in the call chain; function calls form a stack of frames, where the local variables of a function resides in its frame; SP & FP always point to somewhere in this segment; stack grows negatively Heap (data): for dynamically allocating runtime, user-managed memory (e.g., when calling malloc()); heap grows positively (optional) OS kernel mapped: the kernel could also be mapped into every process’s address space (probably into the higher half), and is thus shared across processes

In reality, size of the virtual address space typically depends on the number of bits the hardware platform uses for addressing. If the hardware operates on 32-bit numbers, we could use an entire range from 0x00000000 to 0xffffffff. The virtual address space could be very huge in size and very sparse (mostly empty) - this is not a problem. It is just the process’s view on memory but we are not putting this space directly on physical memory at address 0. The OS will have some way to map the occupied bytes in the address spaces of all processes onto physical memory, which we will talk about in the next section.

This layout is just a convention for single-threaded processes. There could be other arrangements and things could be more complicated when a process becomes multi-threaded, which we will talk about in the concurrency section.

Memory APIs

These are the interfaces in C programming on UNIX systems for user programs to allocate memory. Other platforms might have different interfaces but they share the same spirit.

Implicit (automatic) allocation of function call stack memory, containing local variables & local data

Explicit, dynamic allocation of heap memory for large or long-lived, dynamic-size data

brk(), sbrk() - the primitive syscalls for changing (enlarging or shrinking) the heap data segment end-point bound; since memory allocation is tricky, user programs should never call these syscalls directly, but should rather use the library functions described below malloc(), calloc(), realloc(), free() - normally, C programs link against a standard library which contains higher-level routines (wrapping over the brk syscalls) for allocating heap memory regions; these are not syscalls but are library functions with sophisticated allocation policies (using the syscalls as mechanism) mmap(), munmap() - create/unmap a memory region for mapping a file or a device into the address space, often in a lazy manner, as an alternative I/O mechanism With the malloc() + free() interface, here is a list of common memory errors in C programming:

Forgetting to allocate memory and using an uninitialized pointer variable (wild pointer) Not allocating enough memory (buffer overflow) Not initializing allocated memory to known state (uninitialized read) Forgetting to free memory (memory leak) Accessing memory after it’s freed (dangling pointer) Freeing memory repeatedly (double free) Freeing incorrect memory addresses They often lead to the infamous segmentation fault (SEGFAULT) which happens when accessing a memory address the process shouldn’t touch. Beware that code compiles & runs no segfault does not mean it runs semantically correctly - you could be accessing incorrect (but valid) memory addresses, which is still a serious bug.

Address Mapping & Translation

Every address a user program sees is virtual. The OS makes the virtual memory system transparent to users and implicitly translates any address a process asks for into physical memory. This is the procedure of (hardware-based) address translation and it implicitly implies the address mapping scheme the OS adopts. Here we list three address mapping and translation schemes. For efficiency, the OS makes use of hardware support (from a few register to full page table support) instead of simulating everything in software.

The idea of interposition is really powerful and essential in systems. When virtualizing the CPU, the hardware timer sends timer interrupts to interpose the execution of a process to let the OS re-gain control periodically; this enables transparent time-sharing of the CPU. When virtualizing the memory, the hardware MMU interposes on each memory access to perform address translation; this enables transparent space-sharing of the memory.

We will discuss three address translation schemes, along with some complementory knowledge:

Base & Bound

Segmentation

Paging

Base & Bound

Let’s first assume that the address spaces are small and compact, so it can fit in physical memory contiguously. With this assumption, the most intuitive way of address mapping is to simply relocate the address space to start at some offset in physical memory. The base & bound method (BB, or dynamic relocation, or hardware-based relocation) makes use of two hardware registers:

Base register: the starting offset the OS decides to put the current process’s address space at Bound register: the size (limit) of the current process’s address space

Upon a context switch to a process, the two registers get loaded the base & bound values for this process. This step requires OS intervention to decide where to relocate (where is base). Along its execution, upon any memory access, the address translation is done by the hardware directly. This part of hardware (doing address translations) is often named the memory management unit (MMU).

The MMU algorithm for base & bound is obviously simple:

if virtual_addr >= bound:

raise out-of-bound exception

else:

physical_addr = virtual_addr + base

Without hardware support, purely software-based relocation is not so great. We could let a loader scan through the machine code of the executable file and change add a base value to every address it sees at process loading. However, this approach lacks protection and is not flexible.

Hardware/OS Responsibilities

A brief summary of hardware support we have talked about so far:

Two privilege modes - OS code runs in privileged kernel mode and user program runs in user mode MMU registers, specifications, and the translation algorithm Privileged instructions only to be executed in kernel mode (e.g., updating base/bound) Privileged instructions to register trap/exception handlers Ability to raise hardware exception upon invalid memory access, … And the OS must take these responsibilities for virtual memory to work:

Free space management: finding free space for new processes and reclaiming memory back at termination, via some sort of free-list data structures Upon context switch: setting proper MMU register states (e.g., base & bound values) Exception handling: decide what to do upon memory access exceptions the hardware reports, probably terminating the offending process or handling the fault if that is an innocent fault

Segmentation

The base & bound approach has an obvious drawback: it requires that the physical memory has a big, contiguous chunk of empty space to hold the address space of a process. However, our address space could be huge and sparse, so it might not fit in as a whole. And all the unused bytes are still mapped, wasting a lot of memory space. Segmentation is a generalized form of base & bound which eases this problem.

A segment is a a contiguous portion of the address space. We could break the code, stack, & heap into three segments, then for each of them, apply base & bound independently. This way, only used memory is allocated space in physical memory.

One problem thus arise: given a virtual address, how does the hardware know which segment it is referring to (so that it can do the base & bound check)? There are two approaches:

Explicit: we chop the address space into fixed-sized segments, so that the highest several bits of a virtual address is the segment ID and the remaining bits is the offset in the segment (as we will see soon, this is an early form of paging)

The MMU algorithm thus goes:

segment_id = virtual_addr >> SEG_SHIFT offset = virtual_addr & OFFSET_MASK if offset >= bounds[segment_id]:

raise out-of-bound exception

else:

physical_addr = offset + bases[segment_id]

Implicit: the hardware detects how an address value is derived, and determines the segment accordingly (e.g., if an address value is computed by adding something to PC, it should be referring to the code segment)

Some extra support from hardware could be added:

Negative-growth bit for stack: since stack grows negatively, this bit indicates offset should be calculated into a negative value Protection (permission mode) bits for sharing: some systems support sharing segments across processes (e.g., if code is the same, could share the code segment with read-exec permission)

Concept of Paging

Chopping things into variable-sized segments can make free-space management very challenging. Most modern OSes take a more generalized approach of explicit segmentation called paging: chopping the address space into fixed-sized, relatively small pieces, in size of say 4KB. Each of such pieces is called a page (or virtual page). Physical memory is also chopped into pieces of the same size. To allocate space for a page, the OS allocates a physical frame (or physical page) to hold the page.

Paging offers these advantages over previous approaches:

Flexibility: no assumptions on how the address space layout is defined; we just map in-use pages to frames; for example, the heap can grow arbitrarily non-contiguously if we want Simplicity: pages are in fixed size, so the allocation and tracking of free frames will be much easier

The OS must maintain a per-process data structure to record the current mapping from pages to their allocated physical frames. This data structure is called the page table. A page table is essentially a mapping table from virtual page number (VPN) to physical frame number (PFN, or PPN). Assume page size is a power of 2:

Any virtual address can be split into two components: VPN of the page & offset in the page

#bits for offset #bits for VPN #bits per address #bits for offset // Say page size is 16 bytes, and a virtual address is 6 bits // -> Within a page, we need 4 bits to index a byte // -> Offset is the least significant 4 bits // (where am I in the page?) // -> VPN is the most significant 2 bits // (which page?) 0b 01 0101 // example virtual address in binary // |–||––| // VPN offset Address translation is now the process of translating VPN into PFN, and offset stays the same:

The size of DRAM on the machine determines the number of physical frames available, which in turn determines how many bits we need for PFN. Just like in segmentation, multiple processes could share a same physical frame (possibly as different virtual page addresses), one good example being sharing a common code page.

Linear Page Tables

Due to efficiency issues, dynamic data structures like linked lists or hash tables are generally out of concern for implementing a page table. Let’s first consider the simplest form of a linear (flat) page table: a one-level array of page table entries (PTE). The OS indexes the array by VPN, and each PTE holds the PFN for that VPN and a few necessary control bits:

Valid bit (V): whether this VPN is in-use (mapped) or unused; if a translation finds an invalid PTE (valid bit unset), it means the process is trying to access a page not mapped yet, and the hardware raises the famous exception named page fault to trap into OS kernel, which then decides how to deal with this access. The OS could check the faulty address and decide whether to allocate memory for the new page or just terminate the process Present bit (P): this relates to swapping, which we will talk about in the advanced paging section; present bit unset (but valid bit set) means the page is mapped but currently swapped out of memory to disk; (our x86 example only has present bit but no valid bit, because it triggers a page fault as long as page is not present, and leaves the OS to keep track of whether the page is swapped out or is simply not valid) Protection bits (R/W, etc.): indicate whether the page is readable, writable, and/or executable; for example, modifying a read-only page will trigger an exception to trap to the OS Dirty bit (D): if page is writable, has it been modified since brought to memory (useful for page replacement in swapping or when caching mmap’ed files) Reference bit (R), or Access bit (A): used to track whether a page has been accessed (useful for helping page replacement in swapping)

The page table in this form can be incredibly large (e.g., 4MB page table per 32-bit process address space) and cannot fit in hardware MMU. Thus, the page tables themselves are stored in memory, specifically somewhere in kernel-reserved memory. Hardware MMU just keeps a page-table base register (PTBR) to record a pointer to start of the current process’s page table, and upon a translation, go to that location on memory. The MMU algorithm goes:

VPN = virtual_addr >> ADDR_PN_SHIFT offset = virtual_addr & ADDR_OFFSET_MASK PTE_addr = PTBR_reg + (VPN * sizeof(PTE)) PTE_content = *PTE_addr # goes to memory (or hits TLB) if any_control_bit_violation:

raise page-fault or permission exception

else:

PFN = PTE_content >> PTE_PFN_SHIFT
physical_addr = (PFN << ADDR_PN_SHIFT) | offset

We will talk about useful techniques on saving space and speed up translations in the advanced paging section.

Free-Space Management Policies

In the above sections, we haven’t really answered this question: how does the OS find proper free space when it needs to enlarge/allocate something? How to manage free space efficiently? We use the name fragmentation to describe the situation where there is space wasted in an address mapping scheme.

Internal fragmentation: unused bytes in the address space getting mapped External fragmentation: small free spaces being left over between two mapped regions, which can hardly be used to map something else; there is no single contiguous free chunk, though the total number of free bytes is enough Different address translation schemes have different behaviors with regard to the two types of fragmentation. Fragmentation is hard to eliminate completely, but we can try to do better.

Base & bound has both serious external fragmentation and internal fragmentation Segmentation has no internal fragmentation, but has external fragmentation (if w/o periodic garbage collection/compaction, useful but very expensive operations) Paging has no external fragmentation, but has a little bit of internal fragmentation (worse with larger page size) Note that the problem of free-space management is generic. It applies to how a malloc() library allocates new bytes on heap, how an OS allocates physical memory for new segments, etc. Here we list a few classic free-space management policies.

Splitting & Coalescing

Suppose we keep a free list data structure as a linked list of free spaces. Two mechanisms play a significant role in all allocator policies:

Splitting: when a small request comes, split an existing large chunk, return the requested size and keep the remaining chunk

Coalescing: when a piece of memory is freed and there is free chunk next to it, merge them into one big free chunk

Basic Policies

These are the most basic, intuitive policies for memory allocation:

Best-Fit: search through the free list and find the smallest free chunk that is big enough for a request (possibly with splitting)

Advantage: intuitive, nearly optimal Disadvantage: expensive to do exhaustive search Worst-Fit: find the largest chunk, split and return the requested amount, keep the remaining chunk

Advantage: if using a max-heap, finding the largest chunk could be fast Disadvantage: performs badly, leading to excess fragmentation First-Fit: find the first block that is big enough, split and return the request amount

Advantage: fast, stops early Disadvantage: tends to pollute the beginning of the free list with small objects; address-based ordering could help Next-Fit: just like first-fit, but instead of always starting from the beginning, maintains a pointer to remember where it was looking last; start the search from there

Advantage: same efficiency advantage as first-fit Disadvantage: requires keeping an extra state There is hardly any perfect free space allocation policy in general, because we could always construct a worst-case input of requests (adversarial input) to mess it up. We can only compare their pros and cons.

Segregated Lists

If a particular application has one (or a few) popular-sized request it makes, keep a separate list just to manage objects (i.e. free chunks of fixed size) of that size. All other requests are forwarded to a general memory allocator, say running one of the above policies. The slab allocator (see here) used in Solaris and Linux kernel is one such example.

When the kernel boots up, allocate a number of object caches for possibly-popular kernel objects, e.g., locks, inodes, etc. When a given cache is running low on free space, itself requests some slabs of memory from a general allocator, the amount being a multiple of its object’s size When a given cache is going empty, it releases some of the spaces back to the general allocator Objects in the cache can also be pre-initialized so that the time for initialization and destruction at run time is saved.

Buddy Allocation

The binary buddy allocator (see here) is designed around splitting & coalescing in sizes of 2, allowing some internal fragmentation but making the coalescing procedure much more efficient.

In the beginning, the allocator holds a one big space of size 2 When a request comes, the search for free space recursively divides free space by 2, until the smallest power of 2 that is big enough for the request is found When that block is freed, the allocator checks if its buddy block (the one produced by the last split, its sibling block) is free; if so, it coalesces the two blocks; this procedure repeats recursively up the tree until the top of the tree is reached, or until a level where the buddy is in use

We are particularly interested in binary buddy allocation, because it fits the binary address representation on most architectures so well. The address for a block differs with the address of its buddy block in just one bit (which bit depends on its level), so we can have highly-efficient implementations using bit-wise operations. Of course, there could be higher-order buddy allocation.

For scalability issues on multiprocessors, concurrent data structures are being used in modern memory allocators to speed up concurrent accesses on the free list and to reduce the steps for synchronization. We will touch these in the concurrency section.

Advanced Paging

We have talked about basic paging with linear page tables, but they are not very efficient. It requires extra memory read for every memory access (notice that fetching an instruction is also a memory access), which almost doubles the latency penalty. The page tables take up a lot of space, but most pages in an address space are probably unused. We now talk about techniques to optimize paging.

Translation Lookaside Buffer (TLB)

A translation lookaside buffer (TLB) is a cache for address translation - it is part of the hardware MMU for storing several popular PTE entries with fast access speed (e.g., in SRAM instead of DRAM). Like all caches, it assumes that there is locality in page accesses (code instructions tend to be sequentially executed, etc.), so there tend to be popular pages at a given time.

At a context switch to a new process, if we do not have an address-space ID (ASID) field in TLB entries, the TLB must be flushed (i.e., emptied, all invalidated)

Upon an address translation, the MMU checks if the TLB holds the translation for this VPN (and ASID matches):

If yes, it is a TLB hit, and we just extract the PFN from the relevant TLB entry

If no, it is a TLB miss, and we have to go to the page table on memory to perform the translation

After getting the PFN for a TLB miss, we need to decide whether to put the translation for this VPN into TLB; if so and if the TLB was full, it triggers a replacement, and we need to choose a victim entry to replace

Since memory accesses are so common, page lookups happen so frequently, thus we would like to minimize the chance of TLB misses as much as possible (i.e., maximizing the hit rate). Also, one problem remains as who should handle TLB misses.

Hardware-managed TLB: old hardware architectures handle TLB misses entirely in hardware; hence, they need to strictly define the page table format they expect Software-managed TLB: with the impact of RISC architectures, modern architectures raise a fault and trap into OS kernel to let the OS decide how to handle a TLB miss; this allows the OS to define its own page table structures more flexibly, but we must be careful not to let the execution of the trap handler cause chained (cascading) TLB misses, by e.g. keeping the trap handler always accessible bypassing the TLB, or reserve some wired TLB entries for the handler

Multi-Level Page Tables

Now we focus on making the page tables smaller. The main observation is that most of the pages in a sparse address space are unmapped, yet they still take up a PTE slot. To ease this issue, we use multi-level page tables: breaking the page table into multiple levels of indirection. Suppose we use two levels:

The top level is often called a page directory: it is still an array, but in a coarser granularity; it is indexed using the higher bits of VPN, and instead of recording PFNs, they record pointers to sub-level page tables; each entry in the top-level, here could call them page directory entries (PDE), represent a subarray of a linear page table The leaf level is a sub-table indexed using the lower bits of VPN; they store actual PFNs To fit better in memory, every table (at any level) itself takes up the space of a page; so the number of branches per level page size size of PTE; when a sub-table turns active, the OS just need to allocate a page for that

As you can see, if pages in an entire sub-table are unmapped, that sub-table (and it’s children) won’t be allocated at all, saving a lot of space. The virtual address split and the MMU algorithm goes (looking up a multi-level page table is often called walking a page table):

VPN = virtual_addr >> ADDR_PN_SHIFT PDI = VPN >> VPN_PDI_SHIFT PTI = VPN & VPN_PTI_MASK offset = virtual_addr & ADDR_OFFSET_MASK

index the page directories

PD_start = PTBR_reg for levels of page directories:

PDE_addr = PD_start + (PDI * sizeof(PDE))
PDE_content = *PDE_addr  # goes to memory (or hits TLB)
PD_start = (PDE_content >> PDE_PFN_SHIFT) << ADDR_PN_SHIFT

index the leaf-level page table

PT_start = PD_start PTE_addr = PT_start + (PTI * sizeof(PTE)) PTE_content = *PTE_addr # goes to memory (or hits TLB) if any_control_bit_violation:

raise page-fault or permission exception

else:

PFN = PTE_content >> PTE_PFN_SHIFT
physical_addr = (PFN << ADDR_PN_SHIFT) | offset

Two factors here require careful tradeoff between page table size and translation latency performance (time-space tradeoff):

#Levels of page tables: more levels saving more space, but slower translation (more memory accesses) Page size: larger pages fewer pages, smaller tables, possibly faster lookups, but worse internal fragmentation; modern systems do support multiple page sizes, and allow smarter applications to ask for using so-called hugepages on demand A more extreme space-saving technique is to have an inverted page table, which is a global (one) mapping from physical frames to its currently mapped virtual address space & page. Hash tables could be built upon it to enable address translations.

Concept of Swapping

Now let’s consider the situation where the physical memory space is running low and we cannot find a free physical frame to put a new page. This is when swapping is needed: writing some pages to persistent storage to free up frames. Swapping is at its essence a caching problem.

The OS takes out a certain region of a block storage device’s space (say an HDD) as the swap space. Let’s assume that the block device has block size equal the page size of our VM system. A PTE with valid bit set but present bit unset means it is mapped, but currently swapped out to disk. With swapping enabled, the name page fault sometimes narrowly refers to accessing a valid but swapped page, requiring the OS the handle the fault and bring the page back. An example snapshot of system state:

Page out: moving a page from memory to disk Page in: moving a page from disk back to memory Page replacement (or eviction in general caching): when we access a swapped page but the memory is nearly full, we first need to choose a victim page to page out, then page in the requested page to that frame The mechanism of swapping is transparent to user processes, just like almost everything in our VM system. Be aware that, no matter how smart your page replacement policy is, if your workload demands way more memory than the actual physical memory size, paging in/out will happen and they are slow. In this case, the best solution is to buy more memory.

Swapping only at full could be dangerous and could trigger thrashing (or throttling). The OS can have a background process named the swap daemon or page daemon that monitors the free ratio of physical memory. If there are fewer than low watermark (LW) frames free, the daemon starts swapping out pages, until there are high watermark (HW) frames free.

Linux also has an out-of-memory (OOM) killer that kills processes when memory is nearly (but not exactly) full. These are examples of admission control and they help prevent thrashing.

Page Replacement Policies

Accessing a block on a disk is significantly slower than accessing the memory, and is sensitive to sequentiality, thus the page replacement policies must be smart enough to avoid disk reads/writes as much as possible. These policies more generally fit in any caching systems and there are so many of them. Read this wikipedia page and this post if interested.

Optimal (MIN, OPT)

Given perfect knowledge of the workload (memory access pattern), we could derive a theoretically optimal (but quite unpractical) policy that minimizes the miss rate: always replace the page that will be accessed furthest in the future. The optimal hit rate is probably not 100%: you at least have a cold-start miss (compulsory miss). Having an optimal hit rate serves as a good baseline to evaluate other policies.

First-In-First-Out (FIFO)

Simple, intuitive, but generally does not perform well. FIFO suffers from a phenomenon called Belady’s Anomaly: enlarging the cache size could possibly make hit rate worse. Policies like LRUs do not suffer from this problem.

Random (RAND)

Simple and works pretty well in some cases. The strongest thing about random is that its does not suffer from any particular adversarial input - there’s is no special input sequence guaranteed to trigger horrible performance on random, but there are for any other deterministic policy. The downside is of course its non-determinism (performance instability).

Least-Recently-Used (LRU) and Least-Frequently-Used (LFU)

Do accounting on the recency and/or frequency of page accesses, and choose the least-recently used or least-frequently used page. LRU is the most classic caching algorithm that works well in most cases and is very understandable and intuitive. Its downside is that it does not have scan-resistance: if our working set is just slightly larger than the cache, a scanning workload could trigger a miss for every access. Keeping account of recency/frequency is also expensive.

Second-Chance FIFO and Clock

Second-Chance is an example of efforts on approximating LRU while throwing away the accounting for time/frequency. It works as a FIFO but clears the access bit on a page at the first chance, giving it a second chance. Please see the post for details. Clock is an implementation optimization to Second-Chance to make it even more efficient. Clock algorithm could also be enhanced with dirty bits to prioritized pages that aren’t modified (so no need to write back to disk).

Many more advanced caching policies…

Given an average miss rate of , we can calculate the average memory access time (AMAT) for a page as:

, where is the latency of reading from memory and is the latency of reading from disk. Even a tiny bit of increase in builds up AMAT because is generally much larger than .

So far we assumed demand paging (or lazy paging), meaning that we only bring a page to memory the first time it is accessed. Some systems deploy prefetching of nearby pages ahead of time when a page is accessed.

The system also do clustering (or grouping) of write-backs so that a sequence of pages next to each other are evicted in one sequential request to disk, yielding better throughput performance, as we will learn in the persistence section.

Caching Everywhere

We have touched on the important idea of caching several times, a concept that should have been well explained in computer architecture courses. Caching is critical to the performance of modern computer systems.

Memory Hierarchy

In general, on any architecture that forms a memory hierarchy: different levels of storage from faster, smaller, volatile storage to slower, larger, persistent storage, caching brings benefits. The typical memory hierarchy in modern machines has at least the following layers:

Private L1 & L2 CPU cache Shared L3 CPU cache across cores On-chip SRAM for TLB, etc. DRAM as the main memory Persistent memory Fast block devices (NVMe SSDs, etc.) Data over the network Slow block devices (HDDs, etc.) Caching is based on the observation that data accesses tend to have spatial locality & temporal locality:

Spatial locality: a data access tends to be followed by accesses to nearby data around it, in some pattern Temporal locality: a certain range of data tends to be accessed repeatedly in a period of time, in some pattern Hence it would be beneficial if we maintain certain hot (popular) pieces of data in a faster, smaller, upper layer while keeping the majority of data in a slower, larger, lower layer of storage.

Examples of Caching

Quite a few concepts covered in this note are just instances of caching:

CPU cache: fast SRAM over DRAM TLB for paging: SRAM over DRAM Swapping: DRAM over persistent storage File system page cache (block cache): DRAM over persistent storage On-disk cache: on-disk DRAM over persistent media … For caching to work well, a smart (and suitable) policy is a must to maximize hit rate (= minimize miss rate). Caching has been a long line of research and there are tons of caching policies with different characteristics. Please read this post if interested.

See Chapter 23 of the book for a case study on two real-world operating systems’ virtual memory management: DEC VAX/VMS and the Linux VM.