Numericals — Every Worked Calculation

Given data

Total CPU work = 6 + 4 + 5 + 8 = 23 units, and P1 arrives at 0 so the timeline must start at 0 and end at 23 with no idle gap. Use that as a sanity check on any chart you draw. Formulas used: TAT = CT − AT, WT = TAT − BT.

(i) SRTF — Shortest Remaining Time First (preemptive)

1. t = 0: only P1 is in the system → P1 runs 0–1 (remaining 5).
2. t = 1: P2 arrives with BT 4 < P1's remaining 5 → preempt P1, run P2.
3. t = 2: P3 arrives (5) but P2 has only 3 left → P2 continues.
4. t = 3: P4 arrives (8) but P2 has 2 left → P2 continues and finishes at t = 5. CT P2 = 5.
5. t = 5: remaining times are P1 = 5, P3 = 5, P4 = 8. Tie 5 ↔ 5 between P1 and P3 → earlier arrival wins → P1 (AT 0) runs and finishes at t = 10. CT P1 = 10.
6. t = 10: P3 (5) < P4 (8) → P3 runs 10–15. CT P3 = 15.
7. t = 15: only P4 left → runs 15–23. CT P4 = 23.

(ii) Round Robin, quantum q = 3 — every slice

Ready-queue rule: a process that arrives during a slice is queued before the process whose slice just expired.

Check: 3+3+3+3+3+1+2+3+2 = 23 = total burst, and the chart ends at 23 with no idle.

Verification line: Σ slices = 23 = Σ burst ✓ · CT values reproduce the independent re-solver exactly (SRTF 10/5/15/23, RR 15/16/18/23) · averages 24÷4, 47÷4, 43÷4, 66÷4 ✓.

Given data

Total CPU work = 5+6+7+9+2+3 = 32 units; the first arrival is at t = 1, so the chart must contain one idle unit and finish at 1 + 32 = 33. Formulas: TAT = CT − AT, WT = TAT − BT.

Round Robin, q = 3 — every slice

P5's burst is only 2, so its slice is 4–6 (2 units, not 3); P1's last slice is 30–32 and P3's is 32–33 for the same reason. Sum of slices = 1+3+2+3+3+3+3+3+3+3+3+2+1 = 33 ✓.

SJF (non-preemptive) — dispatch order

1. t = 0–1 idle (first arrival is P4 at t = 1).
2. t = 1: only P4 (9) has arrived → it must run, even though it is the longest burst. CT P4 = 10.
3. t = 10: all six have arrived; shortest burst among P1 5, P2 6, P3 7, P5 2, P6 3 → P5. CT P5 = 12.
4. t = 12: shortest of P1 5, P2 6, P3 7, P6 3 → P6. CT P6 = 15.
5. t = 15: shortest of P1 5, P2 6, P3 7 → P1. CT P1 = 20.
6. t = 20: P2 (6) then P3 (7). CT P2 = 26, CT P3 = 33.

Advantages, shown by the metrics (as the question asks)

Verification line: Σ slices = 33 = 1 idle + 32 burst ✓ · RR averages equal the printed 21.33 / 16.00 exactly ✓ · SJF row sums 95 ÷ 6 and 63 ÷ 6 re-checked digit by digit ✓.

Given data

Total CPU work = 5+8+7+6 = 26 ms; first dispatch is at t = 1, so every correct chart for this data must end at 27. Formulas: TAT = CT − AT, WT = TAT − BT.

FCFS — arrival order P3 → P4 → P1 → P2

1. 0–1 idle (nothing has arrived). P3 arrives at 1 → runs 1–8 → CT P3 = 8.
2. P4 runs 8–14 → CT P4 = 14; P1 runs 14–19 → CT P1 = 19; P2 runs 19–27 → CT P2 = 27.

Preemptive SJF (SRTF)

