OS Process Scheduling: FCFS, SJF, SRTF, and Round Robin
How preemptive and non-preemptive schedulers trade off Turnaround Time, Waiting Time, Response Time, and context-switch overhead.
1. CPU Scheduling Metrics
When multiple processes are ready to run in main memory, the Operating System's CPU Scheduler decides which ready process gets the CPU next and for how long. Every scheduling algorithm is evaluated using three exact per-process formulas:
Turnaround Time = Finish Time − Arrival Time (total time from submission to completion)
Waiting Time = Turnaround Time − Burst Time (total time spent waiting in the ready queue)
Response Time = First Start Time − Arrival Time (delay from arrival until first CPU execution)
A non-preemptive scheduler lets a running process keep the CPU until it finishes its CPU burst (or blocks on I/O). A preemptive scheduler can interrupt a running process mid-burst and switch the CPU to another process.
2. Comparing the Four Scheduling Algorithms
| Algorithm | Preemptive? | Selection Rule | Strengths & Trade-offs |
|---|---|---|---|
| FCFS (First-Come, First-Served) | No | FIFO queue by Arrival Time | Zero starvation, minimal context switches, but suffers from the Convoy Effect when a long burst arrives before short bursts. |
| SJF (Shortest Job First) | No | Smallest total Burst Time among ready processes | Minimizes average waiting time among non-preemptive policies, but cannot preempt a long job already running. |
| SRTF (Shortest Remaining Time First) | Yes | Smallest Remaining Time among ready processes | Provably optimal for minimum average waiting time, but can cause starvation of long jobs if short jobs arrive continuously. |
| RR (Round Robin) | Yes | FIFO queue with fixed time slice (Quantum q) | Excellent Response Time and fair CPU sharing for interactive tasks, at the cost of higher Turnaround Time and context-switch overhead. |
3. Tracing the Presets in the Simulator
A. The Convoy Effect (FCFS vs. SJF / RR):
Click CONVOY EFFECT (P1: burst 12 arrives at t = 0, followed by P2, P3, P4: burst 1 at t = 1, 2, 3). Under FCFS, the three 1-unit jobs wait behind P1 until t = 12, 13, 14, giving an Average Waiting Time of (0 + 11 + 11 + 11) / 4 = 8.25. Switch to SRTF: P1 is preempted at t = 1 so P2, P3, and P4 finish at t = 2, 3, 4, dropping Average Waiting Time to (3 + 0 + 0 + 0) / 4 = 0.75.
B. Non-Preemptive SJF vs. Preemptive SRTF:
Click PREEMPTION TEST (P1: arr 0, burst 7; P2: arr 2, burst 4; P3: arr 4, burst 1; P4: arr 5, burst 4):
- Under SJF (non-preemptive), only P1 is ready at
t = 0, so P1 runs uninterrupted from0 → 7. Att = 7, the ready queue holds P2 (4), P3 (1), and P4 (4), so SJF runsP3 (7→8),P2 (8→12), andP4 (12→16). Average Waiting Time =4.00. - Under SRTF (preemptive), P1 runs
0 → 2(5 remaining). Att = 2, P2 arrives with burst 4 (4 < 5), preempting P1! Att = 4, P3 arrives with burst 1 (1 < 2remaining on P2), preempting P2! Average Waiting Time drops to3.00.
C. Choosing the Round Robin Time Quantum (q):
Select Round Robin and vary TIME QUANTUM from 1 to 10:
- If
q → ∞(larger than the longest burst), every job finishes on its first turn and Round Robin degenerates into FCFS. - If
qis too small, SWITCHES (context switches) spike. In a real OS kernel, each context switch costs microseconds to save/restore CPU registers, flush the pipeline, and warm up the TLB/caches.
Exercises
1. Load PREEMPTION TEST and select SRTF. Calculate the Turnaround Time, Waiting Time, and Response Time for P2 (Arrival = 2, Burst = 4) by hand, then check the table.
Show solution
P2 starts immediately at t = 2, gets preempted by P3 from 4 → 5, and finishes from 5 → 7.• First Start:
2 → Response Time = 2 − 2 = 0.• Finish:
7 → Turnaround Time = 7 − 2 = 5.• Waiting Time:
Turnaround − Burst = 5 − 4 = 1 (the 1 unit it waited while P3 ran from 4→5).
2. Suppose two processes with identical burst times of 4 arrive at the exact same time t = 0. Which policy has a lower Average Turnaround Time: running them back-to-back (FCFS) or alternating 1 unit at a time (Round Robin, q = 1)?
Show solution
t = 4 and P2 finishes at t = 8 → Average Turnaround = (4 + 8) / 2 = 6.0.• Under RR (q = 1): Both jobs are stretched out and finish at
t = 7 and t = 8 → Average Turnaround = (7 + 8) / 2 = 7.5.Round Robin improves Response Time (P2 starts at
t = 1 instead of t = 4), but when jobs have similar lengths, time-slicing always increases Average Turnaround Time.
Quiz
Which scheduling algorithm is provably optimal for minimizing average waiting time across any set of arrival and burst times?
Always running the job with the shortest remaining work finishes jobs at the earliest possible times, minimizing total queue wait.
What happens to Round Robin scheduling when the time quantum q is larger than every process's burst time?
Every process completes its entire burst on its first turn in arrival order.
A process arrives at t = 2, first starts executing at t = 5, has a CPU burst of 4, and finishes at t = 14. What are its Turnaround, Waiting, and Response times?
Turnaround = 14 − 2 = 12; Waiting = 12 − 4 = 8; Response = 5 − 2 = 3.
What is the main drawback of SJF and SRTF in a general-purpose operating system?
Continuous arrivals of short jobs can delay a long job indefinitely (starvation), and OS schedulers can only estimate future CPU bursts from past behavior.