Sackgasse

Beide Prozesse benötigen Ressourcen, um die Ausführung fortzusetzen. P1 Benötigt zusätzliche Ressource R1 und ist im Besitz von Ressourcen R2, P2 Benötigt zusätzliche Ressource R2 und ist im Besitz von R1; Keiner der beiden Prozesse kann fortgesetzt werden.
Vier Prozesse (blaue Linien) konkurrieren um eine Ressource (Graukreis), die nach einer rechtsweiter linken Richtlinie. Ein Deadlock tritt auf, wenn alle Prozesse die Ressource gleichzeitig sperren (schwarze Linien). Die Deadlock kann durch Brechen der Symmetrie gelöst werden.

Im Gleichzeitiges Computer, Sackgasse ist eine Situation, in der kein Mitglied einer Gruppe von Unternehmen vorgehen kann, da jedes auf ein anderes Mitglied wartet, einschließlich sich selbst, um Maßnahmen zu ergreifen, z. sperren.[1] Deadlocks sind ein häufiges Problem in Multiprozessierung Systeme, Parallele Computing, und verteilte Systeme, weil in diesen Kontexten Systeme häufig Software- oder Hardware -Sperren verwenden, um gemeinsam genutzte Ressourcen zu vermitteln und zu implementieren Prozesssynchronisation.[2]