1. t = 1: P3 (7) starts. t = 2: P4 arrives with 6 while P3 has 6 left → tie, earlier arrival keeps the CPU → P3 continues.
2. t = 3: P1 arrives with 5 while P3 has 5 left → again a 5 ↔ 5 tie → P3 (AT 1) continues.
3. t = 5: P2 arrives with 8 > 4 left → P3 continues and finishes at t = 8 → CT P3 = 8.
4. t = 8: remaining P1 5, P4 6, P2 8 → P1 runs 8–13 → CT P1 = 13.
5. t = 13: P4 (6) < P2 (8) → P4 runs 13–19 → CT P4 = 19; P2 runs 19–27 → CT P2 = 27.

Round Robin, q = 2 ms — every slice

Check: 2×12 + 1 + 1 + 2 + 2 = 26 ms of CPU work, plus 1 ms idle at the start = timeline ends at 27 ✓.

Verification line: FCFS above is confirmed by the book (7.75 / 14.25) ✓ · every chart here ends at 27 ✓ · row sums 57, 31, 56, 30, 82, 56 re-added ✓.

Given data

Total CPU work = 12+8+5+1+11 = 37 ms and A arrives at 0, so all four charts must end at 37 with no idle. Formulas: TAT = CT − AT, WT = TAT − BT.

1. FCFS — arrival order A → B → C → D → E

1. A owns the CPU from 0 (only process present) → 0–12, CT A = 12.
2. B 12–20 → CT 20 · C 20–25 → CT 25 · D 25–26 → CT 26 · E 26–37 → CT 37.

2. SJF (non-preemptive)

1. t = 0: only A has arrived → A must run to completion: 0–12. CT A = 12.
2. t = 12: ready set B 8, C 5, D 1, E 11 → shortest is D (1) → 12–13.
3. t = 13: B 8, C 5, E 11 → C (5) → 13–18.
4. t = 18: B 8 < E 11 → B → 18–26, then E → 26–37.

Dispatch order A → D → C → B → E, exactly the order the book prints.

3. SRTF — Shortest Remaining Time First

4. Round Robin, q = 3 ms — every slice

Check: 3+3+3+3+3+1+3+3+2+2+3+3+3+2 = 37 ms = Σ burst, chart ends at 37 ✓.

Final comparison — the four algorithms side by side

Verification line: every chart ends at 37 = Σ burst ✓ · FCFS and SJF reproduce the printed book figures exactly ✓ · row sums 96/59, 82/45, 75/38, 111/74 re-added ✓.

Given data

Total CPU work = 12+7+8+6+10 = 43 ms, every process is present at t = 0, so both charts run from 0 to 43 with no idle. Since all AT = 0, TAT = CT and WT = CT − BT here.

SJF (all arrived, so tie-break by lower process number is never needed)

1. Shortest burst first: P4 (6) → P2 (7) → P3 (8) → P5 (10) → P1 (12).
2. Gantt boundaries: 0 – 6 – 13 – 21 – 31 – 43.

Round Robin, q = 3 — every slice

Initial ready queue (all arrive together, so they join in number order): P1, P2, P3, P4, P5.

Check: 3×13 + 1 + 2 + 1 = 39 + 4 = 43 ms ✓ (13 full quanta, plus the short closing slices).

(iii) Comparison — which is more efficient here

Conclusion worth writing: SJF is more efficient on both averages because all processes are available at t = 0, so SJF can order them by burst exactly once and never look back; RR costs an extra 13.6 ms of average waiting purely for the fairness of a bounded response time. The comparison stands either way — even on the book's own (mis-ordered) figures SJF wins both averages.

Verification line: charts end at 43 = Σ burst ✓ · SJF numbers match the book exactly (14.20 / 22.80) ✓ · RR row sums 139 ÷ 5 and 182 ÷ 5 ✓.

Given data

Total CPU work = 10+9+6+7+4 = 36 ms, P1 arrives at 0, so all four charts run 0 → 36 with no idle. Formulas: TAT = CT − AT, WT = TAT − BT.

