Creating process tree using fork

Question

I'm trying to create the process tree shown in the picture. Basically if the level is even I want to create one child process and terminate the parent process. If the level is odd I wanna create two child processes and then terminate the parent process. I have written a program right now but I think it's so hard to visualize what process tree my program is actually creating. I've written some comments to the code to explain how I've been thinking. I also want to output the PID of the bottom children of the tree which my code doesn't do correctly.

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

int main(int argc, char *argv[]){ 
    pid_t pid, ppid; 
    int n, i;
    int childstate;
    int count = 0; 

    if(argc != 2){ 
        printf("Wrong number of arguments"); 
        exit(-1); 
    } 
    n = atoi(argv[1]); 

    fork(); //start process 0
    for(i = 1; i < n + 1; i++){ 
        if(i % 2 != 0){ 
            fork(); //if odd level start 1 child process
             if(getpid() == 0){
                kill (getppid(), 9); //terminate parent process
            }
        } else { 
            if(fork() > 0){  //start new process
                fork(); //if new process is not a child start another process
                if(getpid() == 0){
                    kill (getppid(), 9); //terminate parent process
                }
            } 
        } 
        if(i == n){ //print pid of leaves (not working correctly)
            printf("Process: %d \n", getpid()); 
        } 
    }
    return 0; 
}

Answer 1

I also want to output the PID of the bottom children of the tree which my code doesn't do correctly.

Have your processes output the tree in Dot language, and use Graphviz to output the tree.

For example, if you save the following as say tree.c:

#define  _POSIX_C_SOURCE 200809L
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>

int process(const unsigned int level, const unsigned int maxlevel, FILE *dot)
{
    int           status = EXIT_SUCCESS, childstatus;
    unsigned int  children, i;
    pid_t         p, child[2];

    if (dot) {
        /* Output a node for this child, */
        fprintf(dot, "    \"%ld\" [ label=\"Process %ld\" ];\n", (long)getpid(), (long)getpid());

        /* and if not at the top level (0), an edge from our parent. */
        if (level)
            fprintf(dot, "    \"%ld\" -> \"%ld\";\n", (long)getppid(), (long)getpid());

        fflush(dot);
    }

    /* No more forking? */
    if (level >= maxlevel) {
        if (level)
            exit(status);
        else
            return status;
    }

    /* Odd levels create two child processes, even one. */
    if (level & 1)
        children = 2;
    else
        children = 1;

    /* Fork the child processes, */
    for (i = 0; i < children; i++) {
        child[i] = fork();
        if (child[i] == -1) {
            fprintf(stderr, "Cannot fork: %s.\n", strerror(errno));
            exit(EXIT_FAILURE);
        } else
        if (!child[i]) {
            /* have each child run process() and nothing else, */
            exit(process(level + 1, maxlevel, dot));
        }
        /* This line is run in parent only. */
    }

    /* and wait for them. */
    for (i = 0; i < children; i++) {
        if (child[i] != -1) {
            do {
                p = waitpid(child[i], &childstatus, 0);
            } while (p == -1 && errno == EINTR);
            if (p != child[i])
                status = EXIT_FAILURE;
        } else
            status = EXIT_FAILURE;
    }

    if (level)
        exit(status);
    else
        return status;
}

int dot_process_tree(const int levels, FILE *out)
{
    int  retval = EXIT_SUCCESS;

    if (out) {
        fprintf(out, "digraph {\n");
        fflush(out);
    }

    if (levels > 0)
        retval = process(0, levels - 1, out);

    if (out) {
        fprintf(out, "}\n");
        fflush(out);
    }

    return retval;
}

int main(void)
{
    return dot_process_tree(5, stdout);
}

and compile and run it using

reset ; gcc -Wall -Wextra -O2 tree.c -o tree && ./tree | dot -Tx11

you'll get a nice graphic process tree. (Use dot -Tsvg > out.svg or dot -Tpng > out.png to save it as an SVG or PNG image.) On my system:

Do note that there is no reason why the process IDs should be in the tree order. Although e.g. Linux hands them off in a rather ordered fashion, they can be in any order, even totally random. So do not make any assumptions on the PIDs.

The Dot language itself is simple. The output of the above program is something like

digraph {
    "12375" [ label="Process 12375" ];
    "12377" [ label="Process 12377" ];
    "12375" -> "12377";
    "12378" [ label="Process 12378" ];
    "12377" -> "12378";
    "12379" [ label="Process 12379" ];
    "12377" -> "12379";
    "12380" [ label="Process 12380" ];
    "12378" -> "12380";
    "12381" [ label="Process 12381" ];
    "12379" -> "12381";
    "12382" [ label="Process 12382" ];
    "12380" -> "12382";
    "12384" [ label="Process 12384" ];
    "12381" -> "12384";
    "12383" [ label="Process 12383" ];
    "12380" -> "12383";
    "12385" [ label="Process 12385" ];
    "12381" -> "12385";
}

which should be obvious; nodes are named by the process ID, and [ label="Title" ] sets the text in the node. It is not from the same run as the diagram above, so the process IDs differ.

In Dot, numbers do need to be quoted if used as a name, but if a name starts with a letter, you don't need to quote it. See Graphviz documentation for further details. (The Node, Edge and Graph Attributes page is the one you usually need.)

If you want the level display in each node, use

        fprintf(dot, "    \"%ld\" [ label=\"Process %ld, level %u\" ];\n", (long)getpid(), (long)getpid(), level + 1);

in process(). (It uses level 0 forwards, with all nonzero levels being child processes, and level 0 being the original process. That's why level 0 returns, and all other levels exit().)