Memory Management & Virtual Memory

Memory management exists because programs are written against addresses that do not correspond to physical locations.

The organising fact is that every scheme in this chapter answers one question: how does a virtual address become a physical address, and what happens when it cannot? Contiguous allocation answers with a base register. Paging answers with a table lookup. Demand paging adds the second half, which is a page fault.

Everything else follows from that question. Fragmentation is what happens when the mapping must be contiguous. The translation lookaside buffer exists because the lookup is otherwise too slow. Replacement algorithms exist because the answer to "what happens when it cannot" is that something must be evicted.

The second organising fact is a size hierarchy that all the arithmetic depends on. Fast memory is small and slow memory is large, and every design here is an attempt to get the speed of the small one at the capacity of the large one.

The third is that GATE questions in this area are almost entirely arithmetic, and the arithmetic is nearly always about splitting an address into fields or computing an expected access time.

1. Address Binding and Fragmentation

A logical address is generated by the CPU; a physical address is what the memory unit sees. The memory management unit performs the translation at run time.

Compile-time binding produces absolute code that must load at a fixed address. Load-time binding produces relocatable code fixed when loaded. Execution-time binding allows the process to move during execution and is what all modern systems use.

Contiguous allocation gives each process one block of memory, bounded by a base register and a limit register. Translation is one addition and one comparison.

Three placement policies choose which hole to use. First fit takes the first hole large enough and is fastest. Best fit takes the smallest adequate hole and leaves many tiny unusable fragments. Worst fit takes the largest hole and is generally the poorest performer.

External fragmentation is free memory split into pieces too small to use. The fifty-percent rule states that with first fit, about half as much memory is lost to fragmentation as is allocated.

Internal fragmentation is space wasted inside an allocated block, because the allocation unit is larger than the request.

Compaction removes external fragmentation by sliding processes together, and requires execution-time binding, since addresses change.

2. Paging

Paging divides logical memory into fixed-size pages and physical memory into frames of the same size, and allows any page to sit in any frame.

This eliminates external fragmentation entirely, since any free frame fits any page. Internal fragmentation remains, averaging half a page per process.

The logical address splits into a page number and an offset. With a page size of $2^n$ bytes, the low $n$ bits are the offset and the rest is the page number.

The page table maps page numbers to frame numbers, and the physical address is the frame number concatenated with the unchanged offset.

Each entry carries protection and status bits: valid or invalid, read-write permissions, a reference bit set on access, and a dirty or modify bit set on write.

The naive implementation needs two memory accesses per reference, one for the table and one for the data, which halves effective speed.

The translation lookaside buffer is a small fully associative cache of recent translations. On a hit, translation costs only the TLB lookup time. On a miss, the page table must be read.

Effective access time with a TLB is the hit ratio times the hit cost plus the miss ratio times the miss cost, and this formula appears in the exam almost every year.

3. Page Table Structures

A single-level page table becomes impossibly large for a large address space. A 32-bit space with 4 KB pages needs $2^{20}$ entries per process, and a 64-bit space is hopeless.

Hierarchical paging splits the page number into several fields, each indexing one level. Only the outer table must be resident, and inner tables covering unused regions need not exist at all.

The cost is one memory access per level on a TLB miss, so deeper hierarchies trade space for time.

A hashed page table hashes the virtual page number into a table of chains, and is used for large address spaces.

An inverted page table has one entry per physical frame rather than per virtual page, so its size depends on physical memory, not on the number of processes.

Its entries must record the process ID as well as the page number, since frames are shared across processes, and lookup requires searching rather than indexing, which is why it is paired with a hash table.

Inverted tables make sharing pages difficult, because one frame maps to only one virtual page in the table.

4. Segmentation

Segmentation divides the address space along logical lines into code, data, stack and so on, each a variable-length segment with its own base and limit.

A logical address is a segment number and an offset, and the offset is checked against the segment's limit before the base is added.

Segmentation matches the programmer's view and makes protection natural, since a whole segment can be marked read-only or shareable.

Its defect is external fragmentation, because segments are variable-sized and must be contiguous.

Segmented paging combines both: the address space is divided into segments, and each segment is paged. The segment table entry points to a page table rather than to memory.

This gives logical structure without external fragmentation, at the cost of two table lookups.

5. Demand Paging

Demand paging brings a page into memory only when it is referenced. The valid bit distinguishes pages present in memory from those on disk.

A reference to an invalid page traps to the kernel as a page fault, and the fault handler finds a free frame, reads the page from disk, updates the table, and restarts the faulting instruction.

The instruction is restarted, not resumed, which requires that faults be detected before any side effect, and is why some instruction sets are awkward to make demand-pageable.

Effective access time under demand paging is dominated by the fault rate, because a disk access is roughly a hundred thousand times slower than memory.

$\text{EAT}=(1-p)\times t_m+p\times t_f$

Here $p$ is the page fault rate, $t_m$ is memory access time and $t_f$ is the fault service time. Because $t_f$ is enormous, $p$ must be extraordinarily small for acceptable performance.

