Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

12
  • 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. Commented Jun 3, 2015 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 Commented Jun 3, 2015 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. Commented Jun 4, 2015 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. Commented Jun 4, 2015 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. Commented Jun 4, 2015 at 7:52