Previous | Next --- Slide 41 of 66
Back to Lecture Thumbnails
crs

Does this only work for specific ops, like insertion/deletion? Or is this more general?

nassosterz

My guess is that it works for operations that affect 2 consecutive nodes.

mark

With this hand-over-hand locking, it seems like processors can easily get held up waiting for another processor down the line to finish up before they can move to the part of the link list they need to. Is there any way to have threads safely jump over locked nodes in order to get where they need to?

sidhikab

If you are holding the lock on the previous node (10) when deleting 11, you're guaranteed that 10 cannot be deleted by anyone else. This is because if another thread wanted to delete 10, they would have to have the lock on 10. But since we have a lock on 10, the other thread cannot obtain a lock on 10. Therefore 10 cannot get deleted by anyone else.

Similarly, no one can delete 18. This is because according to the rule, in order to delete 18, you must hold the lock on the previous node (11). However, we currently hold the lock on 11.

awu

Following up on nassosterz, does this mean if we have an operation that affects n consecutive nodes, we'll need to lock all n of them?

kayvonf

note to all... please see the lecture video. This single image is the keynote export where all objects on the slide are rendered even though the slide has animation. During the video, you'll notice that the hand-over hand pattern results in only at most two locks being held at once.

Please log in to leave a comment.