Learning outcomes
- Evaluate first‑come first‑serve, shortest job first, priority, round robin and multilevel queue scheduling algorithms.
Unit 3 · CPU Scheduling, Threads & Deadlocks
Lecture 7: Scheduling algorithms
Lecture Notes
Main content
Scheduling Algorithms
CPU scheduling is the operating-system activity of selecting one process from the ready queue and allocating the CPU to it. The goal is not just to “keep the CPU busy,” but to do so with good performance, fairness, and responsiveness. In this note, we evaluate FCFS, SJF, Priority, Round Robin, and Multilevel Queue scheduling algorithms.
FCFS
SJF
Priority
Round Robin
Multilevel Queue
CPU Scheduling
1. Scheduling Evaluation Criteria
To evaluate a scheduling algorithm, we use standard performance measures.
| Criterion | Meaning | Desired Trend |
|---|---|---|
| CPU Utilization | Percentage of time the CPU is doing useful work | Higher is better |
| Throughput | Number of processes completed per unit time | Higher is better |
| Turnaround Time | Total time from submission to completion | Lower is better |
| Waiting Time | Total time spent waiting in the ready queue | Lower is better |
| Response Time | Time from submission until first response | Lower is better |
| Fairness | Whether processes get a reasonable share of CPU time | Balanced |
Important: No single scheduling algorithm is best for every situation.
Batch systems, interactive systems, and real-time systems prefer different behavior.
2. First-Come First-Serve (FCFS)
2.1 Basic idea
In FCFS, the process that arrives first gets the CPU first. It is the simplest non-preemptive scheduling algorithm.
Rule: Serve processes in order of arrival
2.2 Characteristics
- Simple to understand and implement
- Non-preemptive
- Processes are executed in arrival order
- Suitable for simple batch-style environments
2.3 Evaluation
| Aspect | Evaluation of FCFS |
|---|---|
| Simplicity | Excellent |
| Average waiting time | Often poor |
| Response time for short jobs | Poor if a long job comes first |
| Fairness | Arrival-order fair, but not performance fair |
Convoy effect: A long CPU-bound process can delay many short processes,
causing poor average waiting and response time.
Figure 1: In FCFS, a long process arriving first can delay shorter ones behind it.
3. Shortest Job First (SJF)
3.1 Basic idea
SJF selects the process with the smallest CPU burst next. It may be non-preemptive or, in its preemptive form, called Shortest Remaining Time First (SRTF).
Rule: Choose the process with the shortest next CPU burst
3.2 Why it is important
SJF is famous because it gives the minimum average waiting time among all scheduling algorithms, provided burst lengths are known exactly.
3.3 Evaluation
| Aspect | Evaluation of SJF |
|---|---|
| Average waiting time | Best possible in theory |
| Turnaround time | Usually very good |
| Implementation | Difficult because next CPU burst must be estimated |
| Fairness | Can be unfair to long jobs |
Main weakness: Exact future CPU burst length is usually not known.
So real systems can only approximate SJF.
Example
If processes have burst times 10, 2, and 1, SJF runs 1 first, then 2, then 10. That sharply reduces average waiting time compared with FCFS.
4. Priority Scheduling
4.1 Basic idea
In priority scheduling, the CPU is allocated to the process with the highest priority. Depending on convention, either a smaller number or a larger number may indicate higher priority.
Rule: Choose the highest-priority ready process
4.2 Types
- Non-preemptive priority scheduling – once CPU is allocated, process continues until completion or blocking
- Preemptive priority scheduling – a newly arrived higher-priority process can preempt the running one
4.3 Evaluation
| Aspect | Evaluation of Priority Scheduling |
|---|---|
| Flexibility | Very useful when some jobs are more important than others |
| Response for urgent jobs | Good |
| Fairness | Can be poor for low-priority jobs |
| Main problem | Starvation of low-priority processes |
Starvation: A low-priority process may wait indefinitely if higher-priority jobs keep arriving.
Aging: A common solution to starvation is to gradually increase the priority of waiting processes over time.
5. Round Robin (RR)
5.1 Basic idea
Round Robin is designed mainly for time-sharing systems. Each process gets the CPU for a fixed small unit of time called a time quantum. If the process does not finish within that quantum, it is preempted and placed at the end of the ready queue.
Rule: Each process gets CPU for at most one time quantum per turn
5.2 Evaluation
| Aspect | Evaluation of Round Robin |
|---|---|
| Response time | Very good for interactive systems |
| Fairness | Good; every process gets a turn |
| Waiting time | Moderate; depends on quantum |
| Overhead | Higher due to context switching |
5.3 Effect of time quantum
- If the quantum is too large, RR behaves almost like FCFS.
- If the quantum is too small, too many context switches occur.
- A reasonable quantum gives good response without excessive overhead.
Figure 2: Round Robin gives each process a small time slice in cyclic order.
6. Multilevel Queue Scheduling
6.1 Basic idea
In Multilevel Queue Scheduling, the ready queue is split into several separate queues. Each queue may represent a different class of processes, such as:
- system processes
- interactive processes
- batch processes
- student or low-priority background jobs
Each queue can have its own scheduling algorithm. For example:
- foreground queue → Round Robin
- background queue → FCFS
6.2 Evaluation
| Aspect | Evaluation of Multilevel Queue |
|---|---|
| Specialization | Very good; different workloads can be handled differently |
| Interactive response | Good if higher queues are assigned to interactive jobs |
| Fairness | Can be poor if lower queues get too little CPU |
| Complexity | Higher than FCFS or RR |
Figure 3: Multilevel Queue Scheduling separates processes by class and may assign different policies to different queues.
Main weakness: Lower-priority queues may suffer starvation if CPU time is strongly biased toward higher queues.
7. Comparative Evaluation
| Algorithm | Main strength | Main weakness | Best suited for |
|---|---|---|---|
| FCFS | Very simple and easy to implement | Convoy effect; poor response for short jobs | Simple batch systems |
| SJF | Minimum average waiting time | Needs burst prediction; long jobs may wait | Batch workloads where burst estimates are possible |
| Priority | Urgent jobs can be favored | Starvation of low-priority jobs | Systems with importance-based tasks |
| Round Robin | Good response and fairness | Context-switch overhead; depends on quantum | Interactive and time-sharing systems |
| Multilevel Queue | Different policies for different job classes | Complex; lower queues may starve | Mixed workloads with clear job categories |
8. Final Remarks
FCFS is the simplest scheduling algorithm, but its average waiting and response time may be poor.
SJF gives the best average waiting time in theory, but it depends on burst-time prediction.
Priority Scheduling is useful when some tasks are more important, but starvation is a serious concern.
Round Robin is widely used in interactive systems because it gives fast response and fair CPU sharing.
Multilevel Queue Scheduling is powerful when different types of jobs need different policies, but it is more complex and can also starve lower queues.
9. Likely University Questions
- Explain FCFS scheduling and discuss its advantages and disadvantages.
- Why is SJF considered optimal for average waiting time?
- What is starvation in priority scheduling? How can it be reduced?
- Explain Round Robin scheduling and the effect of time quantum.
- Differentiate between Round Robin and FCFS.
- What is Multilevel Queue Scheduling? How does it differ from simple queue scheduling?
- Compare FCFS, SJF, Priority, Round Robin, and Multilevel Queue scheduling algorithms.