2.1 时间
- 线程是个状态机，其状态的转换称为事件。
- 事件是瞬间发生的，我们假设不同的事件在不同的时间点发生。
- 事件间隔有重叠时，称为 并发的。
2.2 临界区
- 某个时刻仅能够被一个线程执行的代码，称为临界区。
- 上面的特性，称为 互斥。
-
+ 互斥：不同线程的临界区之间没有重叠。
+ 无死锁：如果一个线程正在尝试获得一个锁，那个总会成功的获得这个锁。
+ 无饥饿：每个试图获得锁的线程最终都能成功。//无饥饿意味着无死锁。
//无饥饿特性不保证线程在进入临界区以前需要等待多长时间。
- 即使程序所使用的每个锁都满足无死锁特性，该程序也可能死锁。
2.3 双线程解决方案
2.3.1 LockOne算法
LockOne算法的缺陷：**LockOne算法在交叉执行的时候会出现死锁。若事件writeA(flag[A] = true)与writeB(flag[B] = true)在事件readA(flag[B]==flase)和readB(flag[A]==false)之前发生，那么两个线程都将陷入无穷等待。
2.3.2 LockTwo算法
LockTwo类存在的缺陷：当一个线程完全先于另一个线程执行的时候就会出现死锁。但是两个线程并发地执行，却是成功的。由此，我们看到LockOne与LockTwo算法彼此互补，于是将两者结合的算法Peterson算法实现了。
2.3.3 Peterson锁
Peterson锁算法：//双线程互斥算法
class Peterson implements Lock {
// thread-local index, 0 or 1
private volatile boolean[] flag = new boolean[2];
private volatile int victim;
public void lock() {
int me = ThreadID.get();
int he = 1 - me;
flag[me] = true; // I’m interested
victim = me; // you go first
while (flag[he] && victim == me) {}; // wait
}
public void unlock() {
int me = ThreadID.get();
flag[me] = false; // I’m not interested
}
}
- Peterson锁是满足互斥特性，是无饥饿，无死锁的。
2.4 过滤锁（分层策略）
算法代码：
class Filter implements Lock {
int[] level;
int[] victim;
public Filter(int n) {
level = new int[n];
victim = new int[n]; // use 1..n-1
for (int i = 0; i < n; i++) {
level[i] = 0; //[1]
}
}
public void lock() {
int me = ThreadID.get();
for (int i = 1; i < n; i++) { //attempt level 1 //[2]
level[me] = i;
victim[i] = me;
// spin while conflicts exist
while ((∃k != me) (level[k] >= i && victim[i] == me)) {}; //[3]
}
}
public void unlock() {
int me = ThreadID.get();
level[me] = 0;
}
}
说明： - n 元整数组level [], level[A]的值表示线程A正在尝试进入的层。
- 每个层都有一个victim[l] 域， 用来选出线程，“留守”本层。
