Rekursive Sperre (Mutex) vs nicht rekursive Sperre (Mutex)

182

Mit POSIX können Mutexe rekursiv sein. Das bedeutet, dass derselbe Thread denselben Mutex zweimal sperren kann und nicht blockiert. Natürlich muss es auch zweimal entsperrt werden, sonst kann kein anderer Thread den Mutex erhalten. Nicht alle Systeme, die Pthreads unterstützen, unterstützen auch rekursive Mutexe. Wenn sie jedoch POSIX-konform sein möchten, müssen sie dies tun .

Andere APIs (höherwertige APIs) bieten normalerweise auch Mutexe an, die häufig als Sperren bezeichnet werden. Einige Systeme / Sprachen (z. B. Cocoa Objective-C) bieten sowohl rekursive als auch nicht rekursive Mutexe. Einige Sprachen bieten auch nur die eine oder andere an. Beispielsweise sind Mutexe in Java immer rekursiv (derselbe Thread kann zweimal für dasselbe Objekt "synchronisiert" werden). Abhängig davon, welche anderen Thread-Funktionen sie anbieten, ist es möglicherweise kein Problem, keine rekursiven Mutexe zu haben, da sie leicht selbst geschrieben werden können (ich habe rekursive Mutexe bereits selbst auf der Grundlage einfacherer Mutex- / Bedingungsoperationen implementiert).

Was ich nicht wirklich verstehe: Wofür sind nicht rekursive Mutexe gut? Warum sollte ich einen Thread-Deadlock haben wollen, wenn er denselben Mutex zweimal sperrt? Selbst Hochsprachen, die dies vermeiden könnten (z. B. Testen, ob dies zum Stillstand kommt, und Auslösen einer Ausnahme, wenn dies der Fall ist), tun dies normalerweise nicht. Sie lassen stattdessen den Thread blockieren.

Ist dies nur in Fällen der Fall, in denen ich es versehentlich zweimal und nur einmal entsperre und im Falle eines rekursiven Mutex ist es schwieriger, das Problem zu finden. Stattdessen muss es sofort blockiert werden, um festzustellen, wo die falsche Sperre angezeigt wird. Aber könnte ich nicht dasselbe tun, wenn beim Entsperren ein Sperrzähler zurückgegeben wird und in einer Situation, in der ich sicher bin, dass ich die letzte Sperre freigegeben habe und der Zähler nicht Null ist, kann ich eine Ausnahme auslösen oder das Problem protokollieren? Oder gibt es einen anderen, nützlicheren Anwendungsfall für nicht rekursive Mutexe, den ich nicht sehe? Oder ist es vielleicht nur Leistung, da ein nicht rekursiver Mutex etwas schneller sein kann als ein rekursiver? Ich habe dies jedoch getestet und der Unterschied ist wirklich nicht so groß.

Mecki
quelle

Antworten:

151

Der Unterschied zwischen einem rekursiven und einem nicht rekursiven Mutex hat mit dem Eigentum zu tun. Im Fall eines rekursiven Mutex muss der Kernel den Thread verfolgen, der den Mutex beim ersten Mal tatsächlich erhalten hat, damit er den Unterschied zwischen der Rekursion und einem anderen Thread erkennen kann, der stattdessen blockieren sollte. Wie eine andere Antwort hervorhob, gibt es eine Frage des zusätzlichen Overheads sowohl hinsichtlich des Speichers zum Speichern dieses Kontexts als auch der Zyklen, die zum Verwalten dieses Kontexts erforderlich sind.

Hier spielen jedoch auch andere Überlegungen eine Rolle.

Da der rekursive Mutex ein Gefühl der Eigenverantwortung hat, muss der Thread, der den Mutex erfasst, derselbe Thread sein, der den Mutex freigibt. Bei nicht rekursiven Mutexen besteht kein Eigentumsgefühl, und jeder Thread kann normalerweise den Mutex freigeben, unabhängig davon, welcher Thread ursprünglich den Mutex verwendet hat. In vielen Fällen handelt es sich bei dieser Art von "Mutex" eher um eine Semaphoraktion, bei der Sie den Mutex nicht unbedingt als Ausschlussgerät verwenden, sondern als Synchronisations- oder Signalisierungsgerät zwischen zwei oder mehr Threads.

