使用子进程的共享内存进行排序

Question

我正在尝试在我的快速排序中使用子进程，这样左半部分在一个子进程中排序，右半部分在另一个子进程中排序。我在 shmget 实现之前让它工作，但现在我相信我在某处破坏了数组，因为在打印数组后我的所有值都变成了零。抱歉，如果我在某个地方犯了一些愚蠢的错误，我正在尝试学习如何使用 fork 和 shmget，但运行遇到了一些麻烦。我正在尝试将文本文件作为命令行参数并给出一个分隔符，例如“;”我必须删除定界符并识别它们之间的数字，将它们放在一个数组中并使用子进程对它们进行排序。我的解析工作正常，快速排序工作正常，但现在我正在尝试实现共享内存，我运行遇到了一些问题。

谢谢

我看过几个不同的示例，但主要基于的示例是 geeksforgeeks 使用 fork 进行合并排序的示例。 https://www.geeksforgeeks.org/concurrent-merge-sort-in-shared-memory/

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "fileParser.h"
#include "dataManagement.h"

int main(int argc, char *argv[]){
    char *file = argv[1];
    char delimiter = argv[2][0];
    MyArray *theArray = getArray(file, delimiter);

    size_t SHM_SIZE = theArray->length;

    theArray->key = IPC_PRIVATE;


    if((theArray->shmid = shmget(theArray->key, SHM_SIZE, IPC_CREAT | 0666)) < 0){
        perror("shmget");
        _exit(-1);
    }

    if ((theArray->shm_array = shmat(theArray->shmid, NULL, 0)) == (int *) -1)
    {
        perror("shmat");
        _exit(1);
    }

    printArray(theArray, theArray->length);
    quickSortFork(theArray, 0, theArray->length-1);
    printArray(theArray, theArray->length);

    if (shmdt(theArray->shm_array) == -1)
    {
        perror("shmdt");
        _exit(1);
    }

    if (shmctl(theArray->shmid, IPC_RMID, NULL) == -1)
    {
        perror("shmctl");
        _exit(1);
    }

    return 0;
}

dataManagement.h

#include <unistd.h>
#include <sys/wait.h>
#include "fileParser.h"

int partition(MyArray *arr, int low, int high);
void quickSortFork(MyArray *arr, int low, int high);
void swap(MyArray *arr, int a, int b);


void printArray(MyArray *arr, int length) {
    for(int i = 0; i < length; i++){
        printf("%d  ", arr->shm_array[i]);
    }
    printf("\n");
}


void quickSortFork(MyArray *arr, int low, int high){
    pid_t lpid, rpid;
    rpid = fork();
    if(low < high){
        int partitionIndex = partition(arr,low, high);
        if(rpid < 0){
            perror("Right child not created.\n");
            exit(-1);
        } else if(rpid == 0 ){
            printf("I am the right child!\tMy process id: %d\n",getpid());
            quickSortFork(arr, partitionIndex + 1, high);
            exit(EXIT_SUCCESS);
        } else {
            lpid = fork();
            if(lpid < 0){
                perror("Left child not created.\n");
            } else if (lpid == 0) {
                quickSortFork(arr, low, partitionIndex - 1);
                printf("I am the left child!\tMy process id: %d\n", getpid());
                exit(EXIT_SUCCESS);
            }
        }

        int status;

        waitpid(rpid, &status, 0);
        waitpid(lpid, &status, 0);
    }
}


int partition(MyArray *arr, int low, int high){
    int i = low, j = high;
    int pivot = arr->shm_array[(low+high)/2];
    while(i < j){
        while(arr->shm_array[i] < pivot)
            i++;
        while(arr->shm_array[j] > pivot)
            j--;
        if(i < j){
            swap(arr,i,j);
        }
    }
    return i;
}


void swap(MyArray *arr, int a, int b){
    int temp = arr->shm_array[a];
    arr->shm_array[a] = arr->shm_array[b];
    arr->shm_array[b] = temp;
}

fileParser.h

