理系学生日記

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

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

serializer の実装についての話.ここでは mutex を使って,排他制御を行っている.

mutex とセマフォ

これまで mutex とセマフォの違いを,かなり曖昧なままにしてきてしまったんだけど,

セマフォをクリティカルセクションの排他制御に用いる時、セマフォでは(初期値が1でなければ)複数のタスクがクリティカルセクションへ入ることを許可するのに対し、ミューテックスでは同時に一つのタスクしかクリティカルセクションに入ることを許されない(ここで言うタスクとは、スレッドまたはプロセスを指す)。挙動はセマフォ変数の初期値を1にする事と等価。このようなタスク優先度とリンクしないミューテックスを、バイナリセマフォと呼ぶ場合もある。

狭義には、ミューテックスの場合にそれをロック(P操作)したタスクのみがアンロック(V操作)できるのに対して、セマフォではその様な制約はない。また、ミューテックスには、優先度逆転を防止するための優先度継承(Priority Inheritance)機能や、デッドロックを防止するための優先度上限プロトコル(Priority Ceiling Protocol)機能などが拡張されていることがある。

http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A5%E3%83%BC%E3%83%86%E3%83%83%E3%82%AF%E3%82%B9

というわけで,バイナリセマフォ≒ mutex な感じか.あと,誰が P 操作をしたかを認識するかしないかってのは,セマフォと mutex で違うと.ここの議論も参考になりそう.

ではなぜ2種類が用意されている(用意されている環境が存在する)のかといえば、リソースの排他的利用は非常によくあることなので、これに特化した機能を用意すればより良いであろう、というシステムデザイナの判断によるものと考えられます。

http://oshiete1.goo.ne.jp/qa1470562.html

実装

結局 serializer の実体は何かというと,排他制御の対象となる関数 f が渡されたとき,以下の関数を返す関数として定義されている.

  1. mutex を "acquire" する (P 操作)
  2. f を実行
  3. mutex を "release" する (V 操作)

これで,f を実行しているものが一つだけであることが保証できる*1

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (mutex 'acquire)
        (let ((val (apply p args)))
          (mutex 'release)
          val))
      serialized-p)))

問題3-46

test-and-set! が atomic でないとき,どういうところで mutex による排他制御が失敗するかって話で,またタイミングチャートを書けとかいうメンドい問題.

  1. あるプロセス P1 が mutex のセルを test した結果,P1 が「よっしゃ関数を実行できるぜ!」って判断
  2. ここで制御が別のプロセス P2 に切り替わる
  3. P1 は set を発行していないので,あるプロセス P2 も mutex のセルを test した結果,「よっしゃ関数を実行できるぜ!」って判断
  4. 排他制御失敗

こんな感じ.タイミングチャートは略.

*1:もちろん,f が serializer を介して呼び出されるという前提ありきの話しだけど