本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

令和4年度 技術士第一次試験問題【専門科目】

V−10

オペレーティングシステム上で、N個の要素を持つバッファ (有限バッファ) を介して、複数の生産者と消費者が同期をとるプログラムを考える (生産者・消費者問題)。
以下のP命令、V命令による計数セマフォを用いる。計数セマフォsは整数を値にとり、事象の発生を持つプロセスを登録するための待ち行列をQsとする。
 P(s):
  if s>0 then s ← s - 1
     else P命令を実行したプロセスをQsに入れる fi;
 V(s):
  if Qsが空でない
     then Qsからプロセス1つを取り出して実行可能にする
     else s ← s + 1 fi;
生産者・消費者問題のプログラムで用いる計数セマフォ a (生産者の相互排除)、b (消費者の相互排除)、eとf (「情報」の入ったバッファを制御する) を用意し、e = 0、f = N に初期化する。なおbuffer[]は、N個の要素を持つバッファとし、i、jは、各々生産者が情報を入れる位置を示す値と、消費者が情報を取り出す位置を示す値を格納する。

生産者
 repeat
  次の「情報」を生成する ;
   ア  ;
  P(a);
  buffer[i] に情報を入れる ;
  i ← (i+1) mod N ;
  V(a);
   イ  ;
  until false;

消費者
 repeat
   ウ  ;
  P(b);
  buffer[j] に情報を入れる ;
  j ← (j+1) mod N ;
  V(b);
   エ  ;
  情報を処理する ;
  until false;

    に入る値の組合せとして、最も適切なものはどれか。

        

@ P(e) V(e) P(f) V(f)

A P(f) V(f) P(e) V(e)

B P(e) V(f) P(f) V(e)

C P(f) V(e) P(e) V(f)

D P(e) V(f) P(e) V(f)


正解

C


解説

セマフォは、複数のプロセスが並行して動作し、一つの資源を共有する場合にそのアクセスを制御するための機構のことである。

セマフォの値は「あといくつのプロセスが使えるか」を表す。
P操作は、セマフォの値から1を引き、実行を継続する。
V操作は、セマフォの値に1を足し、待っているタスクが実行可能となる。

生産者・消費者問題では、生産者がバッファに情報を入れ、消費者がバッファから情報を取り出す。
バッファが空の場合、すなわち情報が入っていない場合、消費者は生産者が情報を入れるまで待たなければならない。
一方、バッファが満杯の場合、生産者は消費者が情報を消費するまで待たなければならない。

f = N で初期化するため、最大N個生産することができ、e = 0であるから、まだ生産されていないことが分かる。

また、問題には書かれていないが、計数セマフォ a と b の初期値は1である。
さらに係数セマフォ s と、Qssは異なるものであり、係数セマフォの s は変数扱いだが、Qsは、記号扱いである。

これらを踏まえる。


生産者と消費者のプロセスは並行処理であるが、
生産者@ ⇒ 消費者@ ⇒ 消費者A ⇒ 生産者A
の順に制御することを考える。

(1) 生産者@のプロセス
バッファに空きがあれば生産し、バッファが満杯であれば生産者プロセスを待ち行列に入れる必要があるため、アには P(f) が入る。
P(f) f = N だから、P(N) により、fが1減って、f = N-1となる。(これは、あとN-1個生産できるという意味になる。)
P(a) a = 1だから、P(1) により、aが1減って a = 0となる。
buffer[0] に情報を入れる。
i は (0+1) mod N = 1となる。
V(a) a = 0であり、Qsが空だから、aに1を加えて a = 1となる。
次は、消費者プロセスを待ち行列から取り出して実行可能状態にする必要があるため、イには V(e) が入る。
V(e) Qsが空だから、eに1を加えてe = 1となる。

(2) 消費者@のプロセス
バッファに情報があれば情報を取り出し、バッファに情報がなければ消費者プロセスを待ち行列に入れる必要があるため、ウには P(e) が入る。
P(e) e = 1だから、P(1) により、eが1減って、e = 0となる。
P(b) b = 1だから、P(1) により、bが1減って b = 0となる。
buffer[0] から情報を取り出す。
jには (0+1) mod N = 1が入る。
V(b) Qsが空だから、bに1加えて b = 1となる。
次は、生産者プロセスを待ち行列から取り出して実行可能状態にする必要があるため、エには V(f) が入る。
V(f) Qsが空だから、fに1を加えて、f = Nとなる。

(3) 消費者Aのプロセス
P(e) e = 0だから、P(0) により、消費者AのプロセスをQsに入れ、ここで、待ち状態となる。

(4) 生産者Aのプロセス
P(f) f = N だから、P(N) により、fが1減って、f = N-1となる。
P(a) a = 1であるから、P(1) により、aが1減って a = 0となる。
buffer[1] に情報を入れる。
i は (1+1) mod N = 2となる。
V(a) a = 0だから、Qsから消費者Aのプロセスを取り出して実行可能にする。
V(e) Qsが空だから、eに1を加えてe = 1となる。

(5) 消費者Aのプロセスの続き
P(b) b = 1だから、P(1) により、bが1減って b = 0となる。
buffer[1] から情報を取り出す。
jには (1+1) mod N = 2が入る。
V(b) Qsが空であるから、bに1加えて b = 1となる。
V(f) Qsが空だから、fに1を加えて、f = Nとなる。


ちなみに、(1) の生産者@のプロセスの直後に生産者Aのプロセスが実行されたときは、次のようになる。

(2') 生産者Aのプロセス
P(f) f = N - 1 だから、P(N-1) により、fが1減って、f = N-2となる。
P(a) a = 1だから、P(1) により、aが1減って a = 0となる。
buffer[1] に情報を入れる。
i は (1+1) mod N = 2となる。
V(a) a = 0であり、Qsが空だから、aに1を加えて a = 1となる。
V(e) Qsが空だから、eに1を加えてe = 2となる。

なお、N個の生産者プロセスが続けば、f = 0 となり、
P(f) f = 0 だから、このプロセスを待ち行列Qsに入れることになる。

V−9 目次 V−11