Is a lock (wait) free doubly linked list possible?

Question

Asking this question with C# tag, but if it is possible, it should be possible in any language.

Is it possible to implement a doubly linked list using Interlocked operations to provide no-wait locking? I would want to insert, add and remove, and clear without waiting.

Answer 1

A simple google search will reveal many lock-free doubly linked list papers.

However, they are based on atomic CAS (compare and swap).

I don't know how atomic the operations in C# are, but according to this website

http://www.albahari.com/threading/part4.aspx

C# operations are only guaranteed to be atomic for reading and writing a 32bit field. No mention of CAS.

Answer 2

Yes it's possible, here's my implementation of an STL-like Lock-Free Doubly-Linked List in C++.

Sample code that spawns threads to randomly perform ops on a list

It requires a 64-bit compare-and-swap to operate without ABA issues. This list is only possible because of a lock-free memory manager.

Check out the benchmarks on page 12. Performance of the list scales linearly with the number of threads as contention increases. The algorithm supports parallelism for disjoint accesses, so as the list size increases contention can decrease.

Answer 3

Here is a paper which discribes a lock free doublly linked list.

We present an efficient and practical lock-free implementation of a concurrent deque that is disjoint-parallel accessible and uses atomic primitives which are available in modern computer systems. Previously known lock-free algorithms of deques are either based on non-available atomic synchronization primitives, only implement a subset of the functionality, or are not designed for disjoint accesses. Our algorithm is based on a doubly linked list, and only requires single-word compare-and-swap...

Ross Bencina has some really good links I just found with numerious papers and source code excamples for "Some notes on lock-free and wait-free algorithms".

Answer 4

I don't believe this is possible, since you're having to set multiple references in one shot, and the interlocked operations are limited in their power.

For example, take the add operation - if you're inserting node B between A and C, you need to set B->next, B->prev, A->next, and C->prev in one atomic operation. Interlocked can't handle that. Presetting B's elements doesn't even help, because another thread could decide to do an insert while you're preparing "B".

I'd focus more on getting the locking as fine-grained as possible in this case, not trying to eliminate it.

Answer 5

Read the footnote - they plan to pull ConcurrentLinkedList from 4.0 prior to the final release of VS2010

Answer 6

Well you haven't actually asked how to do it. But, provided you can do an atomic CAS in c# it's entirely possible.

In fact I'm just working through an implementation of a doubly linked wait free list in C++ right now.

Here is paper describing it. http://www.cse.chalmers.se/~tsigas/papers/Haakan-Thesis.pdf

And a presentation that may also provide you some clues. http://www.ida.liu.se/~chrke/courses/MULTI/slides/Lock-Free_DoublyLinkedList.pdf

Answer 7

It is possible to write lock free algorithms for all copyable data structures on most architectures [1]. But it is hard to write efficient ones.

I wrote an implementation of the lock-free doubly linked list by Håkan Sundell and Philippas Tsigas for .Net. Note, that it does not support atomic PopLeft due to the concept.

[1]: Maurice Herlihy: Impossibility and universality results for wait-freesynchronization (1988)

Answer 8

FWIW, .NET 4.0 is adding a ConcurrentLinkedList, a threadsafe doubly linked list in the System.Collections.Concurrent namespace. You can read the documentation or the blog post describing it.

Answer 9

I would say that the answer is a very deeply qualified "yes, it is possible, but hard". To implement what you're asking for, you'd basically need something that would compile the operations together to ensure no collisions; as such, it would be very hard to create a general implementation for that purpose, and it would still have some significant limitations. It would probably be simpler to create a specific implementation tailored to the precise needs, and even then, it wouldn't be "simple" by any means.