如何使循环队列完全线程安全

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

即便如此，仍然存在线程安全问题，您的类的方法的同步本身无法抵御。其中一些涉及多个方法调用的对象的一致性。例如，假设一个线程在队列的一个实例上排队一个对象。如果这个队列是在线程中共享的，那么排队该对象的队列就不能安全地假定它可以稍后退出一个对象，或者如果它退出队列，那么它将与它排队的一样。如果它想要做出这样的假设，那么它必须提供更广泛的范围保护，或者确保它使用的队列实例不共享。

其他问题围绕入列对象的变化，如果它们确实是可变的。它们的状态不受队列及其迭代器的同步保护。