問題3-48 (3.4.1 The Nature of Time in Concurrent Systems)

複数のプロセスが共有資源をアクセスする場合において，各プロセスが資源を確保する順番を同じにしておくと，デッドロックを回避できる(場合がある)がそれはなぜ，という問題．

デッドロックは，あるプロセス A がロックをかけた資源 a に対し他のプロセス B がアクセス待ちの状態になり，そしてそのプロセス B は資源 b をロックしていて，プロセス A が資源 b にアクセスするための待ち状態にあって，互いが待ち状態になるという，全く動けない状態．もちろん，プロセスが二つの状態に限らず，三つでも四つでも起こり得る問題になります．

資源確保の順番を複数のプロセスについて同じにするとなぜデッドロックが回避できるのかというと，互いに待ち合うことがなくなるため．プロセス A も B も，まず資源 a にアクセスするようになっているとすれば，先にプロセス A が資源 a をロックすると，プロセス B は資源 a をアクセスするための待ち状態に入る．プロセス B は a が解放 (アンロック) されるまではずっと待ちで，他の資源には手が出せない．結果として，プロセス A は a を解放後，次の(ロックされていない)資源をアクセスすることができるようになる．

一般化した議論は相当込み合った話になることが予想されるので，OS かなんかの教科書を読んだ方が良さそう．

ちなみに，今作ってみたコードはこちら．serialized-exchange を書き換えるというよりは，exchange を書き換えた方が良いのかなーなどと思った．

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance)))
        (id1 (account1 'id?))
        (id2 (account2 'id?)))
    (if (< id1 id2)
        (begin
          ((account1 'withdraw) difference)
          ((account2 'deposit) difference))
        (begin
          ((account2 'deposit) difference)
          ((account1 'withdraw) difference)))))

(define (make-account balance n)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) (protected withdraw))
            ((eq? m 'deposit) (protected deposit))
            ((eq? m 'balance) balance)
            ((eq? m 'id?) n)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))