多处理器计算机如何正确地执行多任务程序

来自 Leslie Lamport 于 1979 年发表的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

许多大型计算机实际上以不同于程序指定的顺序执行操作。如果执行结果与按顺序执行程序步骤产生的结果相同，那就认为执行正确。对于多处理器计算机来说，每个处理器的执行正确并不能保证整个程序的正确执行。还需要额外的条件来保证这种计算机正确地执行多进程程序。

高速的处理器可能会以不同于程序指定的顺序执行操作。如果处理器满足以下条件：执行的结果与按程序指定的顺序执行操作相同，执行正确就得到了保证。满足这个条件的处理器可被称为顺序的。假设一台由这种处理器组成的计算机，访问一片共享内存，设计和证明多进程算法的正确性满足以下条件：任意执行结果都与所有处理器按某种顺序执行操作相同，每个处理器的操作以程序指定的顺序出现在这个序列中。满足这个条件的多处理器可被称为顺序一致的。每个单独的处理器是顺序的并不能保证多处理器计算机是顺序一致的。本文我们描述了将顺序的处理器与内存模块相连接的方法，保证了多处理器执行结果的顺序一致。

我们假设计算机由一组处理器和内存模块组成，处理器之间只通过内存模块通信（任何特殊的通信寄存器也被看作是内存模块）。我们要关注的唯一的处理器操作是向内存模块发送读写请求。每个处理器都发出一串这样的请求（有时必须等待请求被执行，但这不是重点）。

我们通过一个简单的双进程互斥协议来说明。每个进程都包含一个关键部分，该协议的目的是确保任意时间只有一个进程可以执行其关键部分。协议如下：

• 进程 1

  a = 1
  if b == 0 then critical section;
  a = 0
  else ... fi
  

• 进程 2

  b = 1
  if a == 0 then critical section;
  b = 0
  else ... fi
  

else 语句保证最终访问到关键部分，但这不是重点。该协议保证了对关键部分的互斥访问。因此，当这个双进程程序由顺序一致的多处理器计算机来执行时，两个处理器无法同时执行其关键部分。

我们首先观察到一个顺序的处理器可以按任意顺序执行 b = 1 和进程 1 的读取 b 操作。但是很容易看到先执行读取 b 操作会导致一个错误——然后两个进程可以同时执行其关键部分。这就引出我们对多处理器计算机的第一个要求：

要求 1：每个处理器按程序指定的顺序发出内存请求。

由于一个数值只有在计算后才可被存储，因此满足要求 1 就变复杂了。处理器往往在它知道数值被存储好之前就已经准备好发送内存读取请求了。为了尽量减少等待，处理器可以向内存模块发送存储请求，不指定要存储的值。当然存储模块在它收到要被存储的值之前不能执行存储请求。

需求 1 不足以保证执行正确。要看到这点，假设每个内存模块有几个端口，每个端口服务一个处理器（或 I/O 通道）。将 a 和 b 的值存储在不同的存储模块中，并思考以下事件的顺序：

1. 处理器 1 发送 a = 1 请求到内存模块 1 的端口。该模块正在忙于执行其他处理器的操作（或 I/O 通道）。
2. 处理器 1 发送读取 b 请求到内存模块 2 的端口。该模块目前空闲，开始执行。
3. 处理器 2 发送 b = 1 请求到内存模块 2，在完成处理器 1 读取 b 的请求后执行。
4. 处理器 2 发送读取 a 请求到内存模块 1。该模块也正忙。

现在有两个操作等待内存模块 1。如果处理器 2 的读取 a 操作先执行，那么两个程序会同时执行它们的关键部分，协议就失效了。如果内存模块使用轮询调度规则，就可能发生这种情况。

在这种情况下，对内存模块 1 的两个请求没有按到达的顺序执行导致了错误的发生。这就引出了下面的要求：

要求 2：所有来自处理器的内存请求按 FIFO 顺序进出队列。

意味着一个处理器直到它当前的内存请求进入队列后才能在发送请求。因此，如果队列满了它必须等待。

注意，如果一个读取请求内存中某个位置的内容，而队列中已经有一个写请求，那么这次读取无需入队，只要简单返回最后一个类似写请求的值。

两个要求保证了如果单个处理器是顺序的，那么整个多处理器计算机是顺序一致的。为了证明这点，我们首先介绍一个关系： 定义 A -> B，A 和 B 由同一个处理器发送，A 在 B 之前。A 和 B 访问同一个内存模块，并且 A 在 B 之前进入队列（因此也在 B 之前执行）。不难看出 R1 和 R2 意味着——是对内存请求集合的部分排序。利用每个处理器的顺序性，我们就可以证明以下结果：每次读取和存储相同的值，就像所有操作按任意顺序依次执行一样，这样 A -> B 意味着 A 在 B 之前执行。证明了多处理器计算机的顺序一致性。

要求 R2 指出内存模块的请求队列必须按 FIFO 顺序。这意味着如果排在队头的是一个存储请求，而要被存储的值还未接收到，那么存储模块必须被阻塞。条件 2 也可以适当弱化，以允许内存模块在这种情况下执行其他请求。我们只要对同一内存单元的请求按它们在队列中的顺序执行即可。对不同内存单元的请求可以不按顺序执行。顺序一致性得以保持，因为这样的策略在逻辑上等于把每个内存单元作为独立的存储模块，有自己的请求队列（这些模块可能共享一些硬件，影响了它们的速度和队列的容量，但不影响正确的顺序一致性逻辑）。

保证顺序一致性的要求排除了一些可用于加速单个顺序处理器的技术。对某些应用程序来说，可能没必要实现顺序一致性，它们要的是处理速度。在这种情况下，我们必须意识到不能完全依赖设计多进程算法来保证执行顺序的正确。同步处理器的协议必须设计在机器指令的最底层，而验证其正确性也是一项艰巨的任务。