Eine weitere Eigenschaft, die mit einem Gefühl der Eigenverantwortung in einem Mutex einhergeht, ist die Fähigkeit, die Prioritätsvererbung zu unterstützen. Da der Kernel den Thread verfolgen kann, der den Mutex besitzt, sowie die Identität aller Blocker, kann in einem System mit Prioritäts-Thread die Priorität des Threads, dem der Mutex derzeit gehört, auf die Priorität des Threads mit der höchsten Priorität erhöht werden das blockiert derzeit auf dem Mutex. Diese Vererbung verhindert das Problem der Prioritätsinversion, das in solchen Fällen auftreten kann. (Beachten Sie, dass nicht alle Systeme die Prioritätsvererbung für solche Mutexe unterstützen, aber es ist eine weitere Funktion, die über den Begriff des Eigentums möglich wird.)

Wenn Sie sich auf den klassischen VxWorks RTOS-Kernel beziehen, definieren diese drei Mechanismen:

  • Mutex - unterstützt Rekursion und optional Vererbung mit Priorität. Dieser Mechanismus wird üblicherweise verwendet, um kritische Datenabschnitte auf kohärente Weise zu schützen.
  • Binäres Semaphor - keine Rekursion, keine Vererbung, einfacher Ausschluss, Abnehmer und Geber müssen nicht der gleiche Thread sein, Broadcast-Release verfügbar. Dieser Mechanismus kann zum Schutz kritischer Abschnitte verwendet werden, ist jedoch auch besonders nützlich für die kohärente Signalisierung oder Synchronisation zwischen Threads.
  • Zählsemaphor - keine Rekursion oder Vererbung, fungiert als kohärenter Ressourcenzähler für jede gewünschte Anfangszählung. Threads blockieren nur, wenn die Nettozählung für die Ressource Null ist.

Auch dies variiert je nach Plattform etwas - insbesondere was sie diese Dinge nennen, aber dies sollte repräsentativ für die Konzepte und verschiedenen Mechanismen sein, die im Spiel sind.

Großer Jeff
quelle
9
Ihre Erklärung zu nicht rekursivem Mutex klang eher wie ein Semaphor. Ein Mutex (ob rekursiv oder nicht rekursiv) hat einen Eigentumsbegriff.
Jay D
@ JayD Es ist sehr verwirrend, wenn Leute über solche Dinge streiten. Also, wer ist die Entität, die diese Dinge definiert?
Pacerier
11
@ Pacerier Der relevante Standard. Diese Antwort ist z. B. falsch für posix (pthreads), bei dem das Entsperren eines normalen Mutex in einem anderen Thread als dem Thread, der ihn gesperrt hat, ein undefiniertes Verhalten ist, während das gleiche mit einer Fehlerprüfung oder einem rekursiven Mutex zu einem vorhersehbaren Fehlercode führt. Andere Systeme und Standards verhalten sich möglicherweise sehr unterschiedlich.
Nr.
Vielleicht ist das naiv, aber ich hatte den Eindruck, dass die zentrale Idee eines Mutex darin besteht, dass der Sperrfaden den Mutex entsperrt und andere Threads dies möglicherweise auch tun. Von computing.llnl.gov/tutorials/pthreads :
user657862
1
@curiousguy - Eine Broadcast-Version gibt alle auf dem Semaphor blockierten Threads frei, ohne sie explizit anzugeben (bleibt leer), während ein normaler binärer Give nur den Thread am Kopf der Warteschlange freigibt (vorausgesetzt, es ist einer blockiert).
Tall Jeff
121

Die Antwort ist nicht Effizienz. Nicht wiedereintretende Mutexe führen zu besserem Code.

Beispiel: A :: foo () erwirbt die Sperre. Es ruft dann B :: bar () auf. Das hat gut funktioniert, als du es geschrieben hast. Aber irgendwann später ändert jemand B :: bar (), um A :: baz () aufzurufen, das auch die Sperre erwirbt.

Wenn Sie keine rekursiven Mutexe haben, blockiert dies. Wenn Sie sie haben, läuft es, aber es kann brechen. A :: foo () hat das Objekt möglicherweise vor dem Aufruf von bar () in einem inkonsistenten Zustand belassen, unter der Annahme, dass baz () nicht ausgeführt werden konnte, da es auch den Mutex abruft. Aber es sollte wahrscheinlich nicht laufen! Die Person, die A :: foo () geschrieben hat, ging davon aus, dass niemand gleichzeitig A :: baz () aufrufen kann - das ist der ganze Grund, warum beide Methoden die Sperre erworben haben.

