这篇简短的论文标志着用普通编程语言表达并发处理器的同步化的长期兴趣的开始。本文考虑了通过代码关键部分的相互转换来实现不可分割操作的问题。Dijkstra后来的论文介绍了信号量的概念；信号量的动机之一是降低实现互斥所需的编程复杂性。（1966年5月出版的Don Knuth给编辑的一封信指出，Dijkstra的解决方案容易受到“饥饿”的影响——这意味着某个处理器可能会被意外地永远阻止进入关键部分。Knuth的无饥饿解决方案比这里的解决方案更复杂。)

许多相互通信方式受限的主要独立的顺序循环过程可以以这样一种方式进行，即在任何时刻，其中只有一个过程参与其循环的“关键部分”。

——P.J.D

引言

本文给出了一个问题的解决方案，据作者所知，该问题至少自1962年以来一直是一个悬而未决的问题，无论其可解性如何。本文由三部分组成：问题、解决方案和证明。虽然这个问题的设置起初看起来有些学术性，但作者相信，任何熟悉计算机耦合中出现的逻辑问题的人都会意识到这个问题确实可以解决这一事实的重要性。

相关问题

首先，考虑N台计算机，每台计算机都参与一个过程，就我们的目标而言，这可以看作是循环的。在每一个循环中，都会出现一个所谓的“临界区”，计算机必须以这样的方式编程，即在任何时刻，这N个循环过程中只有一个处于其临界区。为了实现关键部分执行的这种互斥，计算机可以通过公共存储器相互通信。把一个单词写进存储器，或者从存储器中无损地读一个单词，都是不可分割的操作；例如，当两台或多台计算机试图在同一公共位置同时进行通信（读或写）时，这些通信将相继进行，但顺序未知。

解决方案必须满足以下要求。

（a） 解决方案必须在N台计算机之间对称；因此，我们不允许引入静态优先级。

（b） 可以不假设N台计算机的相对速度；我们甚至不能假设它们的速度在时间上是恒定的。

（c） 若任何一台计算机在其关键部分之外停止运行，这不允许导致其他计算机的潜在阻塞。

（d） 如果不止一台计算机即将进入其关键部分，那么就不可能为它们设计出如此有限的速度，以至于决定哪一台计算机将首先进入其关键区域的决定将推迟到永远。换句话说，“After you”-“Afteryou”阻塞仍然是可能的构造，尽管不太可能，但不被视为有效的解决方案。

我们恳请有挑战性的读者在这里停下来，亲自尝试一下，因为这似乎是唯一能让我们感受到每一个计算机一次只能请求一条单向消息。只有这样，读者才能意识到这个问题并不是微不足道的。

解决方案

公共存储包括：

整数k将满足$1\le k\le N$ ，账单和c[i]仅由第i台计算机设置；他们将接受其他人的检查。假设所有计算机都在其关键部分之外启动，所有提到的布尔值数组都设置为true；k的起始值是无关紧要的。

第i台计算机（$1⩽i⩽N$）的程序为：

我们从观察解决方案是安全的开始，因为没有两台计算机可以同时处于其关键部分。进入关键部分的唯一方法是执行复合语句Li4，而不返回Li1，即在将自己的e设置为false之后，找到所有其他c的true。

证明的第二部分必须表明，不可能出现无限的“After you”-“After you”阻塞；例如，当没有一台计算机处于其关键部分时，循环（即跳回Li1）的计算机中至少有一台（因此恰好有一台）将被允许在适当的时候进入其关键部分。

如果第k台计算机不在循环计算机中，则bi[k]将为真，循环计算机将全部找到$k\ne i$。结果，其中一个或多个将在Li3中发现布尔值b[k]为真，因此一个或更多将决定赋值“$k:=i$”。在第一次赋值“$k:=i$”之后，b[k]变为假，并且没有新的计算机可以再次决定为k赋值。当对k的所有决定赋值都已执行时，k将指向循环计算机之一，并且暂时不会改变其值，即直到b[k]变为真，即直到第k台计算机完成其关键部分。一旦]c的值不再改变，第k台计算机将等待（通过复合语句Li4），直到所有其他c都为真，但这种情况肯定会出现，如果还没有出现的话，因为所有其他循环都会被迫将其c设置为真，因为它们会发现$k\ne i$。作者相信，这就完成了证明。

关于并发程序控制中一个问题的评述

亲爱的编辑：

我想谈谈一下迪科斯彻先生的解决方案[解决了计算机程序控制中的一个问题]，这是一个学术严谨的问题。在多台计算机上使用它。

如果只有两台计算机，算法可以简化为

迪科斯彻先生提出了一个解决实际问题的巧妙方案。

HARRIS HYMAN

Munitype

New York

关于并发编程控制中的问题的补充评论

亲爱的编辑：

