Linux passive waiting for condition update

Question

I am attempting to create a code that simulates child care center. In this center one adult can care for up to three children. This condition has to be fulfilled all the time. Adults and children are processes generated randomly and amount of children and adults is set in program arguments. Child can enter only if there is enough adults inside and adult can leave only if there is enough other adults to care for the children. If not, passive waiting should be implemented, until the condition allows child/adult to leave/enter.

#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <signal.h>
#include <string.h>
#include <semaphore.h>
#include <sys/mman.h>
#include <sys/ipc.h>
#include <sys/shm.h>

 void load_init_values();
 void handler(int, int, char*);

 pid_t adults, children;
 int adult_max_t, child_max_t, adc, chc, amt, cmt, shm_a_id, shm_c_id;
 int *adults_inside, *children_inside;
 sem_t *adults_sem, *children_sem, *entry;


int main(int argc, char *argv[])
{

 srand(time(NULL));
 setbuf(stdout,NULL);

 adc=atoi(argv[1]);
 chc=atoi(argv[2]);
 adult_max_t=atoi(argv[3]);
 child_max_t=atoi(argv[4]);
 amt=atoi(argv[5]);
 cmt=atoi(argv[6]);

 int pid=0;

 load_init_values();
 adults = fork();

 if (adults == 0)
 {

   for(int i=0; i<=adc-1; i++)
   {
      int adult_t = (random() % (adult_max_t + 1));
      usleep(adult_t*1000);

       adults = fork();

       // Adult process is created here
       if(adults == 0)
       {
        handler(getpid(), amt, "adult");
       }
       else
       {
       }
   }
 }

 else
 {
   children = fork();

   if (children == 0)
   {

     for(int i=0; i<=chc-1; i++)
     {
       int child_t = (random() % (child_max_t + 1));
       usleep(child_t*1000);

       children = fork();

       // Child process is created here
       if(children == 0)
       {
        handler(getpid(), cmt, "child");
        break;
       }
       else
       {
       }
     }
   }

   else
   {
   }
 }
 return 0;
}

void handler(int pid,int maxtime, char* type)
{
 sem_wait(entry);

  printf("%s %i%s\n",type,pid," attempting to enter...");

  if(type == "child")
  {
    int child_leave_t = (random() % (maxtime + 1));

    if((*adults_inside) != 0)
    {

     if(((*children_inside)+1)/(*adults_inside) <= 3)
     {
       (*children_inside)++;
       printf("%s %i%s\n",type,pid," entered!");

       usleep(child_leave_t*1000);

       printf("%s %i%s\n",type,pid," left!");
       (*children_inside)--;
     }

     else
     {
        printf("%s %i%s\n",type,pid," can not enter. Waiting...");
     }

    }
    else
    {
        printf("%s %i%s\n",type,pid," can not enter. Waiting...");
    }
  }

  else if(type == "adult")
  {

    (*adults_inside)++;
    printf("%s %i%s\n",type,pid," entered.");

  }

 sem_post(entry);
}

void load_init_values()
{
 adults_sem = mmap(NULL, sizeof(sem_t), PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, 0, 0);
 children_sem = mmap(NULL, sizeof(sem_t), PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, 0, 0);
 entry = mmap(NULL, sizeof(sem_t), PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, 0, 0);
 shm_a_id = shmget(IPC_PRIVATE, sizeof(int), IPC_CREAT | IPC_EXCL | 0666);
 shm_c_id = shmget(IPC_PRIVATE, sizeof(int), IPC_CREAT | IPC_EXCL | 0666);
 adults_inside = (int *) shmat(shm_a_id, NULL, 0);
 children_inside = (int *) shmat(shm_c_id, NULL, 0);
 sem_init(adults_sem,1,1);
 sem_init(children_sem,1,1);
 sem_init(entry,1,1);
}

This code only simulates generating of processes. There is one shared semaphore entry that allows only one process at the time to request entering. Shared memory variables adults_inside and children_inside keep track of the inner state.

My problem is basically located in handler function. After condition disallowing child to enter is triggered, I can not figure out how to implement passive wait. I was thinking about using pause() system call and store the waiting processes in queue, but is seem quite inefficient. What approach should I choose?

Answer 1

You will need to implement this in terms of some form of IPC. You mentioned using Linux, but I will assume POSIX-with-unnamed-semaphores (i.e. not OS X) since you aren't yet using anything Linux-specific. Others have mentioned this could be simpler if you used threads. But maybe you have some reason for using multiple processes, so I'll just assume that.

As specified, the code does not appear to allow adults to exit, which makes things a bit simpler. You already know how many children are allowed at any point in time, as that is directly proportional to the number of adults present at any given point in time.

