sorted atomic linked list algorithm (priority queue)

6
votes

Can somebody point me towards an algorithm for a sorted thread-safe atomic (lock-free) linked list/priority queue? I'm aware of how to do just a linked list itself, but now I need one that is sorted. I'm unsure if this is minor change or significant redesign compared to an unsorted list, thus would like to see an existing algorithm before I make my own.

It needn't actually be a list (or technically sorted), but behaves like a priority queue with these properties:

  • lowest element is the one with the minimum integer field value
  • access to lowest element in constant time
  • modification via atomic operations only (no locks)
  • insertion/removal in linear time

The contents will likely be pointers to structures. The integer field to sort is one of the members of that structure.

This is for a C++ program, but I don't need code examples, an algorithm description is fine. Algorithms which come close, but not perfect, are also appreciated.

1
c++calgorithm
Seems like you want an atomic priority queue if you just need the minimum element. This is still an interesting question, though, and I'm curious what the answer is. - templatetypedef
Yes, priority queue is probably closer to what I logically want. I've updated the description. - edA-qa mort-ora-y

1 Answers

5
votes

Look at this: "Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems". Googling will give you more links for sure.