Subject:Concurrency The question is from the book called \"art of multiprocessor
ID: 664491 • Letter: S
Question
Subject:Concurrency
The question is from the book called "art of multiprocessor programming"
Chapter:2 Mutual Exclusion
Exercise 15. In practice, almost all lock acquisitions are uncontended, so the most
practical measure of a lock’s performance is the number of steps needed for a
thread to acquire a lock when no other thread is concurrently trying to acquire
the lock.
Scientists at Cantaloupe-Melon University have devised the following “wrapper”
for an arbitrary lock, shown in Fig. 2.16. They claim that if the base Lock class
provides mutual exclusion and is starvation-free, so does the FastPath lock, but
it can be acquired in a constant number of steps in the absence of contention.
Sketch an argument why they are right, or give a counterexample.
1 class FastPath implements Lock {
2 private static ThreadLocal<Integer> myIndex;
3 private Lock lock;
4 private int x, y = -1;
5 public void lock() {
6 int i = myIndex.get();
7 x = i; // I’m here
8 while (y != -1) {} // is the lock free?
9 y = i; // me again?
10 if (x != i) // Am I still here?
11 lock.lock(); // slow path
12 }
13 public void unlock() {
14 y = -1;
15 lock.unlock();
16 }
17 }
Explanation / Answer
Critical sections of different threads do not overlap. For
threads $A$ and $B$, and integers $j$ and $k$, either $CS_A^j checkexception CS_B^k$ or $CS_B^k checkexception CS_A^j$.
Suppose not. Then there exist integers $j, k$ such that $CS_A^j CS_B^k$ and
$CS_B^k CS_A^j$. Inspecting the code, we see that
w_A(turn = A) checkexception r_A(busy == false) checkexception w_A(busy = true) checkexception r_A(turn == A)
w_B(turn = B) checkexception r_B(busy == false) checkexception w_B(busy = true) checkexception r_B(turn == B)
r_A(turn == A) checkexception w_B(turn = B)
If we only look at the last loop iteration, in which $A$ successfully enters the critical
section, then the last equation must hold. However, this implies
$w_A(busy = true) checkexception r_A(turn == A) checkexception w_B(turn = B) checkexception r_B(busy == false)
Since busy is never reset to false, this is a contradiction
Therefore the protocol must satisfy mutual exclusion.