Non-Blocking-Algorithmus und die gegenseitigen Ausschluß

Question

Wikipedia sagt, dass:

Non-Blocking-Algorithmus sorgt dafür, dass Threads für eine gemeinsame Ressource im Wettbewerb nicht über ihre Hinrichtung auf unbestimmte Zeit im gegenseitigen Ausschluß verschoben.

Wie kann man sicherstellen, dass dies erreicht wird, wenn mehrere Threads auf einen kritischen Bereich zugreifen müssen?

Answer 1

den Aufsatz Bitte entschuldigen Sie, aber das dazu neigt, mein Schreibstil zu sein.

Nicht blockierende Algorithmen haben eine Vielzahl von Formen, aber die Grundidee besteht darin, den Algorithmus so zu strukturieren, dass Sie in einer mehr oder weniger deterministischen Anzahl von Schritten enden, statt unbegrenzt durch eine Sperre gestoppt zu werden. Wenn Sie eine Operation haben, die möglicherweise zeitaufwendig sein kann, ist es manchmal das Beste, was Sie tun können, um sicherzustellen, dass Ihre Threads andere Aufgaben haben, um die gesamte Operation des Programms voranzutreiben.

Nicht alle Algorithmen sind für nicht blockierende Methoden geeignet, und viele nicht blockierende Methoden enthalten kleine kritische Abschnitte und sind daher streng genommen nicht blockierend, verhalten sich aber in der Praxis so. Verwenden Sie Ihren Kopf bei der Implementierung von Nebenläufigkeiten jeglicher Art, da es sich um einen Debugger handelt, unabhängig davon, ob Sie ein erfahrener Programmierer sind oder nicht.

- = Non Blocking Algorithmen = -

Atomic Algorithmen ausführen Updates, die in einem einzigen Schritt erfolgen, die nicht unterbrochen werden kann. Ein einfaches Beispiel ist das Inkrementieren eines Wertes mit ++ oder + =, was bei der Aktualisierung buchstäblich auf einen einzelnen CPU-Befehl hinausläuft und somit ohne die Möglichkeit der Unterbrechung abgeschlossen wird, und die CPU wird es reparieren, wenn die Multi-Verarbeitung das bricht aktualisieren. Ich bin mir nicht ganz sicher, wie weit dies in SIMD-Anweisungen hineinreicht, wo ein CPU-Befehl mehrere Datenstücke berührt.

Wenn Sie über einen Algorithmus verfügen, für den Sie keinen Rückgabewert benötigen, können Sie möglicherweise ein Producer/Consumer-Queue-System verwenden, bei dem nur die Warteschlange sperrbasiert ist oder atomare Updates zum Einfügen von Elementen in die Warteschlange verwendet werden Warteschlange. In beiden Fällen wird die Warteschlange schnell aktualisiert, und die Steuerung wird an den Aufrufer zurückgegeben, während ein Consumer-Thread den Rückstand verarbeitet. Netzwerk- und Festplattenschreibvorgänge sind typischerweise von dieser Art.

Wenn Sie einen Rückgabewert benötigen, kann ein Callback Ihren Thread benachrichtigen, wenn der Vorgang abgeschlossen ist, oder einige neue Daten können von Ihnen verarbeitet werden. Im Optimalfall haben Sie andere Dinge zu tun, als einfach auf den Rückruf zu warten.

CAS-Algorithmen, bei denen das Lesen und Aktualisieren auf einem System "Erste bis Vervollständigung" sichergestellt ist, ist ein weiterer Weg, um den Fortschritt zu sichern, aber der Abbruch kostet Zeit und kann daher zu einer nichtdeterministischen Fertigstellungszeit führen wenn es zu einem Abbruch kommt. Datenbanken verwenden eine Art von CAS für die Transaktionsvervollständigung, die als optimistisches Sperren bezeichnet wird. Dies funktioniert am besten, wenn die Konkurrenzsituation niedrig ist oder wenn die Konkurrenz den Benutzer benachrichtigen und zusätzliche Eingaben sammeln müsste.

- = Blocking Algorithms = -

Blocking Algorithmen Blöcke vorwärts Fortschritt aller sondern eine einzige oder eine kleine Vielzahl von Gewinde (s) auf eine gemeinsam genutzte Ressource zu arbeiten versucht.Wenn die Operation langwierig ist, kann dies zu erheblichen Verzögerungen führen, so dass das Ziel bei jedem Blocking-Algorithmus darin bestehen sollte, den kritischen Abschnitt, in dem Konflikte auftreten, auf einen Bruchteil des gesamten Algorithmus zu reduzieren. Datenbanktransaktionen, die dies tun, verwenden Pessimistic Locking.

- = Deadlocks und Live-Sperren = -

Deadlocks sind, wo zwei Themen von einander jeweils blockiert sind, in der Regel, weil jeder ist eine Sperre der andere will halten.

Live-Sperren können auftreten, wenn zwei Threads wieder Zugriff auf Ressourcen der anderen Steuerelemente wünschen oder wenn zwei Threads vollständig von den Daten verbraucht werden, die sie sich senden. In beiden Fällen versucht der Algorithmus weiter vorwärts zu gehen, ohne zu warten, aber die zwei (oder möglicherweise mehr) Threads drehen sich weiter, ohne einen echten Vorwärtsfortschritt zu machen.

- = Bedeutung = -

Warum ist jeder das wichtig? Das Hauptproblem mit Nebenläufigkeit jeglicher Art ist die Möglichkeit eines unvorhersehbaren Zustands, da zwei Threads ohne Rücksicht auf die Änderungen des jeweils anderen auf denselben Daten arbeiten. Um dies zu verhindern, werden blockierende und nicht blockierende Algorithmen verwendet. Wenn sie jedoch falsch verstanden werden, kann dies zu Deadlocks, Live-Locks oder Datenverfälschungen führen.

Ich hoffe, dies betont, dass Nebenläufigkeit Probleme mit BEIDEN blockierenden und nicht-blockierenden Algorithmen vorhanden sind, und dass unabhängig von Ihrer gewählten Methode der Bekämpfung der Nebenläufigkeit, müssen Sie genau darauf achten, wie Ihr Programm strukturiert zu verwenden ist, oder Bereitstellen von freigegebenen Ressourcen

Answer 2

Non-Blocking-Algorithmen nutzen CAS: Java Concurrency: CAS vs Locking