Process Creation with fork and exec

A process is a running instance of a program, represented in the kernel by a Process Control Block holding its process ID (PID), memory map, open file table, register state, and scheduling information. Process creation is the act of producing a new PCB and address space so that a second, independently schedulable process comes into existence. In Unix-derived systems this is accomplished with `fork()`, a system call that clones the calling process — called the parent — into a new process called the child, which is an almost exact copy: same code, same data (initially), same open files, but a distinct PID and a distinct address space going forward. `fork()` alone would only ever let you run copies of the same program. The second half of the idiom is `exec()` (in practice one of `execve`, `execvp`, `execl`, etc.), which does not create a new process at all — it replaces the calling process's text, data, heap, and stack segments with those of a new executable file, resetting the instruction pointer to that program's entry point. Crucially, `exec` preserves the PID, the parent-child relationship, and (by default) the open file descriptor table. This is the key design insight: file descriptors opened or redirected before `exec` survive into the new program, which is exactly how shell redirection (`cmd > file.txt`) and pipelines (`cmd1 | cmd2`) are implemented without any special-casing inside `cmd1` or `cmd2` themselves. The third piece, `wait()` / `waitpid()`, lets a parent synchronize with child termination. When a child calls `exit()`, the kernel does not immediately destroy its PCB; it transitions the child to a zombie state, retaining its exit status until some ancestor calls `wait` to "reap" it. This design exists so that exit status — a single integer, otherwise unrecoverable once a process is gone — can be reliably delivered to whichever ancestor cares, even if that ancestor is busy doing something else when the child actually finishes.

The full fork–exec–wait protocol, as used by every Unix shell, proceeds in five conceptual steps. First, the parent calls `fork()`. The kernel duplicates the parent's PCB, giving the child a new PID and (logically) a full copy of the address space; both parent and child now resume execution at the instruction immediately after the `fork()` call, distinguished only by `fork`'s return value — zero in the child, the child's PID in the parent, and a negative value in the parent if creation failed. Second, the child (identified by the zero return value) typically performs setup: closing or duplicating file descriptors for redirection, changing its working directory, or resetting signal handlers. Third, the child calls one of the `exec` functions, naming the new program to run; on success this call never returns, because the calling process's image has been replaced entirely. Fourth, the parent — running concurrently — calls `wait()` or `waitpid()`, blocking until the child terminates, or polling if it passed `WNOHANG`. Fifth, the kernel delivers the child's exit status to the parent and reclaims the zombie PCB. ``` // Parent process, e.g. a shell executing one command pid = fork() if pid < 0: // fork failed: no child was created report_error("fork failed") return FAILURE else if pid == 0: // ----- child branch ----- // Optional: redirect stdin/stdout/stderr, close unneeded fds setup_redirections() execve(program_path, argv, envp) // exec only returns on failure (e.g. file not found, bad permissions) report_error("exec failed") exit(127) // conventional "command not found" status else: // ----- parent branch, pid = child's PID ----- child_status = 0 result_pid = waitpid(pid, &child_status, 0) // block until this child exits if WIFEXITED(child_status): code = WEXITSTATUS(child_status) report("child exited with code", code) else if WIFSIGNALED(child_status): sig = WTERMSIG(child_status) report("child killed by signal", sig) ``` Two subtleties make this idiom work correctly rather than merely "usually work." First, `fork()` is called exactly once, but it returns twice — once in each process — which is why the branch on `pid` is essential; forgetting the `pid == 0` check means both processes run the parent's logic. Second, the ordering of `wait` relative to `exec` matters not at all for correctness (the kernel schedules parent and child independently), but the ordering of redirection setup relative to `exec` is critical: file descriptor manipulation must happen in the child, after `fork` but before `exec`, precisely because `exec` inherits the descriptor table as it stands at call time. A minimal pseudocode sketch of the kernel-side `fork` implementation clarifies what "copy" really means: ``` // Kernel-side fork() implementation sketch function kernel_fork(parent_pcb): child_pcb = allocate_pcb() child_pcb.pid = generate_new_pid() child_pcb.parent_pid = parent_pcb.pid child_pcb.registers = copy(parent_pcb.registers) child_pcb.open_files = copy(parent_pcb.open_files) // fd table duplicated, // underlying file objects shared // Address space: do NOT physically copy pages yet. for each page_table_entry in parent_pcb.page_table: child_entry = duplicate_entry(page_table_entry) child_entry.writable = false // mark both copies read-only page_table_entry.writable = false mark_as_shared(page_table_entry.physical_frame) // increment refcount child_pcb.page_table = built from above entries child_pcb.state = READY scheduler.enqueue(child_pcb) // Set up return values: child sees 0, parent sees child_pcb.pid parent_pcb.registers.return_value = child_pcb.pid child_pcb.registers.return_value = 0 return // control returns to both, via normal scheduling ``` And the corresponding `exec` sketch: ``` // Kernel-side exec() implementation sketch function kernel_exec(pcb, program_path, argv, envp): file = open_executable(program_path) if file is invalid: return ERROR // pcb is left completely unchanged new_image = parse_and_load(file) // read ELF/PE headers, segments destroy_address_space(pcb) // discard old text/data/heap/stack pcb.page_table = map_segments(new_image) pcb.registers.instruction_pointer = new_image.entry_point pcb.registers.stack_pointer = setup_stack(argv, envp) // pcb.pid, pcb.parent_pid, pcb.open_files are UNCHANGED return // never returns to caller's old code — new program begins executing ```

