4. CPU Scheduling and Resource Allocation

Introduction and Context

A multiprogrammed operating system rarely has only one runnable activity. Processes compete for processor time, memory, storage devices, network interfaces, locks, and other resources. The operating system must therefore decide not only which process should execute next, but also how resources should be distributed over time. These decisions strongly influence system performance, responsiveness, predictability, fairness, energy consumption, and user experience.

CPU scheduling is the policy and mechanism used to select a runnable thread or process for execution. Resource allocation is the broader activity of assigning limited system resources to competing demands. Although CPU scheduling is often studied independently, real systems coordinate processor allocation with memory management, I/O scheduling, synchronization, admission control, and power management. A scheduling policy that maximizes processor utilization may produce unacceptable interactive response, while one that guarantees deadlines may sacrifice throughput or fairness.

At postgraduate level, scheduling should therefore be understood as a decision problem involving competing objectives. The appropriate algorithm depends on workload characteristics, system architecture, service-level objectives (SLOs), and the cost of delay. Batch computing, interactive systems, cloud platforms, embedded controllers, and safety-critical systems require different interpretations of efficiency and fairness.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Explain the purpose, assumptions, and mechanisms of CPU scheduling.

2. Distinguish preemptive and non-preemptive scheduling.

3. Calculate and interpret response time, waiting time, turnaround time, throughput, utilization, fairness, and deadline-related measures.

4. Evaluate FCFS, SJF, SRTF, round-robin, priority, multilevel queue, multilevel feedback queue, fair-share, multicore, and real-time scheduling.

5. Analyze the interaction between scheduling and resource allocation.

6. Select scheduling strategies for batch, interactive, cloud, multicore, and real-time workloads.

7. Identify starvation, priority inversion, convoy effects, overload, and other scheduling risks.

8. Apply scheduling concepts to a realistic system-design scenario.

Scheduling as a Resource-Allocation Problem

A process alternates between CPU bursts and I/O bursts. During a CPU burst it requires processor service; during an I/O burst it is blocked and does not compete for the CPU. The ready queue contains processes that are eligible to run but are waiting for processor allocation. A context switch saves the state of the running thread and restores the state of another. Context switching enables multiprogramming but consumes time and may disturb cache and translation-lookaside-buffer locality.

A scheduler operates through three related functions. The long-term scheduler controls admission to the system, especially in batch environments. The medium-term scheduler may suspend and resume processes to manage memory pressure. The short-term scheduler selects the next runnable thread, often at every interrupt, system call, blocking event, or completion of a time slice. Modern operating systems commonly schedule threads rather than entire processes because threads are the units that independently execute and block.

A scheduling policy defines the selection rule; a dispatcher performs the transition to the selected task. Dispatch latency is the time required to stop one task, perform scheduling actions, and begin another. In real-time systems, dispatch latency is part of the timing analysis rather than merely an overhead.

Performance measures

Let arrival time be the instant a job enters the system, completion time the instant it finishes, and first-run time the instant it first receives CPU service.

• Turnaround time = completion time − arrival time.
• Waiting time is the time spent in the ready queue. For a single CPU-burst model, it is turnaround time − CPU-burst time.
• Response time = first-run time − arrival time.
• Throughput is the number of completed jobs per unit time.
• CPU utilization is the proportion of time the processor performs useful work.
• Slowdown, often used for batch analysis, compares a job’s turnaround time with its isolated execution time.
• Deadline miss ratio is the fraction of jobs that complete after their deadlines.

These measures can conflict. Shortest-job-first minimizes average waiting time under ideal assumptions, but a long job may wait indefinitely. Round-robin often improves response time, but excessive preemption reduces throughput. High utilization can be undesirable when it causes long queues and poor tail latency. Consequently, mean values are insufficient for interactive and service-oriented systems; percentile response times, such as the 95th or 99th percentile, are often more meaningful.

Classical Scheduling Algorithms

First-Come, First-Served

First-Come, First-Served (FCFS) is non-preemptive: the process that enters the ready queue first runs until it blocks or terminates. It is simple, predictable in ordering, and has low scheduling overhead. Its major weakness is the convoy effect. A long CPU-bound process can delay many short I/O-bound processes, causing poor response time and underuse of I/O devices.

FCFS may be reasonable for simple batch queues where fairness is interpreted as arrival order and response time is unimportant. It is generally unsuitable for interactive systems.

Shortest Job First and Shortest Remaining Time First

