Lesson 5.1: Scheduling Objectives

01 Introduction

In Unit 3 we followed a process from creation to termination and saw that a running program is not always using the CPU. It issues a read, waits for a page fault, blocks on a lock, or is simply preempted by the kernel so that another process can run. In Unit 4 we saw the same phenomenon at the level of threads: a process may have several threads, each of which is an independent schedulable entity, and the kernel must decide which of them gets a processor core and for how long.

Those decisions are the subject of this unit. CPU scheduling is the set of policies and mechanisms by which the operating system chooses which ready thread or process to run next, and for how long. It is one of the oldest and most studied problems in operating systems, and it remains one of the most visible: the difference between a responsive desktop and a sluggish one, between a server that meets its latency targets and one that does not, and between a supercomputer that runs at ninety percent of peak and one that runs at forty percent, is usually a scheduling difference.

This first lesson of Unit 5 sets out the problem before we look at any particular algorithm. It defines what scheduling is, describes the CPU–I/O burst cycle that makes it necessary, distinguishes preemptive from non-preemptive decisions, surveys the levels at which scheduling happens, and — most importantly — enumerates the objectives that a scheduler is trying to satisfy. The remaining five lessons in the unit examine specific algorithms — FCFS, SJF and SRTF, priority scheduling, round robin, and multilevel queues — and measure each one against the criteria introduced here.

A theme that runs through the unit is that scheduling objectives conflict. Throughput and response time pull in opposite directions. Fairness and priority pull in opposite directions. Minimizing average waiting time and minimizing the maximum waiting time are different goals that different algorithms satisfy to different degrees. Understanding these trade-offs is more important than memorising any single algorithm, because in practice the scheduler is chosen to fit the workload, not the other way around.

Prerequisites

This lesson builds directly on Unit 3 (process states, process control blocks, context switching) and Unit 4 (kernel threads, multicore processing). It assumes the development environment from Lesson 2.5 is available, since the interactive activity uses standard Linux tools to observe scheduling in a live system.

02 Learning objectives

By the end of this lesson you will be able to

Define CPU scheduling and explain its role in a multiprogrammed system.
Describe the CPU–I/O burst cycle and explain why it motivates scheduling.
Distinguish preemptive from non-preemptive scheduling decisions.
Identify the major scheduling criteria and compute the standard scheduling metrics.
Explain the tensions between competing scheduling objectives.

This lesson contributes to U5.1 and U5.3, and to course learning outcomes CLO1, CLO2, and CLO3.

03 Required reading

OSTEP — Chapter 7, Scheduling: Introduction. The clearest short treatment of the scheduling problem and its metrics. Read it before the rest of the unit; the terminology it establishes is used throughout.
Operating System Concepts — Chapter 5, Sections 5.1–5.3, Basic Concepts, Scheduling Criteria, and Scheduling Algorithms (the introductory parts). The chapter's coverage of the CPU–I/O burst cycle is the standard reference.
Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.4, Scheduling. A complementary treatment that places scheduling in the broader context of process management.
Love, R. — Linux System Programming, Chapter 3, Process Management, and the sections on scheduling and priority. A practical view of how Linux exposes scheduling to user space.
Linux man pages: man 7 sched, man 2 sched_setscheduler, man 2 sched_setaffinity, man 1 nice, man 1 chrt, man 1 taskset.

Reading strategy

Read OSTEP Chapter 7 first — it introduces the metrics (turnaround time, response time) and the central tension between them in a few pages. Then read the corresponding sections of Silberschatz for the formal definitions and the CPU–I/O burst discussion. Keep man 7 sched open as a reference for how Linux names and exposes the concepts; the terminology there is the terminology you will use in the laboratory.

04 Core content

4.1 What is CPU scheduling?

A CPU scheduler is the part of the kernel that decides which ready thread or process runs next on each processor core, and for how long. The decision is made whenever the set of ready entities changes — when a running process blocks, when an I/O interrupt makes a waiting process ready, when a time slice expires, or when a new process is created — and the outcome is enforced by the dispatcher, which performs the actual context switch.

Scheduling exists because the number of ready processes is usually larger than the number of available cores. On a single-core system, at most one process can run at a time; every other ready process must wait. Even on a multicore system, the number of runnable threads in a busy server can easily exceed the number of cores by an order of magnitude. The scheduler's job is to allocate the scarce resource — CPU time — among the competing claimants in a way that satisfies the system's objectives.

