At The Bakery

After the topical excitement of the last couple of posts, let’s look at an all-time great – Leslie Lamport’s Bakery Algorithm (and of course this is still topical; Lamport is the most recent winner of the Turing Award).

The problem is mutual exclusion without mutual exclusion primitives. Usually, it’s described in the context of a shared memory system (and that is what we will implement here), but will work equally well in a message-passing system with only local state (each thread or process only needs to write to its own part of the store).

For further details, and Lamport’s later thoughts see http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#bakery: “For a couple of years after my discovery of the bakery algorithm, everything I learned about concurrency came from studying it.” – and since Lamport understands more about concurrency than just about anyone on the planet, it’s maybe worth spending some time looking at it ourselves.

I’m not going to attempt to prove the algorithm correct, I’ll leave that to Lamport, but the crucial idea seems to me to be that a thread reading a particular value from another thread is a synchronization signal from that thread – here, reading a false value for the entering variable is a signal that the other thread isn’t in the process of deciding on it’s own number, therefore it is safe for the reading process to proceed.

Implementing on a real multiprocessor system, we find that use of memory barriers or synchronization primitives is essential – the algorithm requires that reads and writes are serialized in the sense that once a value is written, other processes won’t see an earlier value (or earlier values of other variables). This doesn’t conflict with what Lamport says about not requiring low-level atomicity – we can allow reads and writes to happen simultaneously, with the possibility of a read returning a bogus value – and in fact we can simulate this in the program by writing a random value just before a process selects its real ticket number, but once a write has completed, all processes should see the new value.

Another essential feature is the volatile flag – as many have pointed out, this isn’t enough by itself for correct thread synchronization, but for shared memory systems, prevents the compiler from making invalid assumptions about consistency of reads from shared variables.

A final point – correctness requires that ticket numbers can increase without bound, this is hard to arrange in practice, so we just assert if they grow too large (this rarely happens in reality, unless we get carried away with our randomization).

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>

// Compile with: g++ -Wall -O3 bakery.cpp -pthread -o bakery

static const int NTHREADS = 4;

// Some features to play with
//#define NCHECK     // Disable crucial check
//#define NSYNC      // Disable memory barrier
//#define NVOLATILE  // Disable volatile

#if defined NVOLATILE
#define VOLATILE
#else
#define VOLATILE volatile
#endif

VOLATILE bool entering[NTHREADS];
VOLATILE unsigned number[NTHREADS];
VOLATILE int count = 0;
VOLATILE int total = 0;

unsigned getmax(int n)
{
  unsigned max = 0;
  for (int i = 0; i < n; i++) {
    if (number[i] > max) max = number[i];
  }
  return max;
}

bool check(int i, int j)
{
  return number[j] < number[i] || 
         (number[j] == number[i] && j < i);
}

inline void synchronize()
{
#if !defined NSYNC
    // gcc builtin full memory barrier
  __sync_synchronize();
#endif
}

void lock(int i) {
  entering[i] = true;
  synchronize();
  // Simulate non-atomic write
  number[i] = rand();
  synchronize();
  number[i] = 1 + getmax(NTHREADS);
  assert(number[i] > 0);
  entering[i] = false;
  synchronize();
  for (int j = 0; j < NTHREADS; j++) {
    // Wait until thread j receives its number:
#if !defined NCHECK
    while (entering[j]) { /* nothing */ }
#endif
    // At this point, we have read a false value for 
    // "entering[j]", therefore any number picked by j
    // later will takes our choice into account, any value
    // chosen earlier (and so might be less than ours) 
    // will be visible to us in the following test.

    // Wait until all threads with smaller numbers or with 
    // the same number, but with higher priority, finish 
    // their work:
    while ((number[j] != 0) && check(i,j)) { /* nothing */ }
  }
}

void unlock(int i)
{
  number[i] = 0;
}

void *threadfun(void *arg) 
{
  int i = *(int*)(arg);
  while (true) {
    lock(i);
    total++;
    if (total % 1000000 == 0) fprintf(stderr,"%c", 'a'+i);
    assert(count==0); // Check we have exclusive access
    count++;
    // It's not clear that these synchs are unnecessary,
    // but nothing seems to break if I remove them.
    //synchronize();
    count--;
    //synchronize();
    unlock(i);
    // non-critical section...
  }
  return NULL;
}

int main()
{
  pthread_t t[NTHREADS];
  int n[NTHREADS];
  for (int i = 0; i < NTHREADS; i++) {
    n[i] = i;
    pthread_create(&t[i], NULL, threadfun, (void*)&n[i]);
  }
  for (int i = 0; i < NTHREADS; i++) {
    pthread_join(t[i], NULL);
  }
}

---