5.3Paging and address translation
The idea
Paging cuts memory into equal frames and programs into pages. A page table maps pages to frames, and the address is split into page number | offset.
Think of it like this: A book split into pages that can be filed in any free shelf slot; an index (the page table) says which slot holds each page.
Why it exists
Any free frame will do, so external fragmentation disappears.
How it works
- Page size is 2^d, so the low d bits are the offset and the rest is the page number.
- Look the page number up in the page table to get a frame.
- Physical address = frame × page size + offset.
- The last page of a process is usually partly empty: internal fragmentation, on average half a page.
Worked example: Page size 1024, page table 5, 2, 7, −1, 0, 3, address 2500
Page = 2500 / 1024 = 2, offset = 2500 − 2048 = 452. Frame of page 2 is 7. Physical = 7 × 1024 + 452 = 7620.
Now play with it
- →Enter address 3100: page 3 has −1, so a page fault.
- →Try 6100: it is beyond the table.
6 bits
10 bits
Physical address = frame × page size + offset. The offset is copied unchanged, only the page number is translated. Entries equal to -1 model pages that are not in memory.
Check yourself
A system has 32-bit logical addresses and 4 KB pages. The number of bits in the page number is
Exam notes (the dense version)
Physical memory is split into frames, logical memory into pages of the same size. A logical address = page number | offset. The page table maps page → frame; physical address = frame × page size + offset. If the address has L bits and the page size is 2^d, there are L − d page-number bits and d offset bits. Paging removes external fragmentation but leaves internal fragmentation (on average half a page per process).
Previous year questions: Memory Management (11)
PYQs are grouped by topic, so this is the full set for Memory Management; try the ones that match this subtopic. Open all 11 on the topic page.