Thrashing & Working Set Model

Page faults, and why too many are fatal

With virtual memory a process runs even though only some of its pages are in RAM. When it touches a page that is not there, a page fault occurs: the OS must read the page from disk, which takes about 100,000 times longer than a memory access. While one process waits, the OS runs another. That is why a few processes in memory keep the CPU busy.

The trouble begins when there are too many processes for the memory. Each one gets fewer frames than it needs. To load one process’s page the OS has to evict someone else’s page, and that page is needed again almost at once, causing another fault, which evicts another page… Soon nearly every memory access faults. The disk is saturated, the CPU is idle, and no program makes progress. This is thrashing.

Thrashing = the system spends more time paging than executing.

Locality: why a small number of frames is enough

Programs do not use all their pages at once. Over any short period, they stay inside a small locality: a loop and the arrays it touches, one function and its local variables. When the program moves on, the locality changes. This is the principle of locality, and it is why virtual memory works at all. A process runs without trouble if its current locality fits in memory. Thrashing means it does not.

The 3D experiment: adding processes

The first demo has a machine with 12 frames. Every process keeps using random pages out of 3 pages of its own (its locality). Pages are replaced by global LRU, so a fault can evict any process’s page. We add processes one at a time.

Processes n	Pages needed	Fault rate	CPU utilisation
1	3	2.0%	50.0%
2	6	2.0%	75.0%
3	9	2.0%	87.5%
4	12	2.0%	93.8%
5	15	24.5%	32.4%
6	18	39.3%	25.7%
7	21	48.1%	24.8%
8	24	66.4%	21.1%

The 2% at the start are only the first-touch faults (every page must be loaded once). Up to n = 4 all the localities fit: 4 × 3 = 12 pages in 12 frames. As processes are added, utilisation rises, because while one waits for the disk another can use the CPU. At n = 5, the demand (15 pages) exceeds the memory (12 frames) and the fault rate jumps by a factor of 12. CPU utilisation falls from 94% to 32%. With 4 pages per process the cliff arrives already at n = 4.

The utilisation column uses a standard model: if one process spends a fraction q of its time waiting for the disk, the CPU is idle only when all n processes wait, which happens a fraction qⁿ of the time, so utilisation is 1 − qⁿ. Here a fault costs as much as 50 memory references, so q = 50p / (1 + 50p) for fault rate p. The numbers come from the simulation, the cost of 50 is a simplification (in real life it is far bigger, so real cliffs are even steeper).

The vicious circle

Early schedulers reasoned “CPU utilisation is low, so there is spare capacity” and started more processes. In a thrashing system the low utilisation is caused by waiting for the disk, so more processes make things worse. This is why modern OSs control the degree of multiprogramming instead of just reacting to CPU use.

The working set model

Peter Denning’s working set model (1968) measures the locality directly. Fix a window of Δ (delta) memory references. The working set of a process at time t is

WS(t, Δ) = the distinct pages referenced in the last Δ references
WSS(t, Δ) = |WS(t, Δ)|          (its size: how many frames it needs right now)

In the second demo the process uses pages 1 2 1 3 2 4 1 2 3 1 4 2 | 5 6 5 7 6 5 7 6 5 5 7 6 | 2 8 2 3 8 2, a change of locality at t = 12 and again at t = 24. Take Δ = 6:

t	Page	Last 6 references	WS	WSS
11	2	1 2 3 1 4 2	{1, 2, 3, 4}	4
12	5	2 3 1 4 2 5	{1, 2, 3, 4, 5}	5
13	6	3 1 4 2 5 6	{1, 2, 3, 4, 5, 6}	6
14	5	1 4 2 5 6 5	{1, 2, 4, 5, 6}	5
16	6	2 5 6 5 7 6	{2, 5, 6, 7}	4

When the locality changes, the window briefly contains both the old and the new pages, so the WSS peaks (6 at t = 13). After a few references the old pages leave the window and the WSS drops. If the process has only 5 frames, it faults while the peak lasts.

Choosing Δ

• Δ too small (Δ = 4 here): the window forgets pages the program still uses. The WSS never exceeds 4, and the OS under-estimates the real need.
• Δ too large (Δ = 12): the window spans two or three localities, so the WSS stays at 7 for a long time. The OS over-estimates the need and wastes memory.
• A good Δ covers the current locality only.

Using it to prevent thrashing

The OS computes the working-set size WSS_i of each process and the total demand D = Σ WSS_i. Let m be the number of frames.

• D > m: the demand is greater than the memory. Pick a process and suspend it (swap all its pages out). The remaining processes get enough frames, and the suspended one resumes later.
• D ≤ m: there is room. Start or resume another process.