(i) SRTF — Shortest Remaining Time First

1. t = 0: P1 runs. t = 1: P2 arrives with 9 and P1 has 9 left → tie; P1 arrived earlier, so P1 keeps the CPU (this single tie-break is where the book goes wrong).
2. t = 2: P3 arrives with 6 < P1's 8 → preempt P1. t = 3: P4 arrives (7) > P3's 5 → P3 continues.
3. t = 4: P5 arrives with 4 and P3 has 4 left → tie; P3 arrived earlier, so P3 continues and finishes at t = 8 → CT P3 = 8.
4. t = 8: remaining P1 8, P2 9, P4 7, P5 4 → P5 shortest → 8–12 → CT P5 = 12.
5. t = 12: P4 (7) < P1 (8) < P2 (9) → P4 12–19 → CT P4 = 19.
6. t = 19: P1 (8) < P2 (9) → P1 19–27 → CT P1 = 27; then P2 27–36 → CT P2 = 36.

(ii) Round Robin, q = 2 — every slice

Check: 17 slices × 2 + 2 slices × 1 = 34 + 2 = 36 ms = Σ burst ✓.

(iii) SJF (non-preemptive)

1. t = 0: only P1 present → P1 runs 0–10 → CT P1 = 10.
2. t = 10: bursts available are P2 9, P3 6, P4 7, P5 4 → P5 first (4) → CT P5 = 14.
3. t = 14: P3 (6) < P4 (7) < P2 (9) → P3 → CT P3 = 20; then P4 → CT P4 = 27; then P2 → CT P2 = 36.

(iv) Priority Scheduling — preemptive (higher number = higher priority)

1. t = 0: P1 (pri 3) runs alone for 1 unit.
2. t = 1: P2 arrives with pri 5 > 3 → preempt P1; P2 owns the CPU until it finishes at t = 10 → CT P2 = 10.
3. t = 4: P5 arrives with pri 4 — higher than P1 (3), but P2 (5) is still running, so P5 waits.
4. t = 10: P2 gone → highest priority present is P5 (4) → P5 runs 10–14 → CT P5 = 14.
5. t = 14: P1 (3) > P3 (2) > P4 (1) → P1 runs 14–23 → CT P1 = 23; then P3 23–29 → CT P3 = 29; then P4 29–36 → CT P4 = 36.

Four-algorithm comparison

Verification line: all four charts end at 36 = Σ burst ✓ · SJF and Priority row sums 97/61 and 102/66 re-added ✓ · RR slice count 19 with 17×2 + 2×1 = 36 ✓.

Given data

Rules to state before you start: first-fit = the first partition (scanning in address order) that is big enough; best-fit = the smallest partition that is big enough; worst-fit = the largest partition available. A process that fits nowhere must wait. Total memory 1700K vs total demand 1167K, so the failures below are about fragmentation, not capacity.

First-fit

Why 426K waits: the 100K, 176K, 200K, 300K and 183K holes are all smaller than 426K. 959K of the 1167K requested is placed; 426K is left out even though 959K of free space exists in total — external fragmentation.

Best-fit

Free list after all four placements: 100K, 83K, 88K, 88K, 174K.

Worst-fit

Worst-fit deliberately keeps the largest leftover, but it burns the only two blocks that a 426K request could ever have fitted into whole.

Answer to "which makes the most efficient use of memory"

Best-fit is the only policy that places all four processes, so it makes the most efficient use of memory on this data set — exactly the conclusion printed in the 2016 paper: "Best-fit algorithm makes the most efficient use of memory. It is the only [one] capable of meeting all memory requests in this case."

Verification line: every policy trace re-ran from the free list 100K, 500K, 200K, 300K, 600K; best-fit consumes 1167K with fragments 100+83+88+88+174 = 533K, and 1167 + 533 = 1700K = total memory ✓. First-fit and worst-fit each place 212+417+112 = 741K and leave 426K waiting ✓.

