8.3 Lock-Based Existence Guarantees

Figure: Per-Element Locking Without Existence Guarantees
\begin{figure}{ \scriptsize
\begin{verbatim}1 int delete(int key)
2 {
3 int...
...nlock(&p->lock);
13 kfree(p);
14 return 1;
15 }\end{verbatim}
}\end{figure}

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
\begin{figure}{ \scriptsize
\begin{verbatim}1 int delete(int key)
2 {
3 int...
...spin_unlock(sp);
17 kfree(p);
18 return 1;
19 }\end{verbatim}
}\end{figure}

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