多进程桶排序程序出现Segmentation Error问题求助

问题背景 #

需要实现多进程桶排序程序，对比不同进程数的执行时间：

1. makerand.c 可正常生成500万个随机数到random.txt；
2. bucketsort.c 运行时出现Segmentation Error(core dumped)，无法完成排序。

段错误核心原因 #

1. 栈内存溢出 #

main函数中声明的int arr[MAX_NUM]是栈上的局部数组，MAX_NUM=5000000，每个int占4字节，总大小约20MB，而Linux默认栈大小仅为8MB左右，直接导致栈溢出触发段错误。

2. 多进程内存隔离逻辑错误 #

fork()创建的子进程拥有独立的地址空间，子进程对arr的修改仅作用于自身副本，父进程无法获取排序后的结果，原程序的多进程设计逻辑完全无效。

3. 桶排序的潜在内存浪费（非直接段错误原因） #

桶排序中每个桶分配了n（当前chunk大小）的内存，实际每个桶的元素数量远小于该值，造成内存浪费。

解决方案 #

1. 改用堆内存存储数据 #

将栈上的数组改为malloc分配的堆内存，避免栈溢出。

2. 使用共享内存实现进程间数据共享 #

通过shmget、shmat等系统调用创建共享内存，让子进程直接修改共享内存中的数据，父进程可获取排序结果。

3. 优化桶排序的内存分配 #

每个桶初始分配小容量内存，满了再扩容，减少内存浪费。

修正后的bucketsort.c代码 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/shm.h>

#define MAX_NUM 5000000 // 최대 데이터 크기
#define BUCKET_SIZE 100 // 버킷 크기
#define FILENAME "random.txt"
#define OUTPUT_FILENAME "sorted.txt"
#define SHM_KEY 0x1234 // 共享内存键值

// 优化的桶排序：按需扩容桶内存 + 插入排序子桶
void bucketSort(int arr[], int n) {
    if (n == 0) return;

    int max_val = arr[0], min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) max_val = arr[i];
        if (arr[i] < min_val) min_val = arr[i];
    }

    int num_buckets = (max_val - min_val) / BUCKET_SIZE + 1;
    int** buckets = (int**)malloc(num_buckets * sizeof(int*));
    int* bucket_capacities = (int*)malloc(num_buckets * sizeof(int));
    int* bucket_sizes = (int*)calloc(num_buckets, sizeof(int));

    // 初始化每个桶的初始容量
    for (int i = 0; i < num_buckets; i++) {
        bucket_capacities[i] = 100;
        buckets[i] = (int*)malloc(bucket_capacities[i] * sizeof(int));
    }

    for (int i = 0; i < n; i++) {
        int bucket_idx = (arr[i] - min_val) / BUCKET_SIZE;
        // 桶满了就扩容
        if (bucket_sizes[bucket_idx] >= bucket_capacities[bucket_idx]) {
            bucket_capacities[bucket_idx] *= 2;
            buckets[bucket_idx] = (int*)realloc(buckets[bucket_idx], bucket_capacities[bucket_idx] * sizeof(int));
        }
        buckets[bucket_idx][bucket_sizes[bucket_idx]] = arr[i];
        bucket_sizes[bucket_idx]++;
    }

    // 对每个桶进行插入排序（小数据量高效）
    for (int i = 0; i < num_buckets; i++) {
        if (bucket_sizes[i] > 1) {
            for (int j = 1; j < bucket_sizes[i]; j++) {
                int temp = buckets[i][j];
                int k = j - 1;
                while (k >= 0 && buckets[i][k] > temp) {
                    buckets[i][k+1] = buckets[i][k];
                    k--;
                }
                buckets[i][k+1] = temp;
            }
        }
    }

    // 合并桶到原数组
    int index = 0;
    for (int i = 0; i < num_buckets; i++) {
        if (bucket_sizes[i] > 0) {
            memcpy(&arr[index], buckets[i], bucket_sizes[i] * sizeof(int));
            index += bucket_sizes[i];
        }
        free(buckets[i]);
    }
    free(buckets);
    free(bucket_capacities);
    free(bucket_sizes);
}

