25-Comp-A5 Operating Systems · May 2015

Question 6 of 7: Variant Round-Robin Scheduling; Page-Reference LRU Trace

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Question 6: Variant Round-Robin Scheduling; Page-Reference LRU Trace (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given (a). Four single-burst, no-I/O processes; each process's own OWN time slice is fixed once from its total execution time (never adaptive during its run): <4 s → 2 s slice, 4–12 s (exclusive of 12) → 3 s slice, ≥12 s → 4 s slice.

Find. The mean turnaround time across the four processes under this variant Round Robin.

Approach. Run a standard FIFO ready-queue Round Robin, but give each process its own fixed slice (from the table above) every time it is dispatched; a process whose remaining burst exceeds its own slice is preempted and re-queued at the back, one whose remaining burst is at most its slice runs to completion.

1. Trace the queue. $t{=}0$: only Proc1 is present; it runs its 4 s slice, $0\to4$ (remaining $16-4=12$). At $t{=}4$, Proc3 arrives (enqueued first, per the stated convention) and Proc1 is re-queued behind it: queue order becomes Proc2, Proc3, Proc1 (Proc2 had already been waiting since $t{=}2$). Proc2 runs its 3 s slice, $4\to7$ (remaining $8-3=5$); Proc4 arrives at $t{=}6$ mid-slice and is enqueued the moment it arrives. At $t{=}7$ Proc2 is re-queued: order is Proc3, Proc1, Proc4, Proc2.
2. Continue the round-robin cycle. Proc3 runs $7\to11$ (remaining $18-4=14$, re-queued). Proc1 runs $11\to15$ (remaining $12-4=8$, re-queued). Proc4 runs its 2 s slice $15\to17$ and, since its remaining burst was exactly 2 s, finishes at $t=17$ (no re-queue). Proc2 runs $17\to20$ (remaining $5-3=2$, re-queued). Proc3 runs $20\to24$ (remaining $14-4=10$, re-queued). Proc1 runs $24\to28$ (remaining $8-4=4$, re-queued). Proc2's remaining burst (2 s) is now under its own 3 s slice, so it runs to completion $28\to30$ and finishes at $t=30$.
3. Finish the remaining two processes. Proc3 runs $30\to34$ (remaining $10-4=6$, re-queued). Proc1's remaining burst (4 s) exactly matches its slice; it runs $34\to38$ and finishes at $t=38$. Only Proc3 is left: it runs $38\to42$ (remaining $6-4=2$, re-queued to itself, since it is the only process left), then runs its final 2 s $42\to44$ and finishes at $t=44$. $$TT_{Proc1}=38-0=38,\quad TT_{Proc2}=30-2=28,\quad TT_{Proc3}=44-4=40,\quad TT_{Proc4}=17-6=11$$ $$\boxed{\overline{TT} = \dfrac{38+28+40+11}{4} = \dfrac{117}{4} = 29.25\ \text{s}}$$

Given (b). Reference string of 20 accesses: 311,312,313,314,312,311,315,316,312,312,311,313,317,316,313,312,312,311,313,316; demand paging (a page loads only on first reference / fault); frames start empty.

Find. (i) The minimum possible page-fault count for this string under any replacement policy and any number of frames. (ii) The LRU fault count with exactly 3 frames.

Approach. (i) The absolute floor on page faults is set purely by how many distinct pages ever appear — each must fault at least once, on its first reference, and if there are at least that many frames available no page is ever evicted, so no page faults twice. (ii) Step through the string maintaining 3 frames, evicting the least-recently-used page on every fault.

1. (i) Minimum possible faults. The distinct pages referenced are $\{311,312,313,314,315,316,317\}$ — seven distinct pages. Every page must fault the first time it is ever referenced (it cannot already be resident), so seven faults are unavoidable regardless of algorithm or frame count; with at least 7 frames allocated (enough to hold every distinct page simultaneously, so nothing is ever evicted), no page faults a second time. $$\boxed{\text{Minimum possible faults} = 7}$$
2. (ii) LRU trace, 3 frames. Stepping through the string (full trace in the table below): the first three references (311, 312, 313) fault to fill the empty frames. Page 314 faults, evicting 311 (least recently used). Reference 312 hits; 311 faults again, evicting 313 (now LRU, since 312 and 314 were touched more recently). From there, 315 faults (evicts 314), 316 faults (evicts 312), 312 faults again (evicts 311), a hit on 312, then 311 faults (evicts 315), 313 faults (evicts 316), 317 faults (evicts 312), 316 faults (evicts 311), a hit on 313, 312 faults (evicts 317), a hit on 312, 311 faults (evicts 316), a hit on 313, and finally 316 faults once more (evicts 312). Counting every FAULT row in the trace table gives 15 faults. $$\boxed{\text{LRU faults (3 frames)} = 15}$$