SICP 习题参考答案 3.4

win_hate

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

• 本节电子版：[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 之前。
  
  可能的序列个数为：binomial(6,2)*binomial(4,2)=90
  
  其中一些序列生成的最终值是相同的。
  
  一个例子：A1 B1 B2 C1 C2 A2
  
  开始有 100 元。Paul 得到了 20， Mary 得到了 40，Peter 存入了 10 元。但银行里现在有 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 设置新值 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

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

设第一个 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

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 ?