TIM Labs

SICP読書会(Exercise 3.43 - Exercise 3.45)

| コメント(0) | トラックバック(0)

今回のあらすじ

SICP3.4.2 Mechanisms for Controlling ConcurrencyComplexity of using multiple shared resources をバリバリ読んで Exercise 3.45 まで解きます。

並列処理のバグを埋め込んでいる図

Complexity of using multiple shared resources

depositwithdraw を組み合わせると exchange のような高レベルの操作を実現できます。 しかし depositwithdraw をserializerで保護しても、これらを組み合わせた exchange はinterleaveされる余地があるので安全ではありません。 interleaveされない為には両方の口座のserializersを使う必要がある......という話です。

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.

問題文の状況をコードにすると以下の通りです:

(define a (make-account 10))
(define b (make-account 20))
(define c (make-account 30))
(parallel-execute (lambda () (exchange a b))   ; P1
                  (lambda () (exchange b c)))  ; P2

最初のバージョンの account-exchange で残高が正常に交換できない実行例としては以下のものが考えられます:

 |        P1                 a      b      c              P2
 |        :                ($10)  ($20)  ($30)            :
 |        :  ________________|     | |     |              :
 |        :  |                     | |     |              :
 |  [Get a's balance]              | |     |              :
 |        :  |  ___________________| |     |              :
 |        v  |  |                    |     |              :
 |  [Get b's balance]                |     |              :
 |        :  |  |                    |_____|_________     :
 |        v  |  |                          |        |     v
 |  [Calculate diff (=-10)]                |     [Get b's balance]
 |        :  |  |                          |________|___  :
 |        v  |  |                                   |  |  v
 |  [Withdraw diff from a]                       [Get c's balance]
 |        :  |__|_____________                      |  |  :
 |        :     |            |                      |  |  v
 |        v     |          ($20)                 [Calculate diff (=-10)]
 |  [Deposit diff to b]                             |  |  :
 |              |____________________               |  |  v
 |                                  |            [Withdraw diff from b]
 |                                ($10)             |  |  :
 |                                  ________________|  |  :
 |                                  |                  |  v
 |                                ($20)           [Deposit diff to c]
 |                                         ____________|
 |                                         |
 |                                       ($20)
 v
time

全くserializeされていない exchange だと全口座の合計残高が変化し得る実行例としては以下のものが考えられます:

 |        P1                 a      b      c              P2
 |        :                ($10)  ($20)  ($30)            :
 |        :  ________________|     | |     |              :
 |        :  |                     | |     |              :
 |  [Get a's balance]              | |     |              :
 |        :  |  ___________________| |     |              :
 |        v  |  |                    |     |              :
 |  [Get b's balance]                |     |              :
 |        :  |  |                    |_____|_________     :
 |        v  |  |                          |        |     v
 |  [Calculate diff (=-10)]                |     [Get b's balance]
 |        :  |  |                          |________|___  :
 |        v  |  |                                   |  |  v
 |  [Withdraw diff from a]                       [Get c's balance]
 |        :  |__|_____________                      |  |  :
 |        :     |            |                      |  |  v
 |        :     |          ($20)                 [Calculate diff (=-10)]
 |        v     |                                   |  |  :
 |  [Deposit diff to b]                          [Withdraw diff from b]
 |  :           |     :                          :  |  |              :
 |  : [Get balance]   :                          : [Get balance]      :
 |  :           |     :                          :  |  |              :
 |  : [New value: 10] :                          : [New value: 30]    :
 |  :           |     :                          :  |  |              :
 |  : [Set balance]   :                          :  |  |              :
 |  :           |_____:_____________             :  |  |              :
 |  :.................:            |             : [Set balance]      :
 |                                ($10)          :  |  |              :
 |                                   ____________:__|  |              :
 |                                   |           :.....|..............:
 |                                ($30)                |  :
 |                                                     |  :
 |                                                     |  v
 |                                                [Deposit diff to c]
 |                                         ____________|
 |                                         |
 |                                       ($20)
 v
time

この2種類の実行例を示す以外に各口座の残高がどうなるかについて証明しろというサブ問題もあるのですが、 本題とは今一関係無さそうなので飛ばしましょう。

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

Louis君が言ってることなので間違いです。

transferexchange も二つの口座を扱う点は共通ですが、 前者は各口座に対して一回の操作しか行わず、 後者は各口座に対して「残高取得」「預け入れまたは払い出し」の二回の操作を行う点が異なります。

口座という共有リソースに対して複数回に渡る操作を行うなら全体をserializeする必要がありますが、 既にserializeされている depositwithdraw を一回使うだけで良いなら全体をserializeする必要はありません。

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.

これは駄目ですねー。 withdrawdeposit を自動でserializeしてしまうと、 exchange のようにこれらを組み合わせた高レベルな操作が作れなくなってしまいます。

serialized-exchange が実行される過程を考えてみましょう。 exchange は以下のステップで構成されています:

  1. 2つの口座の差分を求める
  2. 差分を一方の口座から払い出す
  3. 差分をもう一方の口座へ預け入れる

これらのステップがinterleaveされると悲惨な目に遭うので serialized-exchange は事前に exchange 全体をserializeしてから各ステップの実行を始めます。 ここでは exchange の実行がすぐに始まったとしましょう。

差分を求めるところは別に問題ありません。 差分を口座から払い出すところが問題です。 withdrawdeposit は自動でserializeされています。 もし同一のserializerでserializeされた手続きが実行中なら、 それが完了するまで待ち続けることになります。 ところが serialized-exchange が既に実行中です。 serialized-exchange 内の withdraw は大元の serialized-exchange の実行が終わるまで待たされることになります。 しかし withdraw が待たされている限り serialized-exchange の実行が終わることはありません。 自分で自分を待ち続けることになるので永久に実行が終わることはありません。

次回予告

3.4.2 Mechanisms for Controlling ConcurrencyImplementing serializers から3.4節の最後までバリバリ読み進めます。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/454

コメントする

このブログ記事について

このページは、kanaが2015年2月23日 18:16に書いたブログ記事です。

ひとつ前のブログ記事は「SICP読書会(Section 3.4 - Exercise 3.42)」です。

次のブログ記事は「SICP読書会(Exercise 3.46 - Exercise 3.47)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。