Chinaunix首页 | 论坛 | 博客
  • 博客访问: 346315
  • 博文数量: 161
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 345
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-13 11:04
文章分类

全部博文(161)

文章存档

2015年(15)

2014年(144)

2013年(2)

我的朋友

分类: LINUX

2014-11-10 13:34:02

原文地址:fork()调用的一个趣题 作者:

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

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <sys/types.h>
  3. #include <unistd.h>

  4. int main(int argc, char *argv[])
  5. {
  6.     int i, pid;

  7.     pid = 0;
  8.     for (i = 0; i < 3; i++) {
  9.         pid = fork();
  10.         if (pid == 0)
  11.             printf("pid:%d\n", getpid());
  12.     }

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

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <sys/types.h>
  3. #include <unistd.h>

  4. int main(int argc, char *argv[])
  5. {
  6.     int i, pid;

  7.     pid = 0;
  8.     for (i = 0; i < 3; i++) {
  9.         pid = fork();
  10.         wait(NULL);
  11.     }
  12.     printf("pid:%d\n", getpid());

  13.     return 0;
  14. }
那么答案很明显就是所有的进程个数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个进程。
阅读(718) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~