3

私は次のように非常に単純な同期Circular Queueを実装しています。私の友人は、それはdeadlock! しかし、私はそうは思いません。

実際には、キューが空の場合にスレッドがデキュー (ポーリング) する場合、別のスレッドが要素をエンキュー (提供) するまで待機する必要があり、キューがいっぱいの場合はその逆になります。

私はデッドロックが発生しやすいコードを見つけるのが苦手ですが、デッドロックも発生しやすいと思いますか? 

import java.util.ArrayList;

class CircularQueue<T>{
    ArrayList<T> q;
    int front , rear , size;
    public CircularQueue(int size){
        q = new ArrayList<T>();
        for (int i = 0 ; i < size ; i++)
            q.add(null);
        front =  0;
        rear =0;
        this.size = size;
     }
     public void offer(T t) throws InterruptedException{
        synchronized(this){
            if ( (rear + 1) % size == front)
                this.wait();    
        }
        rear = (rear + 1) % size;
        q.set(rear, t);
        this.notify();
     }
     public T poll() throws InterruptedException{
        synchronized(this){
            if (rear == front)
                this.wait();
        }
        front = (front+1) % size;
        T result = q.get(front);
        this.notify();
        return result;
     }
}
4

2 に答える 2

1

実装にはいくつかの問題があります。

  • の呼び出しはブロックnotify()内から来なければならないsynchronized
  • 実装により、オブジェクトが必要以上に長く収集されない場合に、一種の Java メモリ リークである「リンガラー」が作成されます。これを修正するには、元の要素を に設定しpoll()ますnull。
  • sを使用ArrayList<T>して埋める必要はありません。nullの単純な配列でObject十分です。キャストを追加する必要がありますが、 の有無にかかわらずとにかく存在するArrayListため、コードに移動することもできます。
  • で同期しないでくださいthis。

この最後のポイントにより、キューの悪意のあるユーザーは、ロックを解放せずにキュー オブジェクト自体を同期することで、進行を永続的に停止させることができます。

于 2013-06-21T16:37:00.090 に答える
0

wait() 呼び出しだけでなく、メソッド全体を同期する必要があります。

スロットが 2 つ残っているときに、2 つのスレッドが同時に offer() を試みた場合にどうなるか想像してみてください。どちらも同期ブロックを通過し、次の行でリアの異なる値を読み取ることができます。その後、 poll() への次の呼び出しはブロックされますが、値は既にそこにあります。

このコードには他にもいくつかの問題があります。誤ったウェイクアップを処理せず、モニターを保持せずに外部で notify() を呼び出します。また、ここでは ArrayList の代わりに Object[] を使用します。これは、固定サイズの可変コレクションがまさに必要なものだからです。

于 2013-06-21T16:35:55.567 に答える