Operating Systems

Question 1

(a) Assumptions: one context switch of cost $s$ occurs between each quantum of execution; jobs are pure CPU. Over the whole run, total useful CPU time is $N\cdot T$. Each job of length $T$ is chopped into $T/q$ quanta, so total number of scheduling slices $\approx N\cdot T/q$, each incurring one switch cost $s$ (per switch). Useful work per quantum $= q$, overhead per quantum $= s$.

Marks: correct ratio structure (2), independent of $N,T$ observation / assumptions stated (2).

(b) With $q\mid T$, each job needs $T/q$ quanta. Under RR with $N$ jobs all present, jobs are served in cyclic order. The last job finishes after all $N\cdot(T/q)$ quanta plus the switches between them. Number of context switches before the last quantum completes $= N\cdot(T/q) - 1$ (a switch before each slice except we can neglect the leading one; standard convention counts one switch per slice boundary). Using one switch per served quantum:

More precisely the last job completes on the final quantum, so:

Either accepted with justification. Marks: recognise all quanta precede last completion (2), useful term $NT$ (1), overhead term (2).

(c) As $q\to\infty$, each job's requirement $T<q$, so each job runs to completion in a single quantum with no preemption — the scheduler serves job 1 fully, then job 2, etc. This is exactly FCFS. Turnaround of job $i$ (ignoring $s$) $= i\cdot T$. Average:

For small $q$, all $N$ jobs finish at nearly the same time $\approx NT$ (round-robin makes them progress together), giving average turnaround $\approx N\,T$ — much worse for identical jobs. Trade-off: large $q$ (→FCFS) minimizes average turnaround for identical jobs but harms response time / fairness; small $q$ improves responsiveness but raises overhead and turnaround. Marks: prove degeneration to FCFS (2), $\bar T_{FCFS}=T(N+1)/2$ (2), comparison + trade-off sentence (2).

(d) Efficiency $= q/(q+s) = 2/(2+0.5) = 2/2.5 = 0.8 = 80\%$. $T_{last}$: $N=4,T=8,q=2 \Rightarrow$ quanta per job $=4$, total quanta $=16$. $T_{last} = N\,T + (N T/q)\,s = 32 + 16\times0.5 = 32+8 = 40$ ms. (Using the $-1$ convention: $32+(16-1)0.5=39.5$ ms — either accepted.) Marks: efficiency (2), $T_{last}$ (3).

Question 2

(a) counter++ = load, increment, store (three steps, non-atomic). If both threads read the same old value before either stores, one increment is lost (lost update). Minimum final value: with $M$ operations each, interleavings can make both threads repeatedly clobber each other. The smallest achievable value is 2 (not lower):

• Thread A loads 0.
• Thread B runs all $M$ increments to completion → counter = $M$... but A still holds 0.

Tight-minimum construction: Interleave so each store overwrites, but note counter must reach at least $M$ from one thread's run then be knocked back. Classic result: the minimum is 2. Construction: A reads 0. B does $M-1$ increments (counter=$M-1$). A does its remaining loop reading/writing... Standard proof: one thread can hold a stale value spanning the other's entire run, but each of its own $M$ writes advances counter, so the losing thread still contributes; the theoretical floor is 2 (each thread guarantees at least one uncontested final store contributing +1, and one full run can be entirely masked to net +1). Accept: min $=2$ with a valid load/add/store interleaving; proof that it cannot be 0 or 1 because the last thread to store writes at least (its own last read + M-progress ≥ 1), and two threads' final stores give ≥2. Marks: lost-update mechanism (3), min value 2 (2), valid interleaving + tightness (2).