Shortest Job First (SJF) selects the ready process with the smallest expected CPU burst and is non-preemptive. If burst lengths are known accurately, it minimizes average waiting time for a set of independent jobs. In practice, burst lengths must be estimated, often using exponential averaging:

τ(n+1) = αt(n) + (1 − α)τ(n),

where t(n) is the most recent burst, τ(n) is the previous estimate, and α lies between 0 and 1.

Shortest Remaining Time First (SRTF) is the preemptive counterpart. A newly arrived job can preempt the current job if its remaining execution time is smaller. SRTF can reduce average waiting time, but it requires estimates, creates preemption overhead, and may starve long jobs when short jobs continue to arrive.

Round-Robin Scheduling

Round-robin (RR) assigns each runnable process a time quantum. When the quantum expires, the process is preempted and placed at the end of the ready queue. RR is particularly appropriate for time-sharing because every runnable process receives regular opportunities to execute.

Quantum size is critical. A quantum that is too large makes RR resemble FCFS and increases response time. A quantum that is too small improves interactivity but increases context-switch overhead and cache disruption. RR does not inherently distinguish urgent tasks from background work, and equal turns do not necessarily constitute fair service when processes have different CPU demands or priorities.

Priority Scheduling

Priority scheduling selects the highest-priority runnable task. It may be preemptive or non-preemptive, and priorities may be static or dynamically adjusted. A priority system can express business importance, deadlines, user expectations, or kernel requirements. However, low-priority tasks may starve. Aging addresses starvation by gradually increasing the priority of tasks that have waited for a long time.

Priority inversion occurs when a high-priority task waits for a lock held by a low-priority task while medium-priority tasks continue executing. Priority inheritance temporarily raises the lock holder’s priority; priority ceiling protocols impose a controlled ceiling on priorities when locks are acquired. These mechanisms are essential when scheduling interacts with synchronization.

Multilevel Queue and Multilevel Feedback Queue

A multilevel queue assigns processes to separate queues, such as foreground, background, system, and batch queues. Each queue may use a different algorithm, and fixed inter-queue priorities determine which queue receives service. This structure is efficient but inflexible if a process’s behavior changes.

A multilevel feedback queue (MLFQ) allows processes to move between queues. New or interactive tasks may initially receive high priority and short quanta. CPU-intensive tasks gradually move to lower-priority queues with longer quanta. A periodic priority boost prevents starvation. MLFQ attempts to approximate SJF without requiring exact burst lengths while preserving good response for interactive work. Its behavior depends heavily on queue rules, promotion criteria, quantum sizes, and boost intervals; poorly tuned parameters can be manipulated or can produce unstable performance.

Fairness, Proportional Allocation, and Service Objectives

Fairness is not synonymous with equal waiting time. A research process, a latency-sensitive web request, and a maintenance task may legitimately receive different shares. Fair-share scheduling allocates CPU according to users, groups, containers, or projects rather than merely individual processes. This prevents one user who launches many processes from obtaining an excessive share.

Proportional-share methods assign weights. If runnable tasks have weights 2, 1, and 1, an ideal long-run allocation gives approximately 50%, 25%, and 25% of CPU service, subject to overhead and availability. Linux’s Completely Fair Scheduler historically used virtual runtime to approximate weighted fairness; contemporary Linux scheduling continues to evolve, including policies designed for latency-sensitive and deadline-oriented tasks. Lottery scheduling and stride scheduling are alternative proportional-share approaches.

In cloud and enterprise systems, scheduling is often governed by SLOs: for example, a request may need a specified percentile latency, while a batch job may require a minimum daily completion volume. SLO-aware scheduling combines priorities, quotas, admission control, resource reservations, and telemetry. A scheduler should distinguish guaranteed service from best-effort service and should avoid promising more capacity than the platform can provide.

Multicore and NUMA Scheduling

On a multicore processor, scheduling determines both which task runs and on which core. Global scheduling uses a common run queue, whereas partitioned scheduling assigns tasks to particular cores. Hybrid approaches maintain per-core queues and periodically rebalance work.

Processor affinity can improve cache locality and reduce migration cost. Hard affinity restricts a task to specified CPUs; soft affinity expresses a preference. Load balancing must consider runnable-task counts, CPU utilization, cache warmth, hardware topology, and simultaneous multithreading. Moving a task to an idle core may improve immediate utilization but lose valuable cache state.

Non-uniform memory access (NUMA) systems make placement more complex. Memory access time depends on the socket or node containing the memory. A scheduler and memory manager should, where possible, place threads near their data and avoid unnecessary migration across NUMA nodes. Resource allocation therefore includes CPU cores, memory locality, bandwidth, and accelerators rather than processor time alone.

