什么是死锁

拿着，然后等着

讲竞态条件时，我们养成了一个好习惯：要改什么，先把它拿住，用完之前其他人都得等着，就像排队用单间厕所一样。这样一来，两个人交错着把结果弄坏的事故就没了。
现在假设一件活需要两样资源，叫作工具 1 和工具 2，两样都到手才能干完。A 先拿工具 1，再等工具 2；B 先拿工具 2，再等工具 1。两人都只是按规矩各拿了一样，可另一样谁也拿不到。
拿到的不放，没有的就等。这种“拿着等”，就是一切麻烦的开头。

点两个按钮，让 A 和 B 各拿一样。A 拿着工具 1 等工具 2，B 拿着工具 2 等工具 1。两人都不松手，只等自己缺的那一样，于是谁也走不下去（红色）。

奇怪吧？两人都没做错什么，只是按竞态条件那一课说的安全办法，轮流拿了一样，可还是都停住了。
问题不在于拿，而在于“拿着互相等”这个形状。要把这个形状看得更清楚，不妨想一个熟悉的场景。

窄桥上迎面相遇的两个人

有一座窄得只能过一个人的桥。一个人从这头、另一个人从那头，同时踏上桥。两人朝中间走，正好迎面撞上。
要往前走，就得对方让开。可两人谁也不肯让出自己站的那一格：我先来的，我更急。谁都不退，两人就一直僵在桥中间。
桥上的每一格，就是前面的工具 1 和工具 2；两个人，就是 A 和 B。各自占着自己的位置、等着对方的位置，跟刚才看到的形状一模一样。

用两个按钮把 A 和 B 一格一格往中间挪。两人在桥中央碰面时，谁也不让，就再也走不动，停住了（红色）。

在桥上，两人一碰面就停住了。可卡住的不一定只有两个。三个、四个，甚至更多的人不是排成一列，而是围成一圈互相等，同样的停顿就会闹得更大。
这一次，我们让大家围着餐桌坐下，亲手让等待的圈合上。

圈一合上，所有人都停住

五个人围坐在餐桌旁，每两个相邻的人中间各放着一根筷子。吃饭要左右两根筷子，可大家约好了：都先拿左边的，再等右边的。
只有一两个人这样做，没什么问题：总有人能拿齐两根，吃完再放下。可要是大家同时拿起左边的筷子，每个人右边的筷子都在邻座手里。人人都在等邻座，等待绕桌子转了一整圈，又回到自己身上。
等待的箭头一旦连成这样一个闭合的圈，圈上的谁都永远动不了。窄桥上的两个人，变成了围着餐桌的一整圈人。

每点一次按钮，下一个人就拿起左边的筷子。第五个人也拿起的那一刻，圈就合上了：每个人右边的筷子都在邻座手里，全部停住（红色）。

圈合上的最后一步，原本好好运转的餐桌一下子整个冻住了。可怕的是，谁也没犯什么特别的错。大家都同样合情合理地先拿左边，结果整桌都停了。
那么，冻住的餐桌怎么化开？好在办法出奇地简单，有两条路。

解法：让一步，或者定好顺序

第一条路是让。圈上随便一个人，把手里拿着的先放下。等着他的那位邻座就能凑齐两根筷子，吃完再放下。一处松开，下一处跟着松开，堵塞像多米诺骨牌一样依次解开。因为圈上只要出现一个缺口，就不再是闭合的圈了。
第二条路更聪明：根本不让圈合上。给所有人同一条规矩：“谁都一样，永远先拿编号小的。”这样，没拿到工具 1 的人，也不会去拿工具 2，而是等着。大家都按同一个顺序拿，就不会有两个人交叉着面对面，圈也就根本形成不了。

先把圈合上让所有人都停住，再让其中一人让一步。他一放下手里的东西，圈就断了，从邻座开始依次松开，所有人又动了起来（绿色）。

让一步，是解开已经停住的圈；定好顺序，是让停顿根本不会发生。一个是出事之后的急救，一个是出事之前的预防。
两条路的关键是一样的：不让等待的圆圈合上。只要有一处断开，停顿就会重新变回流动。

归纳成一页

记住四点就够了。
第一，各自拿着一样、又互相等对方的，“拿着等”就开始了。第二，像窄桥上的两个人那样，面对面谁也不让，两个都会停住。
第三，这种停顿绕成一整圈、圈一合上，圈上的所有人都会停住，这就是死锁。第四，只要有人放下手里的东西让一步，或者事先约定所有人按同一顺序拿，圈就会断开或者根本形不成，事情又能流动起来。

按顺序点四个步骤，死锁从头到尾就归纳在一页里：拿着等、桥上对峙、合上的圈，以及靠让步和定顺序解开。

讲竞态条件时我们学到，一个一个轮流来就安全；这一次却看到，同样的轮流拿，反而可能让所有人都停住。同一件工具，好坏全看怎么用。
安全的排队和永远停住的死锁，只隔着一层纸。大家拿东西的顺序是否一致、有没有人懂得让一步，决定了站在这层纸的哪一边。
操作系统这一单元只剩最后一课了：从按下电源键到屏幕亮起，计算机是怎样自己醒过来的。