Lock-free data structures: the limited priority queue
published: Mon, 7-Nov-2005 | updated: Sat, 18-Apr-2009
Notes: the implementation of the free list used in the code in this priority queue is broken. The reason is that nodes used by the free list will tend to suffer from the ABA problem. DO NOT USE THIS FREE LIST CODE. The code you can download does not use free lists at all.
------
Last time in this series on building lock-free data structures in C# 2.0 we designed and implemented a lock-free queue, a FIFO structure that doesn't use locking to ensure correct thread safety. In doing so we also built a lock-free free list to ensure that we wouldn't block on the memory manager when allocating nodes. This time we'll tie it all up by creating a lock-free priority queue, one for a limited number of priority values, based on the code I wrote earlier.
Actually, I'm pretty sure, knowing the intelligence of my readers, that many of you have already done it. After all, it's pretty easy since the limited priority queue I implemented before uses an array of queues internally. So all that needs to be done is to replace these queues with lock-free queues instead.
Actually, not quite. The original implementation of
Dequeue() used the Count property of the
Queue class to determine whether anything was available
to be dequeued. We don't have such a property on the lock-free queue,
so we have to try and dequeue an item and see if we get back the
default value for the instantiating type.
This gave me pause when I first wrote it. The C# language
documentation defines the default keyword in terms of
being able to set a local variable or a result value, not in terms of
comparisons.
Undeterred, I wrote this:
public T Dequeue() {
foreach (LockFreeQueue<T> q in queueList) {
T result = q.Dequeue();
if (!result.Equals(default(T)))
return result;
}
return default(T);
}
So, to paraphrase in English, for every queue in the list, dequeue from the current queue, if the result is not equal to the default for the type, return it. If we reach the end of the loop, return the default for the type. Seems simple enough, no?
Except if T is a reference type, result
would be null if there was nothing to dequeue. So I'd be
calling the Equals() method on null. Can you
spell NullReferenceException? The answer is to use the
static object.Equals() method instead. Unfortunately, I'm
not happy with that one either, since calling the method would cause
boxing to occur for non-reference types.
As I see it, I have two options, accept this situation, or change the
signature of LockFreeQueue.Dequeue() so that it returned
a boolean indicating whether something was dequeued or not, and an
out value for the item itself. In fact I did something
slightly different and added another Dequeue() method
instead to LockFreeQueue so you can decide to use either
to dequeue an item, the easy one, or the slightly more awkward, but
more complete, version.
public class LockFreeQueue<T> {
...
public bool Dequeue(out T item) {
item = default(T);
SingleLinkNode<T> oldHead = null;
// 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
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 false;
}
// 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 try to advance the head reference
item = oldHeadNext.Item;
HaveAdvancedHead =
SyncMethods.CAS<SingleLinkNode<T>>(ref head, oldHead, oldHeadNext);
}
}
}
freeList.FreeNode(oldHead);
return true;
}
public T Dequeue() {
T result;
Dequeue(out result);
return result;
}
}
Finally, here's the code for the lock-free priority queue, one that is designed for a priority type that has a very limited number of possible values.
public class LimitedPriorityQueue<T,P> {
private IPriorityConverter<P> converter;
private LockFreeQueue<T>[] queueList;
public LimitedPriorityQueue(IPriorityConverter<P> converter) {
this.converter = converter;
this.queueList = new LockFreeQueue<T>[converter.PriorityCount];
for (int i = 0; i < queueList.Length; i++) {
queueList[i] = new LockFreeQueue<T>();
}
}
public void Enqueue(T item, P priority) {
this.queueList[converter.Convert(priority)].Enqueue(item);
}
public bool Dequeue(out T item) {
foreach (LockFreeQueue<T> q in queueList) {
if (q.Dequeue(out item)) {
return true;
}
}
item = default(T);
return false;
}
public T Dequeue() {
T result;
Dequeue(out result);
return result;
}
}
(Note: I also added the same kind of code to both the stack —
there are now two Pop() methods — and to the
priority queue — there are now two Dequeue()
methods.)
By the way, why is there no Count property for
these lock-free data structures? Why do we have to rely on trying to
pop or dequeue an item to see if there are no items present?
Consider the case that there were a Count property and
we'd intelligently written it so that we incremented and decremented
it in a lock-free manner (we are, after all, gods of lock-free code
now). We’d automatically try and write this:
if (myStack.Count != 0) {
myItem = myStack.Pop();
}
The issue, as you can imagine, is that suppose that Count
were non-zero for the if condition, what's to guarantee that no other
thread would not pop everything before we executed our call to
Pop()? We'd have the situation that Count
told us that there was something to pop, but we couldn't pop anything.
The issue here is that there is no hard link between retrieving the
value of Count, ensuring that it is greater than zero,
and the subsequent call to Pop(). Each of these
executable conditions are interruptable by other threads doing the
same thing. We can't make them atomic, for then we'd have to use a
lock (and that's not allowed).
So we can't have a Count property that's meaningful in a
multithreaded context. So we don't bother.
And with that, we come to an end of this mini-series on writing some simple lock-free data structures in C# for multithreaded applications. There were five articles in the series:
- Writing a limited priority queue
- Writing a lock-free stack
- Writing a lock-free queue
- Writing a lock-free free list (included changes to the stack and queue)
- Writing a lock-free limited priority queue (included changes to the stack and queue)
What would you use any of these nifty data structures for? Well, how's this for an example. You want to log various events from your threads: informational events, exception events, warning events and the like. At present you've implemented it as a lockable call to a logging library where each thread locks the logger, logs the event, and then unlocks the logger. (Or maybe this locking occurs under the hood.)
Better would be to launch a thread that just logs events. Get it to dequeue events it should log from a lock-free queue, and then all your other threads should merely enqueue these events when they need to log something. You've suddenly completely decoupled your logging library from all of your other threads, both in a design and in a run-time locking sense.
Maybe you should be logging critical events before informational events just in case the system might try and shut down. Simple: use a lock-free priority queue.
I'm sure you can come up with other examples. Good luck!
Here's a bunch of links for you to tie all this lock-free stuff up.
