The key necessity of hand-over-hand locking is that you must have the locks for everything you are modifying. For a singly-linked list, this means having the lock for the node whose data you are modifying and the lock for the node before it whose pointer you are modifying. For a doubly-linked list the locks for the nodes before AND after whose pointers' you are modifying are both required.
This comment was marked helpful 0 times.
ycp
To build on what @asinha said, the reason for this is that if you do not have a lock on something you might be editing, then another thread might come up and cause problems. For instance, when considering the doubly linked list, if you just have a lock on the curr and next nodes, then another thread can delete the prev node while you were trying to set prev->next = next. It is clear to see how this can cause problems. Therefore, when editing anything, you need a lock on anything that can be affected.
This comment was marked helpful 0 times.
spilledmilk
While it is correct to have locks on all the nodes whose data you're modifying, it may not be necessary. As Kayvon describes in the previous slide, if you have a lock for a node, you know that no one will insert after it and no one will be able to delete it or the next node. Therefore, as it maybe even be possible to get away with inserting with 1 lock and deleting with 2 on both singly-linked and doubly-linked lists, as @rokhinip describes.
This comment was marked helpful 0 times.
rokhinip
@spilledmilk: I was actually wrong in my hypothesis and we do need 2 locks for insertion.
The key necessity of hand-over-hand locking is that you must have the locks for everything you are modifying. For a singly-linked list, this means having the lock for the node whose data you are modifying and the lock for the node before it whose pointer you are modifying. For a doubly-linked list the locks for the nodes before AND after whose pointers' you are modifying are both required.
This comment was marked helpful 0 times.
To build on what @asinha said, the reason for this is that if you do not have a lock on something you might be editing, then another thread might come up and cause problems. For instance, when considering the doubly linked list, if you just have a lock on the curr and next nodes, then another thread can delete the prev node while you were trying to set prev->next = next. It is clear to see how this can cause problems. Therefore, when editing anything, you need a lock on anything that can be affected.
This comment was marked helpful 0 times.
While it is correct to have locks on all the nodes whose data you're modifying, it may not be necessary. As Kayvon describes in the previous slide, if you have a lock for a node, you know that no one will insert after it and no one will be able to delete it or the next node. Therefore, as it maybe even be possible to get away with inserting with 1 lock and deleting with 2 on both singly-linked and doubly-linked lists, as @rokhinip describes.
This comment was marked helpful 0 times.
@spilledmilk: I was actually wrong in my hypothesis and we do need 2 locks for insertion.
This comment was marked helpful 0 times.