Thrashing and the working set

Why it exists

If a process does not have enough frames for the pages it is actively using, it faults, replaces a page it needs again almost at once, faults again, and spends nearly all its time waiting for the disk. This is thrashing. It is not just slow: it can make the whole system collapse, because the operating system sees low CPU utilization and responds by admitting more processes, which take frames from the others and make things worse. The cure is to give each process enough frames for its working set, and to reduce the number of processes when there are not enough frames for all. GATE asks for working-set sizes from a reference string, for the condition that avoids thrashing, and for the allocation of frames.

Prerequisites

You need the fault rate, page replacement and the idea that the disk is much slower than memory from page replacement and virtual memory.

Precise definitions

Thrashing. A process (or the system) is thrashing when it spends more time paging than executing: a very high page-fault rate with little useful work. The CPU is mostly idle, waiting for the disk.

The vicious circle. A scheduler that watches CPU utilization sees it fall when processes wait for page faults, concludes that the degree of multiprogramming is too low, and admits more processes. Each new process takes frames from the others (with global replacement), so they fault more, utilization falls further, and more processes are added. CPU utilization rises with the degree of multiprogramming up to a point and then collapses.

Locality. A locality is the set of pages a process uses together over a period (a procedure, its local data, the array it is scanning). A program moves from one locality to another as it runs, and localities may overlap. A process thrashes if its current locality does not fit in its allocated frames. Demand paging works because locality makes the fault rate low when the locality fits.

Working-set model. Fix a window $\Delta$ (a number of the most recent page references). The working set $WS(t)$ of a process at time $t$ is the set of distinct pages in the most recent $\Delta$ references. The working-set size is $WSS = |WS(t)|$.

• If $\Delta$ is too small it does not cover the locality; if too large it spans several localities; if infinite it includes the whole program.
• $WSS \le \Delta$ always (there are only $\Delta$ references in the window), and $WSS \le$ the number of distinct pages of the program.
• The working set changes by at most one page per reference (the new page may enter, the one leaving the window may leave).

Using the working set. If $WSS_i$ is the working-set size of process $i$, the total demand for frames is

$D = \sum_i WSS_i.$

If $D > m$ (the number of available frames), thrashing will occur: the operating system suspends (swaps out) one or more processes until $D \le m$, which lowers the degree of multiprogramming. If $D < m$ it can start another process. This keeps as many processes as possible running without thrashing. The difficulty is keeping track of the working sets; it is approximated with a periodic timer interrupt and the reference bit (pages whose bit was set in the last interval are in the working set).

Page-fault-frequency (PFF) scheme. Measure each process's fault rate directly. Set an upper bound and a lower bound: if a process's rate exceeds the upper bound, it needs more frames: give it one (or, if none are free, suspend a process); if the rate falls below the lower bound, it has too many: take a frame away. This keeps the rates in a band. It is simpler than tracking working sets.

Allocation of frames. Each process needs a minimum number of frames (set by the instruction set architecture: an instruction that can refer to several pages needs them all resident). The rest is divided:

• Equal allocation: $m/n$ frames to each of $n$ processes.
• Proportional allocation: process $i$ of size $s_i$ gets $a_i = \dfrac{s_i}{S}\,m$ frames, with $S = \sum s_i$ (rounded, and at least the minimum). Sometimes based on priority instead of, or as well as, size.

Global versus local replacement. With global replacement a process may take a frame from another; with local replacement it replaces only among its own. Local replacement gives predictable behaviour for each process and confines thrashing to the thrashing process, but may leave frames unused; global replacement gives better throughput but lets one process disturb the others.

How it works

The animation computes the working set with $\Delta = 4$ along the reference string 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6. At each reference the window is the last four references and the working set is the set of distinct pages in it. Watch the working-set size: it grows to 4 as new pages arrive (1, 2, 3, 4 give sizes 1, 2, 3, 4) and falls to 3 when a page repeats inside the window (the second 2 at reference 5). A process whose allocation is below its current working-set size thrashes; one with 4 frames is safe throughout this string.

Worked examples

#include <stdio.h>
 
static int wss(const int *refs, int t, int delta) {
    int count = 0;
    for (int i = (t - delta + 1 < 0 ? 0 : t - delta + 1); i <= t; i++) {
        int seen = 0;
        for (int j = (t - delta + 1 < 0 ? 0 : t - delta + 1); j < i; j++) if (refs[j] == refs[i]) seen = 1;
        if (!seen) count++;
    }
    return count;
}
 
int main(void) {
    int refs[20] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6};
    printf("working-set size with window 4 after each reference:");
    for (int t = 0; t < 20; t++) printf(" %d", wss(refs, t, 4));
    printf("\n");
    /* thrashing check: total demand D = sum of working-set sizes against the m frames available */
    int w[4] = {6, 10, 14, 20}, m = 40, d = 0;
    for (int i = 0; i < 4; i++) d += w[i];
    printf("demand D = %d pages, frames m = %d: %s\n", d, m, d > m ? "D > m, the system thrashes: suspend a process" : "D <= m, no thrashing");
    int suspend = 3;                                 /* suspend the process with the largest working set */
    printf("after suspending the process with WSS %d: D = %d <= %d\n", w[suspend], d - w[suspend], m);
    /* proportional allocation of m = 60 frames to processes of 15, 30 and 105 pages */
    int size[3] = {15, 30, 105}, total = 150, frames = 60;
    printf("proportional allocation of %d frames:", frames);
    for (int i = 0; i < 3; i++) printf(" %d", size[i] * frames / total);
    printf("\nequal allocation:");
    for (int i = 0; i < 3; i++) printf(" %d", frames / 3);
    printf("\n");
    return 0;
}

working-set size with window 4 after each reference: 1 2 3 4 3 4 4 4 4 4 3 3 4 4 3 4 4 3 3 4
demand D = 50 pages, frames m = 40: D > m, the system thrashes: suspend a process
after suspending the process with WSS 20: D = 30 <= 40
proportional allocation of 60 frames: 6 12 42
equal allocation: 20 20 20

Cheat box

Traps and GATE patterns

Connections

Thrashing is what happens when page replacement has too few frames to work with; its cost comes from the page-fault service time of virtual memory. The decision to suspend a process is made by the medium-term scheduler (CPU scheduling), moving the process out of the Ready and Running states (process states).

PYQs

A virtual memory system uses First In First Out
(FIFO) page replacement policy and allocates a
fixed number of frames to a process. Consider the
following statements:

P: Increasing the number of page frames allocated
to a process sometimes increases the page fault rate.

Q: Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

Increasing the RAM of a computer typically improves
performance because:

Self-check

Revision card

References