人気ブログランキング | 話題のタグを見る
有限バッファ問題
以下、引用---
生産者-消費者問題(有限バッファ問題)
 マルチスレッドのプログラムでは、おにぎり作りのような協調作業が必要なことがよくあります。その場合、複数のスレッドが協調するわけですから、各スレッドが握り係や海苔係のように動作するということになります。

 おにぎり作りの例で見たように、流れ作業において、握り係と海苔係の作業の速度に差があることから生じる問題のことを、「生産者-消費者問題(producer-consumer problem)」と言います。これは、生産者が何かを生産し、消費者がそれを消費するときに起きる問題です。

 おにぎり作りで言えば、握り係は「生産者」で、(海苔を巻いていない)おにぎりを生産します。一方、海苔係は「消費者」で、握り係が生産したおにぎりを消費します。マルチスレッドのプログラムであれば、あるスレッド(生産者スレッド)が何らかのデータを生産し、別のスレッド(消費者スレッド)がそのデータを消費します。

 生産者-消費者問題を解決するためには、一般に、生産者と消費者の間にバッファを置きます。そのバッファは、おにぎり作りにおいて、皿が果たしていた役割を担います。また、通常そのバッファの大きさには限りがあります。つまり、お皿に載せられるおにぎりの個数には限りがあるということです。なお、バッファのほうに着目して、生産者-消費者問題のことを「有限バッファ問題(bounded buffer problem)」と呼ぶこともあります。

 マルチスレッドにおける生産者-消費者問題を解決するというのは、生産者スレッドと消費者スレッドが有限のバッファを介して協調動作するプログラムを作るということです。

 ところで、おにぎり作りの例で説明したように、待ち方にはビジー・ウェイトと通知の2とおりがありました。

 ビジー・ウェイトの場合、待つためだけにそのスレッドが動作し続けてコンピュータの資源を消費することになるので、あまり良い方法ではありません。一方、通知による方法の場合、スレッドが休憩室で休んでいる間は、そのコンピュータの資源をほかの用途に使えます(人間だと、頻繁に寝たり起きたりしたらそれだけで疲れてしまいますが、スレッドであれば問題はありません)。したがって、生産者-消費者問題は通知による方法で解決するのが妥当です。

 以下のような動作を実現できれば、生産者-消費者問題を解決することができます。

●生産者は、バッファがいっぱいなら待つ
●消費者は、バッファがいっぱいでなくなったら生産者に通知する
●消費者は、バッファが空なら待つ
●生産者は、バッファが空でなくなったら消費者に通知する

 念のため、おにぎり作りの場合に当てはめてみると、以下のようになります。

●握り係は、皿がいっぱいなら寝る
●海苔係は、皿がいっぱいでなくなったら握り係を起こす
●海苔係は、皿が空なら寝る
●握り係は、皿が空でなくなったら海苔係を起こす

 これできちんと協調作業ができそうですね。
-----

参考文献:http://www.itarchitect.jp/technology_and_programming/-/10941.html
by besttseb99 | 2007-05-30 01:58 | Study
<< 岡田了一郎(駿台予備校) 夢は見るものじゃない、叶えるもの >>