Linux 多執行緒排序實作：pthread_barrier 同步機制與效能分析

對於計算密集型任務，合理運用多核心並行處理可大幅提升效能。本文實作多執行緒快速排序，結合 pthread_barrier 同步機制，並分析時間複雜度優勢。

核心思路：分段並行 + 歸併

1. 將陣列均分為 N 段（N = CPU 核心數）
2. 各段由獨立執行緒以 快速排序 並行處理
3. 所有執行緒完成後，主執行緒執行 歸併排序 合併結果

假設 4 核心，時間複雜度約 O(n + n/4 log(n/4))，理論上比單執行緒 O(n log n) 快近一倍（實測視資料分布而定）。

關鍵同步原語：pthread_barrier

作為「欄桿」，阻擋先到達的執行緒，直到所有參與執行緒皆呼叫 wait() 才同時放行，確保分段排序完成再進入歸併階段。

#include <pthread.h>
int pthread_barrier_init(pthread_barrier_t *restrict barrier,
                         const pthread_barrierattr_t *restrict attr,
                         unsigned count);
int pthread_barrier_wait(pthread_barrier_t *barrier);
int pthread_barrier_destroy(pthread_barrier_t *barrier);

• count：指定需等待的執行緒數（含主執行緒）
• attr：通常傳 NULL 使用預設屬性
• 流程：init 設定人數 → 各執行緒 wait() 到達 → 全到齊自動解除阻塞 → destroy 釋放資源

完整實作碼（節錄關鍵段）

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

#define NTHR 4
#define NUM 8000000L
#define TNUM (NUM/NTHR)

long nums[NUM];
pthread_barrier_t barrier;

void *thr_fn(void *arg) {
    long idx = (long)arg;
    qsort(&nums[idx * TNUM], TNUM, sizeof(long), cmp);
    pthread_barrier_wait(&barrier);  // 同步點
    return NULL;
}

int main() {
    // 初始化資料、建立執行緒、barrier_init(NTHR+1)
    // pthread_create NTHR 個執行緒跑 thr_fn
    // 主執行緒也 pthread_barrier_wait 等待
    // 全部歸位後，主執行緒執行歸併合併
    // 輸出耗時統計
}

單執行緒基準測試對照

同樣資料量下，單執行緒 qsort 耗時約 2.3 秒；四執行緒並行 + 歸併約 1.2 秒，效能提升明顯。注意：pthread_barrier 為 POSIX 選擇性功能，編譯需連結 -lpthread，部分舊版 libc 需確認支援度。

掌握 pthread_barrier，不只能用於排序，任何「分階段並行、階段間需同步」的計算模型（如 MapReduce 風格、影像處理管線）皆適用，是多核心程式設計必備工具。