Hacker School: day 265.

(My batch ended on August 22, 2013, but as they say, never graduate.)

I’m sort of embarrassed to admit that I never had a really good handle on how the basic concurrency primitives are implemented. I’m now pretty glad I started to dig into this, because most of the analogies people use to describe mutexes and semaphores are slightly wrong.

Mutexes at a high level

A mutex is a portmanteu of the words mutual and exclusion. At a basic level, it is a variable that all concurrently-executing threads can see, which stops concurrent threads from accessing a block of code. Consider the following pseudo-code:

do_something(x) 
lock_mutex(s)        // "lock" mutex using variable `s`
f(x)                 // CONCURRENT ACCESS ON THIS CODE IS PREVENTED
unlock_mutex(s)      // "unlock" mutex
do_something_else(x)

Some notes:

• In this case the mutex is the variable s.
• All the concurrent threads can see s.
• In this case, x is a resource shared among the threads.
• When one thread “locks” on s, it changes the state of s so that all the other threads know that another thread is executing that code.
• Later it “unlocks” s to indicate to the other threads that the code can be safely run.
• So, in order for a thread to call f(x) in this code block, it needs to wait for s to indicate that it is free and it needs to acquire the lock.

Note that a mutex does not necessarily prevent multiple threads from accessing data concurrently – it only prevents concurrent access to code. In the example above, x could be altered by the do_something or do_something_else functions. The only code that’s restricted is the call to f(x).

In other words, to protect against concurrent access to data, you have to use mutexes to lock access to all the code that touches the data.

That is what a mutex does. But what is a mutex? What type of thing is s?

At the system level, the mutex s can be implemented using a normal global integer, using the following assumptions:

• If a thread tries to access the shared resource and s == 0, (i.e., it doesn’t have the key) then we will take that to mean that the resource is currently being used by another thread.
• If s == 1, then it is free to be accessed.

This leaves the problem of how different threads can cooperate by changing the value of s. Dijkstra, who invented all of this, proposes that manipulation should happen using only a pair of curious functions, P, and V:

P(s)  // "lock" mutex using variable `s`
f(x)  // DO STUFF HERE TO SHARED RESOURCE x
V(s)  // "unlock" mutex

So, what do these functions do?

• P (standing for the Dutch proberent, meaning “to test”), will basically test “lock” the block of code against concurrent access, or block until it can acquire the lock. More specifically, it will check the value of s, and if s == 0, then the thread will suspend the thread and wait until s != 0 to proceed. If s != 0 (and, if necessary, the thread is resumed), then P will immediately decrement s and return.
• V (standing for the Dutch verhogen, meaning “to increment”), which will basically “unlock” the code block, so that other threads are free to acquire the lock and execute the code. More specifically, the function simply increments s. If there are waiting calls to P, this function will restart one of them.

In other words, the current thread will wait at the call to P if s == 0, and will resume execution when the thread that’s currently using the resource x calls V to increment the variable s. On the other hand, if s == 1, then we will simply decrement s, which will “lock” against concurrent calls to f(x).

Mutexes are not like locking a bathroom

Brief interlude. It’s often said that mutexes work like keys to a bathroom. The thinking goes, there is one key, and customers have to acquire the key to unlock and use the bathroom.

I don’t like this analogy. It’s not obvious from this analogy that the lock applies to the code and not the data, which I think is an important distinction.

A mutex is not like a bathroom key. A mutex is like a mutex.

The semaphore at a high level

It turns out that the variable s has a name – it’s called a semaphore. Slightly more formally, a semaphore is a variable that:

• is an integer, and
• can only be manipulated with the functions P and V.

A mutex is just a semaphore that is used to guarantee that only one thread is accessing a bit of code at a time. It does this by forcing s to be either 0 or 1–either the resource is currently being used, or it is not.

When s doesn’t have to be a 0 or a 1, then it is usually called a counting semaphore. In contrast to a mutex, a counting semaphore will stop a thread from accessing a part of the code if and only if n other threads are concurrently accessing the code block.

When is this useful? Suppose there is a buffer of n things to consume, and new threads must wait only when there is nothing in the buffer. In this case:

• Some number of “producer” threads can continually produce new things and place them in the buffer, and then call V, which increments the semaphore s to signal that one more thing is available for consumption.
• Concurrently, a number of “consumer” threads can continually call P, which will degrement semaphore s, indicating that a thing in the buffer is being consumed. If there are 0 things, then the consumer threads will block until the producer threads produce something.

This is called the “consumer-producer” model.

How is the semaphore implemented?

Since the mutex is implemented using a semaphore, the question is now how the semaphore is implemented itself. They’re not a part of the pthreads standard, but they are a part of the POSIX standard, so the implementation is in semaphore.h:

#include <semaphore.h>
int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s);  // P(s)
int sem_post(sem_t *s);  // V(s)

I’ve annotated the source with what I think is going on here. Just to see what’s up in the implementation.

int
sem_post (sem_t * sem)
{
  int result = 0;
  sem_t s = *sem;

  // check for invalid semaphore state. EINVAL indicates that argument `sem`
  // is not a valid semaphore.
  if (s == NULL)
    {
      result = EINVAL;
    }
  // Attempt to lock on this semaphore. This lets us check do things like
  // validation checks on the semaphore, like the fact that it's not < 0 or
  // greater than the maximum number.
  else if ((result = pthread_mutex_lock (&s->lock)) == 0)
    {
      // Unlock and emit error code if semaphore is invalid.
      if (*sem == NULL)
        {
          (void) pthread_mutex_unlock (&s->lock);
          result = EINVAL;
          return -1;
        }

      // Check that semaphore is less than the maximum value
      if (s->value < SEM_VALUE_MAX)
    {
// This preprocessor directive appears to control whether it's a mutex or
// not? How odd. Note though that a binary semaphore is not always a mutex.
#if defined(NEED_SEM)
          // Increment the semaphore, or emit the error if that fails.
      if (++s->value <= 0
          && !SetEvent(s->sem))
        {
          s->value--;
          result = EINVAL;
        }
#else
      // "Release" a binary semaphore, or emit error if that fails. I
      // think this corresponds to releasing a mutex.
      if (++s->value <= 0
          && !ReleaseSemaphore (s->sem, 1, NULL))
        {
          s->value--;
          result = EINVAL;
        }
#endif /* NEED_SEM */
    }
      // Emit error if semaphore is not in correct range (i.e., [0,n])
      else
    {
      result = ERANGE;
    }

      (void) pthread_mutex_unlock (&s->lock);
    }

  // Check results; emit error if necessary
  if (result != 0)
    {
      errno = result;
      return -1;
    }

  return 0;

}