Virtual Memory

The concurrency topic measured three models on the same workload, and all three silently assumed one thing: every address a process touches is already sitting in memory. Hardware gives no such guarantee. A process’s address space can exceed the machine’s physical memory, and when five processes run at once, their combined footprint almost always does.

This lesson builds the abstraction that closes that gap and counts its cost. The Memory Layout lesson in How Computers Work already defined the address space, the stack, and the heap; that definition is not repeated here. The one addition is this: when the address space does not sit directly on real memory, every access passes through a translation, every translation that comes up empty produces a page fault, and page faults can be counted.

Virtual Pages and Physical Pages

Virtual memory is the abstraction that separates the address space a process sees from the machine’s physical memory. The separation is built on fixed-size units: the address space is divided into equal-size virtual pages, physical memory into equal-size physical pages, and a page table tracks which virtual page sits in which physical page. This arrangement is called paging.

The baseline without the abstraction states itself in one sentence: if there are as many physical pages as virtual pages, the mapping is one-to-one, the table is never searched, and after the first load no access ever goes to disk. In the common definition’s workload the address space is 16 virtual pages, and the access sequence produced by five processes touches 15 of them. The baseline is fetching those 15 pages once.

• BD1 — The machine is the common definition’s model: a 16-virtual-page address space, a five-process workload, and seed 20260218. No real operating system is invoked.
• BD2 — The access sequence is produced from the processes’ compute steps in time order; wait steps never touch memory.
• BD3 — Fetching a page from disk is one wait step, that is, 30 time units. A compute step is one time unit.
• BD4 — Page table lookup is free in the model; the only thing measured is faults. On a real machine, table lookup would also carry a cost, and this lesson does not count it.

"""M01/K05 common definition (excerpt): workload and virtual page access sequence."""
SEED = 20260218
PROCESS_COUNT = 5
STEP_COUNT = 12
WAIT_TIME = 30
VIRTUAL_PAGES = 16


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def workload(seed=SEED):
    r = generator(seed)
    jobs = []
    for i in range(PROCESS_COUNT):
        steps = []
        for _ in range(STEP_COUNT):
            if r(10) < 3:
                steps.append(("WAIT", WAIT_TIME))
            else:
                base = (i * 3) % VIRTUAL_PAGES
                steps.append(("COMPUTE", (base + r(4)) % VIRTUAL_PAGES))
        jobs.append({"name": f"P{i+1}", "step": steps,
                     "priority": 1 + r(3), "arrival": i * 4})
    return jobs


def access_sequence(jobs):
    events = []
    for j in jobs:
        t = j["arrival"]
        for kind, value in j["step"]:
            if kind == "COMPUTE":
                events.append((t, value))
                t += 1
            else:
                t += value
    events.sort(key=lambda e: e[0])
    return [s for _, s in events]


SEQUENCE = access_sequence(workload())
print("accesses:", len(SEQUENCE), "| distinct virtual pages:", len(set(SEQUENCE)))
print("sequence:", SEQUENCE)
for window in (4, 8, 16):
    widths = [len(set(SEQUENCE[i:i + window])) for i in range(len(SEQUENCE) - window + 1)]
    print(f"window {window:2d} working set average {sum(widths)/len(widths):5.2f} "
          f"widest {max(widths):2d}")

accesses: 39 | distinct virtual pages: 15
sequence: [6, 9, 11, 9, 11, 9, 12, 1, 3, 1, 6, 9, 7, 9, 0, 2, 0, 5, 2, 3, 0, 5, 2, 3, 5, 3, 8, 9, 6, 4, 13, 12, 15, 13, 8, 12, 14, 12, 7]
window  4 working set average  3.47 widest  4
window  8 working set average  5.75 widest  8
window 16 working set average  9.25 widest 11

The last three lines give the working set: the number of distinct pages touched inside a window. In a four-access window the average is 3.47 distinct pages, meaning nearly every one of the four accesses lands on a different page. The locality defined in the Processor Cache lesson produces a direct number here, and this workload’s locality is weak: in the widest eight-access window, all eight accesses touch eight distinct pages — no repetition at all. Weak locality determines from the outset how sensitive the fault count will be to the number of physical pages.

Address Translation

A virtual address splits into two parts: which virtual page it falls in, and which byte inside that page it is. The second part is called the page offset. If the page size is 256 bytes, translation is two divisions — the page number is the address divided by 256, the offset is the remainder. The physical address is the physical page number the page table returns, combined with the same offset.

• BD5 — Page size is 256 bytes, physical page count is 4. The first ten steps of the access sequence are used; each step’s page offset is fabricated, the page number comes from the common definition.
• BD6 — When no free physical page remains, the first-in-first-out rule applies.

