Search code examples
c#thread-safetylockinglock-freeinterlocked

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

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

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