4 Process 4 way synchronization using semaphores (In a C Programming, UNIX environment)

Question

I have a question about synchronizing 4 processes in a UNIX environment. It is very important that no process runs their main functionality without first waiting for the others to "be on the same page", so to speak.

Specifically, they should all not go into their loops without first synchronizing with each other. How do I synchronize 4 processes in a 4 way situation, so that none of them get into their first while loop without first waiting for the others? Note that this is mainly a logic problem, not a coding problem.

To keep things consistent between environments let's just say we have a pseudocode semaphore library with the operations semaphore_create(int systemID), semaphore_open(int semaID), semaphore_wait(int semaID), and semaphore_signal(int semaID).

Here is my attempt and subsequent thoughts:

Process1.c:

int main() {
    //Synchronization area (relevant stuff):
    int sem1 = semaphore_create(123456); //123456 is an arbitrary ID for the semaphore.
    int sem2 = semaphore_create(78901); //78901 is an arbitrary ID for the semaphore.
    semaphore_signal(sem1);
    semaphore_wait(sem2);

    while(true)  {
        //...do main functionality of process, etc (not really relevant)...
    }
}

Process2.c:

int main() {
    //Synchronization area (relevant stuff):
    int sem1 = semaphore_open(123456); 
    int sem2 = semaphore_open(78901); 
    semaphore_signal(sem1);
    semaphore_wait(sem2);

    while(true)  {
        //...do main functionality of process etc...
    }
}

Process3.c:

int main() {
    //Synchronization area (relevant stuff):
    int sem1 = semaphore_open(123456); 
    int sem2 = semaphore_open(78901); 
    semaphore_signal(sem1);
    semaphore_wait(sem2);

    while(true)  {
        //...do main functionality of process etc...
    }
}

Process4.c:

int main() {
    //Synchronization area (relevant stuff):
    int sem1 = semaphore_open(123456); 
    int sem2 = semaphore_open(78901); 
    semaphore_signal(sem2);
    semaphore_signal(sem2);
    semaphore_signal(sem2);
    semaphore_wait(sem1);
    semaphore_wait(sem1);
    semaphore_wait(sem1);

    while(true)  {
        //...do main functionality of process etc...
    }
}

We run Process1 first, and it creates all of the semaphores into system memory used in the other processes (the other processes simply call semaphore_open to gain access to those semaphores). Then, all 4 processes have a signal operation, and then a wait. The signal operation causes process1, process2, and process3 to increment the value of sem1 by 1, so it's resultant maximum value is 3 (depending on what order the operating system decides to run these processes in). Process1, 2, and 3, are all waiting then on sem2, and process4 is waiting on sem1 as well. Process 4 then signals sem2 3 times to bring its value back up to 0, and waits on sem1 3 times. Since sem1 was a maximum of 3 from the signalling in the other processes (depending on what order they ran in, again), then it will bring its value back up to 0, and continue running. Thus, all processes will be synchronized.

So yea, not super confident on my answer. I feel that it depends heavily on what order the processes ran in, which is the whole point of synchronization -- that it shouldn't matter what order they run in, they all synchronize correctly. Also, I am doing a lot of work in Process4. Maybe it would be better to solve this using more than 2 semaphores? Wouldn't this also allow for more flexibility within the loops in each process, if I want to do further synchronization?

My question: Please explain why the above logic will or will not work, and/or a solution on how to solve this problem of 4 way synchronization. I'd imagine this is a very common thing to have to think about depending on the industry (eg. banking and synching up bank accounts). I know it is not very difficult, but I have never worked with semaphores before, so I'm kind of confused on how they work.

Answer 1

The precise semantics of your model semaphore library are not clear enough to answer your question definitively. However, if the difference between semaphore_create() and semaphore_open() is that the latter requires the specified semaphore to already exist, whereas the former requires it to not exist, then yes, the whole thing will fall down if process1 does not manage to create the needed semaphores before any of the other processes attempt to open them. (Probably it falls down in different ways if other semantics hold.)

That sort of issue can be avoided in a threading scenario because with threads there is necessarily an initial single-threaded segment wherein the synchronization structures can be initialized. There is also shared memory by which the various threads can communicate with one another. The answer @Dark referred to depends on those characteristics.

The essential problem with a barrier for multiple independent processes -- or for threads that cannot communicate via shared memory and that are not initially synchronized -- is that you cannot know which process needs to erect the barrier. It follows that each one needs to be prepared to do so. That can work in your model library if semaphore_create() can indicate to the caller which result was achieved, one of

• semaphore successfully created
• semaphore already exists
• (or error)

In that case, all participating processes (whose number you must know) can execute the same procedure, maybe something like this:

void process_barrier(int process_count) {
    sem_t *sem1, *sem2, *sem3;
    int result = semaphore_create(123456, &sem1);
    int counter;

    switch (result) {
        case SEM_SUCCESS:
            /* I am the controlling process */
            /* Finish setting up the barrier */
            semaphore_create(78901, &sem2);
            semaphore_create(23432, &sem3);
            /* let (n - 1) other processes enter the barrier... */
            for (counter = 1; counter < process_count; counter += 1) {
                semaphore_signal(sem1);
            }
            /* ... and wait for those (n - 1) processes to do so */
            for (counter = 1; counter < process_count; counter += 1) {
                semaphore_wait(sem2);
            }
            /* let all the (n - 1) waiting processes loose */
            for (counter = 1; counter < process_count; counter += 1) {
                semaphore_signal(sem3);
            }
            /* and I get to continue, too */
            break;
        case SEM_EXISTS_ERROR:
            /* I am NOT the controlling process */
            semaphore_open(123456, &sem1);
            /* wait, if necessary, for the barrier to be initialized */
            semaphore_wait(sem1);
            semaphore_open(78901, &sem2);
            semaphore_open(23432, &sem3);
            /* signal the controlling process that I have reached the barrier */
            semaphore_signal(sem2);
            /* wait for the controlling process to allow me to continue */
            semaphore_wait(sem3);
            break;
    }
}

Obviously, I have taken some minor liberties with your library interface, and I have omitted error checks except where they bear directly on the barrier's operation.

The three semaphores involved in that example serve distinct, well-defined purposes. sem1 guards the initialization of the synchronization constructs and allows the processes to choose which among them takes responsibility for controlling the barrier. sem2 serves to count how many processes have reached the barrier. sem3 blocks the non-controlling processes that have reached the barrier until the controlling process releases them all.