76

Why does this program print “forked!” 4 times?

#include <stdio.h>
#include <unistd.h>

int main(void) {

  fork() && (fork() || fork());

  printf("forked!\n");
  return 0;
}
gsamaras
  • 71,951
  • 46
  • 188
  • 305
Rawan Lezzeik
  • 891
  • 1
  • 8
  • 8

6 Answers6

210

The one comes from main() and the other three from every fork().

Notice that all three forks() are going to be executed. You might want to take a look at the ref:

RETURN VALUE

Upon successful completion, fork() shall return 0 to the child process and shall return the process ID of the child process to the parent process. Both processes shall continue to execute from the fork() function. Otherwise, -1 shall be returned to the parent process, no child process shall be created, and errno shall be set to indicate the error.

Note that the process id cannot be zero, as stated here.


So what really happens?

We have:

fork() && (fork() || fork());

So the first fork() will return to the parent its non zero process id, while it will return 0 to the child process. That means that the logic expression's first fork will be evaluated to true in the parent process, while in the child process it will be evaluated to false and, due to Short circuit evaluation, it will not call the remaining two fork()s.

So, now we know that are going to get at least two prints (one from main and one from the 1st fork()).

Now, the 2nd fork() in the parent process is going to be executed, it does and it returns a non-zero value to the parent process and a zero one in the child process.

So now, the parent will not continue execution to the last fork() (due to short circuiting), while the child process will execute the last fork, since the first operand of || is 0.

So that means that we will get two more prints.

As a result, we get four prints in total.


Short circuiting

Here, short circuiting basically means that if the first operand of && is zero, then the other operand(s) is/are not evaluated. On the same logic, if an operand of a || is 1, then the rest of the operands do not need evaluation. This happens because the rest of the operands cannot change the result of the logic expression, so they do not need to be executed, thus we save time.

See example below.


Process

Remember that a parent process creates offspring processes which in turn create other processes and so on. This leads to a hierarchy of processes (or a tree one could say).

Having this in mind, it's worth taking a look at this similar problem, as well as this answer.


Descriptive image

I made also this figure which can help, I guess. I assumed that the pid's fork() returned are 3, 4 and 5 for every call.

fork nodes Notice that some fork()s have a red X above them, which means that they are not executed because of the short-circuiting evaluation of the logic expression.

The fork()s at the top are not going to be executed, because the first operand of the operator && is 0, thus the whole expression will result in 0, so no essence in executing the rest of the operand(s) of &&.

The fork() at the bottom will not be executed, since it's the second operand of a ||, where its first operand is a non-zero number, thus the result of the expression is already evaluated to true, no matter what the second operand is.

And in the next picture you can see the hierarchy of the processes: Process hierarchy based on the previous figure.


Example of Short Circuiting

#include <stdio.h>

int main(void) {

  if(printf("A printf() results in logic true\n"))
    ;//empty body

  if(0 && printf("Short circuiting will not let me execute\n"))
    ;
  else if(0 || printf("I have to be executed\n"))
    ;
  else if(1 || printf("No need for me to get executed\n"))
    ;
  else
  printf("The answer wasn't nonsense after all!\n");

  return 0;
}

Output:

A printf() results in logic true
I have to be executed
Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305
86

The first fork() returns a non-zero value in the calling process (call it p0) and 0 in the child (call it p1).

In p1 the shortcircuit for && is taken and the process calls printf and terminates. In p0 the process must evaluate the remainder of the expression. Then it calls fork() again, thus creating a new child process (p2).

In p0 fork() returns a non-zero value, and the shortcircuit for || is taken, so the process calls printf and terminates.

In p2, fork() returns 0 so the remainder of the || must be evaluated, which is the last fork(); that leads to the creation of a child for p2 (call it p3).

P2 then executes printf and terminates.

P3 then executes printf and terminates.

4 printfs are then executed.

psmears
  • 26,070
  • 4
  • 40
  • 48
Jean-Baptiste Yunès
  • 34,548
  • 4
  • 48
  • 69
  • 3
    could you please explain "shortcircuit for && is taken"? – Rawan Lezzeik Nov 03 '14 at 15:04
  • 8
    @rona-altico, check the link about shortcircuit in my answer. It basically means that if the first operand of `&&` is zero, then the other operand(s) are not evaluated. On the same logic, if an operand of a `||` is 1, then the rest operands to not need evaluation. This happens because the rest operands can not change the result of the logic expression, so they do not need to be executed, thus we save time. Better now rona? Nice question by the way, I can't see why the downvotes. You gtot my +1. – gsamaras Nov 03 '14 at 15:09
  • 3
    @rona-altico: I have a hard time understanding why you'd want to use `fork()`, but do not even know what short circuiting is. Was this a question at school? – Sebastian Mach Nov 04 '14 at 11:55
  • 2
    @G.Samaras: I guess it's downvoted because it's one of many duplicates, and shows no effort even to google it before asking here. – chrk Nov 04 '14 at 12:45
  • 4
    @G.Samaras: You can't see why the downvotes? This is a _terrible_ question. There is an exact duplicate and he didn't bother to explain what different output he expected. Why this has 41 upvotes is entirely beyond me; usually this sort of thing quickly reaches -3 or -4. – Lightness Races in Orbit Nov 06 '14 at 17:24
  • Yeah chrk already explained me why the downvotes @LightnessRacesinOrbit and I agree. :) – gsamaras Nov 06 '14 at 17:26
  • 1
    @G.Samaras: Okay great :) – Lightness Races in Orbit Nov 06 '14 at 17:30
  • 1
    @LightnessRacesinOrbit people with heavily-followed blogs sometimes post links to SO questions (usually in order to farm karma, maybe that happened here) – M.M Nov 09 '14 at 22:15
