论文原题：How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
摘要 - 很多大型的有序计算机不一定是按照程序指定的顺序来执行的。一次执行，如果其结果和按顺序执行的结果一致，则是一次正确的执行。不过，对于一个多核处理器，每个核都正确执行，却不一定能保证整个程序是正确执行的。要保证计算机正确的处理多进程程序，还需要满足一些额外的条件。
一个高速运行的处理器不一定按照程序指定的顺序执行。一个处理器必须满足下面的条件，才能保证正确的执行：处理器的执行结果，必须和按照程序指定顺序执行的结果一致。
倒不如直接说，处理器必须按照程序指定的顺序执行。或许理论上还有不按顺序执行，也能保证正确结果的方法，不过这种方法岂不难以解释
一个满足该条件的处理器就可以被称作是有序的（sequential）。而对于多个处理器访问同一块内存的场景，则必须满足下面的条件才能保证多进程并发的正确性：
- 任何一次执行的结果，和所有处理器按照某个顺序执行的结果一致;
- 在这”某个顺序执行“中单独看每个处理器，则每个处理器也都是按照程序指定的顺序执行的。
一个多核处理器如果满足了这样的条件，就被称作是顺序一致的（sequentially consistent）。
仅仅是每个处理器保证自己的有序性，是无法保证最终多核计算机的顺序一致的。我们在这里介绍一种有序处理器和内存模块协作的方法，以确保最终的多核处理器是顺序一致的。
我们假设计算机由一组处理器和一组内存模块构成，而处理器之间只通过内存模块进行交互（任何特殊的寄存器也当做是内存模块）。那么我们唯一需要关心的处理器操作就是往内存发起“读”或“写”的请求。我们假设每个处理器都会发起一系列的读写请求（有时候，处理器得等当前请求执行完后，才能继续下一步工作，但我们不用关心这个）。
为了阐述这个问题，我们来考虑一个简单的两进程互斥协议。每个进程都有一个临界区，协议的目的是保证任何时候只有一个进程能够在临界区内执行。协议设计如下：
process1
a := 1;
if b = 0 then critical section;
a := 0
else ···
fi
process2
b := 1;
if a = 0 then critical section;
b := 0
else ···
fi
else里的内容保证进程最终能够进入临界区（译者注：也就是不会死锁吧），但是这和我们需要讨论的问题无关。当这个程序在顺序一致的多核计算机上执行时，两个进程是不能同时在临界区内执行的。
我们首先注意到，一个有序处理器可能以任意的顺序执行“b:=1"和process1中的"fetch b"（当只考虑process1时，这两个操作的顺序如何倒是没什么关系）。不过，显而易见，如果先执行"fetch b"会导致两个进程能同时进入临界区执行。这引出了我们对于多核计算机的第一个必要条件：
必要条件R1：每个处理器必须按照程序指定的顺序处理内存请求。
要满足必要条件R1实际上是个复杂的问题。比如有时一个值要计算好了，才能写到内存，这样写内存的耗时会比较长。而处理器往往可以很快发起读内存的请求，此时，上一次写内存的请求却不一定完成了。为了最小化等待时间，处理器可以先向内存发起写请求，而不携带具体要写的值。当然，内存要等接受到这个具体的值，才能完成最终的写操作。
举个例子
a = a + 1
get b
复制代码对于上面的程序，处理器可以采用两种方式：处理器先计算出 a + 1，再将写a的请求，以及计算出的a的新值一起发给内存。之后处理器再向内存发起读b
的请求；先对内存发起写a的请求，但是不携带要写的值，之后，即可发起读b的请求。处理器可在之后的某个时间，计算出a + 1来，发给内存，以完成a = a + 1。
感觉这种讨论蛮奇怪的。
必要条件R1并不足以保证正确的执行。我们假设每个内存模块都有好几个端口，每个端口服务于一个处理器（或是I/O通道）。我们让 a 和 b 的值存储在不同的内存模块中，并且考虑按如下顺序发生的事件：
- 处理器1发送 a := 1 的请求给内存模块1，内存模块1正忙着其他事；
- 处理器1发送 fetch b 的请求给内存模块2，内存模块2闲着，立即开始处理这次请求；
- 处理器2发送 b := 1 的请求给内存模块2，这个请求得等处理器1的 fetch b 完成了才能执行；
- 处理器2发送 fetch a 的请求给内存模块1，内存模块1还没忙完。
这个时候，有两个操作挂在内存模块2上等待执行。如果处理器2的 fetch a 先执行了，那么上文的那个互斥协议就出问题了，因为两个process就同时进入临界区了。这在内存模块采取轮询的调度机制来处理请求时，是有可能发生的。
在这种情况下，因为到达内存模块1的两次请求，并未按照他们被接收到的顺序执行，而导致了错误。这引出了下面的必要条件。
必要条件R2： 一个独立的内存模块在服务所有处理器的请求时，必须基于FIFO队列。发起内存请求，即是将请求加入到FIFO队列。
而必要条件R1则意味着处理器在发起更多的内存请求之前，都必须等待当前的请求入队。因此，如果队列满了，处理器就得等着。如果多个处理器同时尝试将请求入队，那么谁先入队就没关系了。
注意，如果一次读请求A，读的那块内存，正好写请求B想要改，并且写请求B已经在队列里了，那么读请求A就不需要入队了，直接返回队列中写请求B所要写的值就行了。如果队列中有多个这样的写请求，返回最新入队的那个写请求所要写的值就行了。
必要条件R1和R2保证了如果一个核是有序的，那么多核处理器就是顺序一致性的。为了证明这点，我们引入了关系符号 "->" 来描述内存请求。
我们定义 "A -> B" 当且仅当：
1.A和B是被同一个处理器发起的请求，且A发起在B之前；
2.A和B请求的是同一个内存模块，并且A在B之前入队。
可以很容易看出来，必要条件R1和R2意味着在内存请求上存在着 "->" 这样一个偏序关系。利用处理器的有序性，我们可以证明下面这个结论：对同一个值进行的内存读写操作就好像这些操作都是按照某种顺序执行的，因此 A->B 也就意味着A是在B之前执行的。这反过来就证明了多核计算机的顺序一致性。
感觉这段证明的意思就是：R1和R2保证了内存请求上的偏序关系"->"，而该偏序关系保证了多核计算机的顺序一致性。（emmmmm，有点谜...）
必要条件R2要求内存模块必须用FIFO的策略来响应请求，这就意味着如果队列头是一个写请求，并且需要写的值还没收到，那么内存模块就需要等待，就会处于空闲状态。我们可以弱化R2，来允许内存在这种情况下可以响应其他请求。我们只需要要求针对同一块内存单元的所有请求必须按照FIFO的顺序响应既可以了。对不同内存单元的请求可以是乱序响应的。顺序一致性依然是能够得到保证的，因为这样其实和将每一个内存单元都当做一个拥有自己队列的独立内存模块没啥区别。（现实中，这些模块可能会因硬件特质不同，而有不同的响应速度和队列容量，但这并不影响顺序一致性）。
为了保证顺序一致性，需要舍弃一些能够提升有序处理器性能的技术。对于一些应用来说，牺牲性能而追求顺序一致性可能是不值得的。此时，我们必须意识到按照常规的多核程序设计方法设计出来的程序就不一定能正确执行了。此时，我们必须在机器指令层面设计其他的协议来保证多核之间的同步，可这样，正确性的验证也会变得非常繁杂。
对于顺序一致性，我的理解就是，多核计算机必须按照程序指定的顺序执行操作，而内存必须按照处理器发起请求的顺序处理读写（内存也等于间接的按照程序指定的顺序执行操作了）。
那么顺序一致性的主要用途就是，它保证多核系统的运作是按照程序指定的顺序来的，这样我们才能无后顾之忧的设计我们的程序。
网友评论