class FastPath implements Lock { private static ThreadLocal myIndex; private Loc

ID: 3884814 • Letter: C

Question

class FastPath implements Lock {

private static ThreadLocal myIndex;

private Lock lock;

private int x, y = 1;

public void lock() {

int i = myIndex.get();

x = i; // I’m here

while (y != 1) {} // is the lock free?

y = i; // me again?

if (x != i) // Am I still here?

lock.lock(); // slow path

}

public void unlock() {

y = 1;

lock.unlock();

}

Figure 2: Fast path mutual exclusion algorithm.(Figure 2 is the above code)
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. 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 when uncontended. Sketch an argument why they are right, or give a counterexample.

Explanation / Answer