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.

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

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

Solution 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".

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

Solution 5

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)

View more solutions

Comments

[Cheeso]

C# (.NET) absolutely has an atomic Compare-and-Swap. It is called Interlocked.CompareExchange. msdn.microsoft.com/en-us/library/…

[Daniel Earwicker]

"something that would compile the operations together to ensure no collisions" - what does that mean?

[Daniel Earwicker]

"getting the locking as fine-grained as possible" - that could make it slower, as the cost of taking out many short locks may be more significant than the avoided waiting time, depending on the macro-behaviour of the application.

[Unknown]

@ Cheeso, then in that case, its possible.

[plankalkul]

Think of it like how modern CPUs utilize multiple execution units on one core to achieve high instruction throughput; the interactions of the instructions with the execution units is checked to be non-interdependent, and the microinstructions are interleaved so as to preserve any order-dependent operations. It's fundamentally a compilation operation.

[Admin]

This answer is incorrect. Doubly linked lists have been implemented. The key is that the back pointer isn't always up to date and so when you traverse backwards, you have to do some extra work.

[Admin]

I believe however, AFAIK, ALL doubly-linked lists (and indeed, it might even be all singly-linked lists) require GC.

[Admin]

There are better methods than the method suggested here. I don't think anyone has tried doing this - it seems basically to be a form of serialisation, not unlike a multiple-reader/single-writer lock.

[Admin]

I believe Valois' 1995 singly-linked list does not require GC - I need to read the paper though.

[luvieere]

It could be used to implement a multi-threaded user-interface - no more single UI Thread.

[Eloff]

I don't think @JohnGietzen gets the question. The OP wants to know if it's possible to implement a wait free doubly linked list. It is. The back pointer cannot be trusted, so extra work is done when walking the list backward, but that's not waiting. The data structure has very similar performance characteristics to a "real" doubly linked list. But of course low-lock data structures can often be slower than their much simpler locking counterparts - that's why you need to profile first, and verify that the locking is actually the bottleneck.

[Reed Copsey]

@Eloff & @Blank Xavier: Using interlocked, though, doesn't get you there, on it's own. The normal way of doing a single linked list is to have an immutable temp you can compare and swap with interlocked into place. With a double linked list, this doesn't function correctly, because the back referencing can be messed. You can correct this later (while iterating in reverse), but this typically requires some form of locking at that point (often done with a spin lock of some form).

[Eloff]

@Reed Copsey: True as far as I know. But of course a spin lock is just interlocked compare exchange in a loop, likewise a lock-free single linked list using CAS is really the same as a spin lock, you're just spinning on the pointer instead of a separate lock state variable.

[Maciej Piechotka]

-1: a) Lock-free and C# covers a wide spectrum. For example there are papers using hypothetical DCAS operation. Using DCAS operation such operation would be possible (insertion would be at least easy, deletion could be adapted from single linked list probably). b) Please remember that in many structures you can mark nodes using additional bits. It may turn out that it can be done by smart marking of nodes.

[Reed Copsey]

@Maciej: That's fine - you're free to mark it down, but Show me an implementation that actually works, using C#.

[Maciej Piechotka]

@Eloff: No it is not. Spinlocks are usually a very naive implementation of locks although it may be suitable in some situations. If thread having spin-lock is suspended no other thread can do anything. Such algorithm is not even obstruction free.

[Maciej Piechotka]

@Reed Copsey: There is fine difference between 'it is not possible' and 'people haven't figured out how to do this'.

[Maciej Piechotka]

@Reed Copsey: After small amount of thought - set the first the back link of the next node. During iteration check if the prev link is the one we come from and if not we go back. Similarly the deleting could be simple extension of 3 stage deletion with marking and backlink. I haven't proved it, check if it is correct etc. but it at least sounds as possible.

[Ed S.]

@luvieere: The vast majority of the time there is absolutely no need for a multi-threaded UI. Using a single thread simplifies things greatly and the added complexity of using multiple UI threads is simply not worth it.

[JanKanis]

The Valois paper uses reference counting to ensure lock free memory management. The reference count represents the number of global pointers to the node. Additionally each thread keeps a hazard list of pointers to nodes it is currently using. If a thread wants to remove a pointer from its hazard list which has a reference count of 0, it has to scan the hazard lists of all other threads to see if anyone is still using it, and only delete it of no one is. There are some tricks involved in safely scanning the hazard lists without taking any locks.

[MRB]

can you take a look at this question: stackoverflow.com/q/19609417/2279977 , pls