c - 多线程排序应用程序

Question

我是多线程编程的新手，所以我想我可以从事一个项目来帮助我学习它。以下是该项目的详细信息:

在c中编写一个多线程排序程序，其工作方式如下:整数列表分为两个相等大小的较小列表。两个单独的线程(我们将其称为排序线程)使用您选择的排序算法对每个子列表进行排序。然后，通过第三个线程(一个合并线程)合并这两个子列表，该线程将两个子列表合并为一个排序列表。

//Sort a list of numbers using two separate threads
//by sorting half of each list separately then
//recombining the lists

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10
#define NUMBER_OF_THREADS 3

void *sorter(void *params);    /* thread that performs basic sorting algorithm */
void *merger(void *params);    /* thread that performs merging of results */

int list[SIZE] = {7,12,19,3,18,4,2,6,15,8};

int result[SIZE];

typedef struct
{
    int from_index;
    int to_index;
} parameters;

int main (int argc, const char * argv[])
{
    int i;

    pthread_t workers[NUMBER_OF_THREADS];

    /* establish the first sorting thread */
    parameters *data = (parameters *) malloc (sizeof(parameters));
    data->from_index = 0;
    data->to_index = (SIZE/2) - 1;
    pthread_create(&workers[0], 0, sorter, data);

    /* establish the second sorting thread */
    data = (parameters *) malloc (sizeof(parameters));
    data->from_index = (SIZE/2);
    data->to_index = SIZE - 1;
    pthread_create(&workers[1], 0, sorter, data);

    /* now wait for the 2 sorting threads to finish */
    for (i = 0; i < NUMBER_OF_THREADS - 1; i++)
        pthread_join(workers[i], NULL);

    /* establish the merge thread */
    data = (parameters *) malloc(sizeof(parameters));
    data->from_index = 0;
    data->to_index = (SIZE/2);
    pthread_create(&workers[2], 0, merger, data);

    /* wait for the merge thread to finish */
    pthread_join(workers[2], NULL);


    /* output the sorted array */

    return 0;
}

void *sorter(void *params)
{
    parameters* p = (parameters *)params;

    //SORT

    int begin = p->from_index;
    int end = p->to_index+1;

    int z;
    for(z = begin; z < end; z++){
        printf("The array recieved is: %d\n", list[z]);
    }

    printf("\n");

    int i,j,t,k;

    for(i=begin; i< end; i++)
    {
        for(j=begin; j< end-i-1; j++)
        {

            if(list[j] > list[j+1])
            {
                t = list[j];
                list[j] = list[j+1];
                list[j+1] = t;

            }
        }
    }

    for(k = begin; k< end; k++){
            printf("The sorted array: %d\n", list[k]);
    }

    int x;
    for(x=begin; x<end; x++)
    {
            list[x] = result[x];
    }

    printf("\n");

    pthread_exit(0);
}

void *merger(void *params)
{
    parameters* p = (parameters *)params;

   //MERGE
    int begin = p->from_index;
    int end = p->to_index+1;

    int i,j,t;

    printf("list[1]: %d",list[1]);
    printf("result[1]: %d",result[1]);

    for(i=begin; i< end; i++)
    {
        for(j=begin; j< end-i; j++)
        {

            if(result[j] > result[j+1])
            {
                t = result[j];
                result[j] = result[j+1];
                result[j+1] = t;

            }
        }
    }

    int d;
    for(d=0; d<SIZE; d++)
    {
        printf("The final resulting array is: %d\n", result[d]);
    }

    pthread_exit(0);
}

我不确定我在算法中做错了什么，因为它不起作用。它似乎没有 catch 新的排序数组。在这个问题上的任何帮助将不胜感激!再次感谢您的所有帮助!

Answer 1

您的方法不正确。您应该分割分区，然后递归或线程化到它们中，加入结果，然后合并。相信我，这个算法很容易搞砸。

在进行其他操作之前，请确保您的合并算法是可靠的。如果您的合并在单线程舞台上有问题，那么添加线程只会使情况变得更糟。在您的情况下，情况变得更糟，因为合并线程似乎正在与排序程序线程同时运行。

就是说，退后一步，考虑一下。 Mergesort是关于分而治之的。要进行合并排序，您应该执行以下操作:

建立最大线程数。相信我，您想要发生的最后一件事就是为每个分区旋转一个线程。如果您足够努力地进行数学运算，则1024个值的序列将具有1023个分区。这么多线程不是解决方案。建立一些界限。

