Operating Systems

Question 1

(a) SRTF (7 marks)

Track remaining times; at each event pick smallest remaining among arrived.

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

Gantt: P1(0-2) | P2(2-4) | P3(4-5) | P2(5-7) | P4(7-11) | P1(11-16) (2 marks)

Completion: P1=16, P2=7, P3=5, P4=11. Turnaround = Completion − Arrival:

• P1=16, P2=5, P3=1, P4=6 → avg TAT = (16+5+1+6)/4 = 7.0 (2 marks)

Waiting = TAT − Burst:

• P1=9, P2=1, P3=0, P4=2 → avg WT = 12/4 = 3.0 (3 marks)

(b) Round Robin q=3 (5 marks)

Queue events (new arrival enqueued before returning process):

• t=0: run P1 (rem 7→4), during run P2(t2),P3? no P3 at4. Queue after: [P2, P1]
• t=3: run P2 (4→1). Arrivals: P3(t4),P4(t5) enqueue. Queue: [P1, P3, P4, P2]
• t=6: run P1 (4→1). Queue: [P3, P4, P2, P1]
• t=9: run P3 (1→0) done t=10. Queue: [P4, P2, P1]
• t=10: run P4 (4→1). Queue: [P2, P1, P4]
• t=13: run P2 (1→0) done t=14. Queue: [P1, P4]
• t=14: run P1 (1→0) done t=15. Queue: [P4]
• t=15: run P4 (1→0) done t=16.

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)

Completion: P1=15, P2=14, P3=10, P4=16. TAT: P1=15, P2=12, P3=6, P4=11 → avg = 44/4 = 11.0 (1.5) WT = TAT−Burst: P1=8, P2=8, P3=5, P4=7 → avg = 28/4 = 7.0 (1.5)

Question 2

(a) TAS spinlock (4 marks)

test_and_set(target) atomically: reads old value, sets *target=1, returns old. (2)

lock = 0;
acquire(): while (test_and_set(&lock)) ; // spin while old was 1
release(): lock = 0;

(2 marks)

(b) CAS spinlock (3 marks)

CAS(addr, expected, new) atomically: if *addr==expected set *addr=new and return true else return false. (1)

acquire(): while (!CAS(&lock, 0, 1)) ;
release(): lock = 0;

(2 marks)

(c) (3 marks)

Fails bounded waiting (1). ME and progress hold, but there is no queue/ordering: a waiting thread may be starved indefinitely because when the lock frees, any spinning thread (including newly arriving ones) may grab it; no bound on the number of times others enter first (2).

Question 3

(a) (3 marks)

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

Need = Max − Allocation:

(b) Safety (6 marks)

Work=(3,3,2).

• P1 Need(1,2,2)≤Work → Work=(3,3,2)+(2,0,0)=(5,3,2)
• P3 Need(0,1,1)≤Work → Work=(5,3,2)+(2,1,1)=(7,4,3)
• P4 Need(4,3,1)≤(7,4,3) → Work=(7,4,3)+(0,0,2)=(7,4,5)
• P0 Need(7,4,3)≤(7,4,5) → Work=(7,4,5)+(0,1,0)=(7,5,5)
• P2 Need(6,0,0)≤(7,5,5) → Work=(7,5,5)+(3,0,2)=(10,5,7)

All finish → SAFE. Safe sequence: P1, P3, P4, P0, P2 (6 marks; award per correct step, other valid sequences accepted).

(c) P1 requests (1,0,2) (3 marks)

Request(1,0,2) ≤ Need(1,2,2) ✓ and ≤ Available(3,3,2) ✓. Pretend-allocate: Available=(2,3,0), P1 Alloc=(3,0,2), Need=(0,2,0). Run safety from Work=(2,3,0): P3 Need(0,1,1)? C=0>0 no... check: (0,1,1)≤(2,3,0)? C:1≤0 false. Try P1 Need(0,2,0)≤(2,3,0)✓→Work=(4,3,2). Then P3(0,1,1)≤(4,3,2)✓→(6,4,3); P4(4,3,1)✓→(6,4,5); P0(7,4,3)? A:7>6 no; P2(6,0,0)≤(6,4,5)✓→(9,4,7); P0(7,4,3)≤(9,4,7)✓. All finish → safe, GRANT the request (3 marks).

