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().)

Answer 2

The getpid can never be zero. As I mentioned in my top comments, you want the parent to wait on children, not the other way round and too many forks.

Here's a cleaned up version that I think works:

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

int
main(int argc, char *argv[])
{
    pid_t pid;
    pid_t ppid;
    int i;
    int n;
    int pcur;
    int pcnt;

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

    pid = fork();                               // start process 0
    if (pid != 0) {
        wait(NULL);
        n = -5;
    }

    for (i = 1; i < n + 1; i++) {
        // odd/even level -- get number of children to start
        // NOTE: you may need to reverse this if
        if (i % 2 != 0)
            pcnt = 1;
        else
            pcnt = 2;

        // get parent pid
        ppid = getpid();

        // do the forks
        for (pcur = 0;  pcur < pcnt;  ++pcur)
            fork();

        // get current pid
        pid = getpid();

        // parent should wait on children
        if (pid == ppid) {
            while (wait(NULL) >= 0);
            break;
        }

        // print pid of leaves (not working correctly)
        if (i == n) {
            printf("Process: %d\n", pid);
        }
    }

    return 0;
}

Answer 3

fork(); //if odd level start 1 child process
if (getpid() == 0){
    kill (getppid(), 9); //terminate parent process
}

This logic is wrong: getpid() does not return 0 / fork doesn't return a pid in the child process - it just returns 0 to signify that it is the child process - it can know parent's pid by calling getpid before.

The logic should be:

pid_t child = fork();
if (child > 0) {
    // use exit instead of kill! exit terminates this process
    exit(0);
}
if (child < 0) {
    ... an error occurred in fork ...
}

Answer 4

From you description, your basic logic should be:

void fork_loop(int level, int stop) {
    if (level > stop) return;
    if (is_even(level)) {
        fork_child(level, stop);
        exit(0);
    } else {
        fork_child(level, stop);
        fork_child(level, stop);
        exit(0);
    }
}

Where fork_child() calls fork(). The child process would call fork_loop(level+1, stop), while the parent would return.