CPU Scheduling and Workload Management

Introduction

A multiprogrammed operating system maintains several ready processes while one or more processors execute instructions. CPU scheduling is the policy and mechanism used to select the next runnable thread. Workload management is broader: it includes admission, priorities, processor affinity, resource allocation, overload handling, and performance monitoring.

Scheduling decisions affect throughput, response time, predictability, fairness, energy consumption, and application quality of service. No single algorithm optimizes all these objectives. A batch analytics system may favor throughput, whereas an interactive service values response time and fairness, and an aircraft controller requires bounded worst-case response time.

Learning Objectives

After studying this chapter, a learner should be able to:

1. Explain preemptive and non-preemptive scheduling.

2. Calculate utilization, throughput, turnaround time, response time, waiting time, and fairness measures.

3. Evaluate FCFS, SJF, priority, round-robin, multilevel, fair-share, multicore, and real-time scheduling.

4. Apply utilization-bound and response-time reasoning to rate-monotonic scheduling.

5. Select a scheduling approach for batch, interactive, cloud, embedded, and real-time workloads.

6. Identify implementation, security, energy, and governance trade-offs.

1. Scheduling Concepts and Performance Measures

A process alternates between CPU bursts and I/O bursts. A scheduler normally chooses among threads in the ready queue; blocked threads are not eligible until their I/O or event completes. A context switch saves the current thread’s state and restores another’s state. It consumes time and may reduce cache and translation-lookaside-buffer locality.

A non-preemptive scheduler allows a running thread to retain the CPU until it blocks, terminates, or voluntarily yields. A preemptive scheduler can interrupt it, commonly when a timer expires or a higher-priority thread becomes ready.

Important measures are:

• CPU utilization: fraction of elapsed time during which a processor executes useful workload instructions. If busy time is B over interval T, utilization is U = B/T.
• Throughput: completed jobs per unit time.
• Turnaround time: completion time minus arrival time.
• Response time: first time the job receives CPU service minus arrival time.
• Waiting time: total time spent ready but not executing. For a process with multiple CPU and blocking intervals, it is not generally turnaround time minus CPU service. If turnaround is TAT, CPU execution time is S, and blocked time is I, then, assuming all non-CPU/non-blocked elapsed time is ready-queue waiting, W = TAT − S − I. More generally, waiting must be measured by summing all intervals in which the job is ready but not running.
• Deadline tardiness: max(0, completion time − deadline).
• Jitter: variation in response or completion time across similar executions.

A useful scheduling objective is therefore a vector rather than a single number: maximize throughput and utilization while constraining latency, waiting, deadline misses, unfairness, and energy.

Worked example: ready waiting versus blocking

A process arrives at time 0, executes for 2 ms, performs I/O from t = 2 to 7 ms, waits in the ready queue from t = 7 to 10 ms, executes for 4 ms, and completes at t = 14 ms. Its turnaround time is 14 ms, CPU service is 6 ms, and blocked time is 5 ms. Its ready-queue waiting time is 14 − 6 − 5 = 3 ms. Calling 8 ms (turnaround minus CPU service) “waiting time” would incorrectly count the 5 ms of blocking.

2. Classical Scheduling Algorithms

First-Come, First-Served

FCFS runs ready processes in arrival order and is normally non-preemptive. It is simple, has low scheduling overhead, and is predictable in order. Its principal weakness is the convoy effect: a long CPU-bound process can delay many short interactive or I/O-bound processes. Average waiting and response times can therefore be poor even when throughput is acceptable.

Shortest Job First and Shortest Remaining Time

SJF selects the ready process with the smallest next CPU-burst estimate. In a non-preemptive form, the selected process runs until its burst ends or it blocks. Shortest Remaining Time First (SRTF) preempts when a newly ready process has a shorter remaining burst. If exact burst lengths are known, SJF minimizes the average waiting time among non-preemptive schedules for the available jobs, subject to the same arrival assumptions; it can starve long jobs and requires burst prediction in real systems.

