多线程编程

多线程编程

Linux提供的pthread库只允许向线程里传入一个参数，如果想传入多个参数，需要用结构体或者指针

功能介绍

该程序借助pthread线程库实现了多线程的快速排序，随机建立N个元素的int型数组，然后八线程地进行快速排序，然后对各线程的排序结果进行归并，并输出归并后的数组。
为检验实现的多线程快速排序的准确性，最后对原数组进行冒泡排序并输出排序后数组，两相对比可知。

code

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
//多线程分开进行快排，最后对各线程快排结果进行归并
//const int N = 1e3;
#define N 100
const int NR_CPU = 8;
// int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int arr[N];

typedef struct{
    int* n;
    int start, end;
}param_t;

void swap(int *x, int *y){
    int t = *x;
    *x = *y;
    *y = t;
}

void quick_sort_recursive(int arr[], int start, int end){
    if(start >= end){
        return;
    }
    int mid = arr[end];
    int left = start, right = end - 1;
    while(left < right){
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if(arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if(left){
        quick_sort_recursive(arr, start, left - 1);
    }
    quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len){
    quick_sort_recursive(arr, 0, len - 1);
}

void* runner(void *args){
    param_t *p = (param_t *)args;
    quick_sort_recursive(arr, p->start, p->end);
    int i = 0;
    // for(i = p->start; i <= p->end; ++i){
    //     printf("%d ", arr[i]);
    // }
    // printf("\n");
}

void merge(const int *n, int start, int mid, int end){
    int *p = malloc(sizeof(int) * (end - start));
    const int *p1 = n + start, *p2 = n + mid;
    int len1 = mid - start, len2 = end - mid;
    int idx = 0, i = 0, j = 0;
    while (i < len1 && j < len2){
        if (p1[i] < p2[j]) p[idx++] = p1[i++];
        else p[idx++] = p2[j++];
    }
    while (i < len1) p[idx++] = p1[i++];
    while (j < len2) p[idx++] = p2[j++];
    memcpy((void *)(n + start), (void *)p, sizeof(int) * idx);
}

int main(){
    srand(time(NULL));
    int i = 0;
    for (; i < N; ++i){
        arr[i] = random() % N;
    }
    // int N = (int) sizeof(arr) / sizeof(*arr);
    printf("%d\n",N);
    int step = N / NR_CPU;
    param_t params[NR_CPU];
    pthread_t pids[NR_CPU];
    // int i = 0;
    for (i = 0; i < NR_CPU; ++i){
        pids[i] = 0;
        params[i].n = arr;
        params[i].start = i * step;
        params[i].end = params[i].start + step-1;
    }
    params[NR_CPU - 1].end = N;
    for (i = 0; i < NR_CPU; i++){
        pthread_create(&pids[i], NULL, runner, &params[i]);
    }
    for (i = 0; i < NR_CPU; ++i){
        pthread_join(pids[i], NULL);
    }
    while (step < N){
        int start = 0;
        while (start < N){
            int mid = start + step;
            int end = mid + step;
            if (mid > N) mid = N;
            if (end > N) end = N;
            merge(arr, start, mid, end);
            start = end;
        }
        step *= 2;
    }
    for (i = 0; i < N; i++)
        printf("%d ", arr[i]);
            printf("\n");
    int j;
    for(i = 0; i < N; ++i){
        for(j = i; j < N; ++j){
            if(arr[i] > arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
        for (i = 0; i < N; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
} 

讨论

创建新线程时,利用pthread_create函数，该函数原型如下：
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);
其中，参数thread用于缓存新线程的pid， 参数attr是新线程的线程属性，可以事先设置也可以缺省，第三个参数是函数指针，是新线程的运行的函数，本程序中是runner，参数arg是向新线程中传入的参数。
可以看到，通过pthread_create函数只能向新线程传入1个参数，这时一般通过结构体来达到传入多个参数的目的。
为防止各进程未执行完毕main函数就执行到输出数组，在print之前应用pthread_join函数来等待线程结束。在本程序中，线程在执行完runner函数之后自动终止。
多线程编程似乎一般用于各线程之间功能相似的程序，最后在主线程里需要进行汇总或者归并。