Operating Systems

Question 1 (14 marks)

(a) SRTF Gantt chart (4 marks)

Track remaining times; preempt when a shorter-remaining job arrives.

• t=0: only P1 → run P1.
• t=2: P2 arrives (rem 4) vs P1 (rem 5) → run P2.
• t=4: P3 arrives (rem 1) vs P2 (rem 2) → run P3.
• t=5: P3 done. P4 arrives (rem 4). Ready: P1(5), P2(2), P4(4) → run P2.
• t=7: P2 done. Ready: P1(5), P4(4) → run P4.
• t=11: P4 done. Run P1(5).
• t=16: P1 done.

Gantt: P1[0–2] P2[2–4] P3[4–5] P2[5–7] P4[7–11] P1[11–16] (2 marks correct sequence, 2 marks correct times)

(b) Turnaround / waiting (4 marks)

Completion times: P1=16, P2=7, P3=5, P4=11.

Average waiting time = (9+1+0+2)/4 = 3.0. (2 marks TAT, 2 marks WT + average)

(c) Round Robin q=3 (4 marks)

Rule: new arrival enqueued before a just-preempted process.

• t=0: P1 runs 0–3 (rem 4). Arrivals during: P2(t2). Queue after: [P2, P1].
• t=3: P2 runs 3–6 (rem 1). During: P3(t4),P4(t5) enqueued before P1. Queue: [P1, P3, P4, P2]. Wait — P2 preempted at t=6 goes to back. Queue before P2 requeue: [P1, P3, P4]; then P2 → [P1,P3,P4,P2].
• t=6: P1 runs 6–9 (rem 1). Queue: [P3, P4, P2, P1].
• t=9: P3 runs 9–10 (done). Queue: [P4, P2, P1].
• t=10: P4 runs 10–13 (rem 1). Queue: [P2, P1, P4].
• t=13: P2 runs 13–14 (done). Queue: [P1, P4].
• t=14: P1 runs 14–15 (done). Queue: [P4].
• t=15: P4 runs 15–16 (done).

Gantt: P1[0–3] P2[3–6] P1[6–9] P3[9–10] P4[10–13] P2[13–14] P1[14–15] P4[15–16] (2 marks queue handling, 2 marks times)

(d) (2 marks)

• SRTF strictly wins when bursts vary widely (a mix of short and long jobs), since short jobs preempt long ones minimising total waiting. (1)
• RR preferred interactively because it bounds response time / prevents starvation and needs no burst-length prediction. (1)

Question 2 (14 marks)

(a) Available & Need (4 marks)

Sum of Allocation = (7,2,3). Total = (10,5,7). Available = (10,5,7) − (7,2,3) = (3,3,2). (2)

Need = Max − Allocation:

(2)

(b) Safety (7 marks)

Work = (3,3,2).

• P1: Need(1,2,2) ≤ (3,3,2) ✓. Work = (3,3,2)+(2,0,0) = (5,3,2). (1)
• P3: Need(0,1,1) ≤ (5,3,2) ✓. Work = (5,3,2)+(2,1,1) = (7,4,3). (1)
• P0: Need(7,4,3) ≤ (7,4,3) ✓. Work = (7,4,3)+(0,1,0) = (7,5,3). (1)
• P2: Need(6,0,0) ≤ (7,5,3) ✓. Work = (7,5,3)+(3,0,2) = (10,5,5). (1)
• All finished → SAFE. (1)

Safe sequence: ⟨P1, P3, P0, P2⟩ (2). (Others valid, e.g. ⟨P1,P3,P4…⟩ variants.)

(c) Request P1 = (1,0,2) (3 marks)

• Request ≤ Need(1,2,2)? (1,0,2)≤(1,2,2) ✓. (1)
• Request ≤ Available(3,3,2)? (1,0,2)≤(3,3,2) ✓. (1)
• Pretend-allocate: Available = (2,3,0); P1 Alloc=(3,0,2), Need=(0,2,0). Check safety: P3 Need(0,1,1)≤(2,3,0)? C: 1≤0 ✗. P1 Need(0,2,0)≤(2,3,0)✓ → Work=(2,3,0)+(3,0,2)=(5,3,2); then P3(0,1,1)≤(5,3,2)✓ → (7,4,3); P0(7,4,3)≤✓→(7,5,3); P2(6,0,0)≤✓. Safe → request can be granted. (1)

