Scheduling Policies Overview
An operating system relies on scheduling policies to determine which process in the ready queue should be given control of the CPU next. Because no single algorithm is perfect for every scenario, many different scheduling algorithms have been developed, each optimized for different types of workloads and goals.
Common Scheduling Algorithms
Here is a high-level look at the most commonly used scheduling policies. We will explore each of these in greater detail in the upcoming lessons:
- First-Come, First-Served (FCFS): The simplest scheduling algorithm. The process that requests the CPU first is allocated the CPU first.
- Shortest-Job-First (SJF): The CPU is assigned to the process that has the smallest next CPU burst. It can be preemptive or non-preemptive.
- Shortest-Remaining-Time-First (SRTF): The preemptive version of SJF. If a new process arrives with a shorter burst than what is left of the currently executing process, the CPU is preempted.
- Priority Scheduling: A priority is associated with each process, and the CPU is allocated to the process with the highest priority.
- Round Robin (RR): Designed especially for time-sharing systems. Each process gets a small unit of CPU time (time quantum). After this time has elapsed, the process is preempted and added to the end of the ready queue.
- Multilevel Queue Scheduling: Partitions the ready queue into several separate queues based on process properties (e.g., system processes vs user processes), each with its own scheduling algorithm.
Important Terminology
| Term | Definition |
|---|---|
| Starvation | A situation where a low-priority process is continuously bypassed and never gets CPU time. |
| Aging | A technique used to prevent starvation by gradually increasing the priority of processes that have been waiting in the system for a long time. |
| Time Quantum (Time Slice) | A small, fixed amount of CPU time given to each process in Round Robin scheduling. |
| Convoy Effect | A phenomenon in FCFS where many short processes wait behind a single long process, leading to poor CPU and device utilization. |
Choosing the Right Policy
The choice of scheduling policy heavily depends on the system's objectives. Interactive systems (like your personal computer) often prioritize Round Robin to ensure that no single application freezes the system, providing fair and fast response times to all active programs.
Conversely, batch processing systems might prefer Shortest-Job-First to simply maximize the total number of jobs completed per hour, ignoring response time fairness.