Рекурсивная Фибоначчи с использованием Fork в C (Pt 2) - PullRequest
Новая
       23

Рекурсивная Фибоначчи с использованием Fork в C (Pt 2)

2 голосов
/ 16 февраля 2012

Я пытаюсь написать функцию, которая рекурсивно вычисляет результирующее число Фибоначчи из заданного int n, используя вилки в C.

Вот спецификация функции: Если doPrint имеет значение true, распечатайте его. В противном случае предоставьте это родительскому процессу. Решение должно быть рекурсивным, и оно должно создавать нового дочернего элемента для каждого вызова. Каждый процесс должен вызывать doFib () ровно один раз. Подпись метода не может быть изменена. Вспомогательные функции не могут быть использованы.

Это продолжение этого вопроса: Рекурсивный Фибоначчи с использованием Форка (в C)

К сожалению, я не нашел решения проблемы в последнем посте, однако это мой модифицированный код. Я думал, что понял (мудрый код psuedo), но пришел, чтобы узнать, что я все еще не уверен насчет нескольких частей.

На данный момент, это исключительно для моего развлечения. Это не домашнее задание и больше не будет рассматриваться в моем классе (после последнего пройденного теста). 

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

Несколько вопросов ...

  1. Нужно ли вызывать обе эти функции для каждого дочернего процесса? 

    doFib(n-1, doPrint); exit(n-1);
  2. Верен ли мой базовый случай в начале? (n <2) </li>
  3. Является ли мой базовый случай в конце правильным? (когда печатать)

Спасибо за любую помощь.

1 Ответ

1 голос
/ 16 февраля 2012

Ответ «когда печатать» действительно сводится к тому, что вы хотите напечатать ... если вы хотите напечатать только окончательный ответ, то вам, скорее всего, понадобится флаг, который указывает, когда вы находитесь вкорневой родительский процесс, и используйте оператор if, чтобы проверить, действительно ли вы являетесь корневым родителем, чтобы вы печатали только одно число.Если, с другой стороны, вы хотите напечатать всю последовательность до конечного числа, то оператор if не требуется.

Например, хорошим значением флага будет PID корневого процесса,Вы можете сохранить это в глобальной переменной с именем root_pid в первых двух строках строки main(), прежде чем начинать разветвление отдельных дочерних процессов.Таким образом, все дочерние процессы будут иметь одинаковое значение, установленное для root_pid, и оператор if может просто быть if (getpid() == root_pid).

Так что сделайте что-то вроде этого: 

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

int main()
{
    root_pid = getpid();

    //... rest of your program

}

И, как уже упоминалось выше, сделайте ваше if утверждение внутри doFib следующего: 

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