14

For all the downvoters, this is from a merged but different question. Blame SO. Thank you.

You can decompose the problem to three lines, the first and last lines both simply double the number of processes.

fork() && fork() || fork();

The operators are short-circuiting, so this is what you get:

       fork()
      /      \
    0/        \>0
 || fork()     && fork()
     /\            /   \
    /  \         0/     \>0
   *    *     || fork()  *
                /   \
               *     *

So this is altogether 4 * 5 = 20 processes each printing one line.

Note: If for some reason fork() fails (for example, you have some limit on the number of processes), it returns -1 and then you can get different results.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • Thanks @yi_H for your response and one thing if only this line is there in our code then the output would be 5 times forked?? – Amit Singh Tomar Aug 17 '11 at 11:29
  • And also fork1() || fork2() && fork3(); this statement results in 16 process. – Amit Singh Tomar Aug 17 '11 at 11:34
  • Hi @yi_H am just confuse how "fork1() || fork2() && fork3()" results in 16 in total . I mean can i have a diagram like this you mentioned above – Amit Singh Tomar Oct 25 '11 at 08:58
  • Without any parentheses you may be parsing the logical tree incorrectly. Doesn't the false (0) path from the first fork() cause the entire expression to be short-circuited at the &&? I *think* the associativity priority of && and || in C are from right to left so that a simple evaluation from left to right can short-circuit the rest of the sub-expression (within any containing parentheses). It's the same as fork() && (fork() || fork()) This would then explain the 4 (not 5) processes from this line alone and 16 total. It may be different in C++ or C#, but this question was in C. – Rob Parker Nov 04 '14 at 00:03
  • Hmm, I may have misunderstood the other comments, but it sounded like @AmitSinghTomar was getting 16 lines printed from the original program. The key point is whether && has higher priority than || (as in C#) and forces grouping as (fork() && fork()) || fork() or they have equal priority (and from right to left as I recall) grouping it as fork() && (fork() || fork()). The former grouping would split into 5 processes (or 20 total) while the latter grouping would only split into 4 (or 16 total). Unfortunately, I don't have a C compiler handy to test it. – Rob Parker Nov 04 '14 at 00:35
  • 3
    This answers the question that uses `fork() && fork() || fork();`, while the question here uses `fork() && (fork() || fork());`. There was a merge, as discussed here: "http://meta.stackoverflow.com/questions/281729/my-top-answer-was-deleted-and-my-worst-question-is-still-not-deleted". You might want to edit your answer, notifying future readers. – gsamaras Jan 05 '15 at 18:14
  • Karoly I just saw your comment. In an attempt to gather all the info in one post I guess. Nice answer by the way, I had upvoted it in the past. :) – gsamaras Jan 05 '15 at 20:31
  • @gsamaras, why it has been merged. I was the one who asked the original Question and it covers few more aspect of C(like associativity of logical operators). I believe Karols' answer is very much complete.If possible please undo the merge . – Amit Singh Tomar Aug 13 '16 at 19:00
  • @AmitSinghTomar because that was the outcome of the meta talk. I suppose you read my answer before posting, but I don't see an upvote, does that mean that's something is wrong with it? :/ – gsamaras Aug 13 '16 at 20:18
  • @gsamaras, to be honest I am not worrying about up votes or points. All I want is right things should come out . I believe both questions and their answers have their own advantageous or the point it proves.Merging it into one question looks bit weird and loss of information. – Amit Singh Tomar Aug 13 '16 at 20:41
  • @AmitSinghTomar obviously votes it's not the point here, correctness is. I see your point, but that was what was decided in Meta by the big guys.. – gsamaras Aug 13 '16 at 21:38
9

Executing fork() && (fork() || fork()), what happens

Each fork gives 2 processes with respectively values pid (parent) and 0 (child)

First fork :

  • parent return value is pid not null => executes the && (fork() || fork())
    • second fork parent value is pid not null stops executing the || part => print forked
    • second fork child value = 0 => executes the || fork()
      • third fork parent prints forked
      • third fork child prints forked
  • child return value is 0 stop executing the && part => prints forked

Total : 4 forked

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
8

I like all the answers that have already been submitted. Perhaps if you added a few more variables to your printf statement, it would be easier for you to see what is happening.

#include<stdio.h>
#include<unistd.h>

int main(){

   long child = fork() && (fork() || fork());
   printf("forked! PID=%ld Child=%ld\n", getpid(), child);
   return 0;
}

On my machine it produced this output:

forked! PID=3694 Child = 0
forked! PID=3696 Child = 0
forked! PID=3693 Child = 1
forked! PID=3695 Child = 1
Bradley Slavik
  • 875
  • 7
  • 13
  • 5
    What about the values returned by each call to fork()? How about: `long f1,f2,f3; (f1 = fork()) && ((f2 = fork()) || (f3 = fork()));` and then print the PID and the three individual values. – Rob Parker Nov 04 '14 at 00:10
5

This code:

fork();
fork() && fork() || fork();
fork();

gets 20 processes for itself and 20 times Printf will go.

And for

fork() && fork() || fork();

printf will go a total of 5 times.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Mayank Dixit
  • 71
  • 2
  • 5
  • 2
    This answers the question that uses `fork() && fork() || fork();`, while the question here uses `fork() && (fork() || fork());`. There was a merge, as discussed here: "http://meta.stackoverflow.com/questions/281729/my-top-answer-was-deleted-and-my-worst-question-is-still-not-deleted". You might want to edit your answer, notifying future readers. – gsamaras Jan 05 '15 at 18:18