CPU Scheduling FCFS, SJF, Round Robin: Tutorial, Examples, FAQs & Interview Tips

CPU Scheduling Concepts

CPU scheduling determines which process in the ready queue gets the CPU next. The goal is to maximize CPU utilization and system throughput while minimizing waiting time and response time.

Scheduling Criteria:

Preemptive vs Non-Preemptive:

CPU Utilization: Keep the CPU as busy as possible (maximize)
Throughput: Number of processes completed per unit time (maximize)
Turnaround Time: Total time from submission to completion (minimize)
Waiting Time: Total time spent in the ready queue (minimize)
Response Time: Time from submission to first response (minimize)
Non-Preemptive: Once a process gets the CPU, it keeps it until it terminates or blocks for I/O.
Preemptive: The OS can forcibly take the CPU from a running process (e.g., when a higher-priority process arrives or time quantum expires).

FCFS - First Come First Served

Processes are executed in the order they arrive. Simple but can cause the convoy effect (short processes wait behind long ones).

Example: Processes P1(24ms), P2(3ms), P3(3ms) arrive at time 0.

Gantt Chart: | P1 (0-24) | P2 (24-27) | P3 (27-30) |

Waiting times: P1=0, P2=24, P3=27 -> Average = 17ms
Non-preemptive

SJF - Shortest Job First

The process with the shortest CPU burst time is scheduled next. Optimal for minimizing average waiting time, but requires knowing burst times in advance.

Non-Preemptive SJF Example: P1(6ms), P2(8ms), P3(7ms), P4(3ms) all arrive at time 0.

Order: P4(3) -> P1(6) -> P3(7) -> P2(8)

Gantt Chart: | P4 (0-3) | P1 (3-9) | P3 (9-16) | P2 (16-24) |

Preemptive SJF (SRTF - Shortest Remaining Time First): If a new process arrives with a shorter remaining burst time than the current process, preempt the current process.

Waiting times: P1=3, P2=16, P3=9, P4=0 -> Average = 7ms

Round Robin (RR)

Each process gets a fixed time quantum (time slice). After the quantum expires, the process is preempted and moved to the back of the ready queue. Fair for all processes.

Example: P1(24ms), P2(3ms), P3(3ms), quantum=4ms

Gantt Chart: | P1(0-4) | P2(4-7) | P3(7-10) | P1(10-14) | P1(14-18) | P1(18-22) | P1(22-26) | P1(26-30) |

Waiting times: P1=6, P2=4, P3=7 -> Average = 5.67ms
Preemptive
Quantum too small -> too many context switches; too large -> degenerates to FCFS

Priority Scheduling

Each process is assigned a priority. The process with the highest priority (lowest number) is scheduled first. Can be preemptive or non-preemptive.

Problem: Starvation - low-priority processes may never execute if high-priority processes keep arriving.

Solution: Aging - gradually increase the priority of waiting processes over time.

Multilevel Queue Scheduling

The ready queue is divided into multiple queues based on process type (e.g., foreground/interactive vs background/batch). Each queue has its own scheduling algorithm. Processes cannot move between queues.

Multilevel Feedback Queue: Processes can move between queues based on their behavior. CPU-bound processes move to lower-priority queues; I/O-bound processes stay in higher-priority queues. Most flexible and complex algorithm.

Scheduling Algorithm Comparison

Algorithm	Preemptive	Starvation	Overhead	Best For
FCFS	No	No	Low	Batch systems
SJF	No	Yes	Low	Batch, known burst times
SRTF	Yes	Yes	Medium	Minimizing avg wait time
Round Robin	Yes	No	High	Time-sharing systems
Priority	Both	Yes	Medium	Real-time systems
MLQ	Both	Yes	High	Mixed workloads
MLFQ	Yes	No (aging)	Very High	General purpose

Previous Next