semaphore.html

COP4610: Operating Systems & Concurrent Programming

Semaphores, versus Mutexes & CVs

The POSIX thread synchronization objects, mutexes and condition variables, are a more recent invention than some other synchronization mechanisms. Using them, one can solve any problem that can be solved using other mechanisms. Here, we show how they can be used to implement one of the earliest and best known types of synchronization objects: semaphores.

Counting Semaphore

A type of synchronization object
Atomically counts available resources, and waits for resources to become available
Holds an integer value, called the count< which is initially non-negative
Has an associated queue of waiting procesess

Operations:

decrement, also known as P, down, and wait

s.count--;
if (s.count < 0) { enqueue and block this process }

increment, also known as V, up, post, and signal

s.count++;
if (s.count <= 0) {dequeue and unblock one process waiting on this semaphore, if any }

This is just one of several published variants of counting semaphores. The variants differ in such things as:

whether the initial count can be negative
whether the count can ever be negative
whether additional operations are supported

For example, the specification of the Linux realtime semaphores API (based on the POSIX specifications) carefully avoids dealing with negative values:

Semaphores are counters for resources shared between threads. The basic operations on semaphores are: increment the counter atomically, and wait until the counter is non- null and decrement it atomically.

sem_init initializes the semaphore object pointed to by tially to value. The pshared argument indicates whether the semaphore is local to the current process (pshared is zero) or is to be shared between several processes (pshared is not zero). LinuxThreads currently does not support process-shared semaphores, thus sem_init always returns with error ENOSYS if pshared is not zero.

sem_wait suspends the calling thread until the semaphore pointed to by sem has non-zero count. It then atomically decreases the semaphore count.
sem_trywait is a non-blocking variant of sem_wait. If the semaphore pointed to by sem has non-zero count, the count is atomically decreased and sem_trywait immediately returns 0. If the semaphore count is zero, sem_trywait immediately returns with error EAGAIN.
sem_post atomically increases the count of the semaphore pointed to by sem. This function never blocks and can safely be used in asynchronous signal handlers.

Note that use of the name signal for the semaphore increment operation, and also in the name pthread_cond_signal has no connection with Unix signals. In this respect, it would be perhaps clearer if we were using an object-oriented notation, like semaphore.signal. Limited to functional notation, the POSIX semaphore API uses the terms sem_wait and sem_post to avoid this confusion.

The name P is used traditionally for the semaphore wait operation and the name V is used traditionally for the semaphore signal operation, because these are the initial letters of the corresponding words in the Dutch language, which is the native language of the person (Edsgar Dijkstra) who wrote the definitive paper on semaphores.

Implementation of Linux/POSIX Semaphore as Monitor, using Mutex & CV

typdef struct counting_semaphore {
  pthread_mutex_t  M;
  pthread_cond_t  CV;
  int          value;
} sem_t;
void semaphore_wait () {
  pthread_mutex_lock (&S.M);
  while (S.value == 0) pthread_cond_wait (&S.CV, &S.M);
  S.value--;
  pthread_mutex_unlock (&S.M);
void semaphore_signal () {
  pthread_mutex_lock (&S.M);
  S.value++ ;
  if (S.value == 1) pthread_cond_signal (&S.CV);
  pthread_mutex_unlock (&S.M);
}

Semaphores are normally implemented by the operating system, using hardware instructions and other low-level building blocks. This example is intended for pedagogical purposes only. It illustrates:

that mutexes and CV's are as powerful as semaphores
how to construct a monitor using a mutex and CV
the difference between POSIX and counting semaphores

Whether the above provides FIFO service, is fair, etc. will depend on the implementation of the condition variable and mutex, which in general are not required to be fair.

By the way, the variation on semaphores implemented above does not allow the semaphore to take on a negative value. Could you modify the code above to support the model that allows negative semaphore values? How much more difficult would it be? Would there be any functional difference?

T. P. Baker. ($Id)