Thrashing and the Working Set

The idea: too little RAM means all faults, no work

Virtual memory lets processes use more memory than the machine has: pages that are not in RAM wait on disk and are read in on a page fault. That works while each process finds the pages it is using right now in RAM. When the pages that all processes are using right now no longer fit, the system starts thrashing: it spends its time moving pages between RAM and disk, and almost no work gets done.

The page models a small machine: 12 page frames, up to 5 processes that each loop over 4 pages, a paging disk that needs 10 ticks for one page-in, and global LRU replacement. One tick is one memory reference.

The working set W(t, Δ)

Peter Denning defined the working set W(t, Δ) of a process as the set of distinct pages it referenced in its last Δ references (the window). Its size is the WSS. Programs have locality: for a while they use a small set of pages, then move on to another. If Δ is large enough to cover one phase, W(t, Δ) is the set of pages the process needs in RAM to run without faulting.

The WSS is a property of the program, not of how much RAM it got. In the PROCESSES panel each process's working set stays {a, b, c, d}, WSS 4, even when only one of its pages is in RAM.

More processes help, until they do not

The degree of multiprogramming N is the number of processes sharing RAM. Each process here runs 4 references and then reads a file for 6 ticks. With one process the CPU is busy 4 ticks out of 10: 40%. A second process runs while the first one waits for its file: 80%. With three, there is almost always someone ready: 100%. Their working sets need 3 × 4 = 12 pages, exactly the 12 frames. (Demo 1: 3 processes fit in 12 frames.)

N	Σ WSS	CPU busy	page faults per 100 references	paging disk busy
1	4 ≤ 12	40%	0	0%
2	8 ≤ 12	80%	0	0%
3	12 ≤ 12	100%	0	0%
4	16 > 12	10%	50	100%
5	20 > 12	10%	50	100%

The numbers are measured over ticks 300 to 700, after the warm-up in which each process faults its pages in (Demo 3: CPU busy for 1 to 5 processes).

Thrashing: frames stolen in a circle

With 4 processes the working sets need 16 pages and there are 12 frames. A page-in must evict a page, and global LRU picks the least recently used frame of any process. Every process loops over its pages, so the least recently used page is always one that some process needs again within a few references. The page-in that ends one fault sets up the next fault.

1. P2 faults on b and waits in the paging disk queue behind the other processes' faults.
2. The disk reads b. RAM is full, and the least recently used frame holds P2's own c, the page P2 needs right after b.
3. P2 gets one hit on b, then faults on c and joins the end of the queue.
4. Meanwhile every other process is in the same queue. The disk is 100% busy; the CPU is idle.

Each page-in buys one hit before the next fault, so half of all references fault, and the CPU does useful work only during 1 tick out of every 10 (one page-in). Real disks are far slower than 10 memory references: a page-in from an SSD takes about 100 µs, a disk seek about 10 ms, while a memory reference takes about 100 ns. Real thrashing is much worse than these numbers. (Demo 2: a 4th process starts thrashing.)

Why "the CPU is idle, admit more" makes it worse

Early batch systems raised the degree of multiprogramming when CPU use was low, because low CPU use usually meant every process was waiting for I/O. In thrashing, CPU use is low because every process waits for the paging disk. A fifth process only adds its 4 pages to the demand: still 10% busy, and each process gets even less done.

What the OS does: load control

The fix is to run fewer processes, so that the ones that run have their working sets in RAM.

Approach	How it decides	Action
Working-set model	run a process only while Σ WSS of the running processes ≤ frames	suspend a process (free its frames); resume it when there is room
Page-fault frequency (PFF)	measure each process's fault rate against an upper and a lower bound	above the upper bound: give it frames; below the lower: take frames; no free frames: suspend a process
Local replacement	a process may evict only its own pages	one process's thrashing no longer steals other processes' frames

In the page, the working-set model keeps P1 to P3 running and P4 and P5 suspended: the CPU is 100% busy and no page faults happen. A real OS takes turns, so a suspended process runs later. (Demo 4: the working-set model suspends P4 and P5.)

Seeing it on Linux

Linux uses global replacement with active and inactive LRU lists, and has no working-set scheduler. Instead it shows the pressure, and in the end the OOM killer removes a process. Places to look:

• vmstat 1: the si/so columns (swap in/out) stay high, and wa (I/O wait) grows while us and sy fall.
• /proc/vmstat: pgmajfault counts page faults that needed disk; workingset_refault_anon and workingset_refault_file count pages read in again soon after they were evicted, which is the thrashing signal of mm/workingset.c.
• /proc/pressure/memory (PSI): the share of time tasks were stalled on memory. full means every non-idle task was stalled at once. systemd-oomd acts on these numbers.

See also page replacement (FIFO, LRU, Clock, OPT) for how one victim is chosen, virtual memory and page faults, the TLB and the page walk, CPU scheduling and process states.

When too many processes share too few frames, swapping turns into thrashing.

What the page leaves out

Programs whose locality changes over time (every process here keeps the same 4 pages); a real working-set estimate from reference bits and a virtual-time window; clean pages that can be dropped without a write and dirty pages that must be written first; how a suspended process's pages are written out and brought back; Linux's active and inactive lists, kswapd and the watermarks; and the many more frames and much slower disks of real machines.

References

P. J. Denning, The working set model for program behavior, CACM 1968

OSTEP, Beyond Physical Memory: Policies (thrashing and admission control)

Linux kernel documentation: PSI, Pressure Stall Information

Linux source: mm/workingset.c (refault distance and thrashing detection)