For an LRU cache I need an algorithm for a lock-free queue similar to the one described in the paper Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
But to maintain an LRU queue I will also need the possibility to delete nodes within the queue (except for nodes at the tail).
My idea is to just mark nodes as deleted with a CAS operation and then use a single cleanup thread which will later on remove the deleted nodes from within the queue.
I found that creation of lock-free algorithm is more complicated than I first anticipated. So, my question is:
Is there any such algorithm available already?
This is the structure that I use currently:
General
Enqueue
Dequeue
Delete
Cleanup thread
Node.prev is used to tell:
Logical deletion of an in-queue element is in fact problematic, which is why you will not find papers for this. Also, it's a very specific function added to a very general data structure, which is another reason you won't find papers; you'll only find papers for the general data structure.
The problematic issue are twofold; firstly, queues typically are not designed to support a cursor. Secondly, knowing whether or not it is still safe to access the element you wish to logically delete - e.g. could it have already been dequeued and deallocated?
The queue you quote uses pointer-counter pairs to solve ABA, which implies the use of a freelist. In this context, you can always be sure the element has not been deallocated.
With regard to a cursor, you'd need to enter at the dequeue and then proceed down the queue to the enqueue pointer. But what happens if the element you're looking at is dequeued before you move on to the next element? you'll then be following the next pointer of an element which has been removed from the queue and is in the freelist. In fact, in general, anything can happen to the queue between the cursor moving from one element to the next - including complete queue removal and recreation with different elements.
So, you need a linked list, which has explicit support for cursors.
You don't mention the language you're using?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With