Thread: binary tree of processes

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    10

    binary tree of processes

    I am having trouble developing a program in C that will fork/create processes in the form of a binary tree. The idea is that the program takes in a command-line argument between 1 and 7, which represents the depth of the binary tree. The program should create processes until the specified depth of the binary tree is reached. Each process also has a random data value between 1 and 5. If a process forks another set of child processes then its data value will grow to be the sum of all of the data values of its child and grandchild processes, etc. So if the command-line argument is 3 then the tree should look something like this, in theory:
    Code:
                           7(2)
               3(4)
                           6(2)
    1(2)
                           5(3)
               2(1)
                           4(4)
    The program will output a line for each process when it is created which declares that process' pid, its parent's pid, its process # (overall), and its data value. Upon exiting, each process will print another line of output which states its process #, its pid, and its data value. So for example, process #4 would print out that it is Process 4, its pid (whatever it may be), and its data value of 4. Process #2 would print out that it is Process 2, its pid, and its data value is calculated to be 8 (the sum of the data values from processes 4 and 5). My program doesn't appear to be correct at all. It is creating too many processes and the data values for any process that has children gets way too big. Because the exit function can only return a value between 0 and 255, 255 is the maximum data value that process #1 could have. That is the reason that the random numbers can only be between 1 and 5 and there is a maximum depth of 7. If all processes in a tree of depth 7 have data values of 5, then the 1st process should end up with a data value of 255. So, I really need some help because I have no idea what I am doing wrong and I don't know where to go from here. Thank you, and my code is posted below.

    Code:
    #include <stdio.h>
    
    void buildTree(int depth)
    {
            int i = 0;
            int pid, status;
            int total = 2; //total number of processes that need to be created
            int data = 0;
    
            if(depth > 1)
            {
                    //performs pow with ints
                    //2^depth to get the total number of processes in the tree
                    for(i = 0; i < depth; i++ )
                    {
                            total = total*2;
                    }
    
                    total--; //subtract 1 from the total because the top level only has 1 process
    
                    for(i = 0; i < total; i++)
                    {
                            pid = fork();
    
                            if(pid < 0)
                            {
                                    //Error
                                    printf("Fork failed\n");
                                    exit(1);
                            }
                            else if(pid == 0)
                            {
                                    //Child
                                    srand(getpid());
                                    data = 1 + rand()%5; //get a random value to store in process
    
                                    //print the child's information
                                    printf("My pid is %d, my parent pid is %d, my data value is %d\n", getpid(), getppid(), data);
    
                                    if(depth > 0) //another level of the tree needs to be created
                                            buildTree(--depth);
                                    else //no more levels need to be created so prepare to exit
                                            printf("My pid is %d and my exit value is %d.\n", getpid(), data);
    
                                    exit(data); //exit and return the data value currently stored
    
                                    return;
                            }
                            else
                            {
                                    //Parent
                                    wait(&status); //wait for child and store returned value in status
                                    data = data + status; //add child's data value to parent's
                                    printf("My pid is %d and my exit value is %d.\n", getpid(), data); //parent is exiting, so print its information
                            }
                    }
            }
            else
                    total = 1; //there is only 1 process
    }
    
    int main(int argc, char *argv[])
    {
            if(argc != 2)
                    printf("Usage: <program> <integer>\n");
            else
            {
                    int depth = atoi(argv[1]);
                    buildTree(depth);
            }
    
            return 0;
    }
    Last edited by gregulator; 02-27-2005 at 05:29 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Start with a program which just creates a tree from your input parameters.
    At each node, print out how many child nodes it has - should be 0, 1 or 2.

    Code:
    void buildTree(int depth) {
      // some stuff
      printf( "This node has %d children\n", nchilds );
      // more stuff
    }
    Once you've done that, then you can modify to
    Code:
    void buildTree(int depth) {
      // some stuff
      printf( "This node has %d children\n", nchilds );
      createChildren( nchilds );
      sum = waitChildren( nchilds );
      exit( sum );
      // more stuff
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM