c - pthreads的多线程调用，排序时不同的结果

Question

在下文中，我尝试使用 pthread 对具有多个线程的数组进行排序。这个想法是拆分数组并给每个线程一个部分。shell_sort它是串行的，而在我的并行尝试中，我每个线程都调用它。

多线程版本与串行结果不匹配（我认为这是正确的），所以我认为我的并行解决方案存在问题，我想寻求帮助。

这main.c是我的并行尝试：

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

typedef struct {
    double *array;
    int size;
} data_s;

double *gen_rand(int size, double min, double max) {
    srand(time(0));
    double *array = malloc(size*sizeof(double));
    for(int i = 0; i < size; i++) {
        double v = min + rand() / (RAND_MAX/(max-min)); 
        array[i] = floor(v*10)/10;
    }
    return array;
}

void print(double *array, int size) {
    for(int i = 0; i < size; i++)
        printf("%.2f ", array[i]);
    printf("\n");
}

void swap(double *a, double *b) {
    double tmp = *a;
    *a = *b;
    *b = tmp;
}

void shell_sort(double *array, int size) {
    printf("ssort serial\n");
    int h = floor(size/2);
    while(h >= 1) {    
        for(int i = h; i < size; i++)
            for(int j = i; j >= h  && array[j] < array[j-h]; j-=h)
                swap(&array[j], &array[j-h]);
        h = floor(h/2);
    }
}

void *ssort_thread(void *arg) {
    printf("ssort parallel\n");
    data_s data = *(data_s*)arg;
    shell_sort(data.array, data.size);
    return 0;
}

void ssort_parallel(double *array, int size, int part) {
    int threads = size/part;
    pthread_t thread[threads];
    for (int i = 0; i < threads; i++) {
        print(array+i*part, part);
        pthread_create(&thread[i], NULL, 
            ssort_thread, &(data_s){array+i*part, part});
    }
    for (int i = 0; i < threads; i++) 
        pthread_join(thread[i], NULL);
}

int main(int argc, char **argv) {
    int array_size = 10;
    double *array = gen_rand(array_size, 0, 99);

    print(array, array_size);

    int threads = 2;
    int part = array_size/threads;
    ssort_parallel(array, array_size, part);

    print(array, array_size);
}

我通过修改ssort_parallel为：

void ssort_parallel(double *array, int size, int part) {
    int threads = size/part;
    pthread_t thread[threads];
    for (int i = 0; i < threads; i++) {
        print(array+i*part, part);
        shell_sort(array+i*part, part);
    }
}

只是想注意：预期结果不是完整的数组排序。相反，应该对左侧部分和右侧部分进行排序。

这就是我得到的并行：

$ ./main
38.60 11.10 22.00 57.00 31.50 89.10 36.00 79.50 3.80 18.10 
38.60 11.10 22.00 57.00 31.50 
89.10 36.00 79.50 3.80 18.10 
ssort parallel
ssort parallel
ssort serial
ssort serial
38.60 11.10 22.00 57.00 31.50 3.80 18.10 36.00 79.50 89.10

而我得到的串行：

$ ./main
39.10 42.10 98.20 42.40 30.90 88.50 9.40 54.30 9.30 35.40 
39.10 42.10 98.20 42.40 30.90 
ssort serial
88.50 9.40 54.30 9.30 35.40 
ssort serial
30.90 39.10 42.10 42.40 98.20 9.30 9.40 35.40 54.30 88.50 

我的感觉是大多数时候右侧是并行正确的。

标签： cmultithreadingsortingpthreadspthread-join