8.3、锁的进化：金鱼生存
左怡和尤尔两个人合住一套公寓，共同养了一条金鱼。该金鱼每天进食一次。两个人想把金鱼养活，一天只喂一次，也只能喂一次。如果一天内两人都喂了鱼，鱼就会胀死。如果一天内两人都没有喂鱼，鱼就会饿死。
方法一：为了把鱼养好，既不让鱼胀死，也不让鱼饿死，做出如下约定。
(1)每天喂鱼一次，且仅一次
(2)如果左怡喂了鱼，尤尔今天就不能喂；反之亦然；
(3)如果左怡没有喂鱼，尤尔今天就必须喂鱼；反之亦然。
要想让鱼活着，左怡和尤尔就必须合作。当然，最简单的情况是不进行任何沟通，每个人觉得需要喂鱼时，查看一下鱼的状态：如果感觉到鱼没有进食，则喂鱼；否则不喂。
图8-3时在没有同步的情况下左怡和尤尔执行的程序。
|
左怡： If(noFeed) { Feed fish; } |
尤尔： If(noFeed) { Feed fish; } |
如果判断noFeed的值呢？程序没有给出，只能依靠左怡和尤尔的高超养鱼技术判断鱼是否需要进食。如果两人的养育技术不达标，那么，鱼会饿死。
假设，两人的养育技术高超，那么，鱼就一定会活吗？答案时否定的。
由于线程的执行可以任意穿插，左怡可以先检查鱼发现没有喂，就准备喂鱼。但就在左怡准备喂但尚未喂食的时候，程序切换，轮到尤尔执行。尤尔一看，鱼还没有喂(确实如此)，就喂鱼。在喂完鱼后，线程再次切换到左怡。此时左怡从检查完鱼状态后的指令开始执行，就喂鱼。因为鱼一天内被喂了2次，鱼死了。
8-4所示：
|
事件时序表 左怡： |
尤尔： |
|
13:00 look at the fish(noFeed) |
|
|
13:05 |
look at the fish(noFeed) |
|
13:10 |
Feed fish; |
|
13:25 feed fish |
|
|
Fish over eat! |
|
图8-4 没有同步情况下左怡和尤尔喂鱼程序的可能结果
为什么这个程序会出现鱼胀死的情况呢？因为左怡和尤尔两个人同时执行了同一段代码(if (noFeed))。两个或多个线程争相执行同一段代码或访问同一资源的现象称为竞争。这个可能造成的共享代码段或资源称为临界区(cirtical section)。
当然，我们知道，在单核情况下，两个线程不可能真的在同一时刻执行。但有可能在同一时刻两个线程都在同一段代码上。这个例子里有竞争的时代码，是代码竞争。如果是两个线程同时访问一个数据就叫数据竞争。图8-3的程序造成鱼胀死就是因为两个线程同时进入了临界区。
以人类进化来比喻，图8-3种的程序只相当于氨基酸阶段，胡乱竞争，并不具备任何协调能力。
8.3.1、变形虫阶段
要防止鱼胀死，就需要防止竞争。要想避免竞争，就需要防止两个或多个线程同时进入临界区。要达到这一点，就需要某种协调手段。
协调的目的就是在任何时刻都只能有一个人在临界区里，这称为互斥(mutual exclusion)。互斥就是说一次只有一个人使用共享资源，其他人皆排除在外，并且互斥不能违反前面给出的进程模型。
因此，正确互斥需要满足4个条件:
(1)不能有两个进程同时在临界区里面。
(2)进程能够在任何数量和速度的CPU上正确执行。
(3)在互斥区域外不能阻止另一个进程的运行。
(4)进程不能无限制的等待进入临界区。
如果任何一个条件不满足，那么设计的互斥就是不正确的。
那么，有办法确保一次只有一个人在临界区吗？有，让两个线程协调。
最简单的协调办法是交谈。问题是左怡和尤尔不一定有时间碰面。那么剩下的办法是留字条。
同步机制(留字条)：左怡和尤尔商定，每个人在喂鱼之前先留下字条，告诉对方自己将检查鱼缸并在需要时喂鱼。
如图8-5所示：同步机制1：留字条
|
左怡： If(nofeed) { Leave note; If(noFeed) { Feed fish; } Remove note; } |
尤尔： If(nofeed) { Leave note; If(noFeed) { Feed fish; } Remove note; } |
上述机制能否避免鱼胀死呢？不能。
如果左怡和尤尔交叉执行上述程序，还是会造成鱼胀死的结局。这是因为使用的时互斥手段，即留字条，并没有达到互斥的目的。因为字条并没有防止左怡和尤尔两个人同时进入临界区。
当然，与第一个解决方案比起来，本方案有所改善，即鱼胀死的概率降低了。
只有在左怡和尤尔严格交叉执行的情况下，才可能发生鱼胀死的现象。因此，我们并没有白费力气。
|
事件时序表： 左怡 3:00 检查字条(没有) 3:05 — 3:10 — 3:25 留下字条 3:50 查看鱼(没有喂过) 4:05 — 4:10 — 4:25 喂鱼 鱼胀死 |
尤尔 — 检查字条(没有) 留下字条 — — 查看鱼(没有喂过) 喂鱼 |
图8-6 第1种同步机制的一种可能结果
此程序虽然加入了一点同步机制，但这个机制太原始，达不到真正的同步目的。以人类进化来比喻，此程序相当于变形虫阶段。
8.3.2、鱼阶段
8-6不能解决问题的原因：我们先检查有没有字条，后留字条。这样造成一个空当，使得检查字条和留字条之间的空隙。那我们就修改一下顺序，先留字条，再检查有没有对方的字条。如果没有对方的字条，那么就喂鱼，喂完鱼把字条拿掉。不过这种方法需要区分字条时谁的。
程序如图8-7：同步机制2：改进留字条的机制
|
左怡： Leave noteZuo; If(no noteYou) { If(noFeed) { Feed fish; } } Remove noteZuo; |
尤尔： Leave noteYou; If(no noteZuo) { If(noFeed) { Feed fish; } } Remove noteYou; |
上述程序怎么样？鱼还会不会胀死呢？答案时是不会了。因为无论按照什么顺序穿插，总有一个人的留字条指令在另一个人的检查字条指令前执行，从而将防止两个人同时进入临界区。因而鱼不会因为两个人都喂而胀死。
那这个程序是成功了。不过，不要过早下结论。我们来看一下，如果两个人穿插执行会出现什么结果。这个时候问题出现了。由于穿插执行，因此在两者检查字条时，如果发现对方已经留有字条，从而都不会喂鱼，这个时候鱼饿死。
如图8-8所示：
|
事件时序表： 左怡 3:10 — 3:25 留字条—左怡 3:50 检查字条—尤尔(有) 4:05 — 4:10 — 4:25 移除字条—左怡 没有人喂鱼，鱼死 |
尤尔 留字条—尤尔 — — 检查字条—左怡(有) 移除字条—尤尔 — |
由于存在饿死这种可能性，这个程序似乎并没有任何改善。难道我们这个力气白费了吗？没有。因为比起胀死来说，饿死是一种改善。对于一个计算机系统来说，饿死也是好于胀死。如果胀死，则程序的运行有可能出错：几个线程同时获得同一个资源，出现不一致及结果不确定性几乎是难以避免的。
但如果是饿死，即使大家都拿不到某个资源，线程处于饥饿状态，至少是停止推进，而这不一定产生错误结果，或许知识推迟结果的出现。
虽然饿死比胀死好受一点，但毕竟还是存在死的可能，还是在很原始的阶段。以人类进化来比喻，相当于鱼阶段。因此，我们需要继续进化，或者说努力。
8.3.3、猴阶段
那么鱼为什么会饿死呢？是因为没有人进入临界区。虽然互斥确保了没有两个人同时进入临界区，但这种没有人进入临界区的情况则有点互斥过了头。要想鱼不饿死，除了互斥之外，还要保证有一个人进入临界区来喂鱼。那用什么办法来保证呢？
办法就是让某个人等着，知道确保有人为了鱼才离去，不要一见对方的字条就开溜走人。也就是说，在两个人同时留下字条的情况下，必须选择某个人来喂鱼。这样就得到第3种同步方式。
如图8-9：同步机制3：循环等待
|
左怡： Leave noteZuo; While(noteYou) { Do nothing; { If(noFeed) { Feed fish; } } } Remove noteZuo; |
尤尔： Leave noteYou; If(no noteZuo) { If(noFeed) { Feed fish; } } Remove noteYou; |
鱼显然不会胀死，因为使用的办法包括了第2种同步方式。那么鱼会不会饿死呢？也不会。因为前面说过，鱼饿死的唯一情况是两个人同时留字条，并且又都走人。而上述程序在两个人都留字条的情况下，左怡不会走人，而是一直等待直到对方删除字条后，再检查鱼有没有喂，并在没有喂的情况下喂鱼。因此，该同步方式既防止了胀死，又防止了饿死。
我们终于有了个能正确养鱼的程序了，一切似乎大功告成。但真的吗？
我们终于进化到了猴子阶段，能够有一定的组织，不会饿死，也不会胀死了。但这就足够了吗？
8.3.4、锁
图8-9的第3种同步机制虽然正确，但存在很多问题。
首先是程序不对称。左怡执行的程序和尤尔执行的程序并不一样。那么不对称有什么问题呢？当然有。首先，上述程序因为不对称而不美观。其次，不对称造成程序编写困难。为了追求程序的正确性，即使是做同样操作的线程也得编写的不同，这自然就增加编程的难度。最后，不对成还造成程序证明的困难。
要想从理论上证明图8-9种程序的正确性是一件十分复杂的事情。这一点研究程序证明的人是很清楚的。
上述程序的另一个大问题是浪费。上述程序种左怡执行的循环等待是一种很大的浪费。但浪费还不是循环等待的唯一问题，它还可能造成CPU调度的优先级倒挂。优先级倒挂就是高优先级的线程等待低优先级的线程。
例如，如果尤尔先于左怡启动，留下字条后正准备检查是否有左怡的字条时，左怡启动。由于左怡的优先级高于尤尔，因此左怡获得CPU，留下字条，进入循环等待。由于左怡的优先级高，因此尤尔将无法获得CPU而完成剩下的工作，进而造成左怡始终处于循环等待阶段无法推进。这样高优先级的左怡就被低优先级的尤尔所阻塞。由于优先级倒挂完全违反了设立优先级的初衷，就像总统得挺平民指挥似的，因此令人无法容忍(至少让总统无法容忍)。
那我们有没有更好的办法来解决喂养金鱼的问题呢？有，就是继续对同步方案进行改进。
那么在哪一个方案的基础上改进呢？自然想到是最后一个方案，因为它已经满足了鱼既不饿死也不胀死的条件，无非就是不好看和循环等待。关键是这两点可以改进吗？答案是否定的。循环等待不能去掉，已去掉变成第2个方案：若想使其对称、美观，就需要将尤尔改为和左怡同样，而这样同样会造成鱼饿死的可能。因此，对最后一个方案进行修改似乎不是明智之举。
看来，我们这种零敲碎打似的推进模式已经走到头了，需要新的思路了。
新的思路就是直接对最开始的两个方案进行修改。由于最开始的两个方案均达不到既不饿死又不胀死的条件，因此我们自然选择一个较为美观、简单的方案来修改。在两个方案之间，第1个方案完全对称，而第2个方案不完全对称，因为每个人的字条不同。因此，我们选择第1个方案作为修改的基础。但如何修改呢？
要想知道如何修改，就得知道第1个方案为什么不满足条件。
那么第1个方案为什么不满足条件呢？我们说过，是因为检查字条和留字条是两个步骤，中间留有被别的线程穿插的空当，从而造成字条作用的丧失。我们就想，能否将这两个步骤并为一个步骤，或者变成一个原子操作，使其中间不留空挡，不就解决问题了吗？
换句话说，我们之所以到现在还没把金鱼的问题处理掉，是因为我们一直在非常低的层次上打转。因为我们试图工作的层面是鱼和鱼缸这个层面，即留字条是为了防止两个人同时查看鱼和鱼缸。我们仅仅在指令层上进行努力。由于控制的单元是一条条指令，因此对指令之间的空当无能为力。而解决这种问题的办法就是提高抽象的层次，将控制的层面上升到对一组指令的控制。
例如，在金鱼问题里，如果我们将抽象层次从保护鱼和鱼缸的层次提高到保护防止鱼缸的房间的层次，这个问题就可以解决。即设计一种同步措施，使得在任何时候只能有一个人进入防止鱼缸的房间。这样，检查字条和留字条的两部操作就变成将房间锁上的一步操作。
那么如何保证这个房间一次只进入一个人呢？我们先看看生活当中我们是如何确保一个房间只能进入一个人的。例如，两个教师都想使用同一个教室来为学生补课，怎么协调呢？进到教室后将门锁上，另外一个教师就无法进来使用教室了。即教室时用锁来保证互斥的。那么在操作系统里，这种可以保证互斥的同步机制称为锁。
有了锁，金鱼问题就可以解决了。当一个人进来想喂鱼时，就把方有鱼缸的房间锁住。这样另外一个人进不来，自然无法喂鱼。
如图8-10所示：同步机制4：锁
|
左怡： Lock() If(noFeed) { Feed fish; } Unlock; |
尤尔： Lock() If(noFeed) { Feed fish; } Unlock; |
如图8-11所示： 同步种的锁与现实生活种锁的概念非常相似
从上面程序我们可以看到，基于锁的互斥性，左怡和尤尔只能有一个人进入房间来喂鱼，因此鱼不会胀死。并且，如果两人都同时执行上述程序时，由于先拿到锁的人会进入房间来喂鱼，因此鱼也不会饿死。更为重要的时，两个人执行完全相同的代码。既对称，也容易写，证明起来也不困难。这样，金鱼问题从而得到解决。
以人类进化来比喻，上述程序相当于人阶段了。
从图8-10可以看出，锁有两个基本操作：闭锁和开锁。闭锁就是将锁锁上，其他人进不来；开锁就是你做的事情做完了，将锁打开，别的人可以进去了。
闭锁操作有两个步骤，分别如下：
1)等待锁达到打开状态。
2)获得锁并锁上。
开锁操作很简单，就是一步：打开锁。
显然，闭锁的两个操作应该是原子操作，即不能分开。不然，就会留下穿插的空当，从而造成锁的功效的丧失。那么，我们是如何让闭锁的两个操作称为一个原子操作的呢？(详见第10章)。这里，我们先来仔细看看锁的机制。
在第一种解决方案里的字条，从某种意义上来说，就是一把锁，只是这把锁没有将资源锁住。那为什么没有锁住呢？这是因为这把锁不具备一把正常锁所应该具备的特性：
(1)锁的初始状态是打开状态；
(2)进临界区前必须获得锁；
(3)出临界区时必须打开锁；
(4)如果别人持有锁则必须等待。
而字条解决方案违反了第4个条件，即在别人持有锁(留下字条)的情况下，也照样进入临界区(因为检查是否有别人持有锁在别人留锁之前进行)。因此，则个字条无法起到锁的作用，即是一把破锁。
在使用了正常的锁之后(8-10)，整个程序就可以正确运行了。程序既漂亮，而且，想形式化证明这个程序也是很容易的事情。
那么这个程序有什么问题吗？如果左怡正在喂鱼的话，尤尔能干什么事情呢？只能等待(等待锁变为打开状态)。如果左怡喂鱼的动作很慢，尤尔等待的时候就会很长。二者种繁忙等待不仅将造成浪费，而且将降低系统效率。那么，有办法消除锁的繁忙等待吗？答案是否定的，因为锁的特性就是在别人持有锁的情况下需要等待。不过还是可以减少繁忙等待的时间长度。
怎么缩短等待的时间呢？
仔细分析发现，左怡喂鱼并不需要在持有锁的状态下进行。我们就希望喂鱼的这段时间不要放在锁里面，而是获得锁后留下字条说他喂鱼去了，然后释放锁，再喂鱼。而尤尔再拿到锁后先检查有没有字条，有字条就释放锁，干别的去。没有就留字条，然后释放锁，再喂鱼。这样，由于持锁的时间只限于设置字条的时间，因此，对方循环等待的时间会很短，而真正的操作(在这里是喂鱼)则随便多慢也没有问题了。
如图8-12所示：同步机制5：减少锁的繁忙等待时间
|
左怡： Lock() If(noNoteYou) { Leave noteZuo; Unlock(); If(noNoteYou) { If(noFeed) { Feed fish; } Remove note; } } |
尤尔： Lock() If(noNoteZuo) { Leave noteYou Unlock(); If(noNoteZuo) { If(noFeed) { Feed fish; } Remove note; } } |
图8-12中的程序比起图8-10中的程序，已经好多了。因为在锁上的繁忙等待时间已经很少了。但不管怎样，终究还是需要等待的。那有没有办法不用进行任何繁忙等待呢？有，答案就是睡觉与叫醒，即sleep和wake up。