理系学生日記

おまえはいつまで学生気分なのか

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

Louis Reasoner (人名) は大抵間違っているんですけど,今回も間違いやがったらしい.
今回 Louis Reasoner が作ったのは,自動的に関数を直列化して返す銀行口座.

(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))

ユーザがいちいち直列化しなくてよさそうで,なんて便利なんだーとかそういう感じですけど,serialized-exchange が呼ばれると困った状況になる.

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    ((serializer1 (serializer2 exchange))
     account1
     account2)))

serialized-exchange では,account1 の serializer と account2 の serializer がともに exchange を直列化してるんですけど,この段階で両 account は他の関数の実行ができない状態になっています.そして exchange が呼び出されるわけですが,exchange は以下のような形で定義されています.

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance))))
    ((account1 'withdraw) difference)
    ((account2 'deposit) difference)))

withdraw,deposit ともに直列化されたものですから,このとき withdraw や deposit の実行はできません.account の開放を待ち続けますが,account 自身はこれらの withdraw,deposit が終わらないと開放されませんから,いわゆるデッドロックの状態になるのかなと.