Chapters 5.1–5.2 Lock-in

ACompressed recap

Base/limit: L < limit → base + L. Fixed partitions → internal, variable → external fragmentation; first/next/best/worst fit. Paging: offset = log₂(page size) bits, page number = the rest; physical = f × size + d; page table = #pages × PTE; frame bits = physical bits − offset bits. TLB EAT = h(t + m) + (1 − h)(t + 2m); multilevel: levels = ⌈page bits / log₂(page size / PTE)⌉, miss = t + (k + 1)m; inverted table per frame. Segmentation: (s, d), base + d if d < limit; external fragmentation.

BMerged rule card

5.1.1 Addresses and contiguous allocation: fits and fragmentation

• Logical address from the CPU; MMU makes the physical address.
• Base/limit: if L < limit then physical = base + L, else trap.
• Fixed partitions → internal fragmentation; variable → external; compaction merges holes.
• First fit (first big enough), next fit (continue from last), best fit (smallest big enough), worst fit (largest).
• 50% rule: N blocks allocated → about 0.5N lost (one third).

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

• 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).

5.2.2 TLBs, effective access time and multilevel page tables

• EAT = h(t + m) + (1 − h)(t + 2m); with k levels the miss costs t + (k + 1)m.
• TLB: small associative cache; flush on switch unless ASIDs.
• Multilevel: entries per page = page size / PTE; bits per level = log₂ of it; levels = ⌈(m − d) / bits per level⌉.
• Inverted table: one entry per frame, searched via hashing.

5.2.3 Segmentation, and segmentation with paging

• Segment table entry (base, limit); (s, d) → base + d if d < limit, else trap.
• Paging: equal pieces, internal fragmentation. Segmentation: logical pieces, external fragmentation, natural sharing/protection.
• Segmentation with paging: (s, p, d); each segment paged.

CInterleaved GATE-style questions

Q1 · NAT · 1 mark(s) — Base/limit

Base 7000, limit 2500. Physical address of logical address 2499?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Worst fit

Holes 150, 350, 200, 500, 100 KB; requests 180, 90, 320, 240 KB by worst fit. Size of the hole that the 240 KB request is placed in (its size just before placement)?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — Pages

A 64 KB logical address space with 2 KB pages has how many pages?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Translation

Pages are 2 KB. Logical address 9000 is on page p; page p is in frame 7. Physical address?

Numerical answer: ________

Q5 · NAT · 2 mark(s) — Page table

Logical addresses 34 bits, pages 16 KB, entries 4 bytes. Page-table size in MB?

Numerical answer: ________

Q6 · NAT · 1 mark(s) — EAT

Memory 80 ns, TLB time negligible, hit ratio 0.75. EAT in ns?

Numerical answer: ________

Q7 · NAT · 2 mark(s) — Levels

39-bit virtual addresses, 4 KB pages, 8-byte entries, each table one page. Number of levels?

Numerical answer: ________

Q8 · MCQ · 1 mark(s) — Segmentation

Which statement about segmentation is true?

1. (A) Translation is base + offset after the check offset < limit
2. (B) It needs no table
3. (C) It has no fragmentation
4. (D) All segments have the same size