Given. Ready-queue priority = a·t; running priority = Q + b·t'; larger priority numbers run first; ties broken by earliest ready-queue entry time.
Find. (a) values of Q, a, b that reproduce FCFS. (b) SRTF described, with its benefits and shortcomings.
Approach. FCFS never lets waiting time or running time change who is selected — only arrival order matters — so the two rate parameters must be neutralized, leaving the explicit tie-break rule to do all the work.
Freeze both priority formulas. Set $a=0$ and $b=0$. Then every process's ready-queue priority is $0\cdot t = 0$ for as long as it waits, and the running process's priority is $Q + 0\cdot t' = Q$ for as long as it runs — neither value ever changes with elapsed time.
Confirm no process can ever jump the queue or get preempted. With every ready process permanently tied at priority $0$ (independent of how long each has waited), the "highest priority" rule can never distinguish between two ready processes on priority alone — it falls straight through to the explicit tie-break, earliest ready-queue entry time, which is exactly the FCFS ordering rule. The running process must also never be displaced by a newcomer, so its priority must not fall below the ready processes' value of $0$: $Q\ge 0$. With $Q=0$ the running process ties with every ready process, and the tie goes to the process that entered the ready queue first — the running process, which was itself chosen as the earliest entrant — so it is never preempted until it blocks or completes; with $Q>0$ it simply outranks them. A negative $Q$ would break FCFS: every ready process (priority $0$) would outrank the running process ($Q<0$) and preempt it at once.
Verify against an independent FCFS reference simulator. A discrete-event simulator driven purely by these two formulas ($a=b=Q=0$) was compared against a plain arrival-order (FCFS) reference scheduler over five processes with staggered arrivals and different burst lengths, for $(Q,b)=(0,0)$, $(5,0)$ and $(2,1)$; each produced the FCFS completion order, while $Q=-1$ did not.
ready-queue priority never ages → ties always broken by arrival order
b
0 (any $b\ge0$)
running priority never decays → running process is never overtaken while executing
Q
0 (any $Q\ge0$)
running priority never drops below a waiting process's 0 → no preemption; $Q<0$ would cause immediate preemption
(b) Shortest-Remaining-Time-First (SRTF). SRTF is the preemptive version of Shortest-Job-First: the scheduler always runs whichever ready process has the smallest remaining CPU burst, and whenever a new process arrives (or a burst estimate changes), if its remaining time is shorter than the currently running process's remaining time, the running process is preempted immediately in favour of the newcomer.
Benefits. SRTF is provably optimal for minimizing average waiting time among all scheduling policies for a given set of processes and burst lengths (a proof by exchange argument: swapping any pair of out-of-order jobs can only increase or leave unchanged the total waiting time). It is highly responsive to short jobs, giving good average turnaround in workloads dominated by many short tasks interspersed with a few long ones.
Shortcomings. It requires knowing (or accurately estimating) each process's remaining CPU burst in advance, which is generally impossible for interactive/general-purpose workloads — in practice it must be approximated (e.g. exponential averaging of past bursts). It can starve long processes indefinitely: if a steady stream of short jobs keeps arriving, a long-burst process may never accumulate enough of a lead to run. It also incurs a higher context-switch overhead than non-preemptive SJF, since a burst can be interrupted mid-flight every time a shorter newcomer arrives.
