LOCK-FREE DATA STRUCTURES: THE QUEUE
[Click to print this article]
Notes: Several people have emailed me to say this code suffers from the ABA problem. It doesn't, but only because it's written in C# and implictly uses the .NET garbage collector. If you just, quote, convert it to C++ or Delphi, unquote, it will not work and will suffer from some form of ABA. See here for details.
------
Last time we looked at implementing a lock-free stack, a stack that can be used in multithreaded applications but that doesn't need locks (such as mutexes) in order to provide thread-safe operation. This gave us an appreciation for one of the basics of lock-free programming: the Compare-And-Swap (CAS) function. This time we'll look at how to implement a queue, another very basic data structure, but this time things start getting difficult.
One reason for the new difficulty is that queues have two endpoints at which things happen. You enqueue items at the tail of the queue and you dequeue them at the head of the queue (as usual when talking about queues you should imagine a supermarket checkout line).
Again we're going to use a linked list approach to writing the structure, the reason being that using an array-like structure is fraught with problems when you have to grow the structure and you aren't using locks. So, a linked list, then.
As before, I'll write a single-threaded implementation first. This will give us some concrete code to look at in order to understand the ramifications of making it lock-free.
internal class SingleLinkNode<T> {
public SingleLinkNode<T> Next;
public T Item;
}
public class LockFreeQueue<T> {
SingleLinkNode<T> head;
SingleLinkNode<T> tail;
public LockFreeQueue() {
head = new SingleLinkNode<T>();
tail = head;
}
public void Enqueue(T item) {
SingleLinkNode<T> node = new SingleLinkNode<T>();
node.Item = item;
tail.Next = node;
tail = node;
}
public T Dequeue() {
if (head == tail) {
return default(T);
}
SingleLinkNode<T> oldHead = head;
T result = oldHead.Next.Item;
head = oldHead.Next;
return result;
}
}
(For those that have already readmy previous installment, I've extracted out the private nested classNode<T> from SimpleStack<T> into its own internal class, as shown here. Remember we can't make the Next and Item members properties: the Next member, in particular, must be a field so that we can use it with the CAS method. Note that once this series on writing lock-free data structures is done, I'll release a zip file containing all the source code that you can download.)
If you look at Dequeue(), you'll see that it's pretty much like Pop() from the stack implementation. In essence all we need to do is to set the head field from within a typical CAS loop. But, before we make that change, let's look at Enqueue(), so that we can appreciate the problems we now face.
Whereas we only have to change one shared reference with Dequeue() (the head field), withEnqueue() our problem is doubled. We have to change two shared references: the tail's Next field (to point to our new node) and then tail itself (again to point to our new node). CAS only allows us to change one item at a time, and if we're not careful another thread might jump in between the two changes and completely wreck our carefully laid plans as well as trash our nice linked list.
The trick we shall use is to add the new node with CAS, but allow the tail reference to lag behind. That does cause a nasty problem in that it's at the tail where we add new nodes. So what we do is to allow any thread enqueuing a node to advance the tail reference. In other words, we'll make sure that the linked list is always fully valid, and then worry about where the tail reference points.
public static class SyncMethods {
public static bool CAS<T>(ref T location, T comparand, T newValue) where T : class {
return
(object) comparand ==
(object) Interlocked.CompareExchange<T>(ref location, newValue, comparand);
}
}
public class LockFreeQueue<T> {
...
public void Enqueue(T item) {
SingleLinkNode<T> oldTail = null;
SingleLinkNode<T> oldNext = null;
// create and initialize the new node
SingleLinkNode<T> node = new SingleLinkNode<T>();
node.Item = item;
// loop until we have managed to update the tail's Next link
// to point to our new node
bool UpdatedNewLink = false;
while (!UpdatedNewLink) {
// make local copies of the tail and its Next link, but in
// getting the latter use the local copy of the tail since
// another thread may have changed the value of tail
oldTail = tail;
oldNext = oldTail.Next;
// providing that the tail field has not changed...
if (tail == oldTail) {
// ...and its Next field is null
if (oldNext == null) {
// ...try to update the tail's Next field
UpdatedNewLink = SyncMethods.CAS<SingleLinkNode<T>>(ref tail.Next, null, node);
}
// if the tail's Next field was non-null, another thread
// is in the middle of enqueuing a new node, so try and
// advance the tail to point to its Next node
else {
SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldTail, oldNext);
}
}
}
// try and update the tail field to point to our node; don't
// worry if we can't, another thread will update it for us on
// the next call to Enqueue()
SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldTail, node);
}
}
Follow on with the code. First thing we do is as before: create and initialize our new node to contain the item we want to enqueue. Now we enter a loop that will terminate once we have successfully updated the tail's Next field to point to our new node.
First thing we do in the loop is to grab a local copy of tail, and then a local copy of tail's Next field. We should not use the tail field itself to get the value of Next, but the copy we just made. Why? Because another thread may have already changed tail in between both reads.
Now, providing that the current value of tail is equal to our copy (that is, the tail hasn't changed yet!), and the copied next reference is null, try and set the real tail.Next to our new node. We only succeed at making the change if tail.Next is still null. If we do succeed, we've managed to properly link our node to the end of the linked list, but note that the tail field still points to our new parent. Set a flag so that we can exit from the loop.
Now, if the copied next reference wasn't null, we're "interfering" with another thread (or many others) that is also enqueuing a new item at the same time as ours. It has already managed to link its new node properly, but tail is lagging behind. We help out by trying to advance tail to point to its Next node. This may fail, since another thread may do it first, but we don't worry about it.
Once we manage to link our new node, we exit the loop and finally try to advance the tail to point to our new node. This may fail since another thread may have already changed the tail value, but again we don't worry about it since someone else is helping us out.
Notice that one of the effects of the loop is to continually advance the tail until it reaches the final node in the linked list. So, in reality it doesn't matter which thread advances tail, so long as all threads take the opportunity to do so. Also notice that the only time a thread exits the loop is once it has managed to link its new node onto the end of the linked list to replace the null reference there.
There's another, more subtle, conclusion to be drawn from the loop. The value of tail is never more than one node away from the actual last node in the list. Why is this? The reason is that there is no code that tries to find the final node in the list by walking the list. In other words, if we find the last node in the list (the one with a null Next reference) then some thread (maybe ours) will have already advanced tailto point to it. If we update this null Next reference then, before anyone else can add another node, someone is going to have to advance the tail reference to point to this new node. So, tail is either pointing to the real last node, or the previous last node.
This fact means that, for example, we can't Dequeue() nodes so quickly that tail is left hanging out there. However, we must be careful when we do dequeue the last node just in case tail hasn't been advanced after the last enqueue. So Dequeue() is not going to be as simple as Pop() was in the stack version.
public class LockFreeQueue<T> {
...
public T Dequeue() {
T result = default(T);
// loop until we manage to advance the head, removing
// a node (if there are no nodes to dequeue, we'll exit
// the method instead)
bool HaveAdvancedHead = false;
while (!HaveAdvancedHead) {
// make local copies of the head, the tail, and the head's Next
// reference
SingleLinkNode<T> oldHead = head;
SingleLinkNode<T> oldTail = tail;
SingleLinkNode<T> oldHeadNext = oldHead.Next;
// providing that the head field has not changed...
if (oldHead == head) {
// ...and it is equal to the tail field
if (oldHead == oldTail) {
// ...and the head's Next field is null
if (oldHeadNext == null) {
// ...then there is nothing to dequeue
return default(T);
}
// if the head's Next field is non-null and head was equal to the tail
// then we have a lagging tail: try and update it
SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldTail, oldHeadNext);
}
// otherwise the head and tail fields are different
else {
// grab the item to dequeue, and then try to advance the head reference
result = oldHeadNext.Item;
HaveAdvancedHead =
SyncMethods.CAS<SingleLinkNode<T>>(ref head, oldHead, oldHeadNext);
}
}
}
return result;
}
}
From the comments you can see the extra work that Dequeue() has to do. First we enter a loop that we'll exit either because there are no items to dequeue (note the return statement in the middle of the loop) or because we have dequeued an item and have also managed to advance the head reference.
In the loop, we take copies of the head and tail references as well as the head's Next reference. Again to get the latter we use our copy of head (since another thread may have already changed the shared variables).
If the head reference has not changed since we took the copy, we do some work (if it has changed we just go round the loop again and start over). First we check to see if the head and tail references are the same, and, if so, whether the head's Next reference is null. If it is, we just return the type's default value to indicate that there is nothing to dequeue.
If the head's Next reference is non-null, it indicates that the tail reference is lagging, so we try and advance it (again it doesn't matter if we can't, some other thread will cooperatively update it anyway). After that, we just go round the loop and try again to dequeue something.
Now, if the head and tail references are different, it indicates that there is something to dequeue. Grab the item, and then try to advance the head reference to its own Next reference. If it succeeds, we have successfully dequeued an item; if not, we just go round the loop and try again.
Having explained the way it works there is still, nevertheless, a subtle issue to resolve here (and to be honest, it was there with the stack, but I chose to ignore it). Suppose, for some unknown reason, the operating system puts the executing thread to sleep just before it sets the result variable. Other threads are still running, enqueuing and dequeuing like crazy. What happens when our thread wakes up and then reads the Item field of its oldHeadNext variable? The node oldHeadNext references may no longer be part of the linked list at all. Gone, dequeued by someone else.
As it happens, it doesn't much matter in .NET because the garbage collector will not have collected the node (it is still being referenced by this thread after all). So reading Item will still be valid. However, if you were using a non-garbage-collected environment (obviously not with C#), you could have significant issues: another thread may have disposed of this node ages ago. You'll be referencing memory that was no longer yours, etc. Big time problems.
Next time, we'll discuss this issue and the problem whereby we've still got an implicit locking structure by the fact that we're using the global memory manager, so our lock-free queue is still not quite lock-free.
Here's a bunch of links for you to tie all this lock-free stuff up.
