SICP読書会(Exercise 3.48 – Exercise 3.49)

今回のあらすじ

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

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まで解くことにしましょう。