Algorithm for lock-free queue with move-to-tail functionality

3
votes

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

  • A node has the following structure: struct { e *entry, next pointer, prev pointer, state uint32}
  • To avoid multiple memory allocation for each new node an array of nodes are allocated.
  • A pointer to a node consists of the array index value and a update counter, multiplexed into a single uint64
  • A node state consist of a high bit telling if the node is deleted or not. Rest of the bits are used as update counter

Enqueue

  • An auxiliary queue holds a list of unused nodes and a "new" node is fetched through dequeue from the aux queue and then set to default
  • node.prev is set to current tail prior to the new node being enqueued

Dequeue

  • head.next.prev is CAS'ed to NIL value prior to head dequeue. In case head.next.prev is set to CLEANUP (being processed by the cleanup thread), a dequeue is not allowed and the thread will yield the CPU and start over again.
  • On successful dequeue of a node with an undeleted state the state will be CAS'ed to deleted and the node will be returned to the auxilary queue. On failure (or state already set to deleted), the dequeued node.prev will be changed from NIL to CLEANUP, signaling to the cleanup thread that the node is dequeued. The dequeue will then start over until an undeleted node is successfully dequeued and CAS'ed to deleted.

Delete

  • To mark in-queue deletion, state is CAS'ed to deleted and passed to a cleanup queue on success. Nothing is done on failure, but the function returns.

Cleanup thread

  • If node.prev is CLEANUP, a Dequeue has removed it from queue. Node is passed back to auxilary queue.
  • If node.prev is NIL, the node is about to become head, is head, or is about to be dequeued. If node == head, cleanup thread tries to perform a dequeue (with state changed to deleted). On failure the cleanup process starts all over.
  • If node is set to another node, node.prev is CAS'ed to CLEANUP. This prevents any dequeue to be made if as soon as head.next == node. On success, in-queue removal is made using the double-linked list. On failure the cleanup process starts all over.

Node.prev is used to tell:

  • What node is previous in the queue
  • Node is about to become head/is head
  • Node is being processed by the cleanup thread
  • Node is dequeued
1
algorithmqueueatomiclock-freelru
Which environment/programming language do you intend to use it in? - Eugen Rieck
Currently I am making the implementation in Go language. But I don't mean to make a language dependent algorithm. - ANisus
But you want it "bare metal" - not Java, dotnet or friends - this was the background of my question. - Eugen Rieck
Preferably, yes. I want to see the the CAS operations so that I can make a similar implementation in Go, C, etc. Using, say, a Java class would, the algorithm would be hidden. - ANisus
The algorithm in your paper is implemented in a very readable manner in C# in blog.boyet.com/blog/blog/testing-the-lock-free-queue, should be trivial to port. It was to slow for me, so I created sourceforge.net/projects/dotnetlockless which should also be quite readable. I didn't do any work on in-queue manipulation, so I can't really advise there. Thinking of it, I might tackle this not by changing the queue, but by an independant invalidation mechanism, where a dequeue would simply drop an element if it was invalidated, moving on to the next. - Eugen Rieck

1 Answers

3
votes

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?