Passive Linux is waiting for state updates

Question

I am trying to create a code that mimics a child care center. In this center, one adult can take care of three children. This condition must be met all the time. Adults and children are randomly generated processes, and the number of children and adults is set in the arguments of the program. A child can only enter if there are enough adults in it, and an adult can leave only if there are enough other adults to take care of the children. If not, passive waiting should be realized until the condition allows the child / adults to exit / 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 the process of generating processes. There is one common entry semaphore that allows only one process to request input. The adults_inside memory variables adults_inside and children_inside monitor the internal state.

My problem is mainly in the handler function. After the condition that prohibits the introduction of a child element is launched, I cannot understand how to implement passive waiting. I was thinking about using the pause() system call and storing pending processes in a queue, but it seems pretty inefficient. Which approach to choose?

Answer 1

You will need to implement this in terms of some form of IPC. You mentioned using Linux, but I assume POSIX with unwritten semaphores (i.e. not with OS X), since you are not using anything specific for Linux yet. Others mentioned that it could be easier if you used streams. But maybe you have a reason to use multiple processes, so I just assume that.

As stated, the code does not allow adults to exit, which makes things a little easier. You already know how many children are allowed at any given time, since this is directly proportional to the number of adults present at a given time.

To find out how to solve the problem, let's look at how such a thing can be handled in real life. We can imagine that there is some kind of “gatekeeper” in the day hospital. This gatekeeper is represented in the code by the sum of the state: a semaphore and shared memory variables representing the number of adults and children present at any given time. When children are not allowed to enter children, the gatekeeper blocks the entry, and the children must form a line. I suppose the intention is for the children to be allowed to enter the first intake system; this means you need to have some kind of FIFO to represent the queue. When the child leaves, the gatekeeper should be able to notify the first child in a line that they can enter.

So this code skips two things:

• Some kind of FIFO representing the ordering of children awaiting entry
• Some kind of notification mechanism that the child can wait for the notification, and that the gatekeeper can cause the child to “wake up”.

Now the question is what data is stored in this queue and how we make a notification. There are several options, but I will discuss the two most obvious.

Waiting for a child can be as simple as having a gatekeeper put the child PID in the FIFO tail and send that PID SIGSTOP with kill(2) . This can happen several times. As soon as the child leaves, the gatekeeper is unloaded from the FIFO head and sends a pid SIGCONT .

As is currently the case in architecture, the gatekeeper in your program is more of an abstract concept. A clearer implementation may implement the gatekeeper as a management process.

But since such a process does not exist, we need to imagine something like a child who sees the “wait” sign, after waiting for the door, and waits. A process representing a child can keep itself waiting by putting itself in the tail of the FIFO and using the raise(3) library function and sending itself to SIGSTOP . Then, when any child leaves, he reads FIFO from the front and sends this pid SIGCONT with kill(2) .

This implementation is relatively simple, and the only additional resources needed to somehow represent the queue in shared memory.

An alternative approach would be to give each child their own file descriptor (s). This can be either pipe(2) or a bidirectional file descriptor of type PF_LOCAL socket(2) . Leaving the file descriptors in lock mode when the child is not allowed to enter, he puts (possibly the write side, if the channel) his file descriptor in the FIFO tail, and blocks read(2) one byte from the read side (which will be the same fd, if not a channel).

When the child exits, he pulls the record from the FIFO front and write(2) one byte into the file descriptor. This will start the child process, which is blocked in read(2) , and it will continue its fun way to kindergarten.

As stated earlier, condition variables have also been proposed. I usually avoid them; they are easy to use and you are already serializing the input process.

Both the signal and the file descriptor file have enough ring buffer of integers - so all the state that you need to save in FIFO.

FIFO requires special attention. Since several processes will read and manipulate it, it must also be in shared memory. Regardless of whether FIFO is implemented as a ring buffer or in any other way, you probably want to define some restrictions on the length of the queue. If there are too many children in the house, perhaps the children who come just “go home”. In addition, you need to make sure that you handle random FIFOs correctly when entering / exiting and make sure that the transition from 1 waiter to 0 works as intended. Since you serialize I / O using a semaphore, this should be simple.

Answer 2

2 semaphores accurately simulate the actual problem

While the temptation is to combine statistics with synchronization, the minimum level of synchronization for this child care is only:

• the number of vacancies for children > 0 to enter the child, otherwise they are waiting .
• Exiting adults takes 3 vacancies atomically relative to each other or wait . (One adult who refuses to take more responsibility for exiting is not explicit in your model, but prevents an exit hunger similar to a writer starving in rwlock implementations.)

But they must be accurately displayed.

When semaphores fall into 0 , they are forced to wait , so to simulate this using the two semaphores that you started setting up, their use should correspond to several more features:

  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 semaphore model to make it wait:

 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 a desire to want

Naturally, you can continue to expand the model:

• use sem_timedwait to model parents by abandoning their children.
• re-enter statistics either with additional synchronization, or simply register a post-analysis.