CPU scheduling: FCFS, SJF, round robin and priority
CPU scheduling policies (FCFS, SJF, Round Robin, Priority): definitions, trade-offs, exact formulas, proofs (SJF optimality by exchange), Gantt-chart drawing instructions, worked numerical examples, common exam mistakes and practice questions.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
CPU schedulers decide which ready process runs on the CPU next. Good scheduling increases CPU utilisation, reduces waiting and response times for interactive users, and meets throughput or real‑time deadlines an engineer must guarantee in operating-system design and performance tuning.
Key ideas
Context switch: the overhead (time) to save one process state and load another (includes changing the PCB, registers, TLB effects). Context-switch time is treated as lost CPU time and should be minimised.
Preemptive vs non-preemptive scheduling: preemptive means the scheduler can interrupt (preempt) a running process to run another; non-preemptive means a running process runs until it blocks, yields, or finishes.
Common metrics (all defined before use): turnaround time (completion time − arrival time), waiting time (total time in the ready queue; in single-CPU-burst examples Wi = Ti − Bi), response time (time from arrival to first run), throughput (processes finished per unit time), CPU utilisation (fraction of time CPU is busy).
Policies covered:
- FCFS (First-Come, First-Served): non-preemptive; order by arrival time. Simple, but can suffer from the "convoy effect" where a long job delays many short ones.
- SJF (Shortest Job First): schedule the process with the smallest next CPU burst. Can be non-preemptive (SJF) or preemptive known as SRTF (Shortest Remaining Time First/SRPT). If all processes are available at time 0 and burst lengths are known, non‑preemptive SJF minimises average waiting time among non‑preemptive schedules (see the exchange‑proof below). For arbitrary arrivals with preemption and known remaining times, SRTF/SRPT minimises average turnaround/waiting time. Caution: repeated arrivals of short jobs can starve long jobs unless aging or limits are used. In practice, exact future CPU bursts are unknown so OSes estimate them; a common predictor is exponential averaging: τ(n+1) = α·t(n) + (1−α)·τ(n), 0 ≤ α ≤ 1, where t(n) is the last actual burst and τ(n) the previous estimate (choose α closer to 1 to weight recent history).
- Round Robin (RR): preemptive; each process gets a time slice (quantum) q; if it does not finish in q it is preempted and placed at the ready queue tail. Good for time‑sharing and fair response; choice of q trades context-switch overhead vs responsiveness.
- Priority scheduling: each process has a priority; scheduler picks highest priority first. Can be preemptive or non‑preemptive. Lower-priority processes can starve unless aging (gradually increasing priority over waiting time) is used.
Exact theorem (SJF optimality) and assumptions:
- Theorem (informal precise form): If all processes are available at time 0 and CPU burst lengths are known, ordering them by nondecreasing CPU burst (SJF non‑preemptive) gives minimum average waiting time among all non‑preemptive schedules. Assumptions: all arrival times equal (commonly 0) and bursts known and nonnegative.
- Proof technique (exchange argument): take any schedule that has an adjacent pair of jobs (i,j) where i's burst > j's burst. Swapping i and j cannot increase the waiting time sum; repeating swaps yields the SJF order and minimises total waiting time. (Full step‑by‑step given in worked theory answer below.)
What to draw for exam diagrams (Gantt chart): draw a horizontal timeline line. Mark time ticks (0, q, etc.) evenly. Above the timeline draw labeled blocks for each CPU allocation segment with process name (P1, P2...). At each block boundary label the exact time. For preemption, show multiple blocks of same process. Label average waiting/turnaround computations below the chart.
Formulas
Turnaround time (Ti) = Completion time (Ci) − Arrival time (Ai) — time units (ms or s); applies always.
Waiting time (Wi) = Turnaround time (Ti) − Total CPU time (sum of all CPU bursts) — same time units; in the single‑CPU‑burst examples here, Wi = Ti − Bi. If Ti includes I/O intervals, then Wi = Ti − (total CPU time) − (total I/O time).
Average waiting time = (1/n) · Σ Wi — average over n processes; applies to any schedule.
Average turnaround time = (1/n) · Σ Ti — applies to any schedule.
Response time (Ri) = Time of first CPU allocation − Arrival time (Ai) — for preemptive systems this may be < Wi.
CPU utilisation = (Total busy CPU time / Total elapsed time) · 100% — dimensionless percentage; subtract context-switch overhead from busy time if counted as lost.
Note: units must be consistent (ms recommended for examples). Replace n by number of processes.
Worked examples
Example 1 — FCFS numerical (non‑preemptive) Data (all times in milliseconds): Processes: P1(A=0, B=5), P2(A=1, B=3), P3(A=2, B=8), P4(A=3, B=6). Order by arrival: P1 → P2 → P3 → P4.
- Schedule timeline (Gantt): [0—5: P1] [5—8: P2] [8—16: P3] [16—22: P4].
- Completion times: C1=5 ms, C2=8 ms, C3=16 ms, C4=22 ms.
- Turnaround times: T1=C1−A1=5−0=5 ms, T2=8−1=7 ms, T3=16−2=14 ms, T4=22−3=19 ms.
- Waiting times: W1=T1−B1=5−5=0 ms, W2=7−3=4 ms, W3=14−8=6 ms, W4=19−6=13 ms.
- Average waiting = (0+4+6+13)/4 = 23/4 = 5.75 ms.
- Average turnaround = (5+7+14+19)/4 = 45/4 = 11.25 ms.
Example 2 — Round Robin (preemptive) with same data, quantum q = 4 ms Data in ms as above. Build Gantt using queue behavior (arrivals considered when they occur): Gantt: [0—4: P1] [4—7: P2] [7—11: P3] [11—15: P4] [15—16: P1] [16—20: P3] [20—22: P4]. Explanation: P1 runs 4 of 5 (remains 1). P2 runs 3 (finishes). P3 runs 4 (remains 4). P4 runs 4 (remains 2). Then P1 runs remaining 1 and finishes, subsequently P3 and P4 finish. Completion times: C1=16 ms, C2=7 ms, C3=20 ms, C4=22 ms. Turnaround: T1=16−0=16 ms, T2=7−1=6 ms, T3=20−2=18 ms, T4=22−3=19 ms. Waiting: W1=16−5=11 ms, W2=6−3=3 ms, W3=18−8=10 ms, W4=19−6=13 ms. Average waiting = (11+3+10+13)/4 = 37/4 = 9.25 ms. Average turnaround = (16+6+18+19)/4 = 59/4 = 14.75 ms.
Example 3 — SJF optimality (proof sketch by exchange) Assumption: n processes all arrive at time 0, bursts b1,...,bn known. Consider any schedule S that is not ordered by nondecreasing burst lengths. Then there exists an adjacent pair i,j in S where bi > bj but i is scheduled before j. Let the start time of i be t. In S, waiting contribution of this pair to total waiting is Wi_pair = t + (t + bi) = 2t + bi. If we swap them, new contribution is 2t + bj. Because bj < bi, the swap reduces total waiting by (bi − bj) > 0. Repeat pairwise swaps until sequence sorted by ascending burst: this final schedule has no adjacent inversion and therefore has minimal total waiting. Thus SJF minimises average waiting time under the assumption.
Common mistakes
- In Round Robin, forgetting to place a partially executed process at the ready queue tail and to account for later time slices.
- When doing preemptive SJF (SRTF), failing to consider newly arriving shorter jobs that preempt the running one.
- Ignoring context-switch time when quantum is very small (practical RR performance degrades if q ≈ context‑switch time).
- Using SJF’s/SRTF’s optimality claims without stating assumptions (for non‑preemptive SJF: all jobs arrive at time 0 and bursts are known; for preemptive SRTF/SRPT with known remaining times: optimal even with arbitrary arrivals).
For your exam
Kinds of questions:
- Definitions (e.g., define waiting time, response time, preemptive scheduling). Answer: give formal definition and unit.
- Short notes (compare FCFS, SJF, RR and Priority). Answer: list key properties, pros/cons, typical use.
- Derivations/proofs (e.g., prove SJF minimises average waiting under given assumptions). Answer: give clear exchange argument with assumptions stated.
- Numericals (scheduling traces, compute averages). Answer: draw Gantt chart, list completion/turnaround/waiting times in a table, show arithmetic and final averages with units.
- Diagrams: draw a Gantt chart for the schedule; label times and show queues if required.
What a full-marks answer includes:
- Precise definitions (bold or labelled), units, and clearly stated assumptions.
- Correct Gantt chart (timeline with times at block boundaries).
- Clear step-by-step computation of Ci, Ti, Wi and averages with arithmetic shown and units.
- For proofs, a clear logical argument (e.g., exchange argument) and statement of when the theorem applies.
Quick check
- Define waiting time.
- In RR, what happens if quantum q → ∞?
- State one disadvantage of priority scheduling.
Answers: 1) Waiting time = total time spent in the ready queue (in the single‑CPU‑burst examples here, Wi = Ti − Bi). 2) If q → ∞ RR becomes FCFS (no preemption). 3) Lower‑priority processes may starve unless aging is used.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?