c - 在 C 中为 fork 进程实现 Bakery 算法

Question

所以，我不熟悉 C 中的共享内存和 shm 函数。

我有两个程序；主人和奴隶。在最一般的意义上:主程序在共享内存中创建一个 sharedNum 整数，并 fork 出多个执行从程序的进程。然后，从属程序进程必须从共享内存中递增 sharedNum(甚至可能多次)并将其打印到指定文件。除了共享内存操作之外，我有 100% 的信心一切正常(尽管它可能看起来很乱)。我一直在整个开发过程中进行测试。

我遇到的问题是从属程序进程中的竞争条件。我知道我需要实现 Bakery 算法，以便锁定和解锁进程访问临界区。缺少这个会导致 sharedNum 操作被关闭。

我试图在我的从属程序中实现一种 Bakery 算法，但它似乎不起作用......通过测试，我发现 choosing 和 turnNum 变量(据我所知，我需要将其用于 Bakery 算法)本身正在经历竞争条件。这怎么能避免呢？我很确定它们也需要在共享内存中，否则它们无法被多个进程更新...

提前致谢。

接下来是程序转储。

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

从属.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;

Answer 1

我刚才发现了这个，但忘了提供解决方案。事实证明，我对 Bakery 算法的实现没有问题。真正的问题来自于我如何在 slave.c 中初始化我的共享内存段。通过为每个段使用不同的 key ，我能够运行我的 master 程序并获得预期的结果。

更新了 slave.c 的“共享内存初始化”部分:

// shared memory initialization
shmkey = ftok("./master", 118371); // arbitrary key #1
shmid_sharedNum = shmget(shmkey, sizeof(sharedNum), 0600 | IPC_CREAT);
sharedNum = (int *)shmat(shmid_sharedNum, NULL, 0);
shmkey = ftok("./slave", 118372); // arbitrary key #2
shmid_choosing = shmget(shmkey, sizeof(choosing), 0600 | IPC_CREAT);
choosing = (int *)shmat(shmid_choosing, NULL, 0);
shmkey = ftok("./slave", 118373); // arbitrary key #3
shmid_turnNum = shmget(shmkey, sizeof(turnNum), 0600 | IPC_CREAT);
turnNum = (int *)shmat(shmid_turnNum, NULL, 0);