Theory behind this — contiguous allocation, internal vs external fragmentation and compaction → Memory Management.

Given data

Solution

1. Logical address space = 8 pages × 1024 words = 8192 words.
2. Bits in the logical address = log2(8192) = 13 bits. Split check: page bits log2 8 = 3, offset bits log2 1024 = 10, and 3 + 10 = 13 ✓.
3. Physical memory = 32 frames × 1024 words = 32768 words.
4. Bits in the physical address = log2(32768) = 15 bits. Split check: frame bits log2 32 = 5, offset bits 10, and 5 + 10 = 15 ✓.

Verification line: 2¹³ = 8192 ✓ · 2¹⁵ = 32768 ✓ · offset bits identical on both sides of the translation ✓.

Given data

Solution, part by part

Verification line: 12 = 8 page bits + 4 offset bits ✓ · 9 = 5 frame bits + 4 offset bits ✓ · 256 pages × 16 B = 4096 B ✓ · 32 frames × 16 B = 512 B ✓.

Given data

Solution

Verification line: 253 × 16 + 2 = 4050 ✓ · 254 pages × 16 B = 4064 B = 4050 + 14 wasted ✓ · 64 frames × 16 B = 1024 B ✓.

Given data

Solution

Verification line: 3 + 21 + 8 = 32 ✓ · 2²¹ pages × 2⁸ bytes = 2²⁹ bytes = the stated maximum segment length ✓ · offset bits = log2(page size) = 8 ✓.

Given data

Solution

1. TLB hit path: search the TLB, then use the frame from the TLB to fetch the word from memory → T + t = 50 + 100 = 150 ns. Probability 0.8.
2. TLB miss path: search the TLB (50), read the page table from memory (100), reload the TLB, then read the required word from memory (100) → T + 2t = 50 + 200 = 250 ns. Probability 1 − 0.8 = 0.2.
3. EAT = h(T + t) + (1 − h)(T + 2t) = 0.8 × 150 + 0.2 × 250 = 120 + 50 = 170 ns.

EAT = 0.8 × (50 + 100) + (1 - 0.8) × (50 + 2 × 100)
    = 0.8 × 150 + 0.2 × 250
    = 120.0 + 50.0
    = 170.0 ns

Verification line: 0.8 × 150 = 120 ✓ · 0.2 × 250 = 50 ✓ · 120 + 50 = 170 ns ✓ · EAT must lie between the hit path (150) and the miss path (250) ✓.

TLB structure and the hit/miss hardware path → Memory Management · Paging and TLB.

Given data

Solution

1. Convert to one unit first — that is the whole trick in this question. 1 ms = 10⁶ ns, so 25 ms = 25,000,000 ns.
2. Access that takes the page-fault path costs service time + the memory access that follows it: 25,000,000 + 100 = 25,000,100 ns ≈ 25 ms.
3. An access with no page fault costs just 100 ns.
4. With a page-fault rate p the general expression is EAT = (1 − p) × 100 ns + p × 25,000,100 ns. The question does not give p, so the only figure that can be produced from the printed data is the single faulting-access total, 25,000,100 ns.

Verification line: 25 ms = 25 × 10⁶ ns ✓ · 25,000,000 + 100 = 25,000,100 ns ✓ · a page fault is about 250,000 × more expensive than a clean memory access — which is the point the question is really testing.

Given data

Solution

1. A hit costs the associative-register time only: 100 ns.
2. A miss costs the page-table search in memory and then the required access: 100 + 180 = 280 ns.
3. Set up the weighted average and solve: 125 = 100x + 280(1 − x) = 280 − 180x → 180x = 155 → x = 155 ÷ 180 = 0.861.
4. So the associative registers must catch about 86.1 % of the references.

