作者：Edsger W. Dijkstra 1965
原文：https://www.di.ens.fr/~pouzet/cours/systeme/bib/dijkstra.pdf
译者：phylips@bmy 2018-9-27
相互之间可以通过有限方式进行通信的一组独立的sequential-cyclic进程，可以通过某种方式使得在任意时刻它们只有一个进入它们自己的“critical-section”。
导引
本文给出了上述问题的一个解决方案，据作者所知，至少从1962年开始该问题就作为一个开放性问题提出，甚至不知道它是否可解。本文由如下三部分组成：问题、解决方案和证明。尽管该问题起初可能看起来有些偏理论，但是作者相信对于那些熟悉因计算机耦合性产生的逻辑问题的人来说，将会意识到该问题的可解所具有的重要意义。
问题
假设有N个计算机，每个计算机内部都有一个进程，方便起见，可以认为这些进程都是在不断地循环执行一段逻辑。在每个执行周期内都有一个“critical-section”，需要以某种方式对这些计算机进行编程，以确保任意时刻这个N个进程中只有一个会处于“critical-section”。为了实现临界区的互斥执行，这些计算机相互之间可以通过一个共享存储模块进行通信。针对该存储模块的一个以word为单位的读写操作可以认为是原子的，比如当有两个或更多的计算机试图同时读写同一个存储单元时，这些操作会以未知顺序依次完成。
针对该问题的解决方案必须满足如下要求：
- 该解决方案对于N个计算机来说必须是对称的，这意味着不能引入静态的优先级
- 不能对这个N个计算机的相对执行速度有任何假设，甚至不能假设它们的执行速度是一个常数时间
- 如果有多于一个的计算机要进入到临界区，必须能在有限时间内决定由哪一个首先进入临界区。换句话说，对于那些可能会出现“after you”-“after you”阻塞情况的解决方案来说，就算无法检测出来，也不会被认为是合法的。
现在我们希望读者可以在此处停一下然后自己尝试一下解决这个问题，只有这样才能对一台计算机一次只能发送一个单向消息请求这一事实是多么的棘手有一个感觉，也才能意识到解决这个问题并非易事。
解决方案
共享存储模块包含如下变量：
“Boolean array b, c[l:N]; integer k”
其中整数k的取值范围为[1,N]，同时对于b[i]和c[i]来说它们的值只能由第i个计算机进行设置；但是它们可以被其他计算机进行读取。假设开始的时候所有的计算机都在临界区外面，并且前面提到的boolean数组的所有值均为true；k的初始值为任意值。第i个计算机的程序代码如下：
{!为了方便代码阅读理解，我们对上面的程序按照C语言风格重写如下：
int j;
Li0: b[i]= false;
Li1: if (k != i)
{
c[i] = true;
Li3: if (b[k])
{
k = i;
}
goto Li1;
}
Li4: else
{
c[i] = false;
for (j = 1; j <=n; ++j)
{
if (j != i && !c[j])
{
goto Li1;
}
}
}
critical section;
c[i] = true;
b[i] = true;
remainder of the cycle in which stopping is allowed;
goto Li0
}
证明
首先我们可以观察到该解决方案是安全的，因为不可能同时有两个计算机进入临界区。因为进入临界区的唯一方式是上面的组合语句Li4执行的时候不会跳回Li1，即在它将自己在数组c中的值置为false后，发现c的其他值均为true。{!假设有两个计算机设为i和j在同时运行到该部分代码，那么可能的执行顺序有如下几种(i和j交换后可以得到另外三种执行序列)：
c[i] = false c[j] = false read c[j] read c[i]
c[i] = false read c[j] c[j] = false read c[i]
c[i] = false c[j] = false read c[i] read c[j]
对于所有可能的执行顺序来言，不可能同时出现两个计算机，设置了自己的值为false后，还会认为对方为true。因为只要有一个将自己设置为false之后，其他人就不可能再读到true，那么也就不可能再进入。但是它自己也可能无法进入临界区，因为在它读取c[j]之前可能c[j]也被置为了false}
此外我们还要证明它不会出现“after you”-“after you”这种被无限阻塞的情况。即在没有计算机进入临界区的情况下，对于那些还在执行循环(重新跳回Li1分支执行)的计算机{!对应的可能还有一部分计算机停止在Li4的“remainder of the cycle in which stopping is allowed;”部分，如上面的程序所示，这部分计算机既不在临界区，也不在执行循环而是停在那里}来说在一定时间内至少会有一个计算机会进入临界区。
如果第k个计算机不属于执行循环的计算机集合，那么意味着b[k]值为true，同时对于那些正在执行循环的计算机来说k != i成立，这样至少会有一个计算机在执行Li3时会发现b[k]为true，同样地至少会有一个计算机执行k = i，当第一个k=i赋值动作完成后，后面将不会再有新的计算机决定将k设置为i。当所有针对k的赋值动作完成后，k的值将指向正在执行循环的那些计算机中的某一个，并且此后直到b[k]变为true之前k的值将不再变化，也就是说要一直等到第k个计算机从临界区出来之后。只要k的值不再变化，那么第k个计算机将会等待其他计算机对应的数组c中的值变为true，这个条件最终一定会被满足，即使当前还不满足。因为所有其他正在执行循环的计算机将会发现k != i，然后把它们对应的数组c中的值设为true。到此为止，证明完成。