CPU Scheduling
What is CPU Scheduling?
CPU scheduling is the process by which the operating system selects one process from the ready queue and allocates the CPU to it.
CPU Scheduling = Deciding which ready process gets the CPU next.
Ready Queue ┌────┬────┬────┬────┐ │ P1 │ P2 │ P3 │ P4 │ └────┴────┴────┴────┘ | ↓ CPU Scheduler | ↓ Selected P2 | ↓ CPU
CPU scheduling is especially important in multiprogramming and multitasking systems, where many processes compete for CPU time.
1. Why CPU Scheduling Is Needed
Suppose four processes are ready:
P1 P2 P3 P4
But only one CPU core is available:
P1 ─┐ P2 ─┤ P3 ─┼──→ CPU P4 ─┘
The OS must determine:
- Which process runs first?
- How long should it run?
- When should it be interrupted?
- Which process should run next?
These decisions are made using CPU scheduling algorithms.
2. CPU-I/O Burst Cycle
A process normally alternates between CPU work and I/O operations.
CPU Burst ↓ I/O Burst ↓ CPU Burst ↓ I/O Burst ↓ CPU Burst ↓ Termination
CPU Burst
Time during which a process is actively using the CPU.
I/O Burst
Time during which a process performs or waits for I/O.
For example:
Process ↓ Calculate something ↓ Read from disk ↓ Calculate ↓ Network request ↓ Calculate
When one process is waiting for I/O, the OS can give the CPU to another ready process.
3. CPU Scheduling Objectives
A good CPU scheduling algorithm tries to achieve several goals.
1. Maximize CPU Utilization
Keep the CPU busy as much as possible.
CPU utilization = 95%
is generally better than:
CPU utilization = 50%
2. Maximize Throughput
Throughput = number of processes completed per unit of time.
For example:
20 processes / second
Higher throughput is generally desirable.
3. Minimize Turnaround Time
Turnaround time is the total time from process arrival/submission until completion.
Turnaround Time = Completion Time − Arrival Time
4. Minimize Waiting Time
Waiting time is the time a process spends waiting in the ready queue.
Ready Queue ↓ waiting ↓ CPU
5. Minimize Response Time
Response time is the time from arrival until the process first receives CPU service.
Response Time = First CPU Start Time − Arrival Time
This is especially important for interactive systems.
6. Ensure Fairness
The scheduler should avoid indefinitely ignoring processes.
4. Important CPU Scheduling Terms
Before learning algorithms, understand these terms.
Arrival Time (AT)
The time at which a process enters the ready queue.
Example:
P1 → AT = 0 P2 → AT = 2 P3 → AT = 4
Burst Time (BT)
The amount of CPU time required by a process for a particular CPU burst.
Example:
P1 → BT = 5 ms
means P1 needs 5 ms of CPU time for that burst.
Completion Time (CT)
The time at which a process finishes execution.
Turnaround Time (TAT)
TAT = CT − AT
Waiting Time (WT)
For the standard single-CPU scheduling calculations:
WT = TAT − BT
Therefore:
WT = CT − AT − BT
Response Time (RT)
RT = First Start Time − Arrival Time
5. Gantt Chart
A Gantt chart is used to represent CPU scheduling visually.
Example:
0 5 8 10 |-------|-------|-------| P1 P2 P3
Meaning:
0–5 → P1 5–8 → P2 8–10 → P3
Gantt charts are extremely important when solving scheduling problems.
6. Preemptive vs Non-Preemptive Scheduling
CPU scheduling algorithms can be classified as:
CPU Scheduling | +── Non-Preemptive | └── Preemptive
Non-Preemptive Scheduling
Once a process gets the CPU, the OS normally lets it continue until:
- It terminates
- It blocks for I/O
- It voluntarily gives up the CPU
Example:
P1 running ↓ P1 continues ↓ P1 finishes ↓ P2 runs
Common examples:
- FCFS
- Non-preemptive SJF
- Non-preemptive Priority
Preemptive Scheduling
The OS can interrupt a running process and assign the CPU to another process.
P1 running ↓ Interrupt ↓ P1 paused ↓ P2 runs
Common examples:
- SRTF
- Round Robin
- Preemptive Priority
7. Major CPU Scheduling Algorithms
The important algorithms are:
CPU Scheduling Algorithms | ├── FCFS ├── SJF ├── SRTF ├── Priority ├── Round Robin ├── Multilevel Queue └── Multilevel Feedback Queue
Let's understand each.
8. FCFS — First-Come, First-Served
FCFS is one of the simplest scheduling algorithms.
The process that arrives first gets the CPU first.
It is normally non-preemptive.
Example:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 2 |
Arrival order:
P1 → P2 → P3
Therefore:
0 5 8 10 |-------|-------|-------| P1 P2 P3
Advantages of FCFS
- Very simple
- Easy to implement
- Fair according to arrival order
- No starvation in the basic form
Disadvantages
- Poor average waiting time in some workloads
- Poor response time for short jobs behind long jobs
- Can suffer from the convoy effect
9. Convoy Effect
Suppose a long process arrives first:
P1 = 20 ms P2 = 2 ms P3 = 2 ms P4 = 1 ms
FCFS:
0 20 22 24 25 |--------------------|----|----|----| P1 P2 P3 P4
P2, P3 and P4 are very short, but they have to wait for P1.
This is called the:
Convoy Effect
10. SJF — Shortest Job First
Shortest Job First selects the process with the smallest CPU burst.
Shortest CPU burst gets selected first.
Example:
| Process | Burst Time |
|---|---|
| P1 | 8 |
| P2 | 3 |
| P3 | 5 |
Order:
P2 → P3 → P1
Gantt chart:
0 3 8 16 |---|-------|---------------| P2 P3 P1
Advantage
SJF can produce a very low average waiting time when burst times are known accurately.
Disadvantage
The OS generally cannot know the exact future CPU burst length in advance.
Also, long processes may experience starvation if short processes keep arriving.
11. SRTF — Shortest Remaining Time First
SRTF is the preemptive version of SJF.
The process with the shortest remaining CPU time gets the CPU.
Suppose:
P1 → remaining 7 ms P2 → remaining 3 ms
P2 gets the CPU because:
3 < 7
If a new shorter process arrives while another process is running, the current process can be preempted.
P1 running ↓ P2 arrives ↓ P2 has shorter remaining time ↓ P1 paused ↓ P2 runs
12. SJF vs SRTF
| SJF | SRTF |
|---|---|
| Usually non-preemptive | Preemptive |
| Shortest burst selected | Shortest remaining time selected |
| Running process normally continues | Running process can be interrupted |
| Simpler | More complex |
| Can cause starvation | Can also cause starvation |
Memory trick:
SJF → Shortest Job
SRTF → Shortest Remaining Time
13. Priority Scheduling
Each process has a priority.
The scheduler selects the process with the highest priority according to the system's priority convention.
Example:
| Process | Priority |
|---|---|
| P1 | 3 |
| P2 | 1 |
| P3 | 2 |
If 1 means highest priority:
P2 → P3 → P1
Priority scheduling can be:
- Preemptive
- Non-preemptive
14. Starvation
A low-priority process may wait for a very long time if higher-priority processes keep arriving.
High Priority → CPU High Priority → CPU High Priority → CPU High Priority → CPU ↓ Low Priority → Still waiting
This is called:
Starvation
15. Aging
Aging is a technique used to reduce starvation.
The priority of a waiting process is gradually increased.
Example:
Initially: P4 → Priority 10 After waiting: P4 → Priority 8 After more waiting: P4 → Priority 5 Later: P4 → Priority 1
Eventually, the process becomes important enough to receive CPU time.
Aging prevents starvation by gradually increasing the priority of waiting processes.
16. Round Robin (RR)
Round Robin is one of the most important preemptive scheduling algorithms.
It is commonly associated with time-sharing systems.
Each process gets a fixed amount of CPU time called a:
Time Quantum
Example:
Time Quantum = 2 ms
Processes:
P1 → P2 → P3 → P1 → P2 → ...
Example:
0 2 4 6 8 10 |----|----|----|----|----| P1 P2 P3 P1 P2
After its quantum expires, a process that still needs CPU time is generally placed back into the ready queue.
17. Round Robin Example
Suppose:
| Process | Burst Time |
|---|---|
| P1 | 5 |
| P2 | 3 |
| P3 | 2 |
Time quantum:
2 ms
Execution:
0 2 4 6 8 9 10 |----|----|----|----|----|-----| P1 P2 P3 P1 P2 P1
Explanation:
0–2 → P1 2–4 → P2 4–6 → P3 finishes 6–8 → P1 8–9 → P2 finishes 9–10 → P1 finishes
18. Effect of Time Quantum
The time quantum is very important.
Very large quantum
Round Robin starts behaving similarly to FCFS.
Large Quantum ↓ Less preemption ↓ More like FCFS
Very small quantum
There can be many context switches.
Very Small Quantum ↓ Many Context Switches ↓ Higher Overhead
Therefore, the time quantum should be chosen appropriately.
19. Multilevel Queue Scheduling
Processes are divided into different queues based on characteristics such as process type or priority.
Example:
Ready Processes | +--------------+--------------+ ↓ ↓ Interactive Queue Batch Queue ↓ ↓ Round Robin FCFS
For example:
Queue 1 → System processes Queue 2 → Interactive processes Queue 3 → Batch processes
Each queue can have its own scheduling algorithm.
20. Multilevel Feedback Queue
Multilevel Feedback Queue (MLFQ) is more flexible.
Processes can move between queues depending on their behavior.
High Priority ┌─────────────┐ │ Queue 1 │ └──────┬──────┘ ↓ ┌─────────────┐ │ Queue 2 │ └──────┬──────┘ ↓ ┌─────────────┐ │ Queue 3 │ └─────────────┘ Low Priority
For example:
- CPU-intensive processes may move to lower-priority queues.
- Interactive/short processes may remain in higher-priority queues.
- Aging can be used to prevent starvation.
21. Scheduling Algorithm Comparison
| Algorithm | Preemptive? | Main Idea | Main Problem |
|---|---|---|---|
| FCFS | Usually No | First arrival first | Convoy effect |
| SJF | No | Shortest burst first | Starvation / burst prediction |
| SRTF | Yes | Shortest remaining time | Starvation / overhead |
| Priority | Either | Highest priority first | Starvation |
| Round Robin | Yes | Fixed time quantum | Quantum selection |
| Multilevel Queue | Usually depends | Separate queues | Inflexibility/starvation |
| MLFQ | Yes | Processes can move between queues | Complexity |
22. Important Scheduling Formulas
These formulas are extremely important for numerical questions.
Turnaround Time
TAT = Completion Time − Arrival Time
Waiting Time
WT = Turnaround Time − Burst Time
Therefore:
WT = CT − AT − BT
Response Time
RT = First Start Time − Arrival Time
23. Average Waiting Time
If there are n processes:
Average Waiting Time = Sum of Waiting Times / Number of Processes
Example:
P1 = 2 ms P2 = 4 ms P3 = 6 ms
Then:
Average WT = (2 + 4 + 6) / 3 = 12 / 3 = 4 ms
24. Average Turnaround Time
Similarly:
Average TAT = Sum of Turnaround Times / Number of Processes
25. Context Switching in CPU Scheduling
When the scheduler changes the running process:
P1 Running ↓ Save P1 context ↓ Load P2 context ↓ P2 Running
This is called a context switch.
Context switching consumes CPU time.
Therefore:
More context switches ↓ More overhead ↓ Potentially lower performance
26. Dispatcher Latency
Dispatcher latency is the time required for the dispatcher to stop one process and start another.
Scheduler selects P2 ↓ Dispatcher ↓ Context switch ↓ P2 starts
Lower dispatcher latency is desirable, especially for interactive systems.
27. CPU Scheduling Example
Let's solve a basic FCFS problem.
Given:
| Process | AT | BT |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 2 |
FCFS order:
P1 → P2 → P3
Gantt chart:
0 5 8 10 |-------|-------|-------| P1 P2 P3
P1
CT = 5 TAT = 5 − 0 = 5 WT = 5 − 5 = 0 RT = 0 − 0 = 0
P2
CT = 8 TAT = 8 − 1 = 7 WT = 7 − 3 = 4 RT = 5 − 1 = 4
P3
CT = 10 TAT = 10 − 2 = 8 WT = 8 − 2 = 6 RT = 8 − 2 = 6
Therefore:
Average Waiting Time = (0 + 4 + 6) / 3 = 10 / 3 ≈ 3.33 ms
Average Turnaround Time = (5 + 7 + 8) / 3 = 20 / 3 ≈ 6.67 ms
28. What Makes a Good CPU Scheduling Algorithm?
A good algorithm tries to:
Good Scheduler | +-------------+-------------+ ↓ ↓ ↓ Low Waiting Low Response High Throughput | ↓ Low Turnaround | ↓ High CPU Utilization | ↓ Fairness
But there is no single algorithm that is best for every workload.
For example:
- FCFS → simple
- SJF → good average waiting time under suitable assumptions
- Round Robin → good for interactive systems
- Priority → useful when tasks have different importance
- MLFQ → flexible but more complex
29. CPU Scheduling vs Process Scheduling
These terms are closely related.
Process Scheduling
A broader concept involving the management and selection of processes.
CPU Scheduling
Specifically focuses on:
Selecting a ready process to execute on the CPU.
So:
Process Scheduling ↓ CPU Scheduling ↓ Select Ready Process ↓ CPU
30. Complete CPU Scheduling Flow
Processes | ↓ Ready Queue | ↓ ┌─────────────────┐ │ CPU Scheduler │ └────────┬────────┘ ↓ Select Process | ↓ Dispatcher | ↓ Context Switch | ↓ CPU | +------+------+ | | I/O Wait Finish | | ↓ ↓ Waiting Terminated | ↓ Ready Queue
🧠 Quick Revision
Remember the major algorithms:
FCFS ↓ First arrival first SJF ↓ Shortest job first SRTF ↓ Shortest remaining time Priority ↓ Highest priority first Round Robin ↓ Fixed time quantum Multilevel Queue ↓ Separate fixed queues MLFQ ↓ Processes can move between queues
Most important exam points
- CPU scheduling selects a ready process for CPU execution.
- FCFS is generally non-preemptive.
- SJF selects the shortest CPU burst.
- SRTF is the preemptive form of SJF.
- Priority scheduling selects according to priority.
- Round Robin uses a time quantum and is preemptive.
- Starvation can occur when a process waits indefinitely.
- Aging helps prevent starvation.
- Context switching introduces overhead.
- Important formulas:
TAT = CT − ATWT = TAT − BTRT = First Start Time − AT
- Important performance criteria:
- CPU utilization
- Throughput
- Waiting time
- Turnaround time
- Response time
- Fairness