fork()调用的一个趣题

经常看到有人问到这样一个问题：

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    int i, pid;

    pid = 0;
    for (i = 0; i < 3; i++) {
        pid = fork();
        if (pid == 0)
            printf("pid:%d\n", getpid());
    }

    return 0;
}

问最后打印了多少行pid:xxx.很多人一看，认为很简单，不就产生了3个子进程嘛，答案就是3个，这样回答可以说压根没有理解Linux/Unix中 fork()系统调用是怎么实现的。上面的问题等价于问这个程序总共产生了多少个进程（算自身）an，最后的答案就是an-1，因为最开始的父进程没有执行故少一条信息，如果把程序这样改一下：

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    int i, pid;

    pid = 0;
    for (i = 0; i < 3; i++) {
        pid = fork();
        wait(NULL);
    }
    printf("pid:%d\n", getpid());

    return 0;
}

那么答案很明显就是所有的进程个数an,上面加入wait调用的目的是使各个进程不交叉输出信息。

为了求an，先简要的介绍一下fork()系统调用，在linux中,fork()调用会调用clone(),而clone()最终会调用 do_fork()系统调用来产生子进程，关键是这个子进程怎么产生的。在linux/unix中，fork()产生的子进程相当于复制了整个父进程，首先复制了PCB，然后将内存页表共享到父进程的页面（写时复制）。通俗一点，子进程和父进程看起来是完全一样的，一样的代码段，一样的数据段，一样的进程控制块，但是他们是独立的，并且从内核返回到用户态时，系统调用对原进程返回子进程的pid,对子进程返回0，这样就可以区分父子进程了。

回到上面的问题，为什么答案3是错的，举个例子：父进程i=0的时候fork()了一个子进程p1,但是p1现在和父进程的状态是一样的，也就是会继续接着循环，从i=1来fork()一个p2,而p2又会继续从i=3开始来fork()其他的子进程，这样就会产生很多很多子进程了。

现在来求解具体的产生的进程的个数。

设f(n)表示程序中循环会执行n次时整个程序会产生的进程数，很容易得到递推公式：

f(n)=1+f(n-1)+f(n-2)+f(n-3)+…+f(0)
比如for i=0;i< p=""> <>

因为i=0时fork()的子进程下次会继续循环n-1次，i=1时 fork()的子进程下次会仅需循环n-2 次。
其中常数1是进程本身。
边界条件，f(0)=1

这样，我们就得到了问题的答案：

f(n)=1+f(n-1)+f(n-2)+…+f(0)
f(0)=1
这个可以求出闭形式：
f(0)=1
f(1)=2
f(2)=4
…

用数学归纳法可以得到f(n)=2^n

所以对于程序一，会打印出2^3-1=7行信息。

对于程序二，总共会产生2^3=8个进程。