Verteiltes DBMS - Deadlock-Handling

In diesem Kapitel werden die Mechanismen zur Behandlung von Deadlocks in Datenbanksystemen beschrieben. Wir werden die Mechanismen zur Behandlung von Deadlocks sowohl in zentralisierten als auch in verteilten Datenbanksystemen untersuchen.

Was sind Deadlocks?

Deadlock ist ein Status eines Datenbanksystems mit zwei oder mehr Transaktionen, wenn jede Transaktion auf ein Datenelement wartet, das von einer anderen Transaktion gesperrt wird. Ein Deadlock kann durch einen Zyklus im Wartediagramm angezeigt werden. Dies ist ein gerichteter Graph, in dem die Eckpunkte Transaktionen und die Kanten das Warten auf Datenelemente bezeichnen.

In dem folgenden Wartediagramm wartet die Transaktion T1 beispielsweise auf das Datenelement X, das von T3 gesperrt wird. T3 wartet auf Y, das durch T2 gesperrt ist, und T2 wartet auf Z, das durch T1 gesperrt ist. Daher wird ein Wartezyklus gebildet, und keine der Transaktionen kann mit der Ausführung fortfahren.

Deadlock-Behandlung in zentralisierten Systemen

Es gibt drei klassische Ansätze für die Behandlung von Deadlocks:

Deadlock-Prävention.
Vermeidung von Deadlocks.
Deadlock-Erkennung und -Entfernung.

Alle drei Ansätze können sowohl in ein zentrales als auch in ein verteiltes Datenbanksystem integriert werden.

Deadlock-Prävention

Der Deadlock-Verhinderungsansatz ermöglicht es keiner Transaktion, Sperren zu erwerben, die zu Deadlocks führen. Die Konvention lautet, dass, wenn mehr als eine Transaktion das Sperren desselben Datenelements anfordert, nur einer von ihnen die Sperre gewährt wird.

Eine der beliebtesten Methoden zur Verhinderung von Deadlocks ist die Vorerfassung aller Schlösser. Bei dieser Methode erfasst eine Transaktion alle Sperren, bevor sie ausgeführt wird, und behält die Sperren für die gesamte Dauer der Transaktion bei. Wenn eine andere Transaktion eine der bereits erworbenen Sperren benötigt, muss sie warten, bis alle benötigten Sperren verfügbar sind. Mit diesem Ansatz wird verhindert, dass das System blockiert wird, da keine der wartenden Transaktionen eine Sperre enthält.

Deadlock-Vermeidung

Der Deadlock-Vermeidungsansatz behandelt Deadlocks, bevor sie auftreten. Es analysiert die Transaktionen und die Sperren, um festzustellen, ob das Warten zu einem Deadlock führt oder nicht.

Das Verfahren kann kurz wie folgt angegeben werden. Transaktionen werden ausgeführt und fordern Datenelemente an, die gesperrt werden müssen. Der Sperrmanager prüft, ob die Sperre verfügbar ist. Wenn es verfügbar ist, weist der Sperrmanager das Datenelement zu und die Transaktion erwirbt die Sperre. Wenn das Element jedoch von einer anderen Transaktion im inkompatiblen Modus gesperrt wird, führt der Sperrmanager einen Algorithmus aus, um zu testen, ob das Halten der Transaktion im Wartezustand zu einem Deadlock führt oder nicht. Dementsprechend entscheidet der Algorithmus, ob die Transaktion warten kann oder eine der Transaktionen abgebrochen werden soll.

Zu diesem Zweck gibt es zwei Algorithmen, nämlich wait-die und wound-wait. Nehmen wir an, dass es zwei Transaktionen gibt, T1 und T2, bei denen T1 versucht, ein Datenelement zu sperren, das bereits von T2 gesperrt ist. Die Algorithmen sind wie folgt:

Wait-Die- Wenn T1 älter als T2 ist, darf T1 warten. Wenn T1 jünger als T2 ist, wird T1 abgebrochen und später neu gestartet.
Wound-Wait- Wenn T1 älter als T2 ist, wird T2 abgebrochen und später neu gestartet. Andernfalls darf T1 warten, wenn T1 jünger als T2 ist.

Deadlock-Erkennung und -Entfernung

Der Ansatz zur Erkennung und Entfernung von Deadlocks führt regelmäßig einen Algorithmus zur Erkennung von Deadlocks aus und entfernt Deadlocks, falls es einen gibt. Es wird nicht auf Deadlock geprüft, wenn eine Transaktion eine Anforderung für eine Sperre stellt. Wenn eine Transaktion eine Sperre anfordert, prüft der Sperrenmanager, ob diese verfügbar ist. Wenn es verfügbar ist, kann die Transaktion das Datenelement sperren. Andernfalls darf die Transaktion warten.

