CPU Scheduling: Algorithms and Concepts
Introduction to CPU Scheduling
CPU scheduling is a fundamental concept in operating systems that determines which process gets access to the CPU when multiple processes are ready to execute. The primary goals of CPU scheduling are to maximize CPU utilization, maximize throughput (number of processes completed per time unit), minimize turnaround time (time from submission to completion), minimize waiting time (time spent waiting in the ready queue), and minimize response time (time from submission to first response).
In multiprogramming environments, the operating system must make decisions about which process to run at any given moment. These decisions are made by the CPU scheduler, which is part of the operating system's process management component. The scheduler selects a process from the ready queue and allocates the CPU to it.
CPU scheduling becomes especially important because the CPU is one of the most important and expensive resources in a computer system. Efficient scheduling ensures that this resource is utilized effectively while providing good performance for all processes.
The scheduling algorithm must consider various factors such as process priority, estimated execution time, and arrival time to make optimal decisions. Different algorithms have different strengths and weaknesses, making them suitable for different scenarios.
Types of CPU Scheduling
Preemptive Scheduling
In preemptive scheduling, the operating system can interrupt a currently running process and switch to another process. This allows the system to respond promptly to important tasks but requires more complex logic to manage context switching. Preemptive scheduling is used in most modern operating systems because it improves system responsiveness and allows for fair resource allocation.
Examples of preemptive scheduling include Round Robin and Multilevel Feedback Queue scheduling.
Non-Preemptive Scheduling
In non-preemptive scheduling, once a process starts executing, it continues until it finishes or voluntarily gives up the CPU (for example, when waiting for I/O). This approach is simpler to implement but may lead to poor system responsiveness, especially when time-critical tasks need to be executed.
Examples of non-preemptive scheduling include First-Come, First-Served and Shortest Job First (when implemented non-preemptively).
Scheduling Criteria
Different CPU scheduling algorithms have different performance characteristics. To compare them, we use several criteria:
- CPU Utilization: We want to keep the CPU as busy as possible. In a real system, CPU utilization should range from 40% (for a lightly loaded system) to 90% (for a heavily used system).
- Throughput: The number of processes completed per time unit. It varies from process to process, but long processes affect throughput more than short processes.
- Turnaround Time: The interval from the time of submission of a process to the time of its completion. This is the sum of periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
- Waiting Time: The sum of the periods spent waiting in the ready queue. This metric excludes time spent executing or waiting for I/O.
- Response Time: The time from the submission of a request until the first response is produced. This is important for interactive systems where users expect quick responses.
- Fairness: Giving each process an equal share of the CPU time. While fairness is important, it may conflict with other efficiency goals.
Often, these criteria conflict with each other. For example, minimizing average waiting time might increase the waiting time of some processes. The choice of scheduling algorithm depends on which criteria are most important for the specific system and workload.
First-Come, First-Served (FCFS) Scheduling
The First-Come, First-Served (FCFS) scheduling algorithm is the simplest CPU scheduling algorithm. As the name suggests, the process that requests the CPU first gets the CPU first. The implementation of the FCFS policy is easily managed with a FIFO (First-In-First-Out) queue.
How FCFS Works
When a process enters the ready queue, its PCB (Process Control Block) is linked to the tail of the queue. When the CPU becomes free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. The FCFS scheduling is non-preemptive, meaning that once the CPU has been allocated to a process, that process keeps the CPU until it releases it, either by terminating or by requesting I/O.
Example of FCFS Scheduling
Consider the following set of processes that arrive at time 0 with the indicated burst times:
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
If we use FCFS scheduling, the Gantt chart is:
0 24 27 30
Let's calculate the waiting time for each process:
- P1: 0 ms (first process, no wait)
- P2: 24 ms (wait for P1 to complete)
- P3: 27 ms (wait for P1 and P2 to complete)
The average waiting time is (0 + 24 + 27) / 3 = 17 ms.
Advantages and Disadvantages of FCFS
Advantages:
- Simple to implement and understand
- No starvation - every process gets a chance to run
- Easy to calculate performance metrics
Disadvantages:
- Convoy effect - when a long process holds the CPU, shorter processes must wait
- Poor average waiting time, especially when a long job arrives before several short jobs
- Not suitable for time-sharing systems
Shortest Job First (SJF) Scheduling
The Shortest Job First (SJF) scheduling algorithm associates with each process the length of the process's next CPU burst. When the CPU is available, it is assigned to the process with the smallest next CPU burst. If two processes have the same length, FCFS is used to break the tie.
How SJF Works
The SJF algorithm can be either preemptive or non-preemptive. When a new process arrives with a shorter CPU burst than the current process's remaining burst, the CPU is preempted. This preemptive version is called Shortest Remaining Time First (SRTF).
Example of SJF Scheduling
Consider the following set of processes:
| Process | Burst Time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
Using SJF, we would arrange the processes in order of burst time: P4, P1, P3, P2.
0 3 9 16 24
The waiting time is:
- P1: 3 ms
- P2: 16 ms
- P3: 9 ms
- P4: 0 ms
The average waiting time is (3 + 16 + 9 + 0) / 4 = 7 ms.
Advantages and Disadvantages of SJF
Advantages:
- Gives minimum average waiting time for a given set of processes
- Provably optimal for minimizing average waiting time
Disadvantages:
- Requires knowing the length of the next CPU request, which is difficult to predict accurately
- Can lead to starvation - long processes may wait indefinitely if shorter processes keep arriving
- Not suitable for interactive systems
Predicting Burst Times
Since we usually can't know the length of the next CPU burst, SJF is often implemented by predicting the next burst time based on previous bursts. A common prediction technique is exponential averaging:
n+1 = tn + (1-)n
Where:
- n+1 = predicted next burst time
- tn = actual burst time of the nth process
- n = predicted burst time for the nth process
- = a weighting factor (0 1)
A higher gives more weight to recent history, while a lower gives more weight to past history.
Priority Scheduling
Priority scheduling is a scheduling algorithm where each process is assigned a priority, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order.
How Priority Scheduling Works
Priority scheduling can be either preemptive or non-preemptive. When a higher priority process arrives, a preemptive priority scheduling algorithm will preempt the currently running lower priority process. In non-preemptive priority scheduling, the newly arrived process with higher priority is placed at the head of the ready queue.
Example of Priority Scheduling
Consider the following set of processes:
| Process | Burst Time | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 2 |
| P4 | 1 | 4 |
| P5 | 5 | 2 |
Higher numbers represent higher priority in this example.
Assuming all processes arrive at time 0 and we're using non-preemptive priority scheduling, the Gantt chart would be:
0 1 11 13 18 19
The waiting time is:
- P1: 1 ms
- P2: 18 ms
- P3: 11 ms
- P4: 0 ms
- P5: 13 ms
The average waiting time is (1 + 18 + 11 + 0 + 13) / 5 = 8.6 ms.
Problem with Priority Scheduling: Starvation
A major problem with priority scheduling is the potential for indefinite blocking or starvation. Low-priority processes may never execute if the system has a continuous supply of higher-priority processes. This can be addressed by aging, which gradually increases the priority of processes that wait a long time in the ready queue.
Round Robin Scheduling
Round Robin (RR) scheduling is designed for time-sharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a time quantum or time slice, is defined. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to one time quantum.
How Round Robin Works
The process starts at the front of the ready queue, executes for at most one time quantum. If the process still needs more CPU time at the end of its time quantum, it is preempted and placed at the end of the ready queue. If the process finishes before its time quantum expires, it releases the CPU voluntarily, and the scheduler proceeds to the next process in the ready queue.
Example of Round Robin Scheduling
Consider the following set of processes:
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
With a time quantum of 4 ms:
0 4 7 10 14 18 22 26 30
The waiting time is:
- P1: 6 ms
- P2: 4 ms
- P3: 7 ms
The average waiting time is (6 + 4 + 7) / 3 = 5.67 ms.
Choosing the Time Quantum
The performance of RR scheduling heavily depends on the size of the time quantum:
- If the time quantum is too large, RR degenerates to FCFS scheduling
- If the time quantum is too small, the overhead from context switching becomes significant
- An optimal time quantum is typically chosen to be around 10-100ms, depending on the system's characteristics
Advantages and Disadvantages of Round Robin
Advantages:
- Fair distribution of CPU time among processes
- No starvation - every process gets a time slice
- Good for time-sharing and interactive systems
- Response time is predictable (at most one time quantum)
Disadvantages:
- High context switching overhead if quantum is too small
- May not be efficient for systems with processes of varying CPU burst times
- Lower throughput compared to SJF for systems with many long processes
Multilevel Queue Scheduling
Multilevel queue scheduling allows processes to be divided into separate queues. Each queue might have its own scheduling algorithm. For example, we might use RR scheduling for interactive processes and FCFS for batch processes. The queues themselves have priorities, and the scheduler schedules the highest-priority queue first.
How Multilevel Queue Works
Processes are permanently assigned to one queue based on some property like memory size, process priority, or process type. Each queue has absolute priority over lower-priority queues. No process in a lower-priority queue can run until all processes in higher-priority queues are finished.
Example of Multilevel Queue
A typical multilevel queue scheduler might have:
- System processes - highest priority, FCFS scheduling
- Interactive processes - high priority, RR scheduling
- Interactive editing processes - medium priority, RR scheduling with a longer time quantum
- Batch processes - low priority, FCFS scheduling
- Student processes - lowest priority, FCFS scheduling
Advantages and Disadvantages of Multilevel Queue
Advantages:
- Separates processes with different characteristics
- Can use different scheduling algorithms for different queues
- Ensures that important processes get preference
Disadvantages:
- Fixed partitioning may lead to inflexibility
- Starvation can occur for processes in lower-priority queues
- Not suitable for processes that change their behavior dynamically
Multilevel Feedback Queue Scheduling
Multilevel feedback queue scheduling is an extension of multilevel queue scheduling that allows processes to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts.
How Multilevel Feedback Queue Works
If a process uses too much CPU time, it will be moved to a lower-priority queue. This scheme leaves I/O-bound and interactive processes in the higher-priority queues. If a process waits too long in a lower-priority queue, it may be moved to a higher-priority queue (aging). This form of aging prevents starvation.
Parameters of Multilevel Feedback Queue
A multilevel feedback queue scheduler is defined by the following parameters:
- Number of queues
- Scheduling algorithm for each queue
- Method used to determine when to upgrade a process to a higher-priority queue
- Method used to determine when to demote a process to a lower-priority queue
- Method used to determine which queue a process will enter when it needs service
Example of Multilevel Feedback Queue
Consider a system with three queues:
- Queue 1: RR with time quantum = 8
- Queue 2: RR with time quantum = 16
- Queue 3: FCFS
A new job enters queue 1. When it gets CPU, it receives 8ms. If it does not finish in 8ms, it is moved to queue 2. At queue 2, it receives 16ms. If it still does not complete, it is moved to queue 3, where it is served in FCFS order.
Advantages and Disadvantages of Multilevel Feedback Queue
Advantages:
- More flexible than fixed-priority multilevel queue scheduling
- Gives preference to short processes
- Aging can be implemented to prevent starvation
- Adapts to different types of processes
Disadvantages:
- Complex to implement
- Difficult to tune parameters for optimal performance
- May require significant computational overhead to manage queue movements
Comparison of Scheduling Algorithms
| Algorithm | Preemptive | Throughput | Response Time | Waiting Time | Overhead | Best For |
|---|---|---|---|---|---|---|
| FCFS | No | Low | Poor | High | Low | Simple batch systems |
| SJF | Can be | High | Good | Low | Moderate | Processes with known burst times |
| Priority | Can be | Variable | Variable | Variable | Moderate | Systems with process priorities |
| Round Robin | Yes | Moderate | Excellent | Moderate | High | Time-sharing systems |
| Multilevel Queue | Variable | Variable | Good | Variable | High | Systems with distinct process types |
| Multilevel Feedback | Yes | High | Excellent | Low | Very High | General-purpose systems |
Selecting the Appropriate Algorithm
The choice of CPU scheduling algorithm depends on the specific requirements of the system:
- For batch systems where throughput is important, SJF or its variants work well
- For interactive systems where response time is critical, Round Robin is preferred
- For real-time systems, priority-based algorithms with appropriate mechanisms to meet deadlines are necessary
- For general-purpose systems, multilevel feedback queue scheduling offers a good balance between different requirements