int main() {
    FILE* file = fopen(FILENAME, "r");
    if (file == NULL) {
        printf("파일을 열 수 없습니다.\n");
        return 1;
    }

    // 改用堆内存分配数组，避免栈溢出
    int* arr = (int*)malloc(MAX_NUM * sizeof(int));
    if (arr == NULL) {
        printf("메모리 할당 실패\n");
        fclose(file);
        return 1;
    }

    int num = 0; // 데이터의 개수
    while (fscanf(file, "%d", &arr[num]) != EOF && num < MAX_NUM) {
        num++;
    }
    fclose(file);

    // 创建共享内存
    int shmid = shmget(SHM_KEY, MAX_NUM * sizeof(int), IPC_CREAT | 0666);
    if (shmid < 0) {
        perror("shmget failed");
        free(arr);
        return 1;
    }

    // 将共享内存附加到当前进程地址空间
    int* shm_arr = (int*)shmat(shmid, NULL, 0);
    if (shm_arr == (int*)-1) {
        perror("shmat failed");
        shmctl(shmid, IPC_RMID, NULL);
        free(arr);
        return 1;
    }

    // 将读取的数据复制到共享内存
    memcpy(shm_arr, arr, num * sizeof(int));
    free(arr); // 不再需要原堆数组

    int num_processes_list[] = {1, 3, 5, 7, 10, 20, 40, 70}; // 프로세스 수 목록

    for (int i = 0; i < sizeof(num_processes_list) / sizeof(num_processes_list[0]); i++) {
        int num_processes = num_processes_list[i];

        // 각 프로세스에 할당할 데이터 크기
        int chunk_size = num / num_processes;
        int start = 0;

        clock_t start_time = clock();

        for (int j = 0; j < num_processes; j++) {
            int current_chunk = chunk_size;
            if (j == num_processes - 1) {
                // 마지막 프로세스는 나머지 데이터를 처리
                current_chunk = num - start;
            }

            pid_t child_pid = fork();

            if (child_pid == 0) {
                // 자식 프로세스操作共享内存中的chunk
                bucketSort(&shm_arr[start], current_chunk);
                shmdt(shm_arr); // 分离共享内存
                exit(0);
            } else if (child_pid < 0) {
                fprintf(stderr, "프로세스 생성 실패\n");
                shmdt(shm_arr);
                shmctl(shmid, IPC_RMID, NULL);
                return 1;
            }

            start += current_chunk;
        }

        // 모든 자식 프로세스가 종료될 때까지 대기
        int status;
        for (int j = 0; j < num_processes; j++) {
            wait(&status);
        }

        clock_t end_time = clock();
        double execution_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;

        printf("프로세스 수: %d, 실행 시간: %.6f 초\n", num_processes, execution_time);

        // 정렬된 데이터를 파일에 저장
        FILE* output_file = fopen(OUTPUT_FILENAME, "w");
        if (output_file == NULL) {
            printf("결과 파일을 생성할 수 없습니다.\n");
            shmdt(shm_arr);
            shmctl(shmid, IPC_RMID, NULL);
            return 1;
        }

        for (int j = 0; j < num; j++) {
            fprintf(output_file, "%d\n", shm_arr[j]);
        }
        fclose(output_file);
    }

    // 清理共享内存
    shmdt(shm_arr);
    shmctl(shmid, IPC_RMID, NULL);

    return 0;
}

补充说明 #

1. 编译时需链接共享内存相关库：gcc bucketsort.c -o bucketsort -lrt
2. 若程序异常终止，可通过ipcrm -M 0x1234手动删除残留的共享内存
3. 优化后的桶排序针对小数据量的子桶使用插入排序，比通用排序算法更高效

内容的提问来源于stack exchange，提问作者seokkyu