Two questions, two mechanisms

Translation: where is this virtual byte mapped?

Replacement: which resident page gives up its frame?

Prerequisites: shifts, masks, array indexing, and integer division.

Derive the split

32-bit virtual address: 10 directory | 10 table | 12 offset.

• dir = (va >> 22) & 0x3ff
• tab = (va >> 12) & 0x3ff
• offset = va & 0xfff

The low 12 bits survive translation unchanged.

Follow values, not similar-looking indices

va = 0x00c0502d: directory 3, table index 5, offset 45.

pd[3]=1 → pts[1][5]=12 → frame 12

Physical address: 12*4096+45 = 49197.

Why is pts[3][5] wrong? The directory stores the table index; it need not equal 3.

Zero is a valid address

Present mapping to frame 0 at offset 0: (0,true).

Missing directory/table entry (-1): (0,false).

Initializing all entries to zero creates apparent mappings.

A virtual page boundary can jump to an unrelated physical frame.

Predict the metadata cost

Assume four-byte entries and only two populated directory regions.

Directory: 4 KiB. Each lower table: 4 KiB.

Total: 12 KiB, versus a 4 MiB flat table.

These are conceptual entry sizes, not a measurement of Go slices.

Clock: trace the hand

Frames [2,4,6], bits [1,1,1], hand 0; request page 8.

Clear slots 0, 1, 2; revisit slot 0 and replace it.

Result: frames [8,4,6], bits [1,0,0], hand 1.

A full circle makes progress because the scan clears reference bits.

A hit changes the next victim

From that state, hit page 4: bits become [1,1,0], hand stays 1.

Now miss page 9: clear slot 1, replace slot 2.

Result: [8,4,9], bits [1,0,1], hand 0.

What if the hit moved the hand? It would change the policy's future scan order.

Debug with invariants

• Translation preserves the offset and checks both levels.
• Frame zero is distinct from an absent mapping.
• A resident page appears once; a hit adds no fault.
• The clock hand persists and moves past every insertion.

Next: add permissions, TLBs, and copy-on-write in Virtual Memory.