Previous | Next --- Slide 8 of 31
Back to Lecture Thumbnails
solovoy

In real implementation of hand-over-hand, do we acquire next lock before release previous lock or release the previous lock and then try to acquire the next lock?

rflood

Slide 12 has source for this, It seems like it releases then acquires.

abist

It does release and then acquire, as Kayvon said this in class

russt17

Yes, you only have two hands, you can't hold three locks at once ;). By the way, for an analogy, when you belay someone who is rock climbing, you use hand-over-hand locking on the rope so you can make progress but always have one hand on the rope.

sgbowen

Maybe a weird question, but is hand-over-hand applicable to any other data structures besides linked lists? Can it be thought of as a general fine-grained locking technique?

pmassey

I believe that as long as your data structure has one-directional connections it will work. So acyclical trees could be another application.

afa4

@sgbowen Yes, hand-over-hand locking can be used for insert and search operations of a binary search trees.

sanchuah

@sgbowen I believe Yes. I think the reason we use hand-over-hand locking is that the data structure is organized with pointers, which maybe changed during we are going to the element we want to modify. If the data structure can be randomly accessed, I think that the hand-over-hand locking is not necessary in those cases.

jcarchi

One of the reasons to use hand over hand locking is it stops other threads from racing through the data structure. For example if we release before acquiring the next lock, if P0 is iterating the list, and releases a lock, P1 could pass P0 between the lock and unlock. This might cause some problems in other data structures.