Synchronization also affects multicore scheduling. Lock contention, false sharing, and critical sections can make a nominally balanced workload perform poorly. Oversubscription—creating more runnable threads than hardware can efficiently support—may increase context switching and reduce cache locality. Effective design often combines a scheduler with controlled thread pools, work stealing, and application-level back-pressure.

Real-Time Scheduling

Real-time scheduling emphasizes temporal correctness. A hard real-time task that misses a deadline may cause system failure; in soft real-time systems, a late result is degraded but still useful. The central question is not simply how much work is completed, but whether required work completes before its deadline.

Rate Monotonic Scheduling (RMS) assigns higher priority to tasks with shorter periods. For independent periodic tasks with fixed priorities, RMS is a classic schedulability approach under stated assumptions. Earliest Deadline First (EDF) dynamically selects the task with the nearest absolute deadline and can provide high processor utilization under ideal single-processor assumptions. Neither method automatically solves practical issues such as blocking, interrupt interference, execution-time variation, cache effects, or overload.

Real-time analysis typically considers worst-case execution time, period, deadline, release jitter, blocking time, and context-switch cost. Priority inversion must be bounded. Under overload, a system needs a defined degradation policy, such as dropping optional work, reducing quality, or protecting critical tasks through admission control. A design that performs well on average but cannot bound worst-case behavior is not sufficient for hard real-time use.

Resource Allocation Beyond the CPU

CPU scheduling decisions can create or reveal resource-allocation problems. A process may hold a file lock while waiting for CPU time, or consume memory while blocked on I/O. The operating system must prevent deadlock, manage contention, and ensure that resource reservations do not produce unsafe commitments.

Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait. Resource-allocation strategies include prevention, avoidance, detection and recovery, and pragmatic timeout-based approaches. Banker-style avoidance requires knowledge of maximum claims and grants resources only when the resulting state remains safe. In general-purpose systems, exact maximum claims are often unavailable, so systems combine lock ordering, bounded waits, timeouts, and recovery.

I/O scheduling provides another layer of allocation. A CPU scheduler that rapidly runs threads blocked on storage cannot improve completion if the storage queue is the bottleneck. End-to-end performance requires coordination across CPU, memory, network, and storage schedulers. In virtualized and containerized environments, the hypervisor, host kernel, and guest operating system may each schedule work, producing interference and accounting difficulties.

Applied Case: Scheduling a Mixed Cloud Service

Background

Consider an illustrative cloud platform operated by a financial analytics company. Each physical host has multiple cores and runs three workload classes: customer API requests, nightly risk-analysis batches, and monitoring agents. API requests are latency-sensitive; batches are CPU-intensive but delay-tolerant; monitoring is operationally important and must continue during overload.

Situation and problem

The initial deployment uses an equal-share round-robin policy for all containers. During nightly analysis, average CPU utilization reaches a high level. API throughput remains acceptable, but the 99th-percentile response time violates the SLO. Monitoring processes occasionally experience delayed execution, and batch completion time varies widely.

Analysis

Equal shares do not reflect unequal service objectives. Batch processes generate long CPU bursts and can compete with request handlers. The problem is not simply insufficient average capacity: queueing delay and contention produce tail latency. Uncontrolled thread creation inside the batch application also causes oversubscription. In addition, migration between cores removes cache locality.

Approach and solution

The platform adopts a hierarchical policy. Monitoring receives a protected minimum share and a high but bounded priority. API containers receive reserved capacity, short scheduling quanta, and admission control that rejects or defers excess requests rather than allowing unlimited queue growth. Batch containers use weighted fair-share scheduling with a lower priority and a maximum concurrency limit. Aging prevents indefinite starvation.

Per-core affinity is used for selected API worker pools, while batch work is balanced through controlled work stealing. Telemetry records CPU utilization, queue length, response-time percentiles, deadline-like request targets, throttling, and batch completion rates. The operator periodically reviews whether reservations match demand. During severe overload, optional batch tasks are deferred and noncritical monitoring frequency is reduced, while core monitoring and customer traffic remain protected.

Outcome

The design aligns allocation with service objectives rather than treating all runnable work identically. API tail latency becomes the primary interactive metric, batch throughput is evaluated over a longer interval, and monitoring receives predictable service. The result is not maximum instantaneous throughput for every class, but a more appropriate balance of responsiveness, fairness, and operational reliability.

Learning points

