Kann mein Algorithmus bei Verwendung von Sperren weiterhin sperrenfrei sein?

Eine übliche Definition von "sperrenfrei" ist, dass mindestens ein Prozess Fortschritte macht. ¹

Wenn ich eine einfache Datenstruktur wie eine Warteschlange habe, die durch eine Sperre geschützt ist, kann ein Prozess immer Fortschritte erzielen, da ein Prozess die Sperre erwerben, tun kann, was er will, und sie freigeben kann.

Entspricht es also der Definition von sperrenfrei?

¹ Siehe z. B. M. Herlihy, V. Luchangco und M. Moir. Hindernisfreie Synchronisation: Double-Ended-Warteschlangen als Beispiel. In Distributed Computing, 2003. "Es ist sperrenfrei, wenn nur sichergestellt wird, dass ein Thread immer Fortschritte macht."

Das ist keine Definition für sperrenfrei.

Wenn Sie den Fortschritt garantieren können, haben Sie Deadlock-frei , und wenn Sie die endgültige Fertigstellung jeder Anfrage haben, haben Sie Hunger-frei , aber nicht Lock-frei.

Ich frage mich, ob Ihr einfaches Beispiel dies tatsächlich tatsächlich liefert. Sie benötigen Sperrhierarchien usw., um tatsächlich Fortschrittsgarantien zu geben, wenn mehrere Sperren beteiligt sind.

Ich habe The Art of Multiprocessor Programming ^{1 studiert} und ihr Text ist nicht klar genug, genau wie das Buch, auf das Sie sich beziehen. Hier sind einige Zitate von TAMPP:

Zitat 1 (Definition von sperrenfrei)

Eine Methode ist sperrfrei, wenn sie garantiert, dass ein Methodenaufruf unendlich oft in einer endlichen Anzahl von Schritten beendet wird.

Zitat 2 (Definition von Nonblocking)

Ein ausstehender Aufruf einer Gesamtmethode ist niemals erforderlich, um auf den Abschluss eines weiteren ausstehenden Aufrufs zu warten.

Zitat 3 (behaupten, dass sperrenfrei nicht blockiert)

Die wartungsfreien und sperrfreien nicht blockierenden Fortschrittsbedingungen garantieren, dass die Berechnung insgesamt Fortschritte macht, unabhängig davon, wie das System Threads plant.

Das Problem ist, dass der Anspruch in Zitat 3 nicht offensichtlich aus der Definition in Zitat 1 folgt. Wie bereits erwähnt, scheint eine synchronisierte Warteschlange Zitat 1 zu erfüllen: Unendlich oft wird eine Methode die Sperre erfolgreich erlangen und vervollständigen.

Beachten Sie insbesondere den recht vagen Satz in Zitat 3: "Unabhängig davon, wie das System Threads plant". Dem geht keine formale Beschreibung des "Thread-Scheduling-Systems" voraus, daher müssen wir seine Eigenschaften auf der Grundlage unserer Vorurteile darüber rekonstruieren, was die Definitionen bedeuten sollten :

1. führt das System immer Anweisungen gewissen Gewinde;
2. Es darf niemals Anweisungen eines bestimmten Threads ausführen .
3. Alle Threads rufen die betreffende Methode auf.

Auf einem solchen System kann eine Blockierungsmethode nicht sperrenfrei sein: Wenn der Thread, der die Sperre hält, nie wieder zur Ausführung eingeplant wird, gibt es keinen anderen Thread, der seinen Methodenaufruf in einer endlichen Anzahl von Schritten abschließen kann Einige Threads, die Schritte der Methode ausführen. Für ein realistischeres System, das garantiert, dass jedem Thread irgendwann CPU-Zeit eingeräumt wird, muss die Definition explizit die nicht blockierende Eigenschaft enthalten:

Die Definition von sperrenfrei wurde korrigiert

Eine Methode ist sperrenfrei, wenn sie nicht blockiert ist, und garantiert außerdem, dass ein Methodenaufruf unendlich oft in einer endlichen Anzahl von Schritten beendet wird.

¹ Maurice Herlihy, Nir Shavit, Die Kunst der Multiprozessor-Programmierung, Elsevier 2008, S. 58-60

Die Terminologie ist nicht immer konsistent, aber ich denke, es ist wichtig, die folgenden Fragen zu einem vorgeschlagenen Algorithmus oder System zu stellen:

1. Gibt es eine Abfolge von Ereignissen, bei denen Threads stecken bleiben und aufeinander warten könnten, selbst wenn allen Threads die gesamte CPU-Zeit eingeräumt würde, die sie verwenden könnten [wenn ja, ist es nicht Deadlock-frei]
2. Wenn ein Thread für eine beliebig lange Zeit blockiert wurde, könnte dies andere Threads blockieren oder den Systembetrieb für eine beliebig lange Zeit beeinträchtigen [wenn ja, ist er nicht nicht blockierend].
3. Gibt es eine zumindest theoretisch mögliche Kombination der Thread-Planung, die dazu führen könnte, dass alle Threads wiederholt dieselben Vorgänge wiederholen, während die Arbeit der anderen ungültig wird, ohne dass jemand Fortschritte macht [wenn ja, ist es nicht sperrenfrei]
4. Wenn einigen Threads im Verhältnis zu anderen Threads ausreichend CPU-Zeit zugewiesen wird, können sie den letzteren Thread dazu zwingen, seine Operationen auf unbestimmte Zeit zu wiederholen [wenn ja, ist es nicht wartungsfrei].

