伝統的なIPC問題

IPCとは Inter Process Communication の略で,日本語ではプロセス間通信と呼ばれる. ここではテープ装置のような入出力装置のように台数に制限のある資源をモデル化した哲学者の食事問題,データベースへのアクセスをモデル化した読者/作者問題,プロセスをCPUに割り当てたり,データの流れをパイプライン化したりする処理のモデル化した居眠りしている理髪師問題などがある.
この報告ではこれらのIPC問題について見ていく.

哲学者の食事問題

5人の哲学者がテーブルに座っている. 哲学者の前にはスパゲティのは言った皿があり,皿と皿の間にはフォークが1本ある. 哲学者はスパゲティを食べるためにフォークが2本いるとする.
哲学者は食べることと考えることを交互に行い,空腹になれば左右どちらかのフォークを一度に1本づつ手にとり,2本手にとることができれば食事を開始し,やがてそれらのフォークを置いてまた思考を続ける.
この問題の自明な解決方法を示すと,哲学者はフォークがしよう可能になるまで待機し,フォークがしよう可能になるとフォークを取り上げる等ものがある. しかし,これは全ての哲学者が同時に右側のフォークを取り上げると右側のフォークを取り上げることの出来る哲学者はいないので,デッドロックに陥る.
右側のフォークを取り上げたあと,左側のフォークが使えるかどうかを調べ,使えなければ右のフォークを戻すように変更してみても,全ての哲学者がその行動を同時に行う可能性があるため,哲学者は右のフォークを取り上げ,左のフォークが使えないので,右のフォークを戻すという作業を延々と続けることになる可能性がある. この状態を枯渇と呼ぶ.
この問題においてデッドロックも枯渇も回避する改善策の一つとして,フォークを手にとってから食事を行い,フォークをテーブルに戻すまでの一連の作業をバイナリセマフォで保護する方法がある. この様にすると理論上この問題は解決されるが,食事ができる哲学者は常に1人であるという問題がある. 5本のフォークがあるのであれば2人の哲学者が食事できるようにするべきであり,そのためには左右の哲学者の状態を調べ,左右の哲学者が食事中でない場合に限り哲学者は食事ができるようにするという方法がある.

読者/作者問題

大きなデータベースにおいては,データを読み取るプロセスとデータを書き込むプロセスが多数競合している. この競合状態においてデータを読み込むプロセスは幾らあっても問題はないが,書き込むプロセスが一つでもあると他のプロセスはデータベースにアクセスできなくなる. この問題の解決方法として,最初の読者がデータベースを読み取るときにdbというセマフォアのDOWNを行い,rcというカウンタの値を増やす. 次からの読者はrcのカウンタを増やし,読者がデータベースから抜ける際にrcの値を減らし,最後に抜けた読者がdbのUPを行うようにする. そしてブロックしていた作者がいた場合には作者にアクセス権が与えられるようにする.
この方法においては読者の方が作者よりも優先順位が高くなっている.

居眠りしている理髪師問題

居眠りしている理髪師問題においては,理髪店に理髪師が一人と理髪台が1台,そして客が座れる椅子がn脚あるとする.
客がいない場合,理髪師は散髪台に座って居眠りをしている. 客がやってくると,客は理髪師を起し散髪してもらう. 理髪師が客の髪を切っている間に更に新しく客が来た場合,その客は空いている椅子があればそこに座って待ち,空いている椅子がなければ店をさる.
この問題の解決方法として,待っている客の数を表すcustomers,待ち状態の理髪師の人数を表すbarbers,そして相互排除のためのmutexの3つのセマフォア,それと待っている客の数を表すwaitingという変数を用いる.
理髪師が店を開くとまず待ち状態になり居眠りを始める. そして最初の客がやってくると最初の客はmutexを得て,客の数が椅子の数よりも少ないかどうかを調べる. 客の数が少なければwaiting変数を増加させ,セマフォアのcustomersを増加させる. もしこのとき客の数が椅子の数よりも多ければ,客はmutexを解放して店を去る. customersを増加させることにより,理髪師が眼を覚し,waitingを減らして散髪を始める. 散髪を終わると理髪師はcustomersを減らす. 理髪師はcustomersが0でない間散髪を続け,0になると再び居眠りを始める.

        • -

輪講のレジュメ〜、とりあえず出来たのでアップ。
参考文献:OSの基礎と応用

これから tex に整形…


といいながらファイル移動やらなんやらやってたら間違えて消してしまった(笑)
日記に書いておいてよかったよ