I'm trying to write a cyclic doubly linked list where the nodes or even the link pointers are locked individualy. Or a lock-free or even wait-free (I think that's not possible) implementation.
The list will be used in a simple kernel for the scheduler and message passing subsystems. The kernel is non-interruptible, so code will never be preempted in the middle, but it is an SMP kernel, so multiple cores can be trying to work on the list in parallel.
Needed operations:
- insert node after current node
- insert node at end
- move current node from one list to another
- delete current node
- advance from current node to next node
Note: if the algorithm is so complex that it is 10 times as slow as locking the whole list then it is pointless. It would be faster to run the cores sequentially than parallel even if they try to modify the list all at the same time.
So, any pointers for an algorithm or should I just use a lock for the whole list?
Best Answer
If you need synchronization and a copy-on-write list is not acceptable, I would place the lock granularity at the node level.
Specifically, you would lock two or three adjacent nodes and perform your operations. This relies on the fact that it is cyclic, which actually simplifies some of the logic.
Without measuring it my gut feeling is the performance would likely be better the larger the list is. There is a bit of overhead both in design/coding as well as in the locking. Locking the whole list is really easy, but penalizes reads unnecessarily. As the list grows, the number of nodes penalized this way increases linearly.
You did not give a language, but it may be worth seeing what existing code is in its standard library and see if that works. If the performance is unacceptable or nothing exists (e.g. C) then roll your own. Compare the two and see what works better.