Copy-on-write is a demand-paging optimisation for fork, sharing frames read-only and duplicating only on a write.

6. Page Replacement

When a fault occurs and no frame is free, a victim must be chosen.

FIFO evicts the oldest page and is trivial to implement. It can evict a heavily used page merely because it arrived early.

Optimal replacement evicts the page whose next use is furthest in the future. It cannot be implemented, since it needs the future, but it gives the lower bound against which others are measured.

Least recently used evicts the page unused for the longest time, approximating optimal by assuming the recent past predicts the near future.

True LRU needs either a counter per entry or a stack of page numbers, both expensive, so systems approximate it.

The second-chance or clock algorithm scans frames in a circle. A frame with its reference bit set gets the bit cleared and is skipped; a frame with the bit clear is evicted. It is FIFO with a reprieve for recently used pages.

The enhanced version uses the reference and dirty bits together, preferring to evict pages that are neither referenced nor modified, since a clean page needs no write-back.

Belady's anomaly is that FIFO can produce more faults with more frames. It is counterintuitive and therefore heavily examined.

Stack algorithms do not suffer it. An algorithm is a stack algorithm if the set of pages resident with $n$ frames is always a subset of the set resident with $n+1$ frames. LRU and optimal have this property; FIFO does not.

7. Allocation and Thrashing

Frames must be divided among processes, either equally, proportionally to process size, or by priority.

Local replacement takes the victim from the faulting process's own frames; global replacement may take it from any process. Global gives better throughput but makes one process's behaviour affect another's fault rate.

Thrashing is a state in which processes spend more time paging than executing. It arises when the degree of multiprogramming rises past the point where each process can hold its actively used pages.

The feedback loop is vicious. High paging lowers CPU utilisation, the scheduler responds by admitting more processes, and the situation worsens.

The working set model defines the working set as the pages referenced in the most recent window of $\Delta$ references. If the sum of all working sets exceeds available frames, thrashing follows, and the fix is to suspend a process.

Page fault frequency control is the practical alternative: measure each process's fault rate and give it more frames when the rate is too high, take frames away when it is too low.

8. Worked Examples

Example 1. A system has 32-bit virtual addresses, 4 KB pages, and 4-byte page table entries. Compute the size of a single-level page table and then design a two-level scheme.

A 4 KB page needs 12 offset bits, since $4096=2^{12}$.

That leaves 20 bits of page number, so there are $2^{20}$ pages, which is about one million.

At 4 bytes per entry the table occupies $2^{20}\times 4=2^{22}$ bytes, which is 4 MB, per process. With a hundred processes that is 400 MB of tables alone.

For a two-level scheme, split the 20-bit page number. A natural split makes each inner table exactly one page: an inner table of $2^{10}$ entries at 4 bytes each occupies 4096 bytes, exactly one page.

So the split is 10 bits outer, 10 bits inner, 12 bits offset.

The outer table also has $2^{10}$ entries and occupies one page.

The saving comes from sparsity. A process using only a few megabytes touches a handful of inner tables, so it needs the 4 KB outer table plus a few 4 KB inner tables, perhaps 20 KB in total against 4 MB.

The cost is that a TLB miss now needs two memory accesses to walk the table instead of one.

Example 2. Memory access takes 100 nanoseconds and the TLB takes 20 nanoseconds. With a two-level page table and a 90 percent hit ratio, compute effective access time.

On a TLB hit, the cost is the TLB lookup plus one memory access for the data: $20+100=120$ nanoseconds.

On a TLB miss, the cost is the TLB lookup, two memory accesses to walk the two-level table, and one memory access for the data: $20+100+100+100=320$ nanoseconds.

Effective access time is $0.9\times 120+0.1\times 320=108+32=140$ nanoseconds.

Compare against 100 nanoseconds for direct access, so the overhead is 40 percent.

Now raise the hit ratio to 99 percent: $0.99\times 120+0.01\times 320=118.8+3.2=122$ nanoseconds, an overhead of 22 percent.

The lesson is how steeply the hit ratio matters, which is why TLB reach, the product of entries and page size, is a first-class design parameter.

Example 3. For the reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with three frames, count faults under FIFO, optimal and LRU.

Under FIFO, evict the oldest resident page.

References 7, 0, 1 fault and fill the frames. Reference 2 faults and evicts 7. Reference 0 hits. Reference 3 faults and evicts 0. Reference 0 faults and evicts 1. Reference 4 faults and evicts 2. Reference 2 faults and evicts 3. Reference 3 faults and evicts 0. Reference 0 faults and evicts 4. Reference 3 hits. Reference 2 hits.

That is 10 faults.

Under optimal, evict the page whose next use is furthest away.

7, 0, 1 fault. Reference 2 faults and evicts 7, which is never used again. Reference 0 hits. Reference 3 faults and evicts 1, whose next use is never. Reference 0 hits. Reference 4 faults and evicts 0, next used at position 11, versus 2 at position 9 and 3 at position 10. References 2 and 3 hit. Reference 0 faults and evicts 4. References 3 and 2 hit.

