Paging and address translation

Every problem in Topic 6.2 came from one requirement: the block must be continuous.

Drop it.

Cut memory into fixed pieces of 4 KB and let a process's memory be scattered across any free pieces, in any order. The process never notices, because Topic 6.1 already established that it does not see physical addresses.

Now any free piece fits any request. The shape problem cannot happen.

Why & what

The two words.

• A page is a fixed-size piece of a process's logical address space.
• A frame is a fixed-size piece of physical RAM.

They are the same size — 4 KB on the Nova-14 — and that is the whole trick. Any page fits in any frame.

The page table. Each process has its own table saying which frame holds each of its pages. The compile job's table starts:

• page 0 → frame 12
• page 1 → frame 5
• page 2 → frame 7
• page 3 → frame 19

Pages are consecutive. Frames are all over the place. Nobody minds.

Splitting the address. A logical address is not translated as a whole. It is split into two parts:

• The page number — which 4 KB piece.
• The offset — how far into that piece.

Because the page size is a power of two, the split is free. It is not arithmetic; it is just deciding which bits are which. With 4 KB pages the bottom 12 bits are the offset and everything above is the page number.

The worked example. The compile job accesses logical address 9,000.

• 9000 ÷ 4096 = 2, so it is in page 2.
• 9000 − 8192 = 808, so the offset is 808.
• The table says page 2 lives in frame 7.
• Physical address = 7 × 4096 + 808 = 29,480.

Now look at it in hex, because this is where it becomes obvious:

• Logical 0x2328 → physical 0x7328.

Only the leading digit changed. 328 is the offset and it was copied straight through, untouched. The offset is never translated. Only the page number is replaced by a frame number.

What it costs. Two things.

• Internal fragmentation. A 9,000-byte need takes 3 pages = 12,288 bytes. 3,288 bytes are wasted inside the last page. Average waste is half a page per process, which is tiny compared with external fragmentation.
• An extra memory access. The page table lives in RAM, so reading data now means reading the table first, then the data. Every access has just gone from 100 ns to 200 ns. That is a serious problem, and Topic 6.4 solves it.

How it works

1. The CPU emits logical address 9,000.
2. The MMU splits it into page number 2 and offset 808.
3. It looks up entry 2 in the page table of the running process. The register holding the table's location was loaded during the context switch — Module 2, step 4.
4. It checks the entry is valid. Invalid means the page is not in RAM, and the MMU raises a page fault. Module 7 is what happens next.
5. It builds the physical address by putting the frame number in front of the unchanged offset, and the RAM access proceeds.

Common confusion

"The offset gets translated too." It does not, and if it did, paging would not work. The offset is a position inside a piece, and the piece is the same size in both worlds. Translating it would be meaningless.

"Bigger pages are better." It is a trade. Bigger pages mean a smaller page table and fewer entries to manage, but more internal fragmentation — the average waste is half a page. Smaller pages waste less and need a much bigger table. 4 KB has been the common compromise for decades.

"Every process has one page table, so there is one page table." There is one per process.

Switching processes means switching page tables, which is the expensive part of the context switch that Topic 2.3 mentioned but could not yet explain.

"Paging eliminates fragmentation." It eliminates external fragmentation. It creates internal fragmentation in exchange. The trade is strongly worth it, but it is a trade.

Interview angle

"Explain paging." Give the two words, the split, and one worked translation. Numbers make this answer; an abstract description does not. Practise until you can do a translation on paper without hesitating.

"Why does paging not suffer from external fragmentation?" Because all pieces are the same size, so any free frame satisfies any page request. There is no such thing as a hole of the wrong shape.

"What is the disadvantage of paging?" Two: internal fragmentation of up to one page per process, and an extra memory access per reference. Naming the second is what leads naturally into the TLB, and interviewers usually want you to get there.