concurrency-sort

psort 程序设计

项目文件结构

1
2
3
4
5
6
7
8
9
10
11
12
concurrency-sort/
├── Makefile # 构建文件
├── psort.md # 程序设计文档
├── README-zh.md # 项目说明
│
├── Record.h # 记录类型定义
├── psort_utils.h/.c # 内存文件映射 mfilemap
├── test_utils.h # 测试工具(随机文件生成、排序校验)
├── thread_pool.h/.c # 通用线程池
│
├── psort.h # 排序组 & 快速排序 & 线性归并
└── psort.c # 主程序 & 最小堆 k 路归并

可用例程

  • get_nprocs()
  • get_nprocs_conf()
  • mmap()
  • fsync()
  • read()
  • fread()

程序要求

  • 并行排序接收两个命令行参数
    • input
    • output
1
prompt> ./psort input output
  • 输入文件格式

    • record: key 4byte | value 96byte
  • 程序操作

    • 将所有记录读入内存,对记录进行排序,随后将其写入输出文件
    • 在完成之前,通过调用 fsync() 对输出文件进行强制写入
    • 可以假设为一次性排序

注意事项

  • 并行化排序
    • 在合适并行,在何时同步
    • 如何分配
    • 如何确定创建线程的数量
  • 高效执行每项工作
    • AlphaSort 论文
      • (2026/06/07) 该论文似乎已无法在服务器上找到,需要自行寻找
      • 找到了以下可用的PDF
        • AlphaSort: A Cache-Sensitive Parallel External Sort
  • 高效访问输入/输出文件
    • fread() C库调用
    • read() 原始系统调用
    • mmap() 内存映射

程序设计

数据结构设计

记录结构 Record(Record.h)

定义 Record 类型,以及相应的依赖类型与相应宏,提供类型安全保证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef uint32_t RecordKey;

#define RECORD_SIZE 100
#define RECORD_KEY_SIZE sizeof(RecordKey)
#define RECORD_VALUE_SIZE (RECORD_SIZE - RECORD_KEY_SIZE)

typedef union {
struct {
RecordKey key;
char value[RECORD_VALUE_SIZE];
} fields;
const char bytes[RECORD_SIZE];
} Record;

static inline
void set_Record_value(Record *record, const char *value) {
strncpy(record->fields.value, value, RECORD_VALUE_SIZE);
}

Record 使用 union 同时提供两种视图:

  • fields 视图:按结构化字段访问 key 和 value
  • bytes 视图:按原始字节数组访问整条记录(用于批量 I/O)

内存文件映射 mfilemap(psort_utils.h / psort_utils.c)

对 mmap 文件访问操作进行结构化封装,统一管理文件描述符、映射缓冲区和文件大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// memory file map
typedef struct {
int fd;
char *mbuf;
off_t size;
} mfilemap;

mfilemap mfilemap_read_open(const char *filename, int oflag,
int mmapprot, int mmapflag);

mfilemap mfilemap_write_open(const char *filename, size_t size, int oflag,
int mmapprot, int mmapflag);

void mfilemap_close(mfilemap file);

读打开流程:

1
2
3
4
5
6
7
8
9
mfilemap mfilemap_read_open(const char *filename, int oflag,
int mmapprot, int mmapflag) {
mfilemap file = { .fd = -1, .mbuf = MAP_FAILED, .size = 0 };
// 1. stat() 获取文件大小
// 2. open(O_RDONLY | oflag)
// 3. mmap(NULL, size, PROT_READ | mmapprot, mmapflag, fd, 0)
// 强制 PROT_READ 保证可读
return file;
}

写打开流程:

1
2
3
4
5
6
7
8
9
mfilemap mfilemap_write_open(const char *filename, size_t size, int oflag,
int mmapprot, int mmapflag) {
mfilemap file = { .fd = -1, .mbuf = MAP_FAILED, .size = 0 };
// 1. open(O_CREAT | O_RDWR | oflag, 0644)
// 2. ftruncate(fd, size) 预分配文件空间
// 3. mmap(NULL, size, PROT_WRITE | mmapprot, mmapflag, fd, 0)
// 强制 PROT_WRITE 保证可写
return file;
}

关闭流程:

1
2
3
4
void mfilemap_close(mfilemap file) {
// 1. munmap(mbuf, size) 解除内存映射
// 2. close(fd) 关闭文件描述符
}

线程池(thread_pool.h / thread_pool.c)

通用任务队列线程池,用于并行化排序任务

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 任务结点
typedef struct task_node_t {
void *(*task)(void *);
void *args;
struct task_node_t *next;
} task_node_t;

// 线程池类型
typedef struct {
pthread_mutex_t mutex; // 互斥量:保护内部字段
pthread_cond_t cond_taskq; // 条件变量:队列非空 / shutdown 时唤醒
pthread_t *threads; // 工作线程组
int num_threads; // 线程数量
int shutdown; // 关闭标识 0/1
task_node_t *head; // 任务队列队头
task_node_t *tail; // 任务队列队尾
} thread_pool_t;

接口:

