A lock-free priority queue in C#

Question

I have been searching lately for information on how to construct a lock-free priority queue in C#. I have yet to even find an implementation in any language, or a decent paper on the matter. I have found several papers which appear to be copies or at least referencing one particular paper which is not actually a paper on lock free priority queues, despite its name; it is in fact a paper on a priority queue which uses fine grained locks.

The responses I have been receiving from elsewhere include "use a single thread" and "you do not need it to be lock free" and "it is impossible". All three of these responses are incorrect.

If someone has some information on this, I would greatly appreciate it.

Answer 1

Generally, it's a bad idea to write this kind of code yourself.

However, if you really want to write this kind of code, I say take a page from Eric Lippert's book (or blog, as it were) (web archive link), where basically, you would implement the queue but instead of having all the functions that make modifications on the queue modify the instance you call the method on, the methods return completely new instances of the queue.

This is semantically similar to the pattern that System.String uses to maintain immutability; all operations return a new System.String, the original is not modified.

The result of this is that you are forced to reassign the reference returned on every call. Because the assignments of references are atomic operations, there is no concern about thread-safety; you are guaranteed that the reads/writes will be atomic.

However, this will result in a last-in-wins situation; it's possible that multiple modifications are being made to the queue, but only the last assignment will hold, losing the other insertions into the queue.

This might be acceptable; if not, you have to use synchronization around the assignment and reading of the reference. You will still have a lock-free-priority queue, but if you have concerns about thread-safety and maintaining the integrity of the operations, you have done nothing but move the concern about synchronization outside of the data structure (which is almost all cases, is a good thing, as it gives you fine-grained explicit control).

Answer 2

The Art of Multiprocessor Programming. Look at Chapter 15 - Priority Queues. Book is in Java, but can be easily translated to C# since they both have GC (which is important for most implementations in the book).