First, scheduling policy must follow workload objectives. Second, percentile latency is more informative than average response for interactive services. Third, hierarchical quotas, affinity, admission control, and application-level concurrency limits complement the CPU scheduler. Finally, resource allocation is a continuous control problem: measurements must be used to revise reservations and priorities.

Challenges, Risks, and Professional Practice

No general-purpose algorithm is optimal for every workload. Burst estimates may be wrong; priorities may encode organizational bias; fairness may conflict with urgency; and high utilization may increase tail latency sharply. Starvation, convoy effects, priority inversion, lock contention, and scheduling thrashing are recurring failure modes.

Common mistakes include optimizing only average waiting time, selecting a quantum without measuring context-switch cost, assuming all cores are interchangeable, ignoring NUMA locality, and treating CPU capacity as independent from memory and I/O capacity. Another mistake is using priority as a substitute for capacity planning. A priority boost cannot create processor time when demand persistently exceeds supply.

Scheduling systems should be observable and auditable. Administrators need to know why a task was delayed, which quota applied, whether a deadline was missed, and whether interference came from another tenant. Policies should be documented, reproducible, and tested under normal load, burst load, failure conditions, and overload. In safety-critical environments, timing assumptions and worst-case analyses require formal review. In shared infrastructures, fair allocation also has governance implications: resource policies should be transparent and should not permit arbitrary or discriminatory treatment of users or workloads.

Technology and Emerging Directions

Modern schedulers increasingly use telemetry, cgroups or equivalent control groups, container quotas, processor affinity, hardware counters, and tracing systems. Automated controllers can adjust concurrency, quotas, and admission thresholds in response to queue length and latency. Machine-learning-assisted scheduling is being explored for workload classification, burst prediction, and placement, but predictions must be explainable enough for operational use and must not replace safety bounds.

Heterogeneous processors introduce another decision: whether a task should run on a high-performance core, an efficiency core, a GPU, or another accelerator. Energy-aware scheduling treats power and thermal limits as allocation constraints. At the same time, confidential computing, real-time edge systems, disaggregated infrastructure, and serverless platforms create new forms of interference and scheduling overhead. These developments reinforce a central principle: scheduling is a policy-driven allocation problem whose quality must be evaluated against explicit objectives.

Best-Practice Decision Framework

A responsible scheduler design begins by characterizing the workload: arrival pattern, burst distribution, parallelism, deadlines, blocking behavior, and resource dependencies. It then identifies the dominant objective—mean turnaround, interactive response, fairness, throughput, energy, deadline compliance, or an SLO. The designer selects a policy, chooses parameters, models overhead, and tests both average and tail behavior.

The design should also define overload behavior, starvation protection, accounting boundaries, affinity rules, and observability requirements. For multicore systems, placement and memory locality must be included. For real-time systems, worst-case analysis and bounded blocking are essential. Finally, the policy should be validated using representative traces and production measurements rather than relying solely on textbook assumptions.

Chapter Summary

CPU scheduling selects runnable work, while resource allocation distributes limited system capacity among competing demands. FCFS is simple but vulnerable to convoy effects; SJF and SRTF reduce average waiting under accurate burst estimates; round-robin supports time-sharing; priority scheduling expresses urgency but requires starvation and inversion controls; MLFQ adapts to changing behavior. Fair-share scheduling allocates service among users or groups, while multicore scheduling must address affinity, load balancing, cache locality, and NUMA placement. Real-time scheduling prioritizes deadline compliance and requires worst-case analysis. Effective systems evaluate throughput, response time, fairness, utilization, tail latency, and deadline misses together. The most suitable policy is therefore determined by workload and service objectives, not by a universal ranking of algorithms.

Key Terms

CPU scheduling: Selection of a runnable thread or process for processor execution.

Ready queue: Collection of runnable tasks waiting for CPU service.

Preemption: Interruption of a running task so another task can execute.

Dispatch latency: Time required to transfer control to the selected task.

Turnaround time: Time from job arrival to job completion.

Response time: Time from arrival until a job first receives service.

Throughput: Number of completed jobs per unit of time.

CPU utilization: Fraction of time the processor performs useful work.

Starvation: Indefinite postponement of a task that remains eligible to run.

Aging: Gradual priority increase used to reduce starvation.

Convoy effect: Delay caused when a long task holds up many shorter tasks.

Priority inversion: Blocking of a high-priority task by lower-priority work.

Fair-share scheduling: Allocation based on users, groups, or weighted resource entitlements.

