Recursive Fibonacci using Fork in C (Pt 2)

Question

I'm attempting to write a function that recursively computes the resulting fibonacci number from a given int n using forks in C.

Here is the function specification: If doPrint is true, print it. Otherwise, provide it to the parent process. The solution should be recursive and it must fork a new child for each call. Each process should call doFib() exactly once. The method signature cannot be changed. Helper functions cannot be used.

This is a continuation of this question: Recursive Fibonacci using Fork (in C)

Unfortunately, I never figured out a solution to the problem in the last post, however this is my modified code. I thought I had it figured out (psuedo code wise) but came to find out that I still am unsure about a few pieces.

At this point, this is solely for my amusement. This is not homework and won't be covered in my class again (after the most recent test, which has passed).

static pid_t root_pid;

// Function to return exit code for PID
static int exitcode(pid_t pid)
{
    pid_t retpid;
    int status;

    retpid = waitpid(pid, &status, 0);
    if (pid != retpid)
    {
        printf("waitpid error\n");
    }

    return WEXITSTATUS(status);
}

static void doFib(int n, int doPrint)
{
    root_pid = getpid();

    pid_t pid1;
    int status1;

    pid_t pid2;
    int status2;

    if(n < 2) // Base case, exit back to parent?
    {
        exit(n);
    }
    else // if not base case, fork child processes
    {
        pid1 = fork();
        if (pid1 == 0) // Child Process 1 (for fib(n-1))
        {
            doFib(n-1, doPrint);
            exit(n-1);
        } 
        else if (pid1 > 0) // Parent Process
        {
            pid2 = fork();
            if (pid2 == 0) // Child Process 2 (for fib(n-2))
            {
                doFib(n-2, doPrint);
                exit(n-2);
            }

            // Get value from child process 1
            status1 = exitcode(pid1);
            // Get value from child process 2
            status2 = exitcode(pid2);

            // When to print?
            if (getpid() == root_pid)
            {
                int result =  status1 +  status2;
                if (doPrint)
                {
                    printf("%d\n", result);
                }
                else
                {
                    exit(result);
                }
            }
        }
    }
}

A few questions...

1. Do I need to call both of these functions for each child process?

   doFib(n-1, doPrint); exit(n-1);
   

2. Is my base case at the beginning correct? (n < 2)
3. Is my base case at the end correct? (when to print)

Thank you for any help.

Answer 1

The answer for "when to print" really comes down to what you want to print ... if you only want to print the final answer, then you'll most likely need a flag that indicates when you're in the root parent process, and use the if statement to test if you are indeed the root parent so that you only print a single number. If on the other-hand you want to print the entire sequence up to the final number, then an if statement is not needed.

For instance, a good flag value would be the PID of the root process. You could save this in a global variable called root_pid in the first couple lines of main() before you start your forking off of separate child processes. That way all the child processes will have the same value set for root_pid, and the if statement can simply be if (getpid() == root_pid).

So do something like this:

//fib.c
#include <unistd.h>
pid_t root_pid

int main()
{
    root_pid = getpid();

    //... rest of your program

}

And as mentioned above, make your if statement inside of doFib the following:

if (getpid() == root_pid)
{
    //...print results
}
else
{
    exit(result)
}

Answer 2

You should use pipes to communicate between these processes. I know it's been over a decade, but today I used a bit of your code with pipes communication and it works.

Edit: After forking, everything is copied into new process(es), so we cannot use a static/global variable in our fibonacci function as a counter. Thus, I just use a temporary counter as an index for pipes, with pipe counter+1 for fib(n-1) value (left branch), and pipe counter+2 for fib(n-2) value (right branch). They would then write back to the root using pipe counter+0. Just imagine a binary tree for the forking process then it would be easier.

Here is my function using pipe and forking. Of course, this is for academic purpose only since it takes too much resources to calculate any n above 20.

long fibonacci(int n, int counter) //counter is for pipe index
{
 pid_t pid1;
 pid_t pid2;

 if(n < 2) // Base case, exit back to parent
 {
     return n;
     exit(0); //for child process
 }
 else // if not base case, fork child processes
 {
     pid1 = fork();
     if (pid1 == 0) // Child Process 1 (for fibonacci(n-1))
     {
         long x = fibonacci(n-1, counter+1);
         write(fds[counter+1][1], &x, sizeof(long));
         exit(0);
     }
     else if (pid1 > 0) // Parent Process
     {
         pid2 = fork();
         if (pid2 == 0) // Child Process 2 (for fibonacci(n-2))
         {
             long y = fibonacci(n-2, counter+2);
             write(fds[counter+2][1], &y, sizeof(long));
             exit(0);
         }
     }
 }

 long result1;
 read(fds[counter+1][0], &result1, sizeof(long));
 long result2;
 read(fds[counter+2][0], &result2, sizeof(long));

 long result = result1 + result2;

 write(fds[counter][1], &result, sizeof(long)); //write back to the previous child process/root

 return result1 + result2;
 }
 
long fib (int index)
{
return fibonacci(index, 0);
}