例: 生産者/消費者問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/15 04:56 UTC 版)
「セマフォ」の記事における「例: 生産者/消費者問題」の解説
生産者/消費者問題（英語版）では、1つの実行単位（生産者）がデータを生成し、もう1つの実行単位（消費者）がそれらを受け取って使用する。データの受け渡しは最大サイズNのキューで行い、次のような条件に従う。 キューが空の場合、消費者は生産者がデータを生成するのを待たなければならない。 キューが満杯の場合、生産者は消費者がデータを消費するのを待たなければならない。 生産者/消費者問題をセマフォで解決する場合、キューの状態を2つのセマフォで表す。emptyCount はキュー上の空いているスロット数を保持し、fullCount はキュー上の要素数を保持する。完全性を維持するには、emptyCount を実際の空きスロット数より小さくなるようにし、fullCount を実際のキュー上の要素数より小さくなるようにする（どちらも実際の数を越えてはならない）。空きスロットと要素は、空の箱と満たされた箱という2種類の資源を表しており、セマフォ emptyCount と fullCount はそれら資源についての制御を管理する。 バイナリセマフォ useQueue は、例えば2つの生産者が同時にデータをキューに格納しようとするなどといった不正な状態が発生しないことを保証するためにある。このバイナリセマフォはミューテックスで代替することもできる。 emptyCount の初期値は N、fullCount の初期値は0、useQueue の初期値は1である。生産者は次のような処理を繰り返す。 produce: P(emptyCount) P(useQueue) putItemIntoQueue(item) V(useQueue) V(fullCount) 消費者は次のような処理を繰り返す。 consume: P(fullCount) P(useQueue) item ← getItemFromQueue() V(useQueue) V(emptyCount) 具体的には次のような動作をする。 1つの消費者がクリティカルセクションに入る。fullCount は0なので、消費者はブロックする。 いくつかの生産者が生産者側のクリティカルセクションに入る。emptyCount で制限されるのでN以上の生産者はクリティカルセクションに入れない。 生産者は useQueue により一度に1つずつキューにアクセスし、データをキューに入れていく。 最初の生産者がクリティカルセクションを抜けるとき、fullCount がインクリメントされるので、ブロックしていた消費者がクリティカルセクション内の処理に進むことができる。 emptyCount はキュー上の実際の空きスロット数より小さくなる可能性がある。例えば、複数の生産者がデクリメントを行っても、useQueue によってキューへのデータ投入は逐次化されるためである。したがって常に emptyCount + fullCount ≤ N であり、等号が成り立つのは生産者も消費者も全くクリティカルセクションに入っていない場合だけである。
※この「例: 生産者/消費者問題」の解説は、「セマフォ」の解説の一部です。
「例: 生産者/消費者問題」を含む「セマフォ」の記事については、「セマフォ」の概要を参照ください。
- 例: 生産者/消費者問題のページへのリンク