Ein großer Teil der Bedeutung von sperrfreien Algorithmen liegt nicht darin, dass sie schneller sind als nicht sperrfreie Algorithmen, sondern vielmehr darin, dass sie nicht zum Absterben neigen, wenn ein Thread überlagert wird [beachten Sie, dass eine solche Garantie lediglich erforderlich ist dass Algorithmen nicht blockierend sind, aber alle sperrfreien Algorithmen sind]. Es ist möglich, dass ein sperrfreier Algorithmus Sperren verwendet, jedoch nur, wenn Sperrenerfassungsversuche Zeitüberschreitungen zusammen mit Algorithmen enthalten, um sicherzustellen, dass immer jemand Fortschritte erzielen kann (z. B. könnte ein Algorithmus eine CompareExchangeSchleife als primäre verwenden Arbitrierungsmethode, aber verwenden Sie Sperren, um den Zugriff zu vermitteln, wenn der Konflikt hoch zu sein scheint. Wenn eine Sperre übermäßig lange gehalten zu werden scheint, könnten andere Threads entscheiden, die Bemühungen zur Verwendung dieser Sperre abzubrechen und stattdessen eine neue zu erstellen.CompareExchangeWenn Kunden das Schloss verlassen, würde dies die Systemkonsistenz nicht gefährden. Dies kann jedoch bedeuten, dass Code, der das alte Schloss gehalten hat, erst dann ausgeführt wird, wenn auch das alte Schloss verlassen wird und sich für das neue Schloss anstellt.

Sie müssen sich die "Definition" ansehen, die Sie im Kontext zitieren :

Die traditionelle Methode zum Implementieren gemeinsam genutzter Datenstrukturen besteht darin, gegenseitigen Ausschluss (Sperren) zu verwenden, um sicherzustellen, dass sich gleichzeitige Vorgänge nicht gegenseitig stören. Das Sperren hat eine Reihe von Nachteilen in Bezug auf Softwareentwicklung, Fehlertoleranz und Skalierbarkeit (siehe [8]). Als Reaktion darauf haben Forscher eine Vielzahl alternativer Synchronisationstechniken untersucht, bei denen kein gegenseitiger Ausschluss angewendet wird . Eine Synchronisationstechnik ist wartungsfrei, wenn sichergestellt wird, dass jeder Thread trotz willkürlicher Verzögerung (oder sogar Ausfall) anderer Threads weiterhin Fortschritte erzielt. Es ist sperrfrei, wenn nur sichergestellt wird, dass ein Thread immer Fortschritte macht.

Sie verwenden Sperren zum gegenseitigen Ausschluss, daher handelt es sich nicht um eine sperrenfreie Technik, über die sie sprechen.

Kann mein Algorithmus bei Verwendung von Sperren weiterhin sperrenfrei sein?

Es könnte sein, aber es hängt vom Algorithmus ab.

Wenn ich eine einfache Datenstruktur wie eine Warteschlange habe, die durch eine Sperre geschützt ist, kann ein Prozess immer Fortschritte erzielen, da ein Prozess die Sperre erwerben, tun kann, was er will, und sie freigeben kann.

Entspricht es also der Definition von sperrenfrei?

Hinweis an sich .

Wenn der Schritt "Tun, was er will" keine anderen Sperren umfasst und garantiert in einer begrenzten Zeit abgeschlossen ist, ist dieser bestimmte Teil Ihres Algorithmus frei von Deadlocks.

Wenn diese Voraussetzungen jedoch nicht erfüllt sind, besteht zumindest die Möglichkeit von Deadlocks ...

Das von Ihnen angegebene Beispiel ist aus folgendem Grund nicht sperrenfrei.

Die Unterstützung eines Threads erwirbt die Sperre, und der OS-Scheduler hat den Thread für einen unendlichen Einzelzeitraum angehalten. Dann kann der gesamte Thread keine Fortschritte erzielen, da kein Benutzer die Sperre erwerben kann, die vom angehaltenen Thread erworben wurde.

Im Allgemeinen sind Algorithmen, die Sperren verwenden, nicht sperrenfrei.

Beachten Sie, dass Deadlock-frei und Lock-frei zwei verschiedene Konzepte sind. Deadlock-frei bedeutet, dass es keine Möglichkeit für Deadlocks gibt, aber es könnte Livelocks geben, die verhindern können, dass das gesamte System Fortschritte macht. Die Sperrfreiheit ist stärker als diese, da einige Threads im System immer mit einer begrenzten Anzahl von Schritten Fortschritte machen.