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()
程序要求
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
| 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 }; 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 }; return file; }
|
关闭流程:
1 2 3 4
| void mfilemap_close(mfilemap file) { }
|
线程池(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; pthread_t *threads; int num_threads; int shutdown; 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; 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
| 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
|
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; 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; 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
| 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); } }
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
| 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
| 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) { }
|
主程序流程(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[]) { if (argc != 3) { } const char *finput = argv[1]; const char *foutput = argv[2];
int threads = get_nprocs(); thread_pool_t *thread_pool = thread_pool_create(threads);
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;
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; } }
for (int i = 0; i < threads; ++i) { thread_pool_add_task(sort_worker, &groups[i], thread_pool); } thread_pool_destroy(thread_pool);
output = mfilemap_write_open(foutput, input.size, 0, PROT_WRITE | PROT_NONE, MAP_SHARED);
free(groups); mfilemap_close(input); fsync(output.fd); mfilemap_close(output);
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; }
|
并行化设计要点:
- 数据划分:将
mmap 映射的输入文件按记录数均分为 threads 组,各组独立排序
- 指针排序:
sort_group.list 存储 Record* 指针,排序时只交换指针不移动数据
- 并发排序:各组通过线程池并行执行
group_qsort,thread_pool_destroy 确保全部排序完成后才进入归并阶段
- 堆归并:归并使用最小堆,每组内部已经有序,每次从堆顶取全局最小记录写入输出文件
- 强制刷盘:
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