迪科斯彻教授的巧妙构造[并发编程控制问题的解决方案，Comm.ACM 8（1965年9月，569]并不是一个很好的解决方案，与他在那里提出的问题几乎相同，Hyman先生对两台计算机的“简化”[Comm.ACM 9（1965年1月），45]根本不起作用。我希望通过这封信，我可以为人们解决一些如果他们要满足这些方法中的任何一种，他们会遇到的问题。

很容易找到Hyman先生“解决方案”的反例。“｛我相信一些读者可能能够理解他的程序，尽管在12行程序中有15个语法ALGOL错误〕如果最初k＝0，b〔0〕＝b〔1〕＝真，计算机1可以通过设置b〔1〕假来开始这个过程，随后发现b〔0〕是真的。然后，计算机0设置b〔0〕为假，并发现k＝0，于是它开始执行其关键部分。但计算机I现在设置k＝1，并同时执行它的关键部分。

Dijkstra教授的解决方案更难攻击；然而有一种确定的可能性是，当其他程序正在执行其关键部分时，一台或多台希望{0执行它的关键部分的计算机可能必须等待“直到永恒”。换句话说，尽管Dijkstra的算法确保所有计算机不会同时被阻止，但单个计算机仍有可能被阻止。（他决定在对问题的陈述中允许这种可能性，因为他对使用关键路段的平均需求相对较低的情况感兴趣；但肯定有许多应用中，单独阻断的可能性是不可接受的。）例如，假设时间以离散的间隔流逝；这个假设对于许多计算机系统都是有效的，并且对于这个例子来说是方便的，但不是严格必要的。假设计算机1正在循环，通过$b_k=false$ 和$k\ne i$查找，其他计算机很有可能在其他时间设置b{k]并更改k，这样计算机I就不会跳出循环。例如，如果k＝N＝2，计算机2可以在时间10n+2设置b[2}为真，然后返回L20，在时间10n＋9再次设置为假，对于任意多个N。

我尝试了十几种方法来解决这个问题，才找到我认为正确的解决方案。第i台计算机的程序（$1\leqq i\leqq N$），使用通用存储

为了证明这一点，首先观察到没有两台计算机可以同时位于其语句L3和L4之间，原因与Dijkstra算法中的情况相同。其次，观察到在所有计算机完成其关键部分计算之前，整个系统无法被阻止；如果在某一点之后没有计算机执行关键节，k的值将保持不变，并且随后希望执行关键节的第一台计算机（按照循环顺序k，k1，…，1，N，N-1，……，k+1）将不受任何限制。

最后，有必要证明，没有一台计算机会被拦截。这一点的证明并非微不足道，因为可以证明，一台计算机所处的不利环境可能需要等待2到1圈，而其他计算机在进行关键路段时，才能进入自己的关键路段。例如，如果N=4，假设计算机4位于L1，计算机1、2、3位于L2。

（i）计算机从L2（高速）转到L5

（ii）计算机2从L2转到L5，然后计算机1从L5转到L2：

（iii）计算机从1从L2转到L5，

（iv）计算机3从L2转到L5，然后计算机1从L5转到L2，然后计算机2从L5到L2；

（v），（vi），（vii）分别类似于（i），（ii），（iii）；

同时，计算机4已经不幸地错过了使其能够到达L2的k的瞬时值。

为了证明电脑$i_0$会在其到达L1后最终执行其关键部分，请注意，由于系统未被完全阻止，只有在至少有一台计算机能够经常任意执行其关键节时，$i_0$才能被阻止。但是，每当jo通过控制$i_0\ne 0$从L0到L5时，它在L1遇到的k值必须由计算机$k_0$设置，该计算机$k_0$在循环顺序N-1，....，2，1，N。中跟随$i_0$并在$j_0$之前。因此，在顺序中跟随$i_0$且在$j_0$之前的一些$k_0$也必须经常任意执行关键Bection。如果我们选择成为拥有这一财产的$i_0$的第一个继承人，这是一个矛盾。

为了避免有人写另一封信只是为了给出当有两台计算机时该算法的特殊情况，这里是计算机i的程序，在简单情况下，计算机j是唯一存在的其他计算机：

当N较大或可变时，上述算法不是很有效。如果我们修改计算机唯一不可分割的操作是信号读取或写入存储的基本假设，就可以很容易地设计出更有效的方法。例如，假设我们有一个公共存储器

（最初为零），并假设三个操作

都是不可分割的硬件操作。然后是第i台计算机的有效解决方案$1\leqq i\leqq N$ 是：

环路处的循环可以由中断处理；因此处理器可以在队列中等待时执行其他工作。这种方法比其他方法更“公平”，并且可以根据优先级进行修改。

DONALD E.KNUTH

Mathematics Department

California Institute of Technology

Pasadena,California