EAT = x(hit) + (1 - x)(miss)
125 = 100x + 280(1 - x)
125 = 280 - 180x
180x = 155
x  = 155/180 = 0.861   (hit ratio, valid because 0 < x < 1)

Verification line: hit 100 < EAT 125 < miss 280 ✓ · x = 155/180 = 0.861 ✓ · 0.861 × 100 + 0.139 × 280 = 86.1 + 38.9 = 125 ns ✓.

Given data

FIFO — frame-by-frame trace

Victim = the page that has been resident longest. Faults land on references 1, 2, 3, 6, 7, 9, 10, 12, 13, 15, 16, 17, 18.

LRU — frame-by-frame trace

Victim = the resident page whose most recent use is furthest back.

Optimal — frame-by-frame trace

Victim = the resident page whose next use is furthest in the future (or never again). Look ahead in the string before every replacement.

Results

Most efficient: Optimal with 9 faults (fault ratio 0.500), then LRU with 12, then FIFO with 13. Optimal is a benchmark only — it needs the future, so it cannot be implemented; among the implementable policies on this string the better one is LRU.

Verification line: FIFO 13 faults + 5 hits = 18 references ✓ · LRU 12 + 6 = 18 ✓ · Optimal 9 + 9 = 18 ✓ · Optimal ≤ LRU ≤ FIFO on this string, as the ratios show.

Given data

FIFO — frame-by-frame trace

LRU — frame-by-frame trace

Optimal — frame-by-frame trace

Results

Best: Optimal (11 faults). Between the two implementable policies, LRU (15) beats FIFO (16) on this string — the locality of 2, 1, 2 in the middle of the string is exactly what LRU exploits and FIFO ignores.

Verification line: 16 + 4 = 20 ✓ · 15 + 5 = 20 ✓ · 11 + 9 = 20 ✓ · hits are the references that repeat a resident page: FIFO hits at references 5, 11, 15, 18.

Given data

FIFO — frame-by-frame trace

LRU — frame-by-frame trace

Optimal — frame-by-frame trace

Results

Best: Optimal (7 faults). Note the teaching point of this string: LRU is worse than FIFO here (10 vs 9). LRU is not guaranteed to beat FIFO on every string — it is a stack algorithm that rewards recent use, and the loop 1, 2, … 1, 2 keeps refreshing exactly the pages FIFO was about to throw away.

Verification line: 9 + 3 = 12 ✓ · 10 + 2 = 12 ✓ · 7 + 5 = 12 ✓ · Optimal's hits are at references 5, 6, 8, 9 and 12.

Given data

Results (frame-by-frame trace: fill the four frames with 5, 6, 1, 2 over the first four references, then replace by FIFO order / least-recently-used / farthest-future-use respectively)

Answer to "which gives the minimum": LRU and Optimal tie at 8 faults — do not write "Optimal alone". On this string the implementable policy (LRU) already reaches the optimal bound, and FIFO is two faults worse.

Verification line: 10 + 10 = 20 ✓ · 8 + 12 = 20 ✓ · 8 + 12 = 20 ✓ · minimum possible faults ≥ number of distinct pages = 6, and both LRU and Optimal land just above it.

Given data

Results

Best: Optimal (8 faults, hit ratio 0.556). LRU is the best implementable choice here with 10; FIFO pays for ignoring the fact that A and B dominate the string.

Verification line: 13 + 5 = 18 ✓ · 10 + 8 = 18 ✓ · 8 + 10 = 18 ✓ · D, F and G appear once or twice, so they are the pages every algorithm keeps evicting.

Given data

Results

Best: Optimal (13). Of the implementable ones MFU (15) beats LRU (18) on this string, which is a good illustration of why MFU exists as a counter-example: a page referenced very often in the past may never be needed again, and MFU throws it out precisely for that reason.

Verification line: 18 + 2 = 20 ✓ · 15 + 5 = 20 ✓ · 13 + 7 = 20 ✓ · the string has 8 distinct pages (0–7) passing through 3 frames, so a fault count this high is expected.

