2

生産者と消費者の問題の古典的なアルゴリズムについて私が理解していないこと (ウィキペディアから:)

セマフォミューテックス = 1
セマフォのfillCount = 0
セマフォ emptyCount = BUFFER_SIZE

手続きプロデューサー() {
    while (真) {
        item = ProduceItem()
        down(emptyCount)
            ダウン (ミューテックス)
                putItemIntoBuffer(アイテム)
            アップ (ミューテックス)
        up(fillCount)
    }
    up(fillCount) //消費者は生産者の前に終了しない可能性があります。
}

手続き消費者() {
    while (真) {
        down(fillCount)
            ダウン (ミューテックス)
                item = removeItemFromBuffer()
            アップ (ミューテックス)
        アップ (emptyCount)
        消費アイテム（アイテム）
    }
}

プロデューサーとコンシューマーの両方が、バッファーをいじる前に「ミューテックス」をロックし、その後ロックを解除することに注意してください。その場合、つまり、任意の時点で単一のスレッドのみがバッファーにアクセスしている場合、上記のアルゴリズムが、保護ミューテックスをバッファーに配置するだけの単純なソリューションとどのように異なるかはわかりません。

セマフォミューテックス = 1

手続きプロデューサー() {
    while (真) {
        item = ProduceItem()
        フラグ = 真
        while (フラグ) {
            ダウン (ミューテックス)
            if (bufferNotFull()) {
                putItemIntoBuffer(アイテム)
                フラグ = false
            }
            アップ (ミューテックス)
        }
    }
}


手続き消費者() {
    while (真) {
        フラグ = 真
        while (フラグ) {
            ダウン (ミューテックス)
            if (bufferNotEmpty()) {
                item = removeItemFromBuffer()
                フラグ = false
            }
            アップ (ミューテックス)
        }
        消費アイテム（アイテム）
    }
}

「fillCount」および「emptyCount」セマフォを使用する必要があると私が考えることができる唯一のものは、スケジューリングです。

おそらく最初のアルゴリズムは、5 つのコンシューマーが空のバッファー (ゼロ 'fillCount') で待機している状態で、新しいプロデューサーが登場したときに、その "down(emptyCount)" を通過することを保証するためのものです。ステートメントをすばやく実行し、「ミューテックス」をすばやく取得します。

(一方、他のソリューションでは、新しいプロデューサーがそれを取得してアイテムを挿入するまで、消費者は不必要に「ミューテックス」を取得して放棄するだけです)。

私は正しいですか？何か不足していますか？

4

4 に答える 4

3

バッファーにメッセージがない場合、コンシューマーはミューテックスをダウンさせ、バッファーをチェックし、バッファーが空であることを確認し、ミューテックスをアップしてループバックし、すぐにプロセスを繰り返します。簡単に言えば、消費者と生産者は、CPU コアを 100% 食い尽くすビジー ループに陥っています。これも単なる理論上の問題ではありません。プログラムを実行するたびに、コンピュータのファンが回転し始めることがあります。

于 2010-10-30T12:07:51.400 に答える
2

生産者/消費者パターンの穴の概念は、特定の基準が満たされた場合にのみ共有リソース (バッファー) にアクセスすることです。そして、それらが満たされていることを確認するために、不必要な CPU サイクルを使用しないようにします。

消費者：

  • 消費するものがない場合は待機します(=> 空のバッファー)。

プロデューサー：

  • バッファに十分なスペースがない場合は待機します。

そして、両方について注意することが非常に重要です：

  • 待って!=スピン待ち
于 2010-10-30T12:46:07.837 に答える
1

バッファのロックだけではありません。

最初のプログラムのfillCountセマフォは、消費するものがなくなったときに消費者を一時停止することです。これがないと、取得するものがあるかどうかを確認するためにバッファーを常にポーリングすることになりますが、これは非常に無駄です。

同様にemptyCount、バッファがいっぱいになると、セマフォはプロデューサを一時停止します。

于 2010-10-30T12:11:48.427 に答える
0

複数の消費者が関与している場合、飢餓の問題があります。後者の例では、消費者はループ内のアイテムをチェックします。しかし、彼が再試行するまでに、他の消費者が彼のアイテムを「盗む」可能性があります。そして次回も、また、また。それは良くありません。

于 2010-10-30T12:10:34.727 に答える