建立您愿意为之旋转线程的最小分区大小。这与上面的第一项一样重要。就像您不想旋转1023个线程来对1024个插槽的序列进行排序一样，您也不想旋转线程来对具有两个项的序列进行排序。零 yield 和高成本。

具有可靠的合并算法。有许多有效的方法可以完成此操作，但是可以做一些简单的事情并在以后进行改进。现在，我们只是有兴趣让常规线程正确执行。总是有时间使用精美的合并算法来增强此功能(例如就地，相信我比听起来更难)。

具有以上想法是这样的:

合并排序算法将具有三个参数:起始指针，长度和线程深度。为了我们的目的，在使用最多2N-1个线程的情况下，线程深度将为N。 (稍后会详细介绍，但请相信我，这样可以更轻松地进行数学运算)。

如果线程深度达到零或序列长度低于最小阈值(我们设置)，请不要设置并运行新线程。只是再次递归到我们的功能。

否则，请分割分区。设置一个包含分区定义的结构(对我们来说这将是一个起点和长度以及线程深度为N/2)，使用该参数块启动一个线程，然后不要启动另一个线程。而是使用当前线程递归到“other”另一半的merge_sort_mt()中。

当前线程从其递归返回后，必须通过联接在另一个线程上等待。一旦完成，两个分区都将完成，并且可以使用您的琐碎合并算法来合并它们。

ew。好的。所以它在实际中看起来如何:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <pthread.h>


struct Params
{
    int *start;
    size_t len;
    int depth;
};

// only used for synchronizing stdout from overlap.
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;

// forward declare our thread proc
void *merge_sort_thread(void *pv);


// a simple merge algorithm. there are *several* more efficient ways
//  of doing this, but the purpose of this exercise is to establish
//  merge-threading, so we stick with simple for now.
void merge(int *start, int *mid, int *end)
{
    int *res = malloc((end - start)*sizeof(*res));
    int *lhs = start, *rhs = mid, *dst = res;

    while (lhs != mid && rhs != end)
        *dst++ = (*lhs < *rhs) ? *lhs++ : *rhs++;

    while (lhs != mid)
        *dst++ = *lhs++;

    // copy results
    memcpy(start, res, (rhs - start) * sizeof *res);
    free(res);
}

// our multi-threaded entry point.
void merge_sort_mt(int *start, size_t len, int depth)
{
    if (len < 2)
        return;

    if (depth <= 0 || len < 4)
    {
        merge_sort_mt(start, len/2, 0);
        merge_sort_mt(start+len/2, len-len/2, 0);
    }
    else
    {
        struct Params params = { start, len/2, depth/2 };
        pthread_t thrd;

        pthread_mutex_lock(&mtx);
        printf("Starting subthread...\n");
        pthread_mutex_unlock(&mtx);

        // create our thread
        pthread_create(&thrd, NULL, merge_sort_thread, &params);

        // recurse into our top-end parition
        merge_sort_mt(start+len/2, len-len/2, depth/2);

        // join on the launched thread
        pthread_join(thrd, NULL);

        pthread_mutex_lock(&mtx);
        printf("Finished subthread.\n");
        pthread_mutex_unlock(&mtx);
    }

    // merge the partitions.
    merge(start, start+len/2, start+len);
}

// our thread-proc that invokes merge_sort. this just passes the
//  given parameters off to our merge_sort algorithm
void *merge_sort_thread(void *pv)
{
    struct Params *params = pv;
    merge_sort_mt(params->start, params->len, params->depth);
    return pv;
}

// public-facing api
void merge_sort(int *start, size_t len)
{
    merge_sort_mt(start, len, 4); // 4 is a nice number, will use 7 threads.
}

int main()
{
    static const unsigned int N = 2048;
    int *data = malloc(N * sizeof(*data));
    unsigned int i;

    srand((unsigned)time(0));
    for (i=0; i<N; ++i)
    {
        data[i] = rand() % 1024;
        printf("%4d ", data[i]);
        if ((i+1)%8 == 0)
            printf("\n");
    }
    printf("\n");

    // invoke our multi-threaded merge-sort
    merge_sort(data, N);
    for (i=0; i<N; ++i)
    {
        printf("%4d ", data[i]);
        if ((i+1)%8 == 0)
            printf("\n");
    }
    printf("\n");

    free(data);

    return 0;

}