Time complexity of `fork`. A naive fork that eagerly copies every page of the parent's address space takes time proportional to the resident memory size, $O(M)$ where $M$ is the number of resident pages, because each page must be duplicated. Real systems avoid this using copy-on-write (COW): `fork` only duplicates the page table — an $O(P)$ operation where $P$ is the number of page table entries, typically far smaller than $M$ and bounded by the address space's mapped region — and marks all shared physical frames read-only in both processes. No physical page is actually copied until one of the two processes attempts to write to it, at which point the kernel intercepts the resulting protection fault, allocates a fresh frame, copies just that one page, and resumes execution. This defers cost from $O(M)$ at fork-time to $O(1)$ per page actually modified, which is essential because the overwhelmingly common case — `fork` immediately followed by `exec` — never touches most of the parent's memory at all before it's discarded.

Correctness of copy-on-write. The invariant COW must preserve is: each process, at every point in its execution, observes memory contents identical to what an eager, full copy would have produced. This holds because (1) immediately after `fork`, both processes' page tables point to the same physical frames with identical data, satisfying the invariant trivially; and (2) any write by either process is trapped by the write-protect bit before it can occur, at which point the kernel copies the specific page being written, remaps only the writing process's page table entry to the new frame, and only then permits the write to proceed. Because the trap-and-copy happens strictly before the write takes effect, the other process's view of that page is never disturbed — it still sees the original, shared frame. Reference counting on physical frames ensures the last process to still share a page (rather than the first) is responsible for eventually freeing it, avoiding both premature frees and permanent leaks.

Time complexity of `exec`. `exec` must read and parse an executable's headers (proportional to header size, effectively constant for a fixed format), tear down the old address space's page table entries ($O(P)$ in the old page count), and construct new mappings for the new program's segments ($O(P')$ in the new page count). Because most segments are demand-paged rather than loaded eagerly, `exec` does not scale with the executable's total size on disk, only with the number of segments and the argument/environment vector length used to build the initial stack — an $O(A)$ term where $A$ is the total bytes of `argv`/`envp`.

Correctness of `wait`. The invariant is that every terminated child's exit status is deliverable to exactly one waiting call in an ancestor, even under arbitrary scheduling delays. The kernel guarantees this by never discarding a terminated child's PCB outright; instead it demotes the PCB to a zombie, retaining only the exit status and accounting information, and defers full deallocation until a `wait` call consumes it. This is why zombies are cheap (they hold no address space, no file descriptors — those are released at `exit` time) but not free: an unreaped zombie still occupies a PCB slot and a PID, which is finite. The tradeoff is explicit: Unix sacrifices a small, bounded amount of kernel memory per terminated-but-unreaped child in exchange for a lossless notification channel that survives arbitrary scheduling races between exit and wait.

Space complexity. A `fork` costs $O(P)$ additional kernel memory for the duplicated page table and PCB, independent of how much data is later written (COW pages are allocated lazily, "pay as you go"). A zombie costs $O(1)$ — a PCB stub — regardless of how large the process was in life, since its address space was already reclaimed at exit.

Consider a simplified shell implementing a two-stage pipeline, `ls | wc -l`, which counts how many files are in the current directory. This exercises `fork`, `exec`, file descriptor manipulation, and `wait` together.

Tracing the PCBs: at step 2, `pid1` is a fresh PCB whose `parent_pid` field equals the shell's PID, and whose file descriptor table is a copy — same entries, but an independent table, so closing `fd[0]` in Child A does not close it in the shell. At step 5, `execve` replaces Child A's address space and instruction pointer, but its PID (`pid1`) and its now-redirected file descriptor table survive unchanged — this is exactly why `ls`'s output, which the `ls` binary itself writes to "file descriptor 1" with no knowledge of pipes, ends up flowing into `wc`. At step 11, the shell blocks on `pid1` first; if `wc -l` (Child B) happens to finish first because it was faster to start, its PCB becomes a zombie and simply waits — patiently, at $O(1)$ memory cost — until the shell's second `waitpid` call reaps it. No data is lost regardless of which child finishes first, which is the correctness property `wait`/zombie semantics were designed to guarantee.

The fork/exec model traces back to the earliest days of Unix at Bell Labs, where the designers deliberately chose a minimal, orthogonal primitive over a monolithic "spawn" call — a decision credited largely to Ken Thompson, who is said to have implemented the original `fork` in a single afternoon by adapting an idea from the Berkeley timesharing system and Project GENIE, both of which had experimented with process duplication.

Every Unix-like shell — `bash`, `zsh`, `dash`, `fish` — is fundamentally a loop that parses a command line, `fork`s, redirects file descriptors and/or sets up pipes in the child, `exec`s the requested program, and `wait`s for it, exactly as traced above. Container runtimes such as Docker and Kubernetes's `containerd` use the same primitives, layered with namespace and cgroup setup calls between `fork` (or `clone`) and `exec`, to isolate a new process's view of the filesystem, network, and process tree. Web servers and network daemons that use a process-per-connection model, including classic Apache's prefork MPM and many CGI-based systems, rely on `fork` to isolate each client's request-handling in its own address space, trading the low memory-sharing overhead of copy-on-write against the higher cost of per-process context switching compared to a threaded model — the natural segue toward Threads and Concurrency, where multiple execution contexts share a single address space instead of forking a new one. Language runtimes (Python's `subprocess`, Java's `ProcessBuilder`) expose higher-level wrappers that internally perform exactly this fork/exec/wait sequence, and understanding the underlying primitive explains otherwise-mysterious behaviors, such as why a forked child in Python can unexpectedly inherit open file handles, or why improperly reaped subprocesses show up as `` zombies under system monitoring tools.

Ask the tutor: How would this fork/exec/wait model need to change if the operating system used threads instead of processes as its basic unit of scheduling?