Как сделать круговую очередь полностью поточно-ориентированной

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() Если метод синхронизирован, ваш итератор недостаточно изолирован от очереди хоста. Проблема не в том, что его методы синхронизируются на экземплярах итераторов, хотя это правда. Ваш итератор делает копии данных очереди хоста, чтобы выполнить итерацию снимка очереди. Это хорошая идея, и в этом случае синхронизация на самом итераторе - правильная вещь.

Но вы не реализуете это полностью. В частности, для конструктора недостаточно выполнения d = dd;, Массивы являются объектами, поэтому просто задает ссылку на массив итератора для ссылки на тот же объект массива, который использует очередь хоста. Вместо этого вам нужно сделать копию этого массива. Есть несколько способов сделать это, но я бы предпочел вызвать массив clone() Метод - короткий и сладкий.

Даже в этом случае существуют проблемы безопасности потоков, от которых не может защитить синхронизация методов ваших классов. Некоторые из них включают согласованность объекта с несколькими вызовами методов. Например, предположим, что один поток помещает объект в очередь в вашей очереди. Если эта очередь является общей для потоков, то та, которая поставила объект в очередь, не может с уверенностью предположить, что он может удалить объект из очереди позже или, если он удалит его из очереди, то это будет тот же объект, который был помещен в очередь. Если он хочет иметь возможность делать такие предположения, он должен либо обеспечить более широкую защиту, либо гарантировать, что используемый им экземпляр очереди не будет использоваться совместно.

Другие проблемы вращаются вокруг мутации объектов в очереди, если они действительно изменчивы. Их состояние не защищено синхронизацией очереди и ее итератора.

Answer 2

empty() не синхронизируется, синхронизированные по методам итератора защищают итератор (что, вероятно, бесполезно), но не саму очередь.