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

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 по этому вопросу, когда писал экзамен. Я надеялся, что кто-нибудь может объяснить, как это сделать?


c math fork combinatorics
person Lukasz D    schedule 10.04.2019    source источник
comment
Это на каком языке?   -  person GBlodgett    schedule 11.04.2019
comment
Поскольку вывод можно чередовать, возможное количество комбинаций огромно.   -  person David Schwartz    schedule 11.04.2019
comment
Это язык Си. И да, я знаю, что это массово. Это вопрос на экзамене, требующий точного ответа, а не «он большой».   -  person Lukasz D    schedule 11.04.2019
comment
Пожалуйста, опубликуйте свой ответ и рассуждения, которые вы использовали для его расчета. Тогда мы можем помочь вам понять, где вы ошиблись. Но разве это не работа профессора или ассистента преподавателя? Ты платишь им, чтобы они научили тебя этому.   -  person Barmar    schedule 11.04.2019
comment
К сожалению, вы являетесь учителем!   -  person Barmar    schedule 11.04.2019
comment
По крайней мере, напечатайте идентификатор текущего процесса: printf("Process %d[%d] created child %d\n", getpid(),id, i); (и дочерний pid тоже)   -  person wildplasser    schedule 11.04.2019

Ответы (1)


arrow_upward
0
arrow_downward

Я не разобрался со всеми комбинациями в конце, но это должно вас заинтересовать.

Вы начинаете с родительского процесса. Он вызовет 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

or

Process 1 created child 2
Process 0 created child 1
person Barmar    schedule 10.04.2019