Thrashing and Belady's anomaly

Difficulty: Advanced

Question

What is thrashing and how do you prevent it? What is Belady's anomaly and which algorithms suffer from it?

Answer

These two topics are often paired because both are counterintuitive: one says that adding more processes can make the system slower, the other says that adding more memory can cause more page faults. Both are favourite advanced questions.

Start with thrashing. A system is thrashing when it spends more time swapping pages in and out than executing useful work. Imagine a student with a tiny desk trying to work on several books. Every time they open a book, they must put another one back, and then immediately need that other book again. They spend all their time shuffling books and no time reading. In an OS, this happens when the combined working sets of the running processes exceed the physical memory. Each process constantly faults, evicting frames that other processes are about to need. Processes then sit waiting for the paging disk, CPU utilization drops, and here comes the vicious part: the scheduler, seeing low CPU utilization, thinks the system is underloaded and admits more processes, which makes memory pressure worse, and CPU utilization collapses. On a graph of CPU utilization against degree of multiprogramming, utilization rises, peaks, and then falls off a cliff.

Locality of reference is the theory behind it. A process at any time uses a small set of pages, its locality, such as the code of the current function and the data it touches. Thrashing occurs when the memory allocated to a process is smaller than its current locality.

Prevention techniques include the working set model. Define the working set WS as the set of pages referenced in the most recent delta references. The OS tracks each process's working set size, and if the total demand exceeds available frames, it suspends one or more processes (swaps them out entirely) until the rest fit. The alternative is page fault frequency (PFF) control: set upper and lower bounds on the acceptable fault rate per process. If the rate goes above the upper bound, allocate the process more frames; if below the lower bound, take frames away; if no free frames remain, suspend a process. Other measures include using local rather than global replacement so one process's faults cannot steal another's frames, reducing the degree of multiprogramming, adding RAM, and improving locality in code by cache-friendly data structures, such as iterating a 2D array in row-major order.

Now Belady's anomaly. Intuitively, giving a process more frames should never increase its page faults. But for FIFO it can. The classic reference string is 1 2 3 4 1 2 5 1 2 3 4 5. With 3 frames, FIFO produces 9 page faults. With 4 frames, FIFO produces 10 page faults. Let me verify with 3 frames: faults at 1, 2, 3, 4, 1, 2, 5, then hits for 1 and 2, then faults at 3 and 4, and a hit for 5. That is 9 faults. With 4 frames: faults at 1, 2, 3, 4, then hits at 1 and 2, then faults at 5, 1, 2, 3, 4, 5 which is 4 + 6 = 10 faults.

Why does it happen? With FIFO, the set of pages in memory with n frames is not necessarily a subset of the set with n+1 frames, so the larger memory can evict a page that the smaller one still keeps, and that page gets used soon. Algorithms with the stack property, where the pages in memory with n frames are always a subset of those with n+1 frames, are immune. LRU and Optimal are stack algorithms and never show the anomaly. The second-chance algorithm, being FIFO based, can suffer from it.

For the interview, say clearly: thrashing is an operating regime problem solved with working sets or PFF, and Belady's anomaly is a property of certain replacement algorithms, mainly FIFO, that lack the stack property.

Code examples

Belady's anomaly with FIFO (Python)

from collections import deque

def fifo_faults(refs, frames):
    mem, q, faults = set(), deque(), 0
    for p in refs:
        if p not in mem:
            faults += 1
            if len(mem) == frames:
                mem.remove(q.popleft())
            mem.add(p)
            q.append(p)
    return faults

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for f in (3, 4):
    print(f"frames={f} faults={fifo_faults(refs, f)}")

More frames produced more faults, which is Belady's anomaly. Running the same experiment with an LRU implementation never shows this.

Key points

• Thrashing: the system spends more time paging than executing.
• Cause: total working sets exceed physical memory, often triggered by too much multiprogramming.
• Fixes: working set model, page fault frequency control, local replacement, fewer processes.
• Belady's anomaly: FIFO can fault more with more frames (1 2 3 4 1 2 5 1 2 3 4 5: 9 vs 10).
• Stack algorithms (LRU, OPT) never exhibit the anomaly.

Concepts covered

thrashing, Belady's anomaly, working set, page fault frequency, locality