The Process Abstraction

A process is formally defined as an instance of a program in execution, together with all the state needed to describe that execution at a given instant. A program, by contrast, is a static entity: a sequence of instructions and initialized data stored as a file on disk (an executable). The distinction matters because the same program file can be launched twice — open two terminal windows running the same shell binary — and produce two entirely distinct processes, each with its own memory, its own variables, and its own execution point, even though they started from identical bytes on disk. To fully describe "a program in motion," the OS must track two broad categories of state. The first is the address space: the range of memory addresses a process can reference, containing its executable code (the text segment), its global and static variables (data), a region for dynamically allocated memory that grows as the program runs (the heap), and a region for function call frames and local variables that grows and shrinks as functions are called and return (the stack). The second is the execution context (also called machine state or hardware context): the values held in CPU registers while the process runs, most critically the program counter (PC), which records the address of the next instruction to execute, and the stack pointer, which records the top of the current call stack. Other general-purpose registers hold whatever intermediate values the running computation needs. Crucially, a process's address space is virtualized. The addresses a program's instructions reference — say, "load the value at address 0x1000" — are not literal physical RAM addresses. They are addresses in a private, per-process virtual address space, translated to physical memory by hardware (the memory management unit) under OS supervision. This virtualization is what permits two processes to both believe their code starts at address 0x1000, without colliding in physical memory, and what makes it impossible for one process's stray pointer to accidentally read or corrupt another process's memory. Address space virtualization is covered in depth in later articles on memory management; here the essential point is that a process is defined relative to its own private view of memory, not the machine's raw physical memory.

Building the process abstraction requires the OS to answer two operational questions: how is a single process represented, and how does the OS switch the physical CPU among many such representations while preserving the illusion that each process runs continuously?

Representing a process. When a program is launched, the OS creates a fresh address space and loads the program's code and initial data into it, reserves space for a stack and a heap, and initializes the CPU registers — most importantly, setting the program counter to the program's entry point. The OS also allocates a bookkeeping record (which later articles call the Process Control Block (PCB)) that stores metadata: a unique process identifier, the process's current state, and — whenever the process is not actively running — a saved copy of its execution context, so it can be resumed exactly where it left off.

Time-sharing the CPU. With only one (or a few) physical CPUs and potentially dozens of processes wanting to run, the OS achieves the illusion of many simultaneously running processes through context switching: rapidly stopping one process, saving its exact execution state, loading a different process's saved state into the CPU, and resuming it. Done fast enough (milliseconds), this creates the perception of parallelism even on a single core — a technique called time-sharing or multiprogramming. The mechanism relies on a periodic interrupt (a timer interrupt) that forces the CPU to trap into the OS at regular intervals, regardless of what the currently running process is doing. This guarantees the OS periodically regains control — a property essential for fairness and responsiveness, since without it a buggy or malicious process could simply never yield the CPU. ```pseudocode // Executed by the timer-interrupt handler, inside the OS kernel. // 'current' is the process the CPU was executing at the moment // the timer fired. function ON_TIMER_INTERRUPT(current): // 1. Hardware has already saved the interrupted PC and a few // registers onto the kernel stack automatically (trap entry). // The handler now saves the REST of the context explicitly. current.context.pc <- read_saved_pc_from_trap_frame() current.context.registers <- read_all_general_registers() current.context.stack_pointer <- read_stack_pointer_register() current.state <- READY // 2. Decide who runs next (policy: covered by the scheduler). next <- SCHEDULER_PICK_NEXT_READY_PROCESS() // 3. Restore the chosen process's saved context into the CPU. load_registers(next.context.registers) load_stack_pointer(next.context.stack_pointer) next.state <- RUNNING // 4. Return-from-interrupt jumps to next.context.pc automatically, // resuming 'next' exactly where it was previously paused. RETURN_FROM_INTERRUPT(next.context.pc) ``` ```pseudocode // Executed once, when a new process is launched (e.g. on exec()). function CREATE_PROCESS(program_file): pcb <- ALLOCATE_PCB() pcb.pid <- NEXT_UNIQUE_ID() addr_space <- ALLOCATE_VIRTUAL_ADDRESS_SPACE() LOAD_CODE_AND_DATA(addr_space, program_file) // text + data segments ALLOCATE_HEAP(addr_space, initial_size = 0) // grows via malloc-like calls ALLOCATE_STACK(addr_space, size = DEFAULT_STACK) // for calls/locals pcb.address_space <- addr_space pcb.context.pc <- program_file.entry_point pcb.context.sp <- top_of(addr_space.stack) pcb.context.regs <- ZERO_REGISTERS() pcb.state <- READY SCHEDULER_ADD_TO_READY_QUEUE(pcb) return pcb.pid ``` Each context switch has a real, non-zero cost: saving and restoring registers, flushing pipeline state, and — because a new address space usually means new virtual-to-physical mappings — often flushing the CPU's translation lookaside buffer (TLB), a cache that speeds up address translation. The OS's scheduling policy (discussed in dedicated articles) decides which ready process to run next; the mechanism above is agnostic to that policy and only implements the how.

Space complexity. Each process requires $O(1)$ fixed metadata for its control block (a handful of registers, a state flag, an identifier — bounded regardless of program size) plus space proportional to its address space contents: code size, static data size, and however much heap and stack it has allocated at a given moment. If $n$ processes exist simultaneously, total OS bookkeeping overhead is $O(n)$ in the number of processes, independent of how large any individual process's memory footprint is, since the PCB itself does not grow with the process's data.

