Lock-free data structures: the queue
published: Sun, 30-Oct-2005 | updated: Sat, 18-Apr-2009
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 class
Node<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), with Enqueue()
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 tail to 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.
