Scheme - 並列性の制御機構(デッドロックとその回避方法について)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.4(並列性)、3.4.2(並列性の制御機構)、デッドロック、問題 3.48、問題 3.49を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 3.48

コード(BBEdit)

sample.scm

(define (make-account balance　id)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define id 1)
  (let ((balance-serializer (make-serializer))
      (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)))

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

口座に独自の識別番号をつけ、少ない番号の口座を保護する手続きに方が、先に入ろうとするよう、serialized-exchangeを書き直したことによって、各プロセスが共に、小さい番号の口座を獲得しようとするので、あるプロセスが小さい番号の口座を獲得したら、他のプロセスはその他の口座を獲得すること無く、保護された小さい番号の口座を獲得できるようになるまで待機することになるのでデッドロックにはならない。

問題 3.49

PaulとPeterがそれぞれ個人口座を持っていて、さらに共有口座を1つ持っているとする。各口座番号は、Paulの個人口座が1、共有口座が2、Peterの個人口座が3とする。PaulとPeterは自分自身の口座に100ドル以上残高があれば、PaulはPeter口座に、PeterはPaulの口座に10ドル移すとする。また、残高が100ドル未満の場合は共有口座から10ドル自分自身の口座に移すとする。このシナリオの場合、デッドロック会日置港が働かない場合がある。

3つの口座の残高は100ドル。Paulが口座1を保護、Peterが口座3を保護、共に100ドル以上の残高なので、PaulはPeterの口座3に10ドル移そうとするけど口座3は保護されている。また、Peterは口座1に10ドル移そうとするけど口座1はロックされている。よって、書くプロセスは相手を待ちながら、永久に立ち往生するという、デッドロック(deadlock)という状態になる。