создать дерево процессов в C - PullRequest
Новая
       13

создать дерево процессов в C

0 голосов
/ 01 марта 2010

Как бы я подошел к созданию иерархии процессов, которая выглядела бы как сбалансированное троичное дерево глубины N? ... это значит, что у каждого процесса есть 3 дочерних элемента, поэтому в дереве глубины N будет (3 ^ N-1) / 2 процесса. Чтобы создать новые процессы, я хочу использовать только fork ().

Это то, что у меня пока есть, но я не думаю, что это работает, потому что я не имею дело с идентификаторами процессов, а также я не думаю, что мне следует делать это рекурсивно: 

void createTernaryTree(int n) {
   if((n-1) == 0) return;
   else {
      int x;
      for(x=0; x<3; x++) {
         fork();
         createTernaryTree(n-1);
      }
   }
}

Спасибо, Христо

Ответы [ 2 ]

2 голосов
/ 01 марта 2010

Этот бит мне не подходит: 

for(x=0; x<3; x++) {
   fork();
   createTernaryTree(n-1);
}

Проблема в том, что и родитель, и потомок продолжают цикл и выполняют рекурсию.

На основе возврата из fork (0 в дочернем элементе,> 0 в родительском элементе, -1 в случае ошибки) вы должны решить, выполнять цикл или рекурсив.

0 голосов
/ 01 марта 2010

Показанный код будет выполнять работу Показанный код будет почти выполнять работу (но есть небольшая проблема). Другая трудность - показать, что он выполняет свою работу.

Проблема в том, что код не ведет себя по-разному для дочернего и родительского процессов после разветвления. Родительский процесс должен завершить свой цикл. Каждому ребенку нужно перезапустить цикл на следующем уровне: 

  for (int x = 0; x < 3; x++) // C99
  {
     if (fork() == 0)
     {
         createTernaryTree(n-1);
         break;  // Per comment from R Samuel Klatchko
     }
  }
  pause();  // See below

Вы можете (должны) добавить 'pause ();' вызов после цикла; это отправит родительский процесс в приостановленную анимацию, пока он не получит сигнал. Затем вы можете показать, что у вас есть дерево процессов. В качестве альтернативы, используйте «sleep (30)» или другой способ приостановки процессов. Вы не хотите, чтобы они немедленно вышли; они сделают это слишком быстро, чтобы вы смогли продемонстрировать древовидную структуру.

Теоретически, вы можете отследить, успешно ли выполняется fork (); на практике неясно, что вы будете делать по-другому, за исключением, возможно, не попытки создать второго ребенка, если первый потерпит неудачу (но это, скорее всего, не удастся, так что слепая попытка, вероятно, лучше в данных обстоятельствах - но помните, что в других ситуациях это будет иметь большое значение).

Деревья по своей природе являются рекурсивными структурами; использование рекурсии для управления ими часто является самым лучшим способом борьбы с ними. Похоже, что это хвостовая рекурсия, что означает, что ее можно довольно легко преобразовать в циклическую структуру. Однако управлять структурой данных для отслеживания происходящего будет сложнее, чем просто делать это рекурсивно.

...