并发编程的艺术03-Bakery互斥锁算法
导读
本章会介绍Bakery互斥锁算法，涉及到并发下的公平性问题，有界计数器和无界计数器问题， 存储单元数量下界问题。
公平性
门廊区应该在有限步数内完成一种强约束条件。称这种约束为有界无等待演进特性。对于公平的定义：满足下面条件的锁称为先到先服务的：如果线程 A 门廊区的结束在线程 B 门廊区的开始之前完成，那么线程 A 比定不会被线程 B 赶超。
按照我们的惯例来举一个生活中的例子来帮助读者理解这种计算机术语都抽象描述。
大多数人都去银行办理过业务，如图1所示很多人都在等待，他们等待的依据是什么呢？总得有个先来后到吧，要不然有人插队岂不是要发生争吵了。于是银行想了一个办法给每一个来办理业务的顾客发一个号码，这个号码就是大家排队的依据。银行按照先到先服务（First-Come-First-Served）（这里的“先到”指的是谁先获取到号码而不是谁先进入银行）的准则来控制当前该叫到那个号码的持有者来办理业务。这种做法就是一种保障公平性的机制。在这个例子中银行中的取号机可以抽象为前文提到的"门廊区"，而客户坐在椅子上等待可以抽象为前文提到的"等待区"。
Bakery 算法
在了解了公平性之后对 Bakery 算法就很容易理解了，因为 Bakery 保证公平性的方式和前文中举的银行排号例子原理是一样的。每个线程在门廊区得到一个序号，然后一直等待，直到再也没有序号比自己更早的线程尝试进入临界区止。
lable[A] 是一个整数型，说明线程进入面包店的相对次数。
class BakeryLock implements Lock {
private boolean[] flag;
private int[] label;
private int n;
public BakeryLock(int n) {
this.n = n;
flag = new boolean[n];
label = new int[n];
for (int i = 0;i < n; i++) {
flag[i] = false;
label[i] = 0;
}
}
public void lock() {
int i = ThreadID.get();
flag[i] = true;
label[i] = max(label) + 1;
for (int k = 0; k < n; k++) {
while ((k != i) && flag[k] && ((label[k] < label[i]) || ((label[k] == label[i]) && k < i))) {
}
}
}
public void unlock() {
flag[ThreadID.get()] = false;
}
private int max(int[] elementArray) {
int maxValue = Integer.MIN_VALUE;
for (int element : elementArray) {
if (element > maxValue) {
maxValue = element;
}
}
return maxValue;
}
}
有界计数器和无界计数器
在理解了 Bakery 算法后，我们再来仔细看看这个算法中的问题。首先就是存在的一个 bug ，就是 label[i] 的值会出现溢出的可能。
lable 值是无限增长的，因此在生命周期很长的系统中不得不考虑溢出的问题。如果某个线程的 lable 在其他线程都不知情的情况下从一个很大的数返回到 0 ，那么公平性将被破坏。例如到2038年1月18日，Unix 的 time_t 数据结构将会溢出，因为其秒数值是从 1970 年 1 月开始计算的，而在那一刻将会超过 2 的 32 次方。大多数采用 64-bit 计数器的应用程序在其声明周期内是不可能发生这种“回零”问题的。
Bakery 算法保证公平性的做法是确保某个线程在另一个线程之前得到一个 lable 值，那么后一个线程的 lable 值一定比前者大。通过仔细观察 Bakery 算法代码，我们可以得出一个线程需要具备两种能力：
1. 读取其他线程的 lable （扫描）。
2. 为自己设置一个更大的 lable （标记）。
这时候的 Bakery 算法中的 lable 值获取看起来像是这样：这个数是随着时间无限向后增长的，显然它是无限的 ,直到出现溢出问题。
为了解决这个溢出问题我们考虑使用有界的 lable 值获取，类似这样（这是只有两个线程的情况）：
在这个有向环中是一系列的节点 n0 , n1 , ... , nk ,其中有一条边从 n0到n1，有一条边从n1到n2,最后一条边从n(k - 1) 到 nk ,并有一条边从nk返回n0。边定义结果集上的次序关系为：0 < 1 , 1 < 2 , 2 < 0。两个线程的 lable 在 0 ， 1 ， 2 三个节点中不断的轮转改变。
N 个 线程的情况较为复杂暂时不进行讨论，只是说明结论。
存储单元数量下界
还记得我们之前说过的么，会介绍一些经典但是不实用的互斥锁算法，Bakery算法就是其中之一。及时 Bakery 算法十分的简洁，无饥饿，无死锁，而且公平，那么它为什么不实用呢？最主要的问题是要读写 N 个不同的存储单元。（N 是线程的最大个数）。
那么是否有更好的基于读/写存储器的锁算法可以避免这种开销呢？答案是否定的。也就是说任何一种无死锁的锁算法在最坏情况下至少需要读/写 N 个不同的存储单元。正是因为如此，才促使我们的多处理器计算机中，增加了一些功能要比读/写更强大的同步操作，并以这些操作作为互斥算法的基础。
现在我们要说明为什么这种线性下界是解决互斥问题时锁固有的。要记得一点只能通过读/写指令访问存储单元具有一个重要限制：一个线程向某个指定单元写的任何信息，在其他线程读取之前可能会被覆盖。下面是证明过程
到这里Bakery算法就讲完了，希望对你有帮助，如果觉得有收获还请点击"再看"自持作者。本人才疏学浅，如果文中有不当之处还请留言指正。
看完本文有收获？请分享给更多人
微信关注「黑帽子技术」加星标，看精选 IT 技术文章
