The previous linked-list code is deadlock free because threads only wait for locks in one direction. A later thread could never exceed a previous thread on the linked-list. Notice that the first thread never needs to wait for locks and it could end eventually. Then the second thread becomes the first one. By induction, all threads operating on the linked-list must end at sometime. Thus, the linked-list is deadlock-free.
This comment was marked helpful 0 times.
ruoyul
It was mentioned in class that we can find a middle-ground by choosing to lock at a larger granularity. But I have a hard time imagining how this would apply on the linked list problem. How might we lock on a granularity in between the hand-over-hand and locking the entire list range?
This comment was marked helpful 0 times.
wcrichto
@ruoyul you could have a lock for, say, every other node. Then locking any one node implicitly locks the node in front of it as well. So you might have to exclude four nodes to do a single delete, but overall you're taking less locks when traversing the list.
This comment was marked helpful 0 times.
mchoquet
@wchricto's solution seems like a good one to me, but extra care would have to be taken to ensure that the lock granularity remains consistent in the face of insertions and removals from the list. This would be annoying, but doesn't seem impossible to me. Can anyone think of a scheme that reduces the number of locks, but is simpler to manage? The best thing I can think of is to have $k$ locks and assign each node a number from 1 to $k$ based on whatever lock is least-used at the time of its insertion. This has a downside over the earlier answer in that a lock's nodes are spread around the list, so operations nowhere near each other can still interfere.
This comment was marked helpful 0 times.
elemental03
Can someone explain to me what fine-grained locking is exactly?
I understand how it works with the linked list but i was hoping for some sort of general terminology in regards to fine-grained locking.
This comment was marked helpful 0 times.
drayson
@elemental03 The "naive" coarse-grained way to handle locking for a data structure is to just put one lock around the entire structure. For many data structures, though, there are sets of operations that can run in parallel on different parts of the structure without issue. Fine-grained locking is when we individually lock smaller subcomponents of the data structure, allowing operations that won't interfere with each other to be done on it in parallel.
The previous linked-list code is deadlock free because threads only wait for locks in one direction. A later thread could never exceed a previous thread on the linked-list. Notice that the first thread never needs to wait for locks and it could end eventually. Then the second thread becomes the first one. By induction, all threads operating on the linked-list must end at sometime. Thus, the linked-list is deadlock-free.
This comment was marked helpful 0 times.
It was mentioned in class that we can find a middle-ground by choosing to lock at a larger granularity. But I have a hard time imagining how this would apply on the linked list problem. How might we lock on a granularity in between the hand-over-hand and locking the entire list range?
This comment was marked helpful 0 times.
@ruoyul you could have a lock for, say, every other node. Then locking any one node implicitly locks the node in front of it as well. So you might have to exclude four nodes to do a single delete, but overall you're taking less locks when traversing the list.
This comment was marked helpful 0 times.
@wchricto's solution seems like a good one to me, but extra care would have to be taken to ensure that the lock granularity remains consistent in the face of insertions and removals from the list. This would be annoying, but doesn't seem impossible to me. Can anyone think of a scheme that reduces the number of locks, but is simpler to manage? The best thing I can think of is to have $k$ locks and assign each node a number from 1 to $k$ based on whatever lock is least-used at the time of its insertion. This has a downside over the earlier answer in that a lock's nodes are spread around the list, so operations nowhere near each other can still interfere.
This comment was marked helpful 0 times.
Can someone explain to me what fine-grained locking is exactly?
I understand how it works with the linked list but i was hoping for some sort of general terminology in regards to fine-grained locking.
This comment was marked helpful 0 times.
@elemental03 The "naive" coarse-grained way to handle locking for a data structure is to just put one lock around the entire structure. For many data structures, though, there are sets of operations that can run in parallel on different parts of the structure without issue. Fine-grained locking is when we individually lock smaller subcomponents of the data structure, allowing operations that won't interfere with each other to be done on it in parallel.
This comment was marked helpful 1 times.