a logical address can't tell you its frame
This week in OS: logical and physical addresses. I kept trying to compute a physical address from the logical one and getting stuck. The reason is simple once you see the whole trip: half of the answer isn't in the address at all.
the exercise
- RAM: 10 MB
- process: 15 MB
- page size (and frame size): 16 KB
- the CPU asks for page 100, offset 16,200
- the page table says page 100 lives in frame 128
what the address gives you
A 16 KB page is 16,384 bytes, which is 2^14. So the low 14 bits of any address are the offset inside the page, and the rest is the page number.
| count | bits needed | |
|---|---|---|
| offset in a page | 16,384 bytes | 14 |
| pages in the process (15 MB / 16 KB) | 960 | 10 |
| frames in RAM (10 MB / 16 KB) | 640 | 10 |
In this exercise's convention (the address is just wide enough for the process), a logical address is 10 + 14 = 24 bits, and a physical one is also 24 bits. Real CPUs use a fixed, much wider virtual address (48 bits on most x86-64 machines), but the split into page number and offset works the same way.
logical = 100 × 16,384 + 16,200 = 1,654,600 (0x193F48)
physical = 128 × 16,384 + 16,200 = 2,113,352 (0x203F48)The offset is identical in both. Only the top part changes.
where the frame comes from
Follow the numbered paths in the sketch:
- The CPU emits page 100, offset 16,200.
- ① The TLB, a small cache of recent translations, is checked first. On a hit it answers "frame 128" immediately.
- ② On a miss, the page table in RAM is read. Entry 100 says frame 128 and valid, and the answer is copied into the TLB for next time.
- The offset never goes through any of this. It's copied straight across.
- ③ If the entry is invalid, that's a page fault: the OS loads the page from disk, updates the page table (and the TLB), and the instruction runs again.
So my question, "what if the frame isn't given?", has a plain answer: you can't compute it. The page number is an index, and the frame is whatever the OS wrote at that index when it loaded the page.
things I want to remember
- Offset bits come from the page size, never from RAM size.
- Page-number bits come from the size of the logical address space (the process size, in exam problems); frame-number bits come from RAM size. They don't have to match.
- Physical = frame × page size + offset. The offset passes through untouched.
- 10 MB of RAM still needs 24-bit physical addresses: 2^23 is only 8 MB.
- The TLB is why this isn't slow: when its hit rate is high, as it usually is, most translations skip the page table.