Chinaunix

标题: SICP 习题参考答案 3.4 [打印本页]

---

作者: win_hate    时间: 2009-01-05 11:44
标题: SICP 习题参考答案 3.4

此帖为 SICP 章节 3.4 的参考答案。为保持可读性，请勿直接在本帖讨论。讨论请另开新帖。

• 本节电子版：[Concurrency: Time Is of the Essence]
  
• 答案目录：[点这里]
  

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

---

作者: win_hate    时间: 2009-01-05 11:46
标题: Exercise 3.38.
Exercise 3.38.  Suppose that Peter, Paul, and Mary share a joint bank account that initially contains $100. Concurrently, Peter deposits $10, Paul withdraws $20, and Mary withdraws half the money in the account, by executing the following commands:
Peter:         (set! balance (+ balance 10))
Paul:         (set! balance (- balance 20))
Mary:         (set! balance (- balance (/ balance 2)))

a. List all the different possible values for balance after these three transactions have been completed, assuming that the banking system forces the three processes to run sequentially in some order.

b. What are some other values that could be produced if the system allows the processes to be interleaved? Draw timing diagrams like the one in figure 3.29 to explain how these values can occur.

---

作者: win_hate    时间: 2009-01-05 11:49
标题: Exercise 3.38. 答案

• + 和 - 连用时次序可交换，总共有四种可能：
  
  (100 + 10 - 20)/2 = 45
  (100 + 10)/2 - 20 = 35
  (100 - 10)/2 - 20 = 25
  (100/2 + 10 - 20) = 40
  
