TIM Labs

SICP読書会(Exercise 3.48 - Exercise 3.49)

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

今回のあらすじ

SICP3.4.2 Mechanisms for Controlling ConcurrencyDeadlock からラストの Concurrency, time, and communication までバリバリ読んで、残った問題をバッサバッサと解きまくります。

Let over Lambdaの図

Deadlock

serializerを導入して一安心かと思いきや、 serialized-exchange のような簡単な例でも

  • Peterが口座a1と口座a2の残高を serialized-exchange する
  • Paulが口座a2と口座a1の残高を serialized-exchange する

という状況だと

  1. Peterがa1をロック
  2. Paulがa2をロック
  3. Peterがa2をロック......しようとするけどPaulが終わるまで待つ
  4. Paulがa1をロック......しようとするけどPeterが終わるまで待つ
  5. 結果としてお互いがお互いを待ち続ける

というデッドロック状態に陥る可能性がありますよ、というお話ですね。

簡単な対応策として

  • 各口座にユニークな番号を付ける
  • 複数の口座をロックする処理は口座の番号順にロックする

が挙げられていますが、これでも回避できない状況もあるそうです。ほうほう。

Exercise 3.48

Explain in detail why the deadlock-avoidance method described above, (i.e., the accounts are numbered, and each process attempts to acquire the smaller-numbered account first) avoids deadlock in the exchange problem.

  • Peterが口座a1と口座a2の残高を serialized-exchange する
  • Paulが口座a2と口座a1の残高を serialized-exchange する

という状況について考えてみると、

  • Peterはa1をロックしてからa2をロックしようとする
  • Paulもa1をロックしてからa2をロックしようとする

ことになるので、どちらのプロセスも処理のステップは

  1. a1をロック
  2. a2をロック
  3. 残高を交換
  4. a2のロックを解除
  5. a1のロックを解除

になります。 ロックする順序が決まっている以上、 互いが互いの必要なリソースをロックする状況は発生しませんね。

Rewrite serialized-exchange to incorporate this idea. (You will also need to modify make-account so that each account is created with a number, which can be accessed by sending an appropriate message.)

まずは口座のIDを生成する generate-account-id を定義しましょう。 複数プロセスから同時に呼ばれる可能性があるのでserializeしておく必要がありますね:

(define generate-accout-id
  (let ((id 0)
        (s (make-serializer)))
    (s (lambda ()
         (set! id (+ id 1))
         id))))

次に make-account を変更してIDを自動で割り振るようにしましょう:

(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 ((balance-serializer (make-serializer))
        (id (generate-accout-id)))  ; *********************
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            ((eq? m 'id) id)        ; *********************
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

後は口座のID順でロックを掛けるよう serialized-exhange を修正すればOKですね:

(define (serialized-exchange account1 account2)
  (define (do-exchange account1 account2)
    (let ((serializer1 (account1 'serializer))
          (serializer2 (account2 'serializer)))
      ((serializer1 (serializer2 exchange))
       account1
       account2)))
  (if (<= (account1 'id) (account2 'id))
    (do-exchange account2 account1)
    (do-exchange account1 account2)))

Exercise 3.49

Give a scenario where the deadlock-avoidance mechanism described above does not work. (Hint: In the exchange problem, each process knows in advance which accounts it will need to get access to. Consider a situation where a process must get access to some shared resources before it can know which additional shared resources it will require.)

あのデッドロック回避策はリソースのロック順序が常に固定であることが前提なので、 「あるリソースをロックしてその情報を得てからでないと次にロックすべきリソースが何か分からない」 という状況だと破綻します。

でも具体的なシナリオと言われても今一思い浮かびませんね......要点は分かってるので飛ばしましょう。

次回予告

ようやく3.4節が読み終わりました。 次回から楽しい楽しい 3.5 Streams に突入します。 先ずは軽く Exercise 3.52 まで解くことにしましょう。

トラックバック(0)

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

コメントする

このブログ記事について

このページは、kanaが2015年4月21日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「Web 管理画面の GUI から Moodle のアドオンをインストール (1)」です。

次のブログ記事は「git rebase でコンフリクトしたコミットが何かを調べる」です。

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