那些遇到过的问题

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

Cam*_*ilo 1 c fork shared-memory

我正在尝试在快速排序中使用子进程，以便左半部分在一个子进程中排序，右半部分在另一个子进程中排序。我在 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;
}
Run Code Online (Sandbox Code Playgroud)

数据管理.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;
}
Run Code Online (Sandbox Code Playgroud)

文件解析器.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;
}
Run Code Online (Sandbox Code Playgroud)

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

实际输出：数组用 0 填充，程序未完成执行

Cra*_*tey 5

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

总结如下：

  1. 在 fork/sort 函数中，是在主语句上方rpid = fork();完成的。如果为 false，则会创建僵尸进程。ifif
  2. 共享区域的大小太小。它只是元素的数量而不是 sizeof(int) * number_of_elements
  3. 数据被读入非共享区域。然后创建共享区域，并且指向实际[非共享]数据的指针丢失。没有将数据复制到共享区域中
  4. 在fork/sort函数中，对函数的调用partition是在第一次调用之后完成的，因此它被父级fork和子级都调用，因此它们发生冲突/竞争。
  5. 创建的进程太多，并且一些调用失败，fork因为没有更多的空闲进程槽。

(1)正如我上面提到的，如果该语句是错误的rpid = fork();，则需要if (low < high)阻止僵尸进程的创建if。下文第 (4) 节将详细介绍这一点。

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

这是不正确的：

size_t SHM_SIZE = theArray->length;
Run Code Online (Sandbox Code Playgroud)

它需要是：

size_t SHM_SIZE = sizeof(int) * theArray->length;
Run Code Online (Sandbox Code Playgroud)

(3)您正在通过调用theArray在非共享内存中创建getArray。

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

稍后，要获取共享区域，您可以执行以下操作：

theArray->shm_array = shmat(theArray->shmid, NULL, 0)
Run Code Online (Sandbox Code Playgroud)

返回的值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;
Run Code Online (Sandbox Code Playgroud)

当然，当您让程序运行时，最好将调用移至执行 [non-shared] forshm*的低级函数，这样您就可以消除额外的复制操作。mallocshm_array

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

int partitionIndex = partition(arr, low, high);
Run Code Online (Sandbox Code Playgroud)

您在 后执行此操作，因此fork父级和rpid子级都尝试执行分区操作，因此它们会发生冲突。

所以，quickSortFork需要从以下开始：

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

    rpid = fork();
Run Code Online (Sandbox Code Playgroud)

(5)您创建了太多进程，并且fork由于进程槽不可用，调用开始失败。

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

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

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

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

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

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

我添加了该想法的一个简单版本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;
}
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

1675 次

最近记录：

6 年，10 月 前
如何确定在C程序中执行的x86机器指令的数量？ 4
更多相关链接
相关归档
是否有技术原因使用>(<)代替!=在'for'循环中递增1？ 196
虚空的大小是多少？ 73
了解Linux内核中的container_of宏 71
从C中的浮点数中提取小数部分 45
ASCII字符串和字节序 39
符号etext,edata和end定义在哪里？ 17
如何在C或C++中以编程方式检测OSX上的IP地址更改 16
glibc/NPTL/Linux强健互斥体中的竞争条件？ 16
gcc的原子操作和代码生成 14
_Exit如何在C++程序中运行？ 12
难疑归档
如何在Python中安全地创建嵌套目录？ 3909
什么时候使用自我超过$？ 1948
检查变量是否是JavaScript中的字符串 1550
在JavaScript对象数组中按id查找对象 1435
vim"用sudo写"技巧如何工作？ 1347
如何在回调中访问正确的`this`？ 1309
如何从Git存储库中删除.DS_Store文件？ 1167
如何配置Visual Studio代码以始终在新选项卡中打开文件？ 1078
NP,NP-Complete和NP-Hard有什么区别？ 1064
功能编程是否取代了GoF设计模式？ 1028