SICP 习题参考答案 3.4

win_hate

这样做是可以的，在允许的并发性上没有不同。

以 withdraw 为例子：

protected 被绑定为 (make-serializer) 返回的函数。

最初的做法，在每返回一个 withdraw 时，用这个 protected 为 withdraw 包上一层序列化代码，所有的 withdraw 都使用 protected 绑定的 (make-serializer) 调用中的互斥锁。

修改后的做法，一开始就用 protected 为 withdraw 包上一层序列化代码，得到的函数记为 protecded-withdraw。这个函数使用 protected 绑定的 (make-serializer) 调用中的互斥锁。

两种情况比较，它们都使用同一个互斥锁。但最初的做法，每次执行的序列化代码都是新的（但跟旧的比，每个字节都一致）；而修改后的做法，每次执行的都是同一"位置"的序列化代码。

由于使用相同的互斥锁，所以在互斥方面应该没有区别。但后一种做法中，序列化代码被重入了，所以那段代码应该是可重入的。从书本给出的代码来看，make-serializer 是可重入的。

win_hate

Exercise 3.43.  Suppose that the balances in three accounts start out as $10, $20, and $30, and that multiple processes run, exchanging the balances in the accounts. Argue that if the processes are run sequentially, after any number of concurrent exchanges, the account balances should be $10, $20, and $30 in some order. Draw a timing diagram like the one in figure 3.29 to show how this condition can be violated if the exchanges are implemented using the first version of the account-exchange program in this section. On the other hand, argue that even with this exchange program, the sum of the balances in the accounts will be preserved. Draw a timing diagram to show how even this condition would be violated if we did not serialize the transactions on individual accounts.

win_hate

• 由于 exhcange 是受保护的，所以即使多个进程同时访问，也会被序列化。从效果上看，就是 n 个进程依次交换这 3 个帐户。所以最后还是 10， 20 和 30。
  
• exchange 的读写是分开的。如果不对 exchange 进行整体保护，读写间可能会失去控制权。等到要写时，读进来的帐户余额可能已经发生了变化。
  
  以两个进程 A， B 为例子：
  
  
  • A 要交换帐户 a1=10, a2=20，计算出应该往 a1 中存 10，从 a2 中提 10;
  • 在 A 开始执行存取前，B 取得了控制权。B 也要交换帐户 a1, a2，他也计算出应该往 a1 中存 10，从 a2 中提 10；
  • 这时，控制权又回到 A 的手上，他存取后，a1=20, a2=10
  • 轮到 B，他存取后，a1=30, a2=0
    
  
  
• 不管有有多少个进程参与交换，设 exchange 被执行了 n 次。由于对帐户的单次修改仍是受保护的，所以这些 exchange 操作被序列化为 n 个存操作和 n 个取操作。一次 exchange 总对应一个存和一个取，且面额相同。从总额上看，这两个操作会抵消。所以 n 个 exchange 执行完后，三个帐户的总额不变。
  
• 如果连存取都不作任何保护，则总额有可能发生改变。以 A、B 进程为例。
  
  
  • A 要交换 a1=10, a2=20，他计算出存取面额为 10；
  • B 要交换 a2=20, a3=30，他计算出存取面额为 10；
  • 当 A 对 a2 提 10 时，银行计算出余额是 10。当银行准备写入时，由于不受保护，可以被中断；
  • B 往 a2 中存入 10。由于之前 A 对 a2 的提取没有完成，a2 的当前余额仍是 20，所以 a2 的余额被修改为 30。
  • A 的操作继续，银行写入 a2 当前余额为 10。这样 B 往 a2 中存入的 10 元就消失了。
  • A、B 的 exchange 完成后，a1=20, a2=10, a3= 20。总额少了 10 元。
    
  
  

[ 本帖最后由 win_hate 于 2009-1-10 16:24 编辑 ]

win_hate

Exercise 3.44.  Consider the problem of transferring an amount from one account to another. Ben Bitdiddle claims that this can be accomplished with the following procedure, even if there are multiple people concurrently transferring money among multiple accounts, using any account mechanism that serializes deposit and withdrawal transactions, for example, the version of make-account in the text above.

(define (transfer from-account to-account amount)
  ((from-account 'withdraw) amount)
  ((to-account 'deposit) amount))

Louis Reasoner claims that there is a problem here, and that we need to use a more sophisticated method, such as the one required for dealing with the exchange problem. Is Louis right? If not, what is the essential difference between the transfer problem and the exchange problem? (You should assume that the balance in from-account is at least amount.)

win_hate

不需要。

交换和转移都是从一个帐户中提取，然后存入另一个帐户中。但前者要保证变换后的 3 个余额是变换前的一个置换；而前者只需要保证 3 个帐户的余额总数不变。

win_hate

Exercise 3.45.  Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that make-account-and-serializer should have exported the serializer (for use by such procedures as serialized-exchange) in addition to (rather than instead of) using it to serialize accounts and deposits as make-account did. He proposes to redefine accounts as follows:

(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) (balance-serializer withdraw))
            ((eq? m 'deposit) (balance-serializer deposit))
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

Then deposits are handled as with the original make-account:

(define (deposit account amount)
((account 'deposit) amount))

Explain what is wrong with Louis's reasoning. In particular, consider what happens when serialized-exchange is called.

win_hate

这样做不可行。

这样修改后，用户的存取都带锁。但从书本的讨论我们知道这样并不能保证交换的正确性，所以仍需要 serialized-exchange。而 serialized-exchange 会锁定两个帐户，然后存取。但现在存取是带锁的，它们会发现帐户已经被锁定，从而被阻塞，进入死锁状态。在未修改的版本中，用户可以选择不带锁的存取操作，从而避免死锁。

[ 本帖最后由 win_hate 于 2009-1-15 11:43 编辑 ]