I'm trying to make a diagram of fork() process calls in C

Question

Here's where I am now

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

main(){   
    int n;
    int i;
    int x = 1;

    printf("\nenter number of forks:\n");
    scanf ("%d",&n);
    printf("\nnow forking %d times....\n\n", n);

    for (i = 1;i <= n; i++){
        int pid = fork();
        if (pid < 0){ 
            return -1;
        }

        if (pid != 0){
            printf("\nI am the parent (
                ppid = %d pid = %d)\n",getppid(),getpid()
            );          
            printf(" x = %d\n",x);

            x++;
            wait();
        }else{
            printf("\nI am the child (
                ppid = %d, pid = %d)\n x = 
                %d\n-------------------------------\n",
                getppid(),getpid(),x
            );
        }
    }
}

and here is my output when I pass in 4:

enter number of forks:
4

now forking 4 times....


I am the parent (ppid = 26178 pid = 39785)
 x = 1

I am the child (ppid = 39785, pid = 39786)
 x = 1
-------------------------------

I am the parent (ppid = 39785 pid = 39786)
 x = 1

I am the child (ppid = 39786, pid = 39787)
 x = 1
-------------------------------

I am the parent (ppid = 39786 pid = 39787)
 x = 1

I am the child (ppid = 39787, pid = 39788)
 x = 1
-------------------------------

I am the parent (ppid = 39787 pid = 39788)
 x = 1

I am the child (ppid = 39788, pid = 39789)
 x = 1
-------------------------------

I am the parent (ppid = 39786 pid = 39787)
 x = 2

I am the child (ppid = 39787, pid = 39790)
 x = 2
-------------------------------

I am the parent (ppid = 39785 pid = 39786)
 x = 2

I am the child (ppid = 39786, pid = 39791)
 x = 2
-------------------------------

I am the parent (ppid = 39786 pid = 39791)
 x = 2

I am the child (ppid = 39791, pid = 39792)
 x = 2
-------------------------------

I am the parent (ppid = 39785 pid = 39786)
 x = 3

I am the child (ppid = 39786, pid = 39793)
 x = 3
-------------------------------

I am the parent (ppid = 26178 pid = 39785)
 x = 2

I am the child (ppid = 39785, pid = 39794)
 x = 2
-------------------------------

I am the parent (ppid = 39785 pid = 39794)
 x = 2

I am the child (ppid = 39794, pid = 39795)
 x = 2
-------------------------------

I am the parent (ppid = 39794 pid = 39795)
 x = 2

I am the child (ppid = 39795, pid = 39796)
 x = 2
-------------------------------

I am the parent (ppid = 39785 pid = 39794)
 x = 3

I am the child (ppid = 39794, pid = 39797)
 x = 3
-------------------------------

I am the parent (ppid = 26178 pid = 39785)
 x = 3

I am the child (ppid = 39785, pid = 39798)
 x = 3
-------------------------------

I am the parent (ppid = 39785 pid = 39798)
 x = 3

I am the child (ppid = 39798, pid = 39799)
 x = 3
-------------------------------

I am the parent (ppid = 26178 pid = 39785)
 x = 4

I am the child (ppid = 39785, pid = 39800)
 x = 4
-------------------------------

The first thing I notice is that for each instance of the code run, the PPID of the "child" is the PID of the "parent", so that's good.

But when I draw a diagram by hand: diagram of my output (I'm new so I can't post photos)

For the sake of the assignment, it should be a balanced tree so that the idea of a level is significant. I'm expected to print each process as a node in a diagram such as I have drawn using graphviz, and each node should include its PID and its Level.

Here is an example from Geeks for Geeks showing what I mean by level:


       L1       // There will be 1 child process 
    /     \     // created by line 1.
  L2      L2    // There will be 2 child processes
 /  \    /  \   //  created by line 2
L3  L3  L3  L3  // There will be 4 child processes 
                // created by line 3

I think I over coded this. How should I alter my code to fork this in a loop and gain a tree-like structure? I am trying to use the variable x to denote the level, but I am not sure if it is working or not, since the structure of the output is quite unexpected to me.

