25-Comp-A5 Operating Systems, December 2019, Q1

Question 1 (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. Five CPU-only processes with the arrivals/execution times above.

Find. (i) the lowest achievable mean turnaround under any non-preemptive dispatch order; (ii) the lowest achievable mean turnaround if preemption is also allowed.

Approach. Both parts ask for the best a clairvoyant scheduler could do, not what a named policy (FCFS/SJF) achieves — (i) is found by exhaustively searching all 5! = 120 release-respecting dispatch orders (idling before a ready job is allowed, and is sometimes optimal); (ii) is found by Shortest-Remaining-Time-First (SRTF), the preemptive policy proven optimal for minimizing mean turnaround/waiting time under arbitrary arrivals.

(i) Greedy non-preemptive SJF is a useful first pass but is not guaranteed optimal. Dispatching the shortest ready job at each decision point gives Proc1(25–39), Proc4(39–41), Proc2(41–48), Proc5(48–49), Proc3(49–70): turnarounds 14, 7, 21, 7, 39, mean $88/5=17.6$ s. This is not yet optimal because SJF-among-ready only maximizes locally; staggered arrivals can make it worth idling to let an even shorter job arrive.
Exhaustive search over all 120 release-respecting orders finds a strictly better schedule. The true minimum idles the CPU past Proc1 (even though Proc1 is already waiting at $t=25$) so that Proc2 can run first as soon as it arrives at $t=27$: $$\text{Optimal order: Proc2}(27\text{-}34)\to\text{Proc4}(34\text{-}36)\to\text{Proc1}(36\text{-}50)\to\text{Proc5}(50\text{-}51)\to\text{Proc3}(51\text{-}72)$$ Turnarounds: $TT_2=34-27=7,\ TT_4=36-34=2,\ TT_1=50-25=25,\ TT_5=51-42=9,\ TT_3=72-31=41$. $$\boxed{\overline{TT}_{\text{non-preempt,min}}=\dfrac{7+2+25+9+41}{5}=\dfrac{84}{5}=16.8\ \text{s}}$$

Fig. Q1(a)(i) — the offline-optimal non-preemptive schedule keeps the CPU idle until $t=27$ s (past Proc1's arrival at 25 s), letting Proc1 wait so the much shorter Proc2/Proc4 clear first.

(ii) SRTF (Shortest-Remaining-Time-First) is optimal once preemption is allowed. Event-driven simulation: only Proc1 is ready at $t=25$, so it runs; at $t=27$ Proc2 arrives with less remaining work (7 s) than Proc1 has left (12 s), so Proc1 is preempted. Proc2 runs to completion at $t=34$ (Proc3 arrives at $t=31$ with 21 s remaining — more than Proc2's 3 s left — so no further preemption). At $t=34$, Proc4 (2 s) is shortest, runs to $t=36$. Proc1 (12 s remaining) resumes at $t=36$; at $t=42$ Proc5 arrives with only 1 s remaining (less than Proc1's 6 s left), preempting Proc1 again. Proc5 finishes at $t=43$, Proc1 resumes and finishes its last 6 s at $t=49$, and Proc3 (queued since $t=31$) finally runs uninterrupted from $t=49$ to $t=70$. $$\text{Finish times: Proc2}=34,\ \text{Proc4}=36,\ \text{Proc5}=43,\ \text{Proc1}=49,\ \text{Proc3}=70$$ Turnarounds: $TT_2=7,\ TT_4=2,\ TT_5=1,\ TT_1=49-25=24,\ TT_3=70-31=39$. $$\boxed{\overline{TT}_{\text{any,min}}=\dfrac{7+2+1+24+39}{5}=\dfrac{73}{5}=14.6\ \text{s}}$$ Preemption buys a further 2.2 s of mean turnaround over the best non-preemptive schedule, entirely by letting the very short Proc4/Proc5 cut into Proc1's burst rather than making them wait behind it.

Fig. Q1(a)(ii) — SRTF preempts Proc1 twice, once for the newly-arrived Proc2 and once for Proc5, before letting it finish.

Final Results – Question 1(a)
Quantity	Value
Minimum mean turnaround, any non-preemptive strategy	16.8 s
Minimum mean turnaround, preemption allowed (SRTF)	14.6 s

(b) Why CPU scheduling is harder on a multiprocessor. A single-CPU scheduler only has to pick one process from a ready queue; a multiprocessor scheduler must additionally decide which of several CPUs runs it, and that choice interacts with several effects a uniprocessor never faces. Load balancing requires spreading ready processes evenly across CPUs (push/pull migration) so no processor idles while another queues work, but migrating a process off the CPU that holds its cache-warm data destroys processor/cache affinity — soft affinity tries to keep a process on the CPU it last ran on to reuse cache contents, in tension with load balancing. Symmetric multiprocessing (SMP) also means several CPUs may try to schedule from a shared ready queue simultaneously, so the queue itself needs synchronization (locks), and lock contention becomes a scalability bottleneck as core counts grow — a cost that simply does not exist with one ready queue and one consumer. On NUMA (non-uniform memory access) systems, a process's memory may be "closer" to one CPU than another, so the scheduler must also weigh memory locality against load balance. Finally, cooperating threads of a single parallel application may need gang scheduling (all runnable simultaneously across CPUs) to communicate efficiently, a coordination problem that has no single-CPU analogue at all.

(c) Priority-based page replacement can express any of FIFO, LRU or MFU purely by choosing how the priority number is set and which extreme is evicted — the replacement rule itself never changes ("evict the resident page with priority $p$ extremal for the chosen policy"); only the priority-assignment rule and the eviction direction differ:

Policy	Priority assignment rule	Evict page with
FIFO	$p(\text{page})=(\text{load time})$, set once when the page is brought in and never updated afterwards	minimum $p$ (i.e. the page loaded longest ago)
LRU	$p(\text{page})=(\text{time of most recent reference})$, rewritten to the current clock/counter value on every access, hit or fault	minimum $p$ (i.e. the page referenced longest ago)
MFU	$p(\text{page})=(\text{reference count})$, incremented by 1 on every access since the page was loaded	maximum $p$ (i.e. the page referenced most often)

Example: pages A, B, C loaded in that order, then referenced B, A, B, C, A. Under FIFO the priorities never move from their load-order stamps (A=1, B=2, C=3), so a fault always evicts A first regardless of the reference pattern. Under LRU each reference rewrites that page's timestamp to "now": after the trace the last-touch times are B = step 3, C = step 4, A = step 5, so the least-recently-used page is B and LRU evicts B next — a different victim from FIFO's A, because A was re-referenced most recently even though it was loaded first. Under MFU the running counts are A=2, B=2, C=1 after the trace, so MFU evicts whichever of A/B has the higher count once a tie-break rule is applied — illustrating that MFU deliberately punishes the hottest page, the opposite intuition from LRU/LFU, and is rarely used in practice for exactly that reason (a page referenced heavily is usually about to be referenced again).

Concept & Theory

Topic. Optimal offline CPU scheduling with staggered arrivals; multiprocessor scheduling complications; priority-number encodings of standard page-replacement policies.

Key relations. Mean turnaround $\overline{TT}=\frac{1}{n}\sum_i(\text{finish}_i-\text{arrival}_i)$; SRTF minimizes mean turnaround/waiting time among all preemptive policies for a fixed arrival/burst sequence; page-priority eviction rule: evict $\arg\min_p$ or $\arg\max_p$ depending on policy.

Why this works. Non-preemptive SJF is only optimal when all jobs are simultaneously available; once arrivals are staggered, deliberately idling the CPU to let a very short job arrive can lower the sum of completion times more than it costs in delay to the jobs already waiting — this is exactly the mechanism the 120-order exhaustive search exploits. SRTF extends the same idea to fine-grained (any instant) decisions, which can only ever do at least as well as any non-preemptive schedule. The FIFO/LRU/MFU priority encodings work because "priority" is just a free real-valued label on each resident page; any total order the eviction rule can compare (age, recency, frequency) reproduces the corresponding classical algorithm exactly.

Common pitfall. Assuming greedy SJF-among-ready-jobs is automatically optimal once arrivals are staggered (it is a good heuristic but provably suboptimal here); confusing LRU's "most recent reference" priority with FIFO's "load time" priority, which coincide only if a page is never re-referenced after loading.

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), Ch.5 (CPU Scheduling, multiprocessor scheduling) and Ch.10 (Virtual Memory, page-replacement algorithms).

Question 1 of 7

Question 1 (20 marks)