To figure out how to solve the problem, let's consider how such a thing might be handled in real life. We can imagine that there is some kind of "gatekeeper" at the daycare. This "gatekeeper" is represented in the code by the sum of the state: the semaphore and the shared memory variables representing the number of adults and children present at any point in time. When no children are allowed to enter, the gatekeeper blocks entry and the children must form a line. I assume that the intent is that children are allowed to enter in a first-come-first-serve basis; this means you'll need to have some kind of FIFO to represent the queue. When a child leaves, the gatekeeper must be able to notify the first child in line that they are eligible to enter.

So this code is missing two things:

1. Some kind of FIFO representing the ordering of children waiting to enter
2. Some kind of notification mechanism that a child can wait for a notification on, and that the gatekeeper can trigger to "wake up" the child.

Now, the question is what data we store in this queue and how we do the notification. There are several options, but I'll discuss the two most obvious.

Making the child wait could be as simple as having the gatekeeper place the child PID at the tail of the FIFO and sending that PID SIGSTOP using kill(2). This may happen several times. Once a child leaves, the gatekeeper dequeues from the head of the FIFO and sends the pid SIGCONT.

As currently architected, the "gatekeeper" in your program is more of an abstract concept. A clearer implementation might implement a gatekeeper as a management process.

But since no such process exists, we need to imagine something like the child sees a "please wait" sign at the door and waits. The process representing the child can make itself wait by placing itself at the tail of the FIFO, and using the raise(3) library function, and sending itself SIGSTOP. Then, when any child leaves, it reads from the front of the FIFO and sends that pid SIGCONT using kill(2).

This implementation is relatively straightforward and the only additional resources required are to somehow represent the queue in shared memory.

An alternative approach would be to give each child its own file descriptor(s). This could be either a pipe(2), or a bidirectional file descriptor like a PF_LOCAL socket(2). Leaving the file descriptors in blocking mode, when a child is not allowed to enter, it puts (maybe the write-side of, if a pipe) its file descriptor at the tail of the FIFO, and blocks read(2)ing one byte from the read-side (which would be the same fd if not a pipe).

When a child exits, it pulls the entry from the front of the FIFO and write(2)s one byte to the file descriptor there. This will wake the child process that is blocked in read(2), and it will continue on its merry way into the daycare.

As previously stated, condition variables have also been suggested. I usually avoid them; they are easy to misuse, and you're already serializing the entry process.

In both the signal and the file descriptor case, a ring buffer of integers suffices -- so that's all the state you need to store in the FIFO.

The FIFO requires some careful consideration. Since multiple processes will be reading and manipulating it, it must also be in shared memory. Whether the FIFO is implemented as a ring buffer or some other way, you'll probably want to define some limits on the length of your queue. If there are too many children in line, maybe arriving children just "go home." Also, you'll need to make sure you handle the case of an empty FIFO gracefully on entry/exit, and make sure that transitioning from 1 waiter to 0 works as intended. Since you're serializing entry / exit with a semaphore, this should be straightforward.

Answer 2

2 semaphores precisely model the actual problem

While it is tempting to combine stats into synchronization, the minimum you need to synchronize for this child care is really only:

• the number of vacancies for children are > 0 for a child to enter, otherwise they wait.
• exiting adults take their 3 vacancies atomically with respect to each other or wait. (One adult refusing to take more responsibility on the way out is not explicit in your model, but prevents an exit starvation similar to writer starvation in rwlock implementations.)

But they must be mapped precisely

When semaphores hit 0 they force a wait, so to model this with the 2 semaphores you began to setup, their usage needs to match a few more specifics:

 sem_init(adults_exiting_sem,1,1); /* Allow 1 adult to be decrementing */
 sem_init(children_spots_sem,1,0); /* Allow no child without an adult */

Then the handler code can rely on the correct model of the semaphores to force waiting:

void handler(int pid,int maxtime, char* type)
{
  int leave_t = (random() % (maxtime + 1));

  if(type == "child")
  {

    printf("%s %i%s\n",type,pid," attempting to enter...");
    sem_wait(children_spots_sem);

    printf("%s %i%s\n",type,pid," entered!");
    sleep(leave_t);

    sem_post(children_spots_sem);
  }
  else if(type == "adult")
  {
    /* probably an inline function */
    sem_post(children_spots_sem);
    sem_post(children_spots_sem);
    sem_post(children_spots_sem);

    printf("%s %i%s\n",type,pid," entered.");
    sleep(leave_t);
    printf("%s %i%s\n",type,pid," attempting to leave...");

    /* adult exit funnel */
    sem_wait(adults_exiting_sem);

    /* probably an inline function */
    sem_wait(children_spots_sem);
    sem_wait(children_spots_sem);
    sem_wait(children_spots_sem);

    sem_post(adults_exiting_sem);

  }
    printf("%s %i%s\n",type,pid," left!");
}

And there is always more to want

Naturally, you may want to further extend the model by:

1. use sem_timedwait to model parents giving up on dropping off their children.
2. reintroducing stats either with additional synchronization or just log for post analysis.