A common exponential estimate is

τ(next) = αt(previous) + (1 − α)τ(previous), 0 ≤ α ≤ 1,

where t(previous) is the observed last burst and τ(previous) is the previous estimate. This is a prediction, not knowledge, and its quality depends on workload stability.

Priority Scheduling

The scheduler chooses the highest-priority ready process. Priorities may be static or dynamic, and either a larger or smaller numerical value may represent higher priority; the convention must be specified. Priority scheduling supports differentiated service but may starve low-priority work. Aging gradually raises the priority of waiting processes. Priority inversion occurs when a high-priority thread waits for a lock held by a low-priority thread while medium-priority work runs. Priority inheritance or priority-ceiling protocols can limit this problem.

Round Robin

Round Robin (RR) gives each ready process a time quantum q and rotates through the queue. It is preemptive and generally improves interactive response compared with FCFS. If q is extremely large, RR approaches FCFS; if q is too small, context-switch overhead becomes excessive. The quantum should be large relative to context-switch cost but small enough to provide the desired response bound. With n continuously ready processes and equal dispatch assumptions, a newly ready process may wait for approximately (n − 1)q plus dispatch overhead before its first turn, although actual response depends on queue position and arrivals.

Multilevel and Multilevel Feedback Queues

A multilevel queue separates classes such as foreground, batch, and system work. Queues may have fixed priorities or receive time shares. A multilevel feedback queue (MLFQ) allows movement between queues. New jobs often begin in a high-priority, short-quantum queue; CPU-intensive jobs move downward, while interactive jobs that frequently block may remain higher. This approximates SJF without requiring exact burst lengths. It requires careful tuning and anti-starvation mechanisms, such as periodic priority boosts.

3. Scheduling on Multicore Systems

On a multicore machine, the scheduler maps runnable threads to logical processors. Global scheduling uses one shared run queue; partitioned scheduling assigns tasks to particular cores; per-core scheduling maintains separate queues, sometimes with load balancing.

Key issues include:

• Load balancing: migration prevents idle cores but costs cache locality and migration time.
• Processor affinity: keeping a thread on a familiar core improves cache reuse; soft affinity is a preference, while hard affinity restricts placement.
• NUMA locality: memory access may be faster from one socket than another, so CPU and memory placement should be coordinated.
• Simultaneous multithreading: logical processors share execution resources, so two runnable threads may not provide twice the performance.
• Heterogeneous cores: systems may combine performance and efficiency cores; scheduler decisions must account for capacity, thermal state, and energy.

A utilization figure should state its denominator. Per-core utilization, aggregate utilization, and capacity-normalized utilization are not interchangeable. A workload can show high aggregate utilization while one latency-sensitive task is delayed on a saturated core.

4. Fair-Share and Service-Level Scheduling

Traditional process fairness gives each runnable process a share. Fair-share scheduling instead assigns shares to users, groups, containers, or services. If group i has weight w_i and all groups are continuously runnable, its ideal long-run CPU fraction is approximately w_i/Σw_j. Actual service differs during short intervals because of arrivals, blocking, affinity, and scheduler overhead.

Linux Completely Fair Scheduler-style designs use virtual runtime concepts to approximate weighted fairness; other systems use hierarchical control groups and quotas. Fairness does not guarantee low latency: a small but important service may need a reserved capacity or latency class. Conversely, strict priority may meet a deadline while starving background users. Production policy therefore combines weights, minimum reservations, maximum limits, burst allowances, and admission control.

A simple fairness diagnostic is Jain’s index:

J = (Σx_i)^2 / (nΣx_i^2),

where x_i is the measured service received by each of n entities over the same interval. J lies between 1/n and 1 for nonnegative service values; 1 indicates equal measured shares. Equal shares are not always equitable when users have different entitlements, so weighted comparisons may be more appropriate.

5. Real-Time Scheduling

