CPU Scheduling Fundamentals
CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes, the operating system can make the computer more productive.
In a single-processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.
The CPU-I/O Burst Cycle
The success of CPU scheduling depends on an observed property of processes: process execution consists of a cycle of CPU execution and I/O wait.
Processes alternate between these two states. Execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution.
Preemptive vs Non-Preemptive Scheduling
CPU-scheduling decisions may take place under the following four circumstances:
- 1. When a process switches from the running state to the waiting state (e.g., an I/O request).
- 2. When a process switches from the running state to the ready state (e.g., an interrupt occurs).
- 3. When a process switches from the waiting state to the ready state (e.g., completion of I/O).
- 4. When a process terminates.
When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is non-preemptive. Otherwise, it is preemptive.
| Non-Preemptive Scheduling | Preemptive Scheduling |
|---|---|
| Once the CPU is allocated to a process, it keeps it until it releases it by terminating or switching to the waiting state. | The OS can interrupt and suspend the currently running process to allocate the CPU to another process. |
| Does not require special hardware (like a timer) for preemptive interrupts. | Requires a hardware timer to generate interrupts. |
| Can lead to starvation if a process has a very long CPU burst. | Prevents a single process from monopolizing the CPU. |
The Dispatcher
Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler.
This function involves switching context, switching to user mode, and jumping to the proper location in the user program to restart that program.
The time it takes for the dispatcher to stop one process and start another running is known as dispatch latency.
Scheduling Criteria
Different CPU-scheduling algorithms have different properties, and the choice of a particular algorithm may favor one class of processes over another. Many criteria have been suggested for comparing CPU scheduling algorithms:
- CPU Utilization: Keeping the CPU as busy as possible.
- Throughput: The number of processes that are completed per time unit.
- Turnaround Time: The interval from the time of submission of a process to the time of completion.
- Waiting Time: The sum of the periods spent waiting in the ready queue.
- Response Time: The time from the submission of a request until the first response is produced.
Sort the Concepts
Sort the following characteristics into Preemptive or Non-Preemptive Scheduling.