A lock-free priority queue in C#
Asked Answered
P

2

9

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.

Pea answered 15/5, 2011 at 1:35 Comment(7)
How do you know they are all wrong?Illaffected
@Illaffected Using a single thread defeats the purpose of this data structure, if I did not need it to be lock free then I would not be asking this question, and it is not impossible because it has been done before.Pea
What are your requirements that a priority queue with some locking wouldn't be good enough?Ansate
@Ansate In excess of 10,000 concurrent operations happening per second across more than 128 processing units. Lock contention inside this message queue alone becomes more time consuming than the main execution loop of the message handler and I have several message queues for this same loop. All of the message queues and handlers need quality of service capabilities as well, and that is why I need a priority queue.Pea
fine grained locks is what you are looking for, i think 100% lock free is impossible.Haematocele
@Snoopy Fortunately I have seen an implementation of a lock free priority queue. Fine grained locks would only be viable in a binary heap acting as a priority queue and locking each of the children you wish to access. I have made such an implementation and it is far less than ideal, and thus I am after something entirely lock free.Pea
Maybe you have a small set of priorities for queue items?Ie
L
5

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).

Lulalulea answered 15/5, 2011 at 1:44 Comment(20)
Could you elaborate on implementation specifics regarding the lock free priority queue? I do not quite follow how this would work in practice, but I understand the theory behind why it might be applicable.Pea
@JNZ: Let's say the PriorityQueue has a Push method. Instead of having a void return type, it would return a new instance of the PriorityQueue; the instance returned would have the items in the original queue, plus the new item pushed onto it. This works without locks because it involves a read operation on the original, and the write operation on the new one occurs in the constructor, which will always be thread-safe. All mutable operations would return a new instance. You would just have to make sure that you keep track of the new reference.Lulalulea
@Lulalulea Alright so let me see if I have this right then. I follow how the Pop method works. A Push method would take in an item and return a new PriorityQueue which has the item in there. The immutable PriorityQueue singleton would update its reference with the one that was just returned, in an atomic operation. Is that how it should be?Pea
What if two or more threads simultaneously do Pop? Wouldn't they all pop the same single item?Menarche
@JNZ: Yep, that's right. Remember, the Pop method would not actually remove anything, but return a new PriorityQueue with the item removed. The link to Eric Lippert's blog show how this is done for a number of data structures.Lulalulea
@shsmith: Yes, but the point is you work with the references of the PriorityQueue that is returned, letting the original one go; assignments of references are atomic operations.Lulalulea
@Lulalulea I will test an implementation of what you have suggested and follow Eric Lippert's post as a reference for the core concept. I will leave this question open until I can test this out and see how it fairs. It looks good so far, though. I do appreciate the assistance.Pea
@Lulalulea Alright so after implementing this and getting it functional, we have a problem. The priority part of the PriorityQueue is difficult to implement. It seems that insertion of a priority higher than anything currently in the queue is the hard part to do in a thread safe manner, without locks of course. The queue works great, but I cannot see how to get priorities working in this way.Pea
Someone in ##csharp on irc.freenode.net pointed out the answer to my previous comment here. It appears that the way to get around this is to clean up the extrenally obvious immutability and use compare and swap to exchange the updated queue with the most recent queue. Thanks you two. I think we can call this one the accepted answer at this point.Pea
This implementation is currently what I am looking at with my existing implementation, to make it a bit cleaner as far as the usage goes.Pea
This method requires exclusive access between the time a thread first starts to read the queue and the time when that thread saves the reference to the new replacement queue. If a second thread also reads the queue and makes a different alteration, one of the two alterations will be lost. Think of one thread continuously pushing and a different thread continuously popping. Although this method guarantees each copy of the queue is incorrupt it does not guarantee that each push has one and only one corresponding pop. It appears you still need a lock. Or am I missing something?Menarche
@shsmith It creates an unavoidable race condition, corruption is all you need to prevent when considering it to be lock free and thread safe; and of course avoid lock contention. When you finally update the state, it should be done in a single atomic operation basically. So, that's the problem we've got here. I actually have not been able to get this implementation done up as a priority queue just yet, so it is not quite solved.Pea
@shsmith: Agreed that if you don't want a last-in-wins situation, you have to lock access to the reference; however, that isn't what the question is really asking for. It's asking how to implement a priority queue with no locks. If @JNZ does not want locks at all, then he has to accept a last-in-wins situation (there's no way to do this without a lock, this solution just moves the responsibility to the caller, not as an internal implementation detail; being immutable automatically translates to thread-safe).Lulalulea
Interesting discussion guys. If you are interested in techniques for making an immutable persistent heap, which is the basic structure that underlies a priority queue, Chris Okasaki's thesis (which is available online) and his book (which is available from Amazon) both have examples of such a data structure. Translating it from the terse functional-style language in which its written can be a bit of a challenge if you're not used to it, but all the ideas you need are there.Holograph
@Lulalulea Ah, I did write my comment awkwardly there. Currently I am satisfied with a last-in-wins situation. However, making this a priority queue, you cannot offer that and remove the potential for state corruption with this design as far as I can see. Currently we have a problem if in A -> B -> D, C is inserted concurrently with a TryDequeue of A and B. C would never be present in the queue and thus we have a problem. Do you happen to have a solution for this part of the implementation?Pea
@JNZ: It's not state corruption, technically, that's what last-in-wins means; there are multiple operations being performed on one resource, the one that finishes last wins. If you are looking for more of an ACID-like transaction/structure, you will have to use a lock somewhere. With the suggestion of an immutable PriorityQueue, the responsibility to place a lock around the assignment/reassignment of the reference to the queue falls on the caller, not the callee; this is a good thing, it allows client code to be in control of synchronization for larger operations.Lulalulea
@JNZ: As for solving the priority insertion issue, it's easy, as you copy over the new items from one PriorityQueue to another, you can simply check to see where the new item in the queue goes and insert it at the appropriate point of the sequence when returning the new PriorityQueue.Lulalulea
Here is an implementation which is a compromise between some of the points we have made here. It appears that it will not cause a problem with the race condition, from what I have examined and from what others have commented on IRC. It looks fairly solid, and testing has not resulted in any problems over the course of a few hundred million operations with randomized waiting and thread access. Comments on this implementation are welcome.Pea
@Lulalulea I saw that just as I noticed your post. I feel like your discussion has uncovered many ways to implement this solution, and it has shown me a different way to look at a few of the other problems I have been encountering. I appreciate your assistance and the great discussion and have marked your solution as the accepted one. Thank you again.Pea
A naive "solution" to last-in-wins is to retry: get the old heap, modify, do test-and-set(new, old, old) and retry in a cycle until it works (or timeout or some other limit is reached). Does not guarantee fairness or no-starvation, though.Salutary
G
3

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).

Gussi answered 15/5, 2011 at 1:42 Comment(4)
That example utilizes a test and set nstruction in its implementation, a feature which is unavailable in C# without specific additions to the execution engine (.NET, Mono, ...); .NET does not offer such a feature unfortunately.Pea
@JNZ isn't Interlocked.CompareExchange what you're looking for?Retainer
@Retainer No, because that's a compare and swap and not a test and set or test, test, and set. They are fundamentally different and cannot compose eachother unfortunately; we need execution level control here.Pea
if test and set means... (if location == 0 then location = 1, return true else return false) as a single atomic instruction, why isn't Interlock.CompareExchange( ref location, 0, 1 ) == 0 the same as test and set?Retainer

© 2022 - 2024 — McMap. All rights reserved.