c - 用c编写并行快速排序

Question

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

    #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("\n\nSorted 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("\n\nSorted 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);

    /* ... */
}

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