Process Scheduling Basics

01 Introduction

Most computers have far more processes than CPUs. Even a modest laptop has hundreds of processes running at any moment; a data-centre server may have thousands. At each instant, the operating system's scheduler decides which of the ready processes gets to use a CPU core, and for how long. This is one of the most consequential decisions the kernel makes — it determines the system's throughput, its responsiveness, its fairness, and the experience of every user interacting with it.

The scheduling problem has no single best answer. A batch system wants to complete as many jobs per hour as possible. An interactive system wants every keystroke to feel instantaneous. A real-time system must guarantee that operations complete by specific deadlines. A fair-share system wants each user to receive their promised slice of the machine. Every scheduler is a design in which some goals are favoured at the expense of others.

This lesson establishes the vocabulary of scheduling without yet presenting the specific algorithms. It defines the problem, describes the three levels at which scheduling decisions are made, introduces the metrics used to compare policies, and lays out the fundamental trade-offs. Unit 5 builds directly on this foundation — the algorithms it presents are all concrete responses to the problem and metrics defined here.

02 Learning objectives

This lesson contributes to U3.4 and to course learning outcomes CLO3 and CLO6. It prepares the ground for Unit 5.

03 Required reading

• Operating System Concepts — Chapter 5, Sections 5.1 and 5.2 (Basic Concepts and Scheduling Criteria). The classical introduction to the scheduling problem and the metrics used to evaluate it.
• OSTEP — Chapter 7, Scheduling: Introduction, especially the discussion of workload assumptions and metrics. OSTEP's treatment of the metrics is more explicit than the classical text.
• Love, R. — Linux Kernel Development, 3rd ed., Chapter 4 (Process Scheduling). The Linux perspective on why scheduling exists and what the kernel cares about.
• Linux man pages: man 7 sched (the overview of Linux's scheduling policies), man 1 nice, man 2 sched_setscheduler, man 1 chrt. These document the scheduling interface available from user space.

04 Core content

4.1 The scheduling problem

At its simplest, the scheduling problem is: given a set of ready processes and a limited number of CPUs, decide which process runs next on which CPU. The decision must be made repeatedly, at every moment when a CPU becomes available or a higher-priority process becomes ready.

Four things make this harder than it first appears:

1. Different workloads want different things. A batch compute job wants long uninterrupted time slices; an interactive terminal wants a quick response after every keystroke. A scheduler that is ideal for one is poor for the other.
2. The future is unknown. A scheduler cannot know in advance how long a process will run before blocking, or how soon a currently-blocked process will become ready. It must decide based on what it can observe.
3. The system changes continuously. Processes arrive and depart, block and unblock, in patterns that the scheduler cannot fully predict or control.
4. The decision has a cost. The scheduler runs on the very CPU it is allocating. Every cycle it spends deciding is a cycle no process is running. A policy that is theoretically optimal but computationally expensive may be worse in practice than a simpler approximate policy.

The rest of this lesson develops the vocabulary needed to reason about these trade-offs: what schedulers exist, when they run, what they try to achieve, and how to measure whether they succeed.

4.2 CPU–I/O burst behaviour

A useful empirical observation underpins most scheduling design: a process alternates between bursts of CPU activity and bursts of I/O activity. It computes for a while, then reads or writes, then computes again, and so on. The distribution of burst lengths is characteristically bimodal — most bursts are short (a few milliseconds) and a few are long.

Two extreme profiles capture the ends of the spectrum:

CPU-bound process

Spends most of its time computing, with occasional I/O to read input or write output. Scientific simulations, video transcoders, and compilers while they are parsing are examples. These processes benefit from long, uninterrupted time slices — each context switch is a small cost that matters less if the slice is long.

I/O-bound process

Spends most of its time waiting for I/O, with brief bursts of CPU activity to process the data that arrives. Shells waiting for input, web servers waiting for requests, and text editors while you are typing are examples. These processes benefit from being scheduled promptly after their I/O completes, so they can issue the next request and get back to waiting — a delay here wastes the device as well as the CPU.

Most real programs fall somewhere on the spectrum between these two extremes, and a single program's position may change over its lifetime. A compiler is CPU-bound while parsing and generating code, but becomes I/O-bound while reading source files and writing object files. A web server is I/O-bound during request handling but CPU-bound during a JSON parse.

This matters to the scheduler because the two profiles want different things. A scheduler that gives CPU-bound processes long slices and I/O-bound processes quick dispatch after blocking is doing the right thing for both. A scheduler that treats them identically will be mediocre at both. The classical observation is that a good scheduler should favour I/O-bound processes when they become ready — they will block again quickly, freeing the CPU for others while keeping the device busy.

4.3 The three levels of schedulers

Traditional operating-systems theory distinguishes three schedulers that operate on different timescales and manage different aspects of the process lifecycle. Modern general-purpose kernels often blur the boundaries — Linux implements the first as an implicit policy and the third as part of the memory manager — but the three-way distinction remains useful for understanding what "scheduling" means.

Long-term scheduler (job scheduler)

Decides which processes in the job pool are admitted into the ready queue. Runs infrequently — seconds or minutes between decisions. Its primary role is controlling the degree of multiprogramming: the number of processes resident in memory at once. On batch systems this matters a lot; on interactive and mobile systems it is often implicit, with every newly created process simply being admitted. Linux does not have a distinct long-term scheduler — when you run a program, it is admitted immediately unless a resource limit intervenes.

Short-term scheduler (CPU scheduler)

Decides which ready process runs on the CPU next. Runs very frequently — on the order of hundreds to thousands of times per second on a busy system. Its speed matters directly to system performance, because every microsecond it spends deciding is a microsecond no process is running. When textbooks or this course use the word "scheduler" unqualified, they almost always mean this one.

Medium-term scheduler

Decides which processes to swap out of memory (to a suspended state on disk) and which to bring back. Its purpose is to control memory pressure when the degree of multiprogramming exceeds what fits in physical memory. In modern systems this role is largely absorbed into the virtual-memory subsystem — the page-replacement policy discussed in Module 3 acts as a fine-grained version of what the medium-term scheduler used to do at process granularity.

4.4 When scheduling decisions are made

The short-term scheduler does not run continuously. It runs at specific points where a decision is required. There are exactly four such points in a general-purpose system:

1. When a running process blocks. The process issues a blocking system call (for example, read on a slow device) and moves from Running to Blocked. The CPU is now idle and must be given to another process. This is a voluntary scheduling event — the process chose to give up the CPU.
2. When a running process is preempted. The timer interrupt fires, or a higher-priority process becomes ready, and the kernel decides the current process should stop running. The process moves from Running to Ready. This is an involuntary event — the process did not ask to give up the CPU.
3. When a blocked process becomes ready. An I/O completion or a signal moves a process from Blocked to Ready. The scheduler may decide to preempt the current process in favour of the newly ready one, or may let the current process continue.
4. When a running process terminates. The process exits. The CPU is now idle and must be given to another process. This is again a voluntary event.

Two of these four events (blocking and termination) are initiated by the running process itself; they always require the scheduler to run because the CPU is genuinely idle. The other two (preemption and a blocked process becoming ready) are opportunities for the scheduler to run: it may choose to switch processes, or it may not.

4.5 Preemptive versus non-preemptive scheduling

This distinction is fundamental and worth stating explicitly.

Non-preemptive scheduling

Once a process is running, it continues until it voluntarily yields — by blocking on I/O, by exiting, or by explicitly giving up the CPU. The scheduler only runs when the running process asks for it. Simple, low-overhead, but vulnerable to a process that never yields: a CPU-bound process with no I/O will monopolise the CPU until it terminates.

Preemptive scheduling

The scheduler can interrupt a running process at any time, typically on a timer tick or when a higher-priority process becomes ready. Requires hardware support (a timer) and considerable care in the kernel, since kernel data structures may be in an inconsistent state when preemption occurs. Modern general-purpose kernels are preemptive.

The transition Running → Ready from Lesson 3.2 is only possible in a preemptive scheduler. In a non-preemptive scheduler, that transition does not exist — a process can only leave the Running state by blocking or terminating. This is one of the reasons the state diagram in Lesson 3.2 was drawn with preemption as an explicit transition: it is a design choice, not a universal property of all operating systems.

Preemption is what makes modern systems responsive. Without it, a single runaway process could freeze the machine for minutes. With it, the kernel can reclaim the CPU at a known maximum interval — typically every 1–10 ms — and give other processes a turn. The cost is the complexity of writing kernel code that is safe to preempt, and the overhead of the resulting context switches.

4.6 Scheduling metrics

To compare scheduling policies, we need quantitative measures. Five metrics appear throughout the literature, and each measures a different aspect of the scheduler's behaviour. No single policy optimises all of them, and understanding which one matters for a given workload is essential to reasoning about a scheduler's design.

4.7 Computing the metrics

For a process with submission time S, first-run time F, completion time C, and total CPU burst length B, the metrics are:

turnaround = C - S
waiting    = turnaround - B
response   = F - S

A small worked example will make these definitions concrete.

P1: starts 0, ends 8
P2: starts 8, ends 12
P3: starts 12, ends 14

Per-process metrics:

Process   Turnaround  Waiting  Response
  P1          8           0        0
  P2         12           8        8
  P3         14          12       12

Average turnaround = (8 + 12 + 14) / 3 = 11.33
Average waiting    = (0 + 8 + 12) / 3  = 6.67
Average response   = (0 + 8 + 12) / 3  = 6.67

P3: starts 0, ends 2
P2: starts 2, ends 6
P1: starts 6, ends 14

Process   Turnaround  Waiting  Response
  P1         14          6        6
  P2          6          2        2
  P3          2          0        0

Average turnaround = (14 + 6 + 2) / 3 = 7.33
Average waiting    = (6 + 2 + 0) / 3  = 2.67
Average response   = (6 + 2 + 0) / 3  = 2.67

4.8 Fundamental trade-offs

Every scheduling policy makes trade-offs among the metrics and between the two process classes. Three trade-offs are worth stating explicitly because they recur throughout the course.

These trade-offs are not incidental to scheduling design — they are the reason there is no universal "best" scheduler. Every policy makes choices, and every choice has consequences that show up in some metric.

4.9 Workload assumptions

Before evaluating a scheduler, it is worth being explicit about what the workload is assumed to look like. Formal analysis of scheduling algorithms relies on simplifying assumptions that make the problem tractable. The common ones are:

• Each job runs for the same amount of time.
• All jobs arrive at the same time.
• Once started, each job runs to completion (no preemption, no blocking).
• All jobs use only the CPU (no I/O).
• Run times are known in advance.

Real workloads violate every one of these assumptions. Jobs have wildly different durations, arrive at irregular times, block on I/O, and their future behaviour is unknown. The assumptions are useful as starting points — they let us prove what a scheduler can do under ideal conditions — but their violation is what makes scheduling an engineering problem rather than a mathematical one.

Unit 5 builds on this by presenting each algorithm with its assumptions stated explicitly. Seeing how a policy behaves when its assumptions are relaxed is one of the most valuable exercises in understanding why real systems make the choices they do.

4.10 How this connects to the PCB

Every one of these concepts has a concrete representation in the process control block from Lesson 3.3. The scheduling fields of the PCB are what the scheduler actually reads and writes on every decision:

• The state field determines whether a process is a scheduling candidate at all — only Ready processes are.
• Priority and nice values express the process's relative importance, encoding the fairness-versus- priority trade-off.
• Recent CPU usage (or virtual runtime, on Linux) is the scheduler's measure of how much of the CPU the process has had lately, used to determine fairness.
• Time slice remaining tracks how much of the current quantum is left before the timer will force preemption.
• Accounting fields such as nvcsw and nivcsw record how many times the process has been voluntarily or involuntarily switched, providing evidence of its workload profile.

When the scheduler runs, it is essentially reading these fields from every ready PCB, applying its policy, and updating the winning process's fields — plus a few others — to reflect the new state. The metric definitions and the policy design are abstractions over exactly this data flow.

4.11 Linux and the scheduling interface

Linux implements the concepts from this lesson with several specific scheduling policies and a user-visible interface for influencing them. The full picture belongs to Unit 5, but the high-level structure is worth previewing here.

Linux's scheduler supports several scheduling policies:

• SCHED_OTHER — the default, fair-share policy for ordinary processes. Implemented by the Completely Fair Scheduler (CFS), which we will examine in Unit 5.
• SCHED_BATCH — a variant of SCHED_OTHER for CPU-bound background work; the scheduler is slightly less eager to preempt these processes, favouring throughput over latency.
• SCHED_IDLE — the lowest priority; runs only when nothing else is runnable.
• SCHED_FIFO and SCHED_RR — real-time policies that run at a higher priority than any SCHED_OTHER process. The difference between them is whether a running real-time task can be preempted by another of the same priority (RR, with a time slice) or not (FIFO). These require CAP_SYS_NICE to set and are reserved for work that genuinely needs deterministic scheduling.
• SCHED_DEADLINE — a deadline-based policy in which each task declares its runtime, deadline, and period. The scheduler guarantees that tasks meet their deadlines if the system is schedulable at all.

From user space, the priority of a SCHED_OTHER process can be adjusted with nice and renice, and the policy of a process can be queried and changed with chrt or sched_setscheduler. The man pages for these tools are the practical entry point to the Linux scheduler.

# Show the scheduling policy and priority of a process
$ chrt -p $$
pid 4321's current scheduling policy: SCHED_OTHER
pid 4321's current scheduling priority: 0

# Run a command at a lower priority (higher nice value)
$ nice -n 10 some_cpu_intensive_command

# Change the policy of a running process (requires privileges for RT policies)
$ sudo chrt -f 50 -p 4321

The numbers that appear here — nice values, priorities, real- time priorities — are exactly the fields from the PCB that the scheduler reads on every decision. The interface exists so that users and administrators can influence the trade-offs this lesson has described.

05 Worked example

To make the metrics and the trade-offs concrete, compare three schedulers on the same workload and observe the different results.

P1: 0–10, P2: 10–12, P3: 12–18, P4: 18–19, P5: 19–23

Wait times:  0, 10, 12, 18, 19        avg = 11.8
Response:    0, 10, 12, 18, 19        avg = 11.8
Turnaround: 10, 12, 18, 19, 23        avg = 16.4

P4: 0–1, P2: 1–3, P5: 3–7, P3: 7–13, P1: 13–23

Wait times:  0, 1, 7, 3, 13           avg = 4.8
Response:    0, 1, 7, 3, 13           avg = 4.8
Turnaround:  1, 3, 7, 13, 23          avg = 9.4

P1: 0–10, P3: 10–16, P5: 16–20, P2: 20–22, P4: 22–23

Wait times:  0, 20, 10, 22, 16        avg = 13.6
Response:    0, 20, 10, 22, 16        avg = 13.6
Turnaround: 10, 22, 16, 23, 20        avg = 18.2

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• The scheduling problem: given a set of ready processes and limited CPUs, decide which runs next. No single best answer — different workloads want different things.
• Processes alternate between CPU bursts and I/O bursts. I/O-bound processes benefit from prompt scheduling after blocking; CPU-bound processes benefit from long time slices.
• Three levels of scheduler: long-term (admission), short-term (CPU dispatch), and medium-term (swapping). The short-term scheduler is what this course usually means by "scheduler."
• Scheduling decisions are made at four points: process blocks, process is preempted, blocked process becomes ready, process terminates.
• Preemptive schedulers can interrupt running processes; non-preemptive schedulers cannot. Modern general-purpose kernels are preemptive and require hardware timer support.
• Five metrics: CPU utilisation, throughput, turnaround time, waiting time, response time. Turnaround measures when a process finishes; response measures when it first produces output.
• Every scheduling policy trades among metrics and between process classes. The three fundamental trade-offs are throughput vs. latency, fairness vs. priority, and overhead vs. decision quality.
• Formal analysis assumes simplifying workloads that real systems violate. The assumptions are useful as starting points, but their violation is what makes scheduling an engineering problem.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Sections 5.1–5.2.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 7. Available online at ostep.org.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 4 (Process Scheduling). Addison-Wesley, 2010.
• Linux man-pages: man 7 sched, man 1 nice, man 1 renice, man 1 chrt, man 2 sched_setscheduler, man 5 proc (the sched file).
• Bach, M. J. The Design of the UNIX Operating System, Chapter 7. Prentice Hall, 1986. (Classical presentation of the three-level scheduler model.)