Operating Systems Module 2 – Processes: creation, life cycle, signals and IPC
The process: address space, PCB and states
What a process is and what the kernel keeps for it: the regions of its address space, its process control block, and the five- and seven-state models.
What you will learn
- Distinguish a program from a process, and a process from a thread
- Draw the regions of a process address space and say what each one holds
- Describe what a process control block holds, with Linux's task_struct as the example
- Trace a process through the five- and seven-state models, and refuse the moves they do not allow
- Read a process's memory map, with /proc/<pid>/maps on Linux and vmmap on macOS
Before you start
What you’ll learn · Before you start
What you will learn
- Distinguish a program from a process, and a process from a thread
- Draw the regions of a process address space and say what each one holds
- Describe what a process control block holds, with Linux's task_struct as the example
- Trace a process through the five- and seven-state models, and refuse the moves they do not allow
- Read a process's memory map, with /proc/<pid>/maps on Linux and vmmap on macOS
Before you start
On this page
A program file on disk does nothing until the kernel runs it, and every run is a new process: on the machine behind this lesson, two more runs of one program put its code at different addresses, and a child process that set a variable to 3 left its parent’s copy at 2. A process: A running program together with what the kernel keeps for it: an address space, saved registers, open files and an owner. Each process runs as if it had the computer to itself. More in “What an operating system does” is a running program together with everything the kernel keeps to run it: an address space, saved registers, open files, an owner and a state.
This lesson takes a process apart. It separates programs, processes and threads, maps the regions of an address space from the code up to the stacks, opens the record in which the kernel keeps each process, and follows processes through the five-state and seven-state models in a program that runs in 14 languages. It ends with reading the memory map of a live process on Linux and on macOS.
A program is a file, and a process is that file running
A program is a file of machine code and data, such as /bin/ls. Nothing happens until the kernel creates a process to
run it, and it can create many from the same file at once: two terminals running ls are two processes, each with its
own memory, its own process ID and its own entries in the kernel’s tables. POSIX defines a
thread: One flow of control inside a process, with its own program counter, registers and stack. The threads of one process share its address space and its open files. as “a single flow of control within a process”, and a live process like this:
An address space with one or more threads executing within that address space, and the required system resources for those threads.
So the thread is the part that runs, with its own program counter, registers and stack, and the process is what the
threads run in: one address space and the resources the kernel gave it, open files among them. The program below shows
the difference with a single global variable. A second thread of the same process changes it, and the first thread sees
the change. Then fork, which the lesson after next covers, creates a second process with a copy of the memory, and the
child changes only its copy:
#include <pthread.h>
#include <stdio.h>
#include <sys/wait.h>
#include <unistd.h>
static int shared = 1; // one global variable of the program
static void *second_thread(void *unused) {
(void)unused;
shared = 2; // another thread of the same process writes it
return NULL;
}
int main(void) {
printf("at the start, shared is %d\n", shared);
pthread_t thread;
if (pthread_create(&thread, NULL, second_thread, NULL) != 0) {
perror("pthread_create");
return 1;
}
pthread_join(thread, NULL);
printf("a second thread set it to 2; the first thread now reads %d\n",
shared);
fflush(stdout); // empty the buffer, so the child does not print it again
pid_t pid = fork(); // a second process, with a copy of the memory
if (pid < 0) {
perror("fork");
return 1;
}
if (pid == 0) {
shared = 3;
printf("a child process set its copy to %d\n", shared);
return 0;
}
waitpid(pid, NULL, 0);
printf("after the child exited, the parent still reads %d\n", shared);
return 0;
}Output
at the start, shared is 1 a second thread set it to 2; the first thread now reads 2 a child process set its copy to 3 after the child exited, the parent still reads 2
Recorded with Apple clang version 21.0.0 (clang-2100.3.34.2) on macOS 26 arm64. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined share_or_copy.c -o share_or_copy && ./share_or_copy
The second thread’s write reached the first thread, because both threads use the same memory. The child’s write went into the child’s own copy, so the parent still read 2 after the child had exited. Threads of one process share an address space; separate processes do not, unless they ask the kernel for shared memory explicitly.
| Aspect | Program | Process | Thread |
|---|---|---|---|
| What it is | A file of code and data | A running instance of a program | One flow of control inside a process |
| Has its own | Nothing while it runs | An address space, open files, a process ID, an owner | A program counter, registers and a stack |
| Shares with others | Its file, with every process that runs it | Nothing, unless it maps shared memory | Its process’s address space and open files |
| Example | /bin/ls on the disk |
Each running ls |
Each worker thread of a web server |
Checkpoint
Check: Programs, processes and threads
An address space is a set of regions, each with its own job
Every address a process uses falls in some region the kernel set up for it, and each region holds one kind of thing, with permissions to match: code may be read and executed but not written, data may be read and written but not executed. Drawn with the highest addresses at the top, the usual layout is:
The usual regions of an address space, highest addresses at the top
Text description of the diagram
The figure is a single column of eight boxes. Addresses grow from the bottom of the column to the top.
- At the bottom is the code, also called the text: the program's machine instructions.
- Above it is the read-only data: string literals and constants.
- Then the data: global and static variables that start with a value written in the program file.
- Then the BSS: globals that start at zero, for which the file records only the size.
- Then the heap, where malloc, new and Box allocate memory while the program runs; it grows upwards as it is used.
- Then the mappings: shared libraries, files mapped with mmap and other mapped memory.
- Then the stacks, one for each thread, which hold local variables and the frames of the calls in progress; the main thread's stack grows downwards.
- At the top is the kernel, which a program running in user mode cannot reach at all.
The order is the common convention, not a rule: the lesson's recorded run on macOS shows the shared libraries above the stacks.
Read it from the bottom. The code (also called the text) holds the machine instructions. Read-only data holds string
literals and constants. The data region holds globals that start with a value, copied from the program file, and the
BSS: The part of a program's global data that starts at zero. The program file records only its size, and the kernel provides zero-filled pages for it when the program starts. holds globals that start at zero, which cost nothing in the file because the kernel supplies
zero-filled pages. The heap: The region of an address space from which a program allocates memory while it runs, with malloc, new or Box. It grows as the program asks for more. serves malloc, new and Box, and grows as the program asks for
more. The mappings hold shared libraries and files mapped with mmap. Each thread has a stack for its local variables
and the calls in progress. Above them all is the kernel, which user mode cannot reach: on x86-64 Linux with four-level
page tables, the kernel’s documentation puts user space at the lowest 128 TB of addresses, “different per mm”, that is,
for each address space.
This Rust program prints the address of one item from each region. It also starts itself twice more to see whether its
code moves, and checks whether the system has Linux’s /proc/self/maps:
use std::path::Path;
use std::process::Command;
use std::sync::atomic::{AtomicU32, Ordering};
use std::thread;
static GREETING: &str = "hello"; // its bytes are read-only data
static SET_TO_SEVEN: AtomicU32 = AtomicU32::new(7); // writable data, stored in the file
static LEFT_AT_ZERO: AtomicU32 = AtomicU32::new(0); // writable, zero: no bytes in the file
unsafe extern "C" {
safe fn getpid() -> i32; // a C library function, in a shared library
}
fn show(what: &str, address: usize) {
println!("{what:<34} {address:#014x}");
}
fn main() {
if std::env::args().nth(1).as_deref() == Some("main-only") {
println!("{:#x}", main as fn() as usize);
return;
}
let local = 1u8;
let boxed = Box::new(2u8);
SET_TO_SEVEN.fetch_add(LEFT_AT_ZERO.load(Ordering::Relaxed), Ordering::Relaxed);
show("code: the function main", main as fn() as usize);
show(
"read-only data: a string literal",
GREETING.as_ptr() as usize,
);
show(
"data: a global set to 7",
&SET_TO_SEVEN as *const AtomicU32 as usize,
);
show(
"bss: a global left at 0",
&LEFT_AT_ZERO as *const AtomicU32 as usize,
);
show("heap: a Box", &*boxed as *const u8 as usize);
show(
"shared library: getpid",
getpid as extern "C" fn() -> i32 as usize,
);
show("stack: a local of main", &local as *const u8 as usize);
let other = thread::spawn(|| {
let local = 3u8;
&local as *const u8 as usize
});
show(
"stack: a local of a second thread",
other.join().unwrap_or(0),
);
// ASLR: start this program twice more and compare where main landed.
let exe = std::env::current_exe().ok();
let where_main = || {
exe.as_ref()
.and_then(|e| Command::new(e).arg("main-only").output().ok())
};
let (first, second) = (where_main(), where_main());
let moved = matches!((&first, &second), (Some(a), Some(b)) if a.stdout != b.stdout);
println!(
"two more runs put main at different addresses: {}",
if moved { "yes" } else { "no" }
);
let maps = Path::new("/proc/self/maps").exists();
println!(
"this system has /proc/self/maps: {}",
if maps { "yes" } else { "no" }
);
}Output
code: the function main 0x0001048d15b8 read-only data: a string literal 0x0001049144e1 data: a global set to 7 0x000104928350 bss: a global left at 0 0x000104928ec0 heap: a Box 0x0001050657f0 shared library: getpid 0x0001900c4178 stack: a local of main 0x00016b52f1bf stack: a local of a second thread 0x00016b736ebf two more runs put main at different addresses: yes this system has /proc/self/maps: no
This output changes from run to run: the kernel places every region at a different address on every run
Recorded with rustc 1.99.0 (b940084d7) on macOS 26 arm64. To run it yourself: rustc --edition 2024 -O where_things_live.rs && ./where_things_live
The recorded run follows the picture for the program’s own image: the code, the literal, the global set to 7 and the
global left at 0 lie within about 350 KB of one another, in that order from low to high, all of them parts of the
program file mapped into memory. The heap block lay about 7 MB above them. The two stacks are separate regions, near
0x16b52f1bf, with the second thread’s about 2 MB above the main thread’s. getpid, in a shared library, was at
0x1900c4178, above both stacks: the usual picture is a convention, and on this Mac the shared libraries sat above the
stacks rather than below them.
Two more runs put main at different addresses. That is address space layout randomisation (ASLR): Placing a program's code, stack, heap and shared libraries at addresses that change from run to run, so that an attacker cannot know them in advance.:
the kernel picks new places for the regions on every run, so that an attack cannot rely on knowing where anything is.
Linux’s documentation for randomize_va_space lists what each level moves: at 1, the stack, the base of the mappings
and the vDSO, and so the shared libraries; at 2, the default for a kernel built without CONFIG_COMPAT_BRK, the heap
as well. It is also why this
page compares the recorded run with a pattern: no two runs print the same addresses.
Treating an address as a fact about the program
An address printed in one run says where that region was placed in that run, nothing more. A test that compares printed addresses fails on the next run, and code that stores them for later breaks after a restart. Compare what stays the same instead: which region an address falls in, or its distance from the start of its own region.
Checkpoint
Check: The regions of an address space
The process control block: what the kernel keeps for each process
The kernel’s record of a process is its process control block (PCB): The kernel's record of one process: its IDs, its state, its saved registers, its scheduling data, its memory map, its open files, its credentials and its signals. Linux calls it task_struct., or PCB.
Everything the kernel needs to stop a process at any instruction, run it again later and clean up after it is kept
there or can be reached from it. On Linux the record is struct task_struct in include/linux/sched.h, and its members
make a good tour of what a PCB must hold:
| The PCB keeps | In Linux’s task_struct | What it is for |
|---|---|---|
| Identity | pid, tgid, real_parent, parent |
Who the process is, which thread group it belongs to, who created it, and which process receives its SIGCHLD |
| State | __state, exit_state, exit_code |
Whether it can run, is waiting or has exited, and how it ended |
| Saved registers | thread, the CPU-specific state |
Where and how to resume it after a context switch |
| Scheduling | se, prio, static_prio, sched_class |
When it runs next, and for how long |
| Memory | mm |
Its address space: the regions and the page tables |
| Open files | files |
Which descriptor numbers name which open files |
| Credentials | cred, real_cred |
Its user and group IDs, which decide what it may do |
| Signals | signal, sighand, blocked, pending |
Its handlers, the signals it blocks and the signals waiting to be delivered |
| Accounting | utime, stime, nvcsw, nivcsw |
The CPU time it used and how often it was switched out |
Linux keeps no separate structure for a thread. Each thread is a task_struct of its own, with its own registers, stack
and state, and the threads of one process point at one shared mm and one shared files table. The pid of a thread
is its own, while tgid names the thread group, which is what programs see as the process ID. That is the sharing the
first program showed, as data structures:
Linux keeps one task_struct per thread; threads of a process share its memory map and its open files
Text description of the diagram
The figure has two columns: task_structs on the left, the structures they point to on the right.
- The first task_struct has pid 501 and tgid 501, and holds its own registers, stack and state. It points at an mm_struct, the address space of process 501, and at a files_struct, the open files of process 501.
- The second task_struct has pid 502 and the same tgid, 501: it is a second thread of process 501. It also has its own registers, stack and state, and it points at the same mm_struct and the same files_struct as the first.
- The third task_struct has pid 610 and tgid 610: a different process. It points at an mm_struct and a files_struct of its own, which nothing else shares.
The two parent fields differ in purpose. The comments in sched.h call real_parent the “real parent process” and
parent the “recipient of SIGCHLD, wait4() reports”; for most processes both point at the same process, the one that
created it.
Key idea
A process can be stopped at any instruction and resumed later only because its PCB holds everything the CPU was using for it and everything the kernel gave it: its registers, its memory map, its open files and its state.
Checkpoint
Check: The process control block
Five states, and the moves a process may make
A process spends its life moving between a few states, and only some moves are allowed. The five-state model names them: new while the kernel creates the process, ready when it could run but has no CPU, running on a CPU, waiting (also called blocked) until something it asked for happens, and terminated once it has exited. Step through two processes, A and B, sharing one CPU:
The drawing shows the whole scene; its 13 steps are listed below.
Every step as text
- Two new processes. The kernel is creating processes A and B. Neither may run yet, because its address space and its process control block are still being set up.
- Both admitted. Both are admitted and join the ready queue. They could run now, but the machine has one CPU.
- A is dispatched. The scheduler dispatches A, the first process in the queue. The kernel loads A's saved registers, and A runs.
- B is refused. A dispatch of B is refused now. The one CPU is running A, and a second running process would need a second CPU.
- A waits for the disk. A asks to read from the disk and cannot go on until the data arrives, so it moves to waiting and gives the CPU up.
- B runs. The CPU is free, so B is dispatched. A process that waits uses no CPU time while it waits.
- No shortcut from waiting. A dispatch of A is refused while A waits, because no arrow leads from waiting to running. A has to become ready first.
- The read is done. The data arrives, and the kernel wakes A. A moves to ready, not to running, because B still has the CPU.
- B's time slice ends. The timer interrupt ends B's time slice. B has not finished, so it goes back to ready, behind A.
- A runs again. A is dispatched again and continues from the instruction after its read, with its registers as the kernel saved them.
- A exits. A finishes and exits. It is terminated now, and its parent can collect its exit status.
- B is dispatched. B is the only ready process left, and the CPU is idle, so B is dispatched.
- B exits. B exits too. Thirteen events moved the two processes from new to terminated, and two of the thirteen were refused.
Six events move a process: admit (new to ready), dispatch (ready to running), timeout (running back to ready, when the timer ends a time slice), wait (running to waiting, for a disk read or a lock), wake (waiting to ready, when the event happens) and exit (running to terminated). Two shortcuts are missing on purpose. A waiting process is never dispatched directly: when its data arrives it becomes ready, and a dispatch follows later. And one CPU runs one process at a time. The model below replays the same thirteen events in 14 languages and refuses every move that has no arrow, with the reason:
Python 3.14 · main.py
# The five-state model: for each state, the events that move a process on.
MOVES: dict[str, dict[str, str]] = {
"new": {"admit": "ready"},
"ready": {"dispatch": "running"},
"running": {"timeout": "ready", "wait": "waiting", "exit": "terminated"},
"waiting": {"wake": "ready"},
"terminated": {},
}
TRACE = [
("A", "admit"),
("B", "admit"),
("A", "dispatch"),
("B", "dispatch"),
("A", "wait"),
("B", "dispatch"),
("A", "dispatch"),
("A", "wake"),
("B", "timeout"),
("A", "dispatch"),
("A", "exit"),
("B", "dispatch"),
("B", "exit"),
]
def main() -> None:
names = ["A", "B"]
state = {name: "new" for name in names}
running: str | None = None # the process on the only CPU
for name, event in TRACE:
before = state[name]
after = MOVES[before].get(event)
if after is None:
print(f"{name}: {event} refused, {before} has no {event} move")
elif after == "running" and running is not None:
print(f"{name}: {event} refused, the CPU is running {running}")
else:
if before == "running":
running = None
if after == "running":
running = name
state[name] = after
print(f"{name}: {before} -> {after} ({event})")
print("in the end:", ", ".join(f"{name} {state[name]}" for name in names))
main()In Python: dict.get returns None for an event with no arrow, so one lookup finds the move or the refusal. The hint str | None says the CPU may be idle.
Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py
JavaScript Node 24 · main.mjs
// The five-state model: for each state, the events that move a process on.
const MOVES = {
new: { admit: "ready" },
ready: { dispatch: "running" },
running: { timeout: "ready", wait: "waiting", exit: "terminated" },
waiting: { wake: "ready" },
terminated: {},
};
const TRACE = [
["A", "admit"],
["B", "admit"],
["A", "dispatch"],
["B", "dispatch"],
["A", "wait"],
["B", "dispatch"],
["A", "dispatch"],
["A", "wake"],
["B", "timeout"],
["A", "dispatch"],
["A", "exit"],
["B", "dispatch"],
["B", "exit"],
];
const names = ["A", "B"];
const state = Object.fromEntries(names.map((name) => [name, "new"]));
let running = null; // the process on the only CPU
for (const [name, event] of TRACE) {
const before = state[name];
const after = MOVES[before][event];
if (after === undefined) {
console.log(`${name}: ${event} refused, ${before} has no ${event} move`);
} else if (after === "running" && running !== null) {
console.log(`${name}: ${event} refused, the CPU is running ${running}`);
} else {
if (before === "running") running = null;
if (after === "running") running = name;
state[name] = after;
console.log(`${name}: ${before} -> ${after} (${event})`);
}
}
console.log(`in the end: ${names.map((name) => `${name} ${state[name]}`).join(", ")}`);In JavaScript: A missing property is undefined, so MOVES[before][event] is either the move or undefined; null marks the idle CPU.
Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs
Java 25 LTS · Main.java
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Main {
// The five-state model: for each state, the events that move a process on.
static final Map<String, Map<String, String>> MOVES =
Map.ofEntries(
Map.entry("new", Map.of("admit", "ready")),
Map.entry("ready", Map.of("dispatch", "running")),
Map.entry("running", Map.of("timeout", "ready", "wait", "waiting", "exit", "terminated")),
Map.entry("waiting", Map.of("wake", "ready")),
Map.entry("terminated", Map.of()));
record Step(String name, String event) {}
static final List<Step> TRACE =
List.of(
new Step("A", "admit"),
new Step("B", "admit"),
new Step("A", "dispatch"),
new Step("B", "dispatch"),
new Step("A", "wait"),
new Step("B", "dispatch"),
new Step("A", "dispatch"),
new Step("A", "wake"),
new Step("B", "timeout"),
new Step("A", "dispatch"),
new Step("A", "exit"),
new Step("B", "dispatch"),
new Step("B", "exit"));
public static void main(String[] args) {
List<String> names = List.of("A", "B");
Map<String, String> state = new LinkedHashMap<>();
names.forEach(name -> state.put(name, "new"));
String running = null; // the process on the only CPU
for (Step step : TRACE) {
String name = step.name();
String event = step.event();
String before = state.get(name);
String after = MOVES.get(before).get(event);
if (after == null) {
System.out.println(
name + ": " + event + " refused, " + before + " has no " + event + " move");
} else if (after.equals("running") && running != null) {
System.out.println(name + ": " + event + " refused, the CPU is running " + running);
} else {
if (before.equals("running")) {
running = null;
}
if (after.equals("running")) {
running = name;
}
state.put(name, after);
System.out.println(name + ": " + before + " -> " + after + " (" + event + ")");
}
}
List<String> ends = names.stream().map(name -> name + " " + state.get(name)).toList();
System.out.println("in the end: " + String.join(", ", ends));
}
}In Java: Map.get returns null for an event with no arrow. Map.ofEntries keeps the table at one state a line, and a record holds each step of the trace.
Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java
C++23 · main.cpp
#include <map>
#include <optional>
#include <print>
#include <string>
#include <utility>
#include <vector>
// The five-state model: for each state, the events that move a process on.
const std::map<std::string, std::map<std::string, std::string>> MOVES = {
{"new", {{"admit", "ready"}}},
{"ready", {{"dispatch", "running"}}},
{"running",
{{"timeout", "ready"}, {"wait", "waiting"}, {"exit", "terminated"}}},
{"waiting", {{"wake", "ready"}}},
{"terminated", {}},
};
const std::vector<std::pair<std::string, std::string>> TRACE = {
{"A", "admit"}, {"B", "admit"}, {"A", "dispatch"}, {"B", "dispatch"},
{"A", "wait"}, {"B", "dispatch"}, {"A", "dispatch"}, {"A", "wake"},
{"B", "timeout"}, {"A", "dispatch"}, {"A", "exit"}, {"B", "dispatch"},
{"B", "exit"},
};
int main() {
const std::vector<std::string> names = {"A", "B"};
std::map<std::string, std::string> state;
for (const auto &name : names) {
state[name] = "new";
}
std::optional<std::string> running; // the process on the only CPU
for (const auto &[name, event] : TRACE) {
const std::string before = state[name];
const auto &moves = MOVES.at(before);
const auto found = moves.find(event);
if (found == moves.end()) {
std::println("{}: {} refused, {} has no {} move", name, event, before,
event);
} else if (found->second == "running" && running) {
std::println("{}: {} refused, the CPU is running {}", name, event,
*running);
} else {
const std::string &after = found->second;
if (before == "running") {
running.reset();
}
if (after == "running") {
running = name;
}
state[name] = after;
std::println("{}: {} -> {} ({})", name, before, after, event);
}
}
std::string ends;
for (const auto &name : names) {
ends += (ends.empty() ? "" : ", ") + name + " " + state[name];
}
std::println("in the end: {}", ends);
}In C++: find returns end() when the state has no arrow for the event, so the code checks it before it reads the move. std::optional holds the running process.
Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main
C# 14 · .NET 10 · app.cs
// The five-state model: for each state, the events that move a process on.
var moves = new Dictionary<string, Dictionary<string, string>>
{
["new"] = new() { ["admit"] = "ready" },
["ready"] = new() { ["dispatch"] = "running" },
["running"] = new() { ["timeout"] = "ready", ["wait"] = "waiting", ["exit"] = "terminated" },
["waiting"] = new() { ["wake"] = "ready" },
["terminated"] = new(),
};
(string Name, string Event)[] trace =
[
("A", "admit"),
("B", "admit"),
("A", "dispatch"),
("B", "dispatch"),
("A", "wait"),
("B", "dispatch"),
("A", "dispatch"),
("A", "wake"),
("B", "timeout"),
("A", "dispatch"),
("A", "exit"),
("B", "dispatch"),
("B", "exit"),
];
string[] names = ["A", "B"];
var state = names.ToDictionary(name => name, _ => "new");
string? running = null; // the process on the only CPU
foreach (var (name, @event) in trace)
{
var before = state[name];
if (!moves[before].TryGetValue(@event, out var after))
{
Console.WriteLine($"{name}: {@event} refused, {before} has no {@event} move");
}
else if (after == "running" && running is not null)
{
Console.WriteLine($"{name}: {@event} refused, the CPU is running {running}");
}
else
{
if (before == "running")
{
running = null;
}
if (after == "running")
{
running = name;
}
state[name] = after;
Console.WriteLine($"{name}: {before} -> {after} ({@event})");
}
}
var ends = names.Select(name => $"{name} {state[name]}");
Console.WriteLine($"in the end: {string.Join(", ", ends)}");In C#: event is a keyword in C#, so the variable is written @event. TryGetValue looks the move up and says whether there is one.
Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs
C23 · main.c
#include <stdio.h>
#include <string.h>
// The five-state model: the events that move a process from one state on.
typedef struct {
const char *from;
const char *event;
const char *to;
} Move;
static const Move MOVES[] = {
{"new", "admit", "ready"}, {"ready", "dispatch", "running"},
{"running", "timeout", "ready"}, {"running", "wait", "waiting"},
{"running", "exit", "terminated"}, {"waiting", "wake", "ready"},
};
typedef struct {
int process; // 0 is A, 1 is B
const char *event;
} Step;
static const Step TRACE[] = {
{0, "admit"}, {1, "admit"}, {0, "dispatch"}, {1, "dispatch"},
{0, "wait"}, {1, "dispatch"}, {0, "dispatch"}, {0, "wake"},
{1, "timeout"}, {0, "dispatch"}, {0, "exit"}, {1, "dispatch"},
{1, "exit"},
};
static const char *next_state(const char *from, const char *event) {
for (size_t i = 0; i < sizeof MOVES / sizeof MOVES[0]; i++) {
if (strcmp(MOVES[i].from, from) == 0 &&
strcmp(MOVES[i].event, event) == 0) {
return MOVES[i].to;
}
}
return NULL; // no such move
}
int main(void) {
const char names[] = {'A', 'B'};
const char *state[] = {"new", "new"};
int running = -1; // the process on the only CPU, or -1
for (size_t i = 0; i < sizeof TRACE / sizeof TRACE[0]; i++) {
const int p = TRACE[i].process;
const char *event = TRACE[i].event;
const char *before = state[p];
const char *after = next_state(before, event);
if (after == NULL) {
printf("%c: %s refused, %s has no %s move\n", names[p], event, before,
event);
} else if (strcmp(after, "running") == 0 && running != -1) {
printf("%c: %s refused, the CPU is running %c\n", names[p], event,
names[running]);
} else {
if (strcmp(before, "running") == 0) {
running = -1;
}
if (strcmp(after, "running") == 0) {
running = p;
}
state[p] = after;
printf("%c: %s -> %s (%s)\n", names[p], before, after, event);
}
}
printf("in the end: %c %s, %c %s\n", names[0], state[0], names[1], state[1]);
return 0;
}In C: C's standard library has no map, so the moves are an array that next_state searches in order, and NULL means no arrow. -1 marks the idle CPU.
Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main
PHP 8.5 · main.php
<?php
declare(strict_types=1);
// The five-state model: for each state, the events that move a process on.
const MOVES = [
'new' => ['admit' => 'ready'],
'ready' => ['dispatch' => 'running'],
'running' => ['timeout' => 'ready', 'wait' => 'waiting', 'exit' => 'terminated'],
'waiting' => ['wake' => 'ready'],
'terminated' => [],
];
const TRACE = [
['A', 'admit'],
['B', 'admit'],
['A', 'dispatch'],
['B', 'dispatch'],
['A', 'wait'],
['B', 'dispatch'],
['A', 'dispatch'],
['A', 'wake'],
['B', 'timeout'],
['A', 'dispatch'],
['A', 'exit'],
['B', 'dispatch'],
['B', 'exit'],
];
$names = ['A', 'B'];
$state = array_fill_keys($names, 'new');
$running = null; // the process on the only CPU
foreach (TRACE as [$name, $event]) {
$before = $state[$name];
$after = MOVES[$before][$event] ?? null;
if ($after === null) {
echo "{$name}: {$event} refused, {$before} has no {$event} move\n";
} elseif ($after === 'running' && $running !== null) {
echo "{$name}: {$event} refused, the CPU is running {$running}\n";
} else {
if ($before === 'running') {
$running = null;
}
if ($after === 'running') {
$running = $name;
}
$state[$name] = $after;
echo "{$name}: {$before} -> {$after} ({$event})\n";
}
}
$ends = array_map(fn(string $name): string => "{$name} {$state[$name]}", $names);
echo 'in the end: ' . implode(', ', $ends) . "\n";In PHP: ?? null turns a missing key into null without a warning, so a state with no arrow for the event gives null.
Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php
Rust 1.99 · main.rs
/// The five-state model: the state an event moves a process to, if it may move.
fn next_state(state: &str, event: &str) -> Option<&'static str> {
match (state, event) {
("new", "admit") => Some("ready"),
("ready", "dispatch") => Some("running"),
("running", "timeout") => Some("ready"),
("running", "wait") => Some("waiting"),
("running", "exit") => Some("terminated"),
("waiting", "wake") => Some("ready"),
_ => None,
}
}
const TRACE: [(usize, &str); 13] = [
(0, "admit"),
(1, "admit"),
(0, "dispatch"),
(1, "dispatch"),
(0, "wait"),
(1, "dispatch"),
(0, "dispatch"),
(0, "wake"),
(1, "timeout"),
(0, "dispatch"),
(0, "exit"),
(1, "dispatch"),
(1, "exit"),
];
fn main() {
let names = ['A', 'B'];
let mut state = ["new", "new"];
let mut running: Option<usize> = None; // the process on the only CPU
for (p, event) in TRACE {
let (name, before) = (names[p], state[p]);
match next_state(before, event) {
None => println!("{name}: {event} refused, {before} has no {event} move"),
Some("running") if running.is_some() => {
let busy = running.map_or('?', |r| names[r]);
println!("{name}: {event} refused, the CPU is running {busy}");
}
Some(after) => {
if before == "running" {
running = None;
}
if after == "running" {
running = Some(p);
}
state[p] = after;
println!("{name}: {before} -> {after} ({event})");
}
}
}
let ends: Vec<String> = names
.iter()
.zip(state)
.map(|(n, s)| format!("{n} {s}"))
.collect();
println!("in the end: {}", ends.join(", "));
}In Rust: The table is a match on (state, event) pairs, which gives None when no arm fits. A match guard refuses a dispatch while another process runs.
Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main
TypeScript 6.0 · main.ts
// The five-state model: for each state, the events that move a process on.
type State = "new" | "ready" | "running" | "waiting" | "terminated";
type Happening = "admit" | "dispatch" | "timeout" | "wait" | "wake" | "exit";
const MOVES: Record<State, Partial<Record<Happening, State>>> = {
new: { admit: "ready" },
ready: { dispatch: "running" },
running: { timeout: "ready", wait: "waiting", exit: "terminated" },
waiting: { wake: "ready" },
terminated: {},
};
const TRACE: [name: string, event: Happening][] = [
["A", "admit"],
["B", "admit"],
["A", "dispatch"],
["B", "dispatch"],
["A", "wait"],
["B", "dispatch"],
["A", "dispatch"],
["A", "wake"],
["B", "timeout"],
["A", "dispatch"],
["A", "exit"],
["B", "dispatch"],
["B", "exit"],
];
const names = ["A", "B"];
const state = new Map<string, State>(names.map((name) => [name, "new"]));
let running: string | null = null; // the process on the only CPU
for (const [name, event] of TRACE) {
const before = state.get(name) ?? "new";
const after = MOVES[before][event];
if (after === undefined) {
console.log(`${name}: ${event} refused, ${before} has no ${event} move`);
} else if (after === "running" && running !== null) {
console.log(`${name}: ${event} refused, the CPU is running ${running}`);
} else {
if (before === "running") running = null;
if (after === "running") running = name;
state.set(name, after);
console.log(`${name}: ${before} -> ${after} (${event})`);
}
}
console.log(`in the end: ${names.map((name) => `${name} ${state.get(name)}`).join(", ")}`);In TypeScript: Partial<Record<Happening, State>> lets each state list only its own events, so a lookup has the type State | undefined. Event is a name browsers already use, hence Happening.
Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts
Go 1.27 · main.go
package main
import (
"fmt"
"strings"
)
// The five-state model: for each state, the events that move a process on.
var moves = map[string]map[string]string{
"new": {"admit": "ready"},
"ready": {"dispatch": "running"},
"running": {"timeout": "ready", "wait": "waiting", "exit": "terminated"},
"waiting": {"wake": "ready"},
"terminated": {},
}
type step struct{ name, event string }
var trace = []step{
{"A", "admit"}, {"B", "admit"}, {"A", "dispatch"}, {"B", "dispatch"},
{"A", "wait"}, {"B", "dispatch"}, {"A", "dispatch"}, {"A", "wake"},
{"B", "timeout"}, {"A", "dispatch"}, {"A", "exit"}, {"B", "dispatch"},
{"B", "exit"},
}
func main() {
names := []string{"A", "B"}
state := map[string]string{"A": "new", "B": "new"}
running := "" // the process on the only CPU, or "" for none
for _, s := range trace {
before := state[s.name]
after, ok := moves[before][s.event]
switch {
case !ok:
fmt.Printf("%s: %s refused, %s has no %s move\n", s.name, s.event, before, s.event)
case after == "running" && running != "":
fmt.Printf("%s: %s refused, the CPU is running %s\n", s.name, s.event, running)
default:
if before == "running" {
running = ""
}
if after == "running" {
running = s.name
}
state[s.name] = after
fmt.Printf("%s: %s -> %s (%s)\n", s.name, before, after, s.event)
}
}
ends := make([]string, len(names))
for i, name := range names {
ends[i] = name + " " + state[name]
}
fmt.Println("in the end:", strings.Join(ends, ", "))
}In Go: A map lookup gives a second value, ok, which is false when the state has no arrow for the event. An empty string marks the idle CPU.
Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go
Swift 6.4 · main.swift
// The five-state model: for each state, the events that move a process on.
let moves: [String: [String: String]] = [
"new": ["admit": "ready"],
"ready": ["dispatch": "running"],
"running": ["timeout": "ready", "wait": "waiting", "exit": "terminated"],
"waiting": ["wake": "ready"],
"terminated": [:],
]
let trace: [(name: String, event: String)] = [
("A", "admit"), ("B", "admit"), ("A", "dispatch"), ("B", "dispatch"),
("A", "wait"), ("B", "dispatch"), ("A", "dispatch"), ("A", "wake"),
("B", "timeout"), ("A", "dispatch"), ("A", "exit"), ("B", "dispatch"),
("B", "exit"),
]
let names = ["A", "B"]
var state = ["A": "new", "B": "new"]
var running: String? = nil // the process on the only CPU
for (name, event) in trace {
let before = state[name, default: "new"]
guard let after = moves[before]?[event] else {
print("\(name): \(event) refused, \(before) has no \(event) move")
continue
}
if after == "running", let busy = running {
print("\(name): \(event) refused, the CPU is running \(busy)")
continue
}
if before == "running" {
running = nil
}
if after == "running" {
running = name
}
state[name] = after
print("\(name): \(before) -> \(after) (\(event))")
}
let ends = names.map { "\($0) \(state[$0, default: "new"])" }
print("in the end: \(ends.joined(separator: ", "))")In Swift: moves[before]?[event] is nil when there is no arrow, and guard let turns that into a refusal. state[name, default:] avoids an optional state.
Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main
Ruby 4.0 · main.rb
# frozen_string_literal: true
# The five-state model: for each state, the events that move a process on.
MOVES = {
'new' => { 'admit' => 'ready' },
'ready' => { 'dispatch' => 'running' },
'running' => { 'timeout' => 'ready', 'wait' => 'waiting', 'exit' => 'terminated' },
'waiting' => { 'wake' => 'ready' },
'terminated' => {}
}.freeze
TRACE = [
%w[A admit], %w[B admit], %w[A dispatch], %w[B dispatch],
%w[A wait], %w[B dispatch], %w[A dispatch], %w[A wake],
%w[B timeout], %w[A dispatch], %w[A exit], %w[B dispatch],
%w[B exit]
].freeze
names = %w[A B]
state = names.to_h { |name| [name, 'new'] }
running = nil # the process on the only CPU
TRACE.each do |name, event|
before = state[name]
after = MOVES[before][event]
if after.nil?
puts "#{name}: #{event} refused, #{before} has no #{event} move"
elsif after == 'running' && running
puts "#{name}: #{event} refused, the CPU is running #{running}"
else
running = nil if before == 'running'
running = name if after == 'running'
state[name] = after
puts "#{name}: #{before} -> #{after} (#{event})"
end
end
puts "in the end: #{names.map { |name| "#{name} #{state[name]}" }.join(', ')}"In Ruby: A Hash returns nil for a missing key, so a missing arrow and an idle CPU are both nil, and if and elsif test them in turn.
Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb
Kotlin 2.4 · Main.kt
// The five-state model: for each state, the events that move a process on.
val MOVES =
mapOf(
"new" to mapOf("admit" to "ready"),
"ready" to mapOf("dispatch" to "running"),
"running" to mapOf("timeout" to "ready", "wait" to "waiting", "exit" to "terminated"),
"waiting" to mapOf("wake" to "ready"),
"terminated" to mapOf(),
)
val TRACE =
listOf(
"A" to "admit",
"B" to "admit",
"A" to "dispatch",
"B" to "dispatch",
"A" to "wait",
"B" to "dispatch",
"A" to "dispatch",
"A" to "wake",
"B" to "timeout",
"A" to "dispatch",
"A" to "exit",
"B" to "dispatch",
"B" to "exit",
)
fun main() {
val names = listOf("A", "B")
val state = names.associateWith { "new" }.toMutableMap()
var running: String? = null // the process on the only CPU
for ((name, event) in TRACE) {
val before = state.getValue(name)
val after = MOVES.getValue(before)[event]
when {
after == null -> {
println("$name: $event refused, $before has no $event move")
}
after == "running" && running != null -> {
println("$name: $event refused, the CPU is running $running")
}
else -> {
if (before == "running") running = null
if (after == "running") running = name
state[name] = after
println("$name: $before -> $after ($event)")
}
}
}
println("in the end: " + names.joinToString(", ") { "$it ${state.getValue(it)}" })
}In Kotlin: getValue fails loudly for an unknown state, while [event] returns null for a missing arrow, which the when expression tests first.
Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
Dart 3.13 · main.dart
// The five-state model: for each state, the events that move a process on.
const moves = {
'new': {'admit': 'ready'},
'ready': {'dispatch': 'running'},
'running': {'timeout': 'ready', 'wait': 'waiting', 'exit': 'terminated'},
'waiting': {'wake': 'ready'},
'terminated': <String, String>{},
};
const trace = [
('A', 'admit'),
('B', 'admit'),
('A', 'dispatch'),
('B', 'dispatch'),
('A', 'wait'),
('B', 'dispatch'),
('A', 'dispatch'),
('A', 'wake'),
('B', 'timeout'),
('A', 'dispatch'),
('A', 'exit'),
('B', 'dispatch'),
('B', 'exit'),
];
void main() {
final names = ['A', 'B'];
final state = {for (final name in names) name: 'new'};
String? running; // the process on the only CPU
for (final (name, event) in trace) {
final before = state[name]!;
final after = moves[before]?[event];
if (after == null) {
print('$name: $event refused, $before has no $event move');
} else if (after == 'running' && running != null) {
print('$name: $event refused, the CPU is running $running');
} else {
if (before == 'running') running = null;
if (after == 'running') running = name;
state[name] = after;
print('$name: $before -> $after ($event)');
}
}
print(
'in the end: ${names.map((name) => '$name ${state[name]}').join(', ')}',
);
}In Dart: moves[before]?[event] is null when either key is missing, and the for loop takes each record of the trace apart with a pattern.
Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart
What every language printed
A: new -> ready (admit) B: new -> ready (admit) A: ready -> running (dispatch) B: dispatch refused, the CPU is running A A: running -> waiting (wait) B: ready -> running (dispatch) A: dispatch refused, waiting has no dispatch move A: waiting -> ready (wake) B: running -> ready (timeout) A: ready -> running (dispatch) A: running -> terminated (exit) B: ready -> running (dispatch) B: running -> terminated (exit) in the end: A terminated, B terminated
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 14 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 156 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 3 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 8 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads PHP (about 4.3 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 21 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 720 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 192 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 14 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
Both refusals are mistakes a scheduler must never make: B could not run while A held the only CPU, and A, waiting for its disk read, could not go straight back to running. In this model each refusal leaves the process where it was, which is the rule the exercise at the end asks you to keep.
Real kernels keep fewer, coarser states. Linux shows its own as single letters, in /proc/<pid>/stat and in ps. In
the words of ps(1), R is “running or runnable (on run queue)”, which covers both ready and running. S is a sleep that a
signal can interrupt, D one that it cannot, usually a wait for I/O, T is stopped, Z a zombie and I an idle kernel
thread.
| Five-state model | Linux state letter |
|---|---|
| new | none yet: the task is being set up |
| ready, running | R |
| waiting | S, or D |
| terminated | Z until its parent collects it; then the entry is gone |
Reading R as on a CPU
A process in state R is ready or running, not necessarily on a CPU. A 4-core machine whose ps lists nine processes
in R has at most four of them running at that instant; the other five are waiting for a core.
Checkpoint
Check: The five-state model
Two more states for processes moved out of memory
The five states assume that every process stays in memory. Early Unix moved whole processes out to disk instead: according to “A fork() in the road”, the first Unix fork, on the PDP-7, copied the running process out to swap and kept the child in memory. Moving a whole process out like that is swapping out: Moving all of a process's memory to disk to make room for others, and back again before it can run, as early Unix systems did. Today's systems mostly move single pages instead., and the seven-state model adds the two states a system that does it needs: ready, suspended, out of memory but able to run once it is brought back, and waiting, suspended, out of memory and still waiting. Follow A as memory runs short while it waits:
The drawing shows the whole scene; its 8 steps are listed below.
Every step as text
- A waits in memory. A waits for a slow device, and another process has the CPU. A's pages stay in memory, although A uses none of them while it waits.
- Memory runs short. Other processes need memory. The seven-state model adds two states for a process whose memory the kernel has moved out to disk.
- A is suspended. The kernel moves A's memory out to disk to make room. A is still waiting, but now it is waiting, suspended.
- The device finishes. The device finishes while A is out. A no longer waits, but its memory is still on disk, so it moves to ready, suspended, not to ready.
- No dispatch yet. A cannot be dispatched from here, because no arrow leads from a suspended state to running. Its memory has to come back first.
- A is activated. Memory is free again, and the kernel brings A's memory back in. A is ready, and the scheduler may pick it.
- A runs. A is dispatched and carries on after its device request, as if it had never left memory.
- Two more suspend arrows. A ready process can be suspended as well, and activate brings it back. In all, the model drawn here has eleven arrows, the six of the five-state model and five for the suspended states.
Three kinds of move come with the new states. Suspend sends a ready or waiting process out of memory, activate brings it back, and an event that happens while a process is out moves it from waiting, suspended to ready, suspended: it no longer waits, but it is still out. No arrow leads from a suspended state to running, so a suspended process is always activated before it runs. Today’s systems rarely move whole processes out; they move single pages, which the module on virtual memory covers. The model stays useful because it tests the rule of the previous section once more: every move needs an arrow.
GATE CS
The GATE 2027 syllabus for Computer Science lists system calls, processes and threads first in its Operating System section. The two state models of this lesson belong to that topic, and the exercise below applies the seven-state rules to traces.
Checkpoint
Check: The suspended states
Reading the memory map of a live process
Every region of the second section can be seen in a running process. On Linux, /proc/<pid>/maps has one line per
region, and /proc/self/maps is the map of the process that reads it, so cat /proc/self/maps prints the map of cat
itself. Here is a line in the format proc_pid_maps(5) documents, with each of its fields:
| Field | In the line 55d0f4a1c000-55d0f4a3d000 rw-p 00000000 00:00 0 [heap] |
What it means |
|---|---|---|
| address | 55d0f4a1c000-55d0f4a3d000 |
Where the region starts and ends |
| perms | rw-p |
Readable and writable, not executable; p is a private copy-on-write mapping, s a shared one |
| offset | 00000000 |
Where in the file the region starts |
| dev, inode | 00:00 0 |
The device and inode of the file behind it; 0 when no file backs it, as for the BSS |
| pathname | [heap] |
The file, or a pseudo-path: [heap], [stack], [vdso]; blank for an anonymous mapping made with mmap |
macOS has no /proc, as the last line of the Rust program reported. Its tool is vmmap, which Apple’s documentation
names among its command-line memory tools: vmmap <pid> prints the virtual memory regions of a process, from the
program’s text, which cannot be written, to writable regions such as its data and its heap, each with its start and
end address and its size in memory. vmmap $$ shows the regions of your own shell.
Checkpoint
Check: Reading a memory map
Practise: replay traces in the seven-state model
Write replay(trace), which plays a list of events through the seven-state model on one CPU and reports where every
process ends and which events were refused. The sample tests run in your browser, and the first one is the trace of the
model above:
Exercise · Easy · Python
Replay a trace in the seven-state model
A trace lists what happens to the processes of a machine with one CPU, as (process, event) pairs in order. Write replay(trace) in states.py for the seven-state model. It returns two things:
- a dict from each process to its state at the end, with the processes in the order the trace first names them;
- the list of the
(process, event)pairs that were refused, in order.
Every process is "new" when the trace first names it. The states are "new", "ready", "running", "waiting", "ready, suspended", "waiting, suspended" and "terminated", and these are the only moves:
| Event | Moves a process from | to | | --- | --- | --- | | admit | new | ready | | dispatch | ready | running, but only while no other process is running | | timeout | running | ready | | wait | running | waiting | | wake | waiting, or waiting, suspended | ready, or ready, suspended | | exit | running | terminated | | suspend | ready, or waiting | ready, suspended, or waiting, suspended | | activate | ready, suspended, or waiting, suspended | ready, or waiting |
Any other pair is refused and changes nothing. For example, [("A", "admit"), ("A", "wait")] ends with {"A": "ready"} and refuses [("A", "wait")]: a ready process is not running, so it cannot start to wait.
Starter code · states.py
def replay(trace):
"""The state of each process after the trace, and the (process, event) pairs that were refused."""
# Replace these lines with your code.
final = {}
refused = []
return final, refusedThe sample tests · test_states.py
from states import replay
LESSON = [
("A", "admit"),
("B", "admit"),
("A", "dispatch"),
("B", "dispatch"),
("A", "wait"),
("B", "dispatch"),
("A", "dispatch"),
("A", "wake"),
("B", "timeout"),
("A", "dispatch"),
("A", "exit"),
("B", "dispatch"),
("B", "exit"),
]
def test_the_lessons_trace():
"""replays the lesson's trace: both processes end terminated, and two dispatches are refused"""
final, refused = replay(LESSON)
assert final == {"A": "terminated", "B": "terminated"}
assert refused == [("B", "dispatch"), ("A", "dispatch")]
def test_suspended_while_waiting():
"""follows a process that is suspended while it waits and then woken while it is out"""
trace = [("A", "admit"), ("A", "dispatch"), ("A", "wait"), ("A", "suspend"), ("A", "wake")]
assert replay(trace) == ({"A": "ready, suspended"}, [])
trace += [("A", "activate"), ("A", "dispatch"), ("A", "exit")]
assert replay(trace) == ({"A": "terminated"}, [])
def test_no_dispatch_while_suspended():
"""refuses to dispatch a suspended process until it is activated"""
trace = [("A", "admit"), ("A", "suspend"), ("A", "dispatch"), ("A", "activate"), ("A", "dispatch")]
assert replay(trace) == ({"A": "running"}, [("A", "dispatch")])
def test_refused_moves_change_nothing():
"""leaves a process where it was when its event has no move"""
trace = [("A", "wake"), ("A", "exit"), ("A", "admit"), ("A", "admit")]
assert replay(trace) == ({"A": "ready"}, [("A", "wake"), ("A", "exit"), ("A", "admit")])
def test_the_cpu_is_freed():
"""frees the CPU when the running process waits, so another one can be dispatched"""
trace = [("A", "admit"), ("B", "admit"), ("A", "dispatch"), ("A", "suspend"), ("B", "dispatch")]
trace += [("A", "wait"), ("B", "dispatch")]
assert replay(trace) == ({"A": "waiting", "B": "running"}, [("A", "suspend"), ("B", "dispatch")])A hint
Keep the moves in a dict keyed by (state, event), such as ("waiting", "wake"): "ready", and keep the name of the running process in a variable. A dispatch needs two checks, the move and a free CPU; a process that leaves running frees the CPU.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Then test yourself on all six ideas of the lesson. The questions come one at a time, and the idea you have answered worst so far comes first:
Practice that adapts to you
Practise this lesson
14 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
The warm-up below comes with its full answer. Two harder questions from this lesson wait in the module’s question bank: a service whose virtual size is many times its memory use, and the fields a small kernel must keep for each process.
-
Fresher · Warm-up
What is the difference between a program, a process and a thread?
A program is a file of machine code and data on disk, such as /bin/ls. A process is one running instance of a program: the kernel gives it an address space, a process ID, open files and credentials, so two runs of ls are two processes with separate memory. A thread is one flow of control inside a process, with its own program counter, registers and stack. The threads of a process share its address space and its open files, so passing data between them is cheap and one thread's bad write reaches all of them. In the lesson's program, a second thread's write to a global was seen by the first thread, while a child process's write changed only the child's copy. A good answer adds the trade-off: threads are cheaper to create and switch, while processes keep failures apart.
Key takeaways
- A program is a file and a process is a running instance of it, with an address space, resources and one or more threads; threads of one process share its memory, while separate processes do not.
- An address space is a set of regions: code, read-only data, data, BSS, heap, mappings and one stack per thread, with the kernel above; ASLR places them anew on every run, and on the recorded Mac the shared libraries sat above the stacks.
- The PCB, Linux’s task_struct, holds a process’s identity, state, saved registers, scheduling data, memory map, open files, credentials, signals and accounting, and Linux threads are task_structs that share one memory map and one file table.
- The five-state model allows six moves: a waiting process becomes ready before it can run again, one CPU runs one process at a time, and Linux merges ready and running into R.
- The seven-state model adds ready, suspended and waiting, suspended for processes moved out of memory, which must be activated before they can run.
/proc/<pid>/mapson Linux lists the regions of a live process with their addresses, permissions and backing files, andvmmaplists them on macOS.
Terms in this lesson
- address space layout randomisation (ASLR)
- Placing a program's code, stack, heap and shared libraries at addresses that change from run to run, so that an attacker cannot know them in advance.
- BSS
- The part of a program's global data that starts at zero. The program file records only its size, and the kernel provides zero-filled pages for it when the program starts.
- heap
- The region of an address space from which a program allocates memory while it runs, with malloc, new or Box. It grows as the program asks for more.
- process control block (PCB)
- The kernel's record of one process: its IDs, its state, its saved registers, its scheduling data, its memory map, its open files, its credentials and its signals. Linux calls it task_struct.
- swapping out
- Moving all of a process's memory to disk to make room for others, and back again before it can run, as early Unix systems did. Today's systems mostly move single pages instead.
- thread
- One flow of control inside a process, with its own program counter, registers and stack. The threads of one process share its address space and its open files.
References
- POSIX.1-2024 Base Definitions, chapter 3: Definitions (3.189 Live Process, 3.190 Live Thread) (The Open Group and IEEE)
- POSIX.1-2024: fork, create a new process (The Open Group and IEEE)
- POSIX.1-2024: pthread_create, thread creation (The Open Group and IEEE)
- proc_pid_maps(5): mapped memory regions (Linux man-pages project (man7.org))
- ps(1): report a snapshot of the current processes (process state codes) (Linux man-pages project (man7.org))
- proc_pid_stat(5): status information about the process (Linux man-pages project (man7.org))
- Linux include/linux/sched.h: struct task_struct (The Linux Kernel Organization (source code))
- Documentation for /proc/sys/kernel/: randomize_va_space (The Linux Kernel Organization)
- Memory management on x86-64: the virtual memory map (The Linux Kernel Organization)
- Gathering information about memory use (vmmap and leaks) (Apple Developer Documentation)
- iOS Memory Deep Dive (WWDC18 session 416): what vmmap prints (Apple Developer)
- A fork() in the road (HotOS 2019) (ACM (Baumann, Appavoo, Krieger and Roscoe))
- Computer Science Curricula 2023: Operating Systems knowledge area (Version Gamma) (ACM, IEEE Computer Society and AAAI (CS2023 Task Force))
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Report a problem with this lesson
Kept only in this browser. Your Learn progress