并行性

开始准备

要实践本节的思想，你需要我们的并发库。在实验楼机器上（或通过 SSH），在你的 Scheme 解释器中输入以下命令：

(load "~cs61as/lib/concurrency.scm")

概览

在普通编程中我们认为理所当然的许多事情，一旦涉及任何形式的并行性（parallelism）就会变成问题。这些情况包括：

• 多个处理器（硬件）共享数据
• 软件多线程（模拟并行）
• 操作系统输入/输出设备处理程序

这在 CS 162（操作系统）中有更详细的介绍。

为什么并行很困难

为了简单看出问题所在，考虑 Scheme 表达式

(set! x (+ x 1))

正如你将在 61C 中更详细地学到的，Scheme 会把它翻译成发给你的计算机的一系列指令。细节取决于具体的计算机型号，但大致是这样：

lw $8, x        ; 把 x 的值放入 8 号处理器寄存器。
addi $8, $8, 1  ; 取 8 号寄存器的值，加 1，然后把新值放回 8 号寄存器。
sw $8, x        ; 把 8 号寄存器中的值设为 x 的值。

你不需要理解这里代码的细节（你会在 61C 中学到），但你应该对发生的事情有个大致的了解。

（寄存器（register）是计算机放置值以便对它们进行操作的地方。所以计算机通常不能直接给 x 加 1——它必须先把 x 的值放进寄存器，然后才能给它加 1。）

通常我们会预期这一系列指令产生预期的效果。如果这些指令执行前 x 的值是 100，执行后应该是 101。

但想象一下，这三条指令序列可能被中途插入的其他事件打断。具体来说，假设另有一个人也在试图给 x 的值加 1。现在我们可能有这样的序列：

my process      value of x   other process
----------      ----------   -------------  
  $8 = ??        x = 100       $9 = ??

lw $8, x  
  $8 = 100       x = 100       $9 = ??

addi $8, $8, 1  
  $8 = 101       x = 100       $9 = ??

                             lw $9, x  
  $8 = 101       x = 100       $9 = 100

                             addi $9, $9, 1  
  $8 = 101       x = 100       $9 = 101

                             sw $9, x  
  $8 = 101       x = 101       $9 = 101

sw $8, x  
  $8 = 101       x = 101       $9 = 101

x 最终的值将是 101，而不是正确的 102。

解决这个问题所需的一般思想是临界区（critical section），即一系列不允许被中断的指令。从 load 开始到 store 结束的这三条指令就是一个临界区。

事实上，我们不必说这些指令完全不能被打断；我们必须强制的唯一条件是：它们不能被另一个使用变量 x 的过程打断。如果与此同时另一个过程想给 y 加 1，那没问题。所以我们希望能说出类似这样的话

reserve x
lw $8, x
addi $8, 1
sw $8, x
release x

抽象的层次

计算机并没有真正像 reserve 和 release 这样的指令，但我们将会看到它们确实提供了类似的机制。一个典型的编程环境在三个抽象层次上包含并发控制机制：

SICP 名称	保护的内容	提供者
serializer	高层抽象（过程、对象等）	编程语言
mutex	临界区	操作系统
test-and-set!	一次原子的状态转换	硬件

serializer 和 mutex 在 SICP 中是抽象数据类型。有一个构造函数 make-serializer 用 mutex 实现，还有一个构造函数 make-mutex 用 test-and-set! 实现，后者是一条（在本例中为模拟的）硬件指令。

我们将在接下来的几节中讲解 serializer 和 mutex。

---