I’ve been thinking about a lockfree queue lately. Well, on and off for a while now, but even moreso lately. Most lockfree queues (ie Michael and Scott’s, etc) tend to be built from nodes, link-list style. I’ve been thinking about going that way, but I have another idea stuck in my head, and it just won’t seem to leave. So I think I better write it down and see where it ends up. Possibly a hybrid of some kind – we’ll see. But to get there, I think we’d better start at the beginning, and build up from there, one step at a time.
To be overly simple, lets start with
- a single-threaded queue,
- built upon a fixed length array.
- Of ints.
A Producer will add items to the queue (‘enqueue’ items), by writing an item into the array, and keep track of where the next item is to be added with a tail variable, which points to the slot in the array one-past the last item added. So
enqueue:
- adds an item to the end of the queue by copying the item to an array slot at tail
- updates (increments) tail
Similarly a Consumer removes items from the queue (‘dequeue’). Note that it does this at the front of the array, where the first items were added, so that the queue is, well, a queue. ie FIFO – first in, first out. And after reading the first item, it somehow needs to mark that the second item will now be the next item removed. We do this with a head variable, which marches forward in the array marking which entry is at the front of the queue.
dequeue:
- removes the first item from front of the queue by copying it from the array slot at head
- increments head to make the next item the ‘new’ first item
So that’s pretty simple – I want to keep it simple, so that we don’t miss anything. But it is, obviously, too simple. We already have questions:
- how long is this array anyhow? Definitely not infinite, so what do we do when tail == end of array?
- what happens when the queue is empty (ie head meets tail) – does the Consumer wait? return false? something else? What about when full?
- more importantly, how can we tell that the queue is empty/full!?
So, let’s tackle a few of those:
For #1, once we get to the end of the array, let’s loop back around to the beginning. The array then becomes what is known as a circular buffer. As soon as we do this, note that we have a new problem: not only can head reach tail, but tail can loop around and meet up with head! This is, in fact, part of #3 – when tail reaches head, the queue is full.
2 – what do we do on empty and full. To be simple (for now) let’s just return false. (ie enqueue returns false when the queue is full, dequeue returns false when the queue is empty). Alternatively, in threaded programming for example, you often want to wait until the full/empty condition changes; but it is easier for now to just return false.
3 – Empty/Full? Well, for empty, we could check head == tail. But, since this is a circular buffer, when tail comes around to head, the buffer is full, so doesn’t head == tail mean full as well as empty? There are a few possible solutions:
- use a flag – that’s simple! Call it, say, ‘
full‘. It is interesting to note that only the Producer will ever setfull, and only the Consumer will ever clear it. - Equivalently to #1, we could ‘hide’ the flag inside
headand/ortail(ie makeheadnegative (but keep its absolute value) whenever the queue is full). This saves a byte or probably sizeof(int) in our Queue, although adds some complications. (When is complexity for efficiency allowed?***) - Change the full condition to be
tail == head - 1. Which means we will end up leaving one entry empty. Note that this also costs us sizeof(int) – but only when our queue really is full. ie if our queue never gets near full, then we were wasting that space in the array anyhow.
Since this is a ‘overly simple’ queue, we should use #1. But my thread-foreshadowing senses tell me we would be better to use #3. Even without knowing the eventual outcome of the code – and as I write this, I don’t – we can use a few important lessons about threading to make our choice:
- Every additional variable multiplies the number of possible states for the system, and states + threading == bugs. Consider what was once simple:
if (A) // only when A... if (B) // ...and B do_something();This becomes a bit of a nightmare in threaded code (particularly outside of locks) when you must remember that between the first
ifand the secondif, A may have become false! So this is a point against using full-method #1 - Having multiple threads ‘own’ or modify the same variable is… well not bad, but dangerous. Up until now, only producers modified
tail, and consumers modifiedhead. Hiding the flag inheadortailmeans both consumers and producers will be ‘owning’ the variable. From experience, this is bad/dangerous. Not always avoidable (our threads are sharing a queue and data for a reason, we must have some sharing) but avoid it when we can. This is a point against full-method #2.
So that leaves #3 – always leave the entry before head empty, and when tail gets to just-before-head we will say the queue is full.
How about some actual code:
class Queue { enum { size = 256 }; int array[size]; int head; int tail; public: Queue() : head(0), tail(0) { } bool enqueue(int item) { // when tail reaches the end of the array, // it loops around back to the start of the array // so the queue is full whenever tail catches up to head. // To avoid confusion with 'empty' we say it is full when // we are one-away from head. if (tail == head - 1) // full? return false; array[tail] = item; tail = (tail + 1) % size; // increment, loop if at end return true; } bool dequeue(int & item) { if (head == tail) // empty? return false; item = array[head]; head = (head + 1) % size; // increment, loop if at end return true; } };
Something to note, about the check for full: if (tail == head - 1) – there is a bug! Already! See how complexity throws a wrench in things! In this case it is more to do with the complexity of being a circular buffer, not just the way we are checking for full.
The bug is fixed with if ((tail + 1) % size == head). Think about it.
Now, what about threading – what if enqueue is being called by the Producer thread while dequeue is being called by the Consumer thread? Let’s tackle that next.
To be continued…