Exercise 3.42 · 习题

Exercise 3.42: Ben Bitdiddle suggests that it’s
a waste of time to create a new serialized procedure in response to every
withdraw and deposit message. He says that make-account
could be changed so that the calls to protected are done outside the
dispatch procedure. That is, an account would return the same
serialized procedure (which was created at the same time as the account) each
time it is asked for a withdrawal procedure.

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

Is this a safe change to make? In particular, is there any difference in what
concurrency is allowed by these two versions of make-account?

Complexity of using multiple shared resources

Serializers provide a powerful abstraction that helps isolate the complexities
of concurrent programs so that they can be dealt with carefully and (hopefully)
correctly. However, while using serializers is relatively straightforward when
there is only a single shared resource (such as a single bank account),
concurrent programming can be treacherously difficult when there are multiple
shared resources.

To illustrate one of the difficulties that can arise, suppose we wish to swap
the balances in two bank accounts. We access each account to find the balance,
compute the difference between the balances, withdraw this difference from one
account, and deposit it in the other account. We could implement this as
follows:

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

This procedure works well when only a single process is trying to do the
exchange. Suppose, however, that Peter and Paul both have access to accounts
a
1, a
2, and a
3, and that Peter exchanges a
1 and a
2 while
Paul concurrently exchanges a
1 and a
3. Even with account deposits and
withdrawals serialized for individual accounts (as in the make-account
procedure shown above in this section), exchange can still produce
incorrect results. For example, Peter might compute the difference in the
balances for a
1 and a
2, but then Paul might change the balance in
a
1 before Peter is able to complete the exchange. For correct behavior, we must arrange for the
exchange procedure to lock out any other concurrent accesses to the
accounts during the entire time of the exchange.

One way we can accomplish this is by using both accounts’ serializers to
serialize the entire exchange procedure. To do this, we will arrange
for access to an account’s serializer. Note that we are deliberately breaking
the modularity of the bank-account object by exposing the serializer. The
following version of make-account is identical to the original version
given in 3.1.1, except that a serializer is provided to protect
the balance variable, and the serializer is exported via message passing:

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

We can use this to do serialized deposits and withdrawals. However, unlike our
earlier serialized account, it is now the responsibility of each user of
bank-account objects to explicitly manage the serialization, for example as
follows:

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

Exporting the serializer in this way gives us enough flexibility to implement a
serialized exchange program. We simply serialize the original exchange
procedure with the serializers for both accounts:

(define (serialized-exchange account1 account2)

(let ((serializer1 (account1 'serializer))

(serializer2 (account2 'serializer)))

((serializer1 (serializer2 exchange))

account1

account2)))

练习 3.42：Ben Bitdiddle 建议，每次收到 withdraw 和 deposit 消息时都创建一个新的串行化过程是在浪费时间。他说，make-account 可以做如下修改：将对 protected 的调用移到 dispatch 过程之外。也就是说，账户每次被要求提供取款过程时，都返回同一个串行化过程（该过程与账户同时创建）。

(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:\nMAKE-ACCOUNT”
m))))
dispatch)))

这是一个安全的改动吗？具体而言，这两个版本的 make-account 在允许的并发程度上有何区别？

使用多个共享资源的复杂性

串行化器提供了一种强大的抽象，有助于隔离并发程序的复杂性，使其能够被仔细地（并希望是正确地）处理。然而，当只有单一共享资源（例如单个银行账户）时，使用串行化器相对简单直接；一旦涉及多个共享资源，并发程序设计就可能变得极为棘手。

为了说明可能出现的一种困难，假设我们希望交换两个银行账户中的余额。我们分别访问每个账户以获取余额，计算两者的差值，从一个账户取出该差值，再存入另一个账户。可以按如下方式实现：

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

当只有单个计算过程尝试进行交换时，此过程运作正常。然而，假设 Peter 和 Paul 都能访问账户 a₁、a₂ 和 a₃，且 Peter 在交换 a₁ 和 a₂ 的同时，Paul 并发地交换 a₁ 和 a₃。即使各账户的存取操作已针对单个账户串行化（如本节上面 make-account 过程所示），exchange 仍可能产生错误的结果。例如，Peter 可能计算出 a₁ 和 a₂ 余额的差值，但在 Peter 完成交换之前，Paul 可能已经改变了 a₁ 的余额。为了保证正确的行为，我们必须安排让 exchange 过程在整个交换过程中锁定对相关账户的任何其他并发访问。

实现这一目标的一种方法是：用两个账户各自的串行化器将整个 exchange 过程串行化。为此，我们需要能够访问账户的串行化器。注意，我们在此是有意打破银行账户对象的模块性，暴露其串行化器。以下版本的 make-account 与 3.1.1 节给出的原始版本相同，区别仅在于：提供了一个串行化器来保护 balance 变量，并通过消息传递将串行化器导出：

(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:\nMAKE-ACCOUNT”
m))))
dispatch))

我们可以用它来进行串行化的存取操作。然而，与之前的串行化账户不同，现在每个银行账户对象的使用者有责任显式地管理串行化，例如：

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

以这种方式导出串行化器，使我们具备了足够的灵活性来实现一个串行化的 exchange 过程。我们只需用两个账户的串行化器将原始的 exchange 过程串行化即可：

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