函数 作用
thread_pool_create(num) 创建线程池,启动 num 个工作线程
thread_pool_add_task(fn, arg, pool) 将任务入队,唤醒一个等待线程
thread_pool_destroy(pool) 关闭线程池,等待所有线程完成,释放资源
thread_pool_join_all(pool) 等待所有工作线程结束

工作线程逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void *task_worker(void *arg) {
thread_pool_t *pool = (thread_pool_t *)arg;
while (1) {
pthread_mutex_lock(&pool->mutex);
// 等待:队列非空或池关闭
while (pool->head == NULL && !pool->shutdown)
pthread_cond_wait(&pool->cond_taskq, &pool->mutex);
// 池关闭且无任务,退出
if (pool->shutdown && pool->head == NULL) {
pthread_mutex_unlock(&pool->mutex);
break;
}
// 出队一个任务
task_node_t *task = thread_pool_pop_taskq(pool);
pthread_mutex_unlock(&pool->mutex);
// 执行任务
if (task != NULL) {
task->task(task->args);
}
free(task);
}
return NULL;
}

排序组与并行快速排序(psort.h)

将输入数据划分为多个排序组,各组内使用快速排序并行执行

sort_group 排序组

1
2
3
4
5
6
7
8
9
10
11
typedef struct {
Record **list; // 指向 Record 指针的数组(指针排序,避免数据拷贝)
int num_records; // 组内记录数
int iter; // 归并迭代器(标记当前已归并位置)
} sort_group;

void sort_group_init(sort_group *group, int num_records) {
group->list = (Record **)malloc(sizeof(Record *) * num_records);
group->iter = 0;
group->num_records = num_records;
}

设计要点:list 存储的是 Record 指针而非 Record 本身。排序时交换指针,不移动 100 字节的记录数据,避免大量内存拷贝。

group_qsort 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 分区函数:以第一个元素为 pivot,Hoare 变体
int group_qsort_partition(Record **list, int low, int high) {
Record *tmp = list[low];
RecordKey pivot = list[low]->fields.key;
while (low < high) {
while (low < high && list[high]->fields.key > pivot)
--high;
list[low] = list[high];
while (low < high && list[low]->fields.key < pivot)
++low;
list[high] = list[low];
}
list[low] = tmp;
return low;
}

// 递归快速排序
void group_qsort(Record **list, int low, int high) {
if (low < high) {
int pivot_idx = group_qsort_partition(list, low, high);
group_qsort(list, low, pivot_idx - 1);
group_qsort(list, pivot_idx + 1, high);
}
}

sort_group_get_next_record 线性归并(参考)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 每次遍历所有组的当前指针,取 key 最小的记录
// 复杂度:O(k * m),k = 组数,m = 总记录数
Record *sort_group_get_next_record(sort_group *groups, int num_groups) {
Record *min_record = NULL;
int min_idx = -1;
for (int i = 0; i < num_groups; ++i) {
if (groups[i].iter < groups[i].num_records) {
Record *cur = groups[i].list[groups[i].iter];
if (min_record == NULL || cur->fields.key < min_record->fields.key) {
min_record = cur;
min_idx = i;
}
}
}
if (min_idx >= 0) {
groups[min_idx].iter++;
}
return min_record;
}

注:此函数为项目历史版本中的归并方式,保留作为对比参考。实际主程序使用下方的最小堆归并。


最小堆 k 路归并(psort.c)

将归并复杂度从 O(k * m) 降至 O(m log k)

堆结点

1
2
3
4
typedef struct {
RecordKey key;
int group_idx; // 记录来自哪个排序组
} heap_node_t;

堆操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 下沉:维护堆性质
static void heap_sift_down(heap_node_t *heap, int size, int i) {
while (1) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left].key < heap[smallest].key)
smallest = left;
if (right < size && heap[right].key < heap[smallest].key)
smallest = right;
if (smallest == i) break;
// swap
heap_node_t tmp = heap[i];
heap[i] = heap[smallest];
heap[smallest] = tmp;
i = smallest;
}
}

// 上浮:插入新元素
static void heap_sift_up(heap_node_t *heap, int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[i].key >= heap[parent].key) break;
// swap
heap_node_t tmp = heap[i];
heap[i] = heap[parent];
heap[parent] = tmp;
i = parent;
}
}

static void heap_push(heap_node_t *heap, int *size,
RecordKey key, int group_idx) {
heap[*size].key = key;
heap[*size].group_idx = group_idx;
heap_sift_up(heap, *size);
(*size)++;
}

static heap_node_t heap_pop(heap_node_t *heap, int *size) {
heap_node_t top = heap[0];
(*size)--;
heap[0] = heap[*size];
heap_sift_down(heap, *size, 0);
return top;
}

归并流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 1. 建堆:每个非空排序组的首条记录入堆(O(k))
heap_node_t *heap = malloc(sizeof(heap_node_t) * threads);
int heap_size = 0;
for (int i = 0; i < threads; ++i) {
if (groups[i].num_records > 0) {
heap_push(heap, &heap_size, groups[i].list[0]->fields.key, i);
}
}

