Virtual Memory

Wikipedia · Virtual memory · CC BY-SA 4.0

Demand paging

Pages are not loaded until accessed. The first access triggers a page fault: the OS loads the page from disk into a free frame, updates the page table, and resumes the instruction. Most programs exhibit locality, so page faults are rare after warmup.

Page replacement algorithms

FIFO: evict the oldest page. Simple but suffers Belady's anomaly (more frames can mean more faults). LRU: evict the least recently used page. Good performance but expensive to track precisely. Optimal: evict the page that will not be used for the longest time. Impossible to implement (requires future knowledge) but useful as a benchmark.

; FIFO page replacement simulation

(define (fifo-replace refs num-frames)
  (define frames '())
  (define faults 0)

  (define (step refs)
    (if (null? refs)
        faults
        (let ((page (car refs)))
          (if (member page frames)
              (begin
                (display page) (display ":hit ")
                (step (cdr refs)))
              (begin
                (set! faults (+ faults 1))
                (if (< (length frames) num-frames)
                    (set! frames (append frames (list page)))
                    (set! frames (append (cdr frames) (list page))))
                (display page) (display ":FAULT ")
                (step (cdr refs)))))))

  (let ((total (step refs)))
    (newline)
    (display "Total faults: ") (display total) (newline)
    (display "Total refs: ") (display (length refs))))

(fifo-replace '(7 0 1 2 0 3 0 4) 3)

# LRU page replacement
from collections import OrderedDict

def lru_replace(refs, num_frames):
    frames = OrderedDict()
    faults = 0
    log = []
    for page in refs:
        if page in frames:
            frames.move_to_end(page)
            log.append(f"{page}:hit")
        else:
            faults += 1
            if len(frames) >= num_frames:
                frames.popitem(last=False)  # evict LRU
            frames[page] = True
            log.append(f"{page}:FAULT")
    print(" ".join(log))
    print(f"Total faults: {faults}/{len(refs)}")

lru_replace([7, 0, 1, 2, 0, 3, 0, 4], 3)

Thrashing

When a process has too few frames, it faults on almost every access. The OS spends more time swapping pages than executing instructions. This is thrashing. The fix: give the process more frames, or reduce the degree of multiprogramming.

Working set

The working set is the set of pages a process has referenced in the last N memory accesses. If the OS keeps the working set in memory, page faults stay low. The working set model prevents thrashing by refusing to run more processes than memory can support.