在上一篇文章之中我们见识到了基于变动数据、内部状态的程序设计的能力，但是就像之前提及过多次的引用透明性的问题被打破，程序中引入了时间的概念，导致我们无论是求值顺序还是过程的运行都出现了一个时序性的问题，我们在 数字电路模拟 之中使用了一个 待处理表 的子过程，用来为我们的信号传播进行排序，通过模拟延时构造了程序的时序性。但是在现实世界中，我们不可能只通过一张表去排序构造顺序，现实系统中的对象都有更为复杂的同时的活动，为了构造这种更为现实的模拟系统，我们可能需要：

  • 使用一组系统进行对同时发生的事情进行模拟
  • 分解我们使用的模型，增强内部状态的演化，就是更为 模块化
  • 能够支持多个进程的硬件支持

在多内核处理器普及的今天，硬件支持已经渐渐不是并发编程的难题了。但是并发编程的复杂性让然没有因为这个原因而降低难度。首先我们要承认正确的运用并行编程是有利的，能提升我们程序的运行效率和对硬件的利用率。

但是由于并发系统的时间的不确定性，两个同时运行并有所依赖的进程，我们并不能确定什么时候某个能运行完，而一个又不能对另一个的结果进行无限的等待。还有就是资源获取的问题，两个并行的程序如何对资源进行管理，比如第三章开始的那个例子，从银行取钱，如果无法控制程序对资源的有效管理就可能造成两个人同时使用一个账户同时取钱，都能取出来的情况出现。

这一节会谈及和并发相关的内容，对于有编程理论经验的同学，这并不是什么复杂的理论内容，其中涉及到的时序控制、锁和信号量等等的知识都是能在各种 OS 相关的课程和书中了解到的知识。

并发和时间

时间是一种设施，发明它就是为了不让所有事情都立即发生。

从抽象的角度来看时间就像是加在事件上的一种顺序，一件事情发生比另一件事情发生的早，只是事件顺序的相对关系，这个过程听起来能够非常原子的控制，但是本身事件还会消耗时间。这就引出了并发带来的一些问题，之前也已经提到了，来自于对相同资源的控制问题，和操作的顺序问题，解决这个问题我们就是在解决程序的 正确性 和 健壮性 的问题，通常我们可以这么去理解程序的正确性：

  • 并发运行不受外界的影响
  • 运行的表现要和不进行并发程序的状态是一样的

并发控制

对正确性的保证其实就是在做和 并发控制 相关的工作，其实质就是对并行操作进行一定的控制，书中谈到的很多策略其实在做开发中都是经常见到的：

禁止所有共享资源的并行操作

Tips :

锁粒度： 简单说就是指不允许并行运行的加锁区域。

其实典型就是加了个 锁 ，但是问题也比较明显，书中的反面 Demo 明显是一个锁粒度设定非常大的例子，这也是这种方案的一个比较突出的缺陷，并不是所有的时间都需要禁止并行进行。很多操作并非互相干扰的，比如非常常见的 读写分离 锁就是这样，我们很多时候对读操作和写操作的要求不同不能一概而论。

允许不互相干扰的并发

书中提到了另一种控制方式，是对一种想法的一种改进，这时候我们允许对很多的不互相干扰的并发执行，但是对结果的要求仅仅期望与某种顺序的运行方式相同，这样会有另一个方面的问题，并发结果有很多种，我们没办法对其结果进行预测。

串行控制器

串行化控制器的思路就是，程序可以并行执行，但是其中也有时序性的要求的部分，这部分无法并行执行程序的部分就靠一个控制器，将所有的执行过程通过一个集合控制起来，同一个时间段只会有一个过程在执行。最简单的应用我们可以借助共享变量去理解，同一个时间段可能有很多个进程在请求同一个资源，但是 同时 只能有一个进程能够获得这个资源，其余的将在等待队列中等待：

lock

通过对程序的分组的方式来禁止不正当的并发行为，并且可通过程序控制将某个方法设置为 串行化 的方法。

