3.4 Concurrency: Time Is of the Essence - CloneableX/SICP-learning GitHub Wiki

前面的章节展示了通过本地状态的可计算对象建模的强大，不过同时也提出了关于透明引用失效的问题，以及关于同一性和状态变化的棘手问题，还有需要使用更加复杂的环境模型替代替换模型分析的问题。

隐藏在状态、同一性及变化等复杂度之下的核心问题是因为赋值操作的引入，使时间元素也被引入了模型中。在引入赋值操作前，我们所编写的程序都是非时间性的，也就是说对于同一个程式只要输入同样的参数就会得到相同的结果。与之相对，从银行账户取款的例子却展示了不同的效果。

(withdraw 25)
75

(withdraw 25)
50

上述示例中，对于同样的程式传入同样的参数却得到不同的结果。这种现象是由于在执行赋值操作修改状态值（在上述示例中修改了 balance 变量）时伴随着时间流逝的瞬间。所以运算结果并不只是信赖表达式本身，同时也由当前运算出现在数值变化的瞬间之前还是之后。如果要构建带有本地状态的计算对象模型，我们就必须要处理将时间作为编程中本质性概念的问题。

我们也可以将现实世界与计算模型结构比对。现实世界中的对象并不会在同一瞬间作出一系统变化，而是将其看作一次并发操作。所以，引申至模型系统中就是并发地执行一组计算过程。就像将程序模块化，使模型基于携带不同本地状态值的对象计算一样，通过这种将计算对象模型分离成多个部分的方式向并发化和模块化演进。即使程序是运行在序列式计算机中，将程序并发化的实践也可以使程序员避开非本质性的时间限制，并提高程序的模块化。

在使程序更加模块化方面，并发计算能够比序列式计算提高更优的计算速度。因为序列式计算一次只能处理一个操作，所以计算消耗的总时间与执行的总任务数成正比。但是，如果将任务划分为不相关的几个片段，便可以同时执行，也就是能够提供与任务执行器数量成正比的速度提升。

不幸的是，由于赋值操作的引入导致并发操作存在许多问题。因为当并发操作发生时，有些任务在并行操作，而有的任务执行完成，这将引出关于时间的复杂性问题。

从表面看，时间看起来很简单，它是强加于事件的执行顺序。对于任何事件 A 和 B，要么是 A 发生于 B 之前，要么 A 与 B 同时发生，要么 A 发生于 B 之后。例如，之前关于银行取款的例子，假设存在拥有 100 美元的通用账号， Peter 从该账户取款 10 美元，Paul 也从该账户取款 25 美无，最后账户余额为 65 美元。根据取款顺序，账户余额的变化可能为 100 -> 90 -> 65，或者 100 -> 75 -> 65。通过计算机实现一个银行系统时，此变化事件序列可以通过连续为 balance 赋值实现。

不过在更复杂的情况下，可能会出现某些问题。假设 Peter 和 Paul 通过网络访问同一个银行账户，余额操作的执行顺序就要依赖操作发生的时机，以及机器间的通信细节。

在设计并发系统时，关于事件执行顺序的判定有几个重要的问题需要研究。例如，如果 Peter 和 Paul 是通过两个不同的操作过程共享 balance 变量，并且每个过程都按照下列程式运行。

(define (withdraw amount)
  (if (>= balance amount)
      (begin
        (set! balance (- balance amount))
        balance)
      "Insufficient funds"))

如果两个流程分别运行，Peter 的流程会先检验余额，并从账户进行取款。不过 Paul 的流程可能在 Peter 检查余额与取款之间完成了取款，这可能会导致 Peter 的账户检查无效。

事态还可能更糟，考虑下列表达式的执行情况。

(set! balance (- balance amount))

上述表达式在每次取款时都会执行。它由三个部分构成：（1）访问变量 balance 的值；（2）计算新的余额；（3）将新余额赋值给 balance。如果 Peter 和 Paul 取款时同时进行了状态操作，那么 balance 的访问顺序和赋值顺序可能出现交错。

