C 中的递归斐波那契数列：Fork()

Question

我正在尝试实现一个递归斐波那契程序，该程序使用 fork() 和带有 getopt 的消息队列来设置用于打印第 n 个斐波那契数和 'm' 计算阈值的命令行选项。我的程序即将完成，但我的输出有问题。我的一个条件似乎工作正常，但另一个似乎尝试并输出这两个条件。我相信这是因为 fork() 的属性。发生这种情况是因为我们不知道子进程何时产生？

生成文件：

# 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) $@.c

fib_seq: fib_seq.c
    $(CC) $(CFLAGS) $@.c

################################ Test ##########################################

test1: myfib
    ./myfib -F 6 -S 6

test2: myfib
    ./myfib -F 6 -S 3

#############################  Clean  ##########################################

clean:
    $(RM) *.o *~ myfib* $(SO)

主要：

#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);
}

输出 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

输出 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

Answer 1

fork() 通过复制调用进程来创建新进程。我建议您详细阅读有关 fork() 的内容。

回到你的程序，你只需要在你的程序中做一些修改就可以正常工作。

更正编号1 -

在子进程中将 x-1 而不是 x 传递给 fib_seq()。

更正编号2 -

在 wait(NULL)（等待子进程的父进程）之后，您已经从 main() 中 return编辑了父进程 -

return 0;

这将退出父进程，因此无论何时派生子进程，父进程都会在子进程完成后退出。

将上面的return语句移到if (pid == 0)块中，并添加一个printf来写入由fib_seq()函数在child中执行的fib值returned过程。

    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;
    }

更正编号3 -

现在，如果子进程正在计算系列下一个值，则父进程不需要计算系列下一个值。因此，在 wait() 之后的 parent 中添加 "continue"。你的程序部分看起来像 -

 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;
 }

C 中的递归斐波那契数列：Fork()

Recursive Fibonacci in C: Fork()

c

recursion

fork

fibonacci