Was ist das Reentry Lock und Konzept im Allgemeinen?

Ich werde immer verwirrt. Würde jemand erklären, was Reentrant in verschiedenen Kontexten bedeutet? Und warum sollten Sie Reentrant vs. Nicht-Reentrant verwenden?

Say pthread (posix) Sperrgrundelemente, sind sie einspringend oder nicht? Welche Fallstricke sollten vermieden werden, wenn man sie benutzt?

Ist Mutex einspringend?

Wiedereintrittssperre

Bei einer Wiedereintrittssperre kann ein process die Sperre mehrfach beanspruchen, ohne sich selbst zu blockieren. Es ist nützlich in Situationen, in denen es nicht einfach ist, den Überblick zu behalten, ob Sie bereits ein Schloss gegriffen haben. Wenn eine Sperre nicht einspringt, können Sie die Sperre ergreifen und dann blockieren, wenn Sie sie erneut greifen, wodurch Ihr eigener process blockiert wird.

Reentrancy im Allgemeinen ist eine Eigenschaft von Code, bei der es keinen zentralen änderbaren Status gibt, der beschädigt werden könnte, wenn der Code während der Ausführung aufgerufen würde. Ein solcher Aufruf könnte von einem anderen Thread ausgeführt werden, oder er könnte rekursiv durch einen Ausführungspfad erfolgen, der aus dem Code selbst stammt.

Wenn der Code auf den gemeinsam genutzten Zustand angewiesen ist, der mitten in der Ausführung aktualisiert werden könnte, ist er nicht einspringend, zumindest nicht, wenn das Update den Code brechen könnte.

Ein Anwendungsfall für die Wiedereintrittssperre

Ein (etwas generisches und erfundenes) Beispiel für eine Anwendung für eine Wiedereintrittssperre könnte sein:

  • Sie haben einige Berechnungen mit einem Algorithmus, der ein Diagramm durchläuft (vielleicht mit Zyklen). Eine Durchquerung kann den gleichen Knoten aufgrund der Zyklen oder wegen mehrerer Pfade zu demselben Knoten mehr als einmal besuchen.

  • Die Datenstruktur unterliegt dem gleichzeitigen Zugriff und könnte aus irgendeinem Grund aktualisiert werden, möglicherweise durch einen anderen Thread. Sie müssen in der Lage sein, einzelne Knoten zu sperren, um mögliche Datenbeschädigungen aufgrund von Race-Bedingungen zu vermeiden. Aus irgendeinem Grund (vielleicht Performance) möchten Sie nicht die gesamte Datenstruktur global sperren.

  • Ihre Berechnung kann keine vollständigen Informationen darüber enthalten, welche Knoten Sie besucht haben, oder Sie verwenden eine Datenstruktur, die nicht zulässt, dass “Ich schon mal hier gewesen bin” -Fragen schnell beantwortet werden.

    Ein Beispiel für diese Situation wäre eine einfache Implementierung des Dijkstra-Algorithmus mit einer Prioritätswarteschlange, die als binärer Haufen implementiert ist, oder eine Breitensuche unter Verwendung einer einfachen verketteten Liste als Warteschlange. In diesen Fällen ist das Durchsuchen der Warteschlange nach vorhandenen Einfügungen O (N), und Sie möchten dies möglicherweise nicht bei jeder Iteration tun.

In dieser Situation ist es sehr kostspielig, zu verfolgen, welche Sperren Sie bereits erworben haben. Angenommen, Sie möchten die Sperrung auf Knotenebene durchführen. Durch einen Reentrant-Sperrmechanismus können Sie nicht mehr feststellen, ob Sie zuvor einen Knoten besucht haben. Sie können den Knoten einfach blind sperren und ihn möglicherweise entsperren, nachdem Sie ihn aus der Warteschlange entfernt haben.

Wiedereintritts-Mutexe

Ein einfacher Mutex ist nicht einspringend, da sich zu einem bestimmten Zeitpunkt nur ein Thread im kritischen Abschnitt befinden kann. Wenn Sie den Mutex greifen und dann versuchen, ihn wieder zu greifen, hat ein einfacher Mutex nicht genug Informationen, um zu sagen, wer ihn zuvor gehalten hat. Um dies rekursiv zu tun, benötigen Sie einen Mechanismus, bei dem jeder Thread ein Token hat, damit Sie erkennen können, wer den Mutex gepackt hat. Dies macht den Mutex-Mechanismus etwas teurer, so dass Sie es möglicherweise nicht in allen Situationen tun möchten.

IIRC Die POSIX-Threads-API bietet die Option von Re-Entrant- und Non-Re-Entrant-Mutexen.

Mit einer Re-Entrant-Sperre können Sie eine Methode M schreiben, die Ressource A sperren und dann M rekursiv oder aus Code aufrufen, der bereits eine Sperre für A .

Mit einer nicht-einspringenden Sperre würden Sie 2 Versionen von M benötigen, eine, die sperrt und eine, die dies nicht tut, und zusätzliche Logik, um die richtige aufzurufen.

Die Wiedereintrittssperre wird in diesem Lernprogramm sehr gut beschrieben.

Das Beispiel im Tutorial ist weit weniger erfunden als in der Antwort zum Durchlaufen eines Graphen. Eine Wiedereintrittssperre ist in sehr einfachen Fällen nützlich.