Question 1 of 7: Generalized (Quadratic) Priority-Scheduling Formula
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-COMP A-5 Operating Systems — National Examinations, May 2015. 3 hours, closed book (approved calculators only), 100 marks. 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.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.
Question 1: Generalized (Quadratic) Priority-Scheduling Formula (20 marks)
Given. Ready-queue priority $= P + a t^2$, where $t$ is the elapsed time since the process's most recent entry into the ready queue (reset on every arrival or preemption). Running priority $= Q + b t'^2$, where $t'$ is the elapsed time since the process was last dispatched. The highest-priority process (over both the running process and every ready process) always runs; ties among ready processes favour the earliest ready-queue entry.
Find. Constants $P,Q,a,b$ that make this generic rule behave as (i) non-preemptive FCFS and (ii) preemptive LCFS.
Approach. Because $t\ge 0$ always, $t^2$ is (like $t$ itself) a non-negative, strictly increasing function of elapsed time — so only the sign of $a$ and $b$ matters, exactly as in the linear ($t$, not $t^2$) version of this formula. FCFS needs (1) the running process never preempted and (2) ties among ready processes resolved purely by arrival order; LCFS needs (1) every arrival to preempt unconditionally and (2) the most-recently-preempted waiter dispatched next.
(i) FCFS — kill the "aging" term so ties decide everything. If $a=0$, every ready process's priority is the constant $P$ regardless of how long it has waited — so the rule "run the highest-priority process" can never distinguish between ready processes on priority alone, and the problem's own tie-break ("favour the process that entered the ready queue first") becomes the sole deciding factor. That tie-break is exactly FCFS order among waiting processes.
$$\boxed{a = 0}$$
(i) FCFS — make the running process unpreemptable. FCFS never preempts, so the running process's priority must exceed every ready process's priority at all times, for any elapsed running time $t'\ge 0$. Setting $b=0$ makes the running priority the constant $Q$ regardless of $t'$; the single remaining requirement, $Q>P$ (constant beats constant), then holds unconditionally and for all time — no ready arrival can ever exceed it, however long the running process has already run.
$$\boxed{b=0,\ Q > P \quad(\text{e.g. } P=0,\ Q=1)}$$
With $a=b=0$ and $Q>P$: the first arrival runs to completion (nothing can preempt it), and every subsequent dispatch decision among ready processes reduces to the arrival-order tie-break — i.e., true FCFS.
(ii) LCFS — make every arrival preempt unconditionally. A process's ready-queue priority the instant it arrives (before it has waited at all) is $P + a(0)^2 = P$. For this arriving process to preempt the current occupant regardless of how long that occupant has been running, $P$ must exceed the running priority $Q+bt'^2$ for every possible $t'\ge 0$. As in the FCFS derivation, the simplest sufficient choice makes the running priority time-invariant:
$$\boxed{b=0,\ P>Q\quad(\text{e.g. } P=1,\ Q=0)}$$
so the single requirement collapses to the constant inequality $P>Q$, satisfied at every instant.
(ii) LCFS — dispatch the most-recently-preempted waiter next. A process sitting in the ready queue re-entered it (by arrival or preemption) at some specific instant; its elapsed wait $t$ is measured from that entry. "Preempted most recently" means "smallest current $t$ among the waiters" (it has been waiting the shortest time). For the priority rule to pick that process, ready priority must be a decreasing function of $t$, i.e. the smallest $t$ must map to the largest priority:
$$\boxed{a < 0\quad(\text{e.g. } a=-1)}$$
Because $t\ge 0$, $t^2$ is non-negative and increasing in $t$ exactly like $t$ itself, so $a<0$ still forces $P+at^2$ to fall as $t$ grows — the quadratic exponent changes nothing about which sign is needed, only the rate at which priority falls.
Verification by simulation. With $P=1,\,Q=0,\,a=-1,\,b=0$: process A arrives at $t=0$ (burst 10 s) and runs immediately (empty system). Process B arrives at $t=2$ s (burst 10 s); B's instantaneous ready priority is $1$, exceeding A's running priority $Q=0$, so B preempts A (A returns to the ready queue with 8 s remaining, its own elapsed-time clock reset to 0 at $t=2$). Process C arrives at $t=5$ s (burst 10 s) and by the same logic preempts B (B returns to the queue with 7 s remaining, clock reset at $t=5$). C then runs uninterrupted to completion at $t=15$ s (no further arrivals). At $t=15$ the ready queue holds A (elapsed $15-2=13$ s since its re-entry) and B (elapsed $15-5=10$ s since its re-entry); ready priority $=1-t^2$, so B ($1-10^2=-99$) beats A ($1-13^2=-168$) — B, the more recently preempted, is dispatched next, exactly matching true LCFS. B finishes its remaining 7 s at $t=22$; A then finishes its remaining 8 s at $t=30$. The resulting completion order (C, B, A) is confirmed programmatically (discrete-event simulation, arbitrary arrival stream).
