forks in C - exercise

Question

I try to repeat and learn more advanced uses and options when cutting trees with forks in the jungle of C. But foolishly I find an example which should be very easy as I have worked with forks before and even written some code, but i can't understand it fully.

Here comes :

main() {
 if (fork() == 0) {
  if (fork() == 0) {
   printf("3");
  }
  else if ((wait(NULL)) > 0) {
   printf("2");
  }
 }
 else {
  if (fork() == 0) {
   printf("1");
   exit(0);
  }
  if (fork() == 0) {
   printf("4");
  }
 }
 printf("0");
 return 0;
}

Possible solutions are :

1. 3201040
2. 3104200
3. 1040302
4. 4321000
5. 4030201
6. 1403020

where 2, 5 and 6 are correct answers.

First of all, shouldn't there be four zeroes in the output? Second... How does one come to the solution at all? Been doing this on paper for almost an hour and I'm not even close to understanding why the given solution are more correct than the false ones (except for nr3 as it can't end with 2 since a 0 must follow).

Anyone with his forks in check who can offer some good explanation?

EDIT:

Found this here look at pdf's from 2009. Can people now stop making posts about this being a homework and actually try to help? If not please find some other topics to spend your time. Thanks !

Answer 1

They are assuming that when you call wait(NULL), the entire '3' fork will execute. This includes printing the '0' at the end of that fork. Thus answers 1 and 4 are incorrect because they do not have a '0' before the '2'.

As for why there aren't four '0's, I don't know.

Answer 2

There are only three zeros in the output because of the exit statement after the program prints 1. That statement ends that process immediately. Ed: No, actually there should be 4 zeros; I had overlooked the original process. I have no idea why there are not four zeros in the answer.

What you have to understand in general when analyzing the answers to the question is this:

1. Every time you call fork() you create a new process, and the old process continues as well, both from the same point
2. You can tell if you are in the "old process" or the "new process" by examining the return value of fork. It will be 0 (false) if you are in the new process, and non-zero (true) if you are in the old process.
3. Calling wait(NULL) will suspend the current process' execution until one of the processes that forked from it finishes.
4. (Most important) The statements in different processes can execute in any order relative to each other. But the statements within a single process must, of course, remain sequential.

To elaborate on 4, imagine you have two processes, one which prints "abc", and the other which prints "xyz". Output such as "abxcyz", "xaybcz", or "xyabcz" are possible because the sequences abc and xyz each appear in order. However, the output "abzcxy" is not possible, because there is no way that z can appear before x, since they are both coming from the same process and the statements which print them appear in the other order.

Answer 3

First, the options that you have to choose from are not all of the possible permutations of output. Rather, they're only a few of them. Looking at the source code, there are a few things that we can notice to eliminate possibilities:

1. The branch that prints "1" then does exit(0) without ever going on to print "0". So there are only three 0's expected in the output. Also for this reason, the last character has t be a 0 or a 1.
2. After the second fork, we wait(NULL) for the child before printing "2". This means that the child that we wait for will always print a 3 followed by a 0 before we print a 2.

These are really the only things that can be said definitively about this problem. This means that any correct answer has to end on a 0 or a 1, and has to have both a 3 and a 0 before the 2. The only answers meeting these criteria are 2, 5, and 6.

Answer 4

I think there should be 4 zeroes, and that is what I see if I run your code...

A good way to analyse this is to draw a diagram like this one - I've shown the forks as * with the parent continuing horizontally, and the child below, so that each individual process is on a separate line:

----*----*----*----0----exit (return from main)
    |    |    |
    |    |    +----4----0----exit (return from main)
    |    |
    |    +----1----exit (explicitly)
    |
    +-----*----wait----2----0----exit (return from main)
          |
          +----3----0----exit (return from main)

Now it's easy to see that, because of the wait(), you must see 3 followed some time later by 0, before seeing 2 followed by 0.