Question 3 (12 marks)

(a) Address split (4 marks)

0x00403ABC = binary. Offset = low 12 bits = 0x3ABC & 0xFFF → 0xABC = 2748. (1) Remaining bits 0x00403ABC >> 12 = 0x00403. Level-2 index = low 10 bits of that = 0x403 & 0x3FF = 0x003 = 3. (1) Level-1 index = 0x00403 >> 10 = 0x1 = 1. (2)

So: L1 = 1, L2 = 3, offset = 0xABC (2748).

(b) Page-table memory (5 marks)

• Level-1 table: 1024 entries × 4 B = 4096 B (4 KiB). (1)
• Range 1 0x0000–0x3FFF = 16 KiB = 4 pages, all in L1 index 0 → needs one L2 table. (1)
• Range 2 0x7FFFF000–0x7FFFFFFF = one page. 0x7FFFF000 >> 12 = 0x7FFFF; L1 index = 0x7FFFF >> 10 = 0x1FF = 511 → needs one L2 table. (1)
• Two L2 tables × 4 KiB = 8 KiB. (1)
• Total = 4 KiB + 8 KiB = 12 KiB = 12288 bytes. (1)

(c) (3 marks) A flat table would need $2^{20}$ entries × 4 B = 4 MiB regardless of usage. The two-level scheme only allocates L2 tables for regions actually used, so sparse address spaces need far fewer entries — saving memory.

Question 4 (12 marks)

(a) Semaphores + pseudocode (5 marks)

Init: empty = 3, full = 0, mutex = 1. (2)

Producer:                 Consumer:
  P(empty)                  P(full)
  P(mutex)                  P(mutex)
  add item to buffer        remove item
  V(mutex)                  V(mutex)
  V(full)                   V(empty)

(3 — correct ordering both)

(b) Deadlock from swapped order (4 marks)

Bad producer: P(mutex); P(empty); …. Interleaving: buffer full (empty=0). Producer does P(mutex) (mutex→0, holds it), then blocks on P(empty) (empty=0). A consumer arrives, does P(full) OK, then P(mutex) — blocks because producer holds mutex. Now producer waits for consumer to free a slot (increment empty), but consumer waits for producer to release mutex → circular wait → deadlock. (4)

(c) Coffman conditions (3 marks)

• Hold-and-wait: producer holds mutex while waiting for empty. (1.5)
• Circular wait: producer→(needs empty from consumer), consumer→(needs mutex from producer). (1.5) (Mutual exclusion and no-preemption also present but the directly-caused pair is hold-and-wait + circular wait.)

Question 5 (8 marks)

(a) SCAN & C-SCAN (5 marks)

Sorted requests: 14, 37, 65, 67, 98, 122, 124, 183. Head=53, moving up.

SCAN: up to 199 then down. Order: 65,67,98,122,124,183,199,(turn) 37,14. Movement = (199−53) + (199−14) = 146 + 185 = 331. (2.5)

C-SCAN: up to 199, wrap to 0, continue up. Order: 65,67,98,122,124,183,199 → 0 → 14,37. Movement = (199−53) + (199−0) + (37−0) = 146 + 199 + 37 = 382. (2.5)

(b) RAID 5 (3 marks)

• Usable = (5−1)×4 TB = 16 TB (one disk parity). (1)
• Tolerates 1 disk failure. (1)
• RAID 6 uses two parity blocks → survives two simultaneous failures, important for large arrays where rebuild time raises the chance of a second failure. (1)

[
  {"claim":"SRTF average waiting time = 3.0","code":"wt=[9,1,0,2]; result = (sum(wt)/4)==3"},
  {"claim":"Banker available vector is (3,3,2)","code":"total=[10,5,7]; alloc=[7,2,3]; result = [total[i]-alloc[i] for i in range(3)]==[3,3,2]"},
  {"claim":"Two-level page table total = 12288 bytes","code":"l1=1024*4; l2=2*(1024*4); result = (l1+l2)==12288"},
  {"claim":"SCAN movement=331 and C-SCAN=382","code":"scan=(199-53)+(199-14); cscan=(199-53)+(199-0)+(37-0); result = (scan==331) and (cscan==382)"},
  {"claim":"RAID5 usable capacity 5x4TB = 16 TB","code":"result = (5-1)*4==16"}
]