Memory Management: translate an address, then choose a victim

A virtual address names a byte in a process's address space. A physical address names a byte in memory. Page tables connect them; replacement decides what to keep when frames are full. These are separate questions: a correct replacement policy cannot repair an incorrect address translation.

You need integer division/remainder, bit shifts/masks, and array indexing. This module builds a two-level translator and a clock simulator. The next virtual-memory module adds permissions, TLBs, faults, and copy-on-write to this foundation.

Split the address without losing the byte

A page and a frame have the same size. With 4096-byte pages, the low 12 bits identify a byte within the page; translation changes the page's location but preserves that offset.

The exercise divides a 32-bit virtual address into 10 directory | 10 table | 12 offset bits:

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

Why those shifts? Removing 12 offset bits leaves the virtual page number. Removing another 10 bits leaves the directory index. The middle index needs a 10-bit mask to exclude the directory bits.

Take va = 0x00c0502d. It equals (3 << 22) + (5 << 12) + 45, so directory=3, table=5, offset=45. If pd[3]=1 and pts[1][5]=12, follow:

virtual address → pd[3] → page table 1 → entry 5 → frame 12
physical address = 12*4096 + 45 = 49197 = 0x0000c02d

pd[3] selects a table, not a frame. Returning 1*4096+45 would stop one level too early. Indexing pts[3] would confuse the virtual directory index with the stored table index.

Presence is separate from address zero

The exercise uses -1 for an absent directory entry or page-table entry. Check each before following it. Frame zero is valid: mapping offset zero to frame zero returns (0,true). An absent mapping returns (0,false). The boolean carries information the address alone cannot.

Initialize absent entries to -1; Go's default integer zero would accidentally claim that they are present. The model has no permission bits or demand-paging handler: false reports unavailable translation, not a complete diagnosis or recovery action.

The last byte of one page and the first byte of the next may map to unrelated physical frames. Crossing a virtual page boundary requires another lookup; incrementing the previous physical address is insufficient.

Why two levels can save space

There are 2^20 virtual pages in this layout. In a conceptual representation with four-byte entries, a flat table needs 4 MiB. A directory needs 4 KiB, and each allocated lower table adds 4 KiB while covering 4 MiB of virtual addresses. If mappings occupy only two directory regions, directory plus two lower tables cost 12 KiB. This arithmetic counts translation metadata, not the data frames.

The Go slices are a teaching representation; their entry width and slice overhead need not equal those conceptual four-byte hardware entries. Sparse levels save space only while enough lower tables can remain absent. A fully populated hierarchy adds the directory on top of all lower tables.

Clock: a reference bit and a persistent hand

Use parallel arrays for page numbers and reference bits, plus one circular hand. Empty frames contain -1; valid page numbers are nonnegative.

• A hit sets that frame's reference bit to 1 and leaves the hand unchanged.
• A miss increments the fault count. Starting at the hand, clear each encountered 1 bit and advance. Insert into the first empty frame or frame with bit 0.
• Set the inserted page's bit to 1 and advance the hand once beyond its slot.

Keep the hand across accesses. Clock remembers whether a page was referenced since its bit was last cleared; it does not record an exact recency order like LRU.

With three frames and accesses [2,4,2,6,8,4,9]:

Access	Result	Frames	Bits	Next hand	Faults
2	Miss, fill slot 0	[2,-1,-1]	[1,0,0]	1	1
4	Miss, fill slot 1	[2,4,-1]	[1,1,0]	2	2
2	Hit	[2,4,-1]	[1,1,0]	2	2
6	Miss, fill slot 2	[2,4,6]	[1,1,1]	0	3
8	Clear all three; replace slot 0	[8,4,6]	[1,0,0]	1	4
4	Hit, refresh slot 1	[8,4,6]	[1,1,0]	1	4
9	Clear slot 1; replace slot 2	[8,4,9]	[1,0,1]	0	5

All bits being 1 does not mean failure. This single-threaded scan clears them and revisits a zero bit. No new references arrive during the scan. A hit must not increment faults, replace a page, or move the hand.

Reconstruct and diagnose

1. In the translation above, change only the final virtual-address byte from 0x2d to 0x2e. What physical address results?
2. Suppose pd[3]=-1 while some entry elsewhere contains frame 12. Can that frame rescue the translation?
3. Three occupied frames have bits [1,1,1], hand=2, and the requested page is absent. Which slot is replaced, and where does the hand end?

Model answers

1. 49198 (0x0000c02e): the same mapping, offset increased by one.
2. No. The directory entry defines the path; searching unrelated tables can return someone else's mapping.
3. Slot 2 is replaced after clearing slots 2, 0, and 1; the hand ends at 0 after insertion.

Build Page Table Translation and Clock Page Replacement, then attempt the checkpoint. General background: OSTEP: Paging and replacement policies.