int findFileLength(FILE *inFile, char delimiter);
int *parseFileToArray(FILE *inFile, char delimiter, int length);

typedef struct {
    int shmid;
    key_t key;
    int length;
    int *shm_array;
} MyArray;


MyArray *getArray(char *fileName, char delimiter){
    FILE *numberFile = fopen(fileName, "r"); // open for reading

    if (numberFile == NULL) // unable to open file
        return NULL;
    MyArray *array = malloc(sizeof(MyArray));
    array->length = findFileLength(numberFile, delimiter);
    array->shm_array = parseFileToArray(numberFile, delimiter,array->length);

    return array;

}


int findFileLength(FILE *inFile, char delimiter){
    char c;
    int length = 0;
    c = fgetc(inFile);
    while(c != EOF){
        if(c != delimiter && c != '\n'){
            length++;
            while((c = fgetc(inFile)) != EOF && c != '\n' && c != delimiter);

        } else {
            c = fgetc(inFile);
        }
    }
    rewind(inFile); // resets the file pointer to the start
    return length;
}


int *parseFileToArray(FILE *inFile, char delimiter, int length){
    int *parsedFile = malloc(sizeof(int) * length);
    char c;
    char *stringInt = malloc(sizeof(char) * 100); // string that is used to combine multiple characters and convert to an integer
    int stringIntP = 0, parsedArrayP = 0; // pointers for our arrays, the first is for the string that determines the integer, the second is for our resulting array
    c = fgetc(inFile);
    while(c != EOF){
        if(c != delimiter && c != '\n'){

            for(;c != '\n' && c != delimiter; (c = fgetc(inFile)) != EOF){
                stringInt[stringIntP++] = c;
            }
            stringIntP = 0;
            parsedFile[parsedArrayP++] = atoi(stringInt); // convert string number to integer value
            memset(stringInt, 0, 100);  // clear the string that builds the integer value from chars
        } else {
            c = fgetc(inFile);
        }
    }
    for(int i = 0; i < length; i++){
        printf("%d ", parsedFile[i]);
    }
    printf("\n");
    fclose(inFile); // close the file after using
    free(stringInt);
    return parsedFile;
}

预期输出：首先传入未排序的数组。然后数组排序。

实际输出：数组全为0，程序未执行完毕

Answer 1

一个紧迫的问题是在

void quickSortFork(MyArray *arr, int low, int high){
    pid_t lpid, rpid;
    rpid = fork();
    if(low < high){
        int partitionIndex = partition(arr,low, high);

父子双方开始划分同一个范围，明显踩到对方的脚趾

让parent做分区，然后才fork。

Answer 2

有几个错误。我能够 [终于] 找到它们，下面是一个工作版本。

总结如下：

在 fork/sort 函数中，rpid = fork(); 在主 if 语句之上 完成。如果 if 为假，则创建僵尸进程。

共享区域太小。只是元素个数，不是sizeof(int) * number_of_elements

数据被读入non-shared区域。然后创建共享区域并丢失指向实际 [non-shared] 数据的指针。有没有拷贝数据到共享区

在fork/sort函数中，对partition函数的调用是在第一次fork调用之后完成的，所以调用 parent 和 child，所以他们 conflict/race.

way 正在创建的进程太多，一些 fork 调用失败，因为没有更多的空闲进程槽。

(1) 正如我上面提到的，如果 if 陈述是错误的。下面第 (4) 节中有更多相关信息。

(2)你的共享内存区太小了。它会在最终打印期间导致段错误。

这是不正确的：

size_t SHM_SIZE = theArray->length;

需要是：

size_t SHM_SIZE = sizeof(int) * theArray->length;

(3) 您正在通过调用 [=28] 在 non-shared 内存中创建 theArray =].

它通过对 parseFileToArray 的调用设置 shm_array。 non-shared 记忆中仍然。

稍后，要获取共享区域，您可以：

theArray->shm_array = shmat(theArray->shmid, NULL, 0)

这个shm_array的返回值现在在共享内存中，但是数据还在[=92] =]shm_array 的旧 值 [同样，在 non-shared 内存中]。指向实际数据的指针永远丢失。