Real-time scheduling emphasizes predictable timing, not merely high average throughput. A hard real-time task missing a deadline may cause unacceptable failure; in soft real-time, occasional misses reduce quality. Tasks may be periodic, sporadic, or aperiodic. A periodic task i is commonly described by execution time C_i, period T_i, and relative deadline D_i. Utilization is

U = Σ(C_i/T_i).

This is the fraction of processor demand under idealized periodic execution, ignoring context-switch and interrupt overhead unless those costs are included in C_i.

Rate-monotonic scheduling

Rate-monotonic (RM) assigns higher fixed priority to tasks with shorter periods. It is optimal among fixed-priority assignments for independent periodic tasks with deadlines equal to periods, under the usual assumptions: single processor, preemption, independent tasks, negligible or accounted-for overhead, and no blocking or release jitter unless analyzed separately.

For n periodic tasks, the classical sufficient schedulability bound is

U ≤ n(2^(1/n) − 1).

As n grows, the bound approaches ln 2, approximately 0.693. This is sufficient, not necessary: a task set above the bound may still be schedulable.

For two tasks the bound is 2(√2 − 1) ≈ 0.828. Consider C1 = 1, T1 = 4 and C2 = 2, T2 = 6. Task 1 has higher RM priority. U = 1/4 + 2/6 = 0.583, below 0.828, so the bound certifies schedulability under the stated assumptions.

Response-time analysis

The utilization test is not a complete test. For fixed-priority task i, a standard response-time recurrence is

R_i^(k+1) = C_i + B_i + Σ over h ofceil(R_i^k/T_h) C_h,

where higher-priority tasks h interfere, B_i is blocking from lower-priority critical sections, and the initial value can be R_i^(0) = C_i + B_i. The recurrence is iterated until it converges or exceeds D_i. The ceiling counts how many releases of each higher-priority task can occur during the response interval. Task i is schedulable if the converged R_i ≤ D_i.

Example: task 1 has C1 = 1, T1 = D1 = 4; task 2 has C2 = 2, T2 = D2 = 6; assume B2 = 0. For task 2, R2^(0)=2. Then R2^(1)=2+ceil(2/4)1=3; R2^(2)=2+ceil(3/4)1=3. Thus R2=3 ≤ 6. For task 1, R1=1 ≤ 4. This analysis provides a response-time argument rather than relying only on average utilization.

Earliest Deadline First (EDF) is dynamic priority scheduling: the ready job with the earliest absolute deadline runs first. Under ideal assumptions on one processor, preemptive EDF can schedule feasible independent implicit-deadline periodic task sets up to utilization 1, whereas RM’s simple sufficient bound is lower. In practice, overhead, blocking, release jitter, multiprocessor effects, and aperiodic work reduce this ideal capacity. Admission control and measured execution-time budgets are essential.

6. Workload Management and Energy

Scheduling begins before dispatch. Admission control limits the number of active jobs when overload would violate service objectives. Queueing policies may reserve capacity for critical services, cap noisy neighbors, or reject work whose deadline cannot be met. Backpressure prevents queues from growing without bound.

Energy-aware scheduling can consolidate work onto fewer cores and enter idle states, or spread work to meet deadlines at lower per-core voltage and frequency. Dynamic voltage and frequency scaling often saves energy but can increase execution time and deadline risk. Race-to-idle may be effective when deep idle states are available; steady pacing may be better when frequency transitions and thermal limits dominate. The scheduler should optimize energy per completed task while preserving response and deadline constraints, rather than treating low utilization as automatically efficient.

7. Applied Case: An Illustrative Cloud Inference Platform

Background. A cloud service hosts interactive AI inference, offline model training, and routine reporting on a multicore server.

Problem. Training jobs consume CPUs for long periods, while inference requests require a 50 ms response target. Unrestricted FCFS produces long inference delays. Strict priority protects inference but can starve training and reporting.

