Warum verursacht ein unsicherer Zustand nicht immer einen Deadlock?

Ich habe Betriebssysteme von Galvin gelesen und bin auf die folgende Zeile gestoßen:

Nicht alle unsicheren Zustände sind jedoch festgefahren. Ein unsicherer Zustand kann zu einem Deadlock führen

Kann jemand bitte erklären, wie Deadlock! = Unsicherer Zustand? Ich fing auch die gleiche Linie hier

Wenn keine sichere Sequenz vorhanden ist, befindet sich das System in einem unsicheren Zustand, was zu einem Deadlock führen kann. (Alle sicheren Zustände sind Deadlock-frei, aber nicht alle unsicheren Zustände führen zu Deadlocks.)

Sackgasse bedeutet etwas Bestimmtes: Es gibt zwei (oder mehr) Prozesse, die derzeit blockiert sind und aufeinander warten.

In einem unsicheren Zustand können Sie auch in einer Situation, wo es könnte ein Deadlock irgendwann in der Zukunft sein, aber es ist noch nicht geschehen , weil ein oder beide der Prozesse tatsächlich nicht gestartet warten.

Betrachten Sie das folgende Beispiel:

Process A                  Process B
lock X                     lock Y           # state is "unsafe"
                           unlock Y
lock Y                                      # state is back to "safe" (no deadlock this time.  We got lucky.)

In Abschnitt 7.5.1 des von Ihnen angegebenen Links finden Sie ein interessanteres Beispiel :

Stellen Sie sich ein System mit 12 Bandlaufwerken vor mit:

Process       Max Need       Current
P0:             10              5
P2:              9              3

Dies ist ein unsicherer Zustand. Aber wir sind nicht in einer Sackgasse. Es gibt nur 4 freie Antriebe, so zum Beispiel, wenn P0 tut Anfrage zusätzlich 5 und P2 tut Anfrage eine zusätzliche 1, werden wir eine Sackgasse, aber es ist noch nicht geschehen. Und P0 könnte nicht noch mehr Laufwerke anfordern, sondern könnten stattdessen die Laufwerke freizugeben es bereits. Das Max needist über alle möglichen Ausführungen des Programms, und dies ist möglicherweise nicht eine der Ausführungen, bei denen wir alle 10 Laufwerke in P0 benötigen.

Nur um zu erklären, was Wandering Logic sagte.

Angenommen, ich habe zwei Threads, die beide Zugriff auf X und Y benötigen, und keine Synchronisation und keinen Mechanismus zum Beheben von Deadlocks. Dies ist unsicher, da einer X und der andere Y sperren und dann keiner fortfahren kann. Aber es ist nicht garantiert.

Thread 1                    Thread 2
Lock X                      
Lock Y
OS Interrupts Thread 1 and passes control to Thread 2
                            Unable to lock needed resources.
OS Interrupts Thread 2 and passes control to Thread 1
Unlock X                    
Unlock Y                    
                            Lock Y
                            Lock X
 ....

Dieses Szenario endete nicht in einer Sackgasse, aber es könnte sein. Aufgrund der Funktionsweise von Threading gibt es keinen festgelegten Ablauf. Das Betriebssystem steuert das Threading und kann daher wie folgt auftreten:

Thread 1                    Thread 2
Lock X        
OS Interrupts Thread 1 and passes control to Thread 2
                            Lock Y              
DEADLOCK Thread 1 needs Y, Thread 2 needs X. Neither knows to back down and simply waits.

