Toter Punkt

Ein toter Punkt ist eine Situation, worin zwei oder mehr konkurrierende Handlungen jeder auf den anderen warten, um fertig zu sein, und so keiner jemals tut.

In einem Betriebssystem ist ein toter Punkt eine Situation, die vorkommt, wenn ein Prozess in einen Warten-Staat eingeht, weil eine dadurch gebetene Quelle durch einen anderen wartenden Prozess gehalten wird, der der Reihe nach auf eine andere Quelle wartet. Wenn ein Prozess unfähig ist, seinen Staat unbestimmt zu ändern, weil die dadurch gebetenen Mittel durch anderen wartenden Prozess verwendet werden, dann, wie man sagt, ist das System in einem toten Punkt.

Toter Punkt ist ein häufiges Problem in in einer Prozession mehrgehenden Systemen, Parallele-Computerwissenschaft und verteilten Systemen, wo Software und Hardware-Schlösser verwendet werden, um geteilte Mittel und Werkzeug-Prozess-Synchronisation zu behandeln.

In Fernmeldesystemen kommen tote Punkte hauptsächlich wegen verlorener oder korrupter Signale statt des Quellenstreits vor.

Beispiele

Situation des toten Punktes kann im Vergleich zum klassischen "Huhn oder Ei" Problem sein. Es kann auch als ein paradoxer "Fang als 22" Situation betrachtet werden. Ein echtes analoges Weltbeispiel würde ein unlogisches Statut sein ist an der Kansas gesetzgebenden Körperschaft am Anfang des 20. Jahrhunderts vorbeigegangen, das festgesetzt hat:

Ein einfaches computergestütztes Beispiel ist wie folgt. Nehmen Sie an, dass ein Computer drei CD-Laufwerke und drei Prozesse hat. Jeder der drei Prozesse hält einen der Laufwerke. Wenn jeder Prozess jetzt um einen anderen Laufwerk bittet, werden die drei Prozesse in einem toten Punkt sein. Jeder Prozess wird auf den "CD-Laufwerk veröffentlicht" Ereignis warten, das nur durch einen der anderen wartenden Prozesse verursacht werden kann. So läuft es auf eine kreisförmige Kette hinaus.

Notwendige Bedingungen

Eine Situation des toten Punktes kann nur entstehen, wenn alle folgenden Bedingungen gleichzeitig in einem System halten:

  1. Gegenseitiger Ausschluss: Mindestens eine Quelle muss non-shareable sein. Nur ein Prozess kann die Quelle in jedem gegebenen Moment der Zeit verwenden.
  2. Halten Sie und Warten Sie oder Quellenholding: Ein Prozess hält zurzeit mindestens eine Quelle und bittet um zusätzliche Mittel, die durch andere Prozesse gehalten werden.
  3. Kein Vorkaufsrecht: Das Betriebssystem muss nicht de-allocate Mittel, sobald sie zugeteilt worden sind; sie müssen durch den haltenden Prozess freiwillig veröffentlicht werden.
  4. Rundschreiben Wartet: Ein Prozess muss auf eine Quelle warten, die durch einen anderen Prozess gehalten wird, der der Reihe nach auf den ersten Prozess wartet, um die Quelle zu veröffentlichen. Im Allgemeinen gibt es eine Reihe von Warten-Prozessen, P = {P, P..., P}, solch, dass P auf eine durch P gehaltene Quelle wartet, wartet P auf eine Quelle, die durch P und so weiter gehalten ist, bis P auf eine durch P gehaltene Quelle wartet.

Diese vier Bedingungen sind als die Bedingungen von Coffman aus ihrer ersten Beschreibung in einem 1971-Artikel von Edward G. Coffman dem Jüngeren bekannt. Die Unerfüllung von einigen dieser Bedingungen ist genug, um einen toten Punkt vom Auftreten auszuschließen.

Das Berühren des toten Punktes

Aktuellste Betriebssysteme können keinen toten Punkt davon abhalten vorzukommen. Wenn ein toter Punkt vorkommt, antworten verschiedene Betriebssysteme ihnen in verschiedenen Sondermanieren. Die meisten Annäherungen arbeiten, indem sie eine der vier Bedingungen von Coffman gehindert wird, besonders die vierte vorzukommen. Hauptannäherungen sind wie folgt.