Formally, the scheduler chooses among the processes in the ready queue. The ready queue is not a simple FIFO; it is a data structure (in Linux, a set of per-CPU runqueues, each containing several priority-ordered trees) that the scheduler maintains and searches. The scheduler selects an entry, the dispatcher switches to it, and the process runs until it blocks, terminates, or is preempted.

4.2 The CPU–I/O burst cycle

The reason scheduling matters — and the reason it is not trivial — is that processes do not use the CPU continuously. A process alternates between periods of CPU activity (CPU bursts) and periods of waiting for I/O (I/O bursts). The pattern is called the CPU–I/O burst cycle, and it is the empirical foundation on which all scheduling theory rests.

Figure 5.1 — The CPU–I/O burst cycle for two processes. Each process alternates between CPU bursts and I/O waits. The two patterns overlap, so the CPU can be kept busy by running one process while the other waits. Maximizing this overlap is the central goal of multiprogramming, and the reason scheduling matters.

The distribution of burst lengths is highly skewed. Most CPU bursts are very short — a few milliseconds or less — while a small number are very long, running for hundreds of milliseconds or more. This distribution is what distinguishes an I/O-bound process, which issues many short CPU bursts separated by I/O waits, from a CPU-bound process, which issues a few long CPU bursts with little I/O in between. The distinction matters because the two classes of process have different scheduling needs: an I/O-bound process wants to be scheduled promptly when its I/O completes, so that it can issue the next request and keep the device busy; a CPU-bound process wants long uninterrupted slices, so that it can make progress without paying the context-switch cost repeatedly.

Why burst length matters

Because the distribution is skewed, a scheduler that gives short bursts priority will satisfy the majority of scheduling events cheaply. This is the intuition behind shortest-job-first scheduling (Lesson 5.3) and behind the multilevel-feedback queues used by real general-purpose schedulers (Lesson 5.6). It is also why the average burst length is not a useful statistic: the mean is dragged up by a small number of very long bursts and says little about the typical process.

4.3 Preemptive versus non-preemptive scheduling

A scheduling decision can be made at one of several points in a process's life. The classification that matters most is whether the scheduler may take the CPU away from a running process.

Non-preemptive scheduling: Once a process has been given the CPU, it keeps it until it blocks (for example, on I/O) or terminates. The scheduler runs only when the running process voluntarily yields the CPU. Non-preemptive scheduling is simple, has low overhead, and is predictable — but a single long-running process can monopolize the CPU and starve everyone else.
Preemptive scheduling: The scheduler may interrupt a running process and move it back to the ready queue, even though it has not blocked or terminated. Preemption happens when a higher-priority process becomes ready, when a time slice expires, or when the scheduler otherwise decides that a different process should run. Preemptive scheduling is more responsive and fairer, but it incurs the cost of additional context switches and requires care: shared data structures must be protected against the possibility that a process is interrupted in the middle of updating them.

The choice between the two is not purely technical. Early batch systems used non-preemptive scheduling because jobs were long and interactive response was not a goal. General- purpose systems since the 1960s have been preemptive, because interactive users demand responsiveness. Real-time systems sometimes use a mix, with preemption enabled only for the highest-priority tasks. The Linux scheduler discussed in Lesson 5.6 is fully preemptive for ordinary tasks, with additional preemption points introduced by the kernel's CONFIG_PREEMPT options.

4.4 Levels of scheduling

The term "scheduling" covers several distinct decisions that occur on different timescales. Three levels are conventionally distinguished.

The three levels of scheduling
Level	Decision	Frequency	Time scale
Long-term	Which jobs to admit from the job pool into the ready queue.	Rare	Seconds to minutes
Medium-term	Which processes to swap out of memory and which to swap back in.	Occasional	Milliseconds to seconds
Short-term	Which ready process to run on a core next.	Very frequent	Microseconds to milliseconds

The long-term scheduler controls the degree of multiprogramming — the number of processes in memory at once. By admitting a mix of I/O-bound and CPU-bound jobs, it can keep both the CPU and the I/O devices busy. It is largely absent from modern interactive systems, where processes are created on demand and admitted immediately, but it remains relevant in batch systems and in cluster schedulers that decide which jobs to place on which nodes.

The medium-term scheduler performs swapping: it removes processes from memory when memory is scarce and restores them later. On a modern system with virtual memory this is largely handled by the page-replacement machinery of Unit 9, but the concept of reducing the active set under memory pressure remains important.

The short-term scheduler — often just called the scheduler — is the subject of this unit. It chooses which ready process runs next on each core, and it runs thousands of times per second. Its decisions are the ones users perceive as responsiveness or sluggishness.

4.5 Scheduling criteria