So the system never admits more processes than the memory can hold, and the cliff in the first demo is never reached. Real systems cannot track every reference, so they approximate the working set with a reference bit that the hardware sets on each access and the OS clears at timer intervals.

Page-fault frequency (PFF)

A simpler alternative is to watch each process’s page-fault rate. If it exceeds an upper bound, give the process more frames. If it falls below a lower bound, take some away. If no frame is free when a process needs more, suspend a process.

Cures at a glance

Remedy	How it helps
Lower the degree of multiprogramming	Fewer processes, so each gets its working set
Working-set model	Admit processes only while Σ WSS ≤ frames
Page-fault frequency control	Adjust each process’s frames from its fault rate
Local replacement	A thrashing process cannot steal frames from others (but it can still thrash itself and keep the disk busy)
More RAM, better locality	Bigger memory or code that touches fewer pages at a time

Code

from collections import OrderedDict

def mulberry32(seed):
    """A tiny seeded random generator (the same one the 3D model uses, so the numbers match)."""
    a = seed & 0xFFFFFFFF
    def imul(x, y):
        return (x * y) & 0xFFFFFFFF
    def rand():
        nonlocal a
        a = (a + 0x6d2b79f5) & 0xFFFFFFFF
        t = imul(a ^ (a >> 15), a | 1)
        t ^= (t + imul(t ^ (t >> 7), t | 61)) & 0xFFFFFFFF
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296
    return rand

FRAMES = 12      # physical frames shared by all processes
SERVICE = 50     # one page fault costs as much time as 50 memory references

def fault_rate(n, w, rounds=150, seed=11):
    """n processes, each using random pages of its own locality of w pages; global LRU replacement."""
    rand = mulberry32(seed)
    memory = OrderedDict()                       # least recently used first
    faults = total = 0
    for _ in range(rounds):
        for p in range(n):
            page = (p, int(rand() * w))
            total += 1
            if page in memory:
                memory.move_to_end(page)         # hit: now the most recently used
            else:
                faults += 1
                if len(memory) >= FRAMES:
                    memory.popitem(last=False)   # evict the LRU page, whoever owns it
                memory[page] = True
    return faults / total

def cpu_utilisation(p, n):
    """The CPU is idle only when ALL n processes wait for the disk: 1 - q^n."""
    q = p * SERVICE / (1 + p * SERVICE)          # share of time one process spends waiting
    return 1 - q ** n

for n in range(1, 9):
    p = fault_rate(n, 3)
    print(f'n={n} demand={3 * n:2} faults={p:6.1%} CPU={cpu_utilisation(p, n):6.1%}')
# n=1 demand= 3 faults=  2.0% CPU= 50.0%
# n=2 demand= 6 faults=  2.0% CPU= 75.0%
# n=3 demand= 9 faults=  2.0% CPU= 87.5%
# n=4 demand=12 faults=  2.0% CPU= 93.8%
# n=5 demand=15 faults= 24.5% CPU= 32.4%
# n=6 demand=18 faults= 39.3% CPU= 25.7%
# n=7 demand=21 faults= 48.1% CPU= 24.8%
# n=8 demand=24 faults= 66.4% CPU= 21.1%

REFS = [1, 2, 1, 3, 2, 4, 1, 2, 3, 1, 4, 2, 5, 6, 5, 7, 6, 5, 7, 6, 5, 5, 7, 6, 2, 8, 2, 3, 8, 2]

def working_set(refs, t, delta):
    """The distinct pages among the last `delta` references up to time t."""
    return sorted(set(refs[max(0, t - delta + 1): t + 1]))

for delta in (4, 6, 12):
    print(delta, [len(working_set(REFS, t, delta)) for t in range(len(REFS))])
# 4 [1, 2, 2, 3, 3, 4, 4, 3, 4, 3, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 3, 3]
# 6 [1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 4, 5, 5, 5, 4, 3]
# 12 [1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 6, 5, 4, 3, 4, 5, 5, 6, 6, 6]
print(working_set(REFS, 13, 6))
# [1, 2, 3, 4, 5, 6]

Common mistakes

• Blaming the CPU. Thrashing shows up as low CPU use and a busy disk. Adding CPU power or processes does not help.
• Thinking local replacement cures thrashing. It protects other processes, but a process with too few frames still thrashes by itself.
• Confusing the working set with the resident set. The working set is what the process needs (measured from its recent references); the resident set is the pages it has in memory.
• Using the wrong window size. Too small forgets live pages, too large mixes localities. Neither describes the true locality.
• Believing more multiprogramming is always better. Utilisation rises only while the combined working sets still fit in memory.