create a process tree in C

Question

How would I approach creating a process hierarchy that would look like a balanced ternary tree of depth N? ... meaning each process has 3 children so there would be (3^N-1)/2 processes in a tree of depth N. To create the new processes, I only want to use fork().

This is what I have so far but I don't think it works because I don't deal with process IDs and also I really don't think I should do this recursively:

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

Thanks, Hristo

Answer 1

The code shown would do the job The code shown would nearly do the job (but there's a subtle problem). The other difficulty would be showing that it does the job.

The problem is that the code doesn't behave differently for the child and the parent processes after the fork. The parent process needs to complete its loop. Each child needs to restart a loop at the next level:

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

You could (should) add a 'pause();' call after the loop; this would send the parent process into suspended animation until it receives a signal. You could then show that you have a tree of processes. Alternatively, use 'sleep(30)' or some other way of suspending the processes. You don't want them to exit immediately; they'll do that too quickly for you to be able to demonstrate the tree structure.

In theory, you might want to track whether 'fork()' succeeds; in practice, it isn't clear what you'd do differently except, perhaps, not try to create the second child if the first fails (but that's likely to fail anyway, so blindly trying is probably best in the circumstances - but remember that in other situations, it would usually matter a lot).

Trees are inherently recursive structures; using recursion to manage them is often the neatest way to deal with them. This looks like it is tail recursion which means that it can be converted into a looping structure fairly easily. However, managing a data structure to keep tabs on what is happening is going to be harder than just doing it recursively.

Answer 2

This bit does not look right to me:

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

The problem is that both the parent and the child continue looping and do the recursion.

Based on the return from fork (0 in the child, > 0 in the parent, -1 on error), you should decide whether to loop or recurse.