Recursive C mergesort freezes when reading using pipe / forks

Question

I am trying to create a mergesort array of 800 ints using a recursive fork system so that each of the youngest children (8 in total) has qsort 100 each and then passes the array back to the appropriate parent processes to merge the sort and transfer again.

For some reason, the function freezes after the first set of the lower majority of children finishes writing to the parent process.

My recursive fork function that takes an initial array of 800 ...

static void forkSort(int* parentNums, int size) { printf("PPid:%ld Pid:%ld Size:%d\n", (long)getppid(), (long)getpid(), size); int childNums[size/2], fd[2], left, right; if(size <= 100) //Send sorted array to parent thru pipe { qsort(parentNums, size, sizeof(int), compare); write(fd[1], &parentNums, sizeof(parentNums)); exit(0); } if (pipe(fd)==-1){perror("Failed");} size /= 2; if(!(left = tryFork()) || !(right = tryFork())) //Children { if(left) copy(childNums, parentNums, size); else copy(childNums, parentNums + size, size); forkSort(childNums, size); } //Parents int first[size], second[size], combined[size*2]; read(fd[0], first, sizeof(first)); read(fd[0], second, sizeof(second)); mergeSort(first, second, combined, size); if(size*2 == SIZE) //Finished, write to out.dat printArray(combined, SIZE); else write(fd[0], combined, sizeof(combined)); } 

Answer 1

There is something wrong with your code (I must add that it was interesting to see).

A) you should exit (), and not just return to client code. Otherwise, you will continue to execute, especially when you do the recursion.

B) You need to pass the end of the recording to your clients so that they know where to write. I added this as a forkSort () parameter.

C) When the size is <= 100, you do sizeof(parentNums) , it turns into sizeof(int*) , the correct way: sizeof(int)*size .

D) When you write a combined set of ints, you write only the first part and write it to the read end of the channel. The correct call: write(write_fd, combined, sizeof(combined)); .

E) I deleted the wait (NULL) call since I did not see the point. Synchronization will be performed by calls to read() and write() .

Here is my suggestion:

 static void forkSort(int* parentNums, int size, int write_fd) { int fd[2]; printf("PPid:%ld Pid:%ld Size:%d\n", (long)getppid(), (long)getpid(), size); int childNums[size/2], left, right; if(size <= 100) //Send sorted array to parent thru pipe { qsort(parentNums, size, sizeof(int), compare); write(write_fd, parentNums, size*sizeof(int)); exit(0); } if (pipe(fd)==-1){perror("Failed");} printf("Creating child processes...\n"); size /= 2; if(!(left = tryFork()) || !(right = tryFork())) //Children { if(left) copy(childNums, parentNums, size); else copy(childNums, parentNums + size, size); forkSort(childNums, size, fd[1]); } /* parent */ int first[size], second[size], combined[size*2]; read(fd[0], first, sizeof(first)); read(fd[0], second, sizeof(second)); printf("\n\nMerge sorting... Size:%d\n", size*2); mergeSort(first, second, combined, size); if(size*2 == SIZE) { //Finished, write to out.dat printf("\nFinished!!! (%d)\n\n", size * 2); printArray(combined, SIZE); } else { write(write_fd, combined, sizeof(combined)); exit(0); } }