要解决此问题，您需要以下内容：

int *shm_array; if ((shm_array = shmat(theArray->shmid, NULL, 0)) == (int *) -1) { perror("shmat"); _exit(1); } int *oldptr = theArray->shm_array; for (int idx = 0; idx < theArray->length; ++idx) shm_array[idx] = oldptr[idx]; free(oldptr); theArray->shm_array = shm_array;

当然，当你让程序运行时，最好将 shm* 调用移动到执行 [non-shared] malloc 的低级函数中 shm_array,这样就可以去掉多余的复制操作了。

(4) 在您的 fork 例程中，您正在调用：

int partitionIndex = partition(arr, low, high);

你在fork之后这样做，所以parent和rpidchild 正在尝试进行分区操作，因此它们存在冲突。

所以，quickSortFork 需要从：
开始
if (low < high) { int partitionIndex = partition(arr, low, high); rpid = fork();

(5) 您正在创建方式太多进程，并且 fork 调用因进程不可用而开始失败插槽。

这可能就是程序挂起的原因。

对于少量数组元素，这可能无法观察到，但如果数组足够大（例如 100,000 个元素），就会发生这种情况

这是一个工作版本[带有一些额外的调试代码]。

为了解决最后的 fork 问题，我创建了一个 quickSortStd 不使用 fork 并改为调用它。

处理过多 fork 调用问题的一种方法是让 quickSortFork 跟踪递归深度并在深度足够高后调用 non-fork 版本。

作为一般规则，在一定数量后添加更多 processes/threads 会适得其反，因为在进程之间切换的开销掩盖了并行性的好处。这是一个调整选项。

我在 quickSortFork 中添加了该想法的一个简单版本，它似乎可行，因此请调整深度限制以满足您的需要。

#include <unistd.h> #include <sys/wait.h> #include <sys/ipc.h> #include <sys/shm.h> #include <stdio.h> #include <stdlib.h> #include <memory.h> typedef struct { int shmid; key_t key; int length; int *shm_array; } MyArray; int findFileLength(FILE * inFile, char delimiter); int *parseFileToArray(FILE * inFile, char delimiter, int length); int partition(MyArray * arr, int low, int high); void quickSortFork(MyArray * arr, int low, int high); void quickSortStd(MyArray * arr, int low, int high); void swap(MyArray * arr, int a, int b); void prtnice(const char *who,int *arr,int length) { int hang = 0; printf("%s: LENGTH %d\n",who,length); for (int i = 0; i < length; i++) { if (hang == 0) printf("%s/%8.8d:",who,i); printf(" %d", arr[i]); ++hang; if (hang == 10) { printf("\n"); hang = 0; } } printf("\n"); } MyArray * getArray(char *fileName, char delimiter) { FILE *numberFile = fopen(fileName, "r"); // open for reading if (numberFile == NULL) // unable to open file return NULL; MyArray *array = malloc(sizeof(MyArray)); array->length = findFileLength(numberFile, delimiter); array->shm_array = parseFileToArray(numberFile, delimiter, array->length); return array; } int findFileLength(FILE * inFile, char delimiter) { char c; int length = 0; c = fgetc(inFile); while (c != EOF) { if (c != delimiter && c != '\n') { length++; while ((c = fgetc(inFile)) != EOF && c != '\n' && c != delimiter); } else { c = fgetc(inFile); } } rewind(inFile); // resets the file pointer to the start return length; } int * parseFileToArray(FILE * inFile, char delimiter, int length) { int *parsedFile = malloc(sizeof(int) * length); char c; char *stringInt = malloc(sizeof(char) * 100); // string that is used to combine multiple characters and convert to an integer int stringIntP = 0, parsedArrayP = 0; // pointers for our arrays, the first is for the string that determines the integer, the second is for our resulting array c = fgetc(inFile); while (c != EOF) { if (c != delimiter && c != '\n') { for (; c != '\n' && c != delimiter; (c = fgetc(inFile)) != EOF) { stringInt[stringIntP++] = c; } stringIntP = 0; parsedFile[parsedArrayP++] = atoi(stringInt); // convert string number to integer value memset(stringInt, 0, 100); // clear the string that builds the integer value from chars } else { c = fgetc(inFile); } } prtnice("INP",parsedFile,length); fclose(inFile); // close the file after using free(stringInt); return parsedFile; } void printArray(const char *who,MyArray * arr, int length) { prtnice(who,arr->shm_array,length); } void quickSortFork(MyArray * arr, int low, int high) { pid_t lpid, rpid; static int depth = 0; if (depth++ > 5) { quickSortStd(arr,low,high); --depth; return; } printf("Fork: ENTER low=%d high=%d\n",low,high); if (low < high) { int partitionIndex = partition(arr, low, high); rpid = fork(); if (rpid < 0) { perror("Right child not created.\n"); exit(-1); } if (rpid == 0) { printf("I am the right child!\tMy process id: %d\n", getpid()); quickSortFork(arr, partitionIndex + 1, high); exit(EXIT_SUCCESS); } lpid = fork(); if (lpid < 0) { perror("Left child not created.\n"); exit(-1); } if (lpid == 0) { quickSortFork(arr, low, partitionIndex - 1); printf("I am the left child!\tMy process id: %d\n", getpid()); exit(EXIT_SUCCESS); } int status; printf("Fork: WAIT rpid=%d\n",rpid); waitpid(rpid, &status, 0); printf("Fork: WAIT lpid=%d\n",lpid); waitpid(lpid, &status, 0); } --depth; printf("Fork: EXIT low=%d high=%d\n",low,high); } void quickSortStd(MyArray * arr, int low, int high) { pid_t lpid, rpid; printf("Std: ENTER low=%d high=%d\n",low,high); if (low < high) { int partitionIndex = partition(arr, low, high); quickSortStd(arr, partitionIndex + 1, high); quickSortStd(arr, low, partitionIndex - 1); } printf("Std: EXIT low=%d high=%d\n",low,high); } int partition(MyArray * arr, int low, int high) { int i = low, j = high; int pivot = arr->shm_array[(low + high) / 2]; while (i < j) { while (arr->shm_array[i] < pivot) i++; while (arr->shm_array[j] > pivot) j--; if (i < j) { swap(arr, i, j); } } return i; } void swap(MyArray * arr, int a, int b) { int temp = arr->shm_array[a]; arr->shm_array[a] = arr->shm_array[b]; arr->shm_array[b] = temp; } int main(int argc, char *argv[]) { char *file = argv[1]; char delimiter = argv[2][0]; MyArray *theArray = getArray(file, delimiter); #if 0 size_t SHM_SIZE = theArray->length; #else size_t SHM_SIZE = sizeof(int) * theArray->length; #endif setlinebuf(stdout); theArray->key = IPC_PRIVATE; if ((theArray->shmid = shmget(theArray->key, SHM_SIZE, IPC_CREAT | 0666)) < 0) { perror("shmget"); _exit(-1); } printArray("BEF",theArray, theArray->length); int *shm_array; if ((shm_array = shmat(theArray->shmid, NULL, 0)) == (int *) -1) { perror("shmat"); _exit(1); } int *oldptr = theArray->shm_array; for (int idx = 0; idx < theArray->length; ++idx) shm_array[idx] = oldptr[idx]; free(oldptr); theArray->shm_array = shm_array; printArray("SHM",theArray, theArray->length); #if 1 quickSortFork(theArray, 0, theArray->length - 1); #else quickSortStd(theArray, 0, theArray->length - 1); #endif printArray("AFT",theArray, theArray->length); if (shmdt(theArray->shm_array) == -1) { perror("shmdt"); _exit(1); } if (shmctl(theArray->shmid, IPC_RMID, NULL) == -1) { perror("shmctl"); _exit(1); } return 0; }

使用子进程的共享内存进行排序

Sorting with shared memory with child processes

c

fork

shared-memory