In einem (n Betriebssystem, ein Deadlock tritt auf, wenn a Prozess oder Faden Geht ein Warten ein Zustand Weil ein Anfrage Systemressource wird von einem anderen Wartevorgang gehalten, der wiederum auf eine andere Ressource wartet, die von einem anderen Wartenprozess gehalten wird.[3] Wenn ein Prozess auf unbestimmte Zeit nicht in der Lage ist, seinen Zustand zu ändern, da von ihm angeforderte Ressourcen von einem anderen Prozess verwendet werden, auf den selbst wartet, soll das System in einem Deadlock befinden.[4]

In einem KommunikationssystemDeadlocks treten hauptsächlich aufgrund des Verlusts oder der Korruption von Signalen und nicht aufgrund von Ressourcen auf.[5]

Zwei Prozesse, die um zwei Ressourcen in der entgegengesetzten Reihenfolge konkurrieren.
  1. Ein einzelner Prozess geht durch.
  2. Der spätere Prozess muss warten.
  3. Ein Deadlock tritt auf, wenn der erste Prozess die erste Ressource gleichzeitig mit dem zweiten Prozess die zweite Ressource sperrt.
  4. Der Deadlock kann durch Stornieren und Neustart des ersten Vorgangs gelöst werden.

Notwendige Bedingungen

Eine Deadlock -Situation auf einer Ressource kann nur dann auftreten, wenn alle folgenden Bedingungen gleichzeitig in einem System auftreten:[6]

  1. Gegenseitiger Ausschluss: Mindestens eine Ressource muss in einem nicht schädlichen Modus gehalten werden. Das heißt, nur ein Prozess zu einem Zeitpunkt kann die Ressource verwenden.[7] Andernfalls würden die Prozesse nicht daran gehindert, die Ressource bei Bedarf zu verwenden. Nur ein Prozess kann die Ressource zu einem bestimmten Zeitpunkt verwenden.[8]
  2. Halten und warten oder Ressourcenhalte: Derzeit hält ein Prozess mindestens eine Ressource und fordert zusätzliche Ressourcen an, die von anderen Prozessen gehalten werden.
  3. Nein Präsentation: Eine Ressource kann nur freiwillig durch den Prozess, der sie hält, freigegeben werden.
  4. Rundschreiben warten: Jeder Prozess muss auf eine Ressource warten, die von einem anderen Prozess aufbewahrt wird, der wiederum auf den ersten Prozess wartet, um die Ressource freizugeben. Im Allgemeinen gibt es a einstellen von Warte Prozessen, P = {{P1, P2,…, PN}, so dass P1 wartet auf eine Ressource von von P2, P2 wartet auf eine Ressource von von P3 und so weiter bis PN wartet auf eine Ressource von von P1.[4][9]

Diese vier Bedingungen sind als die bekannt Coffman -Bedingungen aus ihrer ersten Beschreibung in einem Artikel von 1971 von 1971 von Edward G. Coffman, Jr.[9]

Diese Bedingungen sind zwar ausreichend, um einen Deadlock für Einzelinstanz-Ressourcensysteme zu erzeugen, aber sie weisen nur die Möglichkeit der Möglichkeit an, Systeme mit mehreren Ressourcen mit mehreren Ressourcen zu tadeln.[10]

Deadlock -Handling

Die meisten aktuellen Betriebssysteme können keine Deadlocks verhindern.[11] Wenn ein Deadlock auftritt, reagieren verschiedene Betriebssysteme in verschiedenen nicht standardmäßigen Manieren auf sie. Die meisten Ansätze arbeiten, indem sie verhindern, dass eine der vier gemeinsamen Bedingungen auftritt, insbesondere die vierte.[12] Hauptansätze sind wie folgt.

Deadlock ignorieren

Bei diesem Ansatz wird angenommen, dass ein Deadlock niemals eintreten wird. Dies ist auch eine Anwendung der Ostrich -Algorithmus.[12][13] Dieser Ansatz wurde ursprünglich von verwendet Minix und Unix.[9] Dies wird verwendet, wenn die Zeitintervalle zwischen dem Auftreten von Deadlocks groß sind und der Datenverlust jedes Mal tolerierbar ist.

Das Ignorieren von Deadlocks kann sicher gemacht werden, wenn Deadlocks sind formell bewiesen niemals auftreten. Ein Beispiel ist das RTIC -Framework.[14]

Erkennung

Nach der Deadlock -Erkennung dürfen Deadlocks auftreten. Dann wird der Zustand des Systems untersucht, um festzustellen, dass ein Deadlock aufgetreten ist und anschließend korrigiert wird. Ein Algorithmus wird verwendet, der Ressourcenzuweisung und Prozesszustände verfolgt. Er rollt zurück und startet einen oder mehrere der Prozesse neu, um die erkannte Deadlock zu entfernen. Das Erkennen eines bereits aufgetretenen Deadlocks ist leicht möglich, da die Ressourcen, die jeder Prozess gesperrt und/oder derzeit angefordert hat, dem Ressourcenplaner des Betriebssystems bekannt ist.[13]

Nachdem ein Deadlock erkannt wurde, kann er unter Verwendung einer der folgenden Methoden korrigiert werden:

  1. Prozessabschluss: Ein oder mehrere Prozesse, die am Deadlock beteiligt sind, können abgebrochen werden. Man könnte sich dafür entscheiden, alle konkurrierenden abzubrechen Prozesse am Deadlock beteiligt. Dies stellt sicher, dass Deadlock mit Sicherheit und Geschwindigkeit aufgelöst wird. Die Kosten sind jedoch hoch, da teilweise Berechnungen verloren gehen. Oder man könnte sich entscheiden, jeweils einen Prozess abzubrechen, bis die Deadlock behoben ist. Dieser Ansatz hat einen hohen Overhead, da nach jedem Abbruch ein Algorithmus bestimmen muss, ob sich das System noch in Deadlock befindet. Bei der Auswahl eines Kandidaten für die Beendigung müssen mehrere Faktoren berücksichtigt werden, wie Priorität und Alter des Prozesses.
  2. Ressourcenpräsentation: Ressourcen, die verschiedenen Prozessen zugeteilt werden, können nacheinander vorgegeben und anderen Prozessen zugewiesen werden, bis die Deadlock gebrochen ist.[15][Fehlgeschlagene Überprüfung]

Verhütung

(A) Zwei Prozesse, die nach einer erstmaligen Richtlinie der ersten kennzeichnenden Ressourcen um eine Ressource konkurrieren. (B) Deadlock tritt auf, wenn beide Prozesse die Ressource gleichzeitig sperren. (C) Der Deadlock kann sein Aufgelöst durch Brechen der Symmetrie der Schlösser. (D) Der Deadlock kann sein verhindert durch Brechen der Symmetrie des Verriegelungsmechanismus.

Deadlock -Prävention arbeitet, indem eine der vier Coffman -Bedingungen vorhanden ist.

  • Entferne den gegenseitiger Ausschluss Die Bedingung bedeutet, dass kein Prozess ausschließlich zu Zugriff auf eine Ressource verfügt. Dies erweist sich für Ressourcen, die nicht sein können, unmöglich spulen. Aber auch mit Spulenressourcen könnte der Deadlock auftreten. Algorithmen, die gegenseitige Ausgrenzung vermeiden, werden genannt Nicht blockierende Synchronisation Algorithmen.
  • Das halten und warten oder Ressourcenhalte Die Bedingungen können entfernt werden, indem Prozesse verlangt, alle Ressourcen zu beantragen, die sie benötigen, bevor sie starten (oder bevor Sie eine bestimmte Reihe von Operationen anstellen). Dieses Vorauswissen ist häufig schwer zu erfüllen und in jedem Fall eine ineffiziente Verwendung von Ressourcen. Eine andere Möglichkeit besteht darin, Prozesse zu verlangen, um Ressourcen nur dann anzufordern, wenn sie keine haben. Erstens müssen sie alle derzeit gehaltenen Ressourcen veröffentlichen, bevor sie alle Ressourcen anfordern, die sie von Grund auf neu benötigen. Auch dies ist oft unpraktisch. Dies liegt daran, dass Ressourcen zugewiesen werden können und für lange Zeiten ungenutzt bleiben. Außerdem muss ein Prozess, der eine beliebte Ressource erfordert Ressourcenhunger.[16] (Diese Algorithmen, wie z. Serialisierende Tokensind als die bekannt All-or-None-Algorithmen.))
  • Das nein Präsentation Die Bedingung kann auch schwierig oder unmöglich zu vermeiden sein, da ein Prozess in der Lage sein muss, eine Ressource für einen bestimmten Zeitraum zu haben, oder das Verarbeitungsergebnis kann inkonsistent sein oder Prügel kann auftreten. Die Unfähigkeit, die Präsentation durchzusetzen Priorität Algorithmus. Präsentation einer "gesperrten" Ressource im Allgemeinen impliziert a Rollbackund soll vermieden werden, da es sehr kostspielig im Overhead ist. Algorithmen, die die Präsentation ermöglichen lock-freie und wartungsfreie Algorithmen und optimistische Parallelitätskontrolle. Wenn ein Prozess, der einige Ressourcen und Anfragen für einige weitere Ressourcen enthält, die ihm nicht sofort zugewiesen werden können, kann die Bedingung entfernt werden, indem alle derzeit gehaltenen Ressourcen dieses Prozesses veröffentlicht werden.
  • Die endgültige Bedingung ist die Rundschreiben Bedingung. Ansätze, die kreisförmige Waiten vermeiden teilweise Bestellung von Ressourcen. Wenn keine offensichtliche Hierarchie besteht, wurde sogar die Speicheradresse der Ressourcen verwendet, um die Bestellung zu bestimmen, und Ressourcen werden in der zunehmenden Reihenfolge der Aufzählung angefordert.[4] Dijkstra -Lösung kann auch benutzt werden.

Deadlock Vermeidung

Ähnlich wie bei Deadlock Prevention stellt der Deadlock -Vermeidungsansatz sicher, dass Deadlock in einem System nicht auftritt. Der Begriff "Deadlock -Vermeidung" scheint in einem sprachlichen Kontext sehr nahe an "Deadlock -Verhinderung" zu sein, aber sie unterscheiden sich im Kontext der Deadlock -Handhabung sehr unterschiedlich. Die Vermeidung von Deadlocken verhängt keine Bedingungen, wie sie in der Prävention zu sehen ist. Hier wird jedoch jede Ressourcenanfrage sorgfältig analysiert, um festzustellen, ob sie sicher erfüllt werden kann, ohne eine Deckenschloss zu verursachen.

Die Vermeidung von Deadlocken erfordert, dass das Betriebssystem im Voraus zusätzliche Informationen darüber gegeben wird, welche Ressourcen ein Prozess während seiner Lebensdauer anfordert und verwendet wird. Deadlock -Vermeidungsalgorithmus analysiert jede einzelne Anfrage, indem er untersucht, dass in Zukunft keine Möglichkeit besteht, dass die angeforderte Ressource zugewiesen wird. Der Nachteil dieses Ansatzes ist die Anforderung von Informationen im Voraus darüber, wie Ressourcen in Zukunft angefordert werden sollen. Einer der am häufigsten verwendeten Deadlock -Vermeidungsalgorithmus ist Banker -Algorithmus.[17]

Lebensunterhalt

A Lebensunterhalt ähnelt einer Deadlock, außer dass sich die Zustände der in den Lebensunterhalt beteiligten Prozesse in Bezug auf einander ständig ändern, und keine Fortschritte.

Der Begriff wurde von Edward A. Ashcroft in einem Papier von 1975 geprägt[18] im Zusammenhang mit einer Untersuchung von Flugbuchungssystemen.[19] Livelock ist ein Sonderfall von Ressourcenhunger; Die allgemeine Definition besagt nur, dass ein bestimmter Prozess nicht voranschreitet.[20]

Lebensunterhalt ist ein Risiko bei einigen Algorithmen das erkennen und erholt sich von Sackgasse. Wenn mehr als ein Prozess Maßnahmen ergriffen, kann der Deadlock -Erkennungsalgorithmus wiederholt ausgelöst werden. Dies kann vermieden werden, indem sichergestellt wird, dass nur ein Prozess (willkürlich oder nach Priorität) Maßnahmen ergriffen.[21]

Verteilte Deadlock

Verteilte Deadlocks kann in verteilte Systeme Wenn verteilte Transaktionen oder Parallelitätskontrolle wird benutzt.

Verteilte Deadlocks können entweder durch Erstellen eines globalen Konstruktions erkannt werden Wartezeit für Diagramm von lokalen Waiten für Grafiken bei einem Deadlock-Detektor oder von a verteilter Algorithmus Wie Edgejagd.

Phantom Deadlocks sind Deadlocks, die in einem verteilten System fälschlicherweise aufgrund von Systemverzögerungen mit Systemen festgestellt werden, aber nicht tatsächlich existieren.

Zum Beispiel, wenn ein Prozess eine Ressource veröffentlicht R1 und erfragt eine Anfrage für R2und die erste Nachricht geht verloren oder verzögert, ein Koordinator (Detektor von Deadlocks) könnte fälschlicherweise einen Deadlock abschließen (falls die Anfrage für R2 während haben R1 würde einen Deadlock verursachen).

Siehe auch

Verweise

  1. ^ Coulouris, George (2012). Verteilte Systemkonzepte und Design. Pearson. p. 716. ISBN 978-0-273-76059-7.
  2. ^ Padua, David (2011). Enzyklopädie des parallelen Computers. Springer. p. 524. ISBN 9780387097657. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  3. ^ Falsafi, Babak; Midkiff, Samuel; Dennis, Jackb; Dennis, Jackb; Kauting, Amol; Campbell, Roy H; Klaucker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Philippe, Bernard; Simeh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Snir, Marc; George, Thomas; Sarin, Vivek; Jann, Joefon (2011). "Deadlocks". Enzyklopädie des parallelen Computers. Boston, MA: Springer uns. S. 524–527. doi:10.1007/978-0-387-09766-4_282. ISBN 978-0-387-09765-7. Ein Deadlock ist eine Bedingung, die in einem System aus mehreren Prozessen auftreten kann, die auf gemeinsame Ressourcen zugreifen können. Ein Deadlock soll auftreten, wenn zwei oder mehr Prozesse darauf warten, dass einander eine Ressource freigibt. Keiner der Prozesse kann Fortschritte machen.
  4. ^ a b c Silberschatz, Abraham (2006). Betriebssystemprinzipien (7. Aufl.). Wiley-India. p. 237. ISBN 9788126509621. Archiviert vom Original am 25. Januar 2022. Abgerufen 16. Oktober 2020.
  5. ^ Schneider, G. Michael (2009). Einladung zur Informatik. Cengage -Lernen. p. 271. ISBN 978-0324788594. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  6. ^ Silberschatz, Abraham (2006). Betriebssystemprinzipien (7 ed.). Wiley-India. p. 239. ISBN 9788126509621. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  7. ^ Betriebssystemkonzepte. Wiley. 2012. p. 319. ISBN 978-1-118-06333-0.
  8. ^ "ECS 150 Spring 1999: Vier notwendige und ausreichende Bedingungen für Deadlock". nob.cs.ucdavis.edu. Archiviert vom Original am 29. April 2018. Abgerufen 29. April 2018.
  9. ^ a b c Shibu, K. (2009). Intro in eingebettete Systeme (1. Aufl.). Tata McGraw-Hill Education. p. 446. ISBN 9780070145894. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  10. ^ "Betriebssysteme: Deadlocks". www.cs.uic.edu. Archiviert vom Original am 28. Mai 2020. Abgerufen 25. April 2020. Wenn eine Ressourcenkategorie mehr als eine Instanz enthält, zeigt das Vorhandensein eines Zyklus in der Ressourcenrechnung die Möglichkeit eines Deadlocks an, garantiert jedoch keine. Betrachten Sie beispielsweise Abbildungen 7.3 und 7.4 unten:
  11. ^ Silberschatz, Abraham (2006). Betriebssystemprinzipien (7 ed.). Wiley-India. p. 237. ISBN 9788126509621. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  12. ^ a b Stuart, Brian L. (2008). Prinzipien der Betriebssysteme (1. Aufl.). Cengage -Lernen. p. 446. ISBN 9781418837693. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  13. ^ a b Tanenbaum, Andrew S. (1995). Verteilte Betriebssysteme (1. Aufl.). Pearson Ausbildung. p. 117. ISBN 9788177581799. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  14. ^ "Vorwort-Echtzeit unterbrechungsgetriebene Parallelität". Archiviert Aus dem Original am 18. September 2020. Abgerufen 1. Oktober 2020.
  15. ^ "IBM Knowledge Center". www.ibm.com. Archiviert Aus dem Original am 19. März 2017. Abgerufen 29. April 2018.
  16. ^ Silberschatz, Abraham (2006). Betriebssystemprinzipien (7 ed.). Wiley-India. p. 244. ISBN 9788126509621. Archiviert vom Original am 18. April 2021. Abgerufen 16. Oktober 2020.
  17. ^ "Deadlock -Vermeidungsalgorithmen im Betriebssystem (OS)" ". Elektronik Geist. 26. Januar 2022.
  18. ^ Ashcroft, E.A. (1975). "Beweisen von Behauptungen über parallele Programme". Journal of Computer and System Sciences. 10: 110–135. doi:10.1016/s0022-0000 (75) 80018-3.
  19. ^ Kwong, Y. S. (1979). "In Ermangelung von Lebensunterlagen in parallelen Programmen". Semantik der gleichzeitigen Berechnung. Vorlesungsnotizen in Informatik. Vol. 70. S. 172–190. doi:10.1007/bfb0022469. ISBN 3-540-09511-x.
  20. ^ Anderson, James H.; Yong-Jik Kim (2001). "Gemeinsam genutzte gegenseitige Ausschluss: Große Forschungstrends seit 1986". Archiviert vom Original am 25. Mai 2006.
  21. ^ Zöbel, Dieter (Oktober 1983). "Das Deadlock -Problem: Eine klassifizierende Bibliographie". ACM SIGOPS -Betriebssysteme Überprüfung. 17 (4): 6–15. doi:10.1145/850752.850753. ISSN 0163-5980. S2CID 38901737.

Weitere Lektüre

Externe Links