6

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?

  • I don't know if you looked around Stack Exchange much, but here's a similar question, with a few answers but none marked as the accepted answer, and at least one warning about tough bugs and advising to just use coarse locking: stackoverflow.com/q/4320337/618649 – Craig Jun 3 '15 at 23:50
  • It has lots of non-solutions that's for sure. Just like the first answere here will deadlock within seconds. Google was also quite unhelpfull since most cases deal with threads and not cores and try to solve the problem that one thread gets preempted before finishing its operation. – Goswin von Brederlow Jun 4 '15 at 0:17
  • Well...each core is still effectively executing a thread even if this is your own custom kernel that only spins up as many threads as you have CPU cores (or call them processes or executors or whipsits or whatever you want to call them). Point being that they're all still contending over a shared resource (RAM) and you have to coordinate access or you end up in deadlock, or with hopelessly corrupted data structures. So it's not so different from threads. That threads are pre-emptible by a scheduler just means you have even more opportunities for conflicts, because more threads. ;-) – Craig Jun 4 '15 at 0:47
2

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.

  • insert node after current node: lock the current and next node, then do your insertion, rewiring the pointers between the two nodes to point at the new node.
  • insert node at end: same as above, except the next node is the first node.
  • move current node from one list to another: this is unlinking from one list and inserting into another. You would need to lock the node being moved, and the adjacent nodes in both lists.
  • delete current node: lock the current node and the two around it. Unlink the current node.
  • advance from current node to next node: lock nothing, but wait for the lock to release if moving to a locked node. After the lock releases, reevaluate what "next node" is.

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.

  • If you do something like this, I'd probably measure performance with various list sizes, and if there's a crossover point where performance is better the bigger the list, just use coarse-grained locking with small lists and switch to granular locking with big lists. – Craig Jun 3 '15 at 23:52
  • Say you have a list like A-B-C-D. Core 0 tries to delete B and Core 1 tries to delete C. Core 0 locks B, core 1 locks C, core 0 locks A, core 1 blocks on locking B, core 0 blocks on locking C. deadlock – Goswin von Brederlow Jun 3 '15 at 23:57
  • 1
    @GoswinvonBrederlow there are ways to mitigate deadlocks. If a thread cannot lock every node it needs, it should immediately release the locks it already has and wait a random (but small) amount of time and repeat. – user22815 Jun 4 '15 at 0:05
  • 1
    Another option is to have an object that manages the locks. A lock request comes in with all of the nodes (pointers, IDs, whatever) that a thread needs to lock. Each lock is processed atomically and could either fail or block if unable to proceed at the current time. There are options here. – user22815 Jun 4 '15 at 0:06
  • @GoswinvonBrederlow core0 should lock in order A-B-C and core 1 should lock B-C-D, aka always lock the node closest to the head first, if the group wraps (you want to insert before A) then you should lock A-B-D. This way there is no deadlock. – ratchet freak Jun 4 '15 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.