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

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;
}

---

数据管理.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;
}

---

文件解析器.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

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

总结如下:

1. 在 fork/sort 函数中，rpid = fork();在 主线之上完成 if陈述。如果那个if为 false，则创建僵尸进程。
2. 共享区域太小。它只是元素的数量，不是 sizeof(int) * number_of_elements
3. 数据被读入非共享区域。然后共享区域被创建，指向实际[非共享]数据的指针丢失。共享区域中没有数据副本
4. 在 fork/sort 函数中，调用 partition函数在第一个 fork 之后 完成调用，所以它被 parent 和 child 双方调用，所以他们发生冲突/种族。
5. 创建的进程方式太多，其中一些 fork调用失败，因为没有更多的空闲进程槽。

---

(1) 正如我上面提到的 rpid = fork();需要去寻找 if (low < high)以防止在 if 时创建僵尸进程陈述是错误的。在第 (4) 节中有更多相关信息。

---

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

这是不正确的:

size_t SHM_SIZE = theArray->length;

它需要是:

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

---

(3) 您正在创建 theArray在 非共享 内存中来自对 getArray 的调用.

设置shm_array从调用 parseFileToArray .这仍然在非共享内存中。

稍后，要获得共享区域，您需要:

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

shm_array 的返回值现在在共享 内存中，但数据 仍在shm_array 的旧 值中[同样，在非共享内存中]。指向实际数据的指针将永远丢失。

要解决这个问题，您需要这样的东西:

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*调用执行 [非共享] malloc 的低级函数对于 shm_array , 所以你可以消除额外的复制操作。

---

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

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

您在 fork 之后执行此操作, 所以 父级和 rpid child 正在尝试进行分区操作，因此它们存在冲突。

所以，quickSortFork需要开始:

if (low < high) {
    int partitionIndex = partition(arr, low, high);

    rpid = fork();

---

(5) 您正在创建方式 太多进程和 fork由于进程槽不可用，调用开始失败。

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

对于少量数组元素，这可能无法观察到，但如果数组足够大(例如 100,000 个元素)，则会发生

---

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

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

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

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

我在 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;
}