Why does my solution to The Cigarette Smoker's Problem not terminate?

Question

I wrote a solution to The Cigarette Smoker's Problem that does not terminate.

A full description of the problem and pseudo-code for the solution can be found here. Briefly, the task is to synchronize four processes using semaphores.

I used the pseudo-code as a guide for writing my solution. The following is my C implementation of the solution:

#include "sem.h"      //Allows the use of semget(), sem_create(), and the P() and V() functions.
#include <stdlib.h>   //Allows the use of srand() and rand().
#include <time.h>     //Allows the use of time().
#include <stdbool.h>  //Allows the use of the boolean variable that terminates smoker processes
#include <unistd.h>   //Allows the use of fork().
#include <sys/wait.h> //Allows the use of waitpid().

int main()
{

  /*Create and initialize semaphores*/
  int smkr_matches = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT); // Smoker that has matches
  int smkr_tobacco = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT); // Smoker that has tobacco
  int smkr_paper = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT);   // Smoker that has paper
  int agent = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT);
  int lock = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT); // The mutex variable

  /*According to http://www.cs.umd.edu/~hollings/cs412/s96/synch/smokers.html,
    all semaphores are initialized to zero except "lock", which is initialized to one.
  */
  sem_create(smkr_matches, 0);
  sem_create(smkr_tobacco, 0);
  sem_create(smkr_paper, 0);
  sem_create(agent, 0);
  sem_create(lock, 1);

  /*Seed the random number generator to generate random choice of ingredients.*/
  srand(time(NULL));

  // Delcare a boolean variable to terminate the smoker processes.
  bool done = false;

  //Declare variables to store PID after wait() calls and status.
  int pid = 0;
  int status = 0; 

  /*Declare variables to store PIDs.*/
  int smkr_mat_PID = 0;
  int smkr_tob_PID = 0;
  int smkr_pap_PID = 0;
  int agent_PID = 0;

  /*Implement the agent process*/
  agent_PID = fork();

  if (agent_PID == -1)
  { // Forking the agent process failed
    perror("Forking the agent process");
    exit(EXIT_FAILURE);
  }

  else if (agent_PID == 0)
  {
    printf("AGENT process created (PID = %d).\n", getpid());
    int rand_num = 0;
    for (int i = 0; i < 4; i++)
    { // Agent will place items on table ten times.
      P(lock);

      // Randomly choose a pair of ingredients.
      rand_num = (rand() % 3) + 1;

      // Place the ingredients on the table and wake the appropriate smoker.
      if (rand_num == 1)
      {
        printf("AGENT has placed TOBACCO and PAPER on the table.\n");
        printf("AGENT wakes smoker with MATCHES.\n");
        V(smkr_matches);
      }
      else if (rand_num == 2)
      {
        printf("AGENT has placed TOBACCO and MATCHES on the table.\n");
        printf("AGENT wakes smoker with PAPER.\n");
        V(smkr_paper);
      }
      else if (rand_num == 3)
      {
        printf("AGENT places MATCHES and PAPER on the table.\n");
        printf("AGENT wakes smoker with TOBACCO.\n");
        V(smkr_tobacco);
      }

      // Allow the smoker to work
      V(lock);

      printf("AGENT will now sleep.\n");
      P(agent);
    }

    done = true;
  }

  /*Implement the smoker with tobacco*/
  else
  {
    smkr_tob_PID = fork();

    if (smkr_tob_PID == -1)
    {
      perror("Forking smoker with tobacco");
      exit(EXIT_FAILURE);
    }

    else if (smkr_tob_PID == 0)
    {
      printf("SMOKER WITH TOBACCO created. (PID = %d)\n", getpid());
      while(done == false)
      {
        P(smkr_tobacco);
        P(lock);
        printf("SMOKER WITH TOBACCO picks up matches and paper from the table.\n");
        V(agent);
        V(lock);
        printf("SMOKER WITH TOBACCO begins smoking.\n");
      }
    }

    /*Implement the smoker with paper*/
    else
    {
      smkr_pap_PID = fork();

      if (smkr_pap_PID == -1)
      {
        perror("Forking smoker with paper");
        exit(EXIT_FAILURE);
      }

      else if (smkr_pap_PID == 0)
      {
        printf("SMOKER WITH PAPER created (PID = %d).\n", getpid());
        while(done == false)
        {
          P(smkr_paper);
          P(lock);
          printf("SMOKER WITH PAPER picks up tobacoo and matches from the table.\n");
          V(agent);
          V(lock);
          printf("SMOKER WITH PAPER begins smoking.\n");
        }
      }

      /*Implement the smoker with matches*/
      else
      {
        smkr_mat_PID = fork();

        if (smkr_mat_PID == -1)
        {
          perror("Forking smoker with matches");
          exit(EXIT_FAILURE);
        }

        else if (smkr_mat_PID == 0)
        {
          printf("SMOKER WITH MATCHES created (PID = %d).\n", getpid());
          while(done == false)
          {
            P(smkr_matches);
            P(lock);
            printf("SMOKER WITH MATCHES picks up tobacco and paper from the table.\n");
            V(agent);
            V(lock);
            printf("SMOKER WITH MATCHES begins smoking.\n");
          }
        }

        else
        {
          pid = wait(&status);
          printf("PID = %d terminated with status = %d\n.", pid, status);
          
          pid = wait(&status);
          printf("PID = %d terminated with status = %d\n.", pid, status);
          
          pid = wait(&status);
          printf("PID = %d terminated with status = %d\n.", pid, status);
          
          pid = wait(&status);
          printf("PID = %d terminated with status = %d\n.", pid, status);
        }
        exit(EXIT_SUCCESS);
      }
      exit(EXIT_SUCCESS);
    }
    exit(EXIT_SUCCESS);
  }
  exit(EXIT_SUCCESS);
}

