25-Comp-A5 Operating Systems · May 2018
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.
(a) Locality of reference. Real programs do not reference their address space uniformly at random; instead, over any short interval of execution, references cluster into a relatively small subset of pages. Temporal locality is the tendency to re-reference a recently-accessed location again soon (e.g. a loop counter or an accumulator variable touched on every iteration). Spatial locality is the tendency for references to cluster near recently-accessed addresses (e.g. sequentially scanning an array, or executing straight-line code in a function body). Together these two principles explain why a program's memory footprint at any instant — its working set — is typically far smaller than its total virtual address space, and why demand paging with a modest number of resident frames can still achieve a low fault rate: a well-localized program keeps re-touching the same handful of pages long before it needs a fresh one. This is the same underlying assumption that justifies hardware caches and TLBs: a small, fast structure only pays off if the reference stream it serves is itself localized, and real programs reliably are, because loops, arrays, and call-stack-local variables are the dominant memory-access idioms in ordinary code.
(b) Thrashing and its relationship to locality. Thrashing is the pathological state in which a process (or the whole system) spends far more time servicing page faults than executing useful instructions, because the number of frames allocated to it is smaller than the size of its current working set. Each instruction faults in a page it needs, and the very act of doing so evicts a page from the (already too-small) resident set that will be needed again within the next few references — that evicted page's own working set is violated, triggering yet another fault soon after, and so on. The system enters a self-reinforcing spiral: CPU utilization collapses (most processes are blocked on I/O waiting for page-ins), which naively looks like "we need more multiprogramming," but adding more processes only shrinks each one's frame allocation further and deepens the thrashing. The link to locality is direct: thrashing is precisely what happens when the allocated frame count falls below what a process's locality at that moment requires to avoid faulting on every reference; a process with poor locality (e.g. one that scans a huge data structure with no reuse) needs a proportionally larger frame allocation just to reach the same fault rate as a well-localized one.
(c) Working-set memory management. The working-set model makes locality an explicit, measurable quantity: $WS(t,\Delta)$ is defined as the set of distinct pages referenced in the most recent $\Delta$ virtual-time units (the window $\Delta$ is chosen to approximate the process's dominant locality interval). The OS tracks each process's working set size $|WS(t,\Delta)|$ and only admits/keeps running as many processes as can each be given at least their own working-set's worth of frames — if $\sum_i|WS_i(t,\Delta)|$ exceeds total available frames, the working-set manager suspends (swaps out) one or more processes rather than let all of them run underfed. For example, a process looping tightly over a 20-page inner array (its working set stabilizes near 20 pages once $\Delta$ spans a full loop iteration) is given at least ~20 frames; if a second process's own working set would push the combined demand over the frame budget, the OS defers that second process instead of admitting it and starving both. This directly controls thrashing because the admission decision is made before the fault storm starts, using locality (via $|WS(t,\Delta)|$) as the resource-sizing signal, rather than reactively discovering the shortage only after CPU utilization has already collapsed. A related practical technique, page-fault-frequency (PFF) control, monitors each process's live fault rate directly and grows or shrinks its frame allocation to keep that rate inside a target band, which is a cheaper approximation of the same idea when tracking the exact working-set window is judged too costly.
