4 CPU Scheduling

What the scheduler chooses

CPU scheduling is the operating system’s method for choosing which ready thread runs on a processor next. A thread can become ready when it is created or when it finishes waiting for an event such as input/output (I/O). If a running thread blocks, the scheduler can give the processor to another ready thread.

In a preemptive system, the operating system can also interrupt a running thread and switch to another one. This supports time-sharing and responsiveness.

Scheduling goals and trade-offs

Scheduling policies pursue several goals, and no single policy is best for every workload. Common measures and aims include:

• CPU utilization: Keep processors busy when runnable work exists.

• Throughput: Complete more jobs per unit of time.

• Turnaround time: Minimize the time from a job’s arrival to its completion: $\text{completion time} - \text{arrival time}$.

• Response time: Minimize the time from arrival until the job first gets CPU time; this matters for interactive applications.

• Fairness: Give runnable tasks a reasonable share of CPU time and avoid starvation, or indefinite postponement.

• Predictability and deadlines: Meet timing requirements in systems where late work may be less useful.

• Low overhead: Avoid spending too much processor time switching between tasks and managing queues.

These goals can conflict. A policy that quickly finishes short jobs may delay long jobs. Frequent sharing can improve responsiveness but increase completion times and switching overhead.

Scheduling by job length

First Come, First Served

First Come, First Served (FCFS), also called First In, First Out (FIFO), runs ready jobs in arrival order, typically until a job blocks or finishes. It is simple, but a long job at the front can delay many short jobs; this is the convoy effect.

For jobs arriving in order with CPU bursts of $10$, $2$, and $1$ time units, FCFS produces turnaround times of $10$, $12$, and $13$ time units, averaging about $11.7$ time units.

Shortest Job First

Shortest Job First (SJF) runs the job with the shortest expected CPU burst first. When all jobs are available together and their burst lengths are known, SJF can reduce average turnaround time. Future job lengths are not usually known exactly in practice, so an operating system must estimate them or use another policy. Non-preemptive SJF does not interrupt a job that has already started.

For the same jobs, SJF runs the $1$-unit and $2$-unit jobs before the $10$-unit job. Their turnaround times are $1$, $3$, and $13$ time units, averaging about $5.7$ time units. This improvement makes the longest job wait longer.

Shortest Remaining Time First

Shortest Remaining Time First (SRTF) is the preemptive version of SJF. Whenever a new job becomes ready, the scheduler compares its expected CPU time with the running job’s remaining time, then runs the job with the shortest remaining time. SRTF can improve turnaround when short jobs arrive while longer work is running, but it relies on estimates and can starve long jobs if short work keeps arriving.

Round Robin and switching costs

Round Robin (RR) gives each ready thread a short interval called a time quantum. If the thread has not finished when its interval ends, the scheduler moves it to the back of the ready queue. Repeated rotation gives tasks regular opportunities to run and generally supports responsive time-sharing.

The quantum involves a trade-off. A shorter quantum can improve first response but causes more context switches. A longer quantum reduces switching overhead but makes the system feel less responsive. Context switches also have indirect costs, including disruption to useful processor-cache state.

Priority, feedback, and fair-share policies

A priority scheduler chooses a task according to its priority; a higher-priority task may run before a lower-priority one. Priorities can help urgent or important work, but low-priority tasks may be postponed indefinitely. Aging reduces this risk by gradually raising the priority of tasks that have waited a long time.

A multilevel feedback queue (MLFQ) uses several queues with different priorities or time quanta. It moves tasks between queues based on their observed behavior. For example, tasks that frequently give up the CPU to wait for I/O can be favored for responsiveness, while tasks that use long CPU bursts may be placed in a lower-priority queue. This adapts scheduling to workloads without requiring exact job lengths, but the policy requires careful tuning.

Fair-share scheduling aims to distribute CPU time among runnable tasks, sometimes accounting for task weights or groups rather than treating every task equally. The Linux kernel’s newer EEVDF design considers a task’s fair share and a virtual deadline when selecting work.

Workloads and processor performance

Scheduling affects how quickly applications respond, how quickly jobs finish, how evenly CPU time is distributed, and how efficiently processors are used. When a task waits for I/O, running another ready task can keep the CPU productive. Frequent preemption and switching consume time, while long uninterrupted bursts can delay interactive work.

The workload influences which goals matter most. Interactive systems often prioritize short response times and fairness. Batch systems may emphasize throughput and turnaround. Real-time systems must meet timing requirements, so their policies may prioritize tasks with deadlines; a high-priority policy alone does not guarantee that every deadline will be met.

On multicore processors, the operating system must distribute runnable work among cores. Balancing work can improve utilization, while keeping a task on the same core when practical can help preserve useful processor state. Modern schedulers combine scheduling rules with workload estimates, priorities, and processor-level balancing rather than relying on one simple algorithm.

Putting the policies in context

CPU scheduling selects which ready thread runs and when. FCFS is simple but can delay short jobs; SJF and SRTF can improve turnaround when burst lengths can be estimated. Round Robin supports responsive time-sharing but trades off against switching overhead and completion time. Priority, feedback-queue, and fair-share policies address urgency, changing workloads, and equitable CPU access. A scheduler balances response time, throughput, turnaround, fairness, deadlines, and overhead for the system’s workload.