Количество возможных комбинаций вилки

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

После его первой ветки есть один дочерний процесс с id = 1. Этот процесс продолжит цикл, поэтому он напечатает

Process 1 created child 2
Process 1 created child 3

Затем родительский процесс разветвляет дочерний элемент с id = 2. Этот процесс также продолжит свой цикл, поэтому он напечатает

Process 2 created child 3

Это все дети первого поколения. Но потомок 1 также разветвляет своего потомка 2, который напечатает

Process 2 created child 3

Все процессы, которые разветвляются, когда i = 3 немедленно выходит из цикла. Они больше не разветвляют детей и не печатают что-либо, поэтому их можно игнорировать.

Каждый процесс печатает свои собственные сообщения по порядку, но они могут чередоваться в любом порядке между процессами. Единственное ограничение заключается в том, что дочерний элемент не может ничего напечатать до того, как его родитель напечатает сообщение о том, что он создал более ранний дочерний элемент, поскольку сообщение печатается до итерации, которая создает дочерний элемент (я предполагаю, что выходные данные являются буферизованными строками). Но он может напечатать свои собственные сообщения до того, как сообщение о том, что оно было создано!

Итак, первые два сообщения могут быть:

Process 0 created child 1
Process 1 created child 2

или

Process 1 created child 2
Process 0 created child 1