Analysis. The platform separates workloads into control groups. Inference receives reserved capacity and a high-priority, preemptive class. Training uses weighted fair sharing on remaining capacity, with a maximum quota. Reporting runs at low priority and is subject to backpressure. Affinity is used for inference workers to preserve cache locality, but the system permits migration when a core is overloaded. Monitoring records tail latency, not only mean latency, because a small number of slow requests can violate the service objective.

Approach. A two-level policy is deployed: admission control rejects or defers inference requests when capacity cannot support the target; within the admitted set, a short-quantum policy limits response delay. Training is scheduled fairly across users, with aging to prevent indefinite delay. CPU-frequency controls are constrained so that energy savings cannot reduce inference capacity below its reservation.

Outcome. The design trades some batch throughput for predictable inference response, maintains a defined training share, and makes overload behavior explicit. Its effectiveness must be validated under bursty arrivals, model-cache misses, garbage collection, and thermal throttling.

Learning points. Scheduling policy must match workload objectives; reservations and fairness are complementary; tail metrics matter; and admission, placement, and energy controls are part of workload management rather than separate afterthoughts.

8. Limitations, Governance, and Best Practices

Scheduling models often assume known execution times, independent tasks, and negligible overhead. Real systems include locks, page faults, interrupts, device delays, garbage collection, virtualization, and adversarial workloads. Therefore, benchmark under representative load and report distributions, percentiles, context-switch costs, and deadline misses.

Priority and quota policies can encode organizational bias: a high-paying tenant may receive preferential service, while low-priority users experience systematic delay. Policies should be documented, auditable, and reviewed for contractual and regulatory obligations. Security also matters: timing behavior can reveal co-resident activity, and untrusted workloads can exploit priority or resource-accounting mechanisms. Isolation, quotas, least privilege, and anomaly monitoring reduce these risks.

Best practices include defining objectives before selecting an algorithm, measuring both average and tail latency, accounting for blocking and overhead, using aging or reservations against starvation, applying response-time analysis for real-time tasks, preserving locality where useful, and testing overload and failure modes.

Chapter Summary

CPU scheduling selects runnable threads, while workload management additionally controls admission, shares, placement, overload, and energy. FCFS is simple but vulnerable to convoy effects; SJF minimizes average waiting under restrictive assumptions but requires prediction and may starve long jobs. Priority scheduling supports differentiated service but needs aging and inversion control. Round Robin improves interactive response when its quantum is properly chosen. Multilevel feedback queues approximate burst-aware scheduling, while fair-share systems allocate service among users or groups. Multicore scheduling must address affinity, migration, NUMA, heterogeneous capacity, and shared resources. Real-time scheduling requires predictability: RM uses fixed priorities and a sufficient utilization bound, while response-time analysis explicitly accounts for higher-priority interference and blocking. Effective engineering decisions balance throughput, utilization, response time, waiting, fairness, deadlines, and energy, supported by measurement and transparent governance.

Key Terms

CPU scheduling: Selecting the next runnable thread for execution.

Preemption: Interrupting a running thread to schedule another.

Context switch: Saving one execution context and restoring another.

CPU utilization: Fraction of elapsed time a processor performs useful work.

Throughput: Completed jobs per unit time.

Turnaround time: Completion time minus arrival time.

Response time: First service time minus arrival time.

Ready-queue waiting time: Time spent ready but not executing.

FCFS: Non-preemptive arrival-order scheduling.

SJF: Scheduling the shortest predicted next CPU burst first.

SRTF: Preemptive shortest-remaining-burst scheduling.

Priority inversion: High-priority work blocked indirectly by lower-priority work.

Round Robin: Cyclic time-quantum scheduling.

MLFQ: Feedback scheduling using multiple priority queues.

Processor affinity: Preference or restriction for running on particular cores.

Fair-share scheduling: Allocating service among users, groups, or services.

Jain’s fairness index: A normalized measure of equality of received service.

Rate-monotonic scheduling: Fixed-priority scheduling with shorter periods assigned higher priority.

