System V Semaphores in Linux

Semaphores

A semaphore is a mechanism for synchronizing processes and threads. Semaphore, in Unix-like systems, are provided under interprocess communication (IPC) facilities along with message queues and shared memory. While message queues can be used by themselves for interprocess communication, semaphores are needed for implementing shared memory based interprocess communication systems. Semaphores are not just about interprocess communication; they can be used for any synchronization requirement between processes and threads.

Under Linux, the IPC comes in two flavors, the traditional System V IPC and the newer POSIX IPC. This post is about System V IPC, and, in particular, the System V semaphores.

To create a System V semaphore, we need a System V IPC key. We can create the key with the ftok function.

#include <sys/types.h>
#include <sys/ipc.h>

key_t ftok (const char *pathname, int proj_id);

The pathname must be an existing and accessible file. The contents of this file are immaterial. Only the lowest eight bits of proj_id are used, which must not be zero. A System V IPC key of type key_t is returned.

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

int semget (key_t key, int nsems, int semflg);

semget gets a semaphore set id based on the first parameter, a System V IPC key. If the key has the value IPC_PRIVATE, a new set of semaphores is created, using the last nine bits of semflg for permissions. (Other bits of semflg are not considered if the key is IPC_PRIVATE.) nsems is number of semaphores requested. The System V semaphore calls are complicated because they deal with a set of semaphores. However, we can keep things simple by making nsems = 1 and asking for just one semaphore. If the last parameter, semflg specifies IPC_CREAT and no semaphore set is associated with the key, a new semaphore set is created. If semflg specifies IPC_CREAT | IPC_EXCL, and a semaphore set exists for the key, semget fails with errno set to EEXIST. semget does not initialize the semaphores; for that, semctl system call has to be used. So if a semaphore has been created with semget, it cannot be used right away. It has to be initialized with a value using semctl, before P and V operations can be done on it using the semop system call.

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

int semctl (int semid, int semnum, int cmd, ...);

semctl is for semaphore control operations. This call can be used for all semaphores in the set identified by semid and for a particular semaphore identified by semid and semnum. In a semaphore set, semaphores are numbered 0 onwards. The third parameter is the command for the semctl system call. The important commands are, IPC_STAT, for getting the data from kernel data structures for the semaphore set into the struct semid_ds pointed by buf described below, IPC_SET, for setting some of the fields in the struct semid_ds for the semaphore set, GETALL, for getting values of all semaphores of the set in the array described below, SETALL, for setting initial values of all semaphores in the set, SETVAL, for setting an initial value for a semaphore, and IPC_RMID for removing the semaphore set.

semctl can have a fourth optional argument, which is the union, semun. The initial semaphore value for the cmd SETVAL can be passed in the union member, val.

union semun {
    int val;                /* value for SETVAL */
    struct semid_ds *buf;   /* buffer for IPC_STAT & IPC_SET */
    unsigned short *array;  /* array for GETALL & SETALL */
    struct seminfo *__buf;  /* buffer for IPC_INFO */
};

And, the struct semid_ds for the above union is,

struct semid_ds {
    struct ipc_perm sem_perm;  /* Ownership and permissions */
    time_t          sem_otime; /* Last semop time */
    time_t          sem_ctime; /* Last change time */
    unsigned long   sem_nsems; /* No. of semaphores in set */
};

with the struct ipc_perm being,

struct ipc_perm {
    key_t          __key; /* Key supplied to semget(2) */
    uid_t          uid;   /* Effective UID of owner */
    gid_t          gid;   /* Effective GID of owner */
    uid_t          cuid;  /* Effective UID of creator */
    gid_t          cgid;  /* Effective GID of creator */
    unsigned short mode;  /* Permissions */
    unsigned short __seq; /* Sequence number */
};

The need of two system calls to make a semaphore ready for use has some usage implications. What if one process creates a semaphore using semget and other process tries to use it before the first process initializes it using semctl? The saving grace is that, although, semget does not initialize the semaphore value, it initializes the sem_otime member of the struct semid_ds for the semaphore set to zero. The second process should check it using semctl and wait for it to become nonzero before doing any semop on the semaphores in the set. Now think of the situation when the application has been restarted and semaphores from previous run are lying around. The startup script must remove any existing semaphores for the key using the ipcrm command before starting the processes.

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

int semop (int semid, struct sembuf *sops, size_t nsops);

The semop system call is for System V semaphore operations. You can do P and V operations on the System V semaphores using the semop system call. However, semop has a lot more functionality. The first parameter, semid is the id of the semaphore set. The second parameter, a pointer to the struct sembuf, and the latter, is,

struct sembuf {
    unsigned short sem_num;  /* semaphore number */
    short          sem_op;   /* semaphore operation */
    short          sem_flg;  /* operation flags */
};

semop allows you to operate on selected semaphores in the set identified by semid. A struct sembuf defines an operation to be done. You can have an array of struct sembuf‘s and nsops gives the size of the array. A semaphore operation is done for each member of the struct sembuf array.

A single struct sembuf represents a semaphore operation. sem_num is the semaphore number in the set. sem_op can be a positive, zero or negative integer. If sem_op is positive, the value is added to the semaphore. If sem_op is zero the call blocks till the time semaphore becomes zero. If sem_op is negative, its absolute value is subtracted from the semaphore value. If the result would become negative, the call blocks till the time semaphore value increases to a level that the subtraction would result in non-negative semaphore value.

The flag, sem_flg, can have IPC_NOWAIT set, in which case the call does not block and returns immediately. That is, if a semaphore operation could not be done immediately and would have required the process to block (had IPC_NOWAIT not been specified), the process does not block (because of the IPC_NOWAIT) and returns immediately with errno set to EAGAIN.

The flag, sem_flg, can also have SEM_UNDO set, in which case the semaphore operation is automatically undone when the process terminates. For each process, an adjustment value is kept for each semaphore. Whenever the process does a semop on a semaphore, the sem_op value is subtracted from the adjustment value. When the process terminates, the adjustment value is added to the semaphore value. This might be useful where a semaphore is used for locking access to a critical section of code. Suppose the process terminates for some reason, the semaphore value would be restored and resources in the critical section would be unlocked. Now, this SEM_UNDO flag has a limitation. What should the system do if adding the adjustment would make the semaphore negative? Linux tries to do the best possible under the circumstances. It decreases the semaphore to zero in such cases and the process terminates.

 
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

int semtimedop (int semid, struct sembuf *sops, size_t nsops,
                      const struct timespec *timeout);

semtimedop is just like semop, except that it has a timeout argument. In those cases that a process would block while executing semop call, semtimedop would block too, except that duration of blocking is limited by the timeout. If timeout occurs, the call returns without doing any of the semaphore operations and with errno set to EAGAIN. If timeout is NULL, semtimedop behaves exactly like the semop call.

System V semaphores calls are very complicated. The example below tries to illustrate how to use System V semaphores in a simple way. We have just one semaphore in each semaphore set. We don’t use IPC_NOWAIT and SEM_UNDO flags. And we use the semop system call to implement the P and V operations on a semaphore. The example program implements a solution to the producer – consumer problem. There are multiple producer threads, producing strings of text. There is one consumer thread that prints these strings in the chronological order. The example illustrates the P and V operations on mutual exclusion (mutex) and counting semaphores.

/*
 *
 *   semaphore-example.c: Program to demonstrate System V semaphores 
 *                        in C under Linux (Producer - Consumer problem)
 */

#include <sys/types.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <errno.h>
#include <pthread.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

#define SEM_MUTEX_KEY "/tmp/sem-mutex-key"
#define SEM_BUFFER_COUNT_KEY "/tmp/sem-buffer-count-key"
#define SEM_SPOOL_SIGNAL_KEY "/tmp/sem-spool-signal-key"

// Buffer data structures
#define MAX_BUFFERS 10
char buf [MAX_BUFFERS] [100];
int buffer_index;
int buffer_print_index;

int mutex_sem, buffer_count_sem, spool_signal_sem;

void *producer (void *arg);
void *spooler (void *arg);

int main (int argc, char **argv)
{
    /* for semaphore */
    key_t s_key;
    union semun  
    {
        int val;
        struct semid_ds *buf;
        ushort array [1];
    } sem_attr;
    pthread_t tid_producer [10], tid_spooler;
    int i, r;

    // initialization
    buffer_index = buffer_print_index = 0;

    //  mutual exclusion semaphore, mutex_sem with an initial value 1.
    /* generate a key for creating semaphore  */
    if ((s_key = ftok (SEM_MUTEX_KEY, 'a')) == -1) {
        perror ("ftok"); exit (1);
    }
    if ((mutex_sem = semget (s_key, 1, 0660 | IPC_CREAT)) == -1) {
        perror ("semget"); exit (1);
    }
    // Giving initial value. 
    sem_attr.val = 1;        // unlocked
    if (semctl (mutex_sem, 0, SETVAL, sem_attr) == -1) {
        perror ("semctl SETVAL"); exit (1);
    }
    
    // counting semaphore, indicating the number of available buffers.
    /* generate a key for creating semaphore  */
    if ((s_key = ftok (SEM_BUFFER_COUNT_KEY, 'a')) == -1) {
        perror ("ftok"); exit (1);
    }
    if ((buffer_count_sem = semget (s_key, 1, 0660 | IPC_CREAT)) == -1) {
        perror ("semget"); exit (1);
    }
    // giving initial values
    sem_attr.val = MAX_BUFFERS;    // MAX_BUFFERS are available
    if (semctl (buffer_count_sem, 0, SETVAL, sem_attr) == -1) {
        perror (" semctl SETVAL "); exit (1);
    }

    // counting semaphore, indicating the number of strings to be printed.
    /* generate a key for creating semaphore  */
    if ((s_key = ftok (SEM_SPOOL_SIGNAL_KEY, 'a')) == -1) {
        perror ("ftok"); exit (1);
    }
    if ((spool_signal_sem = semget (s_key, 1, 0660 | IPC_CREAT)) == -1) {
        perror ("semget"); exit (1);
    }
    // giving initial values
    sem_attr.val = 0;    // 0 strings are available initially.
    if (semctl (spool_signal_sem, 0, SETVAL, sem_attr) == -1) {
        perror (" semctl SETVAL "); exit (1);
    }
    
    // Create spooler
    if ((r = pthread_create (&tid_spooler, NULL, spooler, NULL)) != 0) {
        fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
    }

    // Create 10 producer threads
    int thread_no [10];
    for (i = 0; i < 10; i++) {
        thread_no [i] = i;
        if ((r = pthread_create (&tid_producer [i], NULL, producer, (void *) &thread_no [i])) != 0) {
            fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
        }
    }
    // Wait for producers to terminate
    for (i = 0; i < 10; i++)
        if ((r = pthread_join (tid_producer [i], NULL)) == -1) {
            fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
        }
    
    // No more strings to print? Wait for spool_signal_sem to become 0
    struct sembuf asem [1];
    asem [0].sem_num = 0;
    asem [0].sem_op = 0;
    asem [0].sem_flg = 0;
    if (semop (spool_signal_sem, asem, 1) == -1) {
	perror ("semop: spool_signal_sem"); exit (1);
    }

    // terminate spooler
    if ((r = pthread_cancel (tid_spooler)) != 0) {
        fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
    }
    
    // remove semaphores
    if (semctl (mutex_sem, 0, IPC_RMID) == -1) {
        perror ("semctl IPC_RMID"); exit (1);
    }
    if (semctl (buffer_count_sem, 0, IPC_RMID) == -1) {
        perror ("semctl IPC_RMID"); exit (1);
    }
    if (semctl (spool_signal_sem, 0, IPC_RMID) == -1) {
        perror ("semctl IPC_RMID"); exit (1);
    }

    exit (0);
}

// producer: produce strings for printing
// There might be multiple producer threads
void *producer (void *arg)
{
    // Create 10 strings and terminate
    int i;
    int my_id = *((int *) arg);
    struct sembuf asem [1];
    int count = 0;

    asem [0].sem_num = 0;
    asem [0].sem_op = 0;
    asem [0].sem_flg = 0;

    for (i = 0; i < 10; i++) {
        // get a buffer: P (buffer_count_sem);
        asem [0].sem_op = -1;
        if (semop (buffer_count_sem, asem, 1) == -1) {
	    perror ("semop: buffer_count_sem"); exit (1);
        }
    
        /* There might be multiple producers. We must ensure that 
            only one producer uses buffer_index at a time.  */
        // P (mutex_sem);
        asem [0].sem_op = -1;
        if (semop (mutex_sem, asem, 1) == -1) {
	    perror ("semop: mutex_sem"); exit (1);
        }

	    // Critical section
            int j = buffer_index;
            buffer_index++;
            if (buffer_index == MAX_BUFFERS)
                buffer_index = 0;

        // Release mutex sem: V (mutex_sem)
        asem [0].sem_op = 1;
        if (semop (mutex_sem, asem, 1) == -1) {
	    perror ("semop: mutex_sem"); exit (1);
        }
    
	// Produce a string
        sprintf (buf [j], "Thread %d: %d\n", my_id, ++count);
	// Tell spooler that there is a string to print: V (spool_signal_sem);
        asem [0].sem_op = 1;
        if (semop (spool_signal_sem, asem, 1) == -1) {
	    perror ("semop: spool_signal_sem"); exit (1);
        }
    
        // Take a nap
        sleep (1);
    }
}

// There is only one spooler thread
void *spooler (void *arg)
{
    struct sembuf asem [1];

    asem [0].sem_num = 0;
    asem [0].sem_op = 0;
    asem [0].sem_flg = 0;

    while (1) {  // forever
        // Is there a string to print? P (spool_signal_sem);
        asem [0].sem_op = -1;
        if (semop (spool_signal_sem, asem, 1) == -1) {
	    perror ("semop: spool_signal_sem"); exit (1);
        }
    
        printf ("%s", buf [buffer_print_index]);

        /* Since there is only one thread (spooler) using the 
           buffer_print_index, mutex semaphore is not necessary */
        buffer_print_index++;
        if (buffer_print_index == MAX_BUFFERS)
           buffer_print_index = 0;

        /* Contents of one buffer has been printed.
           One more buffer is available for use by producers.
           Release buffer: V (buffer_count_sem);  */
        asem [0].sem_op = 1;
        if (semop (buffer_count_sem, asem, 1) == -1) {
	    perror ("semop: buffer_count_sem"); exit (1);
        }
    }
}

We can compile and run the above program using the commands,

$ gcc semaphore-example.c -lpthread -o semaphore-example
$ > /tmp/sem-mutex-key
$ > /tmp/sem-buffer-count-key
$ > /tmp/sem-spool-signal-key
$ ./semaphore-example
Thread 0: 1
Thread 1: 1
Thread 2: 1
Thread 3: 1
...

1. POSIX Semaphores
2. Semaphore Basics
3. POSIX Threads Synchronization in C