Question 1 of 7: Dynamic-Priority Scheduling and SJF
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-COMP A-5 Operating Systems — National Examinations, May 2017. 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); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.
Question 1: Dynamic-Priority Scheduling and SJF (20 marks)
(a) Given. Waiting-process priority $=a\cdot t$; running-process priority $=Q+b\cdot t'$; ties go to the earliest ready-queue entry time; a preempted process's ready-queue entry time resets to the instant of preemption. Find. Values of $Q$, $a$, $b$ that force the scheduler to behave as pure FCFS (dispatch in arrival order, never preempt). Approach. FCFS requires two independent guarantees for ANY workload, however long bursts run or however long processes wait: (1) a running process is never preempted, and (2) whenever the CPU is free, the next process chosen is whichever has been waiting longest. Pin down the parameter values that make both guarantees hold unconditionally.
Force waiting priorities to stay constant and equal, so the tie-break rule alone decides selection order. If $a\neq0$, a process's waiting priority $a\cdot t$ grows (or shrinks) without bound the longer it waits, so two processes that have waited different lengths of time would have different priorities and the highest-priority process (not necessarily the longest-waiting one) would be chosen — that is priority scheduling, not FCFS. Setting
$$\boxed{a=0}$$
makes every waiting process's priority identically $0$ regardless of $t$, so every ready-queue comparison is an exact tie. The stated tie-break rule then applies literally — "favour of the process that entered the ready to run queue first" — and since entry order is arrival order (or preemption-instant order, which cannot occur once part (2) below is satisfied), the ready queue is always dispatched in pure FCFS order.
Prevent the running process's priority from ever falling below the (constant) waiting priority of $0$, so no preemption can ever be triggered. The running process's priority is $Q+b\cdot t'$. Since a burst may run for an unbounded length of time, this quantity must stay $\ge 0$ for every $t'\ge0$, which holds for any
$$\boxed{Q\ge0,\ b\ge0}$$
(e.g. the simplest choice $Q=0,\ b=0$, which keeps the running process's priority pinned at exactly $0$, tied with every waiter — and a tie is resolved in favour of whichever process entered the ready queue earlier, which is always the ALREADY-running process, so it is never displaced). Any $b<0$ would eventually drive the running priority negative while a long burst executes, letting a waiting process (priority $0$) overtake it and preempt — violating FCFS's defining non-preemptive property.
Final Results — Q1(a)
Parameter
Value producing FCFS
$a$
0 (necessary — makes every waiting priority identically 0, so the arrival-order tie-break alone governs selection)
$Q$
any constant $\ge 0$ (e.g. 0)
$b$
any value $\ge 0$ (e.g. 0) — keeps the running process's priority from ever dropping below the waiters' constant 0
(b)Shortest Job First (SJF) dispatches, whenever the CPU is free, whichever ready process has the shortest (remaining, in the preemptive variant) CPU burst. Benefits: among all scheduling policies applied to a fixed set of processes that are all simultaneously available, SJF is provably optimal for minimizing mean waiting time (and mean turnaround time) — running short jobs first clears the maximum number of processes out of the system as quickly as possible, so the total accumulated waiting time across all processes is minimized. It is also simple to reason about and, being non-preemptive in its basic form, incurs no context-switch overhead beyond the process's own scheduling. Shortcomings: (1) SJF requires knowing (or accurately predicting) each process's next CPU burst length in advance, which is generally not knowable exactly — real systems must estimate it (e.g. an exponential average of past bursts), and a bad estimate defeats the optimality guarantee; (2) it can cause starvation of long jobs: if a steady stream of short jobs keeps arriving, a long job can be repeatedly bypassed and wait indefinitely, since the algorithm has no ageing mechanism to raise its priority over time; (3) the optimality result itself only holds when all competing jobs are simultaneously ready — with staggered arrivals, greedily running the shortest currently-ready job is not always globally optimal, since a not-yet-arrived very short job may be worth idling the CPU for.
