The idea to ensure correctness here is to treat insert/delete operation as a transaction.
Whenever the operations are executed, the data used for operations is protected from interference of other concurrent operations. The method of this is to lock all currently related resources in each step.
The implementation here locks and only locks necessary resources for current or following steps. So it is a perfect implementation in the frame of this idea.
This comment was marked helpful 1 times.
aakashr
In this implementation each thread uses locks to ensure it has exclusive access to its prev and cur nodes. This is a much better solution than maintaining exclusive access to the entire linked list for a single thread.
This comment was marked helpful 0 times.
kayvonf
@aakaskr: The solution certaining enables a high degree of concurrency when operating on the data structure. Whether the solution is in fact better than a coarse-grained locking solution depends on many factors, such as the number of contenting threads and the overhead of manipulating the fine grained locks. For example, in the transactional memory lecture, there is a slide showing an example where performance degrades when using fine-grained locks.
The idea to ensure correctness here is to treat insert/delete operation as a transaction.
Whenever the operations are executed, the data used for operations is protected from interference of other concurrent operations. The method of this is to lock all currently related resources in each step.
The implementation here locks and only locks necessary resources for current or following steps. So it is a perfect implementation in the frame of this idea.
This comment was marked helpful 1 times.
In this implementation each thread uses locks to ensure it has exclusive access to its
prev
andcur
nodes. This is a much better solution than maintaining exclusive access to the entire linked list for a single thread.This comment was marked helpful 0 times.
@aakaskr: The solution certaining enables a high degree of concurrency when operating on the data structure. Whether the solution is in fact better than a coarse-grained locking solution depends on many factors, such as the number of contenting threads and the overhead of manipulating the fine grained locks. For example, in the transactional memory lecture, there is a slide showing an example where performance degrades when using fine-grained locks.
This comment was marked helpful 0 times.