C - Shared memory and semaphores

Question

I want to create a C program with shared memory and semaphores. There should work two child processes. Both childs got a different int number. Then there is a goal number which should be written in the shared memory. Now both childs should subtract their numbers from the goal number until the goal number is lower or equal 0. I dont want that there appear race conditions. Thats why I try to use semaphores. But it dont work for me. Here is my code:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <errno.h>
#include <sys/sem.h>

#define SEG_SIZE sizeof(int)
#define NUM_OF_CHILDS 2

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

    int i, shm_id, sem_id, *shar_mem;
    int pid[NUM_OF_CHILDS];
    long waittime = 100;
    unsigned short marker[1];

    /* Define the numbers and the goal number */

    int numbers[2] = {28, 23};
    int goal = (numbers[0] + numbers[1]) * 4;   

    /* Create semaphor */

    if((sem_id = semget(IPC_PRIVATE, 1, IPC_CREAT|0644)) == -1){

        perror("semget()");
        exit(EXIT_FAILURE);

    }

    marker[0] = 1;

    /* All sem's to 1 */

    semctl(sem_id, 1, SETALL, marker);

    /* Create shared memory */

    if((shm_id = shmget(IPC_PRIVATE, SEG_SIZE, IPC_CREAT|0600)) == -1){

        perror("shmget()");
            exit(EXIT_FAILURE); 

    }
    if((shar_mem = (int *)shmat(shm_id, 0, 0)) == (int *) -1){

        perror("shmat()");
        exit(EXIT_FAILURE); 

    }
    *shar_mem = goal;

    /* Create child processes */

    for(i = 0; i < NUM_OF_CHILDS; i++){

        pid[i] = fork();
        if(pid[i] < 0){

            printf("Error!\n");
            exit(1);

        }
        if(pid[i] == 0){
            int count = 0;  
            /* Child processes */

            /* Structs for semaphor */

            struct sembuf enter, leave;

            enter.sem_num = leave.sem_num = 0;      
            enter.sem_flg = leave.sem_flg = SEM_UNDO;
            enter.sem_op = -1;              /* DOWN-Operation */
            leave.sem_op = 1;               /* UP-Operation */

            /* Join critical area */

            semop(sem_id, &enter, 1);

            while(*shar_mem > 0){

                usleep(waittime);
                *shar_mem -= numbers[i];

                count++;
            }

            printf("%i\n", count);

            /* Leave critical area */

            semop(sem_id, &leave, 1);

            exit(0);

        }

    }

    /* Wait for childs. */

    for(i = 0; i < NUM_OF_CHILDS; i++){

        waitpid(pid[i], NULL, 0);

    }

    /* Is goal equal 0 or lower? */

    int returnv;

    if(*shar_mem == 0){

        /* No race conditions */

        returnv = 0;

    }
    else {

        /* Race conditions */

        returnv = 1;

    }

    /* Close shared memory and semaphores */

    shmdt(shar_mem);
    shmctl(shm_id, IPC_RMID, 0);
    semctl(sem_id, 0, IPC_RMID);

    return returnv;

}

When the shared memory value is 0 at the end, there should be no race conditions. If it is lower than 0, there were race conditions. And I always get lower than 0. On top of that I count how much times each child subtract his number. The result: First Child 8 times and the second one 0 times. Can anyone help me with it?

Answer 1

In comments you remarked:

I tried to put the semop part into the loop. Now there 8 counts for the first child and 1 for the second. [...] I have to use semaphore.

Clearly, just moving the critical section boundaries into the interior of the loop is not sufficient. This is because there is no guarantee that when one process leaves the critical section by incrementing the semaphore, the other will immediately enter the critical section. It is possible that instead, the first process will loop around and re-enter the critical section before the second enters it. In fact, that result is fairly likely because the loop is tight, and we know that a process exiting the critical section is currently scheduled on some CPU.

It is possible to approach that problem by introducing a delay into the loop, outside the critical section, but this is a bit kludgy. For one thing, it needlessly slows the program. For another, although a sufficiently long delay can make the problem highly unlikely to manifest, no amount of delay can guarantee that the problem will not manifest. You're always at the mercy of the system's scheduler. Inasmuch as you already have a delay, however, you could make your desired behavior highly likely to manifest by putting it, too, outside the critical section.

There are a several ways to deal with this that provide various desirable semantics without artificial delays. All of them involve at least one more semaphore. Here are two of the more likely:

• Create a separate semaphore for each process. Choose one that you initialize to 1, and initialize the rest to 0. At the top the loop, each process decrements its own semaphore, and at the bottom it increment's the next process's semaphore. The processes then run in round-robin fashion.

• Use two additional semaphores to create a "cyclic barrier" at the top of the loop, in addition to the semaphore that you're using to protect the critical section. A cyclic barrier is a re-usable construct that causes some fixed number of processes / threads to all reach a given point before any of them can proceed. This does not make the process strictly alternate, but it prevents any process from ever being more than one loop iteration ahead of the other(s). It has the advantage that it requires only three semaphores regardless of how many processes are being coordinated.

The former is easier to conceptualize and write, even though it places stronger guarantees on process ordering.

Answer 2

Adapt your while loop to something like this in order to leave the critical section after subtracting one time:

for ( ; ; ) {
  usleep(waittime);
  semop(sem_id, &enter, 1);
  if (*shar_mem <= 0) {
    semop(sem_id, &leave, 1);
    break;
  }
  *shar_mem -= numbers[i];
  semop(sem_id, &leave, 1);
  count++;
}

But as stated in my comment it's not guaranteed that both children subtract their numbers alternating, i.e. a result less than zero is possible