pthread 线程池实现快速排序并计时 c++

下面是使用pthread线程池实现快速排序并计时的C代码：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>

#define THREAD_NUM 8
#define ARRAY_SIZE 10000000

typedef struct {
    int *arr;
    int left;
    int right;
} quicksort_args_t;

typedef struct {
    quicksort_args_t *args;
    pthread_t thread;
} worker_t;

typedef struct {
    worker_t *workers;
    int worker_num;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    int task_count;
    int task_index;
    int done;
} thread_pool_t;

void init_thread_pool(thread_pool_t *pool, int worker_num);
void submit_task(thread_pool_t *pool, quicksort_args_t *args);
void join_thread_pool(thread_pool_t *pool);
void *worker(void *args);
void quicksort(int *arr, int left, int right);
int partition(int *arr, int left, int right);
void swap(int *a, int *b);
void print_array(int *arr, int size);
double get_time();

int main() {
    int *arr = (int *)malloc(ARRAY_SIZE * sizeof(int));
    for (int i = 0; i < ARRAY_SIZE; i++) {
        arr[i] = rand() % 1000000;
    }

    double start_time = get_time();

    thread_pool_t pool;
    init_thread_pool(&pool, THREAD_NUM);

    quicksort_args_t args = {
        .arr = arr,
        .left = 0,
        .right = ARRAY_SIZE - 1
    };

    submit_task(&pool, &args);
    join_thread_pool(&pool);

    double end_time = get_time();

    printf("Sorted array:\n");
    print_array(arr, ARRAY_SIZE);

    printf("Time elapsed: %f seconds\n", end_time - start_time);

    free(arr);

    return 0;
}

void init_thread_pool(thread_pool_t *pool, int worker_num) {
    pool->worker_num = worker_num;
    pool->workers = (worker_t *)malloc(worker_num * sizeof(worker_t));
    pool->task_count = 0;
    pool->task_index = 0;
    pool->done = 0;

    pthread_mutex_init(&pool->mutex, NULL);
    pthread_cond_init(&pool->cond, NULL);

    for (int i = 0; i < worker_num; i++) {
        pool->workers[i].args = NULL;
        pthread_create(&pool->workers[i].thread, NULL, worker, pool);
    }
}

void submit_task(thread_pool_t *pool, quicksort_args_t *args) {
    pthread_mutex_lock(&pool->mutex);
    pool->task_count++;
    pool->workers[pool->task_index].args = args;
    pool->task_index = (pool->task_index + 1) % pool->worker_num;
    pthread_cond_signal(&pool->cond);
    pthread_mutex_unlock(&pool->mutex);
}

void join_thread_pool(thread_pool_t *pool) {
    pthread_mutex_lock(&pool->mutex);
    while (pool->done == 0) {
        pthread_cond_wait(&pool->cond, &pool->mutex);
    }
    pthread_mutex_unlock(&pool->mutex);
}

void *worker(void *args) {
    thread_pool_t *pool = (thread_pool_t *)args;
    while (1) {
        pthread_mutex_lock(&pool->mutex);
        while (pool->task_count == 0 && pool->done == 0) {
            pthread_cond_wait(&pool->cond, &pool->mutex);
        }
        if (pool->done == 1) {
            pthread_mutex_unlock(&pool->mutex);
            break;
        }
        quicksort_args_t *task_args = pool->workers[pool->task_index].args;
        pool->task_index = (pool->task_index + 1) % pool->worker_num;
        pool->task_count--;
        pthread_mutex_unlock(&pool->mutex);

        quicksort(task_args->arr, task_args->left, task_args->right);

        free(task_args);

        if (pool->task_count == 0) {
            pthread_mutex_lock(&pool->mutex);
            if (pool->task_count == 0) {
                pool->done = 1;
                pthread_cond_signal(&pool->cond);
            }
            pthread_mutex_unlock(&pool->mutex);
        }
    }
    return NULL;
}

void quicksort(int *arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partition(arr, left, right);
    quicksort(arr, left, pivot - 1);
    quicksort(arr, pivot + 1, right);
}

int partition(int *arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void print_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

double get_time() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (double)tv.tv_sec + (double)tv.tv_usec / 1000000.0;
}

首先在`init_thread_pool`函数中初始化线程池，创建`worker_num`个线程，并将其保存在`pool->workers`数组中。每个线程将执行`worker`函数。

在`submit_task`函数中，我们将任务加入到线程池中。我们使用一个循环数组来记录每个线程的任务，每次调用`submit_task`时，我们将任务保存在下一个线程的任务数组中。`task_count`变量记录了任务数目，`task_index`变量记录了下一个将要保存任务的线程的索引。

在`join_thread_pool`函数中，我们等待所有线程完成任务。`done`变量表示线程池的所有任务是否已经完成。

`worker`函数是每个线程执行的函数。它使用`pthread_cond_wait`函数等待任务，直到线程池中有任务可以执行。然后它获取下一个任务，执行任务，并释放任务的内存。当线程池中没有任务时，它会等待一个信号，直到有新的任务进入线程池或者线程池的所有任务都已经完成。

`quicksort`和`partition`函数是快速排序的实现。`swap`函数用于交换数组中的两个元素。

`print_array`函数用于打印数组。

`get_time`函数用于获取当前时间，用于计算排序的时间。

我们可以在`main`函数中调用`init_thread_pool`函数初始化线程池，创建一个包含`ARRAY_SIZE`个元素的随机整数数组，并将其传递给`quicksort`函数。然后我们调用`submit_task`函数将任务提交到线程池中，并调用`join_thread_pool`函数等待线程池中的所有任务完成。最后我们打印排序后的数组，并计算排序所花费的时间。