8.3 Lock-Based Existence Guarantees
Keywords: perfbook_html

#
8.3 Lock-Based Existence Guarantees

Figure: Per-Element Locking Without Existence Guarantees

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

Figure: Per-Element Locking With Lock-Based Existence Guarantees

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.