我们引入一个内部方法 make-serializer 去提供这个是过程串行化的功能，make-serializer 接受一个过程作为参数返回同样行为的过程，参数与原过程保持一样，但保证其执行被串行化，我们可以继续使用之前的 make-account 的例子：

  1. (define (make-account balance)
  2.   (define (withdraw amount)
  3.     (if (>= balance amount)
  4.         (begin (set! balance (- balance amount)) balance)
  5.         "Insufficient funds"))
  6.   (define (deposit amount)
  7.     (set! balance (+ balance amount))
  8.      balance)
  9.   ; 引入内部过程 make-serializer 
  10.   (let ((protected (make-serializer)))
  11.     (define (dispatch m)
  12.       (cond ((eq? m 'withdraw) (protected withdraw))
  13.             ((eq? m 'deposit) (protected deposit))
  14.             ((eq? m 'balance) balance)
  15.             (else (error "Unknown request -- MAKE-ACCOUNT" m))))
  16.     dispatch))

可以看出我们引入了内部过程，通过对每个向外暴露的方法包装一层方法。

Tips：

这里面可以类比 Java 中的 synchronized 和 Lock 机制，在实际的开发中使用 synchronized 设置为某个方法的关键字，这样我们对某个方法的封装就能让具体的处理业务 互斥 进行处理。

多重资源的复杂性

我们考虑完单一资源的串行化操作之后来看一下涉及到多重资源的程序，比如刚才对 account 的操作，如果我们提供一个过程能够交换两个账户的金额（通过计算差值分别赋值给两个账户）：

  1. (define (exchange account1 account2)
  2.   (let ((difference (- (account1 'balance) (account2 'balance))))
  3.     ((account1 'withdraw) difference)
  4.     ((account2 'deposit) difference)))

但是这就涉及到了另外一个问题，这个的操作确实能在对两个账户进行使用的时候保持并发正确，但是如果我们同时运行两个这个程序分别交换 account1 和 account2 以及 account2 和 account3 的时候，这时候情况就变得复杂了，account 的操作能保证串行化，但是 exchange 的程序还没有保证串行化。

这时候我们就要改变 exchange 的串行租的策略，我们要是能够使用两个 account 的用户的串行组就能让 exchange 过程也并行正确，这里我们提取出了对应方法，把串行租从账户模块中暴露出来，这样就能在想加锁的时候用上锁了：

  1. ; 还是那段 make-account
  2. ; ... 
  3. (let ((serializer (make-serializer)))
  4.     (define (dispatch m)
  5.       (cond ((eq? m 'withdraw) withdraw)
  6.             ((eq? m 'deposit) deposit)
  7.             ((eq? m 'balance) balance)
  8.             ((eq? m 'serializer) serializer)
  9.             (else (error "Unknown request -- MAKE-ACCOUNT" m))))
  10.     dispatch))
  11. ; ...

我们可以看到我们在程序内部没有给操作的过程加锁，而是把锁暴露在了外面，这样我们对操作的定义可能需要一定的修改：

  1. (define (deposit account amount)
  2.   (let ((s (account 'serializer)) 
  3.         (d (account 'deposit)))
  4.     ((s d) amount)))

我们的 exchange 的定义也可以用提取出来的串行控制器进行重构了：

  1. (define (serialized-exchange account1 account2)
  2.   (let ((serializer1 (account1 'serializer))
  3.         (serializer2 (account2 'serializer)))
  4.     ((serializer1 (serializer2 exchange)) account1 account2)))

分别把两个串行控制器提取出来了，并且确信要拿到两道锁的 exchange 程序来操作两个账户。

看起来我们实现了我们所需要的整个功能不是么？可是未必意识到了我们对这个程序都做了什么，首先我们来看修改版本的 deposit 程序，这个 deposit 明显已经不是 account 的一个内部方法了，这是在外面包裹了一层的一个新的方法，破坏了本身的模块和封装。

而且在看我们对 serializer 的使用上来看，明显和上个原因相同以外，我们暴露的是对象所在的串行组，想想串行组是用来管理资源的，这个东西都暴露在了模块的外部，无论是使用还是管理起来都是特别不方便还容易出现危险。

Tips :

我们之前简单的描述过，可以把这里提到的串行控制器等价于我们在实际开发中使用的 锁，多种资源引来的复杂性实际上就是程序所使用的锁的数量不足，不能有效的管控所有的资源。而我们在程序的修改的结果其实就是拆解了模块，把我们的 锁 暴露在了外部，对于封装和安全的问题可想而知。

串行控制器的实现

我们刚才在谈及串行控制器的实质上面，我们可以把它想象成一把锁和一个请求锁的等待队列，在书中的模拟中是使用了 互斥量(mutex) 这个更为细粒度的抽象数据实现的。

互斥元是一个可以被获取、在使用之后被释放的数据抽象（类比锁实现），如果某个互斥元已经被获取，想获取该互斥元的其他操作需要等到该互斥元被释放（任何时候只有一个进程能拿到），来看 make-serializer 的实现过程：

  1. (define (make-serializer)
  2.   ; 创建互斥元
  3.   (let ((mutex (make-mutex)))
  4.     (lambda (p)
  5.       (define (serialized-p .args)
  6.         ; 获取互斥元
  7.         (mutex 'acquire)
  8.         ; 执行 p 过程
  9.         (let ((val (apply p args)))
  10.              ; 释放互斥元
  11.           (mutex 'release)
  12.           val))
  13.       serialized-p)))

这就是我们之前生成串行控制器的过程，以一个过程作为参数，我们先对获取互斥元再执行完过程 p 然后再释放我们的互斥元。我们还需要一个生成互斥元的过程：

  1. (define (make-mutex)
  2.   (let ((cell (list false)))
  3.     (define (the-mutex m)
  4.       (cond ((eq? m 'acquire)
  5.              (if (test-and-set! cell)
  6.                  (the-mutex 'acquire)))
  7.             ((eq? m 'release)
  8.              (set-car! cell false))))
  9.     the-mutex))

注意到互斥元的管理本身也是依赖一个变量来操作的，其中的 test-and-set! 检查参数的 car 值，如果参数的 car 值为假就在返回值前将其设为真值。

test-and-set! 这个方法是生成互斥元的核心，这个操作需要以 原子操作 的方式执行，具体实现可能是一个特殊的硬件指令或者是系统提供的一个专门的过程。在单处理器程序中系统通过轮转时间片的方式为每一个可执行程序安排一段运行时间，多处理器机器中我们就必须通过硬件支持的专门指令。

死锁

在资源抢占和申请的过程中，我们会遇到更为严重的问题 —— 死锁。我们刚才对 serialized-exchange 的修改之后，通过增加一条锁，已经能让我们在交换账户的时候控制好时序性了，但是我们还可能遇到资源互相抢占的问题比如文中的例子：

实例：设 Peter 要交换账户 a1 和 a2，同时 Paul 想交换 a2 和 a1

  • 假定 Peter 进程已进入保护 a1 的串行化过程，与此同时 Paul 也进入了保护 a2 的串行化过程
  • 这时 Peter 占着保护 a1 的串行化过程，等待进入保护 a2 的过程（等待 Paul 的进程释放该过程），而 Paul 占有保护 a2 的串行化过程，并等待进入保护 a1 的过程
  • 两人的进程将相互等待，永远也不能前进

dead

这样两个以上的进程，由于相互等待其他方释放资源无法前进，这种情况我们就称之为死锁，如果并发系统涉及到多种资源的管理和申请，就有可能出现死锁。

流

总结

对于赋值和状态的讨论是本章贯穿的内容，在本节中我们进一步揭示了复制的引入本质上是是对时间的依赖，赋值改变了变量的状态，从而改变了依赖于这些变量的表达式的计算。