今回のあらすじ
SICPの3.4.2 Mechanisms for Controlling ConcurrencyのComplexity of using multiple shared resourcesをバリバリ読んでExercise 3.45まで解きます。
Complexity of using multiple shared resources
deposit や withdraw を組み合わせると exchange のような高レベルの操作を実現できます。
しかし deposit や withdraw を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 theaccount-exchangeprogram in this section. On the other
hand, argue that even with thisexchangeprogram, 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 ofmake-accountin
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 infrom-accountis at leastamount.)
Louis君が言ってることなので間違いです。
transfer も exchange も二つの口座を扱う点は共通ですが、
前者は各口座に対して一回の操作しか行わず、
後者は各口座に対して「残高取得」「預け入れまたは払い出し」の二回の操作を行う点が異なります。
口座という共有リソースに対して複数回に渡る操作を行うなら全体をserializeする必要がありますが、
既にserializeされている deposit や withdraw を一回使うだけで良いなら全体を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 thatmake-account-and-serializershould have
exported the serializer (for use by such procedures asserialized-exchange)
in addition to (rather than instead of) using it to serialize accounts and
deposits asmake-accountdid. 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 whenserialized-exchangeis called.
これは駄目ですねー。withdraw や deposit を自動でserializeしてしまうと、exchange のようにこれらを組み合わせた高レベルな操作が作れなくなってしまいます。
serialized-exchange が実行される過程を考えてみましょう。exchange は以下のステップで構成されています:
- 2つの口座の差分を求める
- 差分を一方の口座から払い出す
- 差分をもう一方の口座へ預け入れる
これらのステップがinterleaveされると悲惨な目に遭うのでserialized-exchange は事前に exchange 全体をserializeしてから各ステップの実行を始めます。
ここでは exchange の実行がすぐに始まったとしましょう。
差分を求めるところは別に問題ありません。
差分を口座から払い出すところが問題です。withdraw や deposit は自動でserializeされています。
もし同一のserializerでserializeされた手続きが実行中なら、
それが完了するまで待ち続けることになります。
ところが serialized-exchange が既に実行中です。serialized-exchange 内の withdraw は大元の serialized-exchange の実行が終わるまで待たされることになります。
しかし withdraw が待たされている限り serialized-exchange の実行が終わることはありません。
自分で自分を待ち続けることになるので永久に実行が終わることはありません。
次回予告
3.4.2 Mechanisms for Controlling ConcurrencyのImplementing serializersから3.4節の最後までバリバリ読み進めます。
＃人気の記事
＃タグ