下图是关于 Peter 和 Paul 取款的时序图。其中账户余额为 100，Peter 取款 10，Paul 取款 25，最终账户余额却为 75。出现这种反常现象的原因是 Paul 在银行账户余额为 100 的基础上进行了取款，但这是个幻象，因为此时 Peter 已经完成取款，银行账户应该为 90。这对于银行系统将造成灾难性的后果，因为系统的总金额正确性无法得到保障。在进行交易前系统总金额为 100，而进行了 10 和 25 的取款后剩余金额却是 75。

通常情况下，可能几个进程会共享一个状态变量，而多个进程在同一时间尝试维护共享状态时将引起问题。对于银行系统的例子，每次交易时，每个客户只有在其他客户不存在时才可以进行操作。当一个客户打算更改账户余额时，一定要保证在修改前的瞬间余额与其计算的基础余额为同一个。

前面的例子已经指明了并发系统中会出现的问题。问题的根源在于系统需要依赖不同进程间的共享状态赋值操作。现在我们已经了解，在编写程序时应该谨慎使用 set! 操作，因为整个事务的计算结果依赖于赋值操作的发生顺序。对于并发进程，必须特别关注赋值操作，因为我们无法控制不同进程赋值的顺序。如果出现并发修改操作（比如两个储户访问通用账户），便需要提供方法保证系统的行为正确。例如，在通用账户取款的例子中，需要确保余额的正确性。为了保障并发程序的结果正确，需要为并发操作设置一些限制。

关于并发的一种限制措施是，规定不允许同时有多个操作修改任何共享状态变量。在分布式银行系统中，它需要系统设计者保证一次只有一个业务在执行。虽然比较低效，但它保证了金额的正确性。下图展示了 Peter 和 Paul 共享账户的操作情况，其中 Paul 有一个私人账户。图示中展示了两次从共享账户中的取款操作（一次由 Peter 完成，一次由 Paul 完成）和一次向 Paul 私人账户存款的操作。对于共享账户的操作不能并发（在访问和更新同一账户时），并且 Paul 对私人账户的存款和取款操作也不能同时进行（在访问和更新 Paul 私人账户时）。不过，当 Paul 向私人账户存款和 Peter 从共享账户取款可以同时发生。

对于并发也可以不这样严格限制，使其能够产生与进程顺序执行同样的结果。不过有两个必要条件。首先，虽然不需要进程实际按顺序式执行，但运算结果要如同顺序执行一样。例如，在上图中，银行系统设计师可以允许 Paul 的存款和 Peter 的取款操作同时发生，因为只要这两个操作有序执行，产生的结果将没有区别。其次，并发程序可能产生多个正确结果，因为只需要操作有序执行即可。例如，假设 Peter 和 Paul 的通用账户余额为 100 美元，Peter 存款 40 美元，同时 Paul 取出其中一半的钱，不同顺序执行的结果分别是 70 美元和 90 美元。

所以保证并发程序正确执行的条件十分脆弱。模拟传播的程序（比如对象的热流）会由大量进程构成，每个过程表示一小部分空间，然后需要并发地更新它们的值。每个进程都将自己的值修改为自身数值与相邻进程数值的平均值。整个算法结果的正确性与操作的执行顺序无关，所以对于共享变量的并发操作并不需要进行限制。

处理并发进程的难点在于对不同进程事件执行顺序的交错部分的处理。例如，如果此时有两个进程，其中一个进程的事件依次为 (a b c)，另一个进程的事件为 (x y z)。如果两个进程并发执行，在不限制两个进程执行的交错情况下，将出现 20 种不同的事件执行顺序，如下。

