Virtual Memory and Page Replacement

Virtual memory lets a process use more memory than physically exists. With demand paging, a page is loaded from disk only when it is first used. Each page-table entry has a valid bit: if a process touches a page that is not in memory, the hardware raises a page fault.

Handling a page fault

Page faults are very expensive because disk access takes milliseconds, while memory access takes nanoseconds:

EAT = (1 − p) × memory access time + p × page-fault service time

With 200 ns memory access and an 8 ms (8,000,000 ns) fault service time, even p = 0.001 (one fault per 1000 accesses) gives EAT = 0.999 × 200 + 0.001 × 8,000,000 ≈ 8,200 ns: about 40 times slower than memory.

Page-replacement algorithms

When memory is full, the OS must choose a victim page to evict:

• FIFO: evict the page that has been in memory longest.
• Optimal (OPT): evict the page that will not be used for the longest time in the future. It gives the fewest faults possible, but needs the future, so it is used only as a benchmark.
• LRU (least recently used): evict the page unused for the longest time in the past, approximating OPT by assuming the recent past predicts the near future.

def fifo(refs, frames):
    memory, queue, faults = set(), [], 0
    for page in refs:
        if page not in memory:
            faults += 1
            if len(memory) == frames:
                memory.remove(queue.pop(0))      # oldest page out
            memory.add(page)
            queue.append(page)
    return faults

def lru(refs, frames):
    memory, faults = [], 0                       # least recently used at the front
    for page in refs:
        if page in memory:
            memory.remove(page)
        else:
            faults += 1
            if len(memory) == frames:
                memory.pop(0)
        memory.append(page)
    return faults

def optimal(refs, frames):
    memory, faults = [], 0
    for i, page in enumerate(refs):
        if page in memory:
            continue
        faults += 1
        if len(memory) == frames:
            future = refs[i + 1:]
            victim = max(memory, key=lambda p: future.index(p) if p in future else len(refs))
            memory.remove(victim)
        memory.append(page)
    return faults

refs = [1, 3, 0, 3, 5, 6, 3, 1, 2, 0, 1, 2]
for algo in (fifo, lru, optimal):
    print(f"{algo.__name__:7} with 3 frames: {algo(refs, 3)} faults")

belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("FIFO 3 frames:", fifo(belady, 3), "faults; FIFO 4 frames:", fifo(belady, 4), "faults")
print("LRU  3 frames:", lru(belady, 3), "faults; LRU  4 frames:", lru(belady, 4), "faults")

fifo    with 3 frames: 9 faults
lru     with 3 frames: 8 faults
optimal with 3 frames: 7 faults
FIFO 3 frames: 9 faults; FIFO 4 frames: 10 faults
LRU  3 frames: 10 faults; LRU  4 frames: 8 faults

Belady's anomaly

Normally, more frames means fewer faults. But for FIFO the reference string above gives more faults with 4 frames than with 3: this is Belady's anomaly. LRU and OPT are stack algorithms (the pages in memory with n frames are always a subset of those with n + 1 frames), so they never suffer from it.

Thrashing and the working set

If processes do not have enough frames for the pages they are actively using, they fault constantly, the CPU sits idle waiting for the disk, and the OS may even add more processes to "use the idle CPU", making it worse. This collapse is thrashing.

The working set of a process is the set of pages it referenced in the last Δ references. Giving each process enough frames for its working set, and suspending processes when the total demand exceeds memory, prevents thrashing.

GATE-style practice questions