Paging: pages, frames, page tables and the address split

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is external fragmentation? from Lesson 5.1.1
2. With base 3000 and limit 1200, where does logical address 500 go? from Lesson 5.1.1
3. How many bits address 2³² bytes? from Lesson 0.1.1

1 · The Hook

A long book doesn't need one shelf long enough for the whole thing: tear it into 10-page booklets, put each booklet in any free slot, and keep an index card saying which slot holds which booklet. Paging does exactly that with programs. GATE asks for the address split (page number and offset bits) and the size of the page table in almost every paper.

3 · Core Concept

Predict First — the answer

3000 = 2 × 1024 + 952 → page 2, offset 952.

In plain words

Cut the program into equal pieces called pages and RAM into pieces of the same size called frames. Any page can go in any free frame. A page table (one per process) records which frame holds each page. An address is split into "which page" and "where inside the page"; only the page part is translated.

1. Pages, frames, page table

• Page size = frame size = a power of 2 (e.g. 4 KB).
• Page table: entry p holds the frame number of page p (plus some bits, below).
• No external fragmentation: every free frame is usable. Only the last page of a process may be partly empty (internal fragmentation, on average half a page).

2. Splitting an address

If the page size is 2ᵈ bytes and logical addresses have m bits:

• offset = the low d bits; page number = the high m − d bits.
• Number of pages = 2ᵐ⁻ᵈ.

Translation: frame f = PageTable[p]; physical address = f × page size + offset. Example: 1 KB pages, logical 3000 → p = 2, d = 952. If page 2 is in frame 5: 5 × 1024 + 952 = 6072.

3. Page-table size

Page-table size = number of pages × size of one entry (PTE).

• 32-bit logical addresses, 4 KB pages (12-bit offset): 2²⁰ pages. With 4-byte entries: 2²⁰ × 4 B = 4 MB per process.
• Frame-number bits = physical-address bits − offset bits. With 1 GB of RAM (30 bits) and 4 KB frames: 30 − 12 = 18 bits; the rest of the entry holds flag bits.

4. What else is in a page-table entry

• Valid/invalid bit: is this page part of the process? An access to an invalid page traps to the OS.
• Protection bits: read / write / execute.
• Modified (dirty) bit and referenced bit (used in Chapter 5.3).
• The OS keeps the table's start address in a register (the page-table base register) and reloads it on each context switch.

5. Sharing

Read-only code (e.g. a text editor used by 40 users) can be shared: each process's page table points to the same frames.

4 · Visual

Logical address (m bits)                          Physical address
+--------------+----------+                      +--------------+----------+
| page p       | offset d |   --> page table --> | frame f      | offset d |
| (m - d bits) | (d bits) |       p -> f         |              | (copied) |
+--------------+----------+                      +--------------+----------+

1 KB pages, address 3000:  p = 3000 div 1024 = 2,  d = 3000 mod 1024 = 952
page 2 -> frame 5:         physical = 5 x 1024 + 952 = 6072

5 · Worked Examples

Example 1 Easy

16-bit logical addresses, 1 KB pages. How many bits are page number and offset? How many pages?

Solution

Offset 10 bits; page number 6 bits; 2⁶ = 64 pages.

Example 2 Medium

A process needs 10,000 bytes and pages are 4 KB (4096 bytes). How many frames does it get, and how much internal fragmentation is there?

Solution

10,000 / 4096 → 3 frames (12,288 bytes); waste 12,288 − 10,000 = 2,288 bytes.

Example 3 GATE

Logical address 32 bits, page size 8 KB, page-table entry 4 bytes. Size of the page table?

Solution

Offset 13 bits → 2¹⁹ pages × 4 B = 2²¹ B = 2 MB.

6 · GATE Traps

• Offset bits come from the page size, not from memory size.
• Page-table entries = number of pages (logical side), not number of frames.
• Frame-number width depends on physical memory size.
• Paging has internal fragmentation (last page), not external.

7 · Memory Hook

"Low bits ride along (offset); high bits get looked up (page → frame)."

8 · Connect the Dots

Each memory access now needs two memory accesses: one to read the page table, one for the data. That doubles memory time. The next lesson fixes it with a small fast cache (the TLB) and shrinks huge page tables with multilevel paging.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Address split

Logical addresses are 32 bits and pages are 4 KB. How many bits form the page number?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Translation

Pages are 1 KB. Logical address 5000 is on page 4. Page 4 is in frame 9. Physical address?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Page-table size

Logical addresses are 32 bits, pages 4 KB, page-table entries 4 bytes. Page-table size in MB?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Frame bits

Physical memory is 1 GB and frames are 4 KB. Minimum number of bits for a frame number?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Fragmentation

Paging suffers from:

1. (A) internal fragmentation only (in the last page)
2. (B) external fragmentation only
3. (C) both kinds equally
4. (D) neither

10 · Rule Card

• Page = frame size = 2ᵈ; offset = low d bits; page number = high m − d bits.
• Physical = frame × page size + offset.
• Page-table size = (#pages) × (PTE size); frame bits = physical bits − d.
• PTE: frame, valid, protection, dirty, referenced. Shared code → same frames.
• Paging: internal fragmentation only (≈ half a page per process).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

pageframepage tablepage number and offsetaddress translationpage-table sizepage-table entryframe-number bitsvalid/invalid bitprotection bitspage-table base registershared pages