Virtual Memory, Paging, Working Set & Thrashing

Demand paging and locality

Virtual memory lets a process run with only part of its address space resident in physical frames; a missing page is fetched on demand when referenced, triggering a page fault. This works only because real programs obey the principle of locality — over any short interval they touch a small, slowly drifting cluster of pages (a loop body, the top of the stack, the current data block).

Address translation, the MMU & the TLB

Every address the CPU emits is a virtual (logical) address; it is translated to a physical address on every memory reference by the Memory Management Unit (MMU) — a dedicated hardware block inside the processor chip, not software and not part of RAM. The MMU does two things at once:

1. Translate — split the virtual address into a page number $p$ and a page offset $d$; use $p$ to index the page table, read the physical frame number $f$, and form the physical address by concatenating $f$ with the unchanged offset $d$.
2. Protect — check the access lies in a page the process owns and matches its permission bits (read / write / execute, user / kernel); a violation raises a hardware trap (page / protection fault) to the OS.

Because both run in hardware on each access, isolation between address spaces is enforced at full speed. The OS only configures the MMU (builds the page tables, reloads the page-table base register on a context switch); it never performs the per-access check itself. The TLB (translation look-aside buffer) caches recent $p\to f$ mappings so most references skip the page-table walk.

For a $v$-bit virtual address and a page of $2^{d}$ bytes, the offset is $d$ bits and the page-number field is $v-d$ bits, so a flat page table has up to $2^{\,v-d}$ entries.

Multilevel paging & segmentation

A flat page table for a large address space is enormous, so systems either use multi-level page tables (the page-number field is itself sliced into indices into a hierarchy of tables) or combine segmentation with paging. In the two-level segmentation+paging scheme the logical address carries three fields:

$\text{address}=[\,\text{segment}\;|\;\text{page number}\;|\;\text{offset}\,].$

To count translation-table rows, split the address by field width:

• an $s$-bit segment field $\Rightarrow$ the segment table holds up to $2^{s}$ rows;
• a $p$-bit page field $\Rightarrow$ each segment's page table holds up to $2^{p}$ rows;
• total $=\underbrace{2^{s}}_{\text{segment table}}+\underbrace{2^{s}\times 2^{p}}_{\text{one page table per segment}}$.

When the process has “at most $k$ segments” and $k$ is not a power of two, the field still needs $\lceil\log_2 k\rceil$ bits, so the table can address up to $2^{\lceil\log_2 k\rceil}$ segments (the maximum an exam asks for).

Mini-example (row counting)

16-bit address, at most 6 sections, 4 bits to address a page. Segment field $=\lceil\log_2 6\rceil=3$ bits $\Rightarrow$ up to $2^{3}=8$ segments, so the segment table has $8$ rows. Each page table has $2^{4}=16$ rows. (The remaining $16-3-4=9$ bits are the offset — page size $2^{9}=512$.) Maximum total rows:

$8+8\times 16 = 8+128 = 136.$

Counting only the page tables (forgetting the segment table) gives the classic wrong answer $128$; rounding 6 down to a 2-bit field gives $4+64=68$.

The working set

Locality is captured by the working set. Fix a window size $\Delta$ (a number of recent references). At time $t$:

$WS(t,\Delta)=\{\text{distinct pages referenced in } (t-\Delta,\; t]\}.$

Its size $WSS_i=|WS(t,\Delta)|$ is the working-set size of process $i$ — an estimate of how many frames it needs right now. The OS sums them, $D=\sum_i WSS_i$, and the working-set policy keeps a process resident only while it can be granted its full $WSS_i$; if $D>m$ (total physical frames) it suspends/swaps a process out to drive $D$ below $m$.

• Stable phase — inside a tight loop or a recursion that re-executes the same code/stack pages, no new page enters the window, so the working set can stay unchanged.
• Phase transition — when control moves to a new region, the working set jumps as fresh pages appear and stale ones age out of the window.

Thrashing

Thrashing is the pathological state where the system spends more time servicing page faults than doing useful work. It arises when the degree of multiprogramming is pushed too high: each resident process gets fewer frames than its working set demands, so it faults almost every reference, the paging disk saturates, CPU utilization collapses, and a mis-tuned scheduler reacts by admitting more processes — a positive-feedback spiral.

Note the symptom is necessary-looking, not sufficient: a busy paging disk with idle CPU suggests thrashing, but the same picture is produced by an ordinary I/O-bound job (a large file copy or sequential scan). High disk use alone never proves thrashing.

Controlling it: page-fault frequency (PFF)

Instead of measuring $WSS$ directly, watch each process's page-fault rate and keep it inside a target band $[L,U]$:

• rate above $U$ $\Rightarrow$ too few frames $\Rightarrow$ give it more;
• rate below $L$ $\Rightarrow$ spare frames $\Rightarrow$ take some away;
• if no free frame exists when a process is over $U$, suspend a process to free frames.

Belady's anomaly and stack algorithms

Intuitively, more frames should never increase faults — but with FIFO replacement, giving more frames can produce more faults. This is Belady's anomaly. It is avoided exactly by stack algorithms, whose resident set with $m$ frames is always a subset of the set with $m+1$ frames:

$\text{pages}(m)\subseteq \text{pages}(m+1).$

LRU and OPT (MIN) are stack algorithms and are immune; FIFO is not, and LFU is generally not a stack algorithm either, so LFU is not guaranteed immune to Belady's anomaly.

Mini-example (working set)

Reference string with window $\Delta=4$ (last 4 references):

ref:  c  c  c  d  d  c  c  d   (a recursive call reusing pages c, d)
WS:  {c}{c}{c}{c,d}{c,d}{c,d}{c,d}{c,d}

After the first transient the working set settles to $\{c,d\}$ and stays constant while the recursion keeps re-touching the same two pages — so the routine needs only 2 frames and never thrashes, however deep the recursion (as long as the active stack region fits the window).

Exam trick: Two traps recur here. (1) On address-translation counting, split the logical address into its fields and remember both levels — the total is $2^{s}+2^{s}\cdot 2^{p}$, so add the segment table (or the outer table), never just the page tables; and the MMU that walks them is hardware inside the CPU, not software and not in RAM. (2) On ‘which statement is correct?’ items, distrust absolutes — definitely thrashing, immune from Belady's — and favour the soft can/may: ‘the working set can stay unchanged during recursion’ is true, while ‘idle CPU + busy disk definitely means thrashing’ and ‘LFU is immune to Belady's anomaly’ are both overstated and false.