yes but it lacks the kind of organization required to have defined levels like in the diagram. It should look more like the example but its all over the place — plants, Sep 25 '20 at 20:45
Your output is going to get gummed up by lack of `fflush`. When you call printf and then fork without flushing, you should expect the data to be written twice. If you fork multiple times without flushing the output streams, you will see the same messages repeated. Try redirecting to a file and see what happens. (When you redirect, you can expect stdout to be block buffered instead of line buffered.) — William Pursell, Sep 25 '20 at 21:12
@plants Maybe I interpreted "not a tree at all" a bit too literally :D — klutt, Sep 25 '20 at 21:16
@WilliamPursell you are exactly right, I tried routing it to an output.txt and it was exactly as described. Also it would like hang without asking for input, then I could just enter input unprompted and it would run but the text file would be all out of sorts repeating the whole thing over and over. I'm going to review fflush docs to see where the best place to put the call would be, bc I need to have graphviz diagram this at some point as well. — plants, Sep 25 '20 at 21:18

Crowman · Accepted Answer · 2020-09-25T21:52:55.597

Your intuition is at fault. During each iteration of your loop, all your processes will fork and create a new process - not only the processes that were created on the previous iteration.

Thus, with 4 iterations, you'd expect the initial process to end up with four children:

one with 3 children (55 in your diagram)
one with 2 children (63 in your diagram)
one with 1 child (67 in your diagram); and
one with no children (69 in your diagram)

and this is precisely what you have ended up with. If you follow the same logic with each of those children and an appropriately reduced number of remaining loop iterations, you'll reproduce exactly the diagram that you have.

This question isn't an exact duplicate, but covers much of the same ground.

Your diagram is a tree, of course - it's just not a completely balanced binary tree. To get such a result, you'd have to do something more along the lines of the following during each loop iteration:

Fork the process twice
In each of the children, continue immediately to the next loop iteration (so that neither of them fork again until the next iteration)
In the parent, break from the loop altogether after forking, so that it doesn't fork again, ever

For example:

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

int main(void) {
    int level;

    for ( level = 1; level <= 3; level++ ) {
        pid_t pids[2];

        pids[0] = fork();
        if ( pids[0] == -1 ) {
            perror("fork failed");
            exit(EXIT_FAILURE);
        } else if ( pids[0] == 0 ) {
            continue;
        }

        pids[1] = fork();
        if ( pids[1] == -1 ) {
            perror("fork failed");
            exit(EXIT_FAILURE);
        } else if ( pids[1] == 0 ) {
            continue;
        }

        for ( int i = 0; i < 2; i++ ) {
            if ( waitpid(pids[i], NULL, 0) == -1 ) {
                perror("waitpid failed");
                exit(EXIT_FAILURE);
            }
        }

        break;
    }

    printf("level %d: parent %ld, child %ld\n", level, (long) getppid(), (long) getpid());

    return 0;
}

with output, showing your completely balanced binary tree:

me@mac:$ ./fork | sort
level 1: parent 62427, child 73103
level 2: parent 73103, child 73105
level 2: parent 73103, child 73106
level 3: parent 73105, child 73107
level 3: parent 73105, child 73109
level 3: parent 73106, child 73108
level 3: parent 73106, child 73111
level 4: parent 73107, child 73110
level 4: parent 73107, child 73114
level 4: parent 73108, child 73112
level 4: parent 73108, child 73116
level 4: parent 73109, child 73113
level 4: parent 73109, child 73117
level 4: parent 73111, child 73115
level 4: parent 73111, child 73118

Can you tell me what the call to waitpid is doing at the bottom? — plants, Sep 26 '20 at 00:12
@plants: It's just waiting for the child processes to terminate. `waitpid` is more capable than `wait`, but in this particular example it's basically the same as your `wait` call, except it explicitly specifies the PID of the process it wants to wait for. — Crowman, Sep 26 '20 at 00:30
man i wish i was more established here so I could openly vote on your genuinely amazing responses, thank you. I probably have more questions, but for now just know that you have helped me a lot. — plants, Sep 26 '20 at 04:03
@plants: No problem. Don't forget to mark the answer as accepted, if it solved your problem to your satisfaction. — Crowman, Sep 26 '20 at 04:40
@plants: Because in the diagram you give to show what you want, each process has exactly two children (except those in the final level, which have none). In order to create two children, a process has to fork twice. — Crowman, Sep 28 '20 at 22:35

I'm trying to make a diagram of fork() process calls in C

1 Answers1