A scheduler is judged against a set of criteria that capture what the system is trying to achieve. The standard criteria are these.

Standard scheduling criteria
Criterion	Definition	Goal
CPU utilization	Fraction of time the CPU is doing useful work.	Maximize (keep the CPU busy).
Throughput	Number of processes completed per unit time.	Maximize.
Turnaround time	Time from submission to completion of a process.	Minimize.
Waiting time	Total time a process spends in the ready queue.	Minimize.
Response time	Time from submission to first response (first CPU allocation).	Minimize.
Fairness	Each process gets a fair share of the CPU over time.	Maximize (or guarantee).
Predictability	Variance in performance across runs or across processes.	Minimize.

The first two — CPU utilization and throughput — measure the system's productivity. The next three — turnaround, waiting, and response time — measure the experience of an individual process. Fairness and predictability measure how evenly and consistently the system distributes its attention. No single scheduler can maximize all of these at once; the art of scheduling is choosing which to prioritize for a given workload.

4.6 Scheduling metrics

The criteria above are made precise by a small set of formulas. Throughout this unit we will use the following notation and definitions. For each process P:

Arrival time (AT) — the time at which the process enters the ready queue.
Burst time (BT) — the total CPU time the process requires to complete.
Start time (ST) — the time at which the process first receives the CPU.
Completion time (CT) — the time at which the process finishes.

From these, four derived metrics follow:

Turnaround time  TAT = CT - AT
Waiting time     WT  = TAT - BT
Response time    RT  = ST - AT
CPU utilization  U   = busy_time / total_time

Throughput is measured in processes per unit time:

Throughput = number_of_processes_completed / elapsed_time

All of these metrics are typically reported as averages across the processes in the workload. But averages hide important behaviour: two schedules with the same average waiting time can differ dramatically in the maximum waiting time experienced by any single process. For interactive systems, the maximum — or a high percentile such as the 99th — is often the more meaningful statistic, because it determines the worst-case experience a user can have. We will report both average and maximum values throughout the unit.

A caution about waiting time

The formula WT = TAT - BT is correct only when the process performs no I/O. If a process issues I/O, its turnaround time includes the time it spent waiting for I/O, which is not time spent waiting for the CPU. In a CPU-scheduling problem we usually assume the process is either running or ready, and the formula is exact. In a real system, the scheduler measures only the time a process spends in the ready queue, which requires kernel instrumentation that is not available from user space.

4.7 The dispatcher and context-switch overhead

The scheduler decides; the dispatcher performs the switch. Dispatching involves saving the state of the outgoing process, loading the state of the incoming one, and transferring control. On a modern processor this includes switching the stack pointer, the program counter, the general- purpose registers, the floating-point and vector register state, and possibly the address-space identifier and page- table base. The time this takes is called the dispatch latency or context-switch overhead.

Dispatch latency is pure overhead: no user-level work is done while it happens. Its cost depends on the hardware but is typically on the order of a few microseconds for a thread switch within the same address space, and somewhat more for a full process switch that changes the address space. As a fraction of a scheduling quantum, the overhead is small when the quantum is long (tens of milliseconds) and significant when the quantum is short (a few milliseconds). This is the fundamental trade-off of round-robin scheduling, examined in Lesson 5.5.

A useful approximation, which we will use in the worked example and the practice exercise, is:

Effective CPU utilization = quantum / (quantum + switch_cost)

For example, a 10 ms quantum with a 5 µs switch cost yields an effective utilization of about 99.95 percent. A 1 ms quantum with the same switch cost yields about 99.5 percent — still high in isolation, but the effect compounds when the switch also disrupts the caches and the TLB, which is the subject of Lesson 4.3's discussion of kernel threads and will reappear when we measure scheduler performance in the laboratory.

4.8 Policy versus mechanism

A distinction that runs through all of operating-system design, and is especially clear in scheduling, is the separation of mechanism from policy. The mechanism is the machinery that makes a scheduling decision possible: the timer interrupt that ends a quantum, the runqueue data structure, the context- switch code. The policy is the rule that selects the next process: shortest job first, round robin, priority, and so on.

Keeping the two separate allows the policy to be changed without rewriting the mechanism. Linux does this through a scheduling class abstraction: the core scheduler provides the runqueue and context-switch machinery, and each scheduling class (the completely fair scheduler for ordinary tasks, the real-time classes, and the deadline class) provides its own policy for selecting the next task. The same separation is what allows the kernel to support different scheduling policies for different kinds of workload on the same machine.

