Warum verursacht ein unsicherer Zustand nicht immer einen Deadlock?

10

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.)

Vikkyhacks
quelle
1
Deadlock kann ein ähnliches Konzept sein wie eine Rennbedingung , die zeitweise auftritt. Der unsichere Code löst den Deadlock nur aus, wenn eine bestimmte Sequenz ansteht.
Diese
Unsicherer Zustand bedeutet, dass theoretisch die Möglichkeit eines Deadlocks besteht. Ein Deadlock kann auftreten, wenn bestimmte Dinge passieren. Für einen sicheren Zustand spielt es keine Rolle, was passiert, es kann keinen Deadlock geben.
Nishantbhardwaj2002
1
Aus genau den gleichen Gründen, aus denen eine gefährliche Situation (im wirklichen Leben) nicht immer dazu führt, dass tatsächlich schlimme Dinge passieren.
David Richerby

Antworten:

14

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.

Wanderlogik
quelle
Vielen vielen Dank, Sir! und ich hasse mein unklares Lehrbuch ...
Ning
Ich habe aber auch einige Fragen: (1) Sie sagten ["] Der maximale Bedarf liegt bei allen möglichen Ausführungen des Programms [."] , Aber Sie sagten auch ["], wenn P0 zusätzliche 5 anfordert und P2 anfordert eine zusätzliche 1, wir werden Deadlock [. "] , wobei (1) bedeutet, wenn Max Need nicht erreicht wird, ist es möglich , Deadlock zu haben, während (2) bedeutet , dass Deadlock haben muss , wenn es nicht erreicht wird?
Ning
Ist meine Argumentation richtig ?: Falls P2 tut Anfrage zusätzlich 1 und es zu beenden , dann die freien Bänder werden (4 + 3 = 7), und da P1 Anfrage für weitere 5 dann kann es also keine Sackgasse erreicht werden. Wenn P2 jedoch nicht beendet wird, tritt ein Deadlock auf, da selbst wenn P1 nur 5 zum Beenden benötigt, immer noch 4 <5.
Ning
Für das letzte Beispiel: P0 fordert zusätzliche 5 an, dann 5 + 5 + 3 = 13> 12, also muss P0 P2 warten, um einen Deadlock zu erzeugen. Lassen Sie P2 einfach eine zusätzliche anfordern.
Bit_hcAlgorithm
7

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.
JustAnotherSoul
quelle
1

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.

Böse
quelle
0

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. unsicherer Zustand mit Zyklus 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).

Mahesh Kumar Chopker
quelle
2
Willkommen auf der Seite! Ein kleiner Punkt: Es ist am besten, den Ausdruck "darf nicht" in schriftlichem Englisch zu vermeiden, da unklar ist, ob er "darf nicht" ("Sie dürfen hier nicht parken") oder "vielleicht nicht" ("Sie mögen diesen Film möglicherweise nicht" bedeutet . ")
David Richerby
0

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.

gnasher729
quelle