Time complexity of a context switch. A context switch takes $O(k)$ time where $k$ is the number of registers the hardware architecture defines — a small constant (dozens, not growing with input size), since saving and restoring registers is a fixed sequence of load/store instructions. In practice the dominant cost is not the register save/restore itself but secondary effects: TLB flushes and cold caches after switching address spaces, which cause subsequent memory accesses to be slower until the new process's working set is "warmed up" again. This is why context switches, though algorithmically $O(1)$-ish, carry real, measurable overhead (typically microseconds) that scheduling policies must amortize by not switching too frequently.

Correctness argument. The correctness property the process abstraction must guarantee is transparent resumability: a paused process, when resumed, must behave exactly as if it had never been paused — same register values, same memory contents, same next instruction. This is an invariant maintained across every context switch: > Invariant. For any process $P$ in the `READY` or `BLOCKED` state, the PCB for $P$ holds a complete and exact snapshot of $P$'s execution context (PC, SP, all registers) as of the instant $P$ stopped running, and $P$'s address space is untouched by any other process. This invariant is established by two guarantees working together: 1. Save-before-switch discipline. The interrupt/trap handler never overwrites a register before it has been copied into the outgoing process's PCB. As long as the save step (lines 1 in `ON_TIMER_INTERRUPT`) completes atomically with respect to interrupts — itself guaranteed because interrupts are disabled while the kernel is mid-handler — no register value is lost. 2. Hardware-enforced address-space isolation. The memory management unit checks every memory access against the currently active process's address-space mappings; an access outside them faults rather than silently succeeding. This guarantees the second half of the invariant — no process can inspect or corrupt another's memory — independent of software bugs in any single process. Given the invariant, resumption correctness follows directly: restoring the saved PC, SP, and registers reconstructs the exact CPU state that existed at the pause point, so the next instruction executed is precisely the one that would have executed had the process never been interrupted. The process cannot observe that it was ever paused (barring timing side channels), which is precisely the illusion of a dedicated, uninterrupted CPU.

Tradeoffs. The abstraction is not free. Isolation and virtualization cost real time (address translation, TLB management, trap overhead) and real space (per-process metadata, page tables). A design that skipped isolation — letting all programs share one flat physical address space directly — would be faster and simpler but catastrophically fragile: any bug in any program could corrupt any other program or the OS itself. The process abstraction trades a modest, well-amortized overhead for strong safety and modularity, a tradeoff virtually every general-purpose OS accepts. Later refinements — Threads sharing one address space, or lightweight containers — exist precisely to reduce this overhead in situations where full isolation is unnecessary.

Consider a machine running two processes: `P1` (a text editor, PID 7) and `P2` (a compiler, PID 8), sharing one CPU. Trace what happens over three timer interrupts, assuming a simple round-robin policy with a fixed time slice.

Notice the essential fact this trace demonstrates: at $t{=}20\text{ms}$, `P1` resumes at PC `0x4050`, not `0x4000`. From `P1`'s own point of view — as a sequence of instructions executing one after another — there is no discontinuity at all; it cannot tell that ten milliseconds of "wall-clock time" and an entire other program's execution happened in between. That is the process abstraction working correctly: the illusion of a dedicated, continuously running processor, built out of one physical CPU rapidly multiplexed between two independent execution contexts and two disjoint address spaces (`P1`'s code lives at `0x4000`–`0x40FF`, `P2`'s at `0x5000`–`0x51FF`, in their respective virtual spaces — both may even be mapped to the same virtual addresses without collision, since each is translated independently to different physical frames).

The process abstraction crystallized during the era of time-sharing systems, when researchers first confronted the problem of running many interactive users' programs on one expensive, scarce mainframe. Earlier batch-processing systems ran one program to completion before loading the next; the leap to multiprogramming — keeping several programs' state alive simultaneously in memory, switching the CPU rapidly among them — required formalizing exactly what "a program in execution" meant as a distinct, manageable object, separate from the static program text.

Every general-purpose operating system — Linux, Windows, macOS, Android, iOS — implements the process abstraction as its fundamental unit of execution and protection. When a phone runs a maps app, a messaging app, and a background music player "at once," each is a separate process, isolated so that a crash in one cannot take down the others — a guarantee users depend on dozens of times a day without noticing. Server infrastructure relies on the same abstraction at scale: a web server might spawn one process per incoming connection (or, more commonly today, use threads or event loops within a process, but the isolation guarantees still trace back to process boundaries between tenants). Sandboxing technologies — web browser tabs, containerized microservices, virtual machines — are all, at their core, refinements or compositions of the process abstraction, tightening or loosening its isolation boundary for particular tradeoffs between safety and performance. Kernel-level security models (permissions, access control, crash containment) are enforceable only because processes are isolated; without this abstraction, a single misbehaving program could read another user's passwords directly out of shared memory. Understanding processes precisely is the prerequisite for understanding Process State and the Lifecycle (how a process moves between running, ready, and blocked), the Process Control Block (PCB) (exactly what metadata the OS tracks per process), and eventually Threads (a lighter-weight unit of execution that shares a process's address space).

Ask the tutor: How does the OS actually create the very first process at boot, before any process yet exists to ask for one?