The policy/mechanism distinction also matters at the level of the interface presented to user space. Linux exposes scheduling policy through sched_setscheduler, priority through nice and setpriority, and CPU affinity through sched_setaffinity. These are policy controls; the kernel's runqueue and timer interrupt are the mechanism that implements them. The interactive activity in this lesson uses these interfaces to observe the scheduler in action.

4.9 Competing objectives and trade-offs

The criteria in section 4.5 are not independent. Several of them pull in opposite directions, and a scheduler that does well on one will inevitably do worse on another. The principal tensions are these.

Throughput vs. response time

Long quanta reduce context-switch overhead and increase throughput, but they delay the first response of newly arrived processes. Short quanta improve response time at the cost of throughput.

Average vs. maximum

Minimizing the average waiting time and minimizing the maximum waiting time are different objectives that different algorithms satisfy. A short job first schedule has a low average but a long job can wait a very long time.

Fairness vs. priority

Strict fairness gives every process an equal share; a priority scheduler deliberately gives some processes more. Which is right depends on whether all processes are equal.

Utilization vs. predictability

A scheduler that adapts to the workload can achieve high utilization, but its decisions are harder to predict. A fixed policy is predictable but may waste CPU time on a workload it does not fit.

CPU-bound vs. I/O-bound

Giving priority to I/O-bound processes keeps devices busy and improves overall utilization, but starves CPU-bound processes if taken to an extreme.

Overhead vs. optimality

The scheduler runs on every context switch. A policy that makes better decisions but takes longer to compute can lose more time than it saves.

The lesson of this section is that there is no best scheduler. There is only a scheduler that is well matched to a workload and an objective. The remaining lessons of Unit 5 examine the classical algorithms and analyse which objectives each one serves, and at what cost.

4.10 A first look at the Linux scheduler

The general-purpose scheduler in Linux today is the Completely Fair Scheduler (CFS), introduced in kernel 2.6.23 and refined many times since. Its central idea is that the CPU should be divided among runnable tasks in proportion to their weights, and that the task that has received the least CPU time relative to its weight should run next. The kernel tracks this using a virtual runtime (vruntime) that advances more slowly for high-weight (high-priority) tasks, so that they receive a larger share.

CFS is only one of several scheduling classes in Linux. The others include:

SCHED_FIFO and SCHED_RR — real-time policies with strict priority over ordinary tasks, used for latency-critical work. SCHED_FIFO runs a task until it blocks; SCHED_RR adds a time slice.
SCHED_DEADLINE — a deadline-based policy for tasks with explicit runtime, deadline, and period parameters, used in real-time and audio/video workloads.
SCHED_IDLE — a policy for tasks that should run only when nothing else can.

The details of CFS and the real-time classes are the subject of Lesson 5.6. For now it is enough to note that Linux implements the policy/mechanism separation of section 4.8: the core scheduler provides the runqueue and the context-switch machinery, and each class provides a policy for selecting the next task. The user-space interfaces (nice, chrt, sched_setscheduler) select among these policies and adjust the parameters that govern each one.

4.11 Common misconceptions

Several intuitions about scheduling that beginners bring to the subject are misleading. It is worth naming them explicitly.

"The scheduler runs the process that was created first."

Only if the policy is FCFS. Most general-purpose schedulers do not preserve creation order, and the scheduler does not guarantee that a thread starts running immediately after it is created.

"The scheduler runs one process at a time."

On a multicore system, several processes run simultaneously. The scheduler assigns each core a different process; scheduling decisions are per-core, not per-system.

"A shorter quantum is always better."

Shorter quanta improve response time but increase context-switch overhead and reduce throughput. The optimal quantum depends on the workload and the hardware.

"Waiting time is the same as turnaround time."

Turnaround time is the total time from submission to completion; waiting time is the time spent in the ready queue. The difference is the time the process actually spent running (and, in a real system, waiting for I/O).

"The scheduler is fair by default."

Fairness is one objective among several, and it is not the default in every policy. Real-time classes can starve ordinary tasks, and priority scheduling deliberately favours some processes over others.

"Scheduling is a solved problem."

It is not. New hardware (many-core processors, heterogeneous cores, non-volatile memory) and new workloads (latency-sensitive services, machine-learning training) continue to force re-examination of scheduling policy.

05 Worked example

To make the metrics concrete, consider a simple workload of three processes, all arriving at time 0, and compare two different schedules. The example is small enough to compute by hand, but it illustrates the central trade-off between average performance and fairness that the rest of the unit elaborates.

Comparing two schedules on the same workload

Three processes arrive at time 0 with the following CPU burst times:

Process	Arrival time	Burst time
P₁	0	24
P₂	0	3
P₃	0	3

