fork() threads : divide and conquer sum of array-CodePudding

EDIT : Thanks everyone, I adjusted my code using pipes and communicating to the main process.

My code now returns "12" which is the sum of half the array.

The other half is not summed in the return.

Here is the new code : (I am aware of memory leaks and odd arrays, I just want to grasp the logic)

#define THRESHOLD 2

int fd[2];

int compute(int *arr, int len) {
    if (len > THRESHOLD) {
        if (fork() == 0) {
            close(fd[0]);
            int half = (len / 2);
            int *left = malloc(half * sizeof(int));
            int *right = malloc(half * sizeof(int));
            memcpy(left, arr, half * sizeof(int));
            memcpy(right, arr   half, half * sizeof(int));
            int res = compute(left, half)   compute(right, half);
            write(fd[1], &res, sizeof(int));
            exit(0);
            close(fd[1]);

        } else {
            close(fd[1]);
            wait(NULL);
            int res;
            read(fd[0], &res, sizeof(int));
            return res;
        }
    }

    else {
        return arr[0]   arr[1];
        exit(0);
    }
}

int main(int argc, char *argv[]) {
    pipe(fd);
    int arr[] = {1, 2, 4, 5, 2, 1, 5, 1};
    int res = compute(arr, 8);
    printf("%d\n", res);
    exit(EXIT_SUCCESS);
}

I'm trying to sum an array of ints using multiple processes.

Here is my code :

#define THRESHOLD 2

int compute(int *arr, int len) {
    if (len > THRESHOLD) {
        if (fork() == 0) {
            int half = (len / 2);
            int *left = malloc(half * sizeof(int));
            int *right = malloc(half * sizeof(int));
            memcpy(left, arr, half * sizeof(int));
            memcpy(right, arr   half, half * sizeof(int));
            return compute(left, half)   compute(right, half);

        } else {
            wait(NULL);
        }
    }

    else {
        return arr[0]   arr[1];
        exit(0);
    }
}

int main(int argc, char *argv[]) {
    int arr[] = {1, 2, 4, 5, 2, 1, 5, 1};
    int res = compute(arr, 8);
    printf("%d\n", res);
    exit(EXIT_SUCCESS);
}

This returns hasardous results, sometimes :

6231

12460

6228

sometimes :

6214

12426

6211

etc...

What is wrong with it ?

CodePudding user response：

There are multiple bugs in the shown code.

        if (fork() == 0) {

fork() creates a new process, not a new thread. Nothing that happens in the child process has any effect on the parent process.

The parent process does the following:

wait(NULL);

This waits for the child process to finish. Ok, the child process will finish. But whatever it does, the parent process has absolutely no knowledge of it. It's a completely different process. Whatever it did it's going to be a complete mystery to the parent process.

This is also the last statement in this function, and it's left without returning any value. This is undefined behavior, and is the primary reason for the garbage output.

There are also major problem in the child process's logic too:

int *left = malloc(half * sizeof(int));
int *right = malloc(half * sizeof(int));
memcpy(left, arr, half * sizeof(int));
memcpy(right, arr   half, half * sizeof(int));
return compute(left, half)   compute(right, half);

If len is odd this will miss one of the values in the array. Even if all other problems here get fixed the resulting sum will be wrong. Odd-sized arrays will have one of its values omitted from the total sum.

This also leaks memory. The malloced memory is never freed anywhere. Furthermore, none of this accomplishes anything useful, whatsoever. The same thing can be accomplished simply by doing appropriate pointer math on arr, and passing adjusted values of arr and len to the recursive calls, without wasting time, and memory, on mallocing and memcpying chunks of it. Nothing here actually requires malloc.

But fixing this will not fix the fundamental fact that the original parent process forks the child process, waits for it to finish, and then leaves compute() without returning anything. It doesn't really have anything to return, anyway, since everything is happening in a completely different child process.

If your intention was to use processes it will be necessary to implement some kind of a mechanism for each child process to transmit its computed sum to the parent process, in some form or fashion -- maybe a pipe, or perhaps a temporary file, or perhaps some other way. The process exit code's range is quite limited, and is completely unusable for this purpose.

If your intention was to really use threads instead of processes, all usage of fork() and wait() needs to be replaced with std::thread, and additional logic will have to be written in order to have all the execution threads communicate their results, their computed partial sums, to the parent execution thread.

Whether it's threads or processes the shown code has major parts of required functionality that are missing and need to be implemented. All of the above issues need to be fixed before the shown code will work correctly.