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