Working set model, thrashing: Foundations — Coding deep dive

This is the ground-floor page for the Working Set & Thrashing topic. We assume you have never seen any of this notation. We define each symbol in plain words, draw the picture it stands for, and say why the topic needs it — in an order where each idea rests on the one before.

0. The stage: memory is split into equal-sized boxes

Before any symbol, picture the two places your program's data can live.

RAM (physical memory) — the fast desk right in front of you. Small.
Disk (the swap area) — the slow shelf across the room. Huge.

Both are chopped into equal-sized chunks so the operating system can shuffle them cheaply.

Why the topic needs this: the whole working-set model is a story about which pages sit in which frames. Without the page/frame split there is no "should this stay in RAM?" question to answer. This connects directly to Demand Paging.

1. A "memory reference": the atom of everything

Every symbol later counts these, so we define it first.

Picture a program executing:

load  X     -> touches the page holding X
add   Y     -> touches the page holding Y
store X     -> touches the page holding X again

Each arrow above is one reference. A reference is not a second, not a byte — it is one access event.

Why the topic needs it: the working-set window $Δ$ is measured in these events, not in clock time. Getting this straight now prevents the classic " $Δ$ is in seconds" mistake later.

2. Virtual time $t$ : counting by references, not by clock

The symbol $t$ everywhere in the parent note ("ending at virtual time $t$ ") is just: how many references have happened so far.

3. The reference string: the program written as a list of pages

Each number is which page that reference hit. The position in the list is the virtual time: the " $5$ " in the fifth slot happened at $t = 5$ .

Why the topic needs it: this list is the raw input to every calculation in the parent note — computing $∣ W ∣$ , tracing faults, spotting locality. It is the program viewed purely through the lens of "what did it touch, and when?"

4. The window $Δ$ : how far back we look

Now the first Greek symbol. $Δ$ is spelled "delta" and here it is just a whole number.

Picture $Δ$ as a sliding window of fixed width gliding along the reference string. It always covers exactly $Δ$ entries (once we're past the start), and it moves right by one every time a new reference happens.

5. The set $W (t, Δ)$ and its size $∣ W ∣$

Two pieces of notation arrive together: the curly-brace set and the vertical-bar size.

Put together:

Worked micro-trace. Reference string $261577751$ , take $Δ = 5$ .

At $t = 5$ : the window holds pages $2, 6, 1, 5, 7$ → all distinct → $W = {2, 6, 1, 5, 7}$ , so $∣ W ∣ = 5$ . At $t = 7$ : the window holds $1, 5, 7, 7, 7$ → distinct pages are $1, 5, 7$ → $∣ W ∣ = 3$ .

Why the topic needs it: $∣ W ∣$ is the process's frame demand. Every allocation decision downstream is built on this single number.

6. Frames available $m$ , total demand $D$ , and the sum $\sum$

Last symbols before the punchline.

Now the parent note's headline formula reads in plain English:

See Multiprogramming Degree for how many processes we dare run at once, and Page Fault Handling for what happens on each miss.

7. How the foundations feed the topic

Read it top-down: an access event defines virtual time and the reference string; page/frame gives the vocabulary of what moves; the window $Δ$ slides over the string to build the set $W$ ; the set's size is the frame demand; summing demands gives $D$ ; comparing $D$ to $m$ is the whole topic.

Equipment checklist

Recall Am I ready? (reveal each — say it before you peek)

A page versus a frame ::: A page is a fixed-size block of virtual address space (the data); a frame is an equal-sized slot in physical RAM that holds one page. What "one memory reference" means ::: A single CPU read or write of one location; it lands inside exactly one page. The atom we count. What virtual time $t$ counts ::: The number of memory references that have happened — it ticks once per reference, independent of clock seconds. What a reference string is ::: The ordered list of page numbers touched, one entry per reference; position = virtual time. What the window $Δ$ is measured in ::: Memory references (virtual time), NOT seconds — a fixed-width count of the most recent accesses. What curly braces ${\dots}$ do to duplicates ::: Collapse them — a set keeps only distinct items, order ignored. What $∣ W (t, Δ) ∣$ tells the OS ::: The number of frames this process needs right now to run without heavy faulting. What $m$ and $D$ stand for ::: $m$ = frames available (supply); $D = \sum_{i} ∣ W_{i} ∣$ = total frames demanded by all runnable processes. Read $D > m \Rightarrow$ thrashing aloud ::: "If total demand exceeds available frames, the system thrashes" — it can't hold everyone's live pages, so it swaps instead of computing.