Timeline for How to write a doubly linked list for multi-core use without global lock?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 4, 2015 at 14:57 | comment | added | user22815 | @GoswinvonBrederlow The lock manager does not need to care how to synchronize between cores. Synchronization in software eventually delegates to hardware synchronization, which is generally guaranteed to synchronize across cores by the underlying architecture (it is for AMD64 among others). | |
| Jun 4, 2015 at 10:14 | comment | added | Goswin von Brederlow | @ratchetfreak Using shared_ptr would work for deletion but not for moving between lists. | |
| Jun 4, 2015 at 9:49 | comment | added | ratchet freak | @GoswinvonBrederlow forward pointers are shared_ptr, backward pointers are weak_ptr, before you can do anything you need a shared_ptr to the node you are manipulating -> no way for B to get deleted because the core holds a shared_ptr. | |
| Jun 4, 2015 at 9:38 | comment | added | Goswin von Brederlow |
@ratchetfreak between unlock B and lock B C another core can delete C and B.next then points to D. You need more protection there.
|
|
| Jun 4, 2015 at 9:35 | comment | added | Goswin von Brederlow |
@Snowman Another option is to have an object that manages the locks. How does that object synchronize across all cores? Does it have a lock so only one core ever runs the core for the lock manager? That basically means you have a global lock for the whole list.
|
|
| Jun 4, 2015 at 9:35 | comment | added | ratchet freak | @GoswinvonBrederlow lock B get &A and &C; unlock B; lock A B and C; double check the values, repeat if needed. | |
| Jun 4, 2015 at 9:31 | comment | added | Goswin von Brederlow | @ratchetfreak Core 0 has a pointer to B and nothing else. How does it get a pointer to A and lock it without locking B to make sure no other core changes B.prev while it is doing that? | |
| Jun 4, 2015 at 7:52 | comment | added | ratchet freak | @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. | |
| Jun 4, 2015 at 0:06 | comment | added | user22815 | 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. | |
| Jun 4, 2015 at 0:05 | comment | added | user22815 | @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. | |
| Jun 3, 2015 at 23:57 | comment | added | Goswin von Brederlow | 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 | |
| Jun 3, 2015 at 23:52 | comment | added | Craig Tullis | 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. | |
| Jun 3, 2015 at 23:50 | history | answered | user22815 | CC BY-SA 3.0 |