理论部分
- 互斥性（critical section）
不同线程的关键区域不会交叉，即对于线程A 和线程B来说，要么 CS_A^j\rightarrow CS_B^k 成立，要么 CS_B^k\rightarrow CS_A^j 成立。
- 无死锁
如果有线程尝试获取锁，则这个线程会获取到锁的。
- 无饿死
每个尝试获取锁的线程最终都会获取锁的。
算法探究
LockOne算法
class LockOne implements Lock {
private boolean[] flag = new boolean[2];
// thread-local index, 0 or 1
private static ThreadLocal<Integer> myIndex;
public void lock() {
int i = ThreadID.get();
int j = i-1;
flag[i] = true;
while (flag[j]) {} // wait
}
public void unlock() {
int i = ThreadID.get();
flag[i] = false;
}
// Any class implementing Lock must provide these methods
public Condition newCondition() {
throw new UnsupportedOperationException();
}
public boolean tryLock(long time,
TimeUnit unit)
throws InterruptedException {
throw new UnsupportedOperationException();
}
public boolean tryLock() {
throw new UnsupportedOperationException();
}
public void lockInterruptibly() throws InterruptedException {
throw new UnsupportedOperationException();
}
}
- 满足互斥性
证明：反证法
线程A进入关键区可表示为read_A(flag[B]=false)，线程A退出临界区可表示为write_A(flag[A]=false) ；
线程B进入关键区可表示为read_B(flag[A]=false)，线程B退出临界区可表示为write_B(flag[B]=false) ；
已知CS_A^j不早于CS_B^k，则有read_B(flag[A]=false)早于write_A(flag[A]=false) ；显然有write_A(flag[A]=true)早于write_A(flag[A]=false)，则有read_B(flag[A]=false)早于write_A(flag[A]=true)，否则B肯定进入不了关键区，即write_A(flag[A]=true)早于read_B(flag[A]=false)早于write_A(flag[A]=false)。
已知CS_B^k不早于CS_A^j，类似的有：
read_A(flag[B]=false)\rightarrow write_B(flag[B]=true).
违反了区间早于偏序关系第一条：事件A早于事件A是不成立的。
- 如果线程并发执行，则会有死锁出现；
- 如果两个线程一前一后地交替执行，则不会有死锁；
LockTwo算法
class LockTwo implements Lock {
private int victim;
// thread-local index, 0 or 1
public void lock() {
int i = ThreadID.get();
victim = i; // let the other go first
while (victim == i) {} // spin
}
public void unlock() {}
// Any class implementing Lock must provide these methods
public Condition newCondition() {
throw new UnsupportedOperationException();
}
public boolean tryLock(long time,
TimeUnit unit)
throws InterruptedException {
throw new UnsupportedOperationException();
}
public boolean tryLock() {
throw new UnsupportedOperationException();
}
public void lockInterruptibly() throws InterruptedException {
throw new UnsupportedOperationException();
}
}
- 满足互斥性
证明：
已知CS_A^j不早于CS_B^k，则A肯定要进入关键区，有write_A(victim=A)早于write_B(victim=B)早于read_A(victim=B)成立；
已知CS_B^k不早于CS_A^j，则B要进入关键区，有write_B(victim=B)早于write_A(vicitim=A)早于read_B(victim=A)成立。
已出现矛盾，因为write_A(victim=A)早于write_B(victim=B)和write_B(victim=B)早于write_A(vicitim=A)同时成立，违反了区间早于偏序关系性质第二条：如果事件A早于事件B成立，则事件B早于事件A必不成立。
- 如果线程一前一后交替执行，则会有死锁出现；
- 如果线程并发执行，则不会有死锁
Peterson算法
class Peterson implements Lock {
private boolean[] flag = new boolean[2];
private int victim;
public void lock() {
int i = ThreadID.get();
int j = 1-i;
flag[i] = true;
victim = i;
while (flag[j] && victim == i) {}; // spin
}
public void unlock() {
int i = ThreadID.get();
flag[i] = false;
}
// Any class implementing Lock must provide these methods
public Condition newCondition() {
throw new UnsupportedOperationException();
}
public boolean tryLock(long time,
TimeUnit unit)
throws InterruptedException {
throw new UnsupportedOperationException();
}
public boolean tryLock() {
throw new UnsupportedOperationException();
}
public void lockInterruptibly() throws InterruptedException {
throw new UnsupportedOperationException();
}
}
