An Almost-Universal Simple Synchronization Scheme

In most cases by far, threads can communicate with eachother by passing eachother small messages, using a simple producer-consumer scheme. When such a model is possible, synchronizing threads (which really is all about communication) is a very simple affair that, if implemented correctly, cannot deadlock, is very efficient and is almost universally applicable.

Ingredients:

• a [circular] queue that
  • allows for multiple producers
  • allows for at least one consumer to access the queue on concurrence with the producer(s)
  • is lock-free
  • need not be wait-free
  • has each of the following accessors:

    • push(T)

      copies an instance of T into the queue, at the tail, atomically

    • pop(): T

      retrieves the head of the queue and pops it from the queue, atomically

    • flush()

      empties the queue

    • empty(): bool

      returns true if the queue is empty, false otherwise

• a light-weight semaphore (event in Window-eze) that
  • has each of the following accessors:
    • signal()
      signals the semaphore, liberating one thread waiting on it. If no thread is waiting on the semaphore, it remains in a signaled state until wait is called (which won’t wait, but will return the semaphore to a non-signaled state and return immediately)
    • wait()
      waits until the semaphore is in a signaled state, then returns it to a non-signaled state when liberating the thread
• a message type that:
  • has value-type semantics
• a consumer thread
• one or more producer threads

The consumer thread

given sem_, the semaphore, and queue_, the queue, both of which are as described above, and Message, the message type, the pseudo-code for the consumer thread looks like this:

1
2
3
4
5
6
7
8
9
10
11

while (!done_ /* a boolean member that will be set to true when  */)
{
    if (!queue_.empty())
    {
        Message message(queue_.pop());
        /* do something with the message, not locking on anything else */
    }
    else
    { /* spurious wake-up */ }
    sem_.wait();
}

The producer thread

The producer thread can do anything at all, but synchronizes with the consumer thread by passing it a message, like this:

1
2
3

Message message(...);
queue_.push(message);
sem_.signal();

Of course, the queue and semaphore could be wrapped into a single object.

Notes

I have found that this method is practically universal and can be used by novices as well as by experts. The rule that the consumer thread shouldn’t wait on anything other than the semaphore is one which I impose especially on novices. The reason for this is that if it is rigorously applied, deadlocks are, for all intents and purposes, impossible. Granted, this may not always be the most efficient way of doing things, but it very often is, and it is definitely safe – which counts for something.