Chapter 5.3 Lock-in

ACompressed recap

Demand paging: page fault → trap, find frame, disk read, update table, restart. EAT = (1 − p)·ma + p·s (ms = 10⁶ ns); dirty victims cost a write. Copy-on-write. FIFO (oldest loaded), OPT (farthest future), LRU (least recently used); running string 3 frames: 10, 7, 9. Belady: FIFO 9 → 10 faults with 3 → 4 frames; LRU/OPT immune. Allocation equal / proportional; thrashing → reduce multiprogramming; working set = distinct pages in last Δ; clock gives second chances.

BMerged rule card

5.3.1 Demand paging, page faults and effective access time

• Demand paging: load on first reference; valid bit = in memory.
• Page fault: trap → check → free frame (or victim) → disk read → update table → restart.
• EAT = (1 − p)·ma + p·s; ms = 10⁶ ns.
• Dirty victims must be written back; average s weighted by the dirty fraction.
• Copy-on-write makes fork() cheap.

5.3.2 Page replacement: FIFO, optimal and LRU; Belady's anomaly

• FIFO: evict earliest loaded. OPT: evict farthest next use (never used = best). LRU: evict least recently used.
• Running string, 3 frames: FIFO 10, OPT 7, LRU 9; 4 frames: FIFO 7, OPT 6, LRU 6.
• Belady (FIFO): 1 2 3 4 1 2 5 1 2 3 4 5 → 9 faults with 3 frames, 10 with 4. LRU and OPT are stack algorithms (no anomaly).
• Faults ≥ distinct pages (from empty); exact LRU needs counters or a stack.

5.3.3 Frame allocation, thrashing, working sets and the clock algorithm

• Equal: m/n. Proportional: aᵢ = sᵢ/S × m. Global vs local replacement.
• Thrashing: more paging than work; cure by reducing multiprogramming.
• Working set: distinct pages in last Δ references; D = Σ WSS > m → suspend someone. PFF bounds.
• Clock: bit 1 → clear and move; bit 0 → replace (new page bit 1). Enhanced: prefer (0,0).

CInterleaved GATE-style questions

Q1 · NAT · 2 mark(s) — EAT

ma = 200 ns, s = 8 ms, p = 0.001. EAT in ns (1 decimal)?

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Valid bit

In demand paging, valid bit 0 for a legal page means:

1. (A) the page is dirty
2. (B) the page is on disk, not in memory
3. (C) the page is in memory
4. (D) the page is shared

Q3 · NAT · 2 mark(s) — FIFO

Reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO, 3 frames. Number of faults?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — LRU

Reference string 1 2 3 4 1 2 5 1 2 3 4 5, LRU, 4 frames. Number of faults?

Numerical answer: ________

Q5 · NAT · 1 mark(s) — Lower bound

Running string 7 0 1 2 0 3 0 4 2 3 0 3 2 with 10 empty frames. Number of faults under any policy?

Numerical answer: ________

Q6 · NAT · 1 mark(s) — Allocation

Proportional allocation of 100 frames to processes of 30 and 120 pages: frames for the larger process?

Numerical answer: ________

Q7 · NAT · 2 mark(s) — Working set

Running string (positions 1–13), Δ = 3. Working-set size at t = 9?

Numerical answer: ________

Q8 · MCQ · 1 mark(s) — Thrashing

Thrashing occurs when:

1. (A) the disk is idle
2. (B) the TLB hit ratio is 1
3. (C) the sum of the working sets exceeds the available frames
4. (D) a process has too many frames