Есть несколько ошибок.Я смог [наконец-то] найти их все, и рабочая версия приведена ниже.
Вот краткое изложение:
- В функции fork / sort,
rpid = fork(); сделано выше основной if оператор.Если значение if равно false, создается процесс зомби. - Размер общей области слишком мал.Это только количество элементов, а не
sizeof(int) * number_of_elements - Данные считываются в общую область.Затем создается общая область, и указатель на фактические [не общие] данные теряется. нет копий данных в общую область
- В функции fork / sort вызов функции
partition выполняется после первого fork вызов, поэтому он вызывается и родителем и потомком, поэтому они конфликтуют / участвуют в гонке. - Есть способ слишком много создаваемых процессов и некоторые из
fork вызовы не выполняются, так как свободных слотов процесса больше нет.
(1) Как я уже упоминал выше, rpid = fork(); нужно идти после if (low < high) допредотвратить создание процесса зомби, если оператор if имеет значение false.Подробнее об этом ниже в разделе (4).
(2) Область вашей общей памяти слишком мала.Это вызывает segfault во время окончательной печати.
Это неверно:
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* в низкоуровневую функцию, которая выполняет [non-shared] malloc для shm_array, чтобы можно было исключить дополнительную операцию копирования.
(4) В своей процедуре форка вы звоните:
int partitionIndex = partition(arr, low, high);
Вы делаете это после fork, поэтому оба parent и 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;
}