Wie man eine zirkuläre Warteschlange vollständig threadsicher macht

Question

In der Minute habe ich gerade synchronisiert, um die Mehrheit der Methoden, wie es scheint, dass ohne diese Methoden mit Thread nicht sicher sein. Gibt es noch etwas, das ich implementieren muss, um sicherzustellen, dass es threadsicher ist?

Gibt es auch einen besseren Weg, dies zu tun. Im Moment wird nur ein Thread in der Lage sein, die zyklische Warteschlange auf einmal zu verwenden, dies scheint ein wenig ineffizient zu sein.

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(){} 
    } 
} 

Jeder Rat oder Hilfe, die Sie geben können, würde geschätzt werden!

Answer 1

empty() ist nicht synchronisiert, die synchronisiert auf die Methoden des Iterators schützen den Iterator (was wahrscheinlich nutzlos ist), aber nicht die Warteschlange selbst.

Answer 2

Zusätzlich dazu, dass Ihre Methode empty() nicht synchronisiert wurde, ist Ihr Iterator nicht ausreichend von der Hostwarteschlange isoliert. Das Problem ist nicht, dass seine Methoden auf Iterator-Instanzen synchronisiert werden, obwohl es wahr ist, dass sie es sind. Ihr Iterator erstellt Kopien der Daten der Hostwarteschlange, um über einen Snapshot der Warteschlange zu iterieren. Das ist eine gute Idee, und in diesem Fall ist die Synchronisierung auf dem Iterator selbst das Richtige.

Aber Sie implementieren es nicht vollständig. Insbesondere reicht es nicht aus, dass der Konstruktor d = dd; ausführt. Arrays sind Objekte, so dass nur die Array-Referenz des Iterators auf dasselbe Array-Objekt verweist, das die Host-Warteschlange verwendet. Stattdessen müssen Sie eine Kopie dieses Arrays erstellen. Es gibt mehrere Möglichkeiten, dies zu tun, aber ich würde lieber die Methode clone() des Arrays aufrufen - kurz und bündig.

Auch dann gibt es Probleme mit der Threadsicherheit, gegen die sich die Synchronisierung der Methoden Ihrer Klassen nicht schützen kann. Einige davon betreffen die Konsistenz des Objekts über mehrere Methodenaufrufe hinweg. Angenommen, ein Thread reiht ein Objekt in eine Instanz Ihrer Warteschlange ein. Wenn diese Warteschlange unter Threads gemeinsam genutzt wird, kann die Person, die das Objekt in die Warteschlange eingereiht hat, nicht sicher davon ausgehen, dass sie ein Objekt später aus der Warteschlange entfernen kann oder es aus der Warteschlange entfernt wird. Wenn es in der Lage sein möchte, solche Annahmen zu treffen, muss es entweder einen umfassenderen Schutzumfang bereitstellen oder sicherstellen, dass die von ihm verwendete Warteschlangeninstanz nicht geteilt wird.

Andere Probleme drehen sich um die Mutation der eingereihten Objekte, wenn sie tatsächlich veränderbar sind. Ihr Zustand ist nicht durch Synchronisation der Warteschlange und ihres Iterators geschützt.