Das Ignorieren des toten Punktes

In dieser Annäherung wird es angenommen, dass ein toter Punkt nie vorkommen wird. Das ist auch eine Anwendung des Straußenalgorithmus. Diese Annäherung wurde durch MINIX und UNIX am Anfang verwendet.

Das wird verwendet, wenn die Zeitabstände zwischen Ereignissen von toten Punkten groß sind und der Datenverlust jedes Mal übernommen hat, wenn erträglich ist. Es wird in sehr kritischen Systemen vermieden.

Entdeckung

Unter der Entdeckung des toten Punktes wird toten Punkten erlaubt vorzukommen. Dann wird der Staat des Systems untersucht, um zu entdecken, dass ein toter Punkt vorgekommen ist und nachher es korrigiert wird. Ein Algorithmus wird verwendet, dass Spur-Betriebsmittelzuweisung und Prozess-Staaten, er wiederholt und ein oder mehr von den Prozessen wiederanfängt, um den entdeckten toten Punkt zu entfernen. Das Ermitteln eines toten Punktes, der bereits vorgekommen ist, ist seit den Mitteln leicht möglich, die jeder Prozess geschlossen und/oder zurzeit gebeten hat, sind dem Quellenplaner des Betriebssystems bekannt.

Entdeckungstechniken des toten Punktes schließen ein, aber werden auf die Musterüberprüfung nicht beschränkt. Diese Annäherung baut ein Zustandsmodell, auf dem sie eine Fortschritt-Analyse durchführt und alle möglichen Endsätze im Modell findet. Diese dann vertritt jeder einen toten Punkt.

Nachdem ein toter Punkt bestimmt wird, kann er durch das Verwenden von einer der folgenden Methoden korrigiert werden:

  1. Prozess-Beendigung: Ein oder mehr am toten Punkt beteiligter Prozess kann abgebrochen werden. Wir können beschließen, alle am toten Punkt beteiligten Prozesse abzubrechen. Das stellt sicher, dass toter Punkt mit der Gewissheit und Geschwindigkeit aufgelöst wird. Aber der Aufwand ist hoch, weil teilweise Berechnung verloren wird. Oder wir können beschließen, einen Prozess auf einmal abzubrechen, bis der tote Punkt aufgelöst wird. Diese Annäherung hat hohe allgemeine Kosten, weil nach jeder Abtreibung ein Algorithmus entdecken muss, wenn das System noch im toten Punkt ist. Mehrere Faktoren müssen betrachtet werden, während man einen Kandidaten für die Beendigung, wie Vorrang und Alter des Prozesses wählt.
  2. Quellenvorkaufsrecht: Verschiedenen Prozessen zugeteilte Quelle kann nacheinander durch Vorkaufsrecht erworben und anderen Prozessen zugeteilt werden, bis toter Punkt gebrochen wird.

Verhinderung