Schedule A — P₁, then P₂, then P₃. The Gantt chart is:

| P1              | P2  | P3  |
0                 24   27    30

The completion times are 24, 27, and 30 respectively. Applying the formulas:

Process	Completion	Turnaround	Waiting	Response
P₁	24	24	0	0
P₂	27	27	24	24
P₃	30	30	27	27
Average	27.0	27.0	17.0	17.0

Schedule B — P₂, then P₃, then P₁. The Gantt chart is:

| P2  | P3  | P1              |
0     3     6                 30

The completion times are 3, 6, and 30 respectively.

Process	Completion	Turnaround	Waiting	Response
P₁	30	30	6	6
P₂	3	3	0	0
P₃	6	6	3	3
Average	13.0	13.0	3.0	3.0

Comparison. Both schedules complete the same three processes in the same 30 time units, so their throughput and CPU utilization are identical. But Schedule B is dramatically better on every per-process metric:

Metric	Schedule A	Schedule B	Improvement
Average turnaround	27.0	13.0	2.1×
Average waiting	17.0	3.0	5.7×
Average response	17.0	3.0	5.7×
Maximum waiting	27	6	4.5×

The reason is straightforward: the two short processes are delayed by the long one in Schedule A, whereas in Schedule B they finish before the long process starts. Because average waiting time is a sum over processes, the two short processes dominate the average, and finishing them quickly pulls the average down sharply.

The catch. Schedule B is better on every metric reported above, but it is not obviously "fair". The long process P₁ waited 6 time units before it started in Schedule B, whereas it started immediately in Schedule A. If P₁ were an interactive process that needed a fast response, Schedule B would be worse from its point of view. The average is a summary; it does not tell you whether any individual process was treated acceptably.

This is the central tension of the unit. Schedule A is the first-come, first-served policy examined in Lesson 5.2; Schedule B is a form of shortest-job-first, examined in Lesson 5.3. Real systems use neither in its pure form, because both have failure modes — FCFS has the convoy effect, and SJF can starve long jobs indefinitely. The algorithms in the rest of the unit are attempts to capture the average-case benefit of SJF while avoiding its fairness problems.

Adding dispatch latency

Suppose each context switch costs 1 time unit of overhead. Schedule A has two switches (at times 24 and 27), so it loses 2 time units to overhead. Schedule B has two switches as well. The completion times become 32 and 32 respectively — the overhead is the same for both schedules here, but it is not always so. A schedule with more switches pays more overhead. Round-robin scheduling, examined in Lesson 5.5, trades throughput for response time precisely because it performs many more switches.

With a quantum of 10 and the same switch cost, the effective CPU utilization for a single-threaded workload is 10/(10+1) ≈ 90.9 percent. With a quantum of 1, it is 1/(1+1) = 50 percent. The numbers in this exercise are exaggerated for clarity; in a real system the switch cost is on the order of microseconds while quanta are on the order of milliseconds, so the utilization loss is small. The principle, however, is general: the shorter the quantum, the larger the fraction of time spent switching.

06 Interactive activity

Activity · observe the scheduler in a live system

The goal of this activity is to connect the concepts in this lesson to the behaviour of a real Linux system. You will use standard tools to observe scheduling decisions, measure context-switch overhead, and see how the choice of policy affects the performance of a simple workload. Work through the steps in your course VM.

Measure context-switch overhead. Write a small program that creates two threads which repeatedly yield to each other using sched_yield, and time a million switches.

#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <time.h>

static volatile int turn = 0;

void *ping(void *arg) {
    for (long i = 0; i < 500000; i++) {
        while (turn != 0) sched_yield();
        turn = 1;
    }
    return NULL;
}