Da beim Gewähren von Sperranforderungen keine Vorsichtsmaßnahmen getroffen werden, sind einige Transaktionen möglicherweise blockiert. Um Deadlocks zu erkennen, überprüft der Sperrmanager regelmäßig, ob der Wartegraph Zyklen aufweist. Wenn das System blockiert ist, wählt der Sperrmanager aus jedem Zyklus eine Opfertransaktion aus. Das Opfer wird abgebrochen und zurückgerollt; und später neu gestartet. Einige der Methoden zur Opferauswahl sind:

Wählen Sie die jüngste Transaktion.
Wählen Sie die Transaktion mit den wenigsten Datenelementen.
Wählen Sie die Transaktion aus, die am wenigsten aktualisiert wurde.
Wählen Sie die Transaktion mit dem geringsten Neustartaufwand.
Wählen Sie die Transaktion, die zwei oder mehr Zyklen gemeinsam ist.

Dieser Ansatz eignet sich hauptsächlich für Systeme mit geringen Transaktionen, bei denen eine schnelle Antwort auf Sperranforderungen erforderlich ist.

Deadlock-Behandlung in verteilten Systemen

Die Transaktionsverarbeitung in einem verteilten Datenbanksystem wird ebenfalls verteilt, dh dieselbe Transaktion kann an mehr als einem Standort verarbeitet werden. Die beiden Hauptprobleme bei der Behandlung von Deadlocks in einem verteilten Datenbanksystem, die in einem zentralisierten System nicht vorhanden sind, sind:transaction location und transaction control. Sobald diese Bedenken ausgeräumt sind, werden Deadlocks durch Deadlock-Verhinderung, Deadlock-Vermeidung oder Deadlock-Erkennung und -Entfernung behandelt.

Transaktionsort

Transaktionen in einem verteilten Datenbanksystem werden an mehreren Standorten verarbeitet und verwenden Datenelemente an mehreren Standorten. Der Umfang der Datenverarbeitung ist nicht gleichmäßig auf diese Standorte verteilt. Der Verarbeitungszeitraum variiert ebenfalls. Daher kann dieselbe Transaktion an einigen Standorten aktiv und an anderen inaktiv sein. Wenn sich zwei widersprüchliche Transaktionen an einem Standort befinden, kann es vorkommen, dass sich eine davon inaktiv befindet. Dieser Zustand tritt in einem zentralisierten System nicht auf. Dieses Problem wird als Transaktionsspeicherortproblem bezeichnet.

Dieses Problem kann durch das Daisy-Chain-Modell behoben werden. In diesem Modell enthält eine Transaktion bestimmte Details, wenn sie von einem Standort zu einem anderen verschoben wird. Einige der Details sind die Liste der erforderlichen Tabellen, die Liste der erforderlichen Sites, die Liste der besuchten Tabellen und Sites, die Liste der Tabellen und Sites, die noch besucht werden müssen, und die Liste der erworbenen Sperren mit Typen. Nachdem eine Transaktion entweder durch Festschreiben oder Abbrechen beendet wurde, sollten die Informationen an alle betroffenen Sites gesendet werden.

Transaktionskontrolle

Die Transaktionssteuerung befasst sich mit der Bestimmung und Steuerung der Standorte, die für die Verarbeitung einer Transaktion in einem verteilten Datenbanksystem erforderlich sind. Es gibt viele Optionen hinsichtlich der Wahl, wo die Transaktion verarbeitet werden soll und wie das Kontrollzentrum festgelegt werden soll, wie z.

Ein Server kann als Kontrollzentrum ausgewählt werden.
Das Kontrollzentrum kann von einem Server zum anderen wechseln.
Die Verantwortung für das Controlling kann von mehreren Servern geteilt werden.

Verteilte Deadlock-Prävention

Genau wie bei der zentralisierten Deadlock-Verhinderung sollte eine Transaktion beim verteilten Deadlock-Verhinderungsansatz alle Sperren erwerben, bevor mit der Ausführung begonnen wird. Dies verhindert Deadlocks.

Der Standort, an dem die Transaktion eingeht, wird als steuernder Standort bezeichnet. Die steuernde Site sendet Nachrichten an die Sites, an denen sich die Datenelemente befinden, um die Elemente zu sperren. Dann wartet es auf Bestätigung. Wenn alle Sites bestätigt haben, dass sie die Datenelemente gesperrt haben, wird die Transaktion gestartet. Wenn eine Site oder Kommunikationsverbindung ausfällt, muss die Transaktion warten, bis sie repariert wurde.

Obwohl die Implementierung einfach ist, weist dieser Ansatz einige Nachteile auf -