Verhinderung des toten Punktes arbeitet, indem sie eine der vier Bedingungen von Coffman gehindert wird vorzukommen.

  • Das Entfernen der gegenseitigen Ausschluss-Bedingung bedeutet, dass kein Prozess exklusiven Zugang zu einer Quelle haben wird. Das erweist sich unmöglich für Mittel, die spooled nicht sein können. Aber sogar mit spooled Mitteln konnte toter Punkt noch vorkommen. Algorithmen, die gegenseitigen Ausschluss vermeiden, werden blockierungsfreie Synchronisationsalgorithmen genannt.
  • Das Halten und wartet oder Quelle, die meint, dass Bedingungen entfernt werden können, indem sie Prozesse verlangt wird, um alle Mittel zu bitten, die sie vor dem Aufspringen (oder vor dem Unternehmen eines besonderen Satzes von Operationen) brauchen werden. Diese Fortschritt-Kenntnisse sind oft schwierig zu befriedigen und sind jedenfalls ein ineffizienter Gebrauch von Mitteln. Ein anderer Weg ist zu verlangen, dass Prozesse um Mittel nur bitten, wenn er niemanden hat. So zuerst müssen sie alle ihr zurzeit Mittel vor der Anforderung aller Mittel veröffentlichen, die sie von Kratzer brauchen werden. Das ist häufig auch unpraktisch. Es ist so, weil Quelle zugeteilt werden und unbenutzt seit langen Zeiträumen bleiben kann. Außerdem kann ein Prozess, der eine populäre Quelle verlangt, unbestimmt warten müssen, weil solch ein Prozess immer etwas Prozess zugeteilt werden kann, auf Quellenverhungern hinauslaufend. (Diese Algorithmen, wie, Jetons in Fortsetzungen zu veröffentlichen, sind als die all-none Algorithmen bekannt.)
  • Keine Vorkaufsrecht-Bedingung kann auch schwierig oder unmöglich sein zu vermeiden, weil ein Prozess im Stande sein muss, eine Quelle für eine bestimmte Zeitdauer zu haben, oder das in einer Prozession gehende Ergebnis inkonsequent sein kann oder Dresche vorkommen kann. Jedoch kann Unfähigkeit, Vorkaufsrecht geltend zu machen, einen Vorzugsalgorithmus stören. Das Vorkaufsrecht einer "ausgesperrten" Quelle bezieht allgemein einen rollback ein und soll vermieden werden, da es in oben sehr kostspielig ist. Algorithmen, die Vorkaufsrecht erlauben, schließen ohne Schlösser ein und warten - freie Algorithmen und optimistische Parallelitätskontrolle.
  • Die Endbedingung ist das Rundschreiben warten auf Bedingung. Annäherungen, die Rundschreiben vermeiden, warten schließen unbrauchbar machende Unterbrechungen während kritischer Abteilungen und des Verwendens einer Hierarchie ein, um eine teilweise Einrichtung von Mitteln zu bestimmen. Wenn keine offensichtliche Hierarchie besteht, ist sogar die Speicheradresse von Mitteln verwendet worden, um Einrichtung zu bestimmen, und Mittel werden in der zunehmenden Ordnung der Enumeration gebeten. Die Lösung von Dijkstra kann auch verwendet werden.

Aufhebung

Toter Punkt kann vermieden werden, wenn die bestimmte Information über Prozesse für das Betriebssystem vor der Zuteilung von Mitteln, solcher als verfügbar ist, welche Mittel ein Prozess in seiner Lebenszeit verbrauchen wird. Für jede Quellenbitte sieht das System, wenn es zugibt, dass die Bitte bedeuten wird, dass das System in einen unsicheren Staat eingehen wird, einen Staat bedeutend, der auf toten Punkt hinauslaufen konnte. Das System gewährt dann nur Bitten, die zu sicheren Staaten führen werden. In der Größenordnung vom System, um im Stande zu sein, zu bestimmen, ob der folgende Staat sicher oder unsicher sein wird, muss er im Voraus jederzeit wissen:

  • Mittel zurzeit verfügbarer
  • Mittel, die zurzeit jedem Prozess zugeteilt sind
  • Mittel, die erforderlich und durch diese Prozesse in der Zukunft veröffentlicht sein werden

Es ist für einen Prozess möglich, in einem unsicheren Staat, aber dafür zu sein, um auf einen toten Punkt nicht hinauszulaufen. Der Begriff von sicheren/unsicheren Staaten bezieht sich nur auf die Fähigkeit des Systems, in einen Staat des toten Punktes einzugehen, oder nicht. Zum Beispiel, wenn ein Prozess bittet, der auf einen unsicheren Staat hinauslaufen würde, aber B veröffentlicht, der Rundschreiben verhindern würde, warten dann der Staat ist unsicher, aber das System ist nicht im toten Punkt.

Ein bekannter Algorithmus, der für die Aufhebung des toten Punktes verwendet wird, ist der Algorithmus des Bankiers, der verlangt, dass Quellengebrauch-Grenze im Voraus bekannt ist. Jedoch für viele Systeme ist es unmöglich, im Voraus zu wissen, worum jeder Prozess bitten wird. Das bedeutet, dass Aufhebung des toten Punktes häufig unmöglich ist.

