Process State and the Lifecycle

A process (see The Process Abstraction) is a program in execution, with its own memory image, registers, and execution context. At any given moment, a process is doing exactly one of a small number of things, and the operating system labels this with a process state. The canonical model, used in essentially every textbook and every real kernel in some form, has five states:

• New: the process is being created — its address space is being set up, but it has not yet been admitted to the pool of processes competing for the CPU.
• Ready: the process is loaded into main memory, has everything it needs to run, and is simply waiting for the scheduler to assign it a CPU.
• Running: the process's instructions are actively being executed by a CPU core. On a single-core machine, at most one process is running at any instant; on an $n$-core machine, at most $n$ processes are.
• Waiting (also called blocked): the process cannot proceed until some event occurs — most commonly the completion of an I/O operation, the availability of a lock, or a signal from another process.
• Terminated (also called exit or zombie, depending on cleanup stage): the process has finished execution, but the OS may still be holding onto its exit status and resources until a parent process collects them.

The crucial structural fact is that transitions between these states are not arbitrary: they form a directed graph where each edge is labeled by exactly one triggering event. A running process cannot jump straight to ready — it must first be preempted by the scheduler. A waiting process cannot jump straight to running — it must first pass through ready and be dispatched. This restriction is what makes the model tractable: the scheduler only ever needs to reason about processes currently in the ready state, and the I/O subsystem only ever needs to reason about processes currently in the waiting state. Each subsystem owns exactly one state's worth of processes at a time.

The kernel maintains, for each process, a Process Control Block (PCB) — a data structure holding the process's state label, saved registers, program counter, memory pointers, and scheduling metadata (this structure is developed in full elsewhere, but its role as "the box that stores the state" is essential here). Processes in the same state are typically threaded together on a queue: a single ready queue, and typically one or more wait queues (often one per device or resource type). The five states and their governing transitions are: 1. new → ready ("admit"): the OS finishes creating the process (allocating a PCB, setting up its address space) and places it on the ready queue. 2. ready → running ("dispatch"): the scheduler selects this process (by whatever scheduling policy — FCFS, round robin, priority, etc.) and the dispatcher performs a context switch onto it. 3. running → ready ("preempt" or "timeout"): the process is still runnable but the OS takes the CPU away from it — typically because a timer interrupt fires (time-sharing) or a higher-priority process becomes ready. 4. running → waiting ("block"): the process issues a blocking request (e.g., a `read()` system call to disk, waiting on a semaphore) that cannot complete immediately. 5. waiting → ready ("wake up"): the event the process was waiting for occurs (I/O completes, lock is released), and the OS moves it back onto the ready queue — not directly to running. 6. running → terminated ("exit"): the process calls `exit()`, returns from `main`, or is killed by a signal. Every legal transition is one of these six edges. There is deliberately no edge directly from waiting to running, and no edge directly from ready to waiting — a process must always become the running process before it can decide to block, and must always pass through ready before it can run again after waking up. This is not an arbitrary restriction; it reflects the physical reality that only the currently-executing process can issue the system call that blocks it, and only the scheduler (acting on ready processes) decides who gets a CPU. ```pseudocode // Global data structures maintained by the kernel ReadyQueue : queue of PCB // FIFO or priority queue, policy-dependent WaitQueue[dev] : queue of PCB // one queue per device/resource, simplified here AllProcesses : map from PID to PCB // --- Transition 1: new -> ready --- function CREATE_PROCESS(program): pcb = new PCB() pcb.pid = fresh_pid() pcb.state = NEW allocate_address_space(pcb, program) load_initial_registers(pcb, program.entry_point) pcb.state = READY ReadyQueue.enqueue(pcb) return pcb.pid // --- Transition 2: ready -> running --- function DISPATCH(): if ReadyQueue.is_empty(): run_idle_process() return next = ReadyQueue.dequeue() // policy decides which PCB (FCFS, priority, ...) next.state = RUNNING context_switch_to(next) // save old registers, load next's registers // --- Transition 3: running -> ready (timer preemption) --- function ON_TIMER_INTERRUPT(current): current.state = READY ReadyQueue.enqueue(current) DISPATCH() // --- Transition 4: running -> waiting (blocking syscall) --- function ON_BLOCKING_SYSCALL(current, device): current.state = WAITING WaitQueue[device].enqueue(current) issue_io_request(device, current) DISPATCH() // CPU must go to someone else // --- Transition 5: waiting -> ready (I/O completion interrupt) --- function ON_IO_COMPLETE(device): pcb = WaitQueue[device].dequeue() pcb.state = READY ReadyQueue.enqueue(pcb) // Note: pcb does NOT become RUNNING here directly. // It waits its turn like any other ready process. // --- Transition 6: running -> terminated --- function ON_EXIT(current, exit_code): current.state = TERMINATED current.exit_code = exit_code release_resources(current) // free memory, close file descriptors notify_parent(current) // parent may wait() to collect status DISPATCH() ``` Two invariants are worth naming explicitly, because they are what a correctness argument will lean on:

• Single-occupancy invariant: on a machine with $n$ CPU cores, at most $n$ PCBs have `state = RUNNING` at any instant.
• Queue-membership invariant: a PCB is on exactly one queue (ready queue, or exactly one wait queue) whenever its state is ready or waiting, and on no queue when it is running, new, or terminated.

Time complexity of a single transition. Each transition function above does $O(1)$ work aside from the queue operation itself: updating `pcb.state` is a single field write, and enqueue/dequeue on a doubly linked list (the standard PCB queue implementation) is $O(1)$. If the ready queue is implemented as a priority queue (for priority scheduling), dispatch becomes $O(\log n)$ for $n$ ready processes, since it requires a heap extract-min. The context switch itself (saving/restoring registers, switching page tables) has a small constant cost independent of $n$, though the resulting cache and TLB misses have real, machine-dependent overhead — this is discussed fully under Context Switching. So the state-machine bookkeeping is cheap; the expense of scheduling lives in the policy (which process to pick), not in the mechanism of moving a PCB between states.

