0

私は、生産者/消費者問題の次の解決策が機能しないことを示しようとしています.消費者がM1の先頭にある場合、有限時間内にアイテムをデキューできない場合があることを示しています.時間、および/またはプロデューサが L2 の先頭にあり、限られた時間内にアイテムをキューに入れることができない場合があります。私はそれを証明する例を見つけることができません。

このアルゴリズムでは、10 のプロデューサー、10 のコンシューマー、および 10 のバッファー サイズがあると想定しています。

nf = 0; // counting semaphore, # of items in queue
bm = 1; // binary semaphore, ensures mutex

プロデューサー

L1: Produce(item);
L2: P(bm);
If (queue_is_full) {
  V(bm);
  GoTo L2;
} else {
  Enqueue(item);
  V(bm);
  V(nf);
  GoTo L1;
}

消費者

M1: P(nf);
P(bm);
Dequeue(item);
V(bm);
Consume(item);
GoTo M1;
4

1 に答える 1

0

私の理解が正しければ、P(x) は x != 0 までロックされ、v(x) は常に x++ を実行します。

上記のコードM1: P(nf);では、アイテムがキューで利用可能な場合にのみコンシューマーを通過させます。その後、常に bm のロックを取得して解放します。したがって、コードが他のコンシューマーやプロデューサーとデッドロックすることはないと確信しています。

プロデューサでは bm を取得し、リストを操作します。v(bm) の前に他のロックを取得せず、両方のブランチで v(bm) を実行するため、確実にロックが発生します。v(bm) が最終的に発生するため、消費者は最終的にアイテムを消費できます。v(bm) av(nf) が保証された後、アイテムが生成されると、1 つの消費者が最終的にそれを消費しようとします。

したがって、listcapacity == 0 のようなばかげたものがない限り、コードは問題ないように見えます。

消費者が P(bm)-> P(nf)-> V(bm) を実行した場合に問題が発生しますが、上記のコードは正常に見えます

于 2013-04-18T03:33:43.667 に答える