Итак, я новичок в общей памяти и функции ШМ в С.Реализация Bakery алгоритма в C для разветвленных процессов
У меня есть две программы; мастер и ведомый. В самом общем смысле: главная программа создает целое число sharedNum
в общей памяти и отбрасывает несколько процессов, выполняющих подчиненную программу. Затем подчиненные программные процессы должны увеличивать sharedNum
из общей памяти (возможно, несколько раз, даже) и печатать их в указанном файле. Я на 100% уверен, что все работает (хотя может показаться беспорядочным), кроме манипуляций с общей памятью. Я тестировал всю разработку.
Проблема, с которой я столкнулась, связана с условиями гонки в подчиненных программных процессах. Я понимаю, что мне нужно реализовать алгоритм Bakery, чтобы блокировать и разблокировать процессы от доступа к критическому разделу. Отсутствие этого приводит к отключению манипуляций sharedNum
.
Я попытался реализовать форму алгоритма пекарни в моей подчиненной программе, но, похоже, не работает ... Через тестирование я обнаружил, что переменные choosing
и turnNum
(которые мне НУЖНО использовать для алгоритм хлебобулочных изделий, насколько я понимаю) сами испытывают расовые условия. Как это можно избежать? Я уверен, что они тоже должны быть в общей памяти, иначе они не могут быть обновлены несколькими процессами ...
Заранее спасибо.
Сдача программы.
master.c:
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<sys/types.h>
#include<sys/wait.h>
#include<ctype.h>
#include<string.h>
#include<errno.h>
#include<signal.h>
#include<sys/ipc.h>
#include<sys/shm.h>
// global variables
pid_t *children;
int slave_max;
// globals relating to shared memory
key_t shmkey;
int shmid_sharedNum;
int *sharedNum;
void handle_sigalrm(int signum, siginfo_t *info, void *ptr)
{
// prevents multiple interrupts
signal(SIGINT, SIG_IGN);
fprintf(stderr, "Master ran out of time\n");
// detaching and deleting shared memory
shmdt(sharedNum);
shmctl(shmid_sharedNum, IPC_RMID, NULL);
// creating tmp_children to replace children
// this way children can be freed before SIGTERM
pid_t tmp_children[slave_max];
int i;
for (i = 0; i < slave_max; i++);
{
tmp_children[i] = children[i];
}
// freeing allocated memory
free(children);
// terminate child processes
for (i = 0; i < slave_max; i++)
{
kill(tmp_children[i], SIGTERM);
}
}
void handle_sigint(int signum, siginfo_t *info, void *ptr)
{
// prevents multiple interrupts
signal(SIGINT, SIG_IGN);
signal(SIGALRM, SIG_IGN);
fprintf(stderr, " interrupt was caught by master\n");
// detaching and deleting shared memory
shmdt(sharedNum);
shmctl(shmid_sharedNum, IPC_RMID, NULL);
// creating tmp_children to replace children
// this way children can be freed before SIGTERM
pid_t tmp_children[slave_max];
int i;
for (i = 0; i < slave_max; i++)
{
tmp_children[i] = children[i];
}
// freeing allocated memory
free(children);
// terminate child processes
for (i = 0; i < slave_max; i++)
{
kill(tmp_children[i], SIGTERM);
}
}
void catch_sigalrm()
{
static struct sigaction _sigact;
memset(&_sigact, 0, sizeof(_sigact));
_sigact.sa_sigaction = handle_sigalrm;
_sigact.sa_flags = SA_SIGINFO;
sigaction(SIGALRM, &_sigact, NULL);
}
void catch_sigint()
{
static struct sigaction _sigact;
memset(&_sigact, 0, sizeof(_sigact));
_sigact.sa_sigaction = handle_sigint;
_sigact.sa_flags = SA_SIGINFO;
sigaction(SIGINT, &_sigact, NULL);
}
int main(int argc, char *argv[])
{
// default variables
int i = 0; // to be used as a counter variable
slave_max = 5;
char slave_max_str[25]; // arbitrary size
char *log_filename = NULL;
int slave_increment = 3;
char slave_increment_str[25]; // arbitrary size
int master_time = 20;
// shared memory initialization
shmkey = ftok("./master", 118371); // arbitrary key
shmid_sharedNum = shmget(shmkey, sizeof(sharedNum), 0600 | IPC_CREAT);
sharedNum = (int *)shmat(shmid_sharedNum, NULL, 0);
sharedNum[0] = 0;
// handling command line args with getopt
int c;
while((c = getopt(argc, argv, "hs:l:i:t:")) != -1)
{
switch(c)
{
// -h : program help
case 'h':
// the following if-else block makes sure
// that -h will be used by itself
if (argc == 2)
{
printf("%s -h : program help\n", argv[0]);
printf("%s -s [integer] : set max number of slave processes\n", argv[0]);
printf("%s -l [filename] : set log filename\n", argv[0]);
printf("%s -i [integer] : set slave process incrementer\n", argv[0]);
printf("%s -t [integer] : set number of seconds master will terminate\n", argv[0]);
exit(0);
}
else
{
fprintf(stderr, "%s: option must be used by itself -- 'h'\n", argv[0]);
exit(1);
}
// -s [integer] : set max number of slave processes
case 's':
slave_max = atoi(optarg);
break;
// -l [filename] : set log filename
case 'l':
log_filename = optarg;
break;
// -i [integer] : set slave process incrementer
case 'i':
slave_increment = atoi(optarg);
break;
// -t [integer] : set number of seconds master will terminate
case 't':
master_time = atoi(optarg);
break;
// the following case takes care of user input errors
case '?':
if (optopt == 's')
fprintf(stderr, "Error: -s requires an integer\n");
else if (optopt == 'l')
fprintf(stderr, "Error: -l requires a filename\n");
else if (optopt == 'i')
fprintf(stderr, "Error: -i requires an integer\n");
else if (optopt == 't')
fprintf(stderr, "Error: -t requires an integer\n");
else if (isprint(optopt))
fprintf(stderr, "Error: input can't be printed\n");
else
fprintf(stderr, "Error: invalid syntax\n");
exit(1);
default:
abort();
}
}
catch_sigint();
catch_sigalrm();
alarm(master_time);
// if log_filename wasn't passed in by -l,
// its default value is set here...
if (!log_filename)
log_filename = "test.out";
// setting slave_increment_str and slave_max_str
// for use in future execl
snprintf(slave_increment_str, 25, "%i", slave_increment);
snprintf(slave_max_str, 25, "%i", slave_max);
// initializing pids
if ((children = (pid_t *)(malloc(slave_max * sizeof(pid_t)))) == NULL)
{
errno = ENOMEM;
perror("children malloc");
exit(1);
}
pid_t p;
// forking off child processes
for (i = 0; i < slave_max; i++)
{
p = fork();
if (p < 0)
{
fprintf(stderr,"Error: fork failed\n");
continue;
}
if (p == 0)
{
children[i] = p;
execl("./slave", "slave", "-l", log_filename, "-s", slave_max_str, "-i", slave_increment_str, (char *) NULL);
exit(0);
}
}
// waiting for all child processes to finish
for (i = 0; i < slave_max; i++)
{
int status;
waitpid(children[i], &status, 0);
}
// clean up and finish
free(children);
shmdt(sharedNum);
shmctl(shmid_sharedNum, IPC_RMID, NULL);
return 0;
}
slave.c:
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>
#include<ctype.h>
#include<sys/types.h>
#include<time.h>
#include<signal.h>
#include<sys/ipc.h>
#include<sys/shm.h>
// global variables
pid_t parent;
pid_t child;
int childProc;
// globals for shared memory
key_t shmkey;
int shmid_sharedNum, shmid_choosing, shmid_turnNum;
int *sharedNum; int *choosing; int *turnNum;
void handle_sigterm(int signum, siginfo_t *info, void *ptr)
{
// detaching and deleting shared memory
shmdt(sharedNum);
shmdt(choosing);
shmdt(turnNum);
shmctl(shmid_sharedNum, IPC_RMID, NULL);
shmctl(shmid_choosing, IPC_RMID, NULL);
shmctl(shmid_turnNum, IPC_RMID, NULL);
fprintf(stderr, "Process #%i was terminated by master\n", childProc);
exit(0);
}
void catch_sigterm()
{
static struct sigaction _sigact;
memset(&_sigact, 0, sizeof(_sigact));
_sigact.sa_sigaction = handle_sigterm;
_sigact.sa_flags = SA_SIGINFO;
sigaction(SIGTERM, &_sigact, NULL);
}
int main(int argc, char *argv[])
{
// default variables
parent = getppid();
child = getpid();
childProc = (int)(child - parent);
int i, j, maxCounter; // to be used as a counter variables
int slave_max = 1;
char *log_filename = NULL;
int slave_incrementer = 3;
srand(time(NULL));
int napTime;
// shared memory initialization
shmkey = ftok("./master", 118371); // arbitrary key
shmid_sharedNum = shmget(shmkey, sizeof(sharedNum), 0600 | IPC_CREAT);
sharedNum = (int *)shmat(shmid_sharedNum, NULL, 0);
shmid_choosing = shmget(shmkey, sizeof(choosing), 0600 | IPC_CREAT);
choosing = (int *)shmat(shmid_choosing, NULL, 0);
shmid_turnNum = shmget(shmkey, sizeof(turnNum), 0600 | IPC_CREAT);
turnNum = (int *)shmat(shmid_turnNum, NULL, 0);
catch_sigterm();
signal(SIGINT, SIG_IGN);
// implementing getopt to handle command line args
int c;
while((c = getopt(argc, argv, "s:l:i:")) != -1)
{
switch(c)
{
// -s [integer] : number of slave processes
case 's':
slave_max = atoi(optarg);
// -l [filename] : set log filename
case 'l':
log_filename = optarg;
break;
// -i [integer] : set slave process incrementer
case 'i':
slave_incrementer = atoi(optarg);
break;
// this case takes care of user input errors
case '?':
if (optopt == 's')
fprintf(stderr, "Error: -s requires an integer\n");
else if (optopt == 'l')
fprintf(stderr, "Error: -l requires a filename\n");
else if (optopt == 'i')
fprintf(stderr, "Error: -i requires an integer\n");
else if (isprint(optopt))
fprintf(stderr, "Error: input can't be printed\n");
else
fprintf(stderr, "Error: invalid syntax\n");
exit(1);
default:
abort();
}
}
// if log_filename wasn't passed in by -l,
// its default value is set here...
if (!log_filename)
log_filename = "test.out";
struct timespec now;
long curTime;
int max = 0;
for (i = 0; i < slave_incrementer; i++)
{
// execute code to enter critical section
choosing[(childProc-1)] = 1;
for (maxCounter = 0; maxCounter < slave_max; maxCounter++)
{
if((turnNum[maxCounter]) > max)
max = (turnNum[maxCounter]);
}
turnNum[(childProc-1)] = 1 + max;
printf("turnNum for process #%i = %i\n", childProc, turnNum[(childProc-1)]);
choosing[(childProc-1)] = 0;
for (j = 0; j < slave_max; j++)
{
while (choosing[j] == 1) {}
while ((turnNum[j] != 0) && (turnNum[j] < turnNum[(childProc-1)])) {}
}
// critical section
napTime = rand() % 3;
sleep(napTime);
sharedNum[0]++;
clock_gettime(CLOCK_REALTIME, &now);
curTime = ((((long)now.tv_sec) * 1000000000) + (long)now.tv_nsec);
// write message to log file here
// for testing purposes:
printf("File modified by process #%i (increment %i) at time %ld with sharedNum = %i\n", childProc, (i+1), curTime, sharedNum[0]);
napTime = rand() % 3;
sleep(napTime);
// exit from critical section
turnNum[(childProc-1)] = 0;
}
// clean up and finish
shmdt(sharedNum);
shmdt(choosing);
shmdt(turnNum);
shmctl(shmid_sharedNum, IPC_RMID, NULL);
shmctl(shmid_choosing, IPC_RMID, NULL);
shmctl(shmid_turnNum, IPC_RMID, NULL);
return 0;
}
(Сломанный) Хлебобулочные алгоритм раздел slave.c:
// execute code to enter critical section
choosing[(childProc-1)] = 1;
for (maxCounter = 0; maxCounter < slave_max; maxCounter++)
{
if((turnNum[maxCounter]) > max)
max = (turnNum[maxCounter]);
}
turnNum[(childProc-1)] = 1 + max;
printf("turnNum for process #%i = %i\n", childProc, turnNum[(childProc-1)]);
choosing[(childProc-1)] = 0;
for (j = 0; j < slave_max; j++)
{
while (choosing[j] == 1) {}
while ((turnNum[j] != 0) && (turnNum[j] < turnNum[(childProc-1)])) {}
}
// critical section
napTime = rand() % 3;
sleep(napTime);
sharedNum[0]++;
clock_gettime(CLOCK_REALTIME, &now);
curTime = ((((long)now.tv_sec) * 1000000000) + (long)now.tv_nsec);
// write message to log file here
// for testing purposes:
printf("File modified by process #%i (increment %i) at time %ld with sharedNum = %i\n", childProc, (i+1), curTime, sharedNum[0]);
napTime = rand() % 3;
sleep(napTime);
// exit from critical section
turnNum[(childProc-1)] = 0;
I оригинальные алгоритмы, это не имеет значения, если есть состояние гонки для '' choosing' и turnNum'; это идея этого алгоритма. Как вы понимаете, что это может быть вашей проблемой? – Matthias
@TonyTannous: Ваш намек вводит в заблуждение. 'fork()' создает новый процесс, а не новый поток. Таким образом, у него есть собственное адресное пространство, память копируется при первом доступе на запись, и у вас есть два экземпляра переменной. – Matthias
@Matthias: при тестировании я включил строку 'printf'' turnNum [(childProc-1)] ', и чаще всего было бы дубликатов для каждого процесса. Как и в случае, несколько процессов будут печатать одно и то же значение 'turnNum'. – Anthony