concurrent linked list

Question

I am trying to design a linked list in c++ that allows concurrent access. Clearly using a single lock for this list is grossly inefficient since disjoint areas may be updated in parallel. Now what are my options other than storing a lock per node?

Also, would a non-blocking version be a better bet in this case? Any relevant links, anyone?

EDIT: Thanks for the responses people. Couple of things I'd like to add:

1. How about storing N locks for every M nodes instead of 1:1 lock:node ratio? Some threads would wait but it's kind of a trade off. What do you think?
2. If I intend to find some node in this linked list looks like all the mutexes need be locked. This is an issue, because locking and unlocking of all the mutexes is time consuming. Does anyone have a better alternative?
3. I am open to non-blocking algorithms. But how do I use CAS in good old C++ without using assembly? I hear that gcc has some __sync attributes that do similar work but not sure.
4. With non-blocking approach, how do you do a find on the linked list?

Answer 1

Linked lists are inherently sequential data structures. No matter what kind of machinery you use to implement it, the interface and expected behavior imply sequential logic.

What are you trying to do? That should determine what data structure you use, not the familiarity of the data structures you already are comfortable with.

Answer 2

It's possible to implement a non-blocking singly linked list using interlocked functions:

Interlocked Singly Linked Lists

I don't think it's possible to implement a non-blocking doubly linked list without interlocked compare-and-swap (CAS), which isn't widely available.