Labs / Systems Architecture

CPU Process Scheduler

Compare FCFS, SJF, SRTF, and Round Robin on a live Gantt chart. Edit arrival and burst times to see the Convoy Effect and preemption in action.

New to this? There\'s a lesson below ↓
← BACK TO LABS
Gantt Timeline & Process Table
CPU EXECUTION TIMELINE
PROC ARRIVAL BURST START FINISH WAIT TURNAROUND RESPONSE
Scheduler Policy & Metrics
AVG WAITING
0.00
AVG TURNAROUND
0.00
AVG RESPONSE
0.00
SWITCHES
0
What's happening?
The lesson

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

AlgorithmPreemptive?Selection RuleStrengths & Trade-offs
FCFS (First-Come, First-Served)NoFIFO queue by Arrival TimeZero starvation, minimal context switches, but suffers from the Convoy Effect when a long burst arrives before short bursts.
SJF (Shortest Job First)NoSmallest total Burst Time among ready processesMinimizes average waiting time among non-preemptive policies, but cannot preempt a long job already running.
SRTF (Shortest Remaining Time First)YesSmallest Remaining Time among ready processesProvably optimal for minimum average waiting time, but can cause starvation of long jobs if short jobs arrive continuously.
RR (Round Robin)YesFIFO 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 from 0 → 7. At t = 7, the ready queue holds P2 (4), P3 (1), and P4 (4), so SJF runs P3 (7→8), P2 (8→12), and P4 (12→16). Average Waiting Time = 4.00.
  • Under SRTF (preemptive), P1 runs 0 → 2 (5 remaining). At t = 2, P2 arrives with burst 4 (4 < 5), preempting P1! At t = 4, P3 arrives with burst 1 (1 < 2 remaining on P2), preempting P2! Average Waiting Time drops to 3.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 q is 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
• Under FCFS: P1 finishes at 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?

What happens to Round Robin scheduling when the time quantum q is larger than every process's burst time?

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?

What is the main drawback of SJF and SRTF in a general-purpose operating system?