这样的输出看起来像这样:

 825  405  691  290  900  715  125  969 
 534  809  783  820  933  895  310  687 
 152   19  659  856   46  765  497  371 
 339  660  297  509  152  796  230  465 
 502  948  278  317  144  941  195  208 
 617  428  118  505  719  161   53  292 
 ....
 994  154  745  666  590  356  894  741 
 881  129  439  237   83  181   33  310 
 549  484   12  524  753  820  443  275 
  17  731  825  709  725  663  647  257 

Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
   0    0    1    1    1    2    3    3 
   5    5    5    5    6    6    7    7 
   7    7    7    8    8   10   10   11 
  11   11   12   12   12   13   14   14 
  15   15   15   15   16   17   17   17 
  17   18   18   19   19   19   20   21 
  21   21   22   22   23   24   24   24 
  25   25   25   26   26   28   28   29 
  29   29   30   30   30   30   30   31 
....
 994  995  996  998 1000 1001 1001 1003 
1003 1003 1003 1004 1004 1005 1007 1007 
1010 1010 1010 1010 1011 1012 1012 1012 
1012 1013 1013 1013 1015 1015 1016 1016 
1016 1017 1018 1019 1019 1019 1020 1020 
1020 1021 1021 1021 1021 1022 1023 1023 

其中最重要的部分是限制器，它使我们避免陷入线程狂(很容易意外地使用递归线程算法)，以及在将其内容与分区的另一半​​合并之前将线程连接起来(在我们的线程上排序，并且可能也做过同样的事情)。

这是一个有趣的练习，希望您能从中学到一些东西。祝你好运。

更新:集成qsort()

一个有趣的任务是使用 qsort()来执行此功能，以对较小的分区进行排序，或者一旦线程池达到耗尽状态。 qsort()是带给该聚会的一个很大的锤子，因此，您将需要将最小分区大小提高到适当的水平(在下面的示例中，我们使用256个元素)。

那么，将 qsort()集成到子分区而不是手动滚动合并排序需要什么呢？令人惊讶的是，数量不多。从 qsort()兼容比较器开始:

// comparator for qsort
int cmp_proc(const void *arg1, const void* arg2)
{
    const int *lhs = arg1;
    const int *rhs = arg2;
    return (*lhs < *rhs) ? -1 : (*rhs < *lhs ? 1 : 0);
}

真死了。现在，将mt-wrapper修改为如下所示:

// our multi-threaded entry point.
void merge_sort_mt(int *start, size_t len, int depth)
{
    if (len < 2)
        return;

    // invoke qsort on the partition. no need for merge
    if (depth <= 0 || len <= 256)
    {
        qsort(start, len, sizeof(*start), cmp_proc);
        return;
    }

    struct Params params = { start, len/2, depth/2 };
    pthread_t thrd;

    pthread_mutex_lock(&mtx);
    printf("Starting subthread...\n");
    pthread_mutex_unlock(&mtx);

    // create our thread
    pthread_create(&thrd, NULL, merge_sort_thread, &params);

    // recurse into our top-end parition
    merge_sort_mt(start+len/2, len-len/2, depth/2);

    // join on the launched thread
    pthread_join(thrd, NULL);

    pthread_mutex_lock(&mtx);
    printf("Finished subthread.\n");
    pthread_mutex_unlock(&mtx);

    // merge the paritions.
    merge(start, start+len/2, start+len);
}

而已。严重地。这就是全部。用原始程序进行简单的测试运行即可证明这一工作，如下所示:

 986  774   60  596  832  171  659  753 
 638  680  973  352  340  221  836  390 
 930   38  564  277  544  785  795  451 
  94  602  724  154  752  381  433  990 
 539  587  194  963  558  797  800  355 
 420  376  501  429  203  470  670  683 
....
 216  748  534  482  217  178  541  242 
 118  421  457  810   14  544  100  388 
 291   29  562  718  534  243  322  187 
 502  203  912  717 1018  749  742  430 
 172  831  341  331  914  866  931  368 

Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Starting subthread...
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
   0    0    1    1    1    1    3    3 
   3    4    5    5    6    6    6    6 
   7    7    8    9   10   10   10   10 
  11   12   12   12   13   13   14   14 
  14   15   15   15   16   17   17   19 
  19   20   20   21   21   21   22   22 
  23   23   23   24   24   24   25   26 
  26   26   26   27   28   28   28   28 
....
1000 1000 1000 1001 1001 1002 1003 1003 
1004 1004 1004 1005 1005 1005 1006 1007 
1008 1010 1010 1010 1010 1010 1011 1011 
1011 1012 1012 1012 1012 1013 1013 1013 
1015 1015 1015 1016 1016 1017 1017 1017 
1018 1018 1018 1019 1019 1021 1021 1022 

如您所见，结果是相似的。