Thrashing and the Working Set | Operating Systems

Thrashing

Thrashing occurs when a process spends more time paging (swapping pages in and out of memory) than executing. The CPU utilisation plummets because the I/O subsystem is overwhelmed by page-fault traffic.

Thrashing happens when the total working-set size of all runnable processes exceeds the available physical memory. Each process needs a minimum number of frames to hold its active pages. If even one process is short of frames, it page-faults frequently. But when one process faults, it blocks on I/O (another process runs, which also faults). The CPU is starved, and the kernel — seeing low CPU utilisation — may mistakenly admit more processes, worsening the problem.

The Working Set Model

A process’s working set at time $t$ is the set of pages that the process has accessed in the last $\Delta$ memory references:

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

$\Delta$ is the working-set window: a parameter that controls how far back the OS looks. A small $\Delta$ captures only the most active pages; a large $\Delta$ includes colder pages.

The working-set size $|\text{WS}(t, \Delta)|$ tends to be stable over long periods and changes abruptly at phase transitions (e.g., moving from one loop to another, or loading a different module).

Working-set page replacement

The OS can use working-set information to guide page replacement:

On a page fault (and periodically), compute each process’s working set.
If a page is not in the working set (its last reference is older than $\Delta$ ), it is a candidate for eviction.
If a process’s working set exceeds its allocated frames, the OS may need to give it more frames (or suspend it) to prevent thrashing.

The working-set algorithm is prepaging-capable: if the OS knows a process’s working set, it can bring those pages in before they are demanded, reducing cold-start faults.

Page-fault frequency (PFF)

A simpler thrashing-prevention strategy: monitor each process’s page-fault frequency. If the fault rate exceeds an upper threshold, give the process more frames. If it drops below a lower threshold, reclaim frames. Processes with high fault rates and insufficient frames are thrashing candidates; the system may suspend them until memory pressure eases.

The working-set model vs PFF

Model	Mechanism	Overhead
Working set	Track $\Delta$ references; compute WS periodically	High — must timestamp every reference, or use A-bit sweeps
PFF	Monitor page-fault rate; adjust frame allocation	Lower — fault rate is already tracked, no per-reference timestamps

Neither is used directly in modern Linux (which uses an LRU-based two-list scheme), but the conceptual frameworks are essential for understanding thrashing.

The intuition

Thrashing is a system-level pathology: it arises from the interaction between the scheduler (admitting more processes when CPU is idle) and the pager (evicting pages to satisfy demand, causing more faults). The feedback loop can spiral until the system is effectively dead. Prevention requires the OS to provide each process with enough frames to hold its working set — and to suspend or kill processes when that is not possible, rather than admitting more.

Summary

Thrashing: processes spend more time paging than executing; CPU utilisation collapses.
The working set is the set of pages referenced in the last $\Delta$ accesses; it captures the page locality of a process.
Working-set-based algorithms prevent thrashing by ensuring each process has enough frames for its working set.
PFF is a simpler alternative: adjust frame allocations based on observed fault rate.