Ist die Multi-Producer/Multi-Consumer Bounded Queue von liblfds wirklich sperrenfrei?

Analyse des sperrfreien Warteschlangenalgorithmus

Frage: Ist der Multi-Produzenten/Multi-Consumer-begrenzte Warteschlangenalgorithmus in liblfds lock-free?

Definition von Sperrenfrei:

Ein sperrenfreier Algorithmus stellt sicher, dass mindestens ein Thread unabhängig von gleichzeitigen Threads Fortschritte machen kann. Dies bedeutet, dass es keinen Code geben kann, bei dem ein Thread auf einen anderen Thread angewiesen ist, um fortzufahren, z. B. darauf, dass ein Flag zurückgesetzt oder deaktiviert wird.

Algorithmusanalyse:

Der Der Algorithmus reserviert einen Platz in der Warteschlange mithilfe einer CAS-Schleife, um den Schreibindex zu erhöhen. Anschließend werden die Benutzerdaten in den reservierten Steckplatz kopiert und die Sequenznummer aktualisiert. Diese Reservierung bedeutet jedoch, dass der POP-Vorgang davon abhängt, dass der PUSH-Thread die Aktualisierung der Sequenznummer abschließt.

Mangelnde Fortschrittsgarantie:

Gemäß der Definition von „Machen“. Fortschritt“ erfüllt der Algorithmus nicht die Kriterien der Sperrenfreiheit. Die Warteschlange kann als voll oder leer beobachtet werden, obwohl PUSH- oder POP-Vorgänge ausgeführt werden, wodurch andere Threads daran gehindert werden, diese Vorgänge auszuführen.

Teilweise blockierter Fortschritt:

Während der Der Algorithmus ermöglicht möglicherweise, dass POP-Vorgänge bis zum laufenden Element fortgesetzt werden. Dieser Fortschritt ist jedoch begrenzt. Wenn ein Thread während des kritischen Bereichs zwischen der Aktualisierung des Schreibindex und dem Schreiben der Sequenznummer kontextumgeschaltet wird, melden alle Verbraucherthreads eine leere Warteschlange.

Versteckter Mutex:

Die Kombination aus Schreibindex und Slot-Sequenznummern fungiert im Wesentlichen als Mutex pro Element. Sobald ein Thread den Schreibindex erfolgreich erhöht, werden alle nachfolgenden Threads daran gehindert, in die Warteschlange zu schreiben, bis der ursprüngliche Thread den Vorgang abschließt.

Leistungsvorteile:

Trotzdem nicht Da der Algorithmus strikt sperrenfrei ist, bietet er Leistungsvorteile in Bezug auf:

• Unumstrittene Leistung: Der Fast-Path besteht aus einem einzigen CompareAndSwap-Vorgang.
• Konkurrierende Leistung: Die Schreibindexvariable ist umstritten, aber das Verhalten ist bei einer gut optimierten CAS-Implementierung angemessen.

Schlussfolgerung:

Während der Algorithmus einige nützliche Leistungseigenschaften bietet, fehlt ihm aufgrund des Reservierungssystems und der Abhängigkeit zwischen ihm die Schlüsselkorrektheitseigenschaft des sperrfreien Betriebs PUSH- und POP-Operationen.

Das obige ist der detaillierte Inhalt vonIst die Multi-Producer/Multi-Consumer Bounded Queue von liblfds wirklich sperrenfrei?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!