3.1 Scheduling Concepts & Criteria
CPU scheduling is the foundation of multiprogrammed operating systems. By switching the processor core among ready processes, the OS maximizes CPU utilization and computational throughput. The short-term scheduler (CPU scheduler) relies on standardized metrics to evaluate and balance scheduling decisions.
Figure 3.1: Relationship between process arrival, queue wait, CPU burst execution, turnaround, and initial response time.
Key Scheduling Metrics Matrix
| Metric | Definition | Optimization Target |
|---|---|---|
| CPU Utilization | Percentage of time the CPU core is performing useful work (typically 40% to 90%). | ▲ Maximize |
| Throughput | Total number of processes completed per unit time. | ▲ Maximize |
| Turnaround Time (TAT) | Total elapsed time from submission to complete process termination. | ▼ Minimize |
| Waiting Time (WT) | Sum of all time spent sitting in the Ready queue waiting for CPU allocation. | ▼ Minimize |
| Response Time (RT) | Time from request submission to the generation of the very first output or response. | ▼ Minimize |
Percentage of time the CPU core is performing useful work (typically 40% to 90%).
Total number of processes completed per unit time.
Total elapsed time from submission to complete process termination.
Sum of all time spent sitting in the Ready queue waiting for CPU allocation.
Time from request submission to the generation of the very first output or response.
3.2 Scheduling Algorithms
Different CPU scheduling algorithms optimize for different system criteria. Understanding their mechanics, Gantt chart representation, and edge-case behavior is a core university and placement interview requirement.
Figure 3.2: FCFS causes long waits when short jobs follow a long job; SJF achieves minimal average waiting time; Round Robin provides fair interactive response.
Algorithm Comparisons
- First-Come, First-Served (FCFS): Non-preemptive. Simple FIFO queue. Suffer from the Convoy Effect: all subsequent short I/O-bound processes get stuck behind a single long CPU-bound process.
- Shortest Job First (SJF): Assigns the CPU to the process with the shortest CPU burst. Provably optimal for minimizing average waiting time.
- Non-Preemptive SJF: Once the CPU is allocated, it cannot be interrupted until the burst completes.
- Preemptive SJF (Shortest Remaining Time First - SRTF): If a newly arrived process has a remaining burst shorter than the currently executing process, the CPU is preempted.
- Weakness: Causes starvation of long jobs if short jobs arrive continuously.
- Priority Scheduling: CPU is given to the process with the highest priority integer. Can suffer from starvation, resolved via Aging (gradually boosting priority the longer a process waits in the queue).
- Round Robin (RR): Preemptive time-sharing scheduler. Allocates a small CPU slice (time quantum $q$, usually 10ā100ms). If $q$ is too small, context-switch overhead dominates; if $q$ is too large, RR degenerates into FCFS.
3.3 Multilevel Queue Scheduling
In modern computer systems, processes have vastly different response time requirements. For instance, interactive foreground desktop applications need immediate response, while background batch compilations prioritize throughput. Multilevel Queue Scheduling partitions the ready queue into multiple distinct queues categorized by process type.
Figure 3.3: In a multilevel queue, each priority level is a separate queue with its own internal scheduling policy. Higher queues preempt lower ones.
Multilevel Feedback Queue (MLFQ)
In a standard multilevel queue, processes are permanently assigned to one queue upon arrival and cannot move. This lack of flexibility can starve lower queues if interactive tasks keep arriving.
A Multilevel Feedback Queue (MLFQ) solves this by allowing processes to dynamically migrate between queues:
- New processes enter the highest-priority queue (Queue 0) with a small quantum (e.g. 8ms).
- If a process finishes its burst within 8ms, it leaves. If it consumes its full quantum without relinquishing the CPU, it is demoted to Queue 1 (quantum = 16ms).
- If it again consumes its 16ms quantum, it is demoted to Queue 2 (FCFS).
- Aging Mechanism: Processes waiting too long in lower queues are promoted back up to prevent starvation.
MLFQ is considered the most versatile general-purpose scheduling design because it automatically rewards short interactive tasks without requiring prior knowledge of burst lengths.