"""Address translation: virtual address -> virtual page + offset -> physical address."""
PAGE_SIZE = 256
PHYSICAL = 4
FIRST = [6, 9, 11, 9, 11, 9, 12, 1, 3, 1]     # first ten steps of the access sequence

table, order = {}, []                          # virtual page -> physical page
print("virtual addr  virtual page  offset  status        physical  physical addr")
for k, virtual in enumerate(FIRST):
    addr = virtual * PAGE_SIZE + (k * 23) % PAGE_SIZE
    page, offset = divmod(addr, PAGE_SIZE)
    if page in table:
        status = "resident"
    else:
        status = "page fault"
        if len(order) == PHYSICAL:
            table.pop(order.pop(0))
        free = min(set(range(PHYSICAL)) - set(table.values()))
        table[page] = free
        order.append(page)
    print(f"{addr:11d}  {page:11d}  {offset:5d}  {status:12s}  {table[page]:8d}"
          f"  {table[page] * PAGE_SIZE + offset:14d}")
print("page table:", dict(sorted(table.items())))

virtual addr  virtual page  offset  status        physical  physical addr
       1536            6      0  page fault           0               0
       2327            9     23  page fault           1             279
       2862           11     46  page fault           2             558
       2373            9     69  resident             1             325
       2908           11     92  resident             2             604
       2419            9    115  resident             1             371
       3210           12    138  page fault           3             906
        417            1    161  page fault           0             161
        952            3    184  page fault           1             440
        463            1    207  resident             0             207
page table: {1: 0, 3: 1, 11: 2, 12: 3}

Ten accesses, six faults. Two points are worth watching. First, the offset never changes across translation: address 2327 had offset 23, its physical counterpart is 279, and 279 divided by 256 also leaves a remainder of 23. When the page size is chosen as a power of two, this division collapses to a bit split and no division is ever performed. Second, on the eighth line virtual page 6 is evicted and virtual page 1 lands in that same physical page; the process’s view of the address did not change, what changed was the physical location under it. That is what the abstraction provides, and the fault on that line is what it costs.

The Page Table’s Own Cost

If the page table holds a mapping, that mapping has to sit somewhere, and that somewhere is memory. The model’s table has 16 entries because the address space is 16 virtual pages. The entry count is the address space divided by the page size, and when both are chosen as powers of two this too collapses to a subtraction.

• BD7 — A table entry is assumed to hold 8 bytes; the entry carries the physical page number, the validity bit, and the access flags.

"""The page table's own cost: entry count grows with the address space."""
ENTRY_BYTES = 8                               # bytes held per table entry
print("address bits  page size  entry count  single-level table (bytes)")
for addr_bits, page_bits in ((12, 8), (22, 12), (32, 12), (48, 12)):
    entries = 2 ** (addr_bits - page_bits)
    print(f"{addr_bits:12d}  {2 ** page_bits:9d}  {entries:11d}  {entries * ENTRY_BYTES:26d}")

address bits  page size  entry count  single-level table (bytes)
          12        256           16                         128
          22       4096         1024                        8192
          32       4096      1048576                     8388608
          48       4096  68719476736                549755813888

The first row is this lesson’s model: a 12-bit address space, a 256-byte page, 16 entries, a 128-byte table. The fourth row shows how the abstraction behaves at scale — with a 48-bit address space, a single-level table demands a place larger than the memory it represents, and one is needed per process. The applied fix is to split the table into levels: the top-level table only points to used ranges, and no sub-table is ever allocated for an unused range. This costs multiple table reads per translation — the abstraction makes you pay in steps once again.

Three Policies, One Sequence

When a physical page fills up, a page replacement policy decides which page to evict. Three policies are measured: first in first out, least recently used, and optimal replacement — the last one evicts the page whose next use is furthest away, that is, it knows the future.

"""Three page replacement policies on the same access sequence. Sequence is the output of block 01."""
SEQUENCE = [6, 9, 11, 9, 11, 9, 12, 1, 3, 1, 6, 9, 7, 9, 0, 2, 0, 5, 2, 3, 0,
            5, 2, 3, 5, 3, 8, 9, 6, 4, 13, 12, 15, 13, 8, 12, 14, 12, 7]
FETCH = 30                                    # a page fault is one wait step


def page_fault(sequence, physical, policy="fifo"):
    """policy: fifo | lru | optimal (looks ahead at the future)"""
    resident, order, faults = [], [], 0
    for k, s in enumerate(sequence):
        if s in resident:
            if policy == "lru":
                order.remove(s)
                order.append(s)
            continue
        faults += 1
        if len(resident) < physical:
            resident.append(s)
            order.append(s)
            continue
        if policy in ("fifo", "lru"):
            evicted = order.pop(0)
        else:
            distance = {}
            for y in resident:
                distance[y] = sequence.index(y, k + 1) if y in sequence[k + 1:] else 10**9
            evicted = max(resident, key=lambda y: distance[y])
            order.remove(evicted)
        resident.remove(evicted)
        resident.append(s)
        order.append(s)
    return faults


