Scheduling
What is CPU Scheduling?
CPU scheduling is the process of allocating CPU time to tasks to optimise system performance.
It ensures fair execution, maximises CPU utilisation, and minimises waiting time for processes.
Different CPU Scheduling Approaches
| Approach | Description | Pros | Cons |
|---|---|---|---|
| First-Come, First-Served (FCFS) | Processes are executed in the order they arrive. | Simple, fair in a queue-based system. | Can cause long waiting times. |
| Round Robin (RR) | Each process gets an equal time slice before moving to the next. | Ensures fairness, prevents starvation. | High overhead due to frequent switching. |
| Multilevel Queue Scheduling | Processes are divided into priority-based queues. | Efficient for systems with different priority levels. | Low-priority tasks may suffer delays. |
| Priority Scheduling | Higher priority processes execute before lower priority ones. | Critical tasks get priority. | Starvation can occur if low-priority tasks are ignored. |
Scheduling Scenarios: Deep Dives
First-Come, First-Served (FCFS)
Definition: In First-Come, First-Served scheduling, processes are enqueued in the order they arrive and run to completion without preemption, ensuring that each task begins only after all earlier tasks have finished.
How it works: The scheduler maintains a simple FIFO queue. When the CPU becomes available, it dequeues the next process and allows it to run until it either completes or voluntarily blocks, resulting in context switches only at those points and minimal scheduling overhead.
Why it’s suitable: Its straightforward implementation and predictable turnaround times under light to moderate load make FCFS ideal for batch-oriented or uniform-length workloads.
Appropriate Scenarios:
- A university computer lab’s shared printer might use FCFS so that student print jobs are handled in exactly the order submitted, avoiding mid-print interruptions.
- A financial application might append transaction logs sequentially in FCFS order to preserve an exact chronology, simplifying auditing and disaster recovery.
Round Robin (RR)
Definition: Round Robin scheduling assigns each process a fixed time slice, or quantum, after which the process is preempted and returned to the back of the ready queue, guaranteeing fair CPU access.
How it works: The scheduler cycles through the ready queue in a circular manner. Each process executes for up to one quantum; if it still needs more CPU time, it is paused and re-enqueued, preventing any single task from monopolising resources.
Why it’s suitable: By capping the maximum CPU time per task, RR ensures low latency and responsiveness in interactive and time-sharing systems.
Appropriate Scenarios:
- A desktop operating system uses RR to interleave CPU bursts among a web browser, text editor, and media player so that user input remains responsive.
- A busy web server applies RR to serve concurrent HTTP requests, so no single heavy request can stall service for others.
Multilevel Queue Scheduling
Definition: Multilevel Queue scheduling divides processes into separate queues—such as real-time, interactive, and batch—each with its own scheduling policy and priority level.
How it works: Processes are permanently assigned to a queue based on their type or priority. The scheduler always selects tasks from the highest-priority nonempty queue, using FCFS, RR, or another algorithm within that queue.
Why it’s suitable: This structure guarantees that critical or time-sensitive jobs receive immediate attention, while lower-priority work utilises idle CPU cycles without interfering.
Appropriate Scenarios:
- In a telecommunications switch, voice packet processing runs in a high-priority queue to meet latency requirements, while bulk data transfers occupy a lower-priority queue and run when capacity allows.
- In a university compute cluster, faculty research jobs go in a top-priority queue, student assignments in mid-priority, and large data analyses in a low-priority queue to maximise resource use.
Priority Scheduling
Definition: Priority Scheduling assigns each process a numerical priority and always selects the highest-priority ready process for execution, with preemptive or non-preemptive variants dictating whether a running process can be interrupted.
How it works: The ready queue is ordered by priority. In preemptive mode, the arrival of a higher-priority process immediately triggers a context switch; in non-preemptive mode, the current process runs until completion or blocking.
Why it’s suitable: By ensuring that essential tasks run first, Priority Scheduling is ideal for systems with mixed criticality, though mechanisms like aging must be in place to prevent starvation of low-priority jobs.
Appropriate Scenarios:
- An automotive embedded system gives safety-critical functions, such as anti-lock braking control, the highest priority, preempting diagnostic routines that run only when the CPU is idle.
- In a hospital monitoring system, patient-vital-sign analysis processes have top priority to guarantee immediate alerting, while background data archiving and reporting occur at lower priority.
Why is Scheduling Important?
- Optimises Performance: Ensures efficient use of CPU resources.
- Improves User Experience: Ensures fast response times in multitasking systems.
- Prevents Starvation: Fair allocation prevents long delays for some processes.
Key Takeaways
- CPU scheduling optimises system performance by allocating CPU time efficiently.
- Common scheduling approaches include FCFS, Round Robin, Multilevel Queue, and Priority Scheduling.
- Each approach has strengths and weaknesses based on fairness, efficiency, and response time.
- Choosing the right scheduling algorithm is crucial for maintaining system performance.