問１ 問２ 問３ 問４ 問５ 問６ 解答例（若林研二氏）
問５
プロセス間の協調に関する次の記述を読んで，設問１～４に答えよ。
複数のプロセス間の排他制御を実現するために，次のP，Vの操作が可能なデータ
型の変数Sを定義する。
P(S):
S≧1の場合は，S←S－1とし，Pを実行したプロセスがそのまま実行を継続す
る。
S＜1の場合は，Pを実行したプロセスはSの待ち行列に入れられ，そのプロセ
スは待機状態に移る。
V(S):
(Sの待ち行列に入っているプロセス数)≧1の場合は、Sの待ち行列からプロ
セスが一つ取り出される。取り出されたプロセスは実行可能状態に移る。
(Sの待ち行列に入っているプロセス数)＝0の場合は，S←S＋1とし，Vを実
行したプロセスがそのまま実行を継続する。
ここで，複数のプロセスで共有するリソースRがある。リソースRは，それぞれの
プロセスが排他的に使用する。Rを使用する二つのプロセスX，Yが並行して動作し
ている場合，上で定義した変数Sと，P(S)及びV(S)操作を使って排他制御を行うこ
とができる。
また，上で定義した変数を利用すると，並行して動作するプロセスを協調して動作
させることができる。例えぱ，図１のようにＮ個のスロットをもつバッファを使って，
生産者プロセスから消費者プロセスヘメッセージを送ることを考える。生産者，消費
者プロセスは並行に動作し，生産者プロセスは生成したメッセージを順番にバッファ
に入れる操作を行い，消費者プロセスはバッファから順にメッセージを取り出す操作
を行う。取り出されたメッセージは，バッファからなくなるものとする。
ここで，生産者プロセスは，バッファがいっぱいのときはメッセージを入れるのを
停止し，バッファが空くのを待つ。また，消費者プロセスは，メッセージが入ってい
ない空のバッファからメッセージを取り出せない。
設問１
P，Vの操作に関する次の問いに答えよ。
(1) P，Vの操作が可能な変数Sのことを何と呼ぶか。
(2) プロセスXとYが一つのリソースRを共有して，排他的に使用する場合の処
理の流れを図２に示す。図２中の【 ア 】～【 ウ 】こ入れる適切な字
句を答えよ。ただし，プロセスX，Yは，それぞれリソースRを利用する処理
と，Rを利用する以外の処理を繰り返して行うプロセスである。
設問２
図１で説明したプロセス間通信において，生産者プロセスと消費者プロセスが
一つずつの場合を考える。このとき，生産者プロセスをA，消費者プロセスをB
とし，P，Vの操作が可能な変数SlとS2を導入して，プロセス間通信を実現する
場合の処理の流れを図３に示す。図３中の【 エ 】～【 キ 】に入れる適
切な字句を答えよ。
設問３
図１で説明した複数の生産者，消費者プロセスによるプロセス間通信を，図３
のアルゴリズムを拡張し，P，Vの操作が可能な新たな変数SA，SBを導入して実
現することを考える。実現方法の一部を図４に示す。
なお，図４中の【 エ 】～【 キ 】は，図３と同じものが入る。また，
図４中の i とSAは生産者プロセス間で共有される変数であり，j とSBは消費者プ
ロセス間で共有される変数である。図４中の消費者プロセス，生産者プロセスの
動作は，個々のプロセスの動作を示している。このとき，次の問いに答えよ。
(1) 図４中の【 ク 】，【 ケ 】に入れる適切な字句を答えよ。
(2) 複数の生産者，消費者間でのプロセス間通信を実現するためには，図４に
P(SA)，V(SA)，P(SB)，V(SB)の各処理を加える必要がある、図４の(a)～(l)で
示されるどの場所に加える組合せが適切か。解答群の①～⑥の中から選べ。
解答群
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
設問４
プロセスの状態遷移に関する次の問いに答えよ。
(1) OSの管理するプロセスは，図５に示すように三つの状態に分類され，プロセ
スはそれらの状態間を遷移する。図５の a，b，c に当てはまる状態名の組合せ
を，解答群の①～⑥の中から選べ。
解答群
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2) プロセスXとYがリソースRを共有して使用する場合を考える。OSは，そ
れぞれのプロセスがもつ優先度の高い順に，各プロセスにCPUを割り当て実行
させる。
ここでは，プロセスX，Yを次の条作で動作させる。
・プロセスX，Yは，一つの共有リソースRを，図２のアルゴリズムを使って
排他的に使用する。また，X，YはR以外のリソースは使用しない。
・プロセスX，Y以外のプロセスは存在せず，プロセスYよりも先にプロセス
Xが実行可能になる。
・プロセスXの優先度より，プロセスYの優先度が高い。
このときのプロセスX，Yの実行状況を示したのが，図６である。実線で示
した部分はプロセスが実行されていることを示し，破線で示した部分はリソー
スRを使用している状態である。図６中，ア～ウのそれぞれの時刻におけるプ
ロセスX，Yの状態名を答えよ。
------------------------------------------------------------------------