Virtual memory and page replacement

Virtual memory lets a process run with only some of its pages in memory; the rest wait on disk. Programs can be bigger than memory, and more programs fit at once. With demand paging, a page is loaded only when it is first used.

A page fault

When the program touches a page whose page-table entry is marked invalid (not in memory), the MMU traps: a page fault. The kernel then:

1. checks the access is legal (if not, the process is stopped: a segmentation fault),
2. finds a free frame, or chooses a victim page to throw out,
3. reads the page from disk into the frame (the process waits meanwhile, and another one runs),
4. updates the page table and marks the entry valid,
5. restarts the instruction that faulted, which now succeeds.

Faults are expensive

A memory access takes about 100 ns; a page fault, which reads the disk, takes milliseconds. With fault rate p:

EAT = (1 − p) × memory time + p × fault time

With 200 ns memory and an 8 ms fault: even one fault in 1000 accesses gives 0.999 × 200 + 0.001 × 8,000,000 ≈ 8,200 ns, 40 times slower. Keeping the fault rate tiny is everything.

Choosing the victim

When every frame is full, a page-replacement algorithm picks the page to remove:

This is the standard textbook reference string, with 3 frames: FIFO gives 15 faults, LRU 12, Optimal 9. Step through each algorithm, and open Compare to see all frame counts.

Real hardware cannot afford to note the time of every access, so systems approximate LRU with a reference bit that the hardware sets on each use. The second-chance (clock) algorithm goes round the frames like a clock hand: a page with its bit set gets the bit cleared and a second chance; the first page with the bit clear is the victim.

A dirty bit saves work: a page that was not changed since it was loaded need not be written back to disk when it is removed.

Belady's anomaly

You would expect more frames to mean fewer faults. With FIFO, not always. For the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO has 9 faults with 3 frames and 10 with 4. Type it into the simulator and try. LRU and Optimal never do this.

#include <stdio.h>

#define FRAMES 3

int main(void) {
    int refs[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
    int n = sizeof refs / sizeof refs[0];
    int frame[FRAMES] = {-1, -1, -1};
    int oldest = 0, faults = 0;   /* the next frame FIFO replaces */

    for (int i = 0; i < n; i++) {
        int hit = 0;
        for (int f = 0; f < FRAMES; f++)
            if (frame[f] == refs[i]) hit = 1;
        if (!hit) {
            frame[oldest] = refs[i];          /* empty frames fill in order too */
            oldest = (oldest + 1) % FRAMES;
            faults++;
        }
    }
    printf("FIFO, %d frames: %d page faults in %d references\n", FRAMES, faults, n);
    return 0;
}

Thrashing

If processes have too few frames for the pages they are actively using, nearly every access faults. The CPU sits idle waiting for the disk, so the OS, seeing low CPU use, starts more processes, which makes it worse. This is thrashing. The cure is to give each process at least its working set, the pages it used in the recent past, and to run fewer processes if they do not fit.

#include <stdio.h>

#define FRAMES 3

int main(void) {
    int refs[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
    int n = sizeof refs / sizeof refs[0];
    int frame[FRAMES], last_used[FRAMES];
    int used = 0, faults = 0;

    for (int i = 0; i < n; i++) {
        int found = -1;
        for (int f = 0; f < used; f++)
            if (frame[f] == refs[i]) found = f;
        if (found >= 0) {
            last_used[found] = i;              /* a hit: just note the time */
            continue;
        }
        faults++;
        int slot = used;
        if (used < FRAMES) {
            used++;                            /* a free frame */
        } else {
            slot = 0;                          /* the least recently used frame */
            for (int f = 1; f < FRAMES; f++)
                if (last_used[f] < last_used[slot]) slot = f;
        }
        frame[slot] = refs[i];
        last_used[slot] = i;
    }
    printf("LRU, %d frames: %d page faults in %d references\n", FRAMES, faults, n);
    return 0;
}

Mark lesson complete