循環キューを完全にスレッドセーフにする方法

Question

分の時に、スレッドセーフではないこれらのメソッドが表示されるので、大部分のメソッドに同期を追加しました。スレッドセーフであることを保証するために実装する必要があるものはありますか？

また、これについては、より良い方法がありますか？分では、1つのスレッドだけが循環キューを一度に使用することができますが、これは少し非効率的です。

class CircularQueue<T> implements Iterable<T>{ 
    private T queue[]; 
    private int head, tail, size; 
    @SuppressWarnings("unchecked") 
    public CircularQueue(){ 
    queue = (T[])new Object[20]; 
    head = 0; tail = 0; size = 0; 
    } 
    @SuppressWarnings("unchecked") 
    public CircularQueue(int n){ //assume n >=0 
    queue = (T[])new Object[n]; 
    size = 0; head = 0; tail = 0; 
    } 
    public synchronized boolean join(T x){ 
    if(size < queue.length){ 
     queue[tail] = x; 
     tail = (tail+1)%queue.length; 
     size++; 
     return true; 
    } 
    else return false; 
    } 
    public synchronized T top(){ 
    if(size > 0) 
     return queue[head]; 
    else 
     return null; 
    } 
    public synchronized boolean leave(){ 
    if(size == 0) return false; 
    else{ 
     head = (head+1)%queue.length; 
     size--; 
     return true; 
    } 
    } 
    public synchronized boolean full(){return (size == queue.length);} 
    public boolean empty(){return (size == 0);} 

    public Iterator<T> iterator(){ 
     return new QIterator<T>(queue, head, size); 
    } 
    private static class QIterator<T> implements Iterator<T>{ 
     private T[] d; private int index; 
    private int size; private int returned = 0; 
     QIterator(T[] dd, int head, int s){ 
      d = dd; index = head; size = s; 
     } 
    public synchronized boolean hasNext(){ return returned < size;} 
    public synchronized T next(){ 
     if(returned == size) throw new NoSuchElementException(); 
     T item = (T)d[index]; 
     index = (index+1) % d.length; 
     returned++; 
     return item; 
    } 
    public void remove(){} 
    } 
} 

ご迷惑をおかけして申し訳ございませんが、ご了承ください。

Answer 1

empty（）は同期されていません。イテレータのメソッドで同期されると、イテレータ（おそらく役に立たない）は保護されますが、キュー自体は保護されません。

Answer 2

empty()メソッドを同期させていないことに加えて、イテレータがホストキューから十分に絶縁されていません。問題はイテレータのインスタンスでメソッドが同期されているということではありませんが、実際にはそうです。イテレータは、ホストキューのデータのコピーを作成して、キューのスナップショットを反復処理します。これは良いアイデアです。その場合、イテレータ自体の同期は正しいことです。

しかし、あなたは完全に実装していません。具体的には、コンストラクタがd = dd;を実行するのに十分ではありません。配列はオブジェクトなので、イテレータの配列参照はホストキューが使用するものと同じ配列オブジェクトを参照するように設定されます。代わりに、その配列のコピーを作成する必要があります。これを行うにはいくつかの方法がありますが、配列のclone()メソッドを短くて甘く呼び出す方が好きです。

でも、クラスのメソッドの同期だけでは防御できないスレッドの安全性の問題があります。これらのうちのいくつかは、複数のメソッド呼び出しに対するオブジェクトの一貫性を伴います。たとえば、あるスレッドがキューのインスタンスにオブジェクトをエンキューするとします。そのキューがスレッド間で共有されている場合、オブジェクトをエンキューしたキューは、後でオブジェクトをデキューできますか、デキューするかどうかは安全に想定できません。このような前提を設定できるようにするには、より広範囲の保護を提供するか、または使用するキューインスタンスが共有されないようにする必要があります。

他の問題は、エンキューされたオブジェクトの変異が、実際には変更可能であるかどうかによって決まります。それらの状態は、キューとイテレータの同期によって保護されません。