25-Comp-A5 Operating Systems · December 2013

Question 1 of 7: CPU Scheduling and Multiprocessor Difficulty

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

Question 1: CPU Scheduling and Multiprocessor Difficulty (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. Four processes, each with a single CPU burst and no I/O; a single CPU.

Find. (i) The theoretical minimum mean turnaround time achievable by any scheduling strategy. (ii) The mean turnaround time under FCFS. (iii) The mean turnaround time under the execution-time-tiered Round Robin variant (slice 2 s for burst <5 s, 3 s for 5–9 s, 4 s for everything else).

Approach. Since turnaround = completion − arrival and total arrival time is fixed, minimizing mean turnaround is equivalent to minimizing the sum of completion times — which preemptive Shortest-Remaining-Time-First (SRTF) achieves optimally for any arrival pattern. Build the FCFS and RR-variant schedules directly from the arrival/execution data, respecting each policy's dispatch rule.

1. (i) Theoretical minimum — preemptive SRTF. "Any CPU scheduling strategy" includes preemptive policies, and preemptive Shortest-Remaining-Time-First is provably optimal for minimizing mean completion (hence mean turnaround, since arrival times are fixed) time for an arbitrary arrival pattern — at every decision point (arrival or completion) it runs whichever ready process has the least remaining work. At $t=0$ only P1 (remaining 15) is ready, so it runs. At $t=2$, P2 arrives with remaining 7 $<$ P1's remaining 13, so P2 preempts. At $t=4$, P3 arrives with remaining 18 $>$ P2's remaining 5, so P2 continues. At $t=6$, P4 arrives with remaining 2 $<$ P2's remaining 3, so P4 preempts and runs to completion (2 units, finishing at $t=8$). P2 (remaining 3) resumes and finishes at $t=11$. Only P1 (remaining 13) and P3 (remaining 18) are left; P1 runs to completion at $t=24$, then P3 runs to completion at $t=42$. $$TT_{P4}=8-6=2,\quad TT_{P2}=11-2=9,\quad TT_{P1}=24-0=24,\quad TT_{P3}=42-4=38$$ $$\boxed{\overline{TT}_{min} = \dfrac{2+9+24+38}{4} = \dfrac{73}{4} = 18.25\ \text{s}}$$ This; no schedule (preemptive or not) can do better, since SRTF is a proven optimum for this metric.
2. (ii) FCFS. All four processes have already arrived in strictly increasing arrival order by the time each prior one finishes, so FCFS simply runs them in that order with no idle time: P1 runs 0–15, P2 (waited since $t=2$) runs 15–22, P3 (waited since $t=4$) runs 22–40, P4 (waited since $t=6$) runs 40–42. $$TT_{P1}=15,\ TT_{P2}=22-2=20,\ TT_{P3}=40-4=36,\ TT_{P4}=42-6=36$$ $$\boxed{\overline{TT}_{FCFS} = \dfrac{15+20+36+36}{4} = \dfrac{107}{4} = 26.75\ \text{s}}$$ FCFS is markedly worse than the optimum because a long process (P1, 15 s; P3, 18 s) can hold the CPU while short processes (P4, 2 s) queue up behind it — the classic "convoy effect."
3. (iii) Execution-time-tiered Round Robin. Each process's OWN slice is fixed for its whole lifetime from its total execution time: P1 (15 s, $\ge10$) $\Rightarrow$ 4 s; P2 (7 s, in $[5,10)$) $\Rightarrow$ 3 s; P3 (18 s, $\ge10$) $\Rightarrow$ 4 s; P4 (2 s, $<5$) $\Rightarrow$ 2 s. Using a single FIFO ready queue, with a process that has just used its slice re-queued AFTER any process arriving at that exact instant (the standard convention for simultaneous arrival/preemption — flagged as an assumption below):
   $t{=}0$: only P1 ready $\to$ runs 0–4 (uses its 4 s slice; rem 11). Queue at $t{=}4$: P2 (arrived $t{=}2$), P3 (arrives exactly $t{=}4$, enqueued first), then P1 re-queued: [P2, P3, P1].
   $t{=}4$: P2 runs 4–7 (3 s slice; rem 4). P4 arrives at $t{=}6$ mid-slice, queued behind the current waiters: [P3, P1, P4, P2].
   $t{=}7$: P3 runs 7–11 (4 s slice; rem 14) $\to$ [P1, P4, P2, P3]. $t{=}11$: P1 runs 11–15 (4 s; rem 7) $\to$ [P4, P2, P3, P1]. $t{=}15$: P4 runs its full remaining 2 s in one slice, 15–17, and FINISHES (no requeue). $t{=}17$: P2 runs 17–20 (3 s; rem 1) $\to$ [P3, P1, P2]. $t{=}20$: P3 runs 20–24 (4 s; rem 10) $\to$ [P1, P2, P3]. $t{=}24$: P1 runs 24–28 (4 s; rem 3) $\to$ [P2, P3, P1]. $t{=}28$: P2's remaining 1 s $<$ its 3 s slice, so it runs 28–29 and FINISHES. $t{=}29$: P3 runs 29–33 (4 s; rem 6) $\to$ [P1, P3]. $t{=}33$: P1's remaining 3 s $<$ its 4 s slice, runs 33–36 and FINISHES. $t{=}36$: only P3 remains (rem 6); it runs 36–40 (4 s; rem 2), then, as sole ready process, immediately continues 40–42 and FINISHES. $$TT_{P4}=17-6=11,\ TT_{P2}=29-2=27,\ TT_{P1}=36-0=36,\ TT_{P3}=42-4=38$$ $$\boxed{\overline{TT}_{RR} = \dfrac{11+27+36+38}{4} = \dfrac{112}{4} = 28\ \text{s}}$$ The total elapsed time (42 s) exactly equals the sum of the four bursts, confirming the CPU never sat idle — a useful cross-check on the trace.

(b) On a single CPU, scheduling only has to decide a single total order: which one ready process runs next on the one available processor. On a multiprocessor system, several additional problems appear simultaneously. First, the scheduler must decide not just when but on which CPU a process runs (load balancing/placement), which is a genuinely harder combinatorial problem than pure ordering. Second, processor (cache) affinity matters: a process that has been running on one CPU has its working set warm in that CPU's cache; migrating it to a different CPU forces those cache lines to be re-fetched, which is a real performance cost that a uniprocessor scheduler never has to weigh — so multiprocessor schedulers bias toward re-scheduling a process on the CPU it last used (soft affinity) even when a perfectly load-balanced assignment would put it elsewhere. Third, for related or cooperating threads (e.g. threads of one parallel program that synchronize frequently), the scheduler may need gang scheduling — dispatching all of them across different CPUs at the same instant — otherwise one thread can spend its slice spinning on a lock held by a partner thread that has been descheduled elsewhere. Fourth, maintaining one shared ready queue across many CPUs creates lock contention on the queue itself as the CPU count grows, which is why real systems use per-CPU run queues with periodic load-balancing passes instead, adding yet another layer of policy (when and how much work to migrate between queues) that a single-CPU design never needs. In short, uniprocessor scheduling is a pure time-ordering problem; multiprocessor scheduling is a joint time-and-space (placement) problem with affinity, synchronization and queue-contention concerns layered on top.