Process Synchronization With Semaphores

One of the problems when writing multi-process application is the need to synchronize various operations between the processes. Communicating requests using pipes, sockets and message queues is one way to do it.

A semaphore is a resource that contains an integer value, and allows processes to synchronize by testing and setting this value in a single atomic operation. This means that the process that tests the value of a semaphore and sets it to a different value (based on the test), is guaranteed no other process will interfere with the operation in the middle.

Two types of operations can be carried on a semaphore: wait and signal. A set operation first checks if the semaphore's value equals some number. If it does, it decreases its value and returns. If it does not, the operation blocks the calling process until the semaphore's value reaches the desired value. A signal operation increments the value of the semaphore, possibly awakening one or more processes that are waiting on the semaphore. How this mechanism can be put to practical use will be explained soon.

A semaphore set is a structure that stores a group of semaphores together, and possibly allows the process to commit a transaction on part or all of the semaphores in the set together. In here, a transaction means that we are guaranteed that either all operations are done successfully, or none is done at all. Note that a semaphore set is not a general parallel programming concept, it's just an extra mechanism supplied by SysV IPC.

Creation of a semaphore set is done using the semget() system call. Similarly to the creation of message queues, we supply some ID for the set, and some flags (used to define access permission mode and a few options). We also supply the number of semaphores we want to have in the given set. This number is limited to SEMMSL, as defined in file /usr/include/sys/sem.h. Lets see an example:

/* ID of the semaphore set.     */
int sem_set_id_1;
int sem_set_id_2;

/* create a private semaphore set with one semaphore in it, */
/* with access only to the owner.                           */
sem_set_id_1 = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600);
if (sem_set_id_1 == -1) {
    perror("main: semget");
    exit(1);
}

/* create a semaphore set with ID 250, three semaphores */
/* in the set, with access only to the owner.           */
sem_set_id_2 = semget(250, 3, IPC_CREAT | 0600);
if (sem_set_id_2 == -1) {
    perror("main: semget");
    exit(1);
}

Note that in the second case, if a semaphore set with ID 250 already existed, we would get access to the existing set, rather than a new set be created. This works just like it worked with message queues.

After the semaphore set is created, we need to initialize the value of the semaphores in the set. We do that using the semctl() system call. Note that this system call has other uses, but they are not relevant to our needs right now. Lets assume we want to set the values of the three semaphores in our second set to values 3, 6 and 0, respectively. The ID of the first semaphore in the set is '0', the ID of the second semaphore is '1', and so on.

/* use this to store return values of system calls.   */
int rc;

/* initialize the first semaphore in our set to '3'.  */
rc = semctl(sem_set_id_2, 0, SETVAL, 3);
if (rc == -1) {
    perror("main: semctl");
    exit(1);
}

/* initialize the second semaphore in our set to '6'. */
rc = semctl(sem_set_id_2, 1, SETVAL, 6);
if (rc == -1) {
    perror("main: semctl");
    exit(1);
}

/* initialize the third semaphore in our set to '0'.  */
rc = semctl(sem_set_id_2, 2, SETVAL, 0);
if (rc == -1) {
    perror("main: semctl");
    exit(1);
}

There are one comment to be made about the way we used semctl() here. According to the manual, the last parameter for this system call should be a union of type union semun. However, since the SETVAL (set value) operation only uses the int val part of the union, we simply passed an integer to the function. The proper way to use this system call was to define a variable of this union type, and set its value appropriately, like this:

/* use this variable to pass the value to the semctl() call */
union semun sem_val;

/* initialize the first semaphore in our set to '3'. */
sem_val.val = 0;
rc = semctl(sem_set_id_2, 2, SETVAL, sem_val);
if (rc == -1) {
    perror("main: semctl");
    exit(1);
}

We used the first form just for simplicity. From now on, we will only use the second form.

Sometimes we have a resource that we want to allow only one process at a time to manipulate. For example, we have a file that we only want written into only by one process at a time, to avoid corrupting its contents. Of-course, we could use various file locking mechanisms to protect the file, but we will demonstrate the usage of semaphores for this purpose as an example. Later on we will see the real usage of semaphores, to protect access to shared memory segments. Anyway, here is a code snippest. It assumes the semaphore in our set whose id is "sem_set_id" was initialized to 1 initially:

/* this function updates the contents of the file with the given path name. */
void update_file(char* file_path, int number)
{
    /* structure for semaphore operations.   */
    struct sembuf sem_op;
    FILE* file;

    /* wait on the semaphore, unless it's value is non-negative. */
    sem_op.sem_num = 0;
    sem_op.sem_op = -1;   /* <-- Comment 1 */
    sem_op.sem_flg = 0;
    semop(sem_set_id, &sem_op, 1);

    /* Comment 2 */
    /* we "locked" the semaphore, and are assured exclusive access to file.  */
    /* manipulate the file in some way. for example, write a number into it. */
    file = fopen(file_path, "w");
    if (file) {
        fprintf(file, "%d\n", number);
        fclose(file);
    }

    /* finally, signal the semaphore - increase its value by one. */
    sem_op.sem_num = 0;
    sem_op.sem_op = 1;   /* <-- Comment 3 */
    sem_op.sem_flg = 0;
    semop(sem_set_id, &sem_op, 1);
}

This code needs some explanations, especially regarding the semantics of the semop() calls.

1. Comment 1 - before we access the file, we use semop() to wait on the semaphore. Supplying '-1' in sem_op.sem_op means: If the value of the semaphore is greater than or equal to '1', decrease this value by one, and return to the caller. Otherwise (the value is 1 or less), block the calling process, until the value of the semaphore becomes '1', at which point we return to the caller.
2. Comment 2 - The semantics of semop() assure us that when we return from this function, the value of the semaphore is 0. Why? it couldn't be less, or else semop() won't return. It couldn't be more due to the way we later on signal the semaphore. And why it cannot be more than '0'? read on to find out...
3. Comment 3 - after we are done manipulating the file, we increase the value of the semaphore by 1, possibly waking up a process waiting on the semaphore. If several processes are waiting on the semaphore, the first that got blocked on it is wakened and continues its execution.

Now, lets assume that any process that tries to access the file, does it only via a call to our "update_file" function. As you can see, when it goes through the function, it always decrements the value of the semaphore by 1, and then increases it by 1. Thus, the semaphore's value can never go above its initial value, which is '1'. Now lets check two scenarios:

1. No other process is executing the "update_file" concurrently. In this case, when we enter the function, the semaphore's value is '1'. after the first semop() call, the value of the semaphore is decremented to '0', and thus our process is not blocked. We continue to execute the file update, and with the second semop() call, we raise the value of the semaphore back to '1'.
2. Another process is in the middle of the "update_file" function. If it already managed to pass the first call to semop(), the value of the semaphore is '0', and when we call semop(), our process is blocked. When the other process signals the semaphore with the second semop() call, it increases the value of the semaphore back to '0', and it wakes up the process blocked on the semaphore, which is our process. We now get into executing the file handling code, and finally we raise the semaphore's value back to '1' with our second call to semop().

We have the source code for a program demonstrating the mutex concept, in the file named sem-mutex.c. The program launches several processes (5, as defined by the NUM_PROCS macro), each of which is executing the "update_file" function several times in a row, and then exits. Try running the program, and scan its output. Each process prints out its PID as it updates the file, so you can see what happens when. Try to play with the DELAY macro (specifying how long a process waits between two calls to "update_file") and see how it effects the order of the operations. Check what happens if you replace the delay loop in the "do_child_loop" function, with a call to sleep().