Previous | Next --- Slide 40 of 66
Back to Lecture Thumbnails
gmukobi

To explain this otherwise strange-out-of-context slide about locking when traversing a linked-list for the purposes of insert/delete: Just like when traversing handelbars (e.g. at a playground or in American Ninja Warrior as depicted), you must be holding onto at least one rung/lock at a time, otherwise you'd fall/risk bad things happening due to race conditions. Further, when starting from rung/lock i, it's safest to grab/lock i+1, release i, grab/lock i+2, release i+1, etc. so that you are constantly grabbing/locking either 1 or 2 rungs/nodes at a time and allowing for safe traversal. Personally, I was super confused about where locks could efficiently be placed until Kayvon showed this metaphor.

ghostcow

Loved @gmukobi's comment! Another summary here to restate the key idea: - Key idea: you should never be in a state in which you are holding no locks at all, because if this is the case you might as well have not even tried locking (you have no guarantees on what the other threads are doing) - Instead of holding a global lock over an entire list, consider holding two locks on consecutive elements, and acquiring/releasing locks in a "hand-over-hand" manner (lock 0, lock 1, release 0, lock 2, release 1, lock 3, etc.)

Please log in to leave a comment.