Given data

Optimal working (how to choose the victim at each fault)

1. Load 4, 6, 7 on references 1–3 → 3 faults, frames {4, 6, 7}.
2. Reference 4 (page 1): 6 and 7 are needed again at references 5 and 6, page 4 not until 14 → evict 4, load 1 → fault 4.
3. References 5–7 (6, 7, 1) are all hits — the pages Optimal chose to keep.
4. Reference 8 (page 2): frames hold 6, 7, 1. 6 is needed at 9, 1 at 13, 7 never again → evict 7 → fault 5.
5. Reference 9 (6) hit · reference 10 (2) hit · reference 11 (0): frames 6, 1, 2 — 6 never used again → evict 6 → fault 6.
6. Reference 12 (3): frames 0, 1, 2 — 2 next at 15, 1 at 13, 0 never again → evict 0 → fault 7.
7. References 13 (1) and 14 (4): frames 3, 1, 2 — 3 never used again → evict 3, load 4 → fault 8; page 1 is a hit.
8. Reference 15 (2) hit. Total = 8 page faults.

Best (and only policy asked): Optimal, 8 faults. Since Optimal is a lower bound for any replacement policy on this string, no FIFO or LRU run can do better than 8 here.

Verification line: 8 + 7 = 15 references ✓ · faults at references 1, 2, 3, 4, 8, 11, 12, 14 and hits at 5, 6, 7, 9, 10, 13, 15.

Given data

LRU working

Best of what is asked: LRU with 6 faults (hits at references 5, 6, 7, 10).

Verification line: 6 + 4 = 10 references ✓ · faults at references 1, 2, 3, 4, 8, 9.

Given data

Results

Best of the two: LRU (11 faults). FIFO faults at references 1, 2, 3, 6, 8, 9, 10, 11, 13, 14, 16, 18, 19 and 20 — fourteen of them. LRU keeps 1, 2 and 3 resident through the busy middle of the string, which is where its three extra hits come from.

Verification line: 14 + 6 = 20 ✓ · 11 + 9 = 20 ✓ · distinct pages 1, 2, 3, 4, 5, 6 = 6, so at least 6 faults are unavoidable.

Given data

Results

Best of the two asked: LRU (8 faults). Optimal also reaches 8, so LRU is at the theoretical lower bound on this string.

Verification line: 10 + 10 = 20 ✓ · 8 + 12 = 20 ✓ · distinct pages 0, 1, 2, 3, 4, 7 = 6 ≤ 20 references, so 8 faults is close to the floor of 6.

Belady's anomaly is the counter-intuitive behaviour of the FIFO page-replacement algorithm in which increasing the number of allocated page frames can increase the number of page faults. LRU does not suffer from it because it is a stack algorithm: the pages held with k frames are always a subset of those held with k+1 frames. Named after L. A. Belady, who reported it in 1969.

Given data

Case 1 — FIFO with 3 frames → 9 page faults

Case 2 — FIFO with 4 frames → 10 page faults

The anomaly, side by side

One extra frame costs one extra fault. Reading the two traces: with 3 frames the reference to page 3 at step 8 is a hit, because 3 is still resident; with 4 frames the loading pattern has shifted and 3 was replaced at step 7, so the same reference faults. Mark the difference in columns 7–8 of the two grids and the point makes itself.

Which is best overall on this string? Neither FIFO case makes the point — the anomaly is exactly the argument for the stack property: LRU and Optimal can never fault more often when frames are added, because the set of pages resident with k frames is always contained in the set resident with k+1 frames. FIFO has no such guarantee, which is why its fault count went up from 9 to 10 above.

Verification line: Case 1 → 9 + 3 = 12 ✓ · Case 2 → 10 + 2 = 12 ✓ · the only requirement for demonstrating the anomaly is the same string, same algorithm, more frames, more faults.