Introduction
CPU scheduling is essential for maximizing CPU efficiency and ensuring smooth process execution. Different scheduling algorithms are used based on system requirements. The four major algorithms discussed here are:
- First Come, First Served (FCFS)
- Shortest Job First (SJF)
- Round Robin (RR)
- Multilevel Queue Scheduling (MLQ)
1. First Come, First Served (FCFS) Scheduling
Definition
- The process that arrives first in the queue is executed first.
- Works like a queue system (FIFO – First In, First Out).
How It Works
- The CPU is allocated to processes in the order of their arrival.
- Once a process gets the CPU, it runs to completion (Non-Preemptive).
Example
| Process | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 ms | 5 ms | 5 ms | 5 ms | 0 ms |
| P2 | 1 ms | 3 ms | 8 ms | 7 ms | 4 ms |
| P3 | 2 ms | 8 ms | 16 ms | 14 ms | 6 ms |
Advantages
Simple and easy to implement Works well for batch systems
Disadvantages
Poor response time for short processes Convoy Effect: Long processes make short ones wait
2. Shortest Job First (SJF) Scheduling
Definition
- The process with the smallest burst time is executed first.
- Can be Non-Preemptive or Preemptive (Shortest Remaining Time First – SRTF).
How It Works
- The scheduler selects the shortest job available in the queue.
- If Preemptive, a newly arrived shorter job preempts the running process.
Example (Non-Preemptive SJF)
| Process | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 ms | 7 ms | 7 ms | 7 ms | 0 ms |
| P2 | 1 ms | 4 ms | 11 ms | 10 ms | 6 ms |
| P3 | 2 ms | 1 ms | 3 ms | 1 ms | 0 ms |
| P4 | 3 ms | 2 ms | 5 ms | 2 ms | 0 ms |
Advantages
Minimizes average waiting and turnaround time Efficient for batch processing
Disadvantages
Starvation: Long processes may never execute Difficult to estimate burst time
3. Round Robin (RR) Scheduling
Definition
- Each process gets a fixed time quantum (time slice) before switching to the next process.
- Preemptive scheduling ensuring fair CPU distribution.
How It Works
- A fixed time quantum (e.g., 4ms) is assigned.
- The CPU cycles through processes in a round-robin fashion.
- If a process is not completed within its quantum, it goes to the end of the queue.
Example (Time Quantum = 4ms)
| Process | Arrival Time | Burst Time | Order of Execution | Completion Time | Turnaround Time | Waiting Time |
|---|---|---|---|---|---|---|
| P1 | 0 ms | 10 ms | P1(4) → P2(4) → P3(4) → P1(4) → P1(2) | 20 ms | 20 ms | 10 ms |
| P2 | 1 ms | 6 ms | P2(4) → P3(4) → P1(4) → P1(4) → P2(2) | 12 ms | 11 ms | 5 ms |
| P3 | 2 ms | 8 ms | P3(4) → P1(4) → P1(4) → P3(4) | 16 ms | 14 ms | 6 ms |
Advantages
Prevents starvation (each process gets CPU time) Fair for interactive systems
Disadvantages
High Context Switching Overhead Performance depends on quantum size:
- Too small → Too many switches, wasting CPU time
- Too large → Becomes similar to FCFS
4. Multilevel Queue (MLQ) Scheduling
Definition
- Processes are divided into multiple queues based on priority or type (foreground/background).
- Each queue has its own scheduling algorithm.
How It Works
- The system divides processes into separate queues, such as:
- Foreground Queue (Interactive, uses Round Robin)
- Background Queue (Batch jobs, uses FCFS)
- CPU allocates time to each queue based on priority.
Example Queue Structure
| Queue Type | Scheduling Algorithm |
|---|---|
| System Processes | Highest Priority |
| Interactive Processes | Round Robin |
| Background (Batch Jobs) | FCFS |
Advantages
Good for multi-user and multi-tasking systems Can handle different process types efficiently
Disadvantages
Difficult to implement Priority inversion (low-priority process may get delayed indefinitely)
Comparison of Scheduling Algorithms
| Criteria | FCFS | SJF | Round Robin | Multilevel Queue |
|---|---|---|---|---|
| Type | Non-Preemptive | Preemptive / Non-Preemptive | Preemptive | Preemptive & Non-Preemptive |
| Efficiency | Low (convoy effect) | High (low waiting time) | Medium (fair but overhead) | High (multi-tasking) |
| Starvation | No | Yes (for long jobs) | No | Yes (lower priority may starve) |
| Response Time | High | Medium | Low (good for interactive) | Varies |
| Best For | Batch Systems | Short processes | Time-sharing Systems | Multi-tasking Systems |
Conclusion
Each scheduling algorithm serves a different purpose:
- FCFS is simple but inefficient.
- SJF minimizes waiting time but causes starvation.
- Round Robin is fair but has context-switching overhead.
- Multilevel Queue is ideal for multi-user systems but complex to implement.