Subject:Concurrency The question is rfom the book \"The art of multiprocessor pr
ID: 664500 • Letter: S
Question
Subject:Concurrency
The question is rfom the book "The art of multiprocessor programming"
Chapter:7
Exercise 87. Prove that the CompositeFastPathLock implementation guarantees
mutual exclusion, but is not starvation-free.
public class CompositeFastPathLock extends CompositeLock {
2 private static final int FASTPATH = ...;
3 private boolean fastPathLock() {
4 int oldStamp, newStamp;
5 int stamp[] = {0};
6 QNode qnode;
7 qnode = tail.get(stamp);
8 oldStamp = stamp[0];
9 if (qnode != null) {
10 return false;
11 }
12 if ((oldStamp & FASTPATH) != 0) {
13 return false;
14 }
15 newStamp = (oldStamp + 1) | FASTPATH;
16 return tail.compareAndSet(qnode, null, oldStamp, newStamp);
17 }
18 public boolean tryLock(long time, TimeUnit unit)
19 throws InterruptedException {
20 if (fastPathLock()) {
21 return true;
22 }
23 if (super.tryLock(time, unit)) {
24 while ((tail.getStamp() & FASTPATH ) != 0){};
25 return true;
26 }
27 return false;
28 }
Figure 7.25 CompositeFastPathLock class: the private fastPathLock() method returns
true if it succeeds in acquiring the lock through the fast
Explanation / Answer
CompositeFastPathLock implementation guarantees mutual exclusion,
Property of mutual exclusion,
Mutual exclusion is only one of several properties of interest. After all, as we noted earlier, a protocol in which Alice and Bob never release a pet satisfies the mutual exclusion property, but it is unlikely to satisfy their pets. Here is another property of central importance. First, if one pet wants to enter the yard, then it eventually succeeds. Second, if both pets want to enter the yard, then eventually at least one of them succeeds. We consider this deadlock-freedom property to be essential.
To check mutual exclusion condition
1) Remove the top node 1 levels from the protocol,
2) Modify the test for progress by requiring that there are no more than top node same level or higher (counting the testing thread itself)
private boolean fastPathUnlock()
{
int oldStamp, newStamp;
oldStamp = tail.getStamp();
if ((oldStamp & FASTPATH) == 0)
{
return false;
}
int[] stamp = {0};
QNode qnode;
do
{
qnode = tail.get(stamp);
oldStamp = stamp[0];
newStamp = oldStamp & (ˆFASTPATH);
}
while (!tail.compareAndSet(qnode, qnode, oldStamp, newStamp));
return true;
}
public void unlock()
{
if (!fastPathUnlock())
{
super.unlock();
};
}
The CompositeFastPathLock class’s unlock() method first calls fastPathUnlock() . If that call fails to release the lock, it then calls the CompositeLock’s unlock() method