Der sichere Zustand ist sicher Deadlock-frei, aber wenn Sie nicht alle Anforderungen erfüllen können, um einen Deadlock zu verhindern, kann dies auftreten. Wenn zum Beispiel zwei Threads beim Starten von Thread A in einen Deadlock geraten, dann Thread B, aber wenn sie das Gegenteil (B, A) starten, funktionieren sie einwandfrei - lassen Sie mich annehmen, dass B besser ist;) Der Systemzustand ist unsicher, aber mit der glücklichen Startsequenz wird es funktionieren. Kein Deadlock, aber es ist möglich. Wenn Sie sie auch von Hand synchronisieren - in guter Reihenfolge starten - ist dies gefährlich - aus irgendeinem Grund werden sie möglicherweise nicht wie gewünscht abgefeuert - das System ist immer noch unsicher (wegen eines möglichen Deadlocks), aber die Wahrscheinlichkeit dafür ist gering. Bei einigen externen Ereignissen wie dem Einfrieren von Threads oder Interrupts nach dem Fortfahren schlägt dies fehl.

Sie müssen erkennen, dass ein sicherer Zustand eine ausreichende Bedingung ist, um einen Deadlock zu vermeiden, aber ein unsicherer Zustand ist nur ein notwendiger Zustand. Es ist momentan schwer, Code aus dem Kopf zu schreiben, aber ich kann nach etwas suchen. Ich habe in Ada Code gefunden, der mehr als 99/100 Mal mehrere Wochen lang einwandfrei funktionierte (und dann aufgrund eines Neustarts des Servers, nicht eines Deadlocks, gestoppt wurde), aber hin und wieder nach einigen Sekunden in den Deadlock-Zustand stürzte.

Lassen Sie mich ein einfaches Beispiel im Vergleich zur Division hinzufügen: Wenn Ihre Funktion c / d dividiert und das Ergebnis zurückgibt, ohne zu prüfen, ob d gleich 0 ist, kann es zu einem Fehler der Division durch Null kommen, sodass der Code unsicher ist (gleiche Benennung beabsichtigt), aber bis Wenn Sie eine solche Unterteilung vornehmen, ist alles in Ordnung, aber nach der theoretischen Analyse ist der Code unsicher und kann in undefiniertes Verhalten verfallen, das nicht richtig gehandhabt wird.

Hier ist mein Verständnis dazu (bitte korrigieren Sie mich, wenn ich falsch liege): (A) Wenn Deadlock, bedeutet dies, dass ein Zyklus existiert (eine der notwendigen Bedingungen). (B) Ein Zyklus ist eine obligatorische Bedingung für Deadlock (sowohl für Single als auch für Multi) Instanzressourcen)

Damit wir jetzt beweisen können, dass es einen Zyklus gibt, der möglicherweise nicht zu einem Deadlock führt. Sie können hier sehen, dass ein Zyklus existiert, was bedeutet, dass ein unsicherer Zustand gefunden wurde. Dies führt jedoch möglicherweise nicht zu einem Deadlock, da die am Zyklus teilnehmende Ressource R2 den Zyklus unterbrechen kann Zyklus, sobald der Prozess P3 abgeschlossen und freigegeben ist (denken Sie daran, dass P3 keine Abhängigkeit hat oder auf eine andere Ressource wartet).

Ein trivialer unsicherer Zustand: Thread 1 nimmt Sperre A, dann Sperre B und entsperrt dann beide. Thread 2 nimmt Sperre B, dann Sperre A und entsperrt dann beide.

Dies führt nur dann zu einem Deadlock, wenn Thread 2 die Sperre B genau zwischen Thread 1, der die Sperre A einnimmt und versucht, die Sperre B zu übernehmen, oder Thread 1 die Sperre A nur zwischen Thread 2, der die Sperre B einnimmt und versucht, die Sperre A zu übernehmen.

Wenn Thread 1 und Thread 2 dies einmal pro Stunde zufällig tun und es eine Mikrosekunden-Zeitspanne gibt, die tatsächlich zu einem Deadlock führen würde. Dies kann in der Hand der Kunden sehr lange dauern, bis Sie schließlich zufällig einen Deadlock bekommen.

Gehen Sie mit geschlossenen Augen über eine Straße. Es ist unsicher. Aber du wirst nicht immer getötet.