SICP 習(xí)題參考答案 3.4

win_hate

此帖為 SICP 章節(jié) 3.4 的參考答案。為保持可讀性，請勿直接在本帖討論。討論請另開新帖。

• 本節(jié)電子版：[Concurrency: Time Is of the Essence]
  
• 答案目錄：[點這里]
  

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

win_hate

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

• + 和 - 連用時次序可交換，總共有四種可能：
  
  (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 之前。
  
  可能的序列個數(shù)為：binomial(6,2)*binomial(4,2)=90
  
  其中一些序列生成的最終值是相同的。
  
  一個例子：A1 B1 B2 C1 C2 A2
  
  開始有 100 元。Paul 得到了 20， Mary 得到了 40，Peter 存入了 10 元。但銀行里現(xiàn)在有 110 元!

win_hate

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

第一個 lambda 中有兩個基本操作：

A) 訪問 x
B) 為 x 設(shè)置新值 x^2

第二個 lambda 整個是受保護(hù)的：

C) 為 x 設(shè)置新值 x+1

A, B 必定是順序出現(xiàn)的，所以可能時序只有三種：

C A B, A C B, A B C

對應(yīng)的值為：

121, 100, 101

[ 本帖最后由 win_hate 于 2009-1-7 09:03 編輯 ]

win_hate

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

設(shè)第一個 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 完全保護(hù)起來后，A1 A2 是不可分的， B1 B2 也是。

所以可能的序列剩下兩個：

A1 A2 B1 B2 -> 1000000
B1 B2 A1 A2 -> 1000000

它們產(chǎn)生相同的最終效果。這是因為 (x^a)^b = (x^b)^a

win_hate

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

這樣做是多余的，因為查看余額不會修改 balance 變量。

win_hate

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 ?