Response-time analysis: Iterative calculation of worst-case fixed-priority response.

Admission control: Accepting work only when resource and timing objectives can be supported.

Review Questions

Short Answer Questions

1. Distinguish turnaround time, response time, and ready-queue waiting time.

2. Why can FCFS create a convoy effect?

3. What problem does aging address in priority scheduling?

4. State two multicore scheduling concerns.

5. Why is the RM utilization bound called sufficient rather than necessary?

Long Answer Questions

1. Compare FCFS, SJF, priority scheduling, and Round Robin for batch and interactive workloads.

2. Explain how MLFQ approximates burst-aware scheduling and discuss its limitations.

3. Discuss global, per-core, and partitioned scheduling on multicore systems.

4. Explain fair-share scheduling, quotas, reservations, and Jain’s fairness index.

5. Describe RM and EDF, including their assumptions and practical limitations.

Analytical / Application Questions

1. A process has a 14 ms turnaround, 6 ms CPU service, and 5 ms blocked time. Calculate its ready-queue waiting time and explain why subtracting only CPU service is incorrect.

2. For tasks (C1,T1)=(1,4) and (C2,T2)=(2,6), calculate total utilization, apply the two-task RM bound, and use response-time analysis for task 2.

3. Design a scheduling and admission policy for a cloud service combining interactive inference, batch training, and low-priority reporting. Justify choices using latency, fairness, utilization, and energy criteria.

Multiple Choice Questions with Answers

Question 1

A process has turnaround time 20 ms, CPU service 8 ms, and blocked time 5 ms. Assuming all remaining elapsed time is ready-queue waiting, what is its waiting time?

A. 5 ms

B. 7 ms

C. 12 ms

D. 20 ms

Correct Answer: B. 7 ms

Question 2

Which algorithm is non-preemptive in its standard form and selects the smallest next CPU burst?

A. FCFS

B. Round Robin

C. SJF

D. EDF

Correct Answer: C. SJF

Question 3

If a Round Robin quantum is made extremely large, the algorithm approaches which policy?

A. FCFS

B. SRTF

C. EDF

D. MLFQ with immediate boosts

Correct Answer: A. FCFS

Question 4

What is the main purpose of aging in priority scheduling?

A. To reduce context-switch cost

B. To prevent starvation of waiting processes

C. To estimate CPU bursts

D. To increase cache capacity

Correct Answer: B. To prevent starvation of waiting processes

Question 5

Three jobs arrive together with CPU bursts 1, 2, and 4 time units. Under non-preemptive SJF, what is the average waiting time?

A. 1 time unit

B. 4/3 time units

C. 2 time units

D. 7/3 time units

Correct Answer: B. 4/3 time units

Question 6

For two periodic tasks, the classical RM sufficient utilization bound is:

A. 0.500

B. 0.693

C. Approximately 0.828

D. 1.000

Correct Answer: C. Approximately 0.828

Question 7

In fixed-priority response-time analysis, the ceiling term ceil(R/T_h) represents:

A. The number of lower-priority locks

B. The number of higher-priority releases that may interfere

C. The number of processors

D. The task’s average waiting time

Correct Answer: B. The number of higher-priority releases that may interfere

Question 8

Which policy dynamically selects the ready job with the earliest absolute deadline?

A. Rate Monotonic

B. FCFS

C. EDF

D. Priority aging

Correct Answer: C. EDF

Question 9

If two continuously runnable groups have weights 1 and 3 under ideal weighted fair sharing, what approximate CPU shares should they receive?

A. 25% and 75%

B. 50% and 50%

C. 33% and 67%

D. 10% and 90%

Correct Answer: A. 25% and 75%

Question 10

Which is a principal multicore scheduling trade-off?

A. Migration can improve balance but reduce cache locality

B. Affinity always eliminates load imbalance

C. NUMA makes all memory accesses equal

D. Logical processors always double physical-core capacity

Correct Answer: A. Migration can improve balance but reduce cache locality