I ran my solution through a debugger and noticed that the bug occurs when the second wait() call towards the end of the program is made. In executing that wait() call, it seems that my program runs forever. I suspected that an infinite loop was occurring in one of the smoker processes. After reviewing my code further, I noticed that, although the agent process seems to terminate normally in the first wait() call, the boolean variable done does not change its value to true as intended. This could explain why there seems to be an infinite loop.

In attempting to understand why the bug was happening, I tried several changes to the code, but all of them failed to correct the bug. The following is a list of what I tried and the rationale for trying it:

1. Changing the initial value of done from false to true.

My solution initializes done to false. I reasoned that, during execution, if one of the smoker processes started first, perhaps their while-loops would run forever. However, I realized the while-loops could not run forever because the P() operation would block the smoker process. Nevertheless, I changed the initial value of done to true to confirm my reasoning.

2. Having the agent process acquire the lock before assigning true to done.

As mentioned earlier, I noticed that the agent process terminated normally without changing the value of done to true. In an attempt to correct that, I changed the solution to have the agent acquire the lock one more time before changing the value of done and then releasing the lock again to allow the smoker processes to do work.

3. In the implementations of the smoker processes, releasing the lock before incrementing the agent semaphore.

In the while-loops of the smoker processes, after a smoker picks up the ingredients from the table, the agent semaphore is incremented before the lock is released. My instructor suggested that this order of operations could cause a deadlock and advised that I swap the order, releasing the lock first before incrementing the agent semaphore.

4. In the implementation of the agent process, releasing the lock before incrementing the semaphore of a smoker process.

Similar to what happens in the while-loop of the smoker processes, after the agent process randomly selects two ingredients and places them on the table, the agent increments the semaphore of the corresponding smoker process and then releases the lock. I wanted to see what would happen if I applied my instructor's suggestion to the agent process, so I changed the code so that the agent releases the lock before incrementing the semaphore of the smoker process.

---

The following additional information may be helpful in answering this problem:

• The sem.h header file included at the beginning of the code works fine. However, if you would like to see it, here it is:

/************************************************************************/
/*  Operating Systems - Fall
/*      Originally developed at KSU by a teaching assistant             */
/*                                  */
/*      Description :  The following library is a collection of         */
/*                     routines for using binary semaphores in C:       */
/*          1. seminit - to initialize a semaphore.         */
/*          2. P - to perform a P(S) (wait) operation.      */
/*          3. V - to perform a V(S) (signal) operation.    */
/*          4. semkill - to remove a semaphore              */
/*                                                          */
/*             These routines call system routines:     */
/*          1. semget - to get a semaphore          */
/*          2. semctl - semaphore control operations    */
/*          3. semop  - semaphore operations        */
/*                                  */
/*             Complete manual entries can be obtained by:      */
/*          man semctl | col -b | lpr           */
/************************************************************************/

#include <stdio.h>
#include <sys/types.h> 
#include <sys/ipc.h>
#include <sys/sem.h> 

union arg{          /* This structure is used to call semctl */
    int val;        
    struct semid_ds *buf;
    char *array;
};

/*
 * Create semaphore based on "key" parameter to "initval"
 */


void sem_create(int semid, int initval)
{
    int semval;
    union semun
    {
        int val;
        struct semid_ds *buf;
        unsigned short *array;
    }s;

    s.val=initval;
    if((semval=semctl(semid,0,SETVAL,s))<0)
    printf("\n Erroe in executing semctl");
}

/*
 * Remove semaphore with semaphore id (sid) from the kernel
 */
static void semkill(int sid)
{
    
    if (semctl(sid,0,IPC_RMID,0) == -1)
        perror("semctl (kill)");
    
    printf("Semaphore with value of sid = %d is killed \n",sid);
    

}

   
/*
 * Perform the designated "op" operation on the semaphore. If "op" is -1,
 * then this implements the "P" operation; it decrements the value of the
 * semaphore (semval) if it was >0, 
 * and blocks the caller if it was zero (semval==0)
 * If "op" is 1, then this is simply added to current value of 
 * the semaphore ("V" operation).
 */
static void semcall(int sid, int op)
{

    
    struct sembuf sb;

    sb.sem_num = 0; /* semaphore number within sid */
    sb.sem_op = op;
    sb.sem_flg = 0; /* blocking call */
    if (semop(sid, &sb, 1) == -1)
        perror("semop");
    
}

/*
 * P operation on semaphore "sid". Should be called upon entry to critical
 * region.
 */
static void P(int sid) {


    semcall(sid, -1);
      

}


/*
 * V operation on semaphore "sid". Should be called upon exit from critical
 * region.
 */
static void V(int sid) {
    
    semcall(sid, 1);
    
}

• I wrote my code in Microsoft Visual Studio using Ubuntu within a Virtual Box VM.

---

Finally, my question is: why does my solution not terminate?

Thank you for your time.