This is one solution to the problem of having 2 threads operate on the linked list at the same time. We can lock the entire data structure. It is important to make sure that we unlock at the end of all paths of execution. It is pretty much sequential though albeit a simple to understand solution.
Funky9000
Problem with this is once a thread gets the lock on the linked list, no other threads can operate on the linked list till the lock is unreleased, thereby reducing the amount of parallelism that can be exploited.
totofufu
Is it not possible to shorten the length of the critical sections here? For example, in insert, could we not just put a lock around the while loop? My guess is that it would make very little difference anyway since most of the time is spent in the loop.
jerryzh
@totofufu, I don't think moving the lock close to the while loop would work, because in that case, the list might change between the assignment of the variable prev and cur and the execution of the while loop, which will cause the list to be inconsistent after the operation.
This is one solution to the problem of having 2 threads operate on the linked list at the same time. We can lock the entire data structure. It is important to make sure that we unlock at the end of all paths of execution. It is pretty much sequential though albeit a simple to understand solution.
Problem with this is once a thread gets the lock on the linked list, no other threads can operate on the linked list till the lock is unreleased, thereby reducing the amount of parallelism that can be exploited.
Is it not possible to shorten the length of the critical sections here? For example, in insert, could we not just put a lock around the while loop? My guess is that it would make very little difference anyway since most of the time is spent in the loop.
@totofufu, I don't think moving the lock close to the while loop would work, because in that case, the list might change between the assignment of the variable prev and cur and the execution of the while loop, which will cause the list to be inconsistent after the operation.