《SICP》习题3.42：两种账户序列化实现替换是否安全？

摘要 #

将SICP中创建并发安全账户的第一段代码替换为第二段，是否安全？

完整问题 #

在《计算机程序的构造和解释》（SICP）第3.4.2节第305页，有一个用于创建可处理并发请求的账户余额的函数：

(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))

这段代码通过(make-serializer)创建序列化器protected，将withdraw和deposit转换为执行过程不可交错的函数，以此保证并发安全。

第307页的习题3.42给出了如下替代版本，问题是该修改是否安全：

(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)))
    (let ((protected-withdraw (protected withdraw)) ; 新增代码行
          (protected-deposit (protected deposit)))    ; 新增代码行
      (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)))

推理与结论 #

你的推理是正确的，这个修改是安全的。

根据SICP第304页「序列化共享状态访问」章节的内容：

[...] serialization 创建不同的过程集合，同一集合中的过程同一时间仅允许一个执行。[...]
我们可以使用serialization控制对共享变量的访问。例如，若要基于共享变量的旧值更新它，需将读取旧值和赋值新值的操作放在同一过程中。然后通过使用同一个serializer序列化所有这类过程，确保其他赋值该变量的过程不会与它并发执行。[...]

关键在于：同一个serializer（由(make-serializer)创建的实体）序列化的所有过程，都属于同一个互斥集合，它们的执行不会相互交错。

在修改后的代码中，每次调用(make-account some-balance)时，(make-serializer)依然只被调用一次，每个账户对应唯一的protected序列化器。protected-withdraw和protected-deposit都是通过这个序列化器生成的，因此它们属于同一个互斥集合，执行时不会互相干扰，完全能保证账户操作的并发安全性。

内容的提问来源于stack exchange，提问作者Enlico