Das richtige mentale Modell für die Verwendung von Mutexen: Der Mutex schützt eine Invariante. Wenn der Mutex gehalten wird, kann sich die Invariante ändern, aber bevor der Mutex freigegeben wird, wird die Invariante wiederhergestellt. Wiedereintretende Sperren sind gefährlich, da Sie beim zweiten Erwerb der Sperre nicht mehr sicher sein können, ob die Invariante wahr ist.

Wenn Sie mit wiedereintretenden Sperren zufrieden sind, liegt dies nur daran, dass Sie ein solches Problem noch nicht debuggen mussten. Java hat heutzutage übrigens nicht wiedereintretende Sperren in java.util.concurrent.locks.

Jonathan
quelle
4
Es hat eine Weile gedauert, bis ich herausgefunden habe, dass die Invariante nicht gültig ist, wenn Sie ein zweites Mal das Schloss greifen. Guter Punkt! Was wäre, wenn es sich um eine Lese- / Schreibsperre handelt (wie bei ReadWriteLock von Java) und Sie die Lesesperre und dann die Lesesperre ein zweites Mal im selben Thread erneut erworben haben? Sie würden eine Invariante nach dem Erwerb einer Lesesperre nicht ungültig machen, oder? Wenn Sie also die zweite Lesesperre erwerben, ist die Invariante immer noch wahr.
dgrant
1
@ Jonathan Hat Java heutzutage nicht wiedereintretende Sperren in java.util.concurrent.locks ?
user454322
1
+1 Ich denke, dass die häufigste Verwendung für die Wiedereintrittssperre innerhalb einer einzelnen Klasse liegt, in der einige Methoden sowohl von geschützten als auch von nicht geschützten Codeteilen aufgerufen werden können. Dies kann eigentlich immer herausgerechnet werden. @ user454322 Sicher , Semaphore.
Maaartinus
1
Verzeihen Sie mein Missverständnis, aber ich sehe nicht, wie wichtig dies für Mutex ist. Angenommen, es handelt sich nicht um Multithreading und Sperren. A::foo()Möglicherweise befindet sich das Objekt vor dem Aufruf noch in einem inkonsistenten Zustand A::bar(). Was hat rekursiver oder nicht rekursiver Mutex mit diesem Fall zu tun?
Siyuan Ren
1
@SiyuanRen: Das Problem besteht darin, lokal über Code nachdenken zu können. Leute (zumindest ich) sind darauf trainiert, gesperrte Regionen als invariante Aufrechterhaltung zu erkennen, dh zum Zeitpunkt des Erwerbs der Sperre ändert kein anderer Thread den Status, sodass die Invarianten in der kritischen Region erhalten bleiben. Dies ist keine harte Regel, und Sie können unter Berücksichtigung der Invarianten codieren, die nicht berücksichtigt werden. Dies würde jedoch die Argumentation und Pflege Ihres Codes erschweren. Das gleiche passiert im Single-Threaded-Modus ohne Mutexe, aber dort sind wir nicht darauf trainiert, lokal in der geschützten Region zu argumentieren.
David Rodríguez - Dribeas
92

Wie von Dave Butenhof selbst geschrieben :

"Das größte aller großen Probleme mit rekursiven Mutexen ist, dass sie Sie dazu ermutigen, Ihr Sperrschema und Ihren Umfang vollständig aus den Augen zu verlieren. Dies ist tödlich. Böse. Es ist der" Fadenfresser ". Sie halten Sperren für die absolut kürzestmögliche Zeit. Punkt. Immer. Wenn Sie etwas mit gehaltenem Schloss anrufen, nur weil Sie nicht wissen, dass es gehalten wird, oder weil Sie nicht wissen, ob der Angerufene den Mutex benötigt, halten Sie ihn zu lange Richten Sie eine Schrotflinte auf Ihre Anwendung und drücken Sie den Abzug. Vermutlich haben Sie damit begonnen, Threads zu verwenden, um Parallelität zu erhalten. Sie haben jedoch gerade Parallelität verhindert. "

Chris Cleeland
quelle
9
Beachten Sie auch den letzten Teil in Butenhofs Antwort: ...you're not DONE until they're [recursive mutex] all gone.. Or sit back and let someone else do the design.
user454322
2
Er sagt auch, dass die Verwendung eines einzelnen globalen rekursiven Mutex (seiner Meinung nach benötigen Sie nur einen) als Krücke in Ordnung ist, um die harte Arbeit des Verstehens der Invarianzen einer externen Bibliothek bewusst zu verschieben, wenn Sie beginnen, sie in Multithread-Code zu verwenden. Sie sollten jedoch keine Krücken für immer verwenden, sondern die Zeit investieren, um die Parallelitätsinvarianten des Codes zu verstehen und zu beheben. Wir könnten also umschreiben, dass die Verwendung von rekursivem Mutex eine technische Verschuldung ist.
FooF
14

