Process Creation and fork()

In UNIX-like systems a new process is made in two separate steps. fork() creates a near-exact copy of the calling process; exec() then replaces the copy's program with a new one. A shell runs a command by forking, letting the child exec the command, and waiting for the child to finish.

Separating the two steps is what makes UNIX process control flexible: between fork and exec the child can redirect its input and output, close files or change its user, and the parent's state is untouched. It is also the basis of a counting exercise: given a few lines of C with fork() calls, how many processes exist and what is printed?

The exact semantics, a counting method that works for loops and short-circuit conditions, and the output-buffering trap are the points that decide the process count and the printed output.

After fork() both processes continue from the same point: the return from fork. Both resume at the fork return point with different return values; the child also has a new process identity and the documented inheritance differences. Which one runs first is up to the scheduler and must not be assumed.

Separate copies. After the fork, parent and child have separate copies of every variable. A change made by one is invisible to the other. A pointer printed in both shows the same virtual address, which maps to different physical frames once either process writes. Open files are different: parent and child share the same open-file entry, and therefore the same file offset.

Copy-on-write. Modern kernels do not copy memory at fork. Eligible private writable pages are shared and temporarily write-protected for copy-on-write; a write creates a private copy as needed. Originally read-only pages remain protected, while explicitly shared mappings remain shared. A fork followed at once by exec therefore copies almost nothing. See Virtual Memory and Demand Paging.

Code after a successful execlp never runs in the child. _exit is used in the failed child so that it does not flush a copy of the parent's stdio buffers.

Each fork() executed by every existing process doubles the count. $n$ consecutive fork() calls, executed unconditionally, give $2^{n}$ processes in total, that is $2^{n} - 1$ new ones.

Inside a condition, the parent sees a non-zero value (true) and the child sees 0 (false). Then apply C's short-circuit rules:

So in fork() && fork(), the first child (which got 0) skips the second fork; in fork() || fork(), the first parent (non-zero) skips it.

For for (i = 0; i < n; i++) fork(); every process alive at iteration $i$ forks once. A child created in iteration $i$ continues with iteration $i + 1$, so it has $n - 1 - i$ children of its own.

Counting with recurrences. Let $T(n)$ be the number of processes after for (i = 0; i < n; i++) fork();. Every process forks once per iteration, so $T(n) = 2\,T(n - 1)$ with $T(0) = 1$, giving $T(n) = 2^{n}$.

Children per process. In the same loop, a process created in iteration $i$ (0-based) forks in iterations $i + 1$ to $n - 1$, so it has $n - 1 - i$ children; the original has $n$. The tree is the binomial tree $B_n$, whose levels hold $\binom{n}{k}$ processes at depth $k$. For $n = 3$: depths 0 to 3 hold $1, 3, 3, 1$ processes.

Lines printed inside a loop. If each iteration forks once and then prints once, iteration $i$ prints $2^{i+1}$ lines, and the total over $n$ iterations is $\sum_{i=0}^{n-1} 2^{i+1} = 2^{n+1} - 2$.

Assume every fork() succeeds and stdout is a terminal (line-buffered) unless stated.

Working for if (fork() && fork()) fork();. The original P forks C1. C1 gets 0, so the && is false and C1 is done. P gets non-zero and forks C2. C2 gets 0 and is done. P again gets non-zero, the condition is true, and P forks C3. Total: P, C1, C2, C3 = 4.

Working for fork() && (fork() || fork()). P forks C1; C1 gets 0 and stops. P evaluates fork() || fork(): it forks C2 and gets non-zero, so || is already true and P stops. C2 got 0, so it evaluates the second operand and forks C3. Total 4: P, C1, C2, C3.

Working for the printing loop. In iteration 0 there are 2 processes after the fork, each printing once: 2 lines. In iteration 1 both fork, giving 4 processes, each printing once: 4 lines. Total 6 lines. A loop of $n$ iterations prints $2 + 4 + \dots + 2^{n} = 2^{n+1} - 2$ lines.

The fan loop. if (fork() == 0) break; makes each child leave the loop at once, so only the original process keeps forking: 4 children, 5 processes, and the tree is a star rather than a binomial tree.

Working for fork() && fork() || fork(). It parses as (fork() && fork()) || fork(). P forks C1. In C1 the first fork() returned 0, so the && is false without evaluating its right side, and C1 goes on to the || and forks C2; C2 gets 0, which ends its expression. In P the first fork() was non-zero, so P forks C3. P gets non-zero, the && is true, and the || short-circuits: P stops. C3 got 0, so its && is false and it forks C4. Total: P, C1, C2, C3, C4 = 5.

Working for fork(); fork() && fork(); fork();. After the first line there are 2 processes. Each runs fork() && fork(), which turns 1 process into 3 (as in the if (fork() && fork()) row above, without the third fork), giving $2 \times 3 = 6$. The last fork() doubles them: 12.

Working for the printing loop. Each fork() call creates exactly one child, and only the child prints, so the lines printed equal the number of fork() calls. Processes double each iteration (both parent and child continue the loop), so $1 + 2 + 4 = 7$ calls are made: 7 lines and 8 processes.

A fork that runs only on some iterations. In the last loop fork() runs only for $i = 2$ and $i = 4$: two doublings, $2^2 = 4$ processes. Count the iterations on which the fork executes, not the iterations of the loop.

Output: child 15 then parent 4. The child changes its own copy; the parent's x is still 5 when it subtracts 1. The wait forces the order; without it either line could come first.

"A" has no newline, so it is still sitting in the parent's stdio buffer (in user memory) when fork() copies the address space. Both processes later flush their own copy, and the output is AB printed twice, not A once and B twice.

With printf("A\n") instead, the behaviour depends on where stdout goes:

IMPERATIVE RULE. Count printf output by asking whether the text was already flushed before the fork. Text still in the buffer is duplicated by every fork that follows.

Common misconceptions.