compulsory = len(set(SEQUENCE))
print("accesses", len(SEQUENCE), "| compulsory faults:", compulsory,
      "| baseline duration:", len(SEQUENCE) + compulsory * FETCH)
print("physical  fifo  lru  optimal   fifo extra  fifo duration")
for f in (2, 3, 4, 5, 6, 8, 15):
    a = page_fault(SEQUENCE, f, "fifo")
    b = page_fault(SEQUENCE, f, "lru")
    c = page_fault(SEQUENCE, f, "optimal")
    print(f"  {f:6d}  {a:4d}  {b:3d}  {c:7d}   {a - compulsory:11d}"
          f"  {len(SEQUENCE) + a * FETCH:13d}")

accesses 39 | compulsory faults: 15 | baseline duration: 489
physical  fifo  lru  optimal   fifo extra  fifo duration
       2    30   31       27            15            939
       3    28   28       23            13            879
       4    23   23       19             8            729
       5    23   22       18             8            729
       6    20   20       17             5            639
       8    19   17       15             4            609
      15    15   15       15             0            489

Three numbers sit side by side. Baseline: 15 physical pages, 15 compulsory faults, 489 time units. Setup: 2 physical pages, first in first out, 30 faults. Cost: 15 extra faults and 939 − 489 = 450 time units. On this workload, the virtual memory abstraction shrinks memory by a factor of seven and a half in exchange for stretching runtime to 1.92 times its baseline.

The table lays bare where the cost comes from. Thirty of the 39 accesses end in a fault, so roughly three quarters of accesses hit disk and the machine spends more time fetching pages than computing. This condition is called thrashing: once the physical page count drops below the working set, every new access evicts a page that will be requested again shortly after. The working-set measurement already predicted this — at an average of 3.47 distinct pages per four-access window, running with two physical pages means refetching half the window on every turn.

A Smarter Policy Does Not Always Pay Off

Least recently used uses more information than first in first out: it tracks when each page was last touched. Even so, at two physical pages it produces 31 faults against first in first out’s 30. The policy that uses more information produces one more fault at this point.

How this difference is read matters. The common definition’s resolution rule is this: at 39 accesses, a one-fault difference is a ratio of 0.0256 and counts as unmeasured; a meaningful difference is at least three faults. So the sentence “least recently used is worse” cannot be written either. Reading the table by this criterion makes the result even clearer: the gap between the two policies never reaches three in any row — the largest is 19 against 17 at eight physical pages, a gap of two. This workload has not measured an advantage for least recently used. An implementation that chooses it pays the cost of keeping a timestamp per page for nothing.

The same criterion applies to adding physical pages. Going from 3 to 4 drops first in first out from 28 to 23: five faults, meaningful. Going from 4 to 5 leaves it at 23: zero. One more physical page buys nothing here. Going from 5 to 6 wins back three faults. The return on adding a resource does not decline smoothly, it steps, and where the step falls depends on the workload’s access pattern.

Why the Optimal Baseline Is Unreachable

The third column sits below the other two on every row: 27 at 2 pages, 15 at 8 pages. At eight physical pages, 15 faults equals the compulsory fault count — meaning the optimal policy never refetches a single page at eight pages.

This column is not a policy, it is a lower bound. Choosing which page to evict requires reading the rest of the access sequence — the addresses a not-yet-run program will produce. A scheduler does not know at translation time which process it will interrupt and when, which data a user will request, or which way a branch will go. The lower bound’s role is not to be implemented but to measure: at eight physical pages, first in first out’s 19 faults are four faults away from the bound’s 15, and that gap is the entire remaining room for improvement.

Summary

• Virtual memory separates the address space a process sees from physical memory through fixed-size pages; every access splits into a virtual page number and a page offset and gets translated.
• The common definition’s 39-access sequence touches 15 distinct virtual pages; the baseline is 15 compulsory faults and 489 time units, the two-physical-page setup is 30 faults and 939 time units, the cost is 450 time units.
• Thrashing starts once the physical page count drops below the working set: 30 of 39 accesses hit disk and the machine fetches pages more than it computes.
• The gap between least recently used and first in first out never reaches three faults at any physical page count; on this workload, no measured advantage exists between the two.
• The return on adding physical pages steps: going from 3 to 4 wins five faults, going from 4 to 5 wins nothing.

Next Step

This lesson distributed memory in fixed-size pages and assumed every request fits one page. That is not true of a process’s heap: requests come in different sizes, arrive out of order, and are released out of order. The next lesson models heap management on the same machine and compares two allocation policies on the same event sequence — one rejects a request while the other places all of them, but leaves behind an unusable remainder.