--- title: 'Process Forking' source: 'https://academia.sh/en/courses/operating-system-concepts/process-forking' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:21+00:00' license: 'CC BY-SA 4.0' --- # Process Forking A new process derived from an existing one, and measuring what it inherits: four forks carry 64 virtual pages with eager copying, drop to 15 pages with copy-on-write, leaving 49 pages copied for nothing, and copy-on-write loses its advantage once the page fault cost rises to 4 time units. The previous lesson supplied five processes ready-made; they were sitting there when the machine started. On a real machine no process is born this way. Every process is created by another, already-running process, and it inherits things from its creator at the moment of creation. This derivation operation is called **forking**. The measurable form of the question is this: when a process is copied, how many virtual pages must be copied. The process abstraction's isolation guarantee demands its price exactly here, because two processes being unable to touch each other's memory is only guaranteed if there are two separate address spaces. - **PT9.** Forking derives a new process from an existing one. The one that forks is the **parent**, the one derived is the **child**; the relationship forms a tree. - **PT10.** In this lesson the tree is fixed: P1 forks to produce P2 and P3, P2 forks to produce P4 and P5. There are **four forks** in total. - **PT11.** A process's address space is **16 virtual pages** (the `VIRTUAL_PAGE` value from the shared definition). Copying one page takes **1 time unit**. - **PT12.** Marking a page read-only is flipping a bit, and in this model it takes **0 time units**. This is a choice, and the result is sensitive to it; the sensitivity is swept within the lesson. - **PT13.** The set of pages a child touches is read from the workload's compute steps. Every touch counts as a write; this is a **pessimistic upper bound** for copy-on-write. - **PT14.** Running child processes, pipelines, and job control were covered at a usage level in the Shell Programming course; they are **not repeated** here. This lesson only counts forking's inheritance and cost. - **PT15.** The measurement's resolution is **2 time units**. A difference below this counts as unmeasured, and is written as such. ## Forking's Three Separate Behaviors Forking looks like a single operation, but it treats a process's state in three separate ways, and these three must not be confused with one another. **Copying.** The address space belongs to the child. If the parent changes a page after the copy, the child does not see it; if the child changes one, the parent does not see it. This is the behavior that provides isolation, and it is also the **only one with a cost**. **Inheritance.** Some fields pass to the child by value: priority, working directory, resource limits. The child can change these afterward, and the change does not affect the parent, but the starting value comes from the parent. **Sharing.** Some structures remain a single object, and both processes see the same object. The read position an open **file descriptor** points to is like this: when the parent reads and advances, the child reads from where it left off. Sharing has zero cost, but it also has no isolation. The three must be kept separate, because the question to ask when hunting a bug is different for each. In a copied field, the parent's later change **never** reaches the child; in an inherited field, the child's starting value is the parent's, but everything after is independent; in a shared object, **every** operation by either process affects the other. When unexpected behavior appears after a fork, the first task is to determine which of these three sets the state in question falls into. The child is a process independent of its parent; even if the parent finishes first, the child keeps running. Its process table entry belongs to it and carries the nine fields from the previous lesson. Forking's cost is therefore two items: a process table entry and an address space. The entry is fixed and small; the address space is not fixed, and that is what this lesson measures. ## The Workload and the Fork Tree The first block rebuilds exactly the same workload as the previous lesson. The second block models forking and counts two copying methods. ```python # This machine is a SIMULATOR. There is no real process, kernel call, or # time measurement; all durations are time units in the model. SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 CONTEXT_COST = 2 VIRTUAL_PAGE = 16 def generator(seed): """Deterministic pseudo-random generator. The same seed gives the same sequence.""" d = seed def advance(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return advance def workload(seed=SEED): """A step is either ("COMPUTE", virtual_page) or ("WAIT", duration).""" r = generator(seed) jobs = [] for i in range(PROCESS_COUNT): steps = [] for _ in range(STEP_COUNT): if r(10) < 3: steps.append(("WAIT", WAIT_DURATION)) else: base = (i * 3) % VIRTUAL_PAGE steps.append(("COMPUTE", (base + r(4)) % VIRTUAL_PAGE)) jobs.append({"name": f"P{i+1}", "step": steps, "priority": 1 + r(3), "arrival": i * 4}) return jobs JOBS = workload() print("process arrival priority compute steps") for i in JOBS: h = sum(1 for t, _ in i["step"] if t == "COMPUTE") print(f" {i['name']:4s} {i['arrival']:5d} {i['priority']:8d} {h:12d}") ``` ``` process arrival priority compute steps P1 0 3 9 P2 4 2 9 P3 8 1 7 P4 12 3 7 P5 16 2 7 ``` ## What It Copies, What It Inherits, What It Shares The `fork` function below produces the child's process table entry. The comments beside each field show which of the three behaviors is at work; the last line proves sharing through object identity. ```python # On top of the first block: JOBS, VIRTUAL_PAGE and STEP_COUNT come from there. COPY_COST = 1 # how many time units it takes to copy one virtual page DESCRIPTOR = [0, 1, 2] # the descriptor list each process holds at startup TREE = [("P2", "P1"), ("P3", "P1"), ("P4", "P2"), ("P5", "P2")] TABLE = {i["name"]: dict(i, descriptor=list(DESCRIPTOR)) for i in JOBS} TOUCHED = {i["name"]: sorted({v for t, v in i["step"] if t == "COMPUTE"}) for i in JOBS} def fork(name, parent_name, method="eager"): """Produces the child's process table entry and counts the pages copied.""" p = TABLE[parent_name] child = {"name": name, # new: the child's own identity "arrival": TABLE[name]["arrival"], # new "step": list(TABLE[name]["step"]), # the child's steps after forking "priority": p["priority"], # inheritance: comes from the parent "descriptor": p["descriptor"]} # sharing: the same list object page = VIRTUAL_PAGE if method == "eager" else len(TOUCHED[name]) return child, page for method in ("eager", "cow"): page = sum(fork(name, pa, method)[1] for name, pa in TREE) print(f"{method:9s} copying: {len(TREE)} forks, {page:2d} pages," f" {page * COPY_COST:2d} time units") print() print("child touched pages count eager cow copied for nothing") for name, pa in TREE: d = len(TOUCHED[name]) print(f" {name:4s} {str(TOUCHED[name]):20s} {d:4d} {VIRTUAL_PAGE:8d} {d:9d}" f" {VIRTUAL_PAGE - d:16d}") print("total pages copied for nothing:", sum(VIRTUAL_PAGE - len(TOUCHED[name]) for name, _ in TREE)) print() c, _ = fork("P2", "P1") print("inheritance: priority", TABLE["P1"]["priority"], "->", c["priority"]) print("sharing : is the descriptor list the same object:", c["descriptor"] is TABLE["P1"]["descriptor"]) print("renewed : name", c["name"], "| arrival", c["arrival"]) ``` ``` eager copying: 4 forks, 64 pages, 64 time units cow copying: 4 forks, 15 pages, 15 time units child touched pages count eager cow copied for nothing P2 [3, 4, 5, 6] 4 16 4 12 P3 [6, 7, 8, 9] 4 16 4 12 P4 [9, 11, 12] 3 16 3 13 P5 [12, 13, 14, 15] 4 16 4 12 total pages copied for nothing: 49 inheritance: priority 3 -> 3 sharing : is the descriptor list the same object: True renewed : name P2 | arrival 4 ``` **Eager copying** produces the entire address space at the moment of forking: for four forks, $4 \times 16 = 64$ pages. **Copy-on-write** copies no page at the moment of forking; it marks every page read-only and produces only that page the first time a write to it is attempted. In this workload the four children touch 15 distinct pages in total, so the pages copied drop from 64 to 15. The remaining 49 pages are pages **copied for nothing**: the eager method produces them, and the child touches none of them. The ratio is clear on a per-process basis — P4 touches only 3 of its address space's 16 pages, and the remaining 13 are copied and discarded unread. ## Inheritance Works Along the Chain Because forking builds a tree, inheritance does not stop at a single step. P4 is derived from P2, and P2 is derived from P1; so P4's starting priority traces all the way back to P1. Once the whole tree is built, what this does can be counted. ```python # On top of the previous blocks: JOBS, TREE, TABLE and fork. PARENT = dict(TREE) def build_tree(method="eager"): """Forks the whole tree starting from root P1; priority is inherited along the chain.""" built, page = {"P1": dict(TABLE["P1"])}, 0 for name, pa in TREE: c, p = fork(name, pa, method) c["priority"] = built[pa]["priority"] # inheritance chain built[name] = c page += p return built, page BUILT, PAGES = build_tree() DEPTH = {"P1": 0} print("process parent depth own priority inherited priority") for i in JOBS: name = i["name"] if name in PARENT: DEPTH[name] = DEPTH[PARENT[name]] + 1 print(f" {name:4s} {PARENT.get(name, '-'):>8s} {DEPTH[name]:9d}" f" {TABLE[name]['priority']:15d} {BUILT[name]['priority']:18d}") print("tree depth:", max(DEPTH.values()), "| leaves:", sum(1 for a in DEPTH if a not in PARENT.values())) print("distinct values in own priorities:", len({TABLE[a]["priority"] for a in DEPTH}), "| in inherited:", len({BUILT[a]["priority"] for a in DEPTH})) ``` ``` process parent depth own priority inherited priority P1 - 0 3 3 P2 P1 1 2 3 P3 P1 1 1 3 P4 P2 2 3 3 P5 P2 2 2 3 tree depth: 2 | leaves: 3 distinct values in own priorities: 3 | in inherited: 1 ``` The last line is inheritance's silent consequence. The workload's own priority values carry three separate levels; once the tree is built by forking, all of them collapse to the root's value, 3, and the number of distinct levels drops to 1. For a scheduler that looks at priority, this means every process becomes indistinguishable. Inheritance's cost is zero in pages but not in information. A child has to explicitly set its own priority afterward; if it does not, it runs with its parent's. The tree's depth in this setup is 2, and its leaf count is 3. Depth matters because it gives the length of the inheritance chain: a child at depth $d$ can have starting values that came from $d$ steps away, and the only way to see this is to walk the tree backward. ## Copying, Set Against the Work Itself Whether these numbers are large can only be judged by placing them next to the workload's actual work. The same five processes' total compute steps come to 39 time units. ```python # On top of the previous blocks: JOBS, TREE, TOUCHED, VIRTUAL_PAGE, COPY_COST. MARK_COST = 0 # marking a page read-only is flipping a bit COMPUTE = sum(1 for i in JOBS for t, _ in i["step"] if t == "COMPUTE") TOUCHED_PAGES = sum(len(TOUCHED[name]) for name, _ in TREE) EAGER_PAGES = len(TREE) * VIRTUAL_PAGE print("workload's total compute steps :", COMPUTE) print("eager copying / compute step ratio :", round(EAGER_PAGES / COMPUTE, 4)) print("cow copying / compute step ratio :", round(TOUCHED_PAGES / COMPUTE, 4)) print() print("page fault cost eager cow winner") for fault in range(7): h = EAGER_PAGES * COPY_COST y = EAGER_PAGES * MARK_COST + TOUCHED_PAGES * (fault + COPY_COST) if abs(h - y) < 2: winner = "unmeasurable" else: winner = "cow" if y < h else "eager" print(f"{fault:19d} {h:8d} {y:9d} {winner}") ``` ``` workload's total compute steps : 39 eager copying / compute step ratio : 1.641 cow copying / compute step ratio : 0.3846 page fault cost eager cow winner 0 64 15 cow 1 64 30 cow 2 64 45 cow 3 64 60 cow 4 64 75 eager 5 64 90 eager 6 64 105 eager ``` The first ratio is this lesson's harshest number: eager forking is **1.641 times more expensive** than all of the five processes' compute work. The cost of setting up new processes is larger than the work those processes will do. Under copy-on-write the ratio drops to 0.3846, meaning copying takes less than a third of the work. This ratio depends on the workload and must be stated as such: if each process had a hundred and two steps instead of twelve, the denominator would grow and the ratio would fall. What is measured is not forking's absolute expense but that, **in short-lived processes**, setup cost exceeds the work. ## When Copy-on-Write Loses Copy-on-write is not free; while it defers copying, it adds two new items. The first is marking all 64 pages read-only at the moment of forking. The second is that every deferred copy starts with a **page fault**: the write attempt is trapped, control passes to the kernel, the page is produced, and the instruction re-executes. Page faults are measured on their own terms in this course's memory and storage topic; here they are only a cost parameter. The sweep shows that the advantage is not absolute. Up to a page fault cost of 3 time units, copy-on-write is ahead; **at 4 time units eager copying takes the lead**, and the gap continues to widen. The result is this lesson's counterpart to the course's second claim: **an abstraction sometimes makes things worse.** Copy-on-write winning depends on both the child touching few pages **and** trapping being cheap; if either one breaks down, the gain disappears. Row 3 of the table also shows how the resolution should be read. There, eager gives 64 and cow gives 60; the 4-time-unit gap between them is above the resolution (2 time units) and counts. Had the gap been 1, the row would be written as unmeasurable, because in this model a 1-time-unit advantage expresses a rounding, not a result. Two extreme cases sharpen this dependency. If the child loads its own program right after forking and replaces its address space entirely, all 64 of the pages the eager method copied go to waste. Conversely, if the child writes to all 16 pages, copy-on-write still copies 64 pages and additionally costs 64 page faults on top — 128 time units instead of 64 in this workload. ## Summary - Forking derives a new process from an existing one and splits process state into three: copied address space, inherited values, shared objects. - The only behavior with a cost is copying; inheritance is a value assignment and sharing is pointing to the same object, and both cost zero pages. - In this tree, four forks carry 64 virtual pages under the eager method and 15 under copy-on-write; the 49-page difference is copied for nothing. - Eager forking is 1.641 times the five processes' total compute work; setting up a process can be more expensive than the work the processes will do. - Inheritance chains along the tree: in this tree the five processes' three distinct priority levels collapse to a single level after inheritance, becoming indistinguishable to a scheduler that looks at priority. - Once the page fault cost rises to 4 time units, copy-on-write loses its advantage; deferred copying is not cheaper under every condition. ## Next Step Forking's cost is the cost of isolation: pages are multiplied so that two processes cannot touch each other's memory. If isolation is given up, this cost disappears too. The next lesson takes up execution units that share the same address space but keep their own stacks, and compares two numbers: the difference in copied pages and context switches between doing the same work with processes versus with threads.