ウォンツテック

そでやまのーと

セマフォ

UNIX

詳解UNIXプログラミングを勉強しててセマフォが出てきたので
ちょっと覚え書き（内容間違ってるかもしれない）


プロセス間通信において複数のプロセスが同時に共有リソース（メモリなど）
にアクセスしようとした場合意図しない結果（競合状態）となる事がある。
その中で生産者と消費者の問題というのがあってタネンバウムさんのMINIX本
によると以下のような内容になってる

[前提]
一対の生産者と消費者が存在し、生産者が新しい項目をバッファに
入れようとし、バッファがすでに一杯の時は生産者はスリープ状態
に入り、消費者が項目を一つ以上削除したときにウェイクアップす
る。同様に消費者がバッファから項目を削除しようとしてそれが空
であった場合、生産者がバッファに項目を一つ以上追加して消費者
をウェイクアップするまでスリープ状態となる。
[致命的な競合]
消費者がバッファの項目数(count)を読み込みcountが0であることを
調べた時、OSのスケジューラが消費者を一時的に停止し、生産者を
実行させるたとする。生産者はバッファに項目を入れてcountを増分
させる。この時countは1なので、生産者は「消費者はcount 0で待機
しているだろうから呼び出して起こしてあげよう」と考える。とこ
ろが、消費者はsleepする前にOSのスケジューラによって切り替えら
れてしまったためまだsleepしていない。よって生産者が出した
wakeupシグナルは破棄されてしまう。消費者がスケジューラによって
次に実行される時はいきなりsleepする。この後スケジューラは
消費者と生産者を交互にスケジューリングしていくが消費者の方は
寝っぱなしで、生産者はバッファに項目を追加し続ける(count > 0
なのでwakeupシグナルを消費者に対して出す事は無い)。終いに
生産者はバッファを満杯にした後sleepする。結果として両者は永遠
にsleep状態となってしまう。

これを回避するために考え出されたのがセマフォでDijkstraさんが
1965年に発表してくれました。

基本的な考え方としては先ほどのwakeupシグナルが破棄される所に
問題があるため、新しい変数型セマフォを用いwakeupが発生したら
破棄せずにセマフォ値を増やす。これを一般化しDOWN, UPという
システムコールを考える。

①DOWNの定義
DOWNの操作はセマフォ値が0より大きいか調べ、大きければその値を減少し、
0であればDOWNを完了せずにスリープ状態に入る。ここで値の検査、変更、
その後に行われるスリープへの移行はアトミックな処理として実行される。
②UPの定義
UPの操作はセマフォ値を増分する役目だが、そのセマフォ上にDOWN操作を
完了できずにスリープ中のプロセスが一つでもあれば、DOWN操作を完了
出来るようにする。この時セマフォ値は増分されず0のまま。


セマフォ値が1の時をバイナリセマフォと言い排他制御に使われて、
セマフォ値が1より大きい場合はプロセスの同期に使うらしい。


排他制御の時の使われ方を自分なりにちょっと考えてみる。<思考>
プロセスp1,p2がありそれぞれ共有リソースAにアクセスしようとしている
とする。またバイナリセマフォ値semを用意する。
p1はAにアクセスする時にsemに対してDOWN操作(down(&sem))を行う。この時
p1はAに対して読み書きを行えるが、その瞬間p2がAにアクセスしようとして
DOWN操作(down(&sem))を行おうとするが、semは先ほどのp1のDOWN操作により
0になっているのでp2のDOWN操作ではp2はスリープ状態となる。(①より)
これによりp1はAに対して安全に操作でき、その後p1がUP操作(up(&sem))が
行われれば②よりp2のDOWN操作を完了させAにアクセス出来るようになる。
この時、またp1がAにアクセスしようとしてもsemは0のままなので、DOWN
操作でスリープ状態となってしまう。
　もしDOWNやUP操作がアトミックで無いとする。p1がAにアクセスする前
のDOWN操作でsem値が0である事を確認してp1がスリープする前にOSのスケ
ジューラによりp2が実行されてしまった場合、p2はsem値がまだ0なのでDOWN
操作でスリープ状態となる。その後p1が実行されればp1もsleepとなり、お互
い永遠にスリープ状態となってしまう。
したがってUP、DOWN操作はアトミックである事が必要。


しかし、詳解UNIXで出てくるセマフォ用の構造体とか複数のセマフォ値の集合
だとかどう使われるんだかさっぱわからん。
なんかいいソースないかな。