[FIXED] Gleichzeitig sichere Warteschlange in Java

Ausgabe

Ich versuche, eine Thread-sichere Warteschlange mit eindeutigen Elementen zu erstellen. Ich sehe keine Schwachstellen, bin mir aber nicht sicher, ob dieser Realisierungsthread sicher ist oder nicht? Die Methoden get(), add(), toArray() erledigen alles unter Sperren, toString() und equals() verwenden toArray(), um eine Kopie des Hauptarrays zu erhalten und unabhängig mit der Kopie ohne Sperren zu arbeiten.

public class SafeQueue<T> {
        private final Object[] queue;
        private final HashSet<T> content;
        private final Lock lock;
        private int size;
        
        public SafeQueue() {
            queue = new Object[100];
            content = new HashSet<>(100);
            lock = new ReentrantLock();
        }

        public boolean add(T el) {
            Objects.requireNonNull(el);
            final Lock lock = this.lock;
            lock.lock();
            try {
               //some logic
            } finally {
                lock.unlock();
            }
            return true;
        }

        public T get() {
            final Lock lock = this.lock;
            lock.lock();
            try {
                T el = (T) queue[0];
                if (el != null) {
                    //some shift logic
                    content.remove(el);
                }
                return el;
            } finally {
                lock.unlock();
            }
        }

        public Object[] toArray() {
            final Lock lock = this.lock;
            lock.lock();
            try {
                return Arrays.copyOf(this.queue, size);
            } finally {
                lock.unlock();
            }
        }

        @Override
        public boolean equals(Object o) {
            Object[] eqQueue = ((SafeQueue<?>) o).toArray();
            Object[] curQueue = toArray();

            //some comparison logic with eqQueue and curQueue
            return equal;
        }

        @Override
        public String toString() {
            Object[] curQueue = toArray();
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            //some logic with curQueue
            return sb.toString();
        }
    }

Lösung

Vielleicht möchten Sie fragen, was es bedeutet, dass die equalsMethode Thread-sicher ist? Bedenken Sie:

SafeQueue<T> qa = ...;
SafeQueue<T> qb = ...;
...
if (qa.equals(qb)) {
    handleEqualsCase();
}

Wenn Sie sich über die Thread-Sicherheit der equals()Methode Sorgen machen sollten, könnte dies nur daran liegen, dass andere Threads möglicherweise beide Warteschlangen beim Aufrufen ändern könnten equals().

Aber zum Zeitpunkt des handleEqualsCase()Aufrufs könnten diese anderen Threads noch laufen, und jetzt ist weder qanoch noch qbgesperrt. Es gibt keine Garantie dafür, dass die beiden Warteschlangen immer noch gleich sind, wenn handleEqualsCase()aufgerufen wird. Aber wenn sie nicht gleich sind, muss das eine schlechte Sache sein, oder? Warum hätten Sie sich sonst überhaupt die Mühe gemacht, auf Gleichheit zu testen?

Hier ist eine Möglichkeit, dieses Problem zu umgehen. Anstatt eine traditionelle equals()Methode zu schreiben, schreiben Sie stattdessen so etwas:

private static
boolean unsynchronizedEqualityTest(SafeQueue<T> qa, SafeQueue<T> qb) {
    ...
}

public static
void doIfEqual(SafeQueue<T> qa, SafeQueue<T> qb, Runnable handler) {
    qa.lock.lock();
    qb.lock.lock();
    try {
        if (unsynchronizedEqualityTest(qa, qb)) {
            handler.run();
        }
    } finally {
        qb.lock.unlock();
        qa.lock.unlock();
    }
}

Wenn nun die vom Client bereitgestellte handleraufgerufen wird, ist garantiert, dass die beiden Warteschlangen immer noch gleich sind, da sie beide noch gesperrt sind.

Aber Vorsicht! Es besteht die Möglichkeit eines Deadlocks, wenn ein Thread aufruft doIfEqual(qa,qb,...)und ein anderer Thread aufruft doIfEqual(qb,qa,...). Ich überlasse es Ihnen, herauszufinden, wie Sie diesen Stillstand verhindern können.

Beantwortet von – Solomon Slow

Antwort geprüft von – David Goodson (FixError Volunteer)