4

Java Concurrency in Practice ブックの次の部分がわかりません。

1 つのスレッドしか進行できない場合に notifyAll を使用するのは非効率的です。10 個のスレッドが条件キューで待機している場合、notifyAll を呼び出すと、各スレッドが起動し、ロックを求めて競合します。その後、それらのほとんどまたはすべてがすぐに眠りに戻ります。これは、(おそらく) 単一のスレッドが進行できるようにするイベントごとに、多くのコンテキスト スイッチと多くの競合するロック取得を意味します。(最悪の場合、notifyAll を使用すると、n で十分なO(n 2 ) ウェイクアップが発生します。)

サンプル コードはリスト 14.6 にあります。

@ThreadSafe
public class BoundedBuffer<V> extends BaseBoundedBuffer<V> {
    // CONDITION PREDICATE: not-full (!isFull())
    // CONDITION PREDICATE: not-empty (!isEmpty())

    public BoundedBuffer(int size) { super(size); }

    // BLOCKS-UNTIL: not-full
    public  synchronized void put(V v) throws InterruptedException {
        while (isFull())
            wait();
        doPut(v);
        notifyAll();
    }

    // BLOCKS-UNTIL: not-empty
    public  synchronized V take() throws InterruptedException {
        while (isEmpty())
            wait();
        V v = doTake();
        notifyAll();
        return v;
    }
}

たとえば、次の一連のイベントを使用できます。

  1. 2 つのコンシューマ スレッドがバッファからオブジェクトを取得しようとすると、バッファが空になるため中断されます。
  2. 10 個のプロデューサが 10 個のオブジェクトをバッファに入れると、バッファ容量は 10 になります。
  3. 100001 個のプロデューサーが 100001 個のオブジェクトをバッファーに入れようとしましたが、バッファーがいっぱいになり、中断されました。
  4. 最初のコンシューマはバッファからオブジェクトを取得し、notifyAll を呼び出します。
  5. プロデューサーがオブジェクトをバッファーに入れ、notifyAll を呼び出すと、バッファーがいっぱいになります。

これで、1 つのスレッド (コンシューマ スレッド) だけが処理を進めることができます。また、100000 人の生産者がいて、進歩できません。

進行可能なスレッドが起動される前に、最悪の場合に O(n 2 ) の起動が発生する理由がわかりません。

最悪の場合は次のシーケンスだと思います

  1. すべてのスレッドが起動されます (notifyAll のため)。O(n) ウェイクアップを「使用」しました。
  2. プロデューサー スレッドがロックを取得し、他のスレッドは中断されます。プロデューサー スレッドは処理を進めることができないため、一時停止され、ロックが解放されます。
  3. 現在、別のメカニズムが使用されているため、 1 つのプロデューサー スレッドのみが起動されます (スレッドはロックを取得するため、実行を再開しますが、今回は notifyAll は呼び出されません)。O(1) ウェイクアップのみを「使用」します。
  4. 2 番目のプロデューサーは進行できないため、一時停止され、ロックが解除されます。
  5. 他のすべての待機中のプロデューサーに対しても同様のイベントが発生します。
  6. 最後に、進行可能なスレッド (コンシューマ スレッド) が起動されます。

O(n) + O(n)*O(1) = O(n) ウェイクアップを「使用」したと思います。

本に誤りがありますか、それともここに何か欠けていますか?

4

2 に答える 2

3

何かが n 回キューに入れられます。「n 回のウェイクアップで十分」とは、理想的には、プロデューサーがバッファーに何かをドロップしたときに 1 つのコンシューマーに通知することを意味します。たとえば、n 回の通知があり、すべてが競合しないようにすることをお勧めします。しかし、代わりに、すべてのプロデューサー (マイナス 1、プットを行っているスレッド) とすべてのコンシューマー (とにかく待機しているもの) を含む、ロックを待機しているすべてのスレッドが、何かがキューにドロップされるたびに通知を受け取ります。すべてがロックのために戦い、スケジューラーが勝者を選びます。(そして、選択されたスレッドが待機しなければならない場合についても考慮していません。それは単なる詳細です。)したがって、各 put に対して 1 回、notifyAll が n 回呼び出され、各 notifyAll が複数のプロデューサーと複数のコンシューマーを起動します。ここで O(n2 ) ウェイクアップ。

于 2013-04-06T16:35:53.293 に答える