I'm trying to implement a recursive Fibonacci program that uses fork() and message queues with getopt to set command line options for printing the nth Fibonacci number and 'm' computing threshold. My program is almost finished, but I'm having an issue with my output. One of my conditions appears to be working correctly but the other seems to try and output both conditions. I believe this is because of the properties of fork(). Is this happening because we don't know when child processes spawn?
Makefile:
# make all: compiles and links all files
# make test1: runs executable for prob1 (n=6 m=6)
# make test2: runs executable for prob1 (n=6 m=3)
# make clean: cleans up .o and *~ files
#
# Options:
# -F => nth sequence
# -S => computing threshold
#
################################################################################
CC = gcc
CFLAGS = -g -Wall -Werror -c
OBJ = main.o fib_seq.o
################################ Make All ####################################
# Compiles all files
all: main fib_seq
$(CC) $(OBJ) -o myfib
# Compiles object files
main: main.c
$(CC) $(CFLAGS) [email protected]
fib_seq: fib_seq.c
$(CC) $(CFLAGS) [email protected]
################################ Test ##########################################
test1: myfib
./myfib -F 6 -S 6
test2: myfib
./myfib -F 6 -S 3
############################# Clean ##########################################
clean:
$(RM) *.o *~ myfib* $(SO)
Main:
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/stat.h>
int fib_seq(int x);
int main(int argc, char **argv) {
// Definitions
int x=0, fib=0;
int c, n, m, i;
int Fflag, Sflag;
pid_t pid;
// interprocess communication
const int size=4096;
char *shared_memory;
int segment_id=shmget(IPC_PRIVATE, size, S_IRUSR|S_IWUSR);
shared_memory= (char *)shmat(segment_id, NULL, 0);
// command line options using getopt for -F and -S
while ((c=getopt(argc, argv, "F:S:")) != -1)
switch(c)
{
case 'F':
Fflag = 1;
//printf("test\n");
n = atoi(optarg);
break;
case 'S':
Sflag = 1;
m= atoi(optarg);
printf("\nn = %d\nm = %d\n", n, m);
break;
default:
abort();
}
//begin fibonacci sequence
for(i=0; i<=n; i+=1) {
fib = fib_seq(x);
x+=1;
// fork child to compute next Fib numbers recursively
//if((((x-1)>m)&&((x-2)>m))) {
if((x-1)>m) {
pid=fork();
if (pid < 0) {
fprintf(stderr, "Fork failed");
return 1;
}
if (pid == 0) {
printf("\nChild computing next Fib number...\n");
fib = fib_seq(x);
printf("Child process complete\n");
}
else {
printf("\nParent waiting for child to finish...\n");
wait(NULL);
}
return 0;
}
// compute next fib numbers recursively
//else if((((x-1)<=m)&&((x-2)<=m))) {
else if((x-1)<=m) {
printf("\nComputing without child...");
fib = fib_seq(x-1);
}
printf("\nFibonacci sequence of %d is %d\n", x-1, fib);
}
return 0;
}
fib_seq:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int extern x;
int fib_seq(int x) {
int i, rint = (rand() % 30);
double dummy;
for (i = 0; i<rint*100; i++) {
dummy = 2.3458*i*8.7651/1.234;
}
if (x == 0)
return(0);
else if (x == 1)
return(1);
else
return fib_seq(x-1)+fib_seq(x-2);
}
Output 1:
n = 6
m = 6
Computing without child...
Fibonacci sequence of 0 is 0
Computing without child...
Fibonacci sequence of 1 is 1
Computing without child...
Fibonacci sequence of 2 is 1
Computing without child...
Fibonacci sequence of 3 is 2
Computing without child...
Fibonacci sequence of 4 is 3
Computing without child...
Fibonacci sequence of 5 is 5
Computing without child...
Fibonacci sequence of 6 is 8
Output 2:
n = 6
m = 3
Computing without child...
Fibonacci sequence of 0 is 0
Computing without child...
Fibonacci sequence of 1 is 1
Computing without child...
Fibonacci sequence of 2 is 1
Computing without child...
Fibonacci sequence of 3 is 2
Parent waiting for child to finish...
Child computing next Fib number...
Child process complete
fork() creates new process by duplicating the calling process. I would suggest you to read in detail about fork().
Coming back to your program, you just need to make few of corrections in your program to make it work properly.
Correction no. 1 -
Pass x-1 instead of x to fib_seq() in child process.
Correction no. 2 -
After wait(NULL) (parent waiting for child), you have returned the parent process from main() -
return 0;
This will exit the parent process, so whenever the child process is spawned the parent process will exit after the child process finishes.
Move the return statement above in if (pid == 0) block and add a printf to write the fib value returned by fib_seq() function executed in child process.
if (pid == 0) {
printf("\nChild computing next Fib number...\n");
fib = fib_seq(x-1);
printf("\nFibonacci sequence of %d is %d\n", x-1, fib);
printf("Child process complete\n");
return 0;
}
Correction no. 3 -
Now, if the child process is calculating the series next value than the parent does not need to calculate the series next value. So, add "continue" in parent after wait(). The part of your program will look like -
if (pid == 0) {
printf("\nChild computing next Fib number...\n");
fib = fib_seq(x-1);
printf("\nCHILD Fibonacci sequence of %d is %d\n", x-1, fib);
printf("Child process complete\n");
return 0;
}
else {
printf("\nParent waiting for child to finish...\n");
wait(NULL);
continue;
}