货叉的可能组合数 [英] Number of possible combinations of fork

问题描述

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调用均成功.

In the code above, multiple ordering of the output (printf statements) can be generated based on how the operating system schedules processes for execution. How many different orderings are possible? You may assume that all fork and printf calls succeed.

我正试图帮助我的学生理解如何解决这个问题，但是当我撰写考试时，我在这个问题上得到了很好的0.我希望有人能解释该怎么做?

I'm trying to help my students understand how to approach this problem, however I got a nice 0 on this question when I wrote the exam. I was hoping someone could explain how to go about it?

推荐答案

最后我还没有弄清所有组合，但这应该可以帮助您.

I haven't worked out all the combinations at the end, but this should get you going.

您从父进程开始.它将调用fork() 3次并打印

You start with a parent process. It will call fork() 3 times, and print

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

在第一次分叉之后，有一个使用id = 1的子进程.该过程将继续循环，因此将打印

After its first fork there's one child process with id = 1. This process will continue the loop, so it will print

Process 1 created child 2
Process 1 created child 3

然后，父进程将使用id = 2派生一个子进程.此过程还将继续其循环，因此将打印

The parent process will then fork a child with id = 2. This process will also continue its loop, so it will print

Process 2 created child 3

第一代孩子就这些了.但是子级1也会派生自己的子级2，该子级会打印

That's all the first generation children. But child 1 also forks its own child 2, which will print

Process 2 created child 3

i = 3时分叉的所有进程立即退出循环.他们不会再分叉孩子或打印任何东西，因此可以忽略它们.

All the processes that are forked when i = 3 exit the loop immediately. They don't fork any more children, or print anything, so they can be ignored.

每个进程按顺序打印自己的消息，但是它们可以在进程之间以任何顺序散布.一个约束是，子级在其父级打印表示创建了较早子级的消息之前不能打印任何内容，因为该消息是在创建该子级的迭代之前打印的(我假设输出是行缓冲的).但是它可以 在表明它已创建的消息之前打印自己的消息！

Each process prints its own messages in order, but they can be interspersed in any order between the processes. The one constraint is that a a child can't print anything before its parent prints the message saying that it created an earlier child, because the message is printed before the iteration that creates the child (I'm assuming output is line buffered). But it can print its own messages before the message that says it was created!

因此前两个消息可以是:

So the first two messages can be either:

Process 0 created child 1
Process 1 created child 2

或

Process 1 created child 2
Process 0 created child 1

这篇关于货叉的可能组合数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！