Process Scheduling
What is Process Scheduling?
Process scheduling is the activity of the operating system that decides which ready process should get the CPU next.
A computer may have many processes ready to execute, but a CPU core can execute only a limited number of instructions at a time.
So the OS scheduler decides:
Ready Processes | ↓ ┌─────────────────┐ │ Process │ │ Scheduler │ └─────────────────┘ | ↓ Which process gets CPU? | ↓ CPU
Exam Definition
Process scheduling is the mechanism by which an operating system selects a process from the ready queue and allocates the CPU to it for execution.
Why Is Process Scheduling Needed?
Suppose five processes are ready:
P1 P2 P3 P4 P5
But there is only one CPU:
P1 ─┐ P2 ─┤ P3 ─┼──→ CPU P4 ─┤ P5 ─┘
The OS needs to decide:
Which process should execute first?
And after that:
Which process should execute next?
This decision is made by the scheduler.
Process Scheduling and Process States
You previously learned the process states:
┌─────────┐ │ New │ └────┬────┘ ↓ ┌─────────┐ │ Ready │ └────┬────┘ ↓ ┌─────────┐ │ Running │ └───┬─┬───┘ │ │ I/O │ │ Exit │ ↓ │ Terminated ↓ Waiting │ └────→ Ready
The scheduler primarily selects processes from the Ready Queue.
Ready Queue
The ready queue contains processes that are:
- Loaded/eligible to run
- Ready to execute
- Waiting for CPU time
Example:
Ready Queue ┌────┬────┬────┬────┬────┐ │ P1 │ P2 │ P3 │ P4 │ P5 │ └────┴────┴────┴────┴────┘ | ↓ Scheduler | ↓ CPU
The scheduler chooses one according to the scheduling algorithm.
Process Scheduler
The process scheduler is the OS component responsible for selecting processes for execution.
A simplified flow is:
Ready Queue | ↓ Scheduler | ↓ Dispatcher | ↓ CPU
The scheduler chooses the process.
The dispatcher gives CPU control to the selected process.
Scheduler vs Dispatcher
These are related but different.
Scheduler
Decides:
Which process should run?
Dispatcher
Actually performs the actions needed to give the CPU to that process.
The dispatcher may perform:
- Context switching
- Switching to user mode
- Jumping to the appropriate instruction in the selected process
Scheduler ↓ Select P2 ↓ Dispatcher ↓ Context Switch ↓ CPU → P2
Types of Process Schedulers
There are traditionally three types:
- Long-Term Scheduler
- Short-Term Scheduler
- Medium-Term Scheduler
1. Long-Term Scheduler
Also called the Job Scheduler.
It decides which jobs/processes should be admitted into the system for execution.
Jobs P1 P2 P3 P4 P5 | ↓ Long-Term Scheduler | ↓ Ready Queue
Main purpose
It controls the degree of multiprogramming — roughly, how many processes are kept active in the system.
Characteristics
- Runs less frequently
- Can take more time to make its decision
- Controls which processes enter the ready state
2. Short-Term Scheduler
Also called the CPU Scheduler.
It selects the next process from the ready queue to run on the CPU.
Ready Queue P1 P2 P3 P4 | ↓ Short-Term Scheduler | ↓ CPU
Characteristics
- Runs very frequently
- Must be fast
- Makes CPU allocation decisions
This is the scheduler most commonly discussed when studying CPU scheduling algorithms.
3. Medium-Term Scheduler
The medium-term scheduler is associated with swapping and temporarily removing processes from main memory.
RAM | ↓ Process temporarily removed | ↓ Disk / Swap | ↓ Later brought back | ↓ RAM
Its purpose can include:
- Reducing memory pressure
- Managing the degree of multiprogramming
- Suspending/resuming processes
Comparison of Schedulers
| Scheduler | Also Called | Main Job | Frequency |
|---|---|---|---|
| Long-term | Job scheduler | Admit jobs/processes | Low |
| Short-term | CPU scheduler | Select next CPU process | Very high |
| Medium-term | Swapper | Suspend/resume processes | Medium |
Easy Memory Trick
Long → Enter
Short → CPU
Medium → Swap
CPU-I/O Burst Cycle
Processes don't usually use the CPU continuously.
A process typically alternates between:
CPU Burst ↓ I/O Burst ↓ CPU Burst ↓ I/O Burst ↓ CPU Burst ↓ Termination
CPU Burst
The process executes instructions using the CPU.
I/O Burst
The process waits for an I/O operation such as:
- Disk
- Keyboard
- Network
- Printer
Example:
CPU → Disk I/O → CPU → Network I/O → CPU
While one process is waiting for I/O, the CPU can run another ready process.
This is one major reason scheduling is important.
Preemptive vs Non-Preemptive Scheduling
This is one of the most important concepts in process scheduling.
1. Non-Preemptive Scheduling
Once a process gets the CPU, it keeps the CPU until it:
- Terminates
- Blocks/waits for I/O
- Voluntarily gives up the CPU
P1 gets CPU ↓ P1 continues ↓ P1 finishes/blocks ↓ P2 gets CPU
The OS does not forcibly take the CPU away from P1 during its CPU burst.
Example
Suppose:
P1 = 5 ms P2 = 3 ms
If P1 starts first:
0 5 8 |-------|-------| P1 P2
2. Preemptive Scheduling
The OS can interrupt a running process and give the CPU to another process.
P1 running ↓ Interrupt / scheduling event ↓ P1 paused ↓ P2 runs
Example:
0 2 5 |----|----| P1 P2 P1
P1 was interrupted so P2 could execute.
Why Use Preemption?
Preemption can improve:
- Responsiveness
- Fairness
- Interactive performance
- CPU utilization
It is particularly important in interactive and time-sharing systems.
Scheduling Criteria
The OS needs criteria to evaluate scheduling algorithms.
Important metrics include:
- CPU Utilization
- Throughput
- Turnaround Time
- Waiting Time
- Response Time
- Fairness
1. CPU Utilization
The percentage of time the CPU is busy.
CPU busy = 90% CPU idle = 10%
Generally, we want:
Higher CPU utilization
2. Throughput
The number of processes completed per unit of time.
For example:
10 processes completed in 1 second
Then:
Throughput = 10 processes/second
Generally, higher throughput is desirable.
3. Turnaround Time
The total time from process submission to completion.
Turnaround Time = Completion Time − Arrival Time
Example:
Arrival = 2 ms Completion = 10 ms Turnaround = 10 − 2 = 8 ms
Goal:
Minimize turnaround time.
4. Waiting Time
The amount of time a process spends waiting in the ready queue.
Waiting Time = Total time spent waiting in Ready Queue
Example:
P1 arrives ↓ Ready Queue ↓ 5 ms waiting CPU
Waiting time = 5 ms.
Goal:
Minimize waiting time.
5. Response Time
Response time is the time from when a request/process arrives until the system first starts responding to it.
For a scheduling problem, commonly:
Response Time = First CPU Start Time − Arrival Time
Example:
Arrival = 2 ms First execution = 5 ms Response Time = 3 ms
This is especially important for interactive systems.
6. Fairness
Every process should get a reasonable opportunity to execute.
Bad scheduling can cause:
P1 → CPU P1 → CPU P1 → CPU P1 → CPU ... P2 → Waiting forever
This problem is called starvation.
Important Scheduling Algorithms
The major process/CPU scheduling algorithms are:
Scheduling Algorithms | ├── FCFS ├── SJF ├── SRTF ├── Priority ├── Round Robin ├── Multilevel Queue └── Multilevel Feedback Queue
Your next topic is specifically CPU Scheduling, where these algorithms can be studied in detail.
Still, let's understand the basic idea now.
1. FCFS
First-Come, First-Served
The process that arrives first gets the CPU first.
Arrival Order: P1 → P2 → P3 Execution: P1 → P2 → P3
Usually non-preemptive.
Example
P1 = 5 ms P2 = 3 ms P3 = 2 ms
Execution:
0 5 8 10 |-------|-------|-------| P1 P2 P3
2. SJF
Shortest Job First
The process with the smallest CPU burst is selected first.
Example:
P1 = 8 ms P2 = 3 ms P3 = 5 ms
Order:
P2 → P3 → P1
SJF is normally discussed as non-preemptive.
Its preemptive version is called Shortest Remaining Time First (SRTF).
3. Priority Scheduling
Each process receives a priority.
Example:
P1 → Priority 3 P2 → Priority 1 P3 → Priority 2
If a smaller number means higher priority:
P2 → P3 → P1
Priority scheduling can be either:
- Preemptive
- Non-preemptive
4. Round Robin
Round Robin is designed for time-sharing systems.
Each process receives a fixed 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
It is preemptive.
Context Switching
When the CPU switches from one process to another, the OS performs a context switch.
Example:
P1 running ↓ Save P1 state ↓ Load P2 state ↓ P2 running
The OS stores information such as:
- Program counter
- CPU registers
- Process state
- Other scheduling/context information
The saved information is associated with the process's PCB.
Context Switch Overhead
Context switching takes time.
During a context switch:
CPU ↓ Save old process state ↓ Load new process state ↓ Resume new process
The CPU is doing management work rather than useful application work.
Therefore:
Too many context switches can reduce performance.
Dispatcher
The dispatcher transfers CPU control to the process selected by the scheduler.
Ready Queue ↓ Scheduler ↓ Select P2 ↓ Dispatcher ↓ Context Switch ↓ CPU ↓ P2 Running
Scheduling Example
Suppose we have:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 2 |
If we use simple FCFS:
0 5 8 10 |-------|-------|-------| P1 P2 P3
P1
Arrival = 0
Completion = 5
Turnaround = 5 − 0 = 5 Waiting = 0
P2
Arrival = 1
Completion = 8
Turnaround = 8 − 1 = 7 Waiting = 7 − 3 = 4
P3
Arrival = 2
Completion = 10
Turnaround = 10 − 2 = 8 Waiting = 8 − 2 = 6
This type of calculation is very important for OS exams.
Important Scheduling Problems
A good scheduling algorithm tries to avoid:
Starvation
A process waits for a very long time because other processes keep getting selected.
P1 → P2 → P3 → P1 → P2 → P3 ... ↓ P4 still waiting
Convoy Effect
A long process can make many short processes wait behind it, especially under FCFS.
Long Process ↓ P1 ──────────────── P2 → waiting P3 → waiting P4 → waiting
Excessive Context Switching
Too many switches can waste CPU time.
Process Scheduling vs CPU Scheduling
These terms are closely related but can be used with slightly different scope.
Process Scheduling
Broader concept of deciding how processes are admitted, suspended, resumed, and selected for execution.
CPU Scheduling
Specifically focuses on:
Selecting a ready process to receive the CPU.
In many OS courses, "process scheduling" and "CPU scheduling" are discussed together, with CPU scheduling algorithms such as FCFS, SJF, Priority, and Round Robin.
Complete Process Scheduling Flow
New Processes | ↓ Long-Term Scheduler | ↓ Ready Queue | ↓ Short-Term Scheduler | ↓ Dispatcher | ↓ CPU | +------+------+ | | I/O Wait Finish | | ↓ ↓ Waiting Terminated | ↓ Ready Queue
Quick Comparison
| Concept | Meaning |
|---|---|
| Scheduler | Selects which process should run |
| Dispatcher | Gives CPU to selected process |
| Ready Queue | Processes waiting for CPU |
| Preemptive | OS can take CPU from running process |
| Non-preemptive | Process keeps CPU until it blocks/finishes |
| CPU Burst | Time executing on CPU |
| I/O Burst | Time waiting/performing I/O |
| Context Switch | Switching CPU from one process to another |
| Waiting Time | Time waiting in ready queue |
| Turnaround Time | Arrival to completion |
| Response Time | Arrival to first CPU response |
| Throughput | Processes completed per unit time |
🧠 Easy Memory Trick
Scheduling = "Who gets the CPU next?"
READY ↓ SCHEDULER ↓ SELECT PROCESS ↓ DISPATCH ↓ CPU ↓ RUN ↓ FINISH / WAIT
Most important points for exams
- Process scheduling selects processes for CPU execution.
- Ready Queue contains processes waiting for CPU.
- Short-term scheduler selects the next process for CPU.
- Dispatcher transfers CPU control to the selected process.
- Preemptive scheduling can interrupt a running process.
- Non-preemptive scheduling does not forcibly remove the CPU.
- Important criteria: CPU utilization, throughput, turnaround time, waiting time, response time, fairness.
- Context switching introduces overhead.
- Important algorithms: FCFS, SJF, SRTF, Priority, Round Robin, Multilevel Queue, and Multilevel Feedback Queue.