Zwei-Lock Concurrent Queue-Algorithmus Ausgabe

Question

So würde ich über den Artikel Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms von Maged M. Michael und Michael L. Scott, und es gibt ein kleines Problem, das ich nicht bekommen:

Nehmen wir an, wir haben zwei gleichzeitige Threads, die direkt nach der Initialisierung der Warteschlange ausgelöst werden. Einer der Threads ruft enqueue und die anderen Aufrufe dequeue. Was verhindert, dass sie gleichzeitig auf das Feld next des Dummy-Knotens zugreifen? kann der dequeue Thread das next Feld nicht lesen, während der enqueue Thread dazu schreibt? Sie benutzen beide verschiedene Schlösser ... also verstehe ich nicht, was zwischen ihnen synchronisiert ..

Danke.

Answer 1

enqueue() manipuliert nur das Endstück, und dequeue() manipuliert nur den Kopf, so dass sie nicht die gleichen Sperren verwenden müssen. Es gibt einen speziellen Fall, wenn Kopf und Endknoten auf denselben Knoten verweisen, den "Dummy" -Knoten, der beim Initialisieren erstellt wurde. Und Sie haben Recht, dass enqueue() den nächsten Zeiger des Knotens schreiben könnte, während dequeue() versucht, es zu lesen.

Es gibt kein Problem mit diesem gleichzeitig Lesen und Schreiben. Beachten Sie, dass enqueue() einen neuen Knoten erstellt und das Objekt vollständig initialisiert, bevor es sichtbar gemacht wird, indem Sie es in tail-> next schreiben. Daher kann kein anderer Code jemals diesen neuen Knoten in einem halb initialisierten Zustand sehen. Darüber hinaus sind Lese-/Schreibvorgänge in einem Zeiger atomar, sodass es nicht möglich ist, dequeue() etwa zur Hälfte des Zeigers zu erhalten.

Also in Ihrem Szenario, in dem enqueue() und dequeue() rechts beide weg genannt werden, gibt es zwei Möglichkeiten:

• enqueue() schreibt> neben Schwanz- vor dequeue() liest aus Kopf- > weiter. In diesem Fall wird dequeue() den Knoten sehen, der in die Warteschlange gestellt wurde und ihn zurückgeben wird.
• dequeue() liest aus head-> next vor enqueue() schreibt in tail-> next. In diesem Fall denkt dequeue(), dass die Warteschlange leer ist und gibt false zurück.