用c语言编写并行快速排序程序

Question

我需要在c中使用pthreads编写并行快速排序。这是我目前所做的。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <pthread.h>
    #include <unistd.h>  // sleep()
    #include <stdio.h>
    #include <stdlib.h>  // EXIT_SUCCESS
    #include <string.h>  // strerror()
    #include <errno.h>
    #define SIZE_OF_DATASET 6
    void* quickSort( void* data);
    int partition( int* a, int, int);

    struct info {
        int start_index;
        int* data_set;
        int end_index;
    };

    int main(int argc, char **argv)
    {
        int a[] = { 7, 12, 1, -2,8,2};
        pthread_t thread_id;
        struct info *info = malloc(sizeof(struct info));
        info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
        info->data_set=a;
        info->start_index=0;
        info->end_index=SIZE_OF_DATASET-1;
        if (pthread_create(&thread_id, NULL, quickSort, info)) {
            fprintf(stderr, "No threads for you.n");
            return 1;
        }
        pthread_join(thread_id, NULL);
        printf("nnSorted array is:  ");
        int i;
          for(i = 0; i < SIZE_OF_DATASET; ++i)
               printf(" %d ", info->data_set[i]);
        return 0;
    }
    void* quickSort( void *data)
    {
        struct info *info = data;
        int j,l,r;
        l = info->start_index;
        r = info->end_index;
        pthread_attr_t attr;
        pthread_t thread_id1;
        pthread_t thread_id2;
        pthread_attr_init(&attr);
       if( l < r )
       {
           j = partition( info->data_set, l, r);
           info->start_index=l;
           info->end_index=j-1;
           if(info->end_index<0)info->end_index=0;
          if (pthread_create(&thread_id1, NULL, quickSort, info)) {
                fprintf(stderr, "No threads for you.n");
                return NULL;
          }
          info->start_index=j+1;
          info->end_index=r;
          if (pthread_create(&thread_id2, NULL, quickSort, info)) {
              fprintf(stderr, "No threads for you.n");
              return NULL;
          }
          pthread_join(thread_id1, NULL);
          pthread_join(thread_id2, NULL);
      }
    return NULL;
    }

    int partition( int* a, int l, int r) {
       int pivot, i, j, t;
       pivot = a[l];
       i = l; j = r+1;
       while( 1)
       {
        do ++i; while( a[i] <= pivot && i <= r );
        do --j; while( a[j] > pivot );
        if( i >= j ) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
       }
       t = a[l]; a[l] = a[j]; a[j] = t;
       return j;
    }

但是在快速排序函数中只调用第一个线程。我不明白这里发生了什么。

注:串行版本的代码已经过测试。没有问题

更新:

这是基于John Bollinger的解决方案的修改版本。但是，在快速排序中，新创建的线程所取的数组的后半部分仍然没有排序。

   int main(int argc, char **argv)
{
    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9,5,3,24,5,23,3,1,56,8,4,34,23,51};
    struct info *info = malloc(sizeof(struct info));
    info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
    info->data_set=a;
    info->start_index=0;
    info->end_index=SIZE_OF_DATASET-1;
    quickSort(info);
    printf("nnSorted array is:  ");
    int i;
      for(i = 0; i < SIZE_OF_DATASET; ++i)
           printf(" %d ", info->data_set[i]);
    return 0;
}
void* quickSort( void *data)
{
    struct info *info = data;
    struct info *info1 = data;
    int j,l,r;
    l = info->start_index;
    r = info->end_index;
    pthread_attr_t attr;
    pthread_t thread_id1;
    pthread_attr_init(&attr);
   if( l < r )
   {
       j = partition( info->data_set, l, r);
       info1->start_index=j+1;
       info1->end_index=r;
       info1->data_set = info->data_set;
       if(info1->end_index<0)info1->end_index=0;
      if (pthread_create(&thread_id1, NULL, quickSort, info1)) {
            fprintf(stderr, "No threads for you.n");
            return NULL;
      }
      info->start_index=l;
      info->end_index=j-1;
      if(info->end_index < 0) info->end_index = 0;
      quickSort(info);  /* don't care about the return value */
      pthread_join(thread_id1, NULL);
  }
return NULL;
}

Answer 1

程序是不正确的，因为您的线程都共享相同的struct info结构，该结构描述了它们应该处理的子问题。它们并发运行(或者可能并发)，并且在运行过程中修改结构，因此任何特定线程看到的值都是不确定的。

要解决这个问题，每个quickSort帧必须至少创建一个新的struct info，这样它在不同线程中的两个quickSort()调用每个都有它自己的。出于效率考虑，最好在每个quickSort()调用中只生成一个额外的线程。例如:

void* quickSort( void *data)
{
    struct info *info = data;
    struct info other_info;
    /* ... */
        /* launch a new thread to handle one partition: */
        other_info.start_index = j + 1;
        other_info.end_index = r;
        other_info.data_set = info->data_set;
        if (pthread_create(&thread_id1, NULL, quickSort, &other_info)) {
            fprintf(stderr, "No threads for you.n");
            return NULL;
        }
        /* handle the other partition in the current thread: */
        info->start_index = l;
        info->end_index = j - 1;
        if(info->end_index < 0) info->end_index = 0;
        quickSort(info);  /* don't care about the return value */
        /* after this thread is done, wait for the other thread to finish, too */
        pthread_join(thread_id1, NULL);
    /* ... */
}

请注意，这并不能确保任何特定的线程对并发运行，无论是在多核意义上还是在时间切片意义上。这取决于操作系统。当然，多核并行感只适用于操作系统愿意调度进程的主机上有多个内核可用的情况。