// 2. k 路归并:每次弹出最小记录,同组补入下一条(O(m log k))
Record *out_records = (Record *)output.mbuf;
int out_idx = 0;
while (heap_size > 0) {
heap_node_t min = heap_pop(heap, &heap_size);
sort_group *g = &groups[min.group_idx];
memcpy(&out_records[out_idx++], g->list[g->iter], RECORD_SIZE);
g->iter++;
if (g->iter < g->num_records) {
heap_push(heap, &heap_size,
g->list[g->iter]->fields.key, min.group_idx);
}
}
free(heap);

复杂度对比:

归并方式 每次取最小 总复杂度
线性扫描 O(k) O(k * m)
最小堆 O(log k) O(m log k)

测试工具(test_utils.h)

随机测试文件生成

1
2
3
// 创建随机的符合Record类型格式的文件内容
void create_random_Record_file(const char *filename, RecordKey base,
int nrecords, float multiply, unsigned int seed);

使用 Fisher-Yates 洗牌算法保证 key 唯一且随机分布,multiply 参数控制键空间大小(>1.0 保证不重复)。

1
2
3
4
5
6
7
8
// 写 Record 类型数据
static inline
size_t fwrite_Record(Record *record, FILE *stream) {
return fwrite(record->bytes, sizeof(char), RECORD_SIZE, stream);
}

// 随机字符串生成
void rand_str(char *dest, size_t length);

排序校验

1
2
3
4
5
void check_Record_file_sorted(const char *filename) {
// 1. mmap 打开输出文件
// 2. 逐条检查 key 是否非递减
// 3. 打印 sorted / not sorted 结果
}

主程序流程(psort.c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int main(int argc, char *argv[])
{
// 0. 参数校验
if (argc != 3) { /* error */ }
const char *finput = argv[1];
const char *foutput = argv[2];

// 1. 创建线程池(线程数 = CPU 核数)
int threads = get_nprocs();
thread_pool_t *thread_pool = thread_pool_create(threads);

// 2. mmap 映射输入文件
input = mfilemap_read_open(finput, 0, PROT_READ | PROT_NONE, MAP_PRIVATE);
int num_records = input.size / RECORD_SIZE;
int num_per_group = (num_records + threads) / threads;

// 3. 将记录均分到各组,建立 Record* 指针列表
sort_group *groups = malloc(sizeof(sort_group) * threads);
for (int i = 0; i < threads; ++i) {
int group_records = (i != threads - 1)
? num_per_group
: num_records - i * num_per_group;
sort_group_init(&groups[i], group_records);
Record *rbase = (Record *)input.mbuf + i * num_per_group;
for (int j = 0; j < groups[i].num_records; ++j) {
groups[i].list[j] = rbase + j;
}
}

// 4. 并行排序:各组提交到线程池,执行 group_qsort
for (int i = 0; i < threads; ++i) {
thread_pool_add_task(sort_worker, &groups[i], thread_pool);
}
thread_pool_destroy(thread_pool); // 等待所有排序线程完成

// 5. mmap 创建输出文件(预分配空间)
output = mfilemap_write_open(foutput, input.size, 0,
PROT_WRITE | PROT_NONE, MAP_SHARED);

// 6. 最小堆 k 路归并(O(m log k))
// a. 建堆:各组首条记录入堆
// b. 循环 pop 最小记录写入输出,同组补入下一条

// 7. 资源释放 & 刷盘
free(groups);
mfilemap_close(input);
fsync(output.fd);
mfilemap_close(output);

// 8. 校验输出文件是否有序
check_Record_file_sorted(foutput);
return 0;
}

// 排序工作线程入口
void* sort_worker(void *arg) {
sort_group *group = (sort_group *)arg;
group_qsort(group->list, 0, group->num_records - 1);
return NULL;
}

并行化设计要点:

  1. 数据划分:将 mmap 映射的输入文件按记录数均分为 threads 组,各组独立排序
  2. 指针排序:sort_group.list 存储 Record* 指针,排序时只交换指针不移动数据
  3. 并发排序:各组通过线程池并行执行 group_qsort,thread_pool_destroy 确保全部排序完成后才进入归并阶段
  4. 堆归并:归并使用最小堆,每组内部已经有序,每次从堆顶取全局最小记录写入输出文件
  5. 强制刷盘:fsync(output.fd) 确保输出文件写入磁盘后再关闭

Makefile 构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CC = gcc

INCDIR_AXC = -I.
LIBDIR_AXC = -L
LINK = -lpthread -lc -lm
DEPEND = $(INCDIR_AXC) $(LINK)

CMACRO = -D_POSIX_C_SOURCE=200812L
STDVER = -std=c11
CFLAGS = -g -Wall $(STDVER) $(CMACRO) -O

INCS = *.h
SRCS = *.c
TARGET = psort

$(TARGET): $(INCS) $(SRCS)
$(CC) $(CFLAGS) $(DEPEND) $^ -o $@

.PHONY: clean

clean:
rm $(TARGET)

所有 .h 和 .c 文件一并编译为单一可执行文件 psort,链接 pthread、libc、libm。

Record.h
psort.c
psort.h
psort_utils.c
psort_utils.h
test_utils.h