25-Comp-A5 Operating Systems · December 2017

Question 1 of 7: CPU Scheduling and Starvation

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

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

Find. (i) the lowest mean turnaround time any non-preemptive strategy could achieve; (ii) mean turnaround under FCFS.

Approach. (i) is a "best possible schedule" question, not "what does greedy SJF give" — with only 5 jobs every release-respecting non-preemptive order can be searched exhaustively for the true minimum. (ii) simply dispatches jobs in arrival order, idling the CPU whenever the queue is empty.

1. (i) Greedy non-preemptive SJF is a useful first check, but is not guaranteed optimal when arrivals are staggered. Dispatching the shortest ready job at each decision point gives the order Proc1(2–16), Proc4(16–18), Proc5(18–19), Proc2(19–26), Proc3(26–47), for turnarounds 14, 10, 9, 22, 41 and a mean of $\dfrac{14+10+9+22+41}{5}=\dfrac{96}{5}=19.2\ \text{s}$. SJF only provably minimizes mean turnaround when every job is ready at $t=0$; here Proc1 blocks the CPU for 14 s before the much shorter Proc4/Proc5 have even arrived, so greedy SJF cannot be trusted as optimal.
2. Search all 120 release-respecting orders for the true minimum. Exhaustively simulating every valid non-preemptive dispatch order (each job starts no earlier than its arrival, idling allowed) finds that delaying Proc1 is worthwhile: the CPU idles from $t=0$ to $t=4$ so that Proc2 and the still-unarrived Proc4/Proc5 can be cleared before Proc1's long 14 s burst ever starts. $$\text{Optimal order: Proc2}(4\text{-}11)\to\text{Proc5}(11\text{-}12)\to\text{Proc4}(12\text{-}14)\to\text{Proc1}(14\text{-}28)\to\text{Proc3}(28\text{-}49)$$ Turnarounds: $TT_2=11-4=7,\ TT_5=12-10=2,\ TT_4=14-8=6,\ TT_1=28-2=26,\ TT_3=49-6=43$. $$\boxed{\overline{TT}_{\min}=\dfrac{7+2+6+26+43}{5}=\dfrac{84}{5}=16.8\ \text{s}}$$ This is strictly better than the 19.2 s greedy-SJF result, confirmed by exhaustive search over every processing order: no non-preemptive strategy can do better than 16.8 s mean turnaround for this arrival pattern.

(ii) FCFS dispatch trace. Jobs run strictly in arrival order 1,2,3,4,5; the CPU is never idle once Proc1 arrives at $t=2$.

$$\boxed{\overline{TT}_{\text{FCFS}}=\dfrac{14+19+38+38+37}{5}=\dfrac{146}{5}=29.2\ \text{s}}$$ FCFS is nearly double the achievable optimum (16.8 s) here because it lets the long Proc3 (21 s) and the earlier-arriving Proc1 (14 s) run before the much shorter Proc4/Proc5, exactly the "convoy effect" FCFS is known for.

(b) A multiple-queue technique approximating Optimal (SJF/SRTF) scheduling. The true Optimal (SJF for non-preemptive, SRTF for preemptive) strategy needs to know each job's remaining CPU-burst length in advance, which is not knowable at admission time. The Multilevel Feedback Queue (MLFQ) approximates it without oracle knowledge by using a job's observed behaviour as a proxy for its length. The scheduler maintains several ready queues ranked by priority, each with progressively longer time quanta (e.g. $Q_0$: 8 ms, $Q_1$: 16 ms, $Q_2$: 32 ms, $Q_3$: FCFS). A new job enters the highest-priority queue $Q_0$. If it finishes within that queue's quantum, it is a short (CPU-bound-light or I/O-bound) job and departs having received the fastest possible service — exactly what SRTF would have given it. If it uses the full quantum without finishing, the scheduler infers it is a longer job and demotes it to the next queue down, which has a longer quantum but lower priority, so it interferes less with the short jobs still arriving at $Q_0$. This repeats, so a job's queue level converges to reflect its actual burst length: short jobs are skimmed off quickly at high priority (mimicking SJF/SRTF favouring short jobs), while long, CPU-bound jobs sink to the lowest, FCFS-like queue where they no longer block newer short arrivals. Because higher queues are always scanned before lower ones, a steady stream of short jobs can, in principle, starve the lowest queue — most MLFQ implementations add periodic priority boosts (moving all jobs back to $Q_0$ after a fixed interval) to bound this.

(c) Starvation in a real-time system. Real-time schedulers (e.g. Rate-Monotonic or fixed static-priority scheduling) assign the highest priority to the task with the tightest deadline/period and always run the highest-priority ready task, preempting lower-priority ones. Starvation occurs when a task's priority is low enough, and the higher-priority workload dense enough, that it is never actually given the CPU, even though it is always ready. Two concrete mechanisms: (1) Priority-based CPU starvation — in a Rate-Monotonic system with several high-frequency periodic tasks (e.g. a 1 ms sensor-sampling task and a 5 ms control-loop task) that together consume nearly 100% of CPU capacity, a low-frequency background task (e.g. a 500 ms logging task) may never find a gap, because every time it is ready to run, one of the shorter-period tasks has already become ready again and preempts it — the low-priority task is perpetually deferred, i.e. starved, even though it is schedulable in isolation. (2) Resource-based starvation (priority inversion feeding starvation) — if a low-priority task holds a mutex/semaphore that a high-priority task needs, and a stream of medium-priority tasks keeps preempting the low-priority holder before it can finish and release the lock, the high-priority task is indefinitely starved of the resource despite having top CPU priority (the classic unbounded priority-inversion scenario, mitigated in practice by priority inheritance or priority-ceiling protocols).