Question 4

(a) EAT (4 marks)

On hit (prob $1-p$): 100 ns. On fault (prob $p$): clean 40% costs 8 ms, dirty 60% costs 20 ms. Average fault service = $0.4(8) + 0.6(20) = 3.2 + 12 = 15.2$ ms $= 15{,}200{,}000$ ns. (2)

$\text{EAT} = (1-p)(100) + p(15{,}200{,}000 + 100) \approx 100 + p \cdot 15{,}200{,}000 \text{ ns}$ (2 marks)

(b) Max p (4 marks)

Within 20%: EAT ≤ 120 ns. $100 + p(15{,}200{,}000) \le 120$ $p \le 20 / 15{,}200{,}000 = 1.316\times10^{-6}$ $p_{max} \approx 1.32\times10^{-6}$ (≈ 1 fault per 760,000 accesses). (4 marks)

(c) Fault steps (2 marks)

Trap to OS → check reference valid (else abort) → find free frame / choose victim (write back if dirty) → schedule disk read of page → update page table (valid bit, frame) → restart faulting instruction. (2 marks, any ordered ≥4 steps)

Question 5

(a) Output (4 marks)

A:5 then B:10, always in that order. (2) Child increments its copy of x (0→5) prints A:5, exits. Parent wait(NULL) blocks until child terminates, so A prints before B; then parent's x (still 0) →10, prints B:10. (2)

(b) (2 marks)

fork gives child a separate address space — writes are private; parent's x unchanged (1). Cheap via copy-on-write: pages shared read-only until a write triggers a copy (1).

(c) (2 marks)

Child terminates but parent never reaps it → its PCB/exit status lingers in the process table as a zombie (defunct) process; accumulation can exhaust PID/table entries. (2)

Question 6

(a) (5 marks)

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

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

C-LOOK (up serving, jump to lowest, continue up; no service on jump-back except it counts as movement): Up: 53→65→67→98→122→124→183 = 130. Jump 183→14 = 169. Then 14→37 = 23. Total = 130 + 169 + 23 = 322 (2.5) (Accept 130+169 = 299 if jump-back and remaining lower requests handling stated; standard C-LOOK counts return + serve remaining = 322.)

(b) (3 marks)

RAID 5 small write: updating one block requires read-old-data + read-old-parity, compute new parity, write-data + write-parity = 4 I/Os per logical write (read-modify-write) (1.5). RAID 10 (mirrored stripes) just writes each block to two mirrors = 2 I/Os, no parity recompute (1). Trade-off: RAID 10 costs 50% capacity (mirroring) vs RAID 5's single-parity overhead of only $1/N$ (0.5).

[
{"claim":"SRTF average waiting time = 3.0","code":"tat=[16,5,1,6]; burst=[7,4,1,4]; wt=[t-b for t,b in zip(tat,burst)]; result=(sum(wt)/4==3.0)"},
{"claim":"SRTF average turnaround = 7.0","code":"tat=[16,5,1,6]; result=(sum(tat)/4==7.0)"},
{"claim":"RR q=3 average waiting = 7.0","code":"tat=[15,12,6,11]; burst=[7,4,1,4]; wt=[t-b for t,b in zip(tat,burst)]; result=(sum(wt)/4==7.0)"},
{"claim":"Banker Available = (3,3,2)","code":"total=[10,5,7]; alloc=[[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]; s=[sum(c) for c in zip(*alloc)]; avail=[t-x for t,x in zip(total,s)]; result=(avail==[3,3,2])"},
{"claim":"Max tolerable page fault rate approx 1.316e-6","code":"p=20/15200000; result=(abs(p-1.3157894736842e-6)<1e-9)"},
{"claim":"SCAN total head movement = 331","code":"result=((199-53)+(199-14)==331)"},
{"claim":"C-LOOK total head movement = 322","code":"result=(130+169+23==322)"}
]