• 假定没个人的操作都可以分为两步，访问值，赋值。把 A 的两个步骤记为 A1, A2，B,C 类似。
  
  可能的序列为 A1, A2, B1, B2, C1, C2 的一个排列，但其中 A1 在 A2 之前，B1 在 B2 之前，
  C1 在 C2 之前。
  
  可能的序列个数为：binomial(6,2)*binomial(4,2)=90
  
  其中一些序列生成的最终值是相同的。
  
  一个例子：A1 B1 B2 C1 C2 A2
  
  开始有 100 元。Paul 得到了 20， Mary 得到了 40，Peter 存入了 10 元。但银行里现在有 110 元!

  ---

  作者: win_hate    时间: 2009-01-06 10:57
  标题: Exercise 3.39.
  Exercise 3.39.  Which of the five possibilities in the parallel execution shown above remain if we instead serialize execution as follows:
  
  (define x 10)
  
  (define s (make-serializer))
  
  (parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))
                    (s (lambda () (set! x (+ x 1)))))

  ---

  作者: win_hate    时间: 2009-01-06 10:59
  标题: Exercise 3.39. 答案
  第一个 lambda 中有两个基本操作：
  
  A) 访问 x
  B) 为 x 设置新值 x^2
  
  第二个 lambda 整个是受保护的：
  
  C) 为 x 设置新值 x+1
  
  A, B 必定是顺序出现的，所以可能时序只有三种：
  
  C A B, A C B, A B C
  
  对应的值为：
  
  121, 100, 101
  
  [ 本帖最后由 win_hate 于 2009-1-7 09:03 编辑 ]

  ---

  作者: win_hate    时间: 2009-01-07 09:02
  标题: Exercise 3.40.
  Exercise 3.40.  Give all possible values of x that can result from executing
  
  (define x 10)
  
  (parallel-execute (lambda () (set! x (* x x)))
                    (lambda () (set! x (* x x x))))
  
  Which of these possibilities remain if we instead use serialized procedures:
  
  (define x 10)
  
  (define s (make-serializer))
  
  (parallel-execute (s (lambda () (set! x (* x x))))
                    (s (lambda () (set! x (* x x x)))))

  ---

  作者: win_hate    时间: 2009-01-07 09:04
  标题: Exercise 3.40. 答案
  设第一个 lambda 的两个基本操作为 A1, A2，第二个 lambda 的两个基本操作为 B1, B2。
  
  可能的时序为有 6 个：
  
  A1 A2 B1 B2 -> 1000000
  A1 B1 A2 B2 -> 1000
  A1 B1 B2 A2 -> 100
  B1 A1 A2 B2 -> 1000
  B1 A1 B2 A2 -> 100
  B1 B2 A1 A2 -> 1000000
  
  用 make-serializer 把两个 lambda 完全保护起来后，A1 A2 是不可分的， B1 B2 也是。
  
  所以可能的序列剩下两个：
  
  A1 A2 B1 B2 -> 1000000
  B1 B2 A1 A2 -> 1000000
  
  它们产生相同的最终效果。这是因为 (x^a)^b = (x^b)^a

  ---

  作者: win_hate    时间: 2009-01-09 10:33
  标题: Exercise 3.41.
  Exercise 3.41.  Ben Bitdiddle worries that it would be better to implement the bank account as follows (where the commented line has been changed):
  
  (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)
    ;; continued on next page
  
    (let ((protected (make-serializer)))
      (define (dispatch m)
        (cond ((eq? m 'withdraw) (protected withdraw))
              ((eq? m 'deposit) (protected deposit))
              ((eq? m 'balance)
               ((protected (lambda () balance)))) ; serialized
              (else (error "Unknown request -- MAKE-ACCOUNT"
                           m))))
      dispatch))
  
  because allowing unserialized access to the bank balance can result in anomalous behavior. Do you agree? Is there any scenario that demonstrates Ben's concern?
  
  [ 本帖最后由 win_hate 于 2009-1-9 10:36 编辑 ]

  ---

  作者: win_hate    时间: 2009-01-09 10:35
  标题: Exercise 3.41. 答案
  这样做是多余的，因为查看余额不会修改 balance 变量。

  ---

  作者: win_hate    时间: 2009-01-09 10:36
  标题: 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 ?

  ---

  作者: win_hate    时间: 2009-01-09 11:00
  这样做是可以的，在允许的并发性上没有不同。
  
  以 withdraw 为例子：
  
  protected 被绑定为 (make-serializer) 返回的函数。
  
  最初的做法，在每返回一个 withdraw 时，用这个 protected 为 withdraw 包上一层序列化代码，所有的 withdraw 都使用 protected 绑定的 (make-serializer) 调用中的互斥锁。
  
  修改后的做法，一开始就用 protected 为 withdraw 包上一层序列化代码，得到的函数记为 protecded-withdraw。这个函数使用 protected 绑定的 (make-serializer) 调用中的互斥锁。
  
  两种情况比较，它们都使用同一个互斥锁。但最初的做法，每次执行的序列化代码都是新的（但跟旧的比，每个字节都一致）；而修改后的做法，每次执行的都是同一"位置"的序列化代码。
  
  由于使用相同的互斥锁，所以在互斥方面应该没有区别。但后一种做法中，序列化代码被重入了，所以那段代码应该是可重入的。从书本给出的代码来看，make-serializer 是可重入的。

  ---

  作者: win_hate    时间: 2009-01-10 13:00
  标题: Exercise 3.43.
  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    时间: 2009-01-10 13:02
  标题: Exercise 3.43. 答案
  
  • 由于 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    时间: 2009-01-15 11:40
  标题: Exercise 3.44.
  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    时间: 2009-01-15 11:41
  标题: Exercese 3.44. 答案
  不需要。
  
  交换和转移都是从一个帐户中提取，然后存入另一个帐户中。但前者要保证变换后的 3 个余额是变换前的一个置换；而前者只需要保证 3 个帐户的余额总数不变。

  ---

  作者: win_hate    时间: 2009-01-15 11:41
  标题: Exercise 3.45.
  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    时间: 2009-01-15 11:42
  这样做不可行。
  
  这样修改后，用户的存取都带锁。但从书本的讨论我们知道这样并不能保证交换的正确性，所以仍需要 serialized-exchange。而 serialized-exchange 会锁定两个帐户，然后存取。但现在存取是带锁的，它们会发现帐户已经被锁定，从而被阻塞，进入死锁状态。在未修改的版本中，用户可以选择不带锁的存取操作，从而避免死锁。
  
  [ 本帖最后由 win_hate 于 2009-1-15 11:43 编辑 ]
  
  
  
  

  ---

  欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

  Powered by Discuz! X3.2