(a,b,c,x,y,z) (a,x,b,y,c,z) (x,a,b,c,y,z) (x,a,y,z,b,c)
(a,b,x,c,y,z) (a,x,b,y,z,c) (x,a,b,y,c,z) (x,y,a,b,c,z)
(a,b,x,y,c,z) (a,x,y,b,c,z) (x,a,b,y,z,c) (x,y,a,b,z,c)
(a,b,x,y,z,c) (a,x,y,b,z,c) (x,a,y,b,c,z) (x,y,a,z,b,c)
(a,x,b,c,y,z) (a,x,y,z,b,c) (x,a,y,b,z,c) (x,y,z,a,b,c)

如果作为一个设计此系统的程序员，还必须考虑每种执行顺序的效率和是否适合。不过这种方式将随着过程和事件的数量增加导致规模快速增长。

一种更具可操作性的方法是为并发系统设计通用机制，对并发进程的交叉点进行限制，以此确保程序行为的正确性。有许多机制就是为了此目标研发。在本节，我们将介绍其中的一种，叫做 串行器（serializer）。

串行的概念为，虽然进程能够并发执行，但是需要确定其中不能并发执行的程式。更确切地说，串行会区分每次串行时不能并发执行的程式。如果无法并发执行的程式组中有程式正在执行，另一个进程想执行其中的其他程式必须要等到当前程式执行完成后。

所以我们可以通过串行控制共享变量的访问。例如，如果想基于之前变量的值更新共享变量，则需要访问变量的前一数值，并将新值赋值给此变量。接着排查由同一串行器串行化的程式，确保它们在并发运行时不会赋值相同的变量。这种机制保障了变量值在访问与赋值之间不会被修改。

为了使上面的机制更加具体，假设我们要为 Scheme 扩展 parallel-execute 程式，其语法为

(parallel-execute <p1> <p2> ... <pk>)

每个 <p> 必须为无参数的程式。parallel-execute 将为每个 <p> 分别创建进程，这些进程将执行对应的程式 <p>，并且这些进程全都将并发运行。

下面是实际运用的例子。

(define x 10)
(parallel-execute
 (lambda () (set! x (* x x)))
 (lambda () (set! x (+ x 1))))

上述例子将创建两个并发进程 P1 和 P2，P1 将计算 x 与 x 的乘积并赋值给 x，P2 将递增 x 的值。在执行完成后，x 将出现五种结果的可能，最终呈现哪种结果有赖于 P1 与 P2 的交叉点组合。

• 101: P1 将 x 设置为 100，然后 P2 递增 x 的值为 101
• 121: P2 将 x 递增至 11，然后 P1 计算 x 乘 x 的值并赋值给 x
• 110: P2 在 P1 两次获取 x 值之间将 x 递增至 11
• 11: P2 先获取 x 值，然后 P1 将 x 的值设置为 100，最后 P2 再递增 x
• 100: P1 先两次获取 x 值，然后 P2 将 x 值设置为 11，最后 P1 再设置 x 的值

我们可以通过利用 串行器（serializers） 创建的串行化程式限制并发行为。串行器通过 make-serializer 构建，具体实现会在后面给出。串行器的参数为一个程式，并将运算行为与原程式相同的串行化程式返回。对同一个串行器的调用将使传入的程式都存储于同一个集合中。

因此，将上面的示例修改如下。

(define x 10)
(define s (make-serializer))
(parallel-execute
  (s (lambda () (set! x (* x x))))
  (s (lambda () (set! x (+ x 1)))))

执行上述程式只会产生两种可能的结果，分别是 101 和 121。因为 P1 与 P2 执行时不能再出现交叉，所以排除了其他可能性。

下列是 make-account 程式关于取款和存款操作的串行化。

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) (protected withdraw))
            ((eq? m 'deposit) (protected deposit))
            ((eq? m 'balance) balance)
            (else (error "Unknown request: MAKE-ACCOUNT"
                         m))))
  dispatch))

