SICP読書会(Section 3.4 – Exercise 3.42)

今回のあらすじ

SICPの3.4 Concurrency: Time Is of the EssenceからExercise 3.42までバリバリ読み解きます。

3.4 Concurrency: Time Is of the Essence

いつもの高尚な前振りです。

• 副作用を導入されると同じ式でも いつ 評価されたかが重要になる→時間の概念を認めざるを得ない
• 複数の処理が並列に実行されることはよくある→副作用があると物凄く大変

という訳で並列処理に纏わる話が始まるようです。

3.4.1 The Nature of Time in Concurrent Systems

銀行口座への預け入れと引き出しを例題にして並列処理×副作用=破滅になる様子がよく分かるようになってます。
という訳で本文を読み終えたとして早速問題を解きましょう。

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.

aは全て組み合わせを試せば良いので簡単ですね。

• Peter ($110) -> Paul ($90) -> Mary ($45)
• Peter ($110) -> Mary ($55) -> Paul ($35)
• Paul ($80) -> Peter ($90) -> Mary ($45)
• Paul ($80) -> Mary ($40) -> Peter ($50)
• Mary ($50) -> Peter ($60) -> Paul ($40)
• Mary ($50) -> Paul ($30) -> Peter ($40)

という訳で取り得る値は$35、$40、$45および$50の4通りです。

bは……流石に全ての組み合わせを列挙するのは現実的ではないので、
一つだけ例を挙げることにしましょう:

