The Process Control Block (PCB)

A Process Control Block is a kernel-resident data structure, one per process, that stores all the information the operating system needs to manage that process's execution and to suspend and later resume it without loss of correctness. It is the process's identity card, its saved brain-state, and its administrative file, combined into a single record. Conceptually, the PCB fields fall into four groups. Identification and state: a unique process ID (PID), the parent's PID, and the current position in the Process State and the Lifecycle state machine (new, ready, running, waiting, terminated). CPU context: the saved values of the program counter, stack pointer, general-purpose registers, and processor status flags — exactly what the CPU was doing at the instant the process was last stopped. Memory management information: pointers to page tables or segment tables, the base and limit of the address space, and pointers to the code, data, and stack regions. Accounting and resource information: CPU time consumed, priority and scheduling class, open file descriptors, pending signals, and pointers to the process's I/O status and owned resources such as sockets or locks. The crucial property that makes the PCB useful is this: the PCB is the only place any of this information lives when the process is not running. When a process is executing, some of its state lives in physical CPU registers. The instant the kernel decides to stop that process — because its time slice expired, it blocked on I/O, or a higher-priority process preempted it — every register value that matters is copied into that process's PCB. The reverse copy, from PCB back into registers, is what "resuming" a process means. This save/restore pair, applied to a pair of processes, is precisely the operation known as a context switch, which is introduced properly elsewhere; here we only need the PCB's role as the storage medium that makes it possible.

The kernel treats the set of all PCBs as a table, conventionally indexed by PID, and additionally threads PCBs onto linked lists corresponding to scheduling queues (ready queue, one queue per blocking device or condition, and so on). Three mechanisms operate on PCBs constantly: creation, context-switch save/restore, and destruction.

Creation. When a new process is made (conceptually via `fork`, detailed in Process Creation with fork and exec), the kernel allocates a fresh PCB, assigns it a new PID, records the parent's PID, initializes memory-map pointers (often by copying and adjusting the parent's), sets the state to new or ready, and inserts it into the ready queue.

Context switch (save and restore). Whenever the kernel stops one process and starts another, it copies the outgoing process's register file into its PCB, updates its state field, moves it to the appropriate queue, then does the reverse for the incoming process: reads registers out of its PCB, restores the memory-map (e.g., loads the page-table base register), sets its state to running, and transfers control via a return-from-interrupt.

Destruction. When a process calls exit (or is killed), its resources are released, its state is set to terminated (a "zombie" in Unix terminology), and it is kept as a husk — just enough of the PCB survives to report the exit status — until the parent calls `wait`, at which point the PCB is finally freed. ``` // Kernel-resident table of all PCBs, indexed by PID. struct PCB { pid_t pid pid_t parent_pid State state // NEW, READY, RUNNING, WAITING, TERMINATED CPUContext context // saved PC, SP, general registers, flags AddressSpace mm // page table base, segment bounds int priority long cpu_time_used FileDescriptorTable fds SignalMask pending_signals PCB next // intrusive link for queue membership } PCB_table[MAX_PID] // sparse array or hash map, PID -> PCB ready_queue, waiting_queue[..], zombie_list // linked lists of PCB* // --- Process creation --- function CREATE_PROCESS(parent): child = allocate(PCB) child.pid = next_free_pid() child.parent_pid = parent.pid child.state = READY child.mm = clone_address_space(parent.mm) // copy-on-write in practice child.context = copy(parent.context) // child resumes as if it were the parent child.priority = parent.priority child.cpu_time_used = 0 child.fds = clone(parent.fds) PCB_table[child.pid] = child enqueue(ready_queue, child) return child.pid // --- Context switch: stop `current`, start `next` --- function CONTEXT_SWITCH(current, next): disable_interrupts() // protect PCB fields (critical section) current.context = save_cpu_registers() // hardware -> PCB if current.state == RUNNING: current.state = READY enqueue(ready_queue, current) load_address_space(next.mm) // switch page-table base register restore_cpu_registers(next.context) // PCB -> hardware next.state = RUNNING enable_interrupts() return_from_interrupt() // resumes `next` at its saved PC // --- Blocking on I/O --- function BLOCK(proc, device): proc.context = save_cpu_registers() proc.state = WAITING enqueue(waiting_queue[device], proc) schedule_next() // pick a READY process, context switch to it // --- Termination --- function EXIT(proc, status): proc.state = TERMINATED proc.exit_status = status release(proc.mm) release(proc.fds) reparent_children(proc, init_process) move_to(zombie_list, proc) // PCB skeleton kept until parent waits schedule_next() function WAIT(parent): if exists z in zombie_list where z.parent_pid == parent.pid: status = z.exit_status remove(zombie_list, z) free(z) // PCB finally released return (z.pid, status) else: parent.state = WAITING schedule_next() ```