That is 7 faults, the lower bound.

Under LRU, evict the page unused longest.

7, 0, 1 fault. Reference 2 evicts 7. Reference 0 hits. Reference 3 evicts 1. Reference 0 hits. Reference 4 evicts 2. Reference 2 evicts 3. Reference 3 evicts 0. Reference 0 evicts 4. References 3 and 2 hit.

That is 10 faults on this string.

The ordering optimal at most LRU and FIFO always holds, though LRU and FIFO can tie or swap depending on the string.

Example 4. Demonstrate Belady's anomaly using the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

With three frames under FIFO:

1, 2, 3 fault. 4 faults, evicting 1. 1 faults, evicting 2. 2 faults, evicting 3. 5 faults, evicting 4. 1 hits. 2 hits. 3 faults, evicting 1. 4 faults, evicting 2. 5 hits.

Total: 9 faults.

With four frames under FIFO:

1, 2, 3, 4 fault. 1 hits. 2 hits. 5 faults, evicting 1. 1 faults, evicting 2. 2 faults, evicting 3. 3 faults, evicting 4. 4 faults, evicting 5. 5 faults, evicting 1.

Total: 10 faults.

More memory produced more faults, which is the anomaly.

The explanation is that FIFO's eviction order does not depend on usage, so the set of pages resident with four frames is not guaranteed to contain the set resident with three. Adding a frame changes which pages are old, and can push out a page that was about to be used.

LRU cannot do this because its resident set with $n$ frames is always the $n$ most recently used pages, which is a subset of the $n+1$ most recently used. That subset property is the definition of a stack algorithm.

Example 5. Memory access takes 100 nanoseconds and servicing a page fault takes 10 milliseconds. What page fault rate keeps degradation under 10 percent?

Target effective access time is $1.1\times 100=110$ nanoseconds.

Express the fault service time in the same units: 10 milliseconds is 10,000,000 nanoseconds.

Set up the equation $110=(1-p)\times 100+p\times 10,000,000$.

Expanding: $110=100-100p+10,000,000p$, so $10=9,999,900p$.

Therefore $p\approx 1.0\times 10^{-6}$, roughly one fault per million accesses.

Take a moment with that number. To lose only ten percent of performance, fewer than one access in a million may fault. This is why locality of reference is not a nice property but a precondition for virtual memory working at all.

Example 6. A system shows 5 percent CPU utilisation and 95 percent paging disk utilisation. Diagnose the situation and evaluate three proposed fixes.

The diagnosis is thrashing. The CPU is idle not for lack of work but because every process is blocked waiting for a page, while the disk is saturated with paging traffic.

Proposal one: increase the degree of multiprogramming. This is the trap, and it is what a naive scheduler does on seeing low CPU utilisation. More processes means fewer frames each, more faults, and worse thrashing.

Proposal two: install a faster CPU. No benefit whatsoever. The bottleneck is the paging disk, and the CPU is already idle 95 percent of the time.

Proposal three: install more memory, or reduce the degree of multiprogramming. Both work, because both increase the frames available per process until each can hold its working set.

The working set model explains why. If the sum of the working sets exceeds the number of frames, faults are unavoidable no matter how good the replacement algorithm is, because the actively used pages simply do not fit.

Suspending a process is the direct fix, since it frees its frames entirely and lets the remainder run without faulting.

Summary

Every scheme answers how a virtual address becomes a physical one and what happens when it cannot.

Execution-time binding is what modern systems use. Contiguous allocation uses base and limit registers, and suffers external fragmentation, with first fit fastest and best fit leaving many unusable slivers.

Paging eliminates external fragmentation and leaves internal fragmentation of about half a page per process. With page size $2^n$, the low $n$ bits are the offset and pass through translation unchanged.

The TLB caches translations, and effective access time is the hit ratio times hit cost plus miss ratio times miss cost. TLB reach, entries times page size, determines how much of the working set the TLB can cover.

Hierarchical page tables save space through sparsity and cost one memory access per level on a miss. Inverted tables are sized by physical memory rather than by process count, but complicate sharing.

Segmentation matches program structure and reintroduces external fragmentation; segmented paging combines both at the cost of two lookups.

Demand paging traps on an invalid reference and restarts the faulting instruction. Because fault service is about a hundred thousand times slower than memory, the fault rate must be around one in a million for ten percent degradation.

FIFO is simple and can suffer Belady's anomaly. Optimal is the unachievable lower bound. LRU approximates it and, like optimal, is a stack algorithm, so it cannot suffer the anomaly. Clock is the practical approximation, and the enhanced form prefers evicting clean pages.

Thrashing occurs when working sets exceed available frames, and the vicious loop is that low CPU utilisation tempts the scheduler to admit more processes. The fixes are more memory or fewer processes, never a faster CPU.