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

c# thread-safety locking lock-free interlocked
esac picture esac · May 11, 2009 · Viewed 9.6k times · Source

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

Qarterd picture Qarterd · Jul 6, 2011

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.

Related questions

How does lock work exactly?

I see that for using objects which are not thread safe we wrap the code with a lock like this: private static readonly Object obj = new Object(); lock (obj) { // thread unsafe code } So what happens when multiple threads access the …

Read More
Concurrent HashSet<T> in .NET Framework?

I have the following class. class Test{ public HashSet<string> Data = new HashSet<string>(); } I need to change the field "Data" from different threads, so I would like some opinions on my current thread-safe implementation. class …

Read More
C# thread safety with get/set

This is a detail question for C#. Suppose I've got a class with an object, and that object is protected by a lock: Object mLock = new Object(); MyObject property; public MyObject MyProperty { get { return property; } set { property = value; } } I want …

Read More