Lesson 1 · Processes, threads, and CPU scheduling

Process States and the PCB

A process is not always running. It moves through a small set of states, and the operating system records everything it needs to resume that process in one kernel structure — the process control block.

The Five-State Process Model

A process state records what a process is currently able to do. New covers the moment the kernel is building its structures — allocating a PID, an address space, and a process control block — before it is eligible to run at all.

Ready is the important one to get right: the process is completely runnable and is waiting for nothing except a free CPU. A machine with 400 ready processes and 8 cores is not broken; it is oversubscribed. Running means it is executing on a core right now, so the count of running processes can never exceed the core count.

Waiting (also called blocked) means the process cannot proceed until some event happens — a disk read completing, a lock being released, a packet arriving. A waiting process is not competing for the CPU, which is why a machine can have thousands of them and still feel idle.

Terminated means execution has finished but the kernel has not yet discarded the record. Some texts split new and terminated out and call it a two-state or seven-state model with suspended variants; the five above are the ones every real kernel implements.

The five states, what each means, and what moves a process out of it
State	Holds the CPU?	Waiting for	Leaves when
New	No	Kernel setup to finish	Admitted to the ready queue
Ready	No	A free CPU only	The scheduler dispatches it
Running	Yes	Nothing	Preempted, blocks, or exits
Waiting	No	An external event	The event completes → ready
Terminated	No	The parent to reap it	`wait` collects the exit status

New — the kernel is still building the process
Ready — runnable, waiting only for a core
Running — on a CPU now, capped by core count
Waiting — blocked on an event, not competing for CPU

Transitions Are What Matter

The states are trivia; the transitions carry the meaning. Admit moves new to ready once the kernel finishes setup. Dispatch moves ready to running and is the scheduler's only real decision.

Preempt moves running back to ready, and it is involuntary — the process was still perfectly able to run and got moved aside anyway, because its time slice expired or something higher-priority woke up. Nothing is wrong; this is normal and happens hundreds of times a second.

Block moves running to waiting and is entirely voluntary: the process asked for something that is not ready yet. It gives back the rest of its slice, which is exactly why schedulers learn to favour it. Wake moves waiting back to ready — note it does not go straight to running. The event finishing only makes it eligible again; the scheduler still has to pick it.

That last detail explains a common confusion. A disk read finishing does not resume your process instantly; it makes it ready, and it then waits its turn like everything else. On a loaded machine that queueing delay can dwarf the disk latency itself.

Dispatch is the scheduler's only genuine choice
Preempt is involuntary; block is the process asking
Waking goes to ready, never straight to running
Blocking early is rewarded because the slice is returned

Key reference

Terms, operations, and practical uses

The five states

NewThe kernel is still allocating a PID, address space, and PCB.
ReadyFully runnable, waiting only for a free CPU.
RunningExecuting on a core now — capped by the core count.
WaitingBlocked on an event; not competing for the CPU at all.

Transitions

DispatchReady to running — the scheduler's only real decision.
PreemptRunning to ready, involuntary, on a timer or a higher-priority wake.
BlockRunning to waiting, voluntary, returning the rest of the slice.
WakeWaiting to ready — never straight to running.

Inside the PCB

Saved contextProgram counter, stack pointer, and general registers.
Scheduling dataState, priority, accumulated runtime, current queue.
Memory mapPage-table base address and the segment layout.
ResourcesOpen descriptor table, working directory, signal handlers.

Code example

Follow one process through every state

# A tiny scheduler tracking one process through every state transition.
# The PCB is what survives each switch.
pcb = {'pid': 1, 'state': 'new', 'pc': 0, 'ran': 0}
log, switches, t = [], 0, 0

def to(state):
    global switches
    if pcb['state'] in ('running',) or state == 'running':
        switches += 1
    log.append((t, pcb['state'], state))
    pcb['state'] = state

to('ready')                       # admitted
to('running')                     # dispatched
for _ in range(2):                # two units of CPU
    t += 1
    pcb['pc'] += 1
    pcb['ran'] += 1
to('waiting')                     # blocked on I/O -- gives back the slice
t += 5                            # the device takes 5 units
to('ready')                       # woken: ready, NOT running
to('running')                     # dispatched again
t += 2
pcb['ran'] += 2
to('terminated')

print(f"P1 ran {2}, blocked, woke, finished at t={t} | switches {switches}")

#include <iostream>
#include <string>
using namespace std;
// A tiny scheduler tracking one process through every state transition.
// The PCB is what survives each switch.
struct PCB {
    int pid;
    string state;
    int pc;
    int ran;
};
PCB pcb {
    1, "new", 0, 0
};
int switches = 0, t = 0;
void to(const string& state) {
    if (pcb.state == "running" || state == "running") switches++;
    pcb.state = state;
}
int main() {
    to("ready"); // admitted
    to("running"); // dispatched
    for (int i = 0; i < 2; i++) {
        t++;
        pcb.pc++;
        pcb.ran++;
    }
    to("waiting"); // blocked on I/O -- gives back the slice
    t += 5; // the device takes 5 units
    to("ready"); // woken: ready, NOT running
    to("running"); // dispatched again
    t += 2;
    pcb.ran += 2;
    to("terminated");
    cout << "P1 ran 2, blocked, woke, finished at t=" << t
    << " | switches " << switches << "\n";
}

class Main {
    // A tiny scheduler tracking one process through every state transition.
    // The PCB is what survives each switch.
    static String state = "new";
    static int pc = 0, ran = 0, switches = 0, t = 0;
    static void to(String next) {
        if (state.equals("running") || next.equals("running")) switches++;
        state = next;
    }
    public static void main(String[] args) {
        to("ready"); // admitted
        to("running"); // dispatched
        for (int i = 0; i < 2; i++) {
            t++;
            pc++;
            ran++;
        }
        to("waiting"); // blocked on I/O -- gives back the slice
        t += 5; // the device takes 5 units
        to("ready"); // woken: ready, NOT running
        to("running"); // dispatched again
        t += 2;
        ran += 2;
        to("terminated");
        System.out.println("P1 ran 2, blocked, woke, finished at t=" + t
        + " | switches " + switches);
    }
}

InputP1 runs 2 units, blocks on I/O for 5, then finishes

OutputP1 ran 2, blocked, woke, finished at t=9 | switches 4

Example

Run the example step by step

Output

What the Process Control Block Stores

The process control block is the kernel's record of one process — task_struct on Linux, EPROCESS on Windows. It exists because a preempted process must be resumable months of CPU-time later as if nothing happened, so every scrap of state the hardware is about to overwrite has to live somewhere.

It holds identification (PID, parent PID, user and group IDs), the saved CPU context (program counter, stack pointer, general registers, flags), and scheduling data (state, priority, accumulated runtime, which queue it sits in).

It also holds memory-management information (the page-table base address, the memory map of segments), I/O state (the open file descriptor table, the working directory), and accounting (CPU time used, limits, signal handlers and their dispositions).

The size is not trivial — a Linux task_struct runs to a few kilobytes — which is one concrete reason threads are cheaper than processes: threads in one process share the memory map and the descriptor table rather than duplicating them.

PCB contents, grouped as an exam answer should group them
Group	Fields	Why it must be saved
Identification	PID, parent PID, user and group IDs	Ownership and permission checks
CPU context	Program counter, stack pointer, registers, flags	The hardware overwrites these on a switch
Scheduling	State, priority, accumulated runtime, queue	The scheduler's next decision needs them
Memory	Page-table base address, segment layout	Restores the correct address space
Resources	Open file descriptors, working directory, signals	Held across the process's whole lifetime

Identity: PID, parent, owner
Context: program counter, stack pointer, registers
Scheduling: state, priority, accumulated runtime
Resources: page-table base, open descriptors, signal handlers

The Context Switch, Step by Step

A context switch is the PCB doing its job. A timer interrupt or a blocking call enters the kernel, the current registers are copied into the running process's PCB, and its state is changed from running to ready or waiting.

The scheduler then picks a successor, loads that process's saved registers out of its PCB, switches the address space by reloading the page-table base register, and returns to user mode. The restored process resumes at the exact instruction it was interrupted on, with no way to detect the gap.

The direct cost is small — a few microseconds of copying. The indirect cost is much larger: the new process finds caches full of its predecessor's data, so it takes thousands of cold misses to warm back up, and the TLB may have been flushed unless the hardware supports address-space tags.

This is measurable and worth knowing: switching between threads of one process is significantly cheaper than between processes, because the address space does not change and the TLB survives intact.

Save registers into the outgoing PCB
Scheduler selects the next runnable process
Load the incoming PCB and swap the address space
Cache and TLB damage costs more than the copying

Queues, Zombies, and Orphans

The kernel does not scan every process to find work. Ready processes sit in a ready queue (per-core run queues on modern kernels), and each blocking condition has its own wait queue — one per disk request, one per lock, one per socket. Waking a process is moving its PCB from a wait queue to a run queue.

Termination has a subtlety worth knowing before you meet it in ps output. When a process exits, its memory and descriptors are released immediately, but the PCB stays — holding just the exit status and PID — until the parent calls wait. That corpse is a zombie, shown as state Z. It consumes no memory to speak of, but it holds a PID, and a parent that never reaps will eventually exhaust the PID space.

The mirror case is an orphan: the parent dies first, so the child is re-parented to init (PID 1), which reaps automatically. Orphans are harmless; zombies are the leak.

One more state confuses people the first time: uninterruptible sleep (state D) is a process blocked mid-way through a device operation the kernel cannot safely abandon. kill -9 does not touch it, because there is no correct point to unwind from. Persistent D state almost always means failing storage rather than a stuck program.

Ready queues hold runnable work; wait queues hold blocked work
A zombie is an unreaped exit status, and it holds a PID
An orphan is re-parented to init and reaped automatically
State D ignores kill -9 — usually a hardware symptom