Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
17-COMP A-5 Operating Systems — National Examinations, May 2018. 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.) — process synchronization/monitors (ch. 6–7), CPU scheduling (ch. 5), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), protection (ch. 14); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on synchronization, scheduling, memory and file systems.
Given. Ready-queue priority $P_{\text{ready}}(t)=P+a\,t^{2}$; running priority $P_{\text{run}}(t')=Q-b\,t'$. Target behaviour (preemptive LCFS): (1) any newly arriving/re-entering process immediately preempts whoever is running, regardless of how long that process has run or how many others are waiting; (2) when the CPU frees, the ready process that has been waiting the shortest time (i.e. was preempted most recently) runs next.
Find. Conditions on $P,Q,a,b$ that produce this behaviour, with a concrete instantiation.
Approach. Translate each required behaviour into an inequality on the priority formulas, then verify a chosen instantiation against an independently coded LCFS-preemptive reference scheduler.
Always-preempt-on-arrival requires $P>Q$. A brand-new (or freshly re-preempted) arrival has ready-priority $P_{\text{ready}}(0)=P$. For it to beat any currently running process, $P$ must exceed $P_{\text{run}}(t')=Q-b\,t'$ for every possible $t'\ge0$. Since $Q-b\,t'\le Q$ whenever $b\ge0$, the condition $P>Q$ (together with $b\ge0$) guarantees the newcomer always wins, no matter how long the incumbent has already run.
$$\boxed{P>Q,\qquad b\ge0}$$
"Resume the most-recently-preempted first" requires $a<0$. Among several ready (waiting) processes, the one to resume next must be whichever has waited the least time so far (that is what "most recently preempted" means under this priority-queue model, since every entry into the ready queue — including a re-entry after preemption — resets $t$ to 0). $P_{\text{ready}}(t)=P+a\,t^{2}$ is maximized at $t=0$ and strictly decreasing in $t$ for $t\ge0$ exactly when $a<0$; this makes the freshest arrival always carry the highest ready-queue priority.
$$\boxed{a<0}$$
Concrete instantiation and independent check. Take $P=1,\ Q=0,\ a=-1,\ b=0$ (any values respecting the two boxed conditions work identically). A discrete-event simulator driven purely by these priority formulas was run against four processes with staggered arrivals (arrivals 0, 2, 3, 7; bursts 10, 4, 2, 3) and compared to an independently coded, direct implementation of preemptive LCFS (new arrival always preempts; on completion, resume the most-recently-preempted waiter via a simple stack). Both produce the identical completion order $[2,3,1,0]$ (process indices), confirming the parameter choice reproduces true LCFS-preemptive behaviour.
Final Results – Question 2(a)
Quantity
Value
Condition for always-preempt-on-arrival
$P>Q$ and $b\ge0$
Condition for "resume most-recently-preempted first"
$a<0$
Worked instantiation
$P=1,\ Q=0,\ a=-1,\ b=0$
(b)(i) Round Robin — benefits and shortcomings. Round Robin (RR) gives every ready process a fixed time quantum in cyclic order, preempting it back to the tail of the ready queue if it hasn't finished. Benefits: it is inherently fair (no process waits more than $(n-1)\times\text{quantum}$ for its next turn, giving a genuine bounded-waiting/response-time guarantee), it is simple to implement, and it gives good, predictable response time for interactive workloads — exactly why it underlies most timesharing and desktop schedulers. Shortcomings: average turnaround time is often worse than SJF/SRTF for CPU-bound batch jobs, because RR interleaves everything instead of favouring short jobs; a large quantum makes RR degrade toward FCFS (losing interactivity), while a very small quantum makes context-switch overhead dominate useful work; and RR does not distinguish CPU-bound from I/O-bound processes, so a CPU-bound "hog" gets the same slice as a process that would have released the CPU almost immediately anyway.
(b)(ii) Impact of time-slice duration. The quantum size directly trades responsiveness against overhead. A very small quantum approaches processor sharing (every process appears to progress smoothly, good for interactivity) but the fraction of time lost to context-switch overhead grows relative to useful execution time, so effective throughput and CPU efficiency fall. A very large quantum reduces switching overhead but makes RR behave increasingly like FCFS — a process can monopolize the CPU for a long interval before yielding, hurting response time for everyone else waiting behind it. The common rule of thumb is to choose the quantum so that most interactive CPU bursts complete within one quantum (keeping context switches infrequent relative to useful work), typically in the tens-of-milliseconds range.