|    Bank       Peter                   Paul                     Mary
|
|   ($100)
|     |||
|     ||`---------------------------------------------------------.
|     |`----------------------------------.                       |
|     `-----------.                       |                       |
|                 |                       |                       |
|                 v                       |                       |
|       [Access balance: $100]            v                       |
|                 |             [Access balance: $100]            v
|                 v                       |             [Access balance: $100]
|       [new value: 100-10=90]            v                       |
|                 |             [new value: 100-20=80]            v
|                 v                       |             [new value: 100/2=50]
|       [set! balance to $90]             v                       |
|                 |             [set! balance to $80]             v
|    ($90)<-------'                       |             [set! balance to $50]
|                                         |                       |
|    ($50)<-------------------------------+-----------------------'
|                                         |
|    ($80)<-------------------------------'
v
time

こんな感じで$80が発生し得ますね。

ただ、Maryの分の新残高計算処理は(処理系の引数評価順序にも依るけれど)

1. balance 参照
2. 割り算
3. balance 参照
4. 引き算

のステップに分解できるので、
二度の balance 参照の合間に balance が書き変わる例を作った方が良かったかな……

3.4.2 Mechanisms for Controlling Concurrency

並列に実行されるプロセスに何の制約もなかったとしたら考慮すべき組み合わせが爆発的に増えてまともに動くものなんて作れやしない……
ということで制約の一種としてserializerを導入して実行を制御しようという話だそうです。

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

このコードのうち同時実行されない部分は以下の通りです:

• A: (\* x x)
• B: (set! x Aの結果)
• P: (set! x (+ x 1))

可能な組み合わせは以下の通りです:

• A (10 * 10) → B (x = 100) → P (x = 100 + 1)
• A (10 * 10) → P (x = 10 + 1) → B (x = 100)
• P (x = 10 + 1) → A (11 * 11) → B (x = 121)

よって取り得る値は100、101および121になります。

……と思ったのですが、よくよく考えるとBは s でserializeされてないですね。
だから以下のコードの断片について考える必要があります。

• A: (\* x x)
• B: (set! x Aの結果) (Aの後にしか来ない)
• P1: (+ x 1)
• P2: (set! x P1の結果) (P1の後にしか来ない/P1-P2間にAは割り込めない)

可能な組み合わせは以下の通りです:

• A (10 * 10) → B (x = 100) → P1 (100 + 1) → P2 (x = 101)
• A (10 * 10) → P1 (100 + 1) → B (x = 100) → P2 (x = 101)
• A (10 * 10) → P1 (100 + 1) → P2 (x = 101) → B (x = 100)
• P1 (10 + 1) → P2 (x = 11) → A (11 * 11) → B (x = 121)

よって取り得る値は100、101および121になります。
あれ? 結局同じか……

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

まず未serializeの場合についてです。
最初の lambda を P1、二番目の lambda を P2 と呼ぶことにします。
コードの実行過程を以下のステップに分解して考えましょう:

• P11: P1が1つめのxの値を参照する。
• P12: P1が2つめのxの値を参照する。
• P13: P1が乗算結果を代入する。
• P21: P2が1つめのxの値を参照する。
• P22: P2が2つめのxの値を参照する。
• P23: P2が3つめのxの値を参照する。
• P24: P2が乗算結果を代入する。

考えられる実行順序は以下の通りです:

• P11 (10) -> P12 (10) -> P13 (100) -> P21 (100) -> P22 (100) -> P23 (100) -> P24 (1000000)
• P11 (10) -> P12 (10) -> P21 (10) -> P13 (100) -> P22 (100) -> P23 (100) -> P24 (100000)
• P11 (10) -> P12 (10) -> P21 (10) -> P22 (10) -> P13 (100) -> P23 (100) -> P24 (10000)
• P11 (10) -> P12 (10) -> P21 (10) -> P22 (10) -> P23 (10) -> P13 (100) -> P24 (1000)
• P11 (10) -> P12 (10) -> P21 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P13 (100)
• P11 (10) -> P21 (10) -> P12 (10) -> P13 (100) -> P22 (100) -> P23 (100) -> P24 (100000)
• P11 (10) -> P21 (10) -> P12 (10) -> P22 (10) -> P13 (100) -> P23 (100) -> P24 (10000)
• P11 (10) -> P21 (10) -> P12 (10) -> P22 (10) -> P23 (10) -> P13 (100) -> P24 (1000)
• P11 (10) -> P21 (10) -> P12 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P13 (100)
• P11 (10) -> P21 (10) -> P22 (10) -> P12 (10) -> P13 (100) -> P23 (100) -> P24 (10000)
• P11 (10) -> P21 (10) -> P22 (10) -> P12 (10) -> P23 (10) -> P13 (100) -> P24 (1000)
• P11 (10) -> P21 (10) -> P22 (10) -> P12 (10) -> P23 (10) -> P24 (1000) -> P13 (100)
• P11 (10) -> P21 (10) -> P22 (10) -> P23 (10) -> P12 (10) -> P13 (100) -> P24 (1000)
• P11 (10) -> P21 (10) -> P22 (10) -> P23 (10) -> P12 (10) -> P24 (1000) -> P13 (100)
• P11 (10) -> P21 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P12 (1000) -> P13 (10000)
• P21 (10) -> P11 (10) -> P12 (10) -> P13 (100) -> P22 (100) -> P23 (100) -> P24 (100000)
• P21 (10) -> P11 (10) -> P12 (10) -> P22 (10) -> P13 (100) -> P23 (100) -> P24 (10000)
• P21 (10) -> P11 (10) -> P12 (10) -> P22 (10) -> P23 (10) -> P13 (100) -> P24 (1000)
• P21 (10) -> P11 (10) -> P12 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P13 (100)
• P21 (10) -> P11 (10) -> P22 (10) -> P12 (10) -> P13 (100) -> P23 (100) -> P24 (10000)
• P21 (10) -> P11 (10) -> P22 (10) -> P12 (10) -> P23 (10) -> P13 (100) -> P24 (1000)
• P21 (10) -> P11 (10) -> P22 (10) -> P12 (10) -> P23 (10) -> P24 (1000) -> P13 (100)
• P21 (10) -> P11 (10) -> P22 (10) -> P23 (10) -> P12 (10) -> P13 (100) -> P24 (1000)
• P21 (10) -> P11 (10) -> P22 (10) -> P23 (10) -> P12 (10) -> P24 (1000) -> P13 (100)
• P21 (10) -> P11 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P12 (1000) -> P13 (10000)
• P21 (10) -> P22 (10) -> P11 (10) -> P12 (10) -> P13 (100) -> P23 (100) -> P24 (10000)
• P21 (10) -> P22 (10) -> P11 (10) -> P12 (10) -> P23 (10) -> P13 (100) -> P24 (1000)
• P21 (10) -> P22 (10) -> P11 (10) -> P12 (10) -> P23 (10) -> P24 (1000) -> P13 (100)
• P21 (10) -> P22 (10) -> P11 (10) -> P23 (10) -> P12 (10) -> P13 (100) -> P24 (1000)
• P21 (10) -> P22 (10) -> P11 (10) -> P23 (10) -> P12 (10) -> P24 (1000) -> P13 (100)
• P21 (10) -> P22 (10) -> P11 (10) -> P23 (10) -> P24 (1000) -> P12 (1000) -> P13 (10000)
• P21 (10) -> P22 (10) -> P23 (10) -> P11 (10) -> P12 (10) -> P13 (100) -> P24 (1000)
• P21 (10) -> P22 (10) -> P23 (10) -> P11 (10) -> P12 (10) -> P24 (1000) -> P13 (100)
• P21 (10) -> P22 (10) -> P23 (10) -> P11 (10) -> P24 (1000) -> P12 (1000) -> P13 (10000)
• P21 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P11 (1000) -> P12 (1000) -> P13 (1000000)

という訳で取り得る値は以下のいずれかになります:

• 100
• 1000
• 10000
• 100000
• 1000000

次にserializeされた場合についてですが、
今度はP1とP2のステップが互い違いに実行されることは無いので、
考えられる実行順序は以下の通りです:

• P11 (10) -> P12 (10) -> P13 (100) -> P21 (100) -> P22 (100) -> P23 (100) -> P24 (1000000)
• P21 (10) -> P22 (10) -> P23 (10) -> P24 (1000) -> P11 (1000) -> P12 (1000) -> P13 (1000000)

という訳で取り得る値は1000000のみになります。

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?

balance の参照と変更はSchemeのコード上では1ステップのように見えますが、
処理系の内部処理レベルでは複数ステップになっているならBenの主張は正しいですね。

例えば

• 10進数4桁の整数が使える
• 整数は上位2桁と下位2桁に対して個別に読み書きがなされる

という謎のScheme処理系があるとしましょう。
この処理系で以下のコードを実行したとします:

(define a (make-account 1000))
(parallel-execute (lambda () ((a 'deposit) 234)  ; P1
                  (lambda () (a 'balance)))      ; P2

そうすると以下のような実行順序が考えられます:

1. P2が balance の上位2桁(10)を読む。
2. P1が234を預け入れる。 balance の値は1234になる。
3. P2が balance の下位2桁(34)を読む。結果1034を返す。

P2はP1による変更が行われる前と行われた後の環境の値を一部づつ組み合わせて結果としてしまうので、
あり得ない値が結果となってしまいます。
という訳でBenの主張が正しい世界も存在し得ます。

とはいえ、現実にはこんな処理系があるとは思えないので、
大抵の場合は単なる杞憂に過ぎないかも知れません。

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 ?

セーフですね。
serializerとは何なのかの説明として

More precisely, serialization creates distinguished sets of procedures such
that only one execution of a procedure in each serialized set is permitted to
happen at a time.

つまり

• 同じserializerでserializeされた手続きは同時に1つしか実行できないし、
• 例え同一の手続きでも同時には1プロセスしか実行できない

ということです。

Benの変更をすると同一のserializeされた手続きを複数のプロセスが同時に実行しようとする状況が発生しますが、
上記の定義に従えばこういう状況になってもやはり1プロセスしか同時には実行されないですね。

次回予告

3.4.2 Mechanisms for Controlling ConcurrencyのComplexity of using multiple shared resourcesをバリバリ読んでExercise 3.45まで解きます。