Das richtige mentale Modell für die Verwendung von Mutexen: Der Mutex schützt eine Invariante.

Warum sind Sie sicher, dass dies wirklich das richtige mentale Modell für die Verwendung von Mutexen ist? Ich denke, das richtige Modell schützt Daten, aber keine Invarianten.

Das Problem des Schutzes von Invarianten tritt auch in Single-Thread-Anwendungen auf und hat mit Multithreading und Mutexen nichts gemeinsam.

Wenn Sie Invarianten schützen müssen, können Sie dennoch ein binäres Semaphor verwenden, das niemals rekursiv ist.


quelle
Wahr. Es gibt bessere Mechanismen, um eine Invariante zu schützen.
ActiveTrayPrntrTagDataStrDrvr
8
Dies sollte ein Kommentar zu der Antwort sein, die diese Aussage angeboten hat. Mutexe schützen nicht nur Daten, sondern auch Invarianten. Versuchen Sie, einen einfachen Container (der einfachste ist ein Stapel) in Bezug auf Atomics (wo sich die Daten selbst schützen) anstelle von Mutexen zu schreiben, und Sie werden die Aussage verstehen.
David Rodríguez - Dribeas
Mutexe schützen keine Daten, sondern eine Invariante. Diese Invariante kann jedoch zum Schutz von Daten verwendet werden.
Jon Hanna
4

Ein Hauptgrund dafür, dass rekursive Mutexe nützlich sind, ist der mehrfache Zugriff auf die Methoden durch denselben Thread. Angenommen, die Mutex-Sperre schützt eine Bank-Klimaanlage vor Abhebungen. Wenn mit dieser Abhebung auch eine Gebühr verbunden ist, muss derselbe Mutex verwendet werden.

avis
quelle
3

Der einzig gute Anwendungsfall für Rekursionsmutex ist, wenn ein Objekt mehrere Methoden enthält. Wenn eine der Methoden den Inhalt des Objekts ändert und daher das Objekt sperren muss, bevor der Status wieder konsistent ist.

Wenn die Methoden andere Methoden verwenden (dh: addNewArray () ruft addNewPoint () auf und wird mit recheckBounds () abgeschlossen), aber jede dieser Funktionen muss den Mutex für sich sperren, dann ist rekursiver Mutex eine Win-Win-Situation.

In jedem anderen Fall (nur schlechte Codierung lösen, sogar in verschiedenen Objekten verwenden) ist dies eindeutig falsch!

DarkZeros
quelle
1

Wofür sind nicht rekursive Mutexe gut?

Sie sind absolut gut, wenn Sie sicherstellen müssen, dass der Mutex entsperrt ist, bevor Sie etwas tun. Dies liegt daran pthread_mutex_unlock, dass garantiert werden kann, dass der Mutex nur dann entsperrt wird, wenn er nicht rekursiv ist.

pthread_mutex_t      g_mutex;

void foo()
{
    pthread_mutex_lock(&g_mutex);
    // Do something.
    pthread_mutex_unlock(&g_mutex);

    bar();
}

Wenn dies g_mutexnicht rekursiv ist, wird der obige Code garantiert bar()mit entsperrtem Mutex aufgerufen .

Das Ausschalten der Möglichkeit eines Deadlocks für den Fall, dass bar()es sich um eine unbekannte externe Funktion handelt, kann durchaus dazu führen, dass ein anderer Thread versucht, denselben Mutex zu erhalten. Solche Szenarien sind in Anwendungen, die auf Thread-Pools basieren, und in verteilten Anwendungen, in denen ein Interprozessaufruf möglicherweise einen neuen Thread erzeugt, nicht ungewöhnlich, ohne dass der Client-Programmierer dies überhaupt bemerkt. In all diesen Szenarien ist es am besten, die genannten externen Funktionen erst aufzurufen, nachdem die Sperre aufgehoben wurde.

Wenn g_mutexes rekursiv wäre, gäbe es einfach keine Möglichkeit , sicherzustellen, dass es entsperrt ist, bevor Sie einen Anruf tätigen.

Igor G.
quelle