c - 并行归并排序(使用fork)

Question

该函数对数组 v 中位于区间 [s,e] 的元素进行排序(v[s],v[s+1],..,v[e] 将被排序)。对于数组 3 2 它给出 2 3但对于具有超过 2 个元素的数组，如 3 2 4，它会返回未更改的数组。

void merge(int v[],int s, int e)
{
    if(e==s)    return; //if there is just one number
    int m=(s+e)/2;
    pid_t f1,f2;
    if((f1=fork())==0){merge(v,s,m);exit(0);} //sort the numbers from position s to position m
    if((f2=fork())==0){merge(v,m+1,e);exit(0);} //same for numbers from position m+1 to e
    waitpid(f1,NULL,0); //wait until the first half is sorted
    waitpid(f2,NULL,0); //same for the second half
    int *t=(int*)malloc((e-s+1)*sizeof(int)); //temporary array for merging the 2 halves
    int k=0,i=s,j=m+1;
    while((i<=m)&&(j<=e)) //while there are stil unprocessed numbers left in each half
        if(v[i]<v[j])   t[k++]=v[i++];
        else            t[k++]=v[j++];
    while(i<=m)         t[k++]=v[i++]; //copy the remaining numbers
    while(j<=e)         t[k++]=v[j++];
    while(k)            v[e--]=t[--k]; //copy them back in the original array
    free(t); //delete the temporary array
}

Answer 1

fork 后，两个进程不共享相同的数据，它们以相同的副本开始，但它们进行自己的更改，父进程看不到它们的更改

如果你想并行化，你必须要么

• 将数组放入共享内存
• 使用线程(它们共享公共(public)内存)
• 使用 IPC 机制将排序后的数据流式传输回来进行合并