Space. Each PCB occupies a fixed-size header (fields for state, PID, registers, pointers) plus variable-size satellite structures it points to, such as the file-descriptor table and page tables. The fixed portion is O(1) per process — typically hundreds of bytes to a few kilobytes depending on the kernel (Linux's `task_struct` is on the order of a few kilobytes; the kernel stack allocated alongside it adds more). Total kernel memory devoted to process bookkeeping is therefore

where $n$ is the number of live processes, since each PCB is allocated once per process and its size does not depend on how many other processes exist. This is why operating systems impose a maximum process count (`pid_max`, ulimits): PCB memory is real, unswappable, privileged kernel memory, and an unbounded number of processes would exhaust it.

Time. Three operations dominate:

• Lookup by PID: with a PID-indexed array or hash table, this is $O(1)$ average case. (A naive linked-list scan over all processes would be $O(n)$; real kernels avoid this.)
• Enqueue/dequeue from a scheduling queue: $O(1)$ using intrusive linked lists (the `next` pointer lives inside the PCB itself, so no separate allocation is needed to add a PCB to a queue). Some schedulers use priority structures (heaps, red-black trees, as in Linux's CFS) giving $O(\log n)$ insertion/removal in exchange for better scheduling decisions — a classic time/quality tradeoff.
• Context switch: copying the register file and switching the memory-map pointer is $O(1)$ in the number of processes — it touches a fixed, small number of registers regardless of $n$ — but it is not free in absolute terms: it costs a fixed number of CPU cycles plus, critically, the cost of a TLB flush or address-space-ID reload, which shows up as cache/TLB misses after the switch. This constant-but-nonzero cost is why excessive context switching (thrashing between many runnable processes) degrades throughput even though each individual switch is $O(1)$.

Correctness — the invariant. The essential correctness property the PCB must maintain is: > Resumption invariant: at any instant a process is not the one occupying the CPU, its PCB's `context` field holds exactly the register values it would have had, had it simply been paused in place. This invariant is established by construction: `CONTEXT_SWITCH` always performs `save_cpu_registers()` into the outgoing process's PCB before it overwrites CPU state with the incoming process's values, and interrupts are disabled for the duration so that no nested context switch can occur mid-save. If this ordering were violated — say, if the scheduler picked the next process and loaded its registers before finishing the save of the current one — the outgoing process's register file would be corrupted and it would resume, later, at the wrong point with wrong data, silently and catastrophically. The invariant, combined with disabling interrupts around the save/restore (a critical section, foreshadowing synchronization concerns discussed alongside concurrency), is exactly what guarantees a process can be stopped and resumed an arbitrary number of times with behavior indistinguishable from uninterrupted execution — the defining promise of preemptive multitasking. A second invariant governs lifecycle bookkeeping: every PCB that has reached `TERMINATED` remains in `zombie_list` until exactly one `wait` call by its parent consumes it. This guarantees exit status is never lost and PCB memory is never freed while a parent might still query it — at the cost of tying up a small PCB skeleton indefinitely if a parent never calls `wait` (a real and named bug class, "zombie accumulation," discussed below).

Trace a small scenario: two user processes, A (pid 40) and B (pid 41), on a single-core system with a preemptive round-robin scheduler and a 10 ms timer tick. Process A is running; process B is ready and waiting in the queue.

Notice the two facts this trace makes concrete. First, process A resumed at `PC=0x1054`, one instruction past where it was interrupted (`0x1050`) — exactly the resumption invariant, because the interrupt handler saved the post-increment PC. Second, PCB(B) is the only place `PC=0x2010` existed between t=10ms and the moment B was restored; if the kernel had crashed or the PCB table had been corrupted in that window, B's execution point would be permanently lost. That fragility, and the discipline required to avoid it, is exactly why the PCB save/restore sequence is written as an atomic, interrupt-disabled operation.

The PCB concept crystallized alongside the first true multiprogramming operating systems, when designers first had to answer: if the CPU can run only one instruction stream at a time, but many programs must appear to progress simultaneously, where does each program's "paused self" live? Early batch systems ran one job at a time and needed no such record; the PCB became indispensable only once systems supported timesharing and multiple concurrent jobs contending for one processor.

Every general-purpose operating system kernel implements some form of PCB, though the name and exact layout vary. Linux calls it `task_struct`, a large structure (several kilobytes) containing state, scheduling class and priority, memory descriptor (`mm_struct`), open-file table, signal handlers, and namespace/cgroup pointers for containerization — the same PCB concept extended to support Docker-style isolation. Windows splits the concept across an `EPROCESS` block (address space, handle table, security token) and one `KTHREAD` per schedulable thread within it, reflecting the OS's thread-centric scheduling model. Real-time operating systems used in embedded and automotive systems (e.g., FreeRTOS's task control block, VxWorks) keep PCBs deliberately tiny and fixed-size to make context-switch latency bounded and predictable, since real-time guarantees depend on that cost being both small and known. Virtualization hypervisors maintain an analogous structure per virtual CPU, and container runtimes lean on the kernel's existing PCB machinery (with added namespace fields) rather than inventing a new one — which is why understanding the PCB is foundational before studying Context Switching internals, Process Creation with fork and exec semantics, or multiprocessor scheduling.

Ask the tutor: How exactly does the page-table base register swap inside a PCB-driven context switch interact with the TLB, and why does that interaction make context switches more expensive than the O(1) register-copy cost alone suggests?