25-Comp-A5 Operating Systems · May 2013

Question 5 of 7: Priority Scheduling Parameters and Optimal Page Replacement

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2013. 3 hours, closed book, 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 5: Priority Scheduling Parameters and Optimal Page Replacement (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. Two priority formulas, both a function of $t$ = time elapsed since a process's own arrival: ready-queue priority $= R + a t$, running priority $= C + b t$. Scheduling always runs the highest-priority process; a process may be preempted mid-burst and later resumed (no work is lost on preemption, no I/O).

Find. Values of $R, C, a, b$ under which this generic priority rule reduces exactly to preemptive LCFS.

Approach. LCFS has two distinct behaviours to reproduce: (1) every new arrival preempts the current CPU occupant, unconditionally; (2) among several waiting (previously preempted) processes, the one preempted most recently is the one dispatched next. Match each behaviour to one of the two coefficients.

Ordering the ready queue (choose the sign of $a$). A process still in the ready queue was preempted at the instant a later process arrived; among several such waiting processes, the one preempted most recently is exactly the one with the most recent arrival (larger arrival time), i.e. the smallest elapsed time $t$ measured from the current instant. For LCFS's "most recently preempted runs next" rule, the ready-queue priority must therefore be a decreasing function of $t$, so that the smallest $t$ gets the largest priority. $$\boxed{a < 0 \quad (\text{take } a = -1 \text{ for concreteness})}$$
Guaranteeing every arrival preempts (choose $b$ and the relation between $R,C$). The instant a process arrives, its own elapsed time is $t=0$, so its ready-queue priority (which it briefly holds before being dispatched) is $R + a(0) = R$. For this arriving process to always preempt the currently running process — no matter how long that process has already been running — we need $R$ to exceed the running process's priority $C+bt_{run}$ for every possible elapsed time $t_{run}\ge 0$ the running process may have accumulated. The simplest way to guarantee this for all $t_{run}$ is to make the running priority not grow with time at all: $$\boxed{b = 0}$$ so the running process's priority is the constant $C$, and the single requirement becomes $R > C$ (take $R=1$, $C=0$ for concreteness). If $b>0$ were allowed, a long-running process's priority would eventually exceed any fixed $R$ and a later arrival could fail to preempt it, breaking LCFS; $b<0$ would also satisfy the inequality but is not needed to obtain the required behaviour, so $b=0$ is the simplest sufficient choice.
Verification by simulation. With $R=1,\ C=0,\ a=-1,\ b=0$: process A arrives at $t=0$ (burst 10) and runs immediately. Process B arrives at $t=2$ (burst 10); its ready-priority at $t=0$ elapsed is $1$, which exceeds A's running priority $C=0$, so B preempts A (A returns to the ready queue with 8 s remaining). Process C arrives at $t=5$ (burst 10); by the same logic C preempts B (B returns to the ready queue with 7 s remaining, having run 2–5). C then runs to completion at $t=15$ (no further arrivals). At $t=15$ the ready queue holds A (elapsed $15-0=15$) and B (elapsed $15-2=13$); ready-priority $=1-t$, so B (elapsed 13, priority $-12$) beats A (elapsed 15, priority $-14$) — B is dispatched next, matching "B was preempted more recently than A." B finishes its remaining 7 s at $t=22$; A then finishes its remaining 8 s at $t=30$. This exactly reproduces true LCFS-preemptive behaviour (order of completion C, B, A).

Final Results — Q5(a)
Parameter	Required condition	Concrete example
$a$	$a < 0$ (ready priority falls with elapsed time)	$a=-1$
$b$	$b = 0$ (running priority constant, simplest sufficient choice)	$b=0$
$R, C$	$R > C$ (an arrival's momentary priority beats any running priority)	$R=1,\ C=0$

(b) The optimal page-replacement strategy (Belady's MIN algorithm) evicts, on every fault, the page in memory that will not be referenced again for the longest time into the future (or never again, if applicable) — this provably yields the fewest possible page faults for any fixed number of frames, as illustrated in Q4(a)-ii above, where OPT achieved 10 faults, tying LRU on that particular string but in general strictly beating it. Why it is hard to implement on a real system: the algorithm requires perfect knowledge of the future reference string — at the moment of a fault, the OS would need to know which of the resident pages is referenced farthest ahead, but a running program's future memory references are not known in advance (they depend on runtime branches, input data, and loop bounds that have not yet executed). It is therefore used only as a theoretical benchmark against which implementable algorithms (LRU, clock/second-chance, working-set) are measured, and can only be computed after the fact, by replaying a recorded execution trace.

Topic: Generalized priority-scheduling parameters (an "aging" formula that can express many named policies); Belady's optimal replacement as an unimplementable upper bound.

Key relations: $Priority_{ready}(t)=R+at$; $Priority_{running}(t)=C+bt$. Choosing $a>0,b>0$ with $R\approx C$ instead yields FCFS-like aging (favours long-waiting jobs); $a=0,b=0$ with $R>C$ gives a fixed priority boost to whichever job is currently running (round-robin-adjacent); the sign of $a$ alone controls whether "aging" favours the oldest or the newest waiter.

Why this works: The two-coefficient formula is a linear model of "priority drifts over time," and different scheduling philosophies are recovered simply by choosing the drift's sign and the two policies' relative offsets — a compact way of showing that FCFS, LCFS and priority-aging schemes are all points in the same parameter space rather than unrelated algorithms.

Common pitfall: Reading "$t$ = time elapsed after the process arrived" as "time elapsed since it was last preempted" — the problem is explicit that $t$ is measured from the process's original arrival at the system, which is exactly what makes the most-recently-arrived (not most-recently-scheduled) process win ties in the ready queue.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 5 §5.3 (priority scheduling, aging) and ch. 10 §10.4.4 (optimal page replacement).

← Question 4 Next: Question 6 →