如何使循環隊列完全線程安全

Question

在剛剛添加的同步到大多數方法的時刻，因爲看起來沒有它，這些方法不是線程安全的。還有什麼我需要實現以確保它是線程安全的。

此外，有沒有更好的方式去做這件事。當時只有一個線程可以同時使用循環隊列，這似乎有點低效。

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()方法 - 簡短而甜蜜。

即便如此，仍然存在線程安全問題，您的類的方法的同步本身無法抵禦。其中一些涉及多個方法調用的對象的一致性。例如，假設一個線程在隊列的一個實例上排隊一個對象。如果這個隊列是在線程中共享的，那麼排隊該對象的隊列就不能安全地假定它可以稍後退出一個對象，或者如果它退出隊列，那麼它將與它排隊的一樣。如果它想要做出這樣的假設，那麼它必須提供更廣泛的範圍保護，或者確保它使用的隊列實例不共享。

其他問題圍繞入列對象的變化，如果它們確實是可變的。它們的狀態不受隊列及其迭代器的同步保護。