按照上述实现，对于同一账号的存款与取款操作不能同时发生。这样便能避免 Peter 在获取余额和修改余额之间被 Paul 取款成功，而 Peter 赋值了一个错误结果的情况。另一方面来看，每个账号都有自己的串行器，所以不同账号间的存取款业务并不会相互影响。

串行器提供的抽象帮助我们隔离了并发程序的复杂性。不过除了只有一种共享资源这种比较简明的情况外（比如银行账户），并发程序在处理多个共享资源时将变得格外麻烦。

为了说明其中的复杂性，需要以交换两个银行账户余额为示例。完成这项业务需要获取两个账户的余额，然后计算余额之间的差值，并从一个账户中取出差值额度，然后存入另一个账户中。具体实现如下。

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance))))
    ((account1 'withdraw) difference)
    ((account2 'deposit) difference)))

在一个进程工作操作的情况下程式运转良好。不过，假设 Peter 和 Paul 都能够访问账户 a1、a2 和 a3，然后 Peter 在 Paul 交换 a1 和 a3 账户余额的同时交换 a1 和 a2 账户的余额。此时，即使同一账户的存款和取款操作已经被串行化，但 exchange 依然会产生错误的结果。例如，Peter 可能正计算完 a1 与 a2 账户的差值，Paul 就在 Peter 完成交换操作前修改了 a1 账户的余额。为了保障行为的正确性，必须将 exchange 操作的账户锁定，避免账户交换业务期间出现其他的并发操作。

目前可以通过账户的串行器对整个 exchange 程式串行化，为了实现此功能，需要能够访问账户的串行器。注意，我们是有意通过暴露账户串行器的行为破坏模块化的。下列的 make-account 与原来的程式并无不同，唯一的区别在于通过消息传递的方式暴露账号的串行器。

(define (make-account-and-serializer balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            (else (error "Unknown request: MAKE-ACCOUNT" m))))
  dispatch))

我们可以通过暴露的串行器对存款和取款业务序列化。不过，不是如同之前一样串行化整个账户，现在每个账户对象的职责只是管理串行器，具体应用如下。

(define (deposit account amount)
  (let ((s (account 'serializer))
        (d (account 'deposit)))
    ((s d) amount)))

通过这种方式暴露串行器能够为交换账号余额程式提供足够的灵活性。下列是具体实现。

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    ((serializer1 (serializer2 exchange))
     account1
     account2)))

要实现串行器，需要通过一个更加基础的同步机制—— 互斥元（mutex）。互斥元对象支持两个操作，一个是 持有（acquired），一个是 释放（released）。一旦一个互斥元被持有，在此互斥元释放前其他操作都无法持有此互斥元。在我们的实现中，每个串行器都有对应的互斥元。向串行器传入一个程式 p，则串行器将返回一个持有互斥元的程式，当 p 运行结束后会释放互斥元。这种机制保证了由串行器产生的程式只有一个能够同时运行，这正是我们需要保证的串行化属性。

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (mutex 'acquire)
        (let ((val (apply p args)))
          (mutex 'release)
          val))
      serialized-p)))

互斥元是一个可变对象（目前使用只有一个元素的列表表示，我们称其为 单元（cell）），它能够处理 true 或 false 值。当值为 false 时，互斥元可以被持有；如果值为 true，则互斥元不可用，此时打算持有互斥元的进程都必须等待。

make-mutex 构造器会将互斥元的单元内容初始化为 false。如果要持有互斥元需要先校验单元。如果互斥元可用，则将单元内容设置为 true 并执行。否则就循环等待，不断尝试持有互斥元，直到互斥元可用为止。要释放互斥元，只需要将单元的值设置为 false 即可。

(define (make-mutex)
  (let ((cell (list false)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire)
             (if (test-and-set! cell)
                 (the-mutex 'acquire))) ;retry
            ((eq? m 'release) (clear! cell))))
    the-mutex))
(define (clear! cell) (set-car! cell false))

test-and-set! 会检测单元的值，并返回检测结果。如果检测结果为 false，则 test-and-set! 在返回 false 结果前已经将单元内容设置为了 true。具体实现如下。

(define (test-and-set! cell)
  (if (car cell) true (begin (set-car! cell true) false)))

然而上述关于 test-and-set! 的实现并不满足标准。其中有个十分重要的关键点，此程式是并发控制的关键所在，所以 test-and-set! 操作必须是 原子性（atomically） 的。也就是说，我们必须保证一个进程检查到单元为 false 时，便能在其他进程检测此单元前将其设置为 true。否则，互斥元将与最开始的并发银行账户操作一样出现问题。

test-and-set! 要根据系统运行并发进程的处理细节实现。例如，我们可能会在一个顺序处理器上通过时间分片机制循环执行进程，以上保证每个进程在被打断和移动至下个进程之前只需要运行一段很短的时间。在这种实现机制下，test-and-set! 可以通过在检测和设置单元时断开时间切片的方式运转。另外，多线程电脑中会提供关于直接通过硬件进行原子操作的说明。

现在我们已经了解了如何实现串行器，不过在交换银行账户余额的示例中（也就是 serialized-exchange）还存在一些问题。试想象，Peter 准备交换 a1 和 a2 账户，此时 Paul 同时交换 a2 和 a1 账户。然后 Peter 的进程串行化了保护 a1 账户的程式，而 Paul 的进程串行化了保护账户 a2 的程式。现在 Peter 无法在 Paul 退出 a2 保护程式前继续执行。同样，Paul 也无法在 Peter 退出 a1 保护程式前继续执行。两个进程都停滞不前，互相等待。这种情况称为 死锁（deadlock）。死锁是提供多共享资源并发访问能力的系统的风险。

避免死锁的方法为每个账户提供一个唯一编号，并重写 serialized-exchange，使进程优先为更低编码的账户提供保护程式。尽管这种方式对于交换账户问题有效，但其他情况需要更加复杂的死锁规避技术，甚至有些死锁根本无法避免。

通过前面内容的学习，我们已经了解到当不同进程访问共享状态时如何通过并发系统控制事件发生的顺序，并且也了解了如何通过串行器实现这种控制。但并发的问题更加深邃，因为从基础的角度出发，共享状态的定义并不总是清晰。

比如 test-and-set! 需要随时检测全局共享标识，在拥有高速处理器的计算机中这是一种有问题的、低效的实现，因为已经存在更加优化的管道技术和缓存技术，这导致存储中的内容不一定会一直保持同一状态。同时对于多线程系统，串行器将被新的并发控制技术取代。

在分布式系统中，也存在大量关于共享状态的问题。例如，分布式银行系统中，一些分行会维护银行余额的本地值，并使用这些数值定期与其他银行比对。但在一些系统中账户余额在正确同步之前无法确定。如果 Peter 向与 Paul 的通用账户中存款，我们该在什么时候说账户余额发生了变化呢，是本地分行的余额变化时，还是余额同步完成时呢？而且此时 Paul 从其他分行访问账户，需要对银行系统实施哪些限制才能使整个交易行为看起来正常呢？唯一影响正确性的行为来自 Peter 和 Paul 对账户的分别观察，以及状态的同步。与之相比，关于真实账户余额的问题或同步时事件的执行顺序可能都无关紧要或毫无意义。

目前的基本情况是，同步不同进程、建立共享状态、或对事件施加顺序都需要进程间的通信。从本质上来说，并发控制系统中的任何时间观念都与通信密不可分。耐人寻味的是，在相对论中也有类似时间与通信的联系，相对论中表示光速（光速是可用于同步事件的最快信号）是与时间和空间相关的基础常量。在我们处理计算模型中时间与状态时所遭遇的复杂性也反映为物理宇宙的一种基本复杂性。