25-Comp-A5 Operating Systems · May 2014

Question 1 of 7: CPU Scheduling and Real-Time Systems

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

Question 1: CPU Scheduling and Real-Time Systems (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 processes, each a single CPU burst with no I/O, arriving over time on one CPU (no other CPU is idle-able for free — a job cannot start before it arrives).

Find. (i) The smallest achievable mean turnaround time using any non-preemptive policy. (ii) The smallest achievable mean turnaround time using any preemptive policy.

Approach. For (i), since Proc1 is the only arrival at t=0 it must run first regardless of policy; from the point every remaining process has arrived, the schedule that minimizes mean completion time among already-arrived jobs is Shortest-Job-Next (non-preemptive), which is optimal once no more arrivals can change the ranking. For (ii), the theorem-optimal preemptive policy is Shortest-Remaining-Time-First (SRTF): always run the ready job with the least remaining execution time, preempting the current job the instant a shorter one becomes ready.

1. (i) Optimal non-preemptive. At t=0 only Proc1 has arrived, so it must run 0–14 (no shorter alternative exists yet, and idling would only delay it for nothing). By t=7 all five processes have arrived, and since Proc1 cannot be preempted, the CPU is committed to it until t=14. From t=14 onward every remaining process (Proc2, Proc3, Proc4, Proc5) is already ready, so no further arrivals can change the ranking — running the shortest ready job first at every step (SJN) is optimal for this static tail. That gives, in order: Proc5 (burst 1) 14–15, Proc4 (burst 2) 15–17, Proc2 (burst 7) 17–24, Proc3 (burst 21) 24–45. $$TT_{1}=14-0=14,\ TT_{5}=15-7=8,\ TT_{4}=17-6=11,\ TT_{2}=24-2=22,\ TT_{3}=45-4=41$$ $$\boxed{\overline{TT}_{non\text{-}pre} = \dfrac{14+8+11+22+41}{5} = \dfrac{96}{5} = 19.2\ \text{s}}$$ An exhaustive search over every valid dispatch order (CPU may only idle before any process has arrived) confirms 19.2 s is the true minimum.
2. (ii) Optimal preemptive (SRTF). Proc1 runs 0–2 (only job present). At t=2 Proc2 arrives with burst 7 < Proc1's remaining 12, so Proc2 preempts. Proc2 runs 2–6 (Proc3's arrival at t=4, burst 21, is far longer than Proc2's remaining 5, so no switch). At t=6 Proc4 arrives with burst 2 < Proc2's remaining 3, so Proc4 preempts and runs 6–7. At t=7 Proc5 arrives with burst 1, exactly tying Proc4's remaining 1 second — a tie does not trigger a preemption (only a strictly shorter job does), so Proc4 finishes its last second, completing at t=8. Proc5 (remaining 1, shortest ready) runs 8–9. Proc2 (remaining 3, next shortest) runs 9–12. Proc1 (remaining 12) runs 12–24. Proc3 (burst 21, never preempted since nothing else remains) runs 24–45. $$TT_{4}=8-6=2,\ TT_{5}=9-7=2,\ TT_{2}=12-2=10,\ TT_{1}=24-0=24,\ TT_{3}=45-4=41$$ $$\boxed{\overline{TT}_{pre} = \dfrac{2+2+10+24+41}{5} = \dfrac{79}{5} = 15.8\ \text{s}}$$ SRTF is the proven optimal preemptive policy for minimizing mean turnaround/completion time (Silberschatz ch. 5); note it beats the non-preemptive optimum (15.8 vs 19.2 s) precisely because it can react to Proc4/Proc5's short bursts the instant they arrive, instead of waiting for Proc1 to finish.

(b) The strategy that is provably optimal for minimizing mean turnaround/waiting time — Shortest-Job-Next (non-preemptive) or SRTF (preemptive) — is difficult to implement in practice because it requires knowing each process's future CPU burst length before it is dispatched, and a general-purpose operating system cannot know in advance how long an arbitrary program will run: burst length depends on the input data, control-flow branches taken, and even I/O wait interleaving, none of which is known until the process actually executes. Real systems can only estimate the next burst (e.g. an exponential average of a process's own recent bursts, as used to approximate SJN/SRTF), and an estimate can be wrong, which both erodes the theoretical optimality and can itself starve a process whose estimate stays large. This is the same fundamental limitation as trying to solve the halting problem's cousin — predicting a program's future behaviour from the outside — and it is why practical schedulers instead use proxies (multilevel feedback queues, priority aging, time-slicing) that approximate the benefit of running short jobs first without needing perfect foreknowledge.

(c) A real-time system is one in which correctness depends not only on the logical result of a computation but also on the time by which that result is produced — each task carries a deadline, and completing the right answer late is treated as a failure of the system, not merely a performance shortfall. A hard real-time system has deadlines that must never be missed, because a missed deadline causes a catastrophic or unacceptable outcome: an automotive airbag-deployment controller or an aircraft flight-control computer are examples, where the scheduler must guarantee, by admission control and worst-case-execution-time analysis, that every task will meet its deadline before the task is ever admitted to run. A time-sharing system (an ordinary desktop or multi-user server), by contrast, aims only for good average responsiveness — it uses techniques such as round-robin time-slicing to give every interactive user the illusion of a dedicated machine, but no individual request carries a hard deadline, and an occasional slow response (a missed "soft" expectation) degrades user experience without being catastrophic. The key distinguishing test is consequence: in a hard real-time system a late result is as useless (or dangerous) as a wrong one, while in a time-sharing system a late result is merely less desirable.