1. Introduction
CPU scheduling is one of the most important functions of an operating system. It is the mechanism by which the operating system decides which process in the ready queue should be allocated the CPU next.
Since the CPU is one of the most critical and limited system resources, multiple processes often compete for CPU time. The operating system must therefore make intelligent scheduling decisions to ensure efficient resource utilization and good overall system performance.
CPU scheduling directly affects:
System responsiveness
Throughput
CPU utilization
Waiting time
Fairness
User experience
In modern multiprogramming systems, many processes may reside in memory simultaneously. However, only one process can execute on a CPU core at any given instant.
The primary responsibility of CPU scheduling is:
To determine which ready process should execute next and for how long.
Because scheduling decisions occur continuously throughout system operation, CPU scheduling forms the foundation of:
Multitasking
Time-sharing systems
Interactive computing
Concurrent execution
Without CPU scheduling:
Multiple processes could not share the CPU efficiently
Modern operating systems would not support multitasking
2. Fundamental Idea
At any given moment in a multiprogramming system:
Several processes are ready to execute
Only one process can use a CPU core
Multiple processes compete for CPU time
Consider the following situation:
Ready Queue
P1
P2
P3
P4
All four processes are prepared to execute.
However:
CPU
Only One Process
The operating system must choose one process and delay the others.
This decision-making process is called:
CPU Scheduling
The scheduler must determine:
Which process should run next
How long it should run
Whether another process should be given priority
Thus CPU scheduling can be viewed as:
A resource allocation problem in which multiple processes compete for access to the CPU.
Why Scheduling Is Necessary
Suppose scheduling did not exist.
Possible problems:
Some processes might never execute
CPU utilization could become inefficient
Interactive programs would become unresponsive
Resource sharing would be unfair
CPU scheduling solves these issues by implementing systematic decision-making policies.
3. Basic Scheduling Model
The overall scheduling process can be represented using the following conceptual model:
Processes
↓
Ready Queue
↓
CPU Scheduler
↓
Dispatcher
↓
CPU
↓
Execution
The operating system continuously repeats this cycle throughout system operation.
High-Level Flow
Step 1
Processes enter the Ready Queue.
Step 2
CPU Scheduler selects a process.
Step 3
Dispatcher performs CPU allocation.
Step 4
Selected process begins execution.
Step 5
When execution conditions change:
Process blocks
Process terminates
Time slice expires
the scheduling cycle repeats.
4. Key Components
Several operating system components participate in CPU scheduling.
4.1 Ready Queue
The Ready Queue contains all processes that:
Are ready to execute
Have all required resources
Are waiting for CPU allocation
These processes are not blocked and can execute immediately if selected.
Example:
Ready Queue
P1
P2
P3
P4
The scheduler chooses one of these processes.
Implementation of Ready Queue
Different scheduling algorithms require different queue structures.
Examples include:
FIFO Queue
Processes ordered by arrival time.
P1 → P2 → P3 → P4
Priority Queue
Processes ordered by priority.
High Priority
↓
P3 → P1 → P4 → P2
Other Structures
Depending on scheduling policy:
Circular queues
Multilevel queues
Balanced trees
Heap-based structures
may be used.
4.2 CPU Scheduler
The CPU Scheduler is the operating system component responsible for selecting the next process to execute.
The scheduler performs:
Decision Making
Its responsibilities include:
Examining ready processes
Applying scheduling policies
Selecting the most appropriate process
The scheduler itself does not perform execution.
Instead, it determines:
Who should run next
Examples of scheduling algorithms include:
First Come First Serve (FCFS)
Shortest Job First (SJF)
Round Robin (RR)
Priority Scheduling
These algorithms will be studied in later sections.
4.3 Dispatcher
The Dispatcher performs the actual CPU allocation.
While the scheduler decides:
Which process should run
the dispatcher performs the physical transition.
Responsibilities include:
Context Switching
Saving current process state and restoring another.
Switching to User Mode
Transitioning from kernel mode to user mode.
Jumping to Correct Instruction
Loading the process's Program Counter.
Conceptually:
Scheduler Selects P2
↓
Dispatcher Activates P2
↓
CPU Executes P2
The dispatcher acts as the bridge between scheduling decisions and actual execution.
4.4 Context Switch (Link to Previous Topic)
Context switching is closely related to CPU scheduling.
Whenever the scheduler selects a different process:
Current process state saved
New process state restored
CPU execution transferred
Example:
Process A
↓
Context Switch
↓
Process B
The PCB stores the information needed for this operation.
Context switching introduces overhead because:
CPU performs administrative work
No useful application computation occurs during switching
Therefore:
Efficient scheduling aims to minimize unnecessary context switches.
5. When Does Scheduling Occur?
The operating system performs scheduling decisions only during specific events.
These events are known as:
Scheduling Points
5.1 Running → Waiting
Occurs when a process requests:
Disk I/O
Network access
User input
Example:
Running
↓
Waiting
The CPU becomes available.
The scheduler selects another process.
5.2 Running → Ready
Occurs when:
Time quantum expires
Process is preempted
Example:
Running
↓
Ready
The scheduler may choose another process.
This transition is common in:
Round Robin Scheduling
5.3 Waiting → Ready
Occurs when:
I/O operation completes
Event finishes
Example:
Waiting
↓
Ready
The process becomes eligible for execution again.
The scheduler may reevaluate CPU allocation.
5.4 Process Termination
Occurs when:
Process finishes execution
Example:
Running
↓
Terminated
The CPU becomes free.
The scheduler must select another ready process.
6. Types of Scheduling (Conceptual)
Scheduling policies can be broadly categorized into two major classes.
6.1 Non-Preemptive Scheduling
In Non-Preemptive Scheduling:
Once a process receives the CPU, it keeps it until completion or blocking.
The operating system cannot forcibly remove the process.
CPU released only when:
Process completes
Process performs I/O
Process blocks
Example:
P1 Executes Completely
↓
P2 Executes
↓
P3 Executes
Advantages
Simple implementation
Low overhead
Disadvantages
Poor responsiveness
Long waiting times
6.2 Preemptive Scheduling
In Preemptive Scheduling:
The operating system may interrupt a running process.
The scheduler can reassign the CPU dynamically.
Example:
P1
↓
Interrupted
↓
P2
↓
P3
This approach is used by most modern operating systems.
Advantages
Better responsiveness
Fair CPU sharing
Suitable for interactive systems
Disadvantages
More context-switch overhead
Greater complexity
7. Scheduling as Resource Allocation
CPU scheduling can be viewed as a resource allocation problem.
The CPU is:
A critical and limited resource
Many processes compete for access simultaneously.
The operating system must allocate CPU time in a manner that balances:
Performance
Fairness
Responsiveness
Conceptually:
Processes
↓
Compete for CPU
↓
Scheduler Allocates CPU
Thus scheduling is fundamentally:
Resource management under constraints.
8. Objectives of Scheduling
A scheduling algorithm should achieve several goals simultaneously.
Maximize CPU Utilization
Keep CPU busy as much as possible.
Goal:
CPU Idle Time → Minimum
Minimize Waiting Time
Reduce time spent in Ready Queue.
Goal:
Ready Queue Delay → Minimum
Minimize Response Time
Important for interactive systems.
Users expect:
Immediate feedback
Quick responses
Maximize Throughput
Throughput measures:
Number of processes completed per unit time
Higher throughput indicates better performance.
Ensure Fairness
All processes should receive reasonable CPU access.
Avoid:
Starvation
Resource monopolization
These objectives often conflict with one another, requiring careful design of scheduling algorithms.
9. Conceptual Timeline
CPU scheduling allows multiple processes to share execution time.
Example timeline:
Time →
P1: ███ ███
P2: ███ ███
P3: ███ ███
Each block represents:
CPU execution interval
Between intervals:
Scheduler makes decisions
Context switches occur
This sharing creates the illusion that all processes execute simultaneously.
Relationship with Previous Topics
CPU scheduling directly builds upon several concepts already studied.
Process States
Scheduler moves processes between:
Ready
Running
Waiting
states.
PCB
Scheduler uses PCB information such as:
Priority
State
CPU usage
for decision making.
Context Switching
Scheduler decisions trigger context switches.
Process Creation
Newly created processes eventually enter:
New → Ready Queue
and become candidates for scheduling.