Die Vorerfassung von Sperren erfordert eine lange Zeit für Kommunikationsverzögerungen. Dies erhöht die für die Transaktion erforderliche Zeit.
Bei einem Site- oder Linkfehler muss eine Transaktion lange warten, damit sich die Sites erholen. Währenddessen sind die Elemente auf den laufenden Websites gesperrt. Dies kann die Ausführung anderer Transaktionen verhindern.
Wenn der steuernde Standort ausfällt, kann er nicht mit den anderen Standorten kommunizieren. Diese Sites halten die gesperrten Datenelemente weiterhin in ihrem gesperrten Zustand, was zu einer Blockierung führt.

Verteilte Deadlock-Vermeidung

Wie im zentralisierten System behandelt die Vermeidung verteilter Deadlocks Deadlocks vor dem Auftreten. Darüber hinaus müssen in verteilten Systemen Probleme mit dem Transaktionsort und der Transaktionssteuerung behoben werden. Aufgrund der Verteilung der Transaktion können die folgenden Konflikte auftreten:

Konflikt zwischen zwei Transaktionen auf derselben Site.
Konflikt zwischen zwei Transaktionen an verschiedenen Standorten.

Im Konfliktfall kann eine der Transaktionen abgebrochen werden oder gemäß den Algorithmen für verteiltes Warten oder Warten warten.

Nehmen wir an, dass es zwei Transaktionen gibt, T1 und T2. T1 kommt an Standort P an und versucht, ein Datenelement zu sperren, das an diesem Standort bereits von T2 gesperrt wurde. Daher gibt es an Standort P einen Konflikt. Die Algorithmen sind wie folgt:

Distributed Wound-Die
- Wenn T1 älter als T2 ist, darf T1 warten. T1 kann die Ausführung fortsetzen, nachdem Standort P eine Nachricht erhalten hat, dass T2 an allen Standorten entweder festgeschrieben oder erfolgreich abgebrochen wurde.
- Wenn T1 jünger als T2 ist, wird T1 abgebrochen. Die Parallelitätskontrolle an Standort P sendet eine Nachricht an alle Standorte, die T1 besucht hat, um T1 abzubrechen. Die steuernde Site benachrichtigt den Benutzer, wenn T1 an allen Sites erfolgreich abgebrochen wurde.
Distributed Wait-Wait
- Wenn T1 älter als T2 ist, muss T2 abgebrochen werden. Wenn T2 an Standort P aktiv ist, bricht Standort P T2 ab und setzt es zurück und sendet diese Nachricht dann an andere relevante Standorte. Wenn T2 Standort P verlassen hat, aber an Standort Q aktiv ist, sendet Standort P, dass T2 abgebrochen wurde. Site L bricht dann T2 ab und setzt es zurück und sendet diese Nachricht an alle Sites.
- Wenn T1 jünger als T1 ist, darf T1 warten. T1 kann die Ausführung fortsetzen, nachdem Standort P eine Nachricht erhalten hat, dass T2 die Verarbeitung abgeschlossen hat.

Verteilte Deadlock-Erkennung

Genau wie bei der zentralisierten Deadlock-Erkennung können Deadlocks auftreten und werden entfernt, wenn sie erkannt werden. Das System führt keine Überprüfungen durch, wenn eine Transaktion eine Sperranforderung stellt. Zur Implementierung werden globale Wartediagramme erstellt. Das Vorhandensein eines Zyklus im globalen Wartediagramm zeigt Deadlocks an. Es ist jedoch schwierig, Deadlocks zu erkennen, da die Transaktion auf Ressourcen im gesamten Netzwerk wartet.

Alternativ können Deadlock-Erkennungsalgorithmen Timer verwenden. Jede Transaktion ist einem Timer zugeordnet, der auf einen Zeitraum eingestellt ist, in dem der Abschluss einer Transaktion erwartet wird. Wenn eine Transaktion nicht innerhalb dieses Zeitraums abgeschlossen wird, läuft der Timer ab und zeigt einen möglichen Deadlock an.

Ein weiteres Werkzeug für die Handhabung von Deadlocks ist ein Deadlock-Detektor. In einem zentralen System gibt es einen Deadlock-Detektor. In einem verteilten System kann es mehr als einen Deadlock-Detektor geben. Ein Deadlock-Detektor kann Deadlocks für die von ihm kontrollierten Standorte finden. Es gibt drei Alternativen für die Deadlock-Erkennung in einem verteilten System, nämlich.

Centralized Deadlock Detector - Ein Standort wird als zentraler Deadlock-Detektor bezeichnet.
Hierarchical Deadlock Detector - Eine Reihe von Deadlock-Detektoren sind hierarchisch angeordnet.
Distributed Deadlock Detector - Alle Sites sind daran beteiligt, Deadlocks zu erkennen und zu entfernen.