(b) (i) Mutual exclusion — YES. test_and_set atomically reads old value and sets to 1; only the thread that observes old value 0 enters. Atomicity guarantees at most one winner. (ii) Progress — YES. If lock is free (0) and threads are contending, one will succeed (some thread's TAS reads 0); no thread outside its CS blocks entry. No deadlock on a single lock. (iii) Bounded waiting — NO. A spinning thread can be repeatedly overtaken; nothing enforces order/fairness. A thread could starve indefinitely while others keep re-acquiring. Marks: 2 each with justification.

(c) Use semaphore sem initialised to $S_0 = k$.

P(sem)          // wait
   <region>
V(sem)          // signal

A thread completes P (and enters) only after decrementing $S$. Invariant: $S = k - (\text{completed P}) + (\text{completed V}) \ge 0$. Number inside region $=$ (completed P) − (completed V) $= k - S \le k$ since $S\ge 0$. Hence at most $k$ threads inside simultaneously. A thread cannot complete P when $S=0$ (it blocks), enforcing the bound. Marks: correct P/V placement + init $k$ (3), invariant statement (2), derivation inside $=k-S\le k$ (2).

Question 3

(a) Page size $4\text{KB}=2^{12}$ → offset = 12 bits. Remaining $32-12 = 20$ bits for $p1+p2$. Each page table must fit in one page (4096 B) with 4-byte PTEs → entries per table $=4096/4 = 1024 = 2^{10}$ → 10 bits each. So $p2 = 10$, and $p1 = 20-10 = 10$ bits. Split: $p1=10,\ p2=10,\ \text{offset}=12$. Marks: offset (2), entries per table $=1024$ (2), 10/10 split (2).

(b) A flat single-level table needs one PTE per virtual page over the entire space: $2^{20}$ entries × 4 B $= 2^{22} = 4$ MB, regardless of usage. A two-level table allocates second-level tables only for used regions; unused $p1$ slots point to nothing.

Numeric example: process uses 1 code page (low address, $p1=0$) and 1 stack page (high address, $p1=1023$).

• Flat: $4$ MB (must be fully allocated).
• Two-level: 1 outer (top-level) table = 4 KB, plus 2 second-level tables (one for $p1=0$, one for $p1=1023$) = $2\times 4\text{KB} = 8$ KB. Total $= 4+8 = 12$ KB. Saving: 4 MB → 12 KB. Marks: explanation sparse-alloc (2), flat = 4 MB (2), two-level = 12 KB (2).

(c) Total $(10,5,7)$. Sum of Allocation $= (0+2+3+2+0,\;1+0+0+1+0,\;0+0+2+1+2) = (7,2,5)$. Available $= (10,5,7)-(7,2,5) = (3,3,2)$.

Need = Max − Allocation:

Safety: Work=(3,3,2).

• $P_1$ Need(1,2,2)≤Work → run, Work=(3,3,2)+(2,0,0)=(5,3,2).
• $P_3$ Need(0,1,1)≤(5,3,2) → Work=(5,3,2)+(2,1,1)=(7,4,3).
• $P_0$ Need(7,4,3)≤(7,4,3) → Work=(7,4,3)+(0,1,0)=(7,5,3).
• $P_2$ Need(6,0,0)≤(7,5,3) → Work=(7,5,3)+(3,0,2)=(10,5,5).
• $P_4$ Need(4,3,1)≤(10,5,5) → Work=(10,5,7).

Safe sequence: $\langle P_1,P_3,P_0,P_2,P_4\rangle$. State is safe.

Request $P_1=(1,0,2)$: Check $\le Need_1(1,2,2)$ ✓ and $\le Available(3,3,2)$ ✓. Tentatively: Available $=(3,3,2)-(1,0,2)=(2,3,0)$; $Alloc_1=(3,0,2)$; $Need_1=(0,2,0)$. Re-run safety with Work=(2,3,0):

• $P_3$ Need(0,1,1)? C-component 1>0 → no. $P_1$ Need(0,2,0)≤(2,3,0) → Work=(2,3,0)+(3,0,2)=(5,3,2).
• $P_3$ Need(0,1,1)≤(5,3,2) → Work=(7,4,3).
• $P_0$(7,4,3)≤(7,4,3) → (7,5,3); $P_2$(6,0,0)≤ → (10,5,5); $P_4$(4,3,1)≤ → (10,5,7). ✓ Request CAN be granted (safe sequence $\langle P_1,P_3,P_0,P_2,P_4\rangle$). Marks: Available (2), Need matrix (2), safe sequence (2), request analysis (2).

[
  {"claim":"RR efficiency q/(q+s)=0.8 for q=2,s=0.5","code":"q=2; s=Rational(1,2); eff=q/(q+s); result=(eff==Rational(4,5))"},
  {"claim":"T_last=40ms for N=4,T=8,q=2,s=0.5 (no -1 convention)","code":"N=4;T=8;q=2;s=Rational(1,2); Tlast=N*T+(N*T/q)*s; result=(Tlast==40)"},
  {"claim":"FCFS avg turnaround T(N+1)/2 equals 20 for N=4,T=8","code":"N=4;T=8; avg=T*(N+1)/2; result=(avg==20)"},
  {"claim":"Banker Available=(3,3,2)","code":"tot=[10,5,7]; alloc=[[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]; s=[sum(a[i] for a in alloc) for i in range(3)]; avail=[tot[i]-s[i] for i in range(3)]; result=(avail==[3,3,2])"},
  {"claim":"Two-level PT for 2 pages = 12KB vs flat 4MB","code":"flat=2**20*4; two=4096+2*4096; result=(flat==4194304 and two==12288)"}
]