25-Comp-A5 Operating Systems · December 2015

Question 1 of 7: CPU Scheduling

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2015. 3 hours, closed book (one approved pocket calculator only). Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.

Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — CPU scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), real-time systems (ch. 19); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.

Question 1: CPU Scheduling (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, single CPU burst each, no I/O.

Given data
Process	Arrival time (s)	Execution time (s)
Proc1	0	16
Proc2	2	6
Proc3	3	12
Proc4	6	3

Find. (a) The lowest mean turnaround time any non-preemptive strategy could achieve; (b) mean turnaround under RR (q=2 s); (c) mean turnaround under the execution-time-tiered RR variant.

Approach. (a) is a "best possible" question, not "what does plain SJF give" — with only 4 jobs, exhaustively try every valid non-preemptive processing order (respecting each job's arrival time, idling allowed) and keep the one minimizing total turnaround. (b)/(c) simulate the FIFO ready queue exactly, admitting new arrivals before re-queuing a preempted process when both happen at the same instant.

(a) Greedy non-preemptive SJF is NOT optimal here — check it, then search further. Dispatching the shortest ready job at each decision point gives: Proc1 (0–16, the only arrival at t=0), then among {Proc2,Proc3,Proc4} all already waiting, shortest-first → Proc4 (16–19), Proc2 (19–25), Proc3 (25–37). $$\overline{TT}_{\text{greedy SJF}}=\dfrac{16+(19-2)+(25-6)... }{4}\ \Rightarrow\ \dfrac{16+13+23+34}{4}=\dfrac{86}{4}=21.5\ \text{s}$$ This is the textbook "SJF minimizes mean turnaround" result — but that theorem only holds when every job is ready at t=0. Here Proc1's 16 s burst blocks the CPU before the shorter Proc2/Proc4 have even arrived, so greedy SJF cannot help it.
Search all release-respecting orders for the true minimum. With only 4 jobs, every valid non-preemptive order (running each job only once it has arrived, idling if necessary) can be enumerated. The result that minimizes total turnaround deliberately makes the CPU idle from t=0 to t=2 rather than starting Proc1 immediately, so that the much shorter Proc2 and Proc4 can be finished (and off the system) before Proc1's long burst ever starts: $$\text{Order: Proc2}(2\text{-}8)\to\text{Proc4}(8\text{-}11)\to\text{Proc3}(11\text{-}23)\to\text{Proc1}(23\text{-}39)$$ Turnaround: $TT_2=8-2=6,\ TT_4=11-6=5,\ TT_3=23-3=20,\ TT_1=39-0=39$. $$\boxed{\overline{TT}_{\min}=\dfrac{6+5+20+39}{4}=\dfrac{70}{4}=17.5\ \text{s}}$$ This is strictly better than the 21.5 s greedy result and is the true minimum (verified by exhaustive search over all 24 processing orders): no non-preemptive strategy, however clever, can beat 17.5 s for this arrival pattern.

Fig. Q1(a) — the clairvoyant-optimal schedule idles 0–2 s, then clears both short jobs before ever starting Proc1.

(b) Round Robin, q=2 s. Convention: when a process's quantum expires at the same instant a new process arrives, the new arrival joins the ready queue before the preempted process is re-appended to the tail.

RR (q=2 s) dispatch trace
Interval	Runs	Remaining after	Note
0–2	Proc1	14	Proc2 arrives @2, queue: Proc2,Proc1
2–4	Proc2	4	Proc3 arrives @3, queue: Proc1,Proc3,Proc2
4–6	Proc1	12	Proc4 arrives @6, queue: Proc3,Proc2,Proc4,Proc1
6–8	Proc3	10	queue: Proc2,Proc4,Proc1,Proc3
8–10	Proc2	2	queue: Proc4,Proc1,Proc3,Proc2
10–12	Proc4	1	queue: Proc1,Proc3,Proc2,Proc4
12–14	Proc1	10	queue: Proc3,Proc2,Proc4,Proc1
14–16	Proc3	8	queue: Proc2,Proc4,Proc1,Proc3
16–18	Proc2	0 — finishes @18	queue: Proc4,Proc1,Proc3
18–19	Proc4 (only 1 s left)	0 — finishes @19	queue: Proc1,Proc3
19–21 / 23–25 / 27–29 / 31–33	Proc1 (2 s each)	8→6→4→2	alternates with Proc3
21–23 / 25–27 / 29–31	Proc3 (2 s each)	6→4→2	alternates with Proc1
33–35	Proc3 (2 s)	0 — finishes @35	queue: Proc1
35–37	Proc1 (2 s)	0 — finishes @37	done

Fig. Q1(b) — RR (q=2 s). Completion times: Proc2=18, Proc4=19, Proc3=35, Proc1=37.

Read off completions and compute turnaround. $C_1=37,\ C_2=18,\ C_3=35,\ C_4=19$. $TT_1=37,\ TT_2=16,\ TT_3=32,\ TT_4=13$. $$\boxed{\overline{TT}_{RR,q=2}=\dfrac{37+16+32+13}{4}=\dfrac{98}{4}=24.5\ \text{s}}$$

(c) Execution-time-tiered RR. Each process keeps its OWN fixed quantum for every one of its turns, based on its total execution time: Proc1 (16 s, ≥13) → 5 s; Proc2 (6 s, <7) → 2 s; Proc3 (12 s, in [7,13)) → 3 s; Proc4 (3 s, <7) → 2 s.

Variant-RR dispatch trace (quantum shown per run)
Interval	Runs (q)	Remaining after
0–5	Proc1 (5)	11
5–7	Proc2 (2)	4
7–10	Proc3 (3)	9
10–15	Proc1 (5)	6
15–17	Proc4 (2)	1
17–19	Proc2 (2)	2
19–22	Proc3 (3)	6
22–27	Proc1 (5)	1
27–28	Proc4 (only 1 s left)	0 — finishes @28
28–30	Proc2 (2)	0 — finishes @30
30–33	Proc3 (3)	3
33–34	Proc1 (only 1 s left)	0 — finishes @34
34–37	Proc3 (3)	0 — finishes @37

Fig. Q1(c) — giving the LONGEST job the LONGEST quantum backfires: Proc1 now monopolizes the CPU for 5 s at a stretch, so everyone else waits longer per round.

Read off completions and compute turnaround. $C_1=34,\ C_2=30,\ C_3=37,\ C_4=28$. $TT_1=34,\ TT_2=28,\ TT_3=34,\ TT_4=22$. $$\boxed{\overline{TT}_{\text{variant}}=\dfrac{34+28+34+22}{4}=\dfrac{118}{4}=29.5\ \text{s}}$$ This is the worst of the three policies — the variant's design gives the process that most needs to be broken into small pieces (the 16 s Proc1) the biggest slice, so it behaves closer to FCFS for the long job while everyone else still queues behind it each round.

Final Results — Q1
Policy	Completion order	Mean turnaround
(a) Clairvoyant-optimal non-preemptive	Proc2, Proc4, Proc3, Proc1	17.5 s
(b) Round Robin, q = 2 s	Proc2, Proc4, Proc3, Proc1	24.5 s
(c) Execution-time-tiered RR	Proc4, Proc2, Proc1, Proc3	29.5 s

Topic: Non-preemptive scheduling optimality limits, and Round-Robin quantum design.

Key relations: Turnaround $TT=C-A$; mean turnaround minimization $\equiv$ mean completion-time minimization when arrival times are fixed (they contribute a constant offset). Classic SJF-is-optimal theorem: minimizes mean turnaround only among jobs simultaneously available; with staggered arrivals the true optimum can require deliberately idling the CPU past an already-ready long job.

Why this works: Idling to let Proc2 (arriving at 2) and Proc4 (arriving at 6) finish before starting the already-ready-but-very-long Proc1 removes their long turnaround exposure entirely, at the cost of adding only 2 s of idle time to Proc1's own eventual start — a clear net win since two short jobs' turnaround shrinks far more than Proc1's grows. The tiered-RR variant fails because it inverts the usual quantum-design intuition: a larger quantum should go to processes needing FEWER context switches to finish, not to the process whose long burst most needs frequent CPU-sharing with everyone else.

Common pitfall: Assuming non-preemptive SJF (or any greedy rule applied only to already-arrived jobs) is automatically the best possible non-preemptive schedule — it is optimal only for the simultaneous-arrival case. For RR, forgetting the simultaneous arrival-vs-preemption tie-break convention changes every downstream completion time.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 5 (CPU Scheduling), §5.3.2 (SJF and its optimality caveat) and §5.3.4 (Round-Robin scheduling).

← Paper overview Next: Question 2 →