Zwei andere Algorithmen sind warten/Sterben und verwunden/Warten, von denen jeder eine Symmetrie brechende Technik verwendet. Sowohl in diesen Algorithmen dort besteht ein älterer Prozess (O) als auch in ein jüngerer Prozess (Y).

Prozess-Alter kann durch einen Zeitstempel in der Prozess-Entwicklungszeit bestimmt werden. Kleinere Zeitstempel sind ältere Prozesse, während größere Zeitstempel jüngere Prozesse vertreten.

Livelock

Ein livelock ist einem toten Punkt ähnlich, außer dass sich die Staaten der Prozesse, die am livelock ständig beteiligt sind, hinsichtlich einander, niemand das Fortschreiten ändern. Livelock ist ein spezieller Fall des Quellenverhungerns; die allgemeine Definition stellt nur fest, dass ein spezifischer Prozess nicht fortschreitet.

Ein wirkliches Beispiel von livelock kommt vor, wenn sich zwei Menschen in einem schmalen Gang treffen, und jeder versucht, höflich zu sein, indem er sich beiseite bewegt, um den anderen Pass zu lassen, aber sie enden damit, von Seite zu Seite zu schwanken, ohne irgendwelche Fortschritte zu machen, weil sie beide wiederholt denselben Weg zur gleichen Zeit bewegen.

Livelock ist eine Gefahr mit einigen Algorithmen, die entdecken und sich von totem Punkt erholen. Wenn mehr als ein Prozess handelt, kann der Entdeckungsalgorithmus des toten Punktes wiederholt ausgelöst werden. Das kann durch das Sicherstellen vermieden werden, dass nur ein Prozess (gewählt zufällig oder durch den Vorrang) handelt.

Verteilter toter Punkt

Verteilte tote Punkte können in verteilten Systemen vorkommen, wenn verteilte Transaktions- oder Parallelitätskontrolle verwendet wird. Verteilte tote Punkte können entweder durch das Konstruieren eines globalen entdeckt werden warten - auf den Graphen, vom Vorortszug warten - auf Graphen an einem Entdecker des toten Punktes oder durch einen verteilten Algorithmus wie das Rand-Verfolgen.

In einem Engagement Einrichtungsbasierte verteilte Umgebung (einschließlich der starken strengen zweiphasigen Blockierung (SS2PL, oder streng) spezieller Fall) werden verteilte tote Punkte automatisch durch das Atomengagement-Protokoll aufgelöst (wie ein zweiphasiger begehen (2PC)), und nicht global warten - auf den Graphen, oder anderer Entschlossenheitsmechanismus ist erforderlich. Ähnliche automatische globale Entschlossenheit des toten Punktes kommt auch in Umgebungen vor, die 2PL verwenden, der nicht SS2PL ist (und normalerweise nicht CO; sieh Tote Punkte in 2PL). Jedoch 2PL, der nicht ist, wird SS2PL in der Praxis selten verwertet.

Tote

Gespenst-Punkte sind tote Punkte, die in einem verteilten System wegen des Systems innere Verzögerungen entdeckt werden, aber nicht mehr wirklich zur Zeit der Entdeckung bestehen.

Siehe auch

  • Der Algorithmus des Bankiers
  • Fangen Sie 22
  • Bestimmung des toten Punktes
  • Speisenphilosoph-Problem
  • Datei, die sich schließen lässt
  • Patt (im Fahrzeugverkehr)
  • Hängen Sie
  • Sackgasse
  • Unendliche Schleife
  • Linearizability
  • Musterkontrolleur kann verwendet werden, um formell nachzuprüfen, dass ein System in einen toten Punkt nie eingehen wird.
  • Straußenalgorithmus
  • Vorzugsinversion
  • Rasse-Bedingung
  • Das Schlafen des Friseur-Problems
  • Patt
  • Schloss der Leser-Schriftstellers
  • Synchronisation

Weiterführende Literatur

Links


Source is a modification of the Wikipedia article Deadlock, licensed under CC-BY-SA. Full list of contributors here.
Millry, Alabama / Camden, Alabama
Impressum & Datenschutz