串行化器

什么是串行化器

我们引入一种称为串行化器（serializer）的抽象。它是一个过程，接收另一个过程（称之为 proc）作为实参。串行化器返回一个新过程（称之为 protected-proc）。被调用时，protected-proc 会调用 proc，但仅当同一个串行化器尚未被另一个受保护过程使用。proc 可以有任意数量的实参，protected-proc 将接收相同的实参并返回相同的值。

可以有许多不同的串行化器同时运作，但每一个都不能同时做两件事。因此如果我们说

(define x-protector (make-serializer))
(define y-protector (make-serializer))
(parallel-execute (x-protector (lambda () (set! x (+ x 1))))
                  (y-protector (lambda () (set! y (+ y 1)))))

那么这两个任务可以同时运行；它们的机器指令如何交错无关紧要。

但如果我们说

(parallel-execute (x-protector (lambda () (set! x (+ x 1))))
                  (x-protector (lambda () (set! x (+ x 1)))))

那么，由于两个任务使用同一个串行化器，串行化器将确保它们在时间上不重叠。

我们引入了一个新的原语过程 parallel-execute。它接收任意数量的实参，每个都是无实参过程，并以并行而非顺序的方式调用它们。（这不是 Scheme 的标准组成部分，而是本教材这一节的扩展。）

你可能想知道为什么需要所有这些 (lambda () ...) 记号。由于串行化器不是特殊形式，它不能把表达式作为实参。相反，我们必须给它一个它可以调用的过程。

让我们看一段示例代码，看看它是如何工作的：

(define x-protector (make-serializer))
(define protected-increment-x (x-protector (lambda () (set! x (+ x 1)))))
> x
100
> (protected-increment-x)
> x
101

实现串行化器

串行化器是一种高层抽象。我们怎样让它工作呢？下面是一个错误的尝试，试图实现串行化器：

(define (make-serializer)
  (let ((in-use? #f))
    (lambda (proc)
      (define (protected-proc . args)
        (if in-use?
            (begin
             (wait-a-while) ; 先不管怎么做。
             (apply protected-proc args)) ; 重试。
            (begin
             (set! in-use? #t) ; 不让其他人进来。
             (apply proc args) ; 调用原过程。
             (set! in-use? #f)))))) ; 完成了，让别人进来。
      protected-proc))

这有点复杂，所以把注意力集中在重要的部分上。特别是，不必关心并行性的调度（scheduling）方面——如果串行化器已在使用中，我们如何让这个过程先等一会儿再重试。也不必关心 apply 的那些麻烦事，它只是为了让串行化器能处理带有任意数量实参的过程。

需要关注的部分是这个：

(if in-use?
    ....... ; 等待并重试
    (begin (set! in-use #t)   ; 不让其他人进来。
           (apply proc args)  ; 调用原过程。
           (set! in-use #f))) ; 完成了，让别人进来。

这段代码的意图是：首先检查串行化器是否已在使用。如果没有，我们就把 in-use 设为真来占用串行化器，做我们的工作，然后释放串行化器。

问题在于，这一系列事件会受到与我们试图保护的过程相同的并行性问题的影响！如果我们检查 in-use 的值，发现它是假，而就在那一刻另一个过程溜进来抢走了串行化器，怎么办？为了让这个方案奏效，我们就得用另一个串行化器来保护这一个，再用第三个串行化器保护第二个，如此无限继续。

在相互竞争的进程内部，靠聪明的编程技巧是无法轻易避免这个问题的。我们需要提供并行性的底层机制——硬件和/或操作系统——提供帮助。这个底层必须提供一个保证原子（atomic）的操作，让我们能测试 in-use 的旧值并把它改成新值，且绝无另一个过程介入的可能。（事实证明，有一个非常棘手的软件算法可以生成保证原子的 test-and-set，但实践中几乎总有硬件对并行的支持。如果你愿意看软件解决方案，可以在维基百科查”Peterson 算法”。）

教材假设存在一个名为 test-and-set! 的过程，它保证原子性。虽然在教材第 312 页有一个伪实现，但那个过程并不能真正工作，原因与我对 make-serializer 的伪实现不能工作相同。你必须想象：test-and-set! 是计算机硬件中的一条指令，与我们一开始提到的 Load Word 等指令类似。（这是一个现实的假设；现代计算机确实提供了某种这样的硬件机制，正是出于我们现在讨论的理由。）

要正确理解如何实现串行化器，你首先需要学习并理解互斥锁（Mutexes）（在接下来两节中）。

---