A key challenge in parallel programming is to provide
existence guarantees [GKAS99],
so that attempts to delete an object that others are concurrently
attempting to access are correctly resolved.
Existence guarantees are extremely helpful in cases where a data
element is to be protected by a lock or reference count that is
located within the data element in question.
Code failing to provide such guarantees is subject to subtle races,
as shown in
Figure .
Quick Quiz 8.5:
What if the element we need to delete is not the first element
of the list on line 8 of
Figure ?
End Quick Quiz
Quick Quiz 8.6:
What race condition can occur in
Figure ?
End Quick Quiz
One way to fix this example is to use a hashed set of global locks, so
that each hash bucket has its own lock, as shown in
Figure .
This approach allows acquiring the proper lock (on line 9) before
gaining a pointer to the data element (on line 10).
Although this approach works quite well for elements contained in a
single partitionable data structure such as the hash table shown in the
figure, it can be problematic if a given data element can be a member
of multiple hash tables or given more-complex data structures such
as trees or graphs.
These problems can be solved, in fact, such solutions form the basis
of lock-based software transactional memory
implementations [ST95,DSS06].
However,
Chapter
describes simpler ways of providing existence guarantees.
Paul E. McKenney 2011-12-16