We have a slight modification to the hand-over-hand locking: if a node is being deleted, not only is the lock on that particular node but also on the node before them. So if 11 is being deleted, 11 and 10 are locked. This prevents any other thread pointing its next to 18 as 11 is locked. Is my reasoning correct?
eknight7
@efficiens I think yes - because 11 is being deleted, 11 and 10 are locked. So another thread cannot modify 18 because that would require 11 but we already locked 11. We therefore know that after deleting 11, 10 would point to 18, and 18 will remain unchanged.
grarawr
Wouldn't this end up being slow on bigger linked lists since this is linear?
rajul
@grarawr Well this does create a barrier in the list but in practice I don't think this will be slow especially on bigger lists because:
If u are doing a linear probe by the time u reach the barrier the lock would likely have been released.
If the barrier is somewhere down the list you are likely to never see the barrier at all. Similarly if its at the beginning of the list and you have crossed that you will never wait for the barrier lock.
anonymous
To summarize what we talked about in class. "Hand over hand locking" is similar to doing the monkey bars as a child. There is always one lock that is kept on the list. When doing an insertion you insert between two elements that are already locked. When doing a deletion, you make sure that the previous element is locked (ensuring that a different thread can not delete the next element in the list from the one that the current thread is deleting).
teamG
in lecture, it was mentioned that both the readers and writers of the nodes will need to hold the lock. It wasn't immediately obvious to me why readers would need to acquire the lock too, but one reason given in lecture is that we want to make sure we aren't reading deallocated memory, and by having the lock, we can ensure that no one else is deleting the node.
stride16
Would insertion or deletion be any different in a doubly linked list as compared to the singly linked list?
bojianh
For insertion, it should be the same since you are holding the lock to both the nodes prev and cur.
For deletion, someone can hold the lock to the cur->next node in which you need to modify. However, in this case, I believe that cur->next node cannot be deleted and the cur->next->prev pointer will also not be modified, so it should be the same as well.
We have a slight modification to the hand-over-hand locking: if a node is being deleted, not only is the lock on that particular node but also on the node before them. So if 11 is being deleted, 11 and 10 are locked. This prevents any other thread pointing its next to 18 as 11 is locked. Is my reasoning correct?
@efficiens I think yes - because 11 is being deleted, 11 and 10 are locked. So another thread cannot modify 18 because that would require 11 but we already locked 11. We therefore know that after deleting 11, 10 would point to 18, and 18 will remain unchanged.
Wouldn't this end up being slow on bigger linked lists since this is linear?
@grarawr Well this does create a barrier in the list but in practice I don't think this will be slow especially on bigger lists because:
To summarize what we talked about in class. "Hand over hand locking" is similar to doing the monkey bars as a child. There is always one lock that is kept on the list. When doing an insertion you insert between two elements that are already locked. When doing a deletion, you make sure that the previous element is locked (ensuring that a different thread can not delete the next element in the list from the one that the current thread is deleting).
in lecture, it was mentioned that both the readers and writers of the nodes will need to hold the lock. It wasn't immediately obvious to me why readers would need to acquire the lock too, but one reason given in lecture is that we want to make sure we aren't reading deallocated memory, and by having the lock, we can ensure that no one else is deleting the node.
Would insertion or deletion be any different in a doubly linked list as compared to the singly linked list?
For insertion, it should be the same since you are holding the lock to both the nodes prev and cur.
For deletion, someone can hold the lock to the cur->next node in which you need to modify. However, in this case, I believe that cur->next node cannot be deleted and the cur->next->prev pointer will also not be modified, so it should be the same as well.