void *pong(void *arg) {
    for (long i = 0; i < 500000; i++) {
        while (turn != 1) sched_yield();
        turn = 0;
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_create(&a, NULL, ping, NULL);
    pthread_create(&b, NULL, pong, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("%.1f ns per switch\n", elapsed / 1e6 * 1e9);
    return 0;
}

Compile with gcc -O2 -pthread -o switch switch.c and run it several times. The measured cost is an upper bound on the switch overhead, because it includes the cost of the sched_yield call itself.

Observe the runqueue. Start a CPU-intensive program in the background and inspect the scheduler's view of the system:
```
yes > /dev/null &
PID=$!
ps -o pid,ni,pri,psr,stat,pcpu,comm -p $PID
cat /proc/$PID/sched | head -20
kill $PID
```
The ni column is the nice value, pri is the dynamic priority assigned by the kernel, psr is the CPU the task last ran on, and the /proc/<pid>/sched file gives detailed scheduling statistics including the number of context switches and the total time spent on the CPU.
Measure the effect of nice. Run two CPU-bound processes, one at the default nice value and one at a higher nice value, and observe how the scheduler divides the CPU between them:
```
nice -n 0  yes > /dev/null &
nice -n 10 yes > /dev/null &
sleep 10
ps -o pid,ni,pcpu,comm -C yes
kill %1 %2
```
The pcpu column shows the share of CPU time each process received. The process with the lower nice value should receive a larger share, in proportion to its weight in the CFS scheduler.
Inspect the scheduling policy. Use chrt to display the current policy of a running process, and to run a process under a different policy:
```
chrt -p $$
chrt -f 10 sleep 1    # SCHED_FIFO, priority 10 (needs privileges)
chrt -r 10 sleep 1    # SCHED_RR, priority 10
chrt -b 0  sleep 1    # SCHED_BATCH
chrt -i 0  sleep 1    # SCHED_IDLE
```
Note which of these require root privileges (the real-time policies do) and which do not.
Pin a process to a core. Use taskset to restrict a process to a single core, then observe how it competes with other work:
```
taskset -c 0 yes > /dev/null &
taskset -c 0 yes > /dev/null &
sleep 5
ps -o pid,psr,pcpu,comm -C yes
kill %1 %2
```
Both processes should report psr equal to 0 and should share the CPU of that core roughly equally. This is CPU affinity, a policy control that constrains the scheduler's choices.
Compare an I/O-bound and a CPU-bound workload. Run a CPU-bound process (such as yes) and an I/O-bound process (such as a loop that reads a small file repeatedly) at the same time, and observe which one appears more responsive. Use vmstat 1 to watch the context-switch rate and the CPU utilization.
```
vmstat 1 10
```
The cs column reports context switches per second. Note how the switch rate changes depending on the mix of workloads.
Read man 7 sched.
```
man 7 sched
```
Read the sections on the scheduling policies, the nice value, and the real-time policies. List the policies that Linux provides, and for each one write a one-sentence description of the workload it is intended for.

Reflect: which of the criteria from section 4.5 does the Linux CFS scheduler appear to prioritize? Which does it appear to trade away? How does the nice value change the trade-off? If you were configuring a server that runs both latency-sensitive and batch workloads, how would you use the policy controls you have seen in this activity?

07 Knowledge check

Check your understanding

Question 1

Explain the CPU–I/O burst cycle. Why does it make CPU scheduling necessary, and how does it explain the distinction between I/O-bound and CPU-bound processes?

Show answer

The CPU–I/O burst cycle is the alternating pattern in which a process runs on the CPU for a while (a CPU burst), then waits for an I/O operation to complete (an I/O burst), then runs again. It makes scheduling necessary because while a process is waiting on I/O it cannot use the CPU. If the CPU were left idle during those waits, the system would be grossly underutilized. The scheduler's job is to run another ready process during the wait, keeping the CPU busy — the essence of multiprogramming. The distinction between I/O-bound and CPU-bound processes follows from the distribution of burst lengths: an I/O-bound process has many short CPU bursts separated by frequent I/O waits, while a CPU-bound process has a few long CPU bursts with little I/O. The distinction matters because the two classes have different scheduling needs: I/O-bound processes want prompt scheduling so they can issue the next request and keep the device busy; CPU-bound processes want long uninterrupted slices so they can make progress without paying the context-switch cost repeatedly.

Question 2

What is the difference between preemptive and non-preemptive scheduling? Give one advantage and one disadvantage of each.

Show answer

In non-preemptive scheduling, a process that has been given the CPU keeps it until it blocks or terminates; the scheduler runs only on voluntary yielding. In preemptive scheduling, the scheduler may interrupt a running process and move it back to the ready queue, for example when a higher-priority process becomes ready or a time slice expires. The advantage of non-preemptive scheduling is that it is simple, has low overhead (fewer context switches), and is predictable. Its disadvantage is that a single long-running or misbehaving process can monopolize the CPU and starve everyone else; there is no way to guarantee responsiveness. The advantage of preemptive scheduling is that it is more responsive and fairer: a newly ready high-priority process can run promptly, and a long-running process cannot lock out others. Its disadvantages are the extra context-switch overhead and the additional synchronization care required — shared data structures in the kernel must be protected against interruption at any point.

Question 3

Distinguish between turnaround time, waiting time, and response time. Given a process with arrival time 4, first CPU allocation at time 10, and completion at time 22, with a burst time of 8, compute all three.

Show answer

Turnaround time is the total time from submission (arrival) to completion. Waiting time is the time the process spends in the ready queue, waiting for the CPU — it excludes both the time the process actually runs and, in a real system, the time it waits for I/O. Response time is the time from submission to the first response, conventionally measured as the time to the first CPU allocation (for an interactive process, the first output may come later, but the scheduling definition uses the first allocation). For the given values: arrival = 4, first allocation = 10, completion = 22, burst = 8. Turnaround = 22 − 4 = 18. Response = 10 − 4 = 6. Waiting = turnaround − burst = 18 − 8 = 10. Note that the waiting time is not simply the gap between arrival and first allocation: the process may run, then be preempted, and wait again. In this example the process had 8 units of CPU time and 18 units of turnaround, so it spent 10 units not running; with no I/O, all 10 units were spent waiting in the ready queue.

Question 4

Why is there no single "best" scheduling algorithm? Give two concrete examples of scheduling objectives that conflict, and explain the conflict in each case.

Show answer

There is no single best algorithm because scheduling objectives are not independent: improving one often degrades another, and the right trade-off depends on the workload and on what the system is trying to achieve. Two concrete conflicts: (1) Throughput versus response time. Throughput is maximized by long time quanta, because each context switch is overhead and fewer switches means more useful work per unit time. Response time, however, is minimized by short quanta, because a newly arrived process must wait at most one quantum before it first runs. A scheduler cannot simultaneously use long quanta (for throughput) and short quanta (for response); it must choose a compromise or use a policy that adapts to the workload. (2) Average waiting time versus maximum waiting time. Shortest-job-first scheduling minimizes the average waiting time, but a long job can wait indefinitely if short jobs keep arriving — its maximum waiting time is unbounded. First-come, first-served gives a bounded maximum waiting time (no job can be starved) but a much worse average. A scheduler must choose which statistic to optimize, and the choice depends on whether the system is measured by its average performance or by its worst-case guarantees. Other conflicts include fairness versus priority (a priority scheduler deliberately favours some processes) and utilization versus predictability (an adaptive scheduler achieves high utilization but is harder to reason about).

Question 5

What is the difference between the scheduler and the dispatcher? Why is dispatch latency a cost that every scheduling policy must account for?

Show answer

The scheduler is the component that decides which process or thread should run next. The dispatcher is the component that actually performs the switch: it saves the state of the outgoing process, loads the state of the incoming one, and transfers control. The time the dispatcher takes is the dispatch latency, and it is pure overhead — no user-level work is done while it runs. Dispatch latency is a cost that every policy must account for because the scheduler runs on every context switch, and the number of switches depends on the policy. A policy that uses short time quanta performs more switches and therefore pays more total overhead, reducing effective CPU utilization. The approximate relationship is utilization = quantum / (quantum + switch_cost). A policy that uses long quanta pays less overhead but may delay response time. Every scheduling policy must therefore balance the benefit of the decisions it makes against the cost of the switches it causes. In modern systems the switch cost is small (microseconds against millisecond quanta), but the effect compounds because a switch also disrupts the CPU caches and the TLB, which can cost far more than the register save and restore itself.

08 Unit discussion

Discussion prompt

The scheduling criteria in this lesson were developed for general-purpose time-sharing systems in the 1960s and 1970s, when the dominant workload was a mix of interactive terminals and batch jobs on a single-core machine. The workloads and hardware of the 2020s are very different: many-core processors with heterogeneous cores, latency- sensitive network services, machine-learning training jobs that run for days, and mobile devices with strict energy budgets.

Which of the classical criteria still matter, and which have become less important? Are there criteria that should be added for modern systems — for example, energy efficiency, tail latency, or fairness across tenants in a shared cloud? How should a scheduler for a modern many-core server differ from the schedulers described in the textbook?

Post your response to the Unit 5 discussion forum and reply to at least two classmates. Supports CLO1, CLO2, and CLO3.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for the scheduling algorithms in Lessons 5.2–5.6 and for Lab 4. Aim to spend 60–90 minutes on it.

Compute the metrics. For the workload below, construct the Gantt chart and compute the completion, turnaround, waiting, and response times for each process under the order P₁, P₂, P₃, P₄. Then compute the same metrics under the order P₂, P₄, P₁, P₃. Report the averages and the maximum for each metric, and comment on which schedule you would prefer and why.

Process	Arrival	Burst
P₁	0	8
P₂	1	4
P₃	2	9
P₄	3	5

Measure the context-switch cost. Run the switch.c program from the interactive activity on your VM. Run it ten times and record the results. What is the mean and the standard deviation? What sources of noise do you think affect the measurement, and how would you reduce them? (Hint: consider CPU frequency scaling, other activity on the machine, and the cost of sched_yield itself.)
Compute effective utilization. Suppose a context switch costs 4 microseconds and the time quantum is (a) 1 ms, (b) 5 ms, (c) 20 ms. Compute the effective CPU utilization for each case using the formula from section 4.7. At what quantum does the overhead exceed one percent of the available CPU time? What does this suggest about the minimum practical quantum?
Classify a workload. Write a short program that creates two threads: one that performs a long arithmetic loop (CPU-bound), and one that repeatedly reads a small file from disk (I/O-bound). Run the program and use vmstat 1 and pidstat -t 1 to observe the behaviour of each thread. Which thread receives more CPU time? Which one has more context switches? Relate your observations to the I/O-bound vs CPU-bound distinction from section 4.2.
Experiment with nice. Run two CPU-intensive processes with different nice values — for example, 0 and 15 — and use ps -o pid,ni,pcpu to measure the share of CPU each receives. Repeat with nice values 0 and 5, and with 0 and 19. Plot or tabulate the relationship between the nice difference and the CPU share. Does the relationship appear linear, or does it saturate? Consult man 7 sched for the definition of how nice values map to scheduler weights.
Observe preemption. Write a program that runs an infinite loop printing a counter, and run it once in the foreground and once in the background with nice -n 19. While it is running, open another terminal and run a short interactive command such as ls -la /usr/bin. Is the interactive command responsive in both cases? Explain what the scheduler did.
Reflect. In your own words, describe the single most important trade-off in CPU scheduling, and explain why it cannot be resolved by a better algorithm. Give one example of a real system that resolves the trade-off in favour of each side.

10 Summary

CPU scheduling is the set of policies and mechanisms by which the operating system chooses which ready process or thread runs next, and for how long.
Scheduling is necessary because processes alternate between CPU bursts and I/O bursts. While a process waits on I/O, another can use the CPU; the scheduler's job is to maximize this overlap.
Processes are classified as I/O-bound (many short CPU bursts) or CPU-bound (a few long CPU bursts). The two classes have different scheduling needs, and a good scheduler balances them.
Non-preemptive scheduling lets a running process keep the CPU until it blocks or terminates; preemptive scheduling may interrupt it. Preemption improves responsiveness and fairness at the cost of extra context switches and synchronization care.
Scheduling occurs at three levels: long-term (admission), medium-term (swapping), and short-term (which ready process runs next). This unit is concerned with the short-term scheduler.
The standard criteria are CPU utilization, throughput, turnaround time, waiting time, response time, fairness, and predictability. Each is a goal, and the goals conflict.
The standard metrics are: turnaround = completion − arrival; waiting = turnaround − burst; response = first allocation − arrival; throughput = completed processes / elapsed time.
The dispatcher performs the context switch; its cost is pure overhead. Effective utilization is approximately quantum / (quantum + switch_cost).
Policy (which process to run) is separated from mechanism (the runqueue, timer interrupt, and context-switch code). Linux implements this separation through scheduling classes.
There is no single best scheduler. The trade-offs — throughput vs. response time, average vs. maximum, fairness vs. priority, utilization vs. predictability — are inherent in the problem, and the right balance depends on the workload.
Linux's general-purpose scheduler is the Completely Fair Scheduler (CFS), which divides CPU time among tasks in proportion to their weights. Other policies (SCHED_FIFO, SCHED_RR, SCHED_DEADLINE, SCHED_IDLE) serve real-time and specialized workloads.

Looking ahead

This lesson established the problem and the vocabulary. Lesson 5.2 begins the survey of algorithms with first-come, first-served — the simplest policy, and the one against which all others are measured. Lessons 5.3–5.5 introduce shortest-job-first, priority scheduling, and round robin. Lesson 5.6 examines multilevel queue scheduling and the Linux scheduler in detail. Lab 4 implements and evaluates several of these algorithms on a simulated workload.

11 References

Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 7 and 8. Available online at ostep.org.
Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Sections 5.1–5.3.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.4.
Love, R. Linux System Programming, 2nd ed., Chapter 3.
Linux man-pages: man 7 sched, man 2 sched_setscheduler, man 2 sched_setaffinity, man 1 nice, man 1 chrt, man 1 taskset.
POSIX.1-2017 / IEEE Std 1003.1, Standard for Information Technology — Portable Operating System Interface (POSIX), Section on Process Scheduling.