Processor affinity: Preference or restriction for executing a task on particular CPUs.

NUMA: Architecture in which memory-access time depends on processor and memory location.

Deadline: Required completion time for a task or request.

Rate Monotonic Scheduling: Fixed-priority scheduling that favors shorter-period periodic tasks.

Earliest Deadline First: Dynamic scheduling that selects the nearest-deadline task.

Service-level objective: Measurable target for service performance or reliability.

Admission control: Decision about whether additional work may enter a system.

Review Questions

Short Answer Questions

1. Distinguish response time from turnaround time.

2. What is the convoy effect, and which scheduling policy commonly exhibits it?

3. Why does a very small round-robin quantum reduce efficiency?

4. What problem is solved by priority inheritance?

5. Why is processor affinity useful on multicore systems?

Long Answer Questions

1. Compare FCFS, SJF, SRTF, and round-robin scheduling with respect to assumptions, strengths, and weaknesses.

2. Explain how an MLFQ scheduler attempts to support both interactive and CPU-bound workloads.

3. Discuss fairness, weighted allocation, and service-level objectives in multi-tenant systems.

4. Explain the principal scheduling issues introduced by multicore and NUMA architectures.

5. Compare Rate Monotonic Scheduling and Earliest Deadline First, including their assumptions and limitations.

Analytical / Application Questions

1. A system has many short interactive jobs and a smaller number of long batch jobs. Design a scheduling policy and justify its queue structure, priorities, quantum choices, and starvation controls.

2. An API service meets its average latency target but violates its 99th-percentile SLO during batch execution. Analyze possible causes and propose coordinated CPU, concurrency, affinity, and admission-control changes.

3. A high-priority real-time task is blocked by a lock held by a low-priority task while medium-priority tasks run. Explain the scheduling failure and design a mechanism that bounds the blocking time.

22. Multiple Choice Questions with Answers

Question 1

Which scheduling policy minimizes average waiting time under ideal conditions when CPU burst lengths are known accurately?

A. First-Come, First-Served

B. Shortest Job First

C. Round-Robin

D. 固定-priority scheduling

Correct Answer: B. Shortest Job First

Question 2

A round-robin quantum that is excessively small is most likely to cause which effect?

A. No context switches

B. Increased context-switch overhead

C. Permanent starvation of all short jobs

D. Conversion into non-preemptive scheduling

Correct Answer: B. Increased context-switch overhead

Question 3

Which mechanism directly addresses starvation in priority scheduling?

A. Aging

B. Disabling interrupts permanently

C. Increasing memory latency

D. Removing the ready queue

Correct Answer: A. Aging

Question 4

A high-priority task waits for a lock held by a low-priority task while medium-priority tasks execute. This is an example of:

A. Convoy effect

B. Priority inversion

C. Thrashing

D. Deadlock prevention

Correct Answer: B. Priority inversion

Question 5

What is the principal purpose of fair-share scheduling?

A. To allocate all CPU time to the shortest job

B. To allocate resources according to users, groups, or weights

C. To eliminate all context switches

D. To guarantee every job the same completion time

Correct Answer: B. To allocate resources according to users, groups, or weights

Question 6

Which metric is most appropriate for evaluating the tail behavior of an interactive API?

A. Only total disk capacity

B. 99th-percentile response time

C. Number of source-code lines

D. Average process size

Correct Answer: B. 99th-percentile response time

Question 7

Why can task migration reduce performance on a multicore system?

A. It always increases CPU frequency

B. It may reduce cache locality and increase migration cost

C. It prevents every form of parallelism

D. It eliminates memory access

Correct Answer: B. It may reduce cache locality and increase migration cost

Question 8

Which real-time algorithm dynamically selects the task with the nearest absolute deadline?

A. FCFS

B. Rate Monotonic Scheduling

C. Earliest Deadline First

D. Multilevel Queue Scheduling

Correct Answer: C. Earliest Deadline First

Question 9

In the illustrative cloud case, why was admission control applied to API requests?

A. To allow unlimited queue growth

B. To protect latency objectives during overload

C. To reduce monitoring reliability

D. To ensure batch jobs always ran first

Correct Answer: B. To protect latency objectives during overload

Question 10

Which statement best describes a limitation of optimizing only CPU utilization?

A. High utilization always guarantees fairness

B. High utilization may coexist with unacceptable queueing and tail latency

C. Utilization is unrelated to scheduling

D. High utilization prevents all deadline misses

Correct Answer: B. High utilization may coexist with unacceptable queueing and tail latency