Hey there! I see you're not using JavaScript. Just FYI, I use MathJax to display things that deserve to look like math.

Alex

Computer "scientist"

Alex Clemmer is a computer programmer. Other programmers love Alex, excitedly describing him as "employed here" and "the boss's son".

Alex is also a Hacker School alum. Surely they do not at all regret admitting him!

Day 265: Semaphores and mutexes. Mutices. Muticii.

February 23, 2014

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:

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:

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?

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:

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:

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;

}



comments powered by Disqus