c - fork 的可能组合数

Question

int main(void) { 
  int id = 0;
  for(int i = 1; i < 4; i++) {
    if(fork() == 0) {
      id = i;
    } else {
      printf("Process %d created child %d\n", id, i);
    }
  }
  return 0;
}

在上面的代码中，可以根据操作系统如何安排进程执行来生成输出(printf 语句)的多个排序。有多少种不同的顺序是可能的？您可以假设所有 fork 和 printf 调用都成功。

我试图帮助我的学生理解如何解决这个问题，但是当我写考试时，我在这个问题上得了 0 分。我希望有人可以解释如何去做？

Answer 1

最后我还没有算出所有的组合，但这应该能让你继续下去。

您从父进程开始。它会调用 fork() 3 次，然后打印

Process 0 created child 1
Process 0 created child 2
Process 0 created child 3

在它的第一个 fork 之后，有一个 id = 1 的子进程。这个过程会继续循环，所以会打印

Process 1 created child 2
Process 1 created child 3

然后父进程将派生一个 id = 2 的子进程。这个过程也会继续它的循环，所以它会打印

Process 2 created child 3

这就是所有的第一代 child 。但是 child 1 也 fork 了它自己的 child 2，它将打印

Process 2 created child 3

当i = 3 时 fork 的所有进程立即退出循环。他们不会再 fork 任何 child ，也不会打印任何东西，所以他们可以被忽略。

每个进程按顺序打印自己的消息，但它们可以以任何顺序散布在进程之间。一个限制是，一个 child 在其 parent 打印消息说它创建了一个较早的 child 之前不能打印任何东西，因为该消息是在创建 child 的迭代之前打印的(我假设输出是行缓冲的)。但它可以在表明它已创建的消息之前打印自己的消息!

所以前两条消息可以是:

Process 0 created child 1
Process 1 created child 2

或

Process 1 created child 2
Process 0 created child 1