Space complexity. Each process requires one PCB, $O(1)$ space per process, so $O(n)$ total for $n$ live processes. Queue pointers add no asymptotic overhead beyond the PCBs themselves.

Correctness argument. We want to show the model never allows an inconsistent or unsafe execution — specifically, that the single-occupancy invariant and the queue-membership invariant, stated above, are maintained by every transition function. Proof sketch by induction on the sequence of transition calls.

• Base case: at system start, no processes exist; both invariants hold vacuously.
• Inductive step: assume both invariants hold before a transition call. We check each of the six functions:
• `CREATE_PROCESS` sets state to `READY` and enqueues onto `ReadyQueue` exactly once — queue-membership holds for the new PCB; no existing PCB's state or queue is touched, so single-occupancy is untouched.
• `DISPATCH` dequeues a PCB from `ReadyQueue` (removing it from a queue) and sets its state to `RUNNING`. Since it was dequeued, it is now on no queue — consistent with running processes being queue-free. Because the scheduler is only ever invoked on a core that just became free (via preemption, blocking, or exit — each of which vacates the running label for that core first), single-occupancy is preserved: the core acquires at most one new running process, and it had none before.
• `ON_TIMER_INTERRUPT` moves the current PCB from running (queue-free) to ready (enqueued once) — the running-slot is vacated before `DISPATCH` is called, so single-occupancy is momentarily "0 running on this core," never "2 running."
• `ON_BLOCKING_SYSCALL` similarly vacates the running slot before enqueuing onto exactly one wait queue.
• `ON_IO_COMPLETE` dequeues from exactly one wait queue and enqueues onto the ready queue — a PCB is never on two queues at once because dequeue and enqueue are performed atomically within the interrupt handler (interrupts are typically disabled or the operation is otherwise made atomic during this critical section).
• `ON_EXIT` vacates the running slot and never re-enqueues the PCB onto `ReadyQueue` or any wait queue — it is marked terminated and removed from active bookkeeping.

Since every transition function preserves both invariants given that they held beforehand, by induction they hold after any finite sequence of transitions. $\blacksquare$

Honest tradeoffs. This five-state model is a simplification. Real kernels add refinements:

• A suspended or swapped-out dimension (orthogonal to ready/waiting) exists in systems with virtual memory pressure, giving effectively seven or more states (ready-suspended, blocked-suspended) — the OS may swap an entire process's memory out to disk to reclaim RAM, and such a process cannot run even if its I/O completes.
• POSIX systems distinguish a zombie state (process has exited but its exit code has not yet been read via `wait()`) from full removal, because the OS must retain minimal bookkeeping until the parent collects it — a `terminated` process is not always instantly reclaimed.
• The model assumes a single wait "reason" abstraction; real kernels track why a process is waiting (which device, which lock, which signal) via separate wait queues, exactly as sketched above, so that a wake-up event only unblocks the relevant processes rather than all waiting ones.

None of these refinements change the core argument: they simply subdivide waiting or ready further while preserving the same transition discipline — a process still can't skip from a blocked variant straight into running.

Consider a single-CPU machine running three processes, $P_1$, $P_2$, $P_3$, admitted in that order at time 0, using round-robin scheduling with a time quantum of 4 ms. $P_1$ needs 6 ms of CPU and then does 3 ms of I/O before finishing with 2 more ms of CPU. $P_2$ needs 3 ms of CPU only. $P_3$ needs 8 ms of CPU only. We trace states over time.

Notice the two subtle points this trace is designed to surface: 1. At $t=16$, $P_1$'s I/O completes while $P_3$ is running. $P_1$ moves waiting → ready, not waiting → running — it must wait its turn even though its event has already occurred, because $P_3$ currently owns the single CPU and the single-occupancy invariant forbids two running processes. 2. $P_1$ passes through running twice (once before blocking, once after waking) and ready three times, illustrating that a process's full lifecycle is not a simple straight line through the five states — it can loop through ready/running/waiting arbitrarily many times before reaching terminated.

The five-state process model crystallized as computing moved from single-program batch systems to multiprogrammed, time-shared systems, where many programs genuinely coexist in memory and compete for one CPU. Formalizing "state" as an explicit, OS-tracked property was necessary the moment more than one program could be resident at once — a batch system running one job at a time never needed to distinguish ready from running.

Every general-purpose operating system kernel — Linux, Windows, macOS's XNU, the BSDs — implements some variant of this state machine as the backbone of its process (and thread) scheduler. In Linux, `/proc/[pid]/status` literally reports a process's state using letters (`R` running, `S` interruptible sleep, `D` uninterruptible sleep, `Z` zombie, `T` stopped) that map almost directly onto the states described here. Tools like `top`, `ps`, and Windows Task Manager are, at their core, dashboards for this state machine — showing you, in real time, which processes are ready, running, or blocked. Container orchestration systems (Kubernetes, Docker) and process supervisors (systemd) build higher-level lifecycles — "pending," "running," "crashed," "restarting" — that are directly analogous extensions of the same idea to a coarser granularity (whole containers instead of processes). Real-time operating systems used in embedded and automotive systems rely on precise, provable state-transition timing guarantees built on exactly this same finite-state discipline, since a car's braking-control process must never be left starving in ready for too long. Anywhere multiple independent computations share a single processor, this five-state lifecycle — or a close descendant of it — is the invisible scaffolding making concurrency manageable.

Ask the tutor: Why can't the OS just let a woken-up process resume running immediately instead of going back to ready?