在嵌套循环中分叉

Question

谁能解释一下这个程序创建了多少个子进程？答案是127，但我不明白他们是怎么得到的。

int create(int num){
int i;
for(i=0;i<num;i++)
fork();
}

int main() {
int i;
fork();
for(i=0;i<4;i++)
create(i);
return 0; 
}

Answer 1

这听起来确实像是操作系统 class 的作业问题，但这是一个有趣的问题，所以我会为您解答。首先，让我们看一下代码如下。在功能上，它是同一件事，但它会让事情更容易消化。此外，首先，让我们忽略最初的 fork() 调用。如果不存在，我们将计算有多少，然后如果我们将其重新添加，我们将拥有相同数量的进程，乘以两倍。

int main() {
    int i, j;
    // fork();
    for (i = 0; i < 4; i++) {
      for (j = 0; j < i; j++) {
        fork();
      }
    }
}

现在这部分是数学问题，部分是编程问题。首先，我们需要了解调用 fork() 时会发生什么。当您创建一个 child 进程时，child 继承它自己的所有 parent 变量的副本，在 fork()打电话了。所以这意味着现在 parent 和 child 具有完全相同的变量的副本，它们具有完全相同的值，但它们可以独立修改这些变量，并且不会相互影响。那么在下面的简单例子中，

int main() {
    int i = 0, pid = fork();

    if (pid == 0) {
      i = 1;
    }

    if (pid > 0) {
      i = 2;
    }
}

在parents的世界里，i的值是2，在child的世界里i的值是1，现在这些都是我们正在讨论的独立变量，因此 parent 可以有它想要的，child 可以有它想要的，它们不会冲突，每个人都很开心。

现在，要回答您的问题，我们必须牢记这一点。因此，让我们看看在没有初始 fork() 调用的情况下我们首先有多少个进程。那么现在，parent 本身将产生 6 个 child 进程。对于这些过程中的每一个，变量 (i,j) 将具有值 (1,0)、(2,0)、(2,1)、(3,0)、(3,1) 和 (3, 2), 分别.

所以在 (3,2) 生成的最后一个 child 将退出循环，并且不会再生成 children。在 (3,1) 生成的 child 将继续 for 循环，递增 j，生成另一个进程，然后两个 children 将在 (3 ,2),退出for循环，然后死掉。然后我们有另一个 child 由 parent 在 (3,0) 产生。那么现在这个 child 将继续通过 for 循环，在 (3,1) 和 (3,2) 处生成一个 child，然后死亡，然后这个新的 child 生成在(3,1) 会产生另一个 child 然后它们就会死去。我想我们可以看到这开始变得相当复杂，所以我们可以用下图来表示这种情况。

图中的每个顶点代表一个进程，标记为 p 的顶点是 parent 进程。每条边上的有序对表示在 child 进程生成时 (i,j) 的值。注意我们如何对流程进行分组。在第一组中，我们有 1 个流程，接下来有 2 个，接下来的 4 个，然后是 8 个，我们现在应该看看事情进展如何。下一组将有 16 个进程，下一组将有 32 个。因此，如果我们计算我们拥有的所有进程，包括 parent，我们有 64 个进程。到目前为止有意义吗？

那么现在让我们把最初的 fork() 回调放回去。这将导致我们刚才描述的完全相同的情况发生两次，这将使我们总共有 128 个进程，包括 parent，也就是说我们已经生成了127个children.

是的，一半是数学问题，一半是编程问题。让我知道你的问题。

您可以将第一个循环重写为 for (i = 1; i <= n; i++)。然后我很确定我们可以说一般来说，你的 parent 进程会产生 $2(\sum_{k=1}^{N} 2^{k}) - 1$ children，其中 $N=\frac{n(n+1)}{2}$

在嵌套循环中分叉

fork in nested loops

fork

parent-child

nested-loops

child-process