The idea of hand-over-hand locking can also be explained as holding the locks on two consecutive nodes at any point of the traversal in the list. By doing this, we can ensure that any deletion of the second node or insertion between the first and second node is essentially atomic as no other threads can be inserting or deleting at the same position. To see how much of a difference this makes, assume that your linked list was a million elements long and every update was originally taking a lock on the entire data structure as opposed to "hand-over-hand" locking where each thread only takes the lock on two nodes at any point in time, which enables a high number of concurrent accesses.
POTUS
One result of hand-over-hand locking is that no thread can overtake another.
atadkase
Thread 0 is trying to delete the node 11. In order to do that, it has to modify node 10. Thread 1 wants to delete node 10, however, as thread 0 already has the node locked using the hand-over-hand locking scheme, thread 1 cannot proceed.
asd
So, the hand-hand-over locking would still stall us from accessing the rest of the linked list if someone has grabbed the lock on some node at the start of the list, right?
rrp123
Is there a way to implement hand over hand locking in such a way that if T1 wanted to insert something in the part of the list that is after node 18, it would be able to jump over the 2 nodes that T0 is holding and make progress?
rsvaidya
@asd Yes, if the list can only be traversed from the head, then if someone has a lock in the beginning of the list them no one else can overtake it. However if it is a Doubly linked list then access can be possible from tail in the backward direction.
Brandon
In this case has anyone implemented a hashing function with multiple heads to prevent this sequential startup for hand-over-hand locking? In other words will it be possible to somehow jump over another processor in a way that does not break the promise of consistency?
The idea of hand-over-hand locking can also be explained as holding the locks on two consecutive nodes at any point of the traversal in the list. By doing this, we can ensure that any deletion of the second node or insertion between the first and second node is essentially atomic as no other threads can be inserting or deleting at the same position. To see how much of a difference this makes, assume that your linked list was a million elements long and every update was originally taking a lock on the entire data structure as opposed to "hand-over-hand" locking where each thread only takes the lock on two nodes at any point in time, which enables a high number of concurrent accesses.
One result of hand-over-hand locking is that no thread can overtake another.
Thread 0 is trying to delete the node 11. In order to do that, it has to modify node 10. Thread 1 wants to delete node 10, however, as thread 0 already has the node locked using the hand-over-hand locking scheme, thread 1 cannot proceed.
So, the hand-hand-over locking would still stall us from accessing the rest of the linked list if someone has grabbed the lock on some node at the start of the list, right?
Is there a way to implement hand over hand locking in such a way that if T1 wanted to insert something in the part of the list that is after node 18, it would be able to jump over the 2 nodes that T0 is holding and make progress?
@asd Yes, if the list can only be traversed from the head, then if someone has a lock in the beginning of the list them no one else can overtake it. However if it is a Doubly linked list then access can be possible from tail in the backward direction.
In this case has anyone implemented a hashing function with multiple heads to prevent this sequential startup for hand-over-hand locking? In other words will it be possible to somehow jump over another processor in a way that does not break the promise of consistency?