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.

Ferdinande

lock free and wait free are different.... lock free means some threads can make progress, wait free means all threads can make process. – Focal

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.

Adventurous

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

@ Cheeso, then in that case, its possible. – Adventurous

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

@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. – Satori

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.

Ameba

can you take a look at this question: https://mcmap.net/q/1160736/-atomic-operations-for-lock-free-doubly-linked-list/2279977 , pls – Governor

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

Guffaw

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

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

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. – Rockoon

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.

Grubbs

"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. – Tapeworm

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. – Untuck

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. – Adios

@Adios & @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). – Grubbs

@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. – Adios

-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. – Casandracasanova

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

@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. – Casandracasanova

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

@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. – Casandracasanova

Answer 5

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

Byte

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

Extrasensory

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)

Dupuis

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.

Imitative

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.

Stronghold

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

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. – Stronghold

This is a pretty much a non-issue as most languages supply some sort of "memory barrier" that disallows both the compiler and the CPU from moving read/write operations beyond it, so you can make sure it doesn't rearrange the operations in a way that invalidates you're code. (Its why the volatile keyword in c/c++ was invented, though volatile only ensures this against other volatile variables, hence the introduction of memory barriers). – Nucleus

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. – Untuck