【Linux】线程同步—屏障（实现多线程排序算法）

迈不过友情╰ 2022-05-29 23:08 184阅读 0赞

屏障与互斥量、读写锁等不同，它不是用来保护临界区的，而是与条件变量类似，是一种线程之间的同步机制。屏障允许每个线程等待，直到所有合作线程都到达某一点，然后从该点继续执行。pthread\_join就是一种屏障，它允许线程等待直到另一个线程退出。

#include <pthread.h>
    pthread_barrier_t ; //屏障数据类型
    
    int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned int count);
                                //初始化屏障，attr指定屏障属性，NULL为默认属性 
                                //count指定在允许所有线程继续执行之前，必须到达屏障的线程数目
    
    int pthread_barrier_destroy(pthread_barrier_t *barrier);
                                //撤销屏障
                                    //返回值：成功，返回0 失败则返回错误编码

int pthread_barrier_wait(pthread_barrier_t *barrier);
                        返回值：若成功，返回0或PTHREAD_BARRIER_SERIAL_THREAD; 否则返回错误编号

调用pthread\_barrier\_wait的线程在屏障计数未满足条件（计数达到init中登记的数字）时，会进入休眠状态。如果该线程是最后一个调用pthread\_barrier\_wait的线程，就满足了计数条件，所有线程会被唤醒。第一个返回的线程会返回PTHREAD\_BARRIER\_SERIAL\_THREAD.可以用第一个返回的线程来进行后续的处理工作。  
一旦达到屏障计数，该屏障就可以被重用。不过计数值不会改变，除非先调用pthread\_barrier\_destroy撤销该屏障，之后在调用pthread\_barrier\_init重新初始化。

下面的程序使用屏障实现一个多线程的排序算法，对于随机生成的15个数分为3部分，使用3个线程分别对各部分进行堆排序。当各部分的排序都完成后（此处用屏障进行各线程的同步），在主线程中对三部分进行归并。对于一个多核处理器来说，这样的多线程排序算法显然优于单线程的算法。对于大量数据来说效率能有显著提高，这里设定总数15个的数据量是为了方便观察结果，只要修改程序中的宏定义即可修改数据总量和使用的线程数。

#include <stdio.h>
    #include <unistd.h>
    #include <stdlib.h>
    #include <pthread.h>
    
    #define NUMS 15
    #define TURN 3
    #define N (NUMS/TURN)
    
    pthread_barrier_t the_barrier;
    pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
    
    int nums[NUMS];
    
    void adjust(int i, int n, int turn)
    {
        int parent = i;
        int child;
        int temp = nums[i+turn*N];
    
        while(parent*2+1 <= n-1){
            child = parent*2+1;
            if(child != n-1 && nums[child+turn*N] < nums[child+turn*N+1])
                child++;
            if(temp >= nums[child+turn*N])
                break;
            nums[parent+turn*N] = nums[child+turn*N];
            parent = child;
        }
        nums[parent+turn*N] = temp;
    }
    
    void *heap_sort(void *args)
    {
        int turn = (int)args;
    
        for(int i = (N-2)/2; i >= 0; i--)
            adjust(i, N, turn);
    
        pthread_mutex_lock(&lock);
        printf("in thread%d before sort : ", turn);
        for(int i = 0; i < N; i++)
            printf("%d ", nums[i+turn*N]);
        printf("\n");
        pthread_mutex_unlock(&lock);
    
        for(int j = N-1; j > 0; j--){
            int t = nums[0+turn*N];
            nums[0+turn*N] = nums[j+turn*N];
            nums[j+turn*N] = t;
            adjust(0, j, turn);
        }
    
        pthread_mutex_lock(&lock);
        printf("in thread%d after  sort : ", turn);
        for(int i = 0; i < N; i++)
            printf("%d ", nums[i+turn*N]);
        printf("\n");
        pthread_mutex_unlock(&lock);
    
        pthread_barrier_wait(&the_barrier);
    
    }
    
    void merge(int start1, int start2, int end)
    {
        int *a = malloc((end-start1+1)*sizeof(int));
        int k = 0;
        int i = start1;
        int j = start2;
    
        while(i <= start2-1 && j <= end){
            if(nums[i] <= nums[j]){
                a[k] = nums[i];
                k++;
                i++;
            }else{
                a[k] = nums[j];
                k++;
                j++;
            }
        }
    
        while(i <= start2-1){
            a[k] = nums[i];
            k++;
            i++;
        }
        while(j <= end){
            a[k] = nums[j];
            k++;
            j++;
        }
    
        for(i = start1, k = 0; i <= end; i++, k++)
            nums[i] = a[k];
    
    }
    
    int main()
    {
        pthread_barrier_init(&the_barrier, NULL, TURN+1);
    
        srand(getpid());
        printf("before sort : ");
        for(int i = 0; i < NUMS; i++){
            nums[i] = rand()%100 +1; //生成1到100之间的随机数
            printf("%d ", nums[i]);
        }
        printf("\n");
    
        pthread_t tid[TURN];
        for(int i = 0; i < TURN; i++)
            pthread_create(&tid[i], NULL, heap_sort, (void*)i);
    
        pthread_barrier_wait(&the_barrier);
    
        int gap = NUMS/TURN;
        for( ; gap < NUMS; gap *= 2){
            int i;
            for(i = 0; i + gap*2 - 1 < NUMS; i += gap*2)
                merge(i, i + gap, i+ gap*2 -1);
            if(i + gap < NUMS)
                merge(i, i + gap, NUMS-1);
        }
    
        printf("after sort : ");
        for(int i = 0; i < NUMS; i++)
            printf("%d ", nums[i]);
        printf("\n");
    
        pthread_mutex_destroy(&lock);
        pthread_barrier_destroy(&the_barrier);
    }

输出结果

before sort : 13 30 53 53 47 91 37 54 10 76 89 68 37 20 23 
    in thread0 before sort : 53 47 53 30 13 
    in thread0 after  sort : 13 30 47 53 53 
    in thread2 before sort : 89 68 37 20 23 
    in thread2 after  sort : 20 23 37 68 89 
    in thread1 before sort : 91 76 54 10 37 
    in thread1 after  sort : 10 37 54 76 91 
    after sort : 10 13 20 23 30 37 37 47 53 53 54 68 76 89 91