Synchronization With Semaphores

A semaphore is a programming construct designed by E. W. Dijkstra in the late 1960s. Dijkstra's model was the operation of railroads. Consider a stretch of railroad where a single track is present over which only one train at a time is allowed.

A semaphore synchronizes travel on this track. A train must wait before entering the single track until the semaphore is in a state that permits travel. When the train enters the track, the semaphore changes state to prevent other trains from entering the track. A train that is leaving this section of track must again change the state of the semaphore to allow another train to enter.

In the computer version, a semaphore appears to be a simple integer. A thread waits for permission to proceed and then signals that the thread has proceeded by performing a P operation on the semaphore.

The thread must wait until the semaphore's value is positive, then change the semaphore's value by subtracting 1 from the value. When this operation is finished, the thread performs a V operation, which changes the semaphore's value by adding 1 to the value. These operations must take place atomically. These operations cannot be subdivided into pieces between which other actions on the semaphore can take place. In the P operation, the semaphore's value must be positive just before the value is decremented, resulting in a value that is guaranteed to be nonnegative and 1 less than what it was before it was decremented.

In both P and V operations, the arithmetic must take place without interference. The net effect of two V operations performed simultaneously on the same semaphore, should be that the semaphore's new value is 2 greater than it was.

The mnemonic significance of P and V is unclear to most of the world, as Dijkstra is Dutch. However, in the interest of true scholarship: P stands for prolagen, a made-up word derived from proberen te verlagen, which means try to decrease. V stands for verhogen, which means increase. The mnemonic significance is discussed in one of Dijkstra's technical notes, EWD 74.

sem_wait(3RT) and sem_post(3RT) correspond to Dijkstra's P and V operations. sem_trywait(3RT) is a conditional form of the P operation. If the calling thread cannot decrement the value of the semaphore without waiting, the call to returns immediately with a nonzero value.

The two basic sorts of semaphores are binary semaphores and counting semaphores. Binary semaphores never take on values other than zero or one, and counting semaphores take on arbitrary nonnegative values. A binary semaphore is logically just like a mutex.

However, although not always enforced, mutexes should be unlocked only by the thread that holds the lock. Because no notion exists of “the thread that holds the semaphore,” any thread can perform a V or sem_post (3RT) operation.

Counting semaphores are nearly as powerful as conditional variables when used in conjunction with mutexes. In many cases, the code might be simpler when implemented with counting semaphores rather than with condition variables, as shown in Example 4-14, Example 4-15, and Example 4-16.

However, when a mutex is used with condition variables, an implied bracketing is present. The bracketing clearly delineates which part of the program is being protected. This behavior is not necessarily the case for a semaphore, which might be called the go to of concurrent programming. A semaphore is powerful but too easy to use in an unstructured, indeterminate way.

Named and Unnamed Semaphores

POSIX semaphores can be unnamed or named. Unnamed semaphores are allocated in process memory and initialized. Unnamed semaphores might be usable by more than one process, depending on how the semaphore is allocated and initialized. Unnamed semaphores are either private, inherited through fork(), or are protected by access protections of the regular file in which they are allocated and mapped.

Named semaphores are like process-shared semaphores, except that named semaphores are referenced with a pathname rather than a pshared value. Named semaphores are sharable by several processes. Named semaphores have an owner user-id, group-id, and a protection mode.

The functions sem_open, sem_getvalue, sem_close, and sem_unlink are available to open, retrieve, close, and remove named semaphores. By using sem_open, you can create a named semaphore that has a name defined in the file system name space.

For more information about named semaphores, see the sem_open, sem_getvalue, sem_close, and sem_unlink man pages.

Counting Semaphores Overview

Conceptually, a semaphore is a nonnegative integer count. Semaphores are typically used to coordinate access to resources, with the semaphore count initialized to the number of free resources. Threads then atomically increment the count when resources are added and atomically decrement the count when resources are removed.

When the semaphore count becomes zero, no more resources are present. Threads that try to decrement the semaphore when the count is zero block until the count becomes greater than zero.

Table 4-6 Routines for Semaphores

Because semaphores need not be acquired and be released by the same thread, semaphores can be used for asynchronous event notification, such as in signal handlers. And, because semaphores contain state, semaphores can be used asynchronously without acquiring a mutex lock as is required by condition variables. However, semaphores are not as efficient as mutex locks.

The scheduling policy determines the order in which blocked threads are awakened. The default scheduling policy, SCHED_OTHER, does not specify the order in which threads are awakened. Under the SCHED_FIFO and SCHED_RR real-time scheduling policies, threads are awakened in priority order.

Semaphores must be initialized before use, however semaphores do not have attributes.

Initializing a Semaphore

Use sem-init to initialize the unnamed semaphore variable pointed to by sem to value amount.

sem_init Syntax

int sem_init(sem_t *sem, int pshared, unsigned int value);

#include <semaphore.h>

sem_t sem;
int pshared;
int ret;
int value;

/* initialize a private semaphore */
pshared = 0;
value = 1;
ret = sem_init(&sem, pshared, value); 

If the value of pshared is zero, then the semaphore cannot be shared between processes. If the value of pshared is nonzero, then the semaphore can be shared between processes.

Multiple threads must not initialize the same semaphore.

A semaphore must not be reinitialized while other threads might be using the semaphore.

Initializing Semaphores With Intraprocess Scope

When pshared is 0, the semaphore can be used by all the threads in this process only.

#include <semaphore.h>

sem_t sem;
int ret;
int count = 4;

/* to be used within this process only */
ret = sem_init(&sem, 0, count); 

Initializing Semaphores With Interprocess Scope

When pshared is nonzero, the semaphore can be shared by other processes.

#include <semaphore.h>

sem_t sem;
int ret;
int count = 4;

/* to be shared among processes */
ret = sem_init(&sem, 1, count);

sem_init Return Values

sem_init() returns zero after completing successfully. Any other return value indicates that an error occurred. When any of the following conditions occurs, the function fails and returns the corresponding value.

EINVAL

Description: The value argument exceeds SEM_VALUE_MAX .

ENOSPC

Description: A resource that is required to initialize the semaphore has been exhausted. The limit on semaphores SEM_NSEMS_MAX has been reached.

EPERM

Description: The process lacks the appropriate privileges to initialize the semaphore.

Incrementing a Semaphore

Use sem_post to atomically increment the semaphore pointed to by sem.

sem_post Syntax

int sem_post(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_post(&sem); /* semaphore is posted */

When any threads are blocked on the semaphore, one of the threads is unblocked.

sem_post Return Values

sem_post() returns zero after completing successfully. Any other return value indicates that an error occurred. When the following condition occurs, the function fails and returns the corresponding value.

EINVAL

Description: sem points to an illegal address.

Blocking on a Semaphore Count

Use sem_wait to block the calling thread until the semaphore count pointed to by sem becomes greater than zero, then atomically decrement the count.

sem_wait Syntax

int sem_wait(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_wait(&sem); /* wait for semaphore */

sem_wait Return Values

sem_wait() returns zero after completing successfully. Any other return value indicates that an error occurred. When any of the following conditions occurs, the function fails and returns the corresponding value.

EINVAL

Description: sem points to an illegal address.

EINTR

Description: A signal interrupted this function.

Decrementing a Semaphore Count

Use sem_trywait to try to atomically decrement the count in the semaphore pointed to by sem when the count is greater than zero.

sem_trywait Syntax

int sem_trywait(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_trywait(&sem); /* try to wait for semaphore*/

This function is a nonblocking version of sem_wait(). sem_trywait() returns immediately if unsuccessful.

sem_trywait Return Values

sem_trywait() returns zero after completing successfully. Any other return value indicates that an error occurred. When any of the following conditions occurs, the function fails and returns the corresponding value.

EINVAL

Description: sem points to an illegal address.

EINTR

Description: A signal interrupted this function.

EAGAIN

Description: The semaphore was already locked, so the semaphore cannot be immediately locked by the sem_trywait() operation.

Destroying the Semaphore State

Use sem_destroy to destroy any state that is associated with the unnamed semaphore pointed to by sem.

sem_destroy Syntax

int sem_destroy(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_destroy(&sem); /* the semaphore is destroyed */

The space for storing the semaphore is not freed.

sem_destroy Return Values

sem_destroy() returns zero after completing successfully. Any other return value indicates that an error occurred. When the following condition occurs, the function fails and returns the corresponding value.

EINVAL

Description: sem points to an illegal address.

Producer and Consumer Problem Using Semaphores

The data structure in Example 4-14 is similar to the structure used for the condition variables example, shown in Example 4-11. Two semaphores represent the number of full and empty buffers. The semaphores ensure that producers wait until buffers are empty and that consumers wait until buffers are full.

Example 4-14 Producer and Consumer Problem With Semaphores

typedef struct {
    char buf[BSIZE];
    sem_t occupied;
    sem_t empty;
    int nextin;
    int nextout;
    sem_t pmut;
    sem_t cmut;
} buffer_t;

buffer_t buffer;

sem_init(&buffer.occupied, 0, 0);
sem_init(&buffer.empty,0, BSIZE);
sem_init(&buffer.pmut, 0, 1);
sem_init(&buffer.cmut, 0, 1);
buffer.nextin = buffer.nextout = 0;

Another pair of binary semaphores plays the same role as mutexes. The semaphores control access to the buffer when multiple producers use multiple empty buffer slots, and when multiple consumers use multiple full buffer slots. Mutexes would work better here, but would not provide as good an example of semaphore use.

Example 4-15 Producer and Consumer Problem: the Producer

void producer(buffer_t *b, char item) {
    sem_wait(&b->empty);
    sem_wait(&b->pmut);

    b->buf[b->nextin] = item;
    b->nextin++;
    b->nextin %= BSIZE;

    sem_post(&b->pmut);
    sem_post(&b->occupied);
}

Example 4-16 Producer and Consumer Problem: the Consumer

char consumer(buffer_t *b) {
    char item;

    sem_wait(&b->occupied);
   
    sem_wait(&b->cmut);

    item = b->buf[b->nextout];
    b->nextout++;
    b->nextout %= BSIZE;

    sem_post(&b->cmut);

    sem_post(&b->empty);

    return(item);
}