Spin locks and contention

Prev: University of consensus Next: Monitors and blocking synchronization

Exercises

Exercise 7.1. The following shows an alternative implementation of CLHLock in which a thread reuses its own node instead of its predecessor node. Explain how this implementation can go wrong, and how the MCS lock avoids the problem even though it reuses thread-local nodes.

public class BadCLHLock implements Lock {
  AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());
  ThreadLocal<QNode> myNode = new ThreadLocal<QNode>() {
    protected QNode initialValue() {
      return new QNode();
    }
  };
 
  public void lock() {
    QNode qnode = myNode.get();
    qnode.locked = true;
    QNode pred = tail.getAndSet(qnode);
    while (pred.locked) {}
  }
 
  public void unlock() {
    myNode.get().locked = false;
  }
 
  static class QNode {
    volatile boolean locked = false;
  }
}

---

Exercise 7.2. Imagine $n$ threads, each of which executes method foo() followed by method bar(). Suppose we want to make sure that no thread starts bar() until all threads have finished foo(). For this kind of synchronization, we place a barrier between foo() and bar().

First barrier implementation: We have a counter protected by a test-and-test-and-set lock. Each thread locks the counter, increments it, releases the lock, and spins, rereading the counter until it reaches $n$.

Second barrier implementation: We have an $n$-element Boolean array b[0..n - 1], all initially false. Thread 0 sets b[0] to true. Every thread i, for $0<i<n$, spins until b[i - 1] is true, sets b[i] to true, and then waits until b[n - 1] is true, after which it proceeds to leave the barrier.

Compare, in 10 lines, the behavior of these two implementations on a bus-based cache-coherent architecture. Explain which approach you expect will perform better under low load and high load.

---

Exercise 7.3. Show how to eliminate the separate cluster-local field that records whether the lock is passed locally by recording this information directly in each QNode, as described in Section 7.7.3.

---

Exercise 7.4. Prove that the CompositeFastPathLock implementation guarantees mutual exclusion, but is not starvation-free.

---

Exercise 7.5. Design an isLocked() method that tests whether any thread is holding a lock, but does not acquire the lock. Give implementations for:

• a test-and-set spin lock,
• the CLH queue lock,
• the MCS queue lock.

---

Exercise 7.6. Hard: where does the $\Omega (n)$ space complexity lower bound proof for deadlock-free mutual exclusion of Chapter 2 break when locks are allowed to use read-modify-write operations?

Prev: University of consensus Next: Monitors and blocking synchronization