DE69422743T2

DE69422743T2 - Endlosschleife-Erkennungsgerät

Info

Publication number: DE69422743T2
Application number: DE69422743T
Authority: DE
Inventors: Kazuhiko Fujita
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1993-03-30
Filing date: 1994-03-04
Publication date: 2000-06-08
Anticipated expiration: 2014-03-05
Also published as: EP0618532A2; EP0618532B1; EP0618532A3; DE69422743D1; US5845117A

Description

Diese Erfindung bezieht sich auf eine Vorrichtung zum Detektieren einer Systemverklemmung in einem Multitasking- System.
In den letzten Jahren wurden Multitasking-Systeme entwickelt, in denen als ein Betriebsmodus eines Computer verwendenden Informationsverarbeitungssystems eine Mehrzahl von Aufgaben oder Transaktionen zur gleichen Zeit ausgeführt wird. Eine Aufgabe ist eine oder mehrere Sequenzen von Anweisungen, die als eine durch eine zentrale Verarbeitungseinheit (CPU) auszuführende Arbeitseinheit behandelt werden. Eine Transaktion ist ein Satz von Operationen, um eine vollständige Datenoperation auszuführen. Das Multitasking ist ein Zustand, in welchem zwei oder mehr Programme (Aufgaben, Transaktionen) gleichzeitig parallel auf einem einzigen Computersystem oder auf einer Mehrzahl von Computersystemen ausgeführt werden, die in einer verschachtelten Weise verbunden ist, einen Informationsaustausch dazwischen erlaubend.
In den Betriebssystemen, die dieses Multitasking unterstützen, können zwei oder mehr Aufgaben eine Computerressource gemeinsam verwenden. In solch einem Fall kann jede Aufgabe Abschnitte der Ressourcen exklusiv verwenden, die für die Ausführung der anderen Aufgabe(n) notwendig sind. Folglich sind die Aufgaben gleichzeitig wartende Ressourcen, die dem (den) anderen zugewiesen sind, wobei keine einzelne eine weitere Verarbeitung ausführen kann. Eine solche Situation nennt man Deadlock oder Systemverklemmung. Ein Ausdruck "Lock oder Verriegelung" wird gewöhnlich als ein technischer Ausdruck verwendet, der "Exklusiv Verwenden" repräsentiert, so daß ein Wort "Verriegelung" im folgenden anstelle von "exklusiv verwenden" auch als ein Verb benutzt wird.
Ein Beispiel der Systemverklemmungssituation ist in Fig. 10 gezeigt. Fig. 10 veranschaulicht ein Beispiel in einem verteilten System, das aus zwei Computersystemen i und j besteht. Ein Computersystem i führt eine Aufgabe x aus, und der andere Computer j führt eine Aufgabe y aus. Außerdem wird angenommen, daß durch die individuellen Computersysteme i und j auf zwei Ressourcen A und B zugegriffen werden kann. Der Ausdruck "Ressource", wie er hierin verwendet wird, meint Software, wie z. B. Programme, Dateien und Daten, die den Aufgaben zugewiesen werden können. Die hierin verwendete Ressource kann sich auch auf die Inhalte (Seiten oder Aufzeichnungen) einer Datenbank beziehen, die sich irgendwo anders als in den Computersystemen i und j befindet.
In Fig. 10 hat die Aufgabe x die Ressource A verriegelt, während die Aufgabe y die Ressource B verriegelt hat. Zur gleichen Zeit hat die Aufgabe y nach der Ressource A verlangt oder gefragt und wartet darauf, die Ressource A zu verriegeln. Die Aufgabe x hat gleichfalls nach der Ressource B gefragt und erwartet, die Ressource B zu verriegeln. In solch einem Fall kann die Aufgabe y die Ressource A nicht verriegeln, bis die Aufgabe x die Verriegelung auf die Ressource A freigegeben hat. Die Aufgabe x kann gleichfalls die Ressource B nicht verriegeln, bis die Aufgabe y die Verriegelung auf der Ressource B freigegeben hat. Folglich warten die Aufgaben x und y jeweils auf die durch die andere verriegelten Ressourcen. Wenn beide Aufgaben x und y suspendiert sind (warten), ist es nicht möglich, die Ressourcen A und B freizugeben, die durch sie verriegelt sind. Dementsprechend dauert diese Situation endlos an, und keine Aufgabe kann folglich eine weitere Verarbeitung ausführen.
Eine derartige Systemverklemmung ist ein Problem, das in den Multitasking-Systemen ungeachtet davon verursacht werden könnte, ob das Computersystem ein Multiverarbeitungssystem oder ein Einzelverarbeitungssystem ist und ob das Computersystem eine selbständige Verarbeitung durchführt oder als ein verteiltes System dient.
Es sollte ein Weg zum Erholen von der Systemverklemmung, wenn sie herbeigeführt ist, vorgesehen sein. Zu diesem Zweck sollten die Systemverklemmungen detektiert werden.
Ein Artikel mit dem Titel "Deadlock Detection in Distributed Systems", von M. Singhal, Computer, Bd. 22, Nr. 11, November 1989, beschreibt z. B. ein Verarbeitungssystem, in welchem eine Mehrzahl von Aufgaben einen Satz von gemeinsamen Ressourcen verwendet. Das beschriebene Verarbeitungssystem kann umfassen: ein Aufgabenverwaltungsmittel zum Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten; ein Verriegelungsverwaltungsmittel zum Verwalten, welche Ressource durch welche Aufgabe verriegelt wird, und betreibbar, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, um eine Wartebeziehungsangabe zu erzeugen, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet; ein Registriermittel zum Registrieren solch einer erzeugten Wartebeziehungsangabe; und ein Systemverklemmung-Detektionsmittel, das auf der Grundlage solcher in dem Registriermittel registrierten Wartebeziehungsangeben betreibbar ist, um eine Systemverklemmungsbedingung zu detektieren, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine durch eine andere der Aufgaben der Gruppe verriegelte Ressource erwartet und eine weitere Verarbeitung nicht ausführen kann.
Um die Systemverklemmungen effektiv zu detektieren, sollten die folgenden Anforderungen erfüllt sein.
Erstens ist es notwendig, ein inkorrektes Detektieren einer Phantom-Systemverklemmung als eine Systemverklemmung in einer Situation zu vermeiden, in der keine Systemverklemmung vorliegt. (Erste Anforderung)
Zweitens sollten alle Systemverklemmungen detektiert werden. Mit anderen Worten, jede Systemverklemmung, falls tatsächlich herbeigeführt, sollte detektiert werden. (Zweite Anforderung)
Drittens sollten jegliche Effekte auf das System aufgrund einer Detektion der Systemverklemmungen soweit wie möglich reduziert sein. Im einzelnen sollte ein Stoppen einer Aufgabe, um eine Systemverklemmung zu detektieren, falls möglich vermieden werden. (Dritte Anforderung)
Falls das Multitasking-System auf einem verteilten System erreicht wird, sollte zusammen mit den oben erwähnten Anforderungen die folgende Anforderung erfüllt sein. Wenn es erforderlich ist, daß Systeme untereinander kommunizieren, um die Systemverklemmungen zu detektieren, sollte eine Overhead- oder Gemeinkosten-Zeit, die die Systeme für die Kommunikation oder Übermittlung aufwenden, soweit wie möglich reduziert sein. (Vierte Anforderung)
Herkömmliche Systemverklemmung-Detektiervorrichtungen basieren auf einer Detektion der Systemverklemmungen mit einer Erfüllung der oben erwähnten ersten bis dritten Anforderungen mittels Erfüllen der folgenden Bedingungen. Die Bedingungen sind:
(a) Ohne asynchronen (unerwarteten) Abbruch von einer der beiden konkurrierenden Transaktionen;
(b) Ohne Verzögerung und Verlust von Übermittlungsnachrichten zwischen den Systemen, wenn das Multitasking-System auf dem verteilten System erreicht ist;
(c) Ohne Modifikation einer Transaktionswartebeziehung während einer Detektion der Systemverklemmungen; und
(d) Ohne einen unerwarteten Zusammenbruch (asynchrones Ausfallen) des Systems, wenn das Multitasking-System auf dem verteilten System erreicht ist.
Im folgenden wird eine Beziehung zwischen den ersten bis dritten Anforderungen und den Bedingungen (a) bis (d) beschrieben.
Für die Bedingung (a) macht es der asynchrone Abbruch der Transaktionen unmöglich, eine Detektion der Phantom-Systemverklemmung in der oben erwähnten ersten Anforderung zu vermeiden. Man nehme als Beispiel den Fall, in welchem die Aufgabe (Transaktion) x die Ressource A verriegelt hat, während die Aufgabe (Transaktion) y die Ressource B verriegelt hat, und in welchem die Aufgabe y asynchron abgebrochen wird, unmittelbar nachdem die Aufgabe y nach der Ressource A fragt und die Aufgabe x nach der Ressource B fragt. In solch einem Fall wird die durch die Aufgabe y verriegelte Ressource B als Folge des asynchronen Abbrechens der Aufgabe y tatsächlich freigegeben, und folglich ist es der Aufgabe x erlaubt, die Ressource B zu verriegeln. Dementsprechend wird die Systemverklemmung tatsächlich vermieden. Es ist jedoch unmöglich, diese Freigabe der Ressource B aufgrund des asynchronen Abbruchs der Aufgabe y sofort zu detektieren, was bewirkt, daß die Situation als eine Systemverklemmung betrachtet wird, selbst wenn tatsächlich keine Systemverklemmung verursacht ist.
Für die Bedingung (b) ermöglicht ein asynchroner Ausfall des Systems manchmal eine Detektion der Systemverklemmung und manchmal nicht. Dementsprechend ist es unmöglich, alle Systemverklemmungen wie in der oben erwähnten zweiten Anforderung gefordert zu detektieren. Dies verhält sich so, weil so gar das Auftreten der Systemverklemmung unsicher wird, wenn eine Übertragung einer Übermittlungsnachricht verzögert wird oder die Nachricht aufgrund einer abnormen Übermittlung verloren wird, da in einem verteilten System jedem Computersystem erlaubt ist, durch die Zwischenkommunikation der Systeme auf eine gemeinsame Ressource zuzugreifen.
Für die Bedingung (d) erlaubt gleichfalls eine Verzögerung oder ein Verlust der Übermittlungsnachricht zwischen Systemen manchmal eine Detektion der Systemverklemmung und manchmal nicht. Dementsprechend ist es unmöglich, alle Systemverklemmungen wie in der oben angeführten zweiten Anforderung gefordert zu detektieren. Dies verhält sich so, weil eine Verwaltungsinformation über die Aufgaben in dem System verloren wird und es unmöglich wird, die Systemverklemmung zu bestimmen, wenn ein System während einer Operation des anderen Systems nicht arbeitet (ausgefallen ist).
Für die Bedingung (c) kann die erste oder die zweite Anforderung nicht erfüllt sein, wenn die Transaktionswartebeziehung während einer Detektion der Systemverklemmungen geändert wird, weil eine Information diesbezüglich, welche Aufgabe welche Ressource verriegelt, verloren wird.
Um die Bedingung (c) zu erfüllen, darf jedoch keine neue Transaktion (Aufgabe) gestartet und keine neue Wartebeziehung während einer Detektion der Systemverklemmungen erzeugt werden. Mit anderen Worten, eine Akzeptanz einer etwaigen Anforderung für solch eine Aktion in dem System sollte vorübergehend suspendiert sein, um die Systemverklemmungen zu detektieren. Falls eine Aufgabe eine Anforderung für eine Ressource ausgibt, die keine Beziehung mit der Systemverklemmung aufweist, sollte dementsprechend die Anforderung suspendiert sein. Folglich hemmt ein Streben danach, die Bedingung (c) zu erfüllen, einen glatten und effektiven Betrieb des Systems, und die dritte Anforderung wird dann nicht erfüllt sein.
In der Praxis ist es unmöglich, eine Detektion der Phanton-Systemverklemmungen zu vermeiden, wenn die Bedingung (a) nicht erfüllt ist. Mit anderen Worten, es ist unmöglich, abnorme Zustände vorherzusagen und zu vermeiden, die in den individuellen Systemen hervorgerufen werden könnten, und folglich kann der asynchrone Abbruch der Aufgaben nicht vermieden werden.
Gemäß einem ersten Gesichtspunkt der vorliegenden Erfindung wird ein Verarbeitungssystem geschaffen, in welchem eine Mehrzahl von Aufgaben einen Satz gemeinsamer Ressourcen verwendet, mit: einem Aufgabenverwaltungsmittel zum Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten; einem Verriegelungsverwaltungsmittel zum Verwalten, welche Ressource durch welche Aufgabe verriegelt wird, und betreibbar, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, um eine Wartebeziehungsangabe zu erzeugen, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet; einem Registriermittel zum Registrieren solch einer erzeugten Wartebeziehungsangabe; und einem Systemverklemmung-Detektiermittel, das auf der Grundlage solcher, in dem Registriermittel registrierten Wartebeziehungsangaben betreibbar ist, um eine Systemverklemmungsbedingung zu detektieren, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine durch eine andere der Aufgaben der Gruppe verriegelte Ressource erwartet und eine weitere Verarbeitung nicht ausführen kann; dadurch gekennzeichnet, daß das Systemverklemmung-Detektiermittel betreibbar ist, um eine Systemverklemmung-Detektieroperation zum Detektieren solch einer Systemverklemmungsbedingung unabhängig von dem Aufgabenverwaltungsmittel und dem Verriegelungsverwaltungsmittel durchzuführen, und auch in dem Fall, in dem eine Wartebeziehungsangabe durch das Verarbeitungssystem während solch einer Operation erzeugt wird, betreibbar ist, um eine Registrierung dieser Angabe bis zum Abschluß der Operation zurückzuhalten.
Gemäß einem zweiten Gesichtspunkt der vorliegenden Erfindung wird ein Verarbeitungssystem zur Verwendung in einem verteilten Multitasking-Gerät geschaffen, in welchem eine Mehrzahl solcher Verarbeitungssysteme verteilt ist und in welchem eine Mehrzahl von Aufgaben einen Satz gemeinsamer Ressourcen verwendet, welches Verarbeitungssystem umfaßt: ein Aufgabenverwaltungsmittel zum Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten; ein Verriegelungsverwaltungsmittel zum Verwalten, welche Ressource durch welche Aufgabe verriegelt wird, und betreibbar, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, um eine Wartebeziehungsangabe zu erzeugen, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet; ein Übermittlungsmittel, das, wenn die erste Aufgabe in dem beanspruchten Verarbeitungssystem gerade ausgeführt wird und die zweite Aufgabe in einem anderen Verarbeitungssystem des Geräts gerade ausgeführt wird, betreibbar ist, um die Wartebeziehungsangabe dem anderen Verarbeitungssystem mitzuteilen; ein Registriermittel zum Registrieren solcher Wartebeziehungsangaben, die durch das Verriegelungsverwaltungsmittel erzeugt oder von einem anderen Verarbeitungssystem des Geräts empfangen wurden; und ein Systemverklemmung-Detektiermittel, das auf der Basis solcher, in dem Registriermittel registrierten Wartebeziehungsangaben betreibbar ist, um eine Systemverklemmungsbedingung zu detektieren, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine durch eine andere der Aufgaben der Gruppe verriegelte Ressource erwartet und eine weitere Verarbeitung nicht ausführen kann; gekennzeichnet durch ein Wartezeit- Überwachungsmittel, das betreibbar ist, um zu detektieren, wenn solch eine registrierte Wartebeziehungsangabe für eine vorbestimmte Zeit fortdauert; und ein Neuversuch-Meldung- Mittel, das betreibbar ist, wenn solch eine fortdauernde Wartebeziehungsangabe detektiert wird, um zu veranlassen, daß eine Neuversuch-Meldung auf die Aufgabe angewendet wird, deren Anforderung bewirkte, daß die fortdauernde Wartebeziehungsangabe erzeugt wurde, welche Meldung dazu dient, der Aufgabe zu melden, daß sie wieder die Anforderung machen soll, so daß die betreffende Wartebeziehungsangabe dem anderen Verarbeitungssystem wieder mitgeteilt werden kann.
Gemäß einem dritten Gesichtspunkt der vorliegenden Erfindung wird ein Verarbeitungsverfahren zur Verwendung in einem Verarbeitungssystem geschaffen, in welchem eine Mehrzahl von Aufgaben einen Satz gemeinsamer Ressourcen verwendet, mit den Schritten: Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten; Verwalten, welche Ressource durch welche Aufgabe verriegelt ist, und, wenn eine erste der Aufgaben eine Anfor derung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, Erzeugen einer Wartebeziehungsangabe, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet; Registrieren solch einer erzeugten Wartebeziehungsangabe; und, auf der Basis solcher registrierter Wartebeziehungsangaben, Detektieren einer Systemverklemmungsbedingung, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine durch eine andere der Aufgaben der Gruppe verriegelte Ressource erwartet und eine weitere Verarbeitung nicht ausführen kann; dadurch gekennzeichnet, daß eine Systemverklemmung-Detektionsoperation zum Detektieren solch einer Systemverklemmungsbedingung unabhängig von der Aufgabenverwaltung und Verriegelungsverwaltung durchgeführt wird, und in dem Fall, daß eine Wartebeziehung während solch einer Operation erzeugt wird, eine Registrierung dieser Angabe bis zum Abschluß der Operation zurückgehalten wird.
Gemäß einem vierten Gesichtspunkt der vorliegenden Erfindung wird ein Verarbeitungsverfahren zur Verwendung in einem verteilten Multitasking-Gerät geschaffen, in welchem eine Mehrzahl von Verarbeitungssystemen verteilt ist und in welchem eine Mehrzahl von Aufgaben einen Satz gemeinsamer Ressourcen verwendet, welches Verarbeitungsverfahren die Schritte umfaßt: Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr Aufgaben zu gestatten; Verwalten, welche Ressourcen durch welche Aufgabe verriegelt wird, und, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, Erzeugen einer Wartebeziehungsangabe, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet; wenn die erste Aufgabe in einem ersten der Verarbeitungssysteme gerade ausgeführt wird und die zweite Aufgabe in einem zweiten der Verarbeitungssysteme des Geräts gerade ausgeführt wird, Mitteilen der Wartebeziehungsangabe von dem ersten dem zweiten Verarbeitungssystem; Registrieren solcher Wartebeziehungsangaben, die erzeugt oder von einem anderen Verarbeitungssystem des Geräts empfangen wurden; und, auf der Basis solcher registrierter Wartebeziehungsangaben, Detektieren einer Systemverklemmungsbedingung, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine durch eine andere der Aufgaben der Gruppe verriegelte Ressource erwartet und eine weitere Verarbeitung nicht ausführen kann; gekennzeichnet durch Detektieren, in dem ersten Verarbeitungssystem, wenn solch eine registrierte Wartebeziehungsangabe für eine vorbestimmte Zeit fortdauert und, wenn solch eine fortdauernde Wartebeziehungsangabe detektiert wird, Anwenden einer Neuversuch-Meldung auf die Aufgabe, deren Anforderung bewirkte, daß die fortdauernde Wartebeziehungsangabe erzeugt wurde, welche Meldung dazu dient, der Aufgabe zu melden, daß sie die Anforderung wieder machen soll, so daß die betreffende Wartebeziehungsangabe dem zweiten Verarbeitungssystem wieder mitgeteilt werden kann.
Solche Verarbeitungssysteme und -verfahren können Systemverklemmungen detektieren, während dem System eine reduzierte Last auferlegt wird, mittels Fortsetzen einer Detektion der Systemverklemmung, selbst wenn eine Transaktionswartebeziehung während einer Detektion der Systemverklemmung geändert wird. In dem Fall eines verteilten Systems können solche Verarbeitungssysteme und -verfahren alle Systemverklemmungen detektieren, ohne eine Phantom-Systemverklemmung zu detektieren, eine Gemeinkosten-Zeit in der Übermittlung so weit wie möglich reduzieren und die Effekte auf das System aufgrund einer Detektion der Systemverklemmungen reduzieren, selbst wenn eine Verzögerung oder ein Verlust einer Übermittlungsnachricht zwischen den Systemen herbeigeführt wird, wenn eine Transaktionswartebeziehung während einer Detektion der Systemverklemmung geändert wird und wenn ein asynchroner Ausfall eines Systems hervorgerufen wird.
Nun wird beispielhaft auf die beiliegenden Zeichnungen Bezug genommen, in denen:
Fig. 1 ein Blockdiagramm ist, das eine erste Ausführungsform der vorliegenden Erfindung veranschaulicht;
Fig. 2 ein Blockdiagramm ist, das eine zweite Ausführungsform der vorliegenden Erfindung veranschaulicht;
Fig. 3 ein Blockdiagramm ist, das eine dritte Ausführungsform der vorliegenden Erfindung veranschaulicht;
Fig. 4 eine Ansicht zur Verwendung beim Beschreiben einer Beziehung zwischen einem lokalen Warten-Auf-Graph und einem globalen Warten-Auf-Graph ist;
Fig. 5 ein Flußdiagramm ist, das eine Operation eines Transaktionsverwalters in Fig. 3 veranschaulicht;
Fig. 6 ist ein Flußdiagramm ist, das eine Operation eines Ressourcenverwalters in Fig. 3 veranschaulicht;
Fig. 7 ein Flußdiagramm ist, das eine Operation eines Verriegelungsverwalters in Fig. 3 veranschaulicht;
Fig. 8 ein Flußdiagramm ist, das eine Operation eines Systemverklemmungsdetektors in Fig. 3 veranschaulicht;
Fig. 9 ein Flußdiagramm ist, das eine Operation eines Überwachungszeitgebers in Fig. 3 veranschaulicht; und
Fig. 10 eine Ansicht zur Verwendung beim Beschreiben einer Systemverklemmungssituation ist.

Erste Ausführungsform

In Fig. 1 ist eine erste Ausführungsform der vorliegenden Erfindung dargestellt. Eine Systemverklemmung-Detektiervorrichtung gemäß der ersten Ausführungsform detektiert Systemverklemmungen, die in einem Multitasking-System hervorgerufen wurden, worin eine Mehrzahl von Aufgaben 100 eine gemeinsame Ressource 101 verwendet.
Ein typisches Multitasking-System umfaßt einen Aufgabenverwalter (TM) 102 und einen Verriegelungsverwalter (LM) 103. Der Aufgabenverwalter (TM) 102 verwaltet eine Ausführung der Aufgaben (x, y) 100, um eine parallele Ausführung einer Mehrzahl von Aufgaben (x, y) 100 zu erlauben. Der Verriegelungsverwalter (LM) 103 detektiert und verwaltet eine Information diesbezüglich, welche Aufgabe 100 welche Ressource 101 gerade verriegelt oder darauf wartet, welche Aufgabe 100 zu verriegeln.
In dieser Ausführungsform ist solch ein Multitasking- System mit einer Warten-Verwaltungstabelle (LT) 105 und einem Systemverklemmungsdetektor (DD) 104 versehen. Die Warten- Verwaltungstabelle (LT) 105 registriert eine "Wartebeziehung" der Aufgabe. Der Systemverklemmungsdetektor (DD) 104 detektiert die Systemverklemmungen, die auf solchen "Wartebeziehungen" basieren, die in dieser Verwaltungstabelle (LT) 105 registriert sind.
Eine "Aufgabe" meint gewöhnlich eine oder mehrere Sequenzen von Anweisungen, die als eine Arbeitseinheit behandelt werden, welche durch eine zentrale Verarbeitungseinheit (CPU) auszuführen ist. Das Wort "Aufgabe" kann sich hier auch auf eine "Transaktion" beziehen. Eine "Transaktion" meint einen Satz von Operationen für eine vollständige Datenoperation und ist ein Konzept, das in der "Aufgabe" beinhaltet ist, die durch Programme ausgeführt wird. Ausführungsformen der vorliegenden Erfindung sind auf ein Detektieren der Verriegelungssituation gerichtet, in der jedes Programm die Ressource gemeinsam verwendet, wenn eine Mehrzahl von Programmen zur gleichen Zeit parallel ausgeführt wird. Folglich ist im Zusammenhang der vorliegenden Erfindung kein Unterschied in der Bedeutung dieser Worte signifikant, und jeder der Ausdrücke "Aufgabe", "Transaktion" und "eine durch die Programme auszuführende Ausführungseinheit" kann untereinander ausgetauscht verwendet werden. Das Wort "Aufgabe" wird im folgenden als ein Äquivalent zum Wort "Transaktion" verwendet. In Ausführungsformen der vorliegenden Erfindung sind die durch die Aufgaben 100 gemeinsam verwendete Ressource 101 Dateien (eine Sammlung von Daten), in den Dateien gespeicherte Aufzeichnungen usw. Das Wort "Verriegelung", das hier verwendet wird, bedeutet, daß eine Aufgabe oder eine Transaktion die gesamte Datei exklusiv verwendet oder eine Aufzeichnung in der Datei exklusiv verwendet.
In der vorliegenden Ausführungsform werden Systemverklemmungen in der folgenden Art und Weise detektiert. Eine Verriegelungsbeziehung zwischen der Aufgabe (Transaktion) 100 und der Ressource 101, d. h. eine "Wartebeziehung", wird in der oben erwähnten Warten-Verwaltungstabelle (LT) 105 registriert. Der Systemverklemmungsdetektor (DD) 104 schlägt eine Information in der Warten-Verwaltungstabelle (LT) 105 nach, um die Systemverklemmung zu detektieren. Diese Detektion wird unabhängig von der Aufgabenverwaltung vorgenommen, die durch den oben erwähnten Verriegelungsverwalter (LM) 103 durchgeführt wird. Der Systemverklemmungsdetektor (DD) 104 ist vorzugsweise erforderlich, um die "Wartebeziehung" in der Warten-Verwaltungstabelle (LT) 105 zu registrieren, wenn der oben erwähnte Verriegelungsverwalter (LM) 103 detektiert, daß "eine bestimmte Aufgabe in der "Wartebeziehung" für eine bestimmte Ressource" ist. Das Vorhandensein oder Nichtvorhandensein der Systemverklemmung wird mittels Nachschlagen der darin registrierten Inhalte bestimmt.
Das folgende Verfahren kann als ein Verfahren zum Registrieren der Wartebeziehung der Transaktion in der Warten- Verwaltungstabelle (LT) 105 zum Detektieren der Systemverklemmung verwendet werden. Die Wartebeziehung der Transaktion wird durch einen Graph ausgedrückt. Auf diesen Graph wird hierin auch als ein Warten-Auf-Graph (WFG) (engl. wait-for graph) verwiesen. Dieser Graph wird in der oben erwähnten Warten-Verwaltungstabelle (LT) 105 registriert.
In diesem Graph ist die in dem System i veranlaßte Transaktion x als T(i, x) definiert, während die im System j veranlaßte Transaktion y als T(j, y) definiert ist. Außerdem wird ein Warten von T(i, x) auf T(j, y), d. h. ein Warten von T(i, x) auf Freigabe der durch T(j, y) verriegelten Ressource 101, hierin repräsentiert durch:
T(i, x) → T(j, y).
In diesem Fall kann T(i, x) nicht weiter arbeiten, bis T(j, y) beendet ist.
Wenn
T(i, x) → T(j, y)
und
T(j, y) → T(i, x)
zur gleichen Zeit gehalten werden, ist eine Schleife aus
T(i, x) → T(j, y) → T(i, x)
gebildet. Dieser Fall entspricht der Systemverklemmungssituation, so daß eine Detektion dieser Schleife eine Detektion der Systemverklemmung erlaubt.
Die obige Beschreibung ist für die Detektion der Systemverklemmung zwischen zwei Systemen. Die Systemverklemmung in dem eigenen System i wird durch
T(i, x) → T(i, y) → T(i, x)
repräsentiert.
Ein Merkmal dieser Ausführungsform liegt in der Tatsache, daß der Systemverklemmungsdetektor (DD) 104 in den Systemen (i, j) unabhängig von Blöcken, wie z. B. dem Aufgabenverwalter (TM) 102 oder dem Verriegelungsverwalter (LM) 103, vorgesehen ist. Dies kann ermöglichen, daß der Systemverklemmungsdetektor asynchron mit dem Aufgabenverwalter (TM) 102 und dem Verriegelungsverwalter (LM) 103 betrieben wird.
In einem herkömmlichen Systemverklemmung-Detektierverfahren wird eine Ausführung der individuellen Aufgaben 101 vorübergehend gestoppt, um Systemverklemmungen zu detektieren, währenddessen das Vorhandensein oder Nichtvorhandensein der Systemverklemmung gemäß einer Verriegelungsinformation im Verriegelungsverwalter (LM) 103 bestimmt wird. Es ist daher schwierig, eine glatte Operation der Aufgaben 100 sicherzustellen.
Im Gegensatz dazu ist in der vorliegenden Ausführungsform die Warten-Verwaltungstabelle (LT) 105 unabhängig von dem Aufgabenverwalter (TM) 102 und dem Verriegelungsverwalter (LM) 103 vorgesehen, und die durch den oben erwähnten Verriegelungsverwalter (LM) 103 erzeugte Verriegelungsinformation wird in der Warten-Verwaltungstabelle (LT) 105 registriert. Außerdem kann der Systemverklemmungsdetektor (DD) 104 unabhängig von der Ausführung der Aufgaben 100 arbeiten. Der Systemverklemmungsdetektor (DD) 104 bestimmt das Vorhandensein oder Nichtvorhandensein der Systemverklemmung gemäß den registrierten Inhalten in der oben erwähnten Warten-Verwaltungstabelle (LT) 105 (welche registrierten Inhalte die Wartebeziehungen der Aufgaben 100 repräsentieren), wenn der Verriegelungsverwalter (LM) 103 eine Information erzeugt, die angibt, daß eine Aufgabe in einen Zustand eines Wartens auf eine Ressource 101 eintritt.
Wie oben erwähnt wurde, ist in der vorliegenden Ausführungsform der Systemverklemmungsdetektor (DD) 104 getrennt (unabhängig) von Systemelementen wie z. B. dem Aufgabenverwalter (TM) 102 und dem Verriegelungsverwalter (LM) 103 vorgesehen, die zum Ausführen der Aufgaben 100 erforderlich sind. Der Systemverklemmungsdetektor (DD) 104 arbeitet unabhängig, so daß es nicht notwendig ist, eine Ausführung der Aufgaben 100 für eine Systemverklemmung-Detektion zu suspendieren.
Eine Detektion der Systemverklemmungen durch den Systemverklemmungsdetektor (DD) 104 in der vorliegenden Ausführungsform wird vorgenommen, wenn die Wartebeziehung der Aufgabe 100 durch den oben erwähnten Verriegelungsverwalter (LM) 103 detektiert wird. Im einzelnen registriert der Systemverklemmungsdetektor (DD) 104 die Wartebeziehung in der Warten- Verwaltungstabelle (LT) 105, wenn der Verriegelungsverwalter (LM) 103 die Wartebeziehung der Aufgabe 100 detektiert. Diese Registrierung wird als ein Startauslöser für die Systemverklemmung-Detektion verwendet. Der Systemverklemmungsdetektor (DD) 104 detektiert das Vorhandensein oder Nichtvorhandensein der Systemverklemmung mittels Nachschlagen der. Warten-Verwaltungstabelle (LT) 105 als Antwort auf einen Empfang der Registrierungsmeldung.
Um die oben erwähnte "Wartebeziehung" in der oben erwähnte Warten-Verwaltungstabelle (LT) 105 zu registrieren, ist es ausreichend, wenn zwei oder mehr Aufgaben (x, y) 100 im gleichen System vorhanden sind, um die "Wartebeziehung" jeder Aufgabe 100 nur in der in dem System vorgesehenen Warten- Verwaltungstabelle (LT) 105 zu registrieren.
Falls andererseits eine Aufgabe 100 in einem System i in dem "Warte"-Zustand für eine Aufgabe in einem anderen System j (dem "Gewartet-Auf"-System) ("waited-for" system) ist, wird diese "Wartebeziehung" von dem einen System i der Warten- Verwaltungstabelle (LT) 105 des anderen Systems j gemeldet. Die Warten-Verwaltungstabelle (LT) 105 registriert diese "Wartebeziehung" als Antwort auf diese Meldung. Zur gleichen Zeit wie diese Registrierung schlägt der Systemverklemmungsdetektor (DD) 104 des anderen Systems j seine Warten- Verwaltungstabelle (LT) 105 nach, um das Vorhandensein oder Nichtvorhandensein der Systemverklemmung zu bestimmen. Es ist auch möglich, der Warten-Verwaltungstabelle (LT) 105 des Systems i eine "Wartebeziehung" mitzuteilen, die vom anderen System j empfangen wurde, um das Vorhandensein oder Nichtvorhandensein der Systemverklemmung mittels Nachschlagen dieser Warten-Verwaltungstabelle (LT) 105 zu bestimmen.
Die oben erwähnte Beschreibung ist für einen Fall, in dem die "Wartebeziehung" der Aufgabe 100 im System i und die "Wartebeziehung" der Aufgabe 100 in dem Gewartet-Auf-System j beide in der Warten-Verwaltungstabelle (LT) 105 des Systems i registriert sind. Im Gegensatz dazu kann nur die "Wartebeziehung" des Systems i in der Verwaltungstabelle (LT) 105 des Systems i registriert werden. In solch einem Fall wird auf die Warten-Verwaltungstabelle (LT) des Gewartet-Auf-Systems j durch eine Übermittlung zugegriffen, um die Systemverklemmung zu detektieren. Die "Wartebeziehung" der Aufgabe 100 im System i wird mit der "Wartebeziehung" der Aufgabe 100 in dem Gewartet-Auf-System j verglichen (verwendet). Falls die oben erwähnte Schleife gebildet ist, wird diese als die Systemverklemmung detektiert.
Gemäß dieser Ausführungsform wird, wenn eine Systemverklemmung auf genau eines der Systeme beschränkt ist, keine Übermittlung von Information von dem einen System zu anderen Systemen vorgenommen, und eine Systemverklemmung wird in dem einen System detektiert. Die Übermittlung der Information wird nur in Fällen vorgenommen, wenn die Systemverklemmung sich aus einer Gruppe von Aufgaben ergibt, die zu zwei oder mehr Systemen gehören. In den meisten derartigen Fällen ergibt sich die Systemverklemmung unter zu zwei Systemen gehörenden Aufgaben, so daß die Systemverklemmung durch eine Übermittlung detektiert werden kann.
In dieser Ausführungsform ist der Systemverklemmungsdetektor (DD) 104 von dem Aufgabenverwalter (TM) 102 und dem Verriegelungsverwalter (LM) 103 unabhängig und von diesen getrennt, und folglich wird die Detektion der Systemverklemmung die Ausführung der Aufgaben 100 nie beeinflussen.
Wenn die Systemverklemmung unter einer Gruppe von Aufgaben detektiert wird, ist es zum Erholen von der Systemverklemmung notwendig, eine Aufgabe 100 der Gruppe zwangsweise abzubrechen. Es hängt von den Systemen ab, welche Aufgabe zwangsweise abgebrochen wird. Zum Beispiel kann man der Auffassung sein, daß die Aufgabe 100 mit einer Startzeit, die später als die der anderen liegt, den geringsten Arbeitsumfang abgewickelt hat und diese Aufgabe 100 abgebrochen werden kann. Alternativ dazu kann der durch jede Aufgabe abgewickelte tatsächliche Arbeitsumfang berechnet und die Aufgabe 100, die den geringsten Arbeitsumfang abgewickelt hat, kann dann abgebrochen werden.

Zweite Ausführungsform

In Fig. 2 ist eine zweite Ausführungsform der vorliegenden Erfindung gezeigt. Eine Systemverklemmung-Detektiervorrichtung gemäß der zweiten Ausführungsform detektiert die Systemverklemmungen, die in einem Multitasking-System hervorgerufen werden, worin eine Mehrzahl von Aufgaben 200 eine gemeinsame Ressource 201 verwendet. Diese zweite Ausführungsform ist durch Aufweisen eines Überwachungszeitgebers (WT) 206 zusammen mit den in der ersten Ausführungsform beschriebenen Komponenten gekennzeichnet. Der Überwachungszeitgeber (WT) 206 ist eine Komponente zum erneuten Ausgeben einer Ressource-Gewinnen-Anforderung (resource gaining request) für eine Aufgabe (Transaktion) 200, für die eine "Wartebeziehung" für eine gegebene Zeitspanne fortgedauert hat. Aus den folgenden Gründen ist der Überwachungszeitgeber (WT) 206 vorgesehen.
Es ist unmöglich, sich von der Systemverklemmung zu erholen, wenn die Systemverklemmung, selbst wenn sie verursacht wurde, nicht detektiert wird. Ein Grund, warum eine Systemverklemmung, die tatsächlich verursacht ist, nicht detektiert wird, kann sein, daß die "Wartebeziehung"-Information aufgrund eines Übermittlungsverlusts in der Verwaltungstabelle (LT) 205 nicht registriert ist. Wenn eine "Wartebeziehung" für eine Aufgabe 200 für eine bestimmte Zeitspanne fortdauert, gibt in dieser Hinsicht der Überwachungszeitgeber (WT) 206 die Ressource-Gewinnen-Anforderung erneut aus, die bewirkte, daß die fortdauernde "Wartebeziehung" in der ersten Stelle erzeugt wurde. Folglich gibt es eine Chance, die "Wartebeziehung"-Information wieder zu der Warten-Verwaltungstabelle (LT) 205 in dem Gewartet-Auf-System (System j für eine "Wartebeziehung" T(i, x) → T(j, y)) zu übertragen, wodurch gestattet wird, daß die Systemverklemmung sicher detektiert wird.

Dritte Ausführungsform

Fig. 3 zeigt eine dritte Ausführungsform der vorliegenden Erfindung.
In dieser Ausführungsform wird das Wort "Transaktion" eher als die "Aufgabe" verwendet, die oben verwendet wird. Diese dritte Ausführungsform ist ein spezielles Beispiel eines Falles, in dem die vorliegende Erfindung in einem verteilten System ausgeführt wird.

< Allgemeine Struktur des Systems>

Fig. 3 zeigt die Struktur eines verteilten Systems. In diesem verteilten System sind zwei Computersysteme (System i und System j) in einer verteilten Art und Weise vorgesehen und durch ein Netzwerk (NW) 30 miteinander verbunden. Außerdem ist durch das Netzwerk (NW) 30 eine Datenbank (DB) 20 mit den Computersystemen i, j verbunden. Es ist erlaubt, daß die Computersysteme auf die Datenbank (DB) 20 zugreifen. Solch ein System ist z. B. für ein Abrechnungssystem einer Bank verwendbar.
Wie aus Fig. 3 ersichtlich ist, umfaßt jedes Computersystem (System i, j) einen Transaktionsverwalter (TM) 10, einen Ressourcenverwalter (RM) 11, einen Verriegelungsverwalter (LM) 12, einen Systemverklemmungsdetektor (DD) 15, eine Warten-Auf-Graph-Tabelle (Warten-Verwaltungstabelle) T3 und einen Überwachungszeitgeber (WT) 13. Das System j hat die gleiche Struktur wie das System i. Dementsprechend zeigt Fig. 3 Einzelheiten für nur das System i, und eine Veranschaulichung der detaillierten Struktur des Systems j ist weggelassen.
Die Datenbank (DB) 20 speichert eine Mehrzahl von Dateien oder Aufzeichnungen als die Ressource. In Fig. 3 sind als die Ressource die Ressourcen A und B vorgesehen.
Jeder Komponentenblock wird im folgenden ausführlich beschrieben.

< Transaktionsverwalter (TM)>

Der Transaktionsverwalter (TM) 10 verwaltet eine Ausführung von zwei oder mehr Transaktionen. Auf den Transaktionsverwalter (TM) 10 kann als der Aufgabenverwalter (TM) verwiesen werden.
Der Transaktionsverwalter (TM) 10 ist ein Block, der eine Mitteilung oder Übermittlung empfängt, die einen Start, eine Ausführung oder Festschreibung (commit) oder einen Abbruch (siehe unten) der Transaktion von einem Anwendungsprogramm angibt, um die Transaktionen in dem System zu verwalten. Im einzelnen werden, wenn die Transaktion x im System i gestartet wird, die Daten in Form von T(i, x) registriert, während diese Daten in Form von T(i, x) gelöscht werden, wenn die Transaktion x beendet ist oder abgebrochen wird.
Als Antwort auf eine Akzeptanz einer Anforderung für eine Ressource von der Transaktion leitet der Transaktionsverwalter (TM) 10 die Anforderung zum Ressourcenverwalter (RM) 11 und empfängt von dort eine Antwort (OK/NEIN). Der Transaktionsverwalter (TM) 10 akzeptiert auch eine von dem Systemverklemmungsdetektor (DD) 15 übertragene Systemverklemmung- Meldung, die angibt, daß eine Transaktion abzubrechen ist. Außerdem akzeptiert der Transaktionsverwalter (TM) 10 eine von dem Systemverklemmungsdetektor (DD) 15 übertragene Neuversuch-Meldung, um eine Ressource-Gewinnen-Anforderung an den Ressourcenverwalter (RM) 11 erneut auszugeben. Der Transaktionsverwalter (TM) 10 empfängt auch eine Mitteilung, die die Festschreibung oder den Abbruch einer Transaktion in einem anderen Computersystem (System j) angibt. Als Antwort darauf fordert der Transaktionsverwalter (TM) 10 den Systemverklemmungsdetektor (DD) 15 auf, den Warten-Auf-Graph zu registrieren oder zu löschen.
In Fig. 3 bedeutet "Start", eine Ausführung der Transaktion zu starten, während "Abbruch" bedeutet, die Transaktion abzubrechen. "Festschreibung" bedeutet, die Transaktion festzuschreiben.
Ressource-Gewinnen-Anforderungen und Ressource-Freigeben- Anforderungen im Transaktionsverwalter (TM) 10 werden in einem Zweiphasen-Verriegelung-(2PL)-System ausgeführt. Dieses System ist durch Berücksichtigung eines Vermeidens einer Detektion der Phanton-Systemverklemmungen effektiv.
Die Phantom-Systemverklemmung wird typischerweise hervorgerufen, wenn eine Registrierung und eine Löschung von Graphen miteinander konkurrieren. Wenn z. B. ein Graph von
T(i, x) → T(j, y)
schon registriert ist, wird angenommen, daß eine Anforderung zum Löschen von
T(i, x) → T(j, y)
und eine Anforderung zum Registrieren von
T(j, y) → T(i, x)
zur gleichen Zeit erzeugt und dem Systemverklemmungsdetektor (DD) 15 mitgeteilt werden. In solch einem Fall wird keine Systemverklemmung hervorgerufen, wenn die Anforderung für eine Löschung zuerst akzeptiert wird. Im Gegensatz dazu wird die Phantom-Systemverklemmung hervorgerufen, wenn die Anforderung für eine Registrierung zuerst akzeptiert wird. Die Anforderung zum Löschen von
T(i, x) → T(j, y)
wird erzeugt, wenn die durch diesen Graphen ausgedrückte Wartebeziehung aufgegeben wird (d. h. wenn T(j, y) die Verriegelung auf die Ressource freigibt). Eine Freigabe der Verriegelung wird entweder vorgenommen, wenn die Transaktion selbst die Verriegelung auf die eigene Ressource freigibt oder wenn die Transaktion asynchron abgebrochen wird.
Das Zweiphasen-Verriegelungsprotokoll ist ein Verriegelungsprotokoll, das aus zwei Phasen besteht; wenn Daten, die durch die Transaktion einmal verriegelt sind, weiterhin ver riegelt sind und die einmal nicht verriegelten weiterhin nicht verriegelt sind. Gemäß diesem Protokoll kann das gleiche Ergebnis erhalten werden, da eine Mehrzahl von Aufgaben oder Transaktionen seriell ausgeführt wird. Gemäß diesem System wird das gleiche Ergebnis geliefert, da die Aufgaben oder Transaktionen sequentiell ausgeführt werden.
Falls angenommen wird, daß die Transaktion nicht asynchron abgebrochen wird, stellt dieses System sicher, daß keine zusätzliche Anforderung für ein Verriegelung-Gewinnen erzeugt wird, wenn die Verriegelung einmal freigegeben ist. Mit anderen Worten, der einmal erzeugte Graph
T(i, x) → T(j, y)
wird nicht gelöscht, bis T(j, y) beendet ist. Wenn die Anforderung für eine Löschung von
T(i, x) → T(j, y)
erzeugt wird, ist dementsprechend T(j, y) schon beendet worden, und folglich wird keine zusätzliche Anforderung zum Erlangen oder Gewinnen der Ressource durch T(j, y) erzeugt. Somit ist es möglich sicherzustellen, daß eine Anforderung zum Registrieren von
T(j, Y) → T(i, x)
nicht erzeugt wird.
Aus den oben erwähnten Gründen ist es mittels Anwenden dieses Systems möglich, die Ursache von Phantom-Systemverklemmungen auf Situationen zu beschränken, in denen eine Transaktion asynchron abgebrochen wird.

< Ressourcenverwalter (RM)>

Der Ressourcenverwalter (RM) 11 ist mit dem Transaktionsverwalter (TM) 10 auf eine Zweiwege-Weise verbunden. Der Ressourcenverwalter (RM) 11 weist eine Ressource-Verwaltungstabelle T1 auf. Der Ressourcenverwalter (RM) 11 bildet eine entsprechende Beziehung zwischen einer Transaktion und der durch die Transaktion angeforderten Ressource gemäß den Inhalten der Ressource-Gewinnen-Anforderung und der Ressource- Freigeben-Anforderung, die vom Transaktionsverwalter (TM) 10 geliefert wurden, ab und verwaltet diese in der Ressource- Verwaltungstabelle T1.
Der Ressourcenverwalter (RM) 11 gibt als Antwort auf die von dem Transaktionsverwalter (TM) 10 gelieferte Ressource- Gewinnen-Anforderung eine Verriegelungsanforderung an den Verriegelungsverwalter (LM) 12 aus. Der Ressourcenverwalter (RM) 11 gibt als Antwort auf die vom Transaktionsverwalter (TM) 10 gelieferte Ressource-Freigeben-Anforderung eine Verriegelung-Freigeben-Anforderung an den Verriegelungsverwalter (LM) 12 aus.

< Verriegelungsverwalter (LM)>

Der Verriegelungsverwalter (LM) 12 ist mit dem Ressourcenverwalter (RM) 11 in einer Zweiwege-Weise verbunden. Der Verriegelungsverwalter (LM) 12 weist eine Verriegelung- Verwaltungstabelle T2 auf. Der Verriegelungsverwalter (LM) 12 ist eine Steuereinheit zum Steuern der Verriegelungsbedingungen unter Verwendung der Verriegelung-Verwaltungstabelle T2.
In einem Fall, in dem die Transaktionen x, y und die Ressourcen A, B vorgesehen sind und wenn die Transaktion x die Ressource A verriegelt, während die Transaktion y die Ressource b verriegelt, registriert der Verriegelungsverwalter (LM) 12 diese Beziehung in der Verriegelung-Verwaltungstabelle T2. Im einzelnen ist, wie in Fig. 3 gezeigt ist, eine Situation, in der x A verriegelt, als z. B. (x : A) definiert, während eine Situation, in der y B verriegelt, als (y : B) definiert ist. Der Verrriegelungsverwalter (LM) 12 registriert diese Information in der Verriegelung-Verwaltungstabelle T2. Die Verriegelung-Verwaltungstabelle wird zum Verwalten einer Verriegelungsinformation für die Transaktionen in dem anderen Computersystem (j oder i) und auch zum Verwalten der Verriegelungsinformation für die Transaktionen in dem eigenen Computersystem (i oder j) verwendet. Die Verriegelungsinformation für die Transaktionen in beliebigen anderen Systemen kann durch eine Übermittlung zwischen den Computersystemen erhalten werden. Alternativ dazu kann die Notwendigkeit für die Übermittlung zwischen den Computersystemen durch Erzeugen einer einzigen Verriegelung-Verwaltungstabelle T2 auf einem gemeinsamen Speicher, der durch das Computersystem (i, j) gemeinsam verwendet wird, und Verwalten von im wesentlichen der Verriegelungsinformation für alle Transaktionen elimimiert werden.
In der oben erwähnten Situation wird ferner angenommen, daß der Ressourcenverwalter (RM) 11 eine Verriegelungsanforderung für die Ressource B durch die Transaktion x und eine Verriegelungsanforderung für die Ressource A durch die Trans aktion y ausgibt. Der Verriegelungsverwalter (LM) 12 schlägt dann die Information in der Verriegelung-Verwaltungstabelle T2 nach, um zu prüfen, ob es unmöglich ist, eine solche Verriegelung vorzunehmen. Falls es unmöglich ist, wartet die Transaktion y auf die Freigabe der Verriegelung auf der Ressource A durch die Transaktion x, während die Transaktion x auf die Freigabe der Verriegelung auf die Ressource B durch die Transaktion y wartet. Diese Situationen sind als (x → B) und (y → A) definiert. Wenn diese Definitionen erzeugt werden, bestimmt der Verriegelungsverwalter (LM) 12, daß "Warten" verursacht ist. In dieser Ausführungsform wird solch eine "Wartebeziehung" registriert und in einer vom Verriegelungsverwalter (LM) 12 unabhängigen Warten-Auf-Graph-Tabelle T3 verwaltet. Wenn die "Wartebeziehung" verursacht ist, fordert der Verriegelungsverwalter (LM) 12 den Systemverklemmungsdetektor (DD) 15 auf, den Graph gemäß den oben erwähnten Definitionen zu registrieren. Beim Anfordern davon wird der Systemverklemmungsdetektor (DD) 15 auch mit Information in bezug auf die Transaktionen (x, y) versorgt; diese Information spezifiziert, in welchem Computer die Transaktion ausgeführt wird, und spezifiziert auch, durch welche Transaktion in welchem Computersystem die Ressourcen (A, B) gegenwärtig verriegelt sind.
Der Verriegelungsverwalter (LM) 12 gibt sofort eine Antwort (OK) an den Ressourcenverwalter (RM) 11 zurück, wenn die Verriegelungsanforderung vom Ressourcenverwalter (RM) 11 zu gewähren ist, d. h. die Anforderung wartet keine weitere Transaktion ab. Ein neuer Eintrag wird in einer Registrierung-Anforderungswarteschlange zum Registrieren des Warten- Auf-Graphen, der die Wartebeziehung angibt, in der Warten- Auf-Graph-Tabelle T3 gemacht, nur wenn die "Wärten"-Situation verursacht ist, gemäß der Bestimmung durch den Verriegelungsverwalter (LM) 12. Die Ausführung einer Transaktion, die das Erlangen oder Gewinnen einer Ressource erfordert, wird nicht gestoppt oder suspendiert, wenn nicht erwartet wird, daß die Anforderung auf eine andere Transaktion "wartet", ob eine Detektion von Systemverklemmungen stattfindet oder nicht.

< Systemverklemmungsdetektor (DD)>

Der Systemverklemmungsdetektor (DD) 15 ist ein Teil, um das Vorhandensein oder Nichtvorhandensein der Systemverklem mung gemäß den in der Warten-Auf-Graph-Tabelle (T3) registrierten Inhalten zu bestimmen.
Der Systemverklemmungsdetektor (DD) 15 umfaßt eine Anforderungswarteschlange-Empfangeinheit (QR) 14. Die Anforderungswarteschlange-Empfangseinheit (QR) 14 im System i empfängt Registrierungsanforderungen für einen Warten-Auf-Graph und Löschanforderungen für einen Warten-Auf-Graph vom Verriegelungsverwalter (LM) 12 in ihrem eigenen Computersystem i. Außerdem empfängt die Anforderungswarteschlange-Empfangseinheit (QR) 14 Registrierungsanforderungen für einen Warten- Auf-Graph von anderen Computersystemen j. Wenn die Transaktion in einem anderen System j abgebrochen oder festgeschrieben wird, empfängt ferner die Anforderungswarteschlange-Empfangseinheit (QR) 14 eine Löschanforderung für einen Warten-Auf- Graph von dem Transaktionsverwalter (TM) 10. Der Systemverklemmungsdetektor (DD) 15 registriert den Warten-Auf-Graph in der Warten-Auf-Graph-Tabelle (T3) oder löscht ihn aus dieser gemäß diesen Anforderungen. Das Format für diesen Warten-Auf- Graph ist wie folgt. Falls z. B. die im System i verursachte Transaktion x = T(i, x) und die im System j veranlaßte Transaktion y = T(j, y) ist, wird dann ein Warten von T(i, x) auf T(j, y) durch
T(i, x) → T(j, y)
repräsentiert.
Um einen diese Wartebeziehung repräsentierenden Warten- Auf-Graph zu registrieren, erzeugt der Systemverklemmungsdetektor (DD) 15 den Warten-Auf-Graph gemäß der vom Verriegelungsverwalter (LM) 12 gemeldeten Information.
Wenn der Warten-Auf-Graph registriert wird, startet der Systemverklemmungsdetektor (DD) 15 eine Detektion der Systemverklemmung. Wenn die Systemverklemmung detektiert wird, meldet der Systemverklemmungsdetektor (DD) 15 dem Transaktionsverwalter (TM) 10 die Systemverklemmung.
Wenn eine Anforderung zum Löschen des Graphen empfangen wird, wird der in Frage kommende Graph gelöscht, und der Systemverklemmungsdetektor (DD) meldet der wartenden Transaktion, eine Verriegelung der betreffenden Ressource erneut zu versuchen.

< Warten-Auf-Graph-Tabelle (T3)>

Die Warten-Auf-Graph-Tabelle T3 wird mit Warten-Auf- Graphen versorgt, die darin registriert werden. Wie oben erwähnt wurde, wird angenommen, daß die im System i veranlaßte Transaktion x T(i, x) und die im System j veranlaßte Transaktion y T(j, y) ist und daß ein Warten von T(i, x) auf T(j, y) durch
T(i, x) → T(j, y)
repräsentiert wird. In solch einem Fall ist der Transaktion x nicht erlaubt, die Ressource B zu verwenden, die durch die Transaktion y verriegelt wurde, bis die Transaktion y ihre Verriegelung auf der Ressource B aufgibt, z. B. T(j, y) endet. Auf diese Situation wird als die "Wartebeziehung" verwiesen, in der "T(i, x) auf T(j, y) wartet". Der Systemverklemmungsdetektor (DD) 15 registriert diesen Graph von
T(i, x) → T(j, y)
in der Warten-Auf-Graph-Tabelle T3 als die "Wartebeziehung".
Andererseits kann dieser Graph von
T(i, x) → T(j, y)
zur gleichen Zeit gehalten werden, während
T(j, y) → T(i, x)
gehalten wird. In solch einem Fall ist es der Transaktion y nicht erlaubt, eine Ressource A zu verwenden, die durch die Transaktion x verriegelt wurde, bis die Transaktion x ihre Verriegelung auf der Ressource A aufgibt, z. B. T(i, x) endet. Eine Schleife aus
T(i, x) → T(j, y) → T(j, y) → T(i, x)
wird mit diesen beiden Wartebeziehungen gebildet. Demgemäß entspricht eine Detektion dieser Schleife der Situation, in der die Systemverklemmung verursacht ist.
Die Wartebeziehung wird zwischen der Transaktion x des Systems i und der Transaktion y des Systems j veranlaßt. Der Graph von
T(i, x) → T(j, y)
wird in der Warten-Auf-Graph-Tabelle T3 des Systems i registriert, während der Graph von
T(j, y) → T(i, x)
in der Warten-Auf-Graph-Tabelle T3 des Systems j registriert wird. Demgemäß soll der in irgendeinem der beiden Systeme registrierte Graph zum anderen System übertragen werden, um zu ermöglichen, daß die beiden Graphen miteinander verglichen werden. In dieser Ausführungsform wird, wenn die "Wartebeziehung" registriert ist, diese "Wartebeziehung" auch zu dem Gewartet-Auf-System übertragen. Das heißt, wenn in der Warten- Auf-Graph-Tabelle T3 des Systems i
T(i, x) → T(j, Y)
registriert ist, überträgt der Systemverklemmungsdetektor (DD) 15 des Systems i die gleiche Wartebeziehung zur Warten- Auf-Graph-Tabelle T3 des Systems j und veranlaßt, daß sie in der Tabelle registriert wird.
Folglich wird es möglich, die Systemverklemmung in dem Gewartet-Auf-System (d. h. dem System j) durch Nachschlagen der Warten-Auf-Graph-Tabelle T3 vom System j zu detektieren. Wenn die "Wartebeziehung" der Transaktion x aufgegeben wird, sollte die Information bezüglich der "Wartebeziehung" über die Transaktion x von dem Gewartet-Auf-System (d. h. das System j) "rückgewonnen" (gelöscht) werden; andernfalls wird die Systemverklemmung ständig detektiert. Demgemäß ist es notwendig, den Graph, der die "Wartebeziehung" angibt, aus der Warten-Auf-Graph-Tabelle T3 des Gewartet-Auf-Systems (d. h. des Systems j) zu löschen oder von ihr rückzugewinnen, wenn die "Wartebeziehung" eliminiert ist. Der Systemverklemmungsdetektor (DD) 15 hat auch eine Funktion zum Löschen und Rückgewinnen des Graphen.
Wird kein Graph des Warten-Auf-Graphen detektiert, gibt dies an, daß eine Möglichkeit der Systemverklemmung in dem anderen System besteht, falls das oberste Ende des Warten- Auf-Graphen die Transaktion im anderen System ist. Folglich wird vom anderen, in Frage kommenden System verlangt, den Graph zu registrieren. Um eine Anforderung zum Registrieren des Graphen zu akzeptieren, die durch andere Systeme ausgegeben wird, registriert der Systemverklemmungsdetektor (DD) 15 einen notwendigen Graph, um die Schleife zu detektieren.
Eine Wartebeziehung kann einfach durch Transaktionen im eigenen System verursacht werden. Wenn z. B. eine Transaktion x1 = T(i, x1), die im System i veranlaßt wurde, auf eine Transaktion y1 = T(i, y1) wartet, die nur im eigenen System (d. h. im System i) veranlaßt wurde, wird
T(i, x1) → T(i, y1)
in der Warten-Auf-Graph-Tabelle T3 des eigenen Systems (d. h. des Systems i) registriert. Falls in diesem Fall
T(i, y1) → T(i, x1)
in der Warten-Auf-Graph-Tabelle T3 des eigenen Systems (d. h. des Systems i) registriert wird, wird eine Schleife aus
T(i, x1) → T(i, y1) → T(i, y1) → T(i, x1)
gebildet, gemäß der die Systemverklemmung detektiert werden kann.
In einem verteilten System kann auf die registrierten Inhalte der Warten-Auf-Graph-Tabelle in bezug auf die in einem gegebenen System veranlaßten Transaktionen kollektiv als ein lokaler Warten-Auf-Graph dieses Systems Bezug genommen werden. Außerdem kann auf einen Graph, der die Wartebeziehungen in dem gesamten verteilten System, d. h. einen Satz aller lokalen Warten-Auf-Graphen in dem verteilten System darstellt, als ein globaler Warten-Auf-Graph Bezug genommen werden. Fig. 4 ist eine Ansicht, die eine beispielhafte Beziehung zwischen lokalen und globalen Warten-Auf-Graphen veranschaulicht.
In jedem Computersystem wird nur der lokale Warten-Auf- Graph in der Warten-Auf-Graph-Tabelle T3 verwaltet. In dieser Ausführungsform überträgt, wie oben erwähnt wurde, der Systemverklemmungsdetektor (DD) 15 des Systems i die registrierten Inhalte, wie z. B. den die Wartebeziehung zwischen den Transaktionen nur im System i (seinem "eigenen" System), nicht zum anderen Computersystem j. Anderseits überträgt der Systemverklemmungsdetektor (DD) 15 den Graph, der die Wartebeziehung zwischen einer Transaktion im anderen Computersystem j und einer Transaktion in seinem eigenen Computersystem i angibt, nur zum zugeordneten System j. Berücksichtigt man, daß statistisch 90% oder mehr der Systemverklemmungen zwischen zwei Aufgaben verursacht werden, kann eine mit einer Transaktion in einem anderen System verbundene Systemverklemmung demgemäß meistens mit einer Übermittlung detektiert werden. Außerdem kann eine innerhalb eines Computersystems verursachte Systemverklemmung ohne Übermittlung detektiert werden. Demgemäß wird es möglich, die Gemeinkosten-Zeit zu reduzieren, die für die Übermittlung erforderlich ist, um die Systemverklemmungen zu detektieren.

< Überwachungszeitgeber>

Der Überwachungszeitgeber (WT) 13 ist ein Zeitgeber zur Verwendung beim Überwachen der Warten-Auf-Graph-Tabelle T3. Dieser Zeitgeber 13 überwacht die in der Warten-Auf-Graph- Tabelle T3 registrierten "Wartebeziehungen". Falls eine "Wartebeziehung" für eine vorbestimmte Zeit fortgedauert hat, seit die "Wartebeziehung" registriert wurde, gibt der Überwachungszeitgeber (WT) 13 eine Neuversuch-Meldung aus, um zu veranlassen, daß die wartende Transaktion in der "Wartebeziehung" die Ressource-Gewinnen-Anforderung neu ausgibt. Die Neuversuch-Meldung wird an die Anforderungswarteschlange- Empfangseinheit (QR) 14 geliefert. Wenn die Neuversuch- Meldung an die Anforderungswarteschlange-Empfangseinheit (QR) 14 geliefert wird, sendet der Systemverklemmungsdetektor (DD) 15 die Neuversuch-Meldung an den Transaktionsverwalter (TM) 10. Als Antwort auf dieses Neuversuchsignal gibt der Transaktionsverwalter (TM) 10 die Ressource-Gewinnen-Anforderung zur Transaktion in der Wartebeziehung neu aus.
Eine Systemverklemmung, die tatsächlich verursacht ist, kann als Folge einer Verzögerung oder eines Verlustes einer Übermittlungsnachricht zwischen den Systemen oder eines asynchronen Abschaltens oder Ausfalls des Computersystems nicht detektiert werden. Der Überwachungszeitgeber (WT) 13 dient zum Vermeiden solch einer Störung. Im einzelnen kann, wenn die Computersysteme i und j eine Übermittlung untereinander in dem verteilten System durchführen, ein Graph, der benötigt wird, um eine Systemverklemmungssituation zu detektieren, aufgrund eines Verlustes einer Übermittlungsnachricht zwischen den Systemen verloren werden. Dies macht die Detektion der Systemverklemmung unmöglich. Um dies zu vermeiden, ist der Überwachungszeitgeber (WT) 13 als ein Mechanismus zum Überwachen der Transaktionen in der Wartebeziehung vorgesehen.
Wie oben erwähnt wurde, wird eine Transaktion, die in einer Wartebeziehung ist, für welche der entsprechende Warten- Auf-Graph in der Tabelle T3 für eine vorbestimmte Zeit oder Länge registriert gewesen ist, durch den Zeitgeber 13 veranlaßt, um die Ressource-Gewinnen-Anforderung durch den Systemverklemmungsdetektor (DD) 15 erneut auszugeben. Als Antwort darauf gibt der Transaktionsverwalter (TM) 10 die Ressource- Gewinnen-Anforderung wieder aus. Falls es nicht länger erforderlich ist, daß die Transaktion wartet, wird dann die Ressource-Gewinnen-Anforderung akzeptiert. Falls es andererseits noch erforderlich ist, daß die Transaktion wartet, wird der Graph wieder zum anderen Computersystem übertragen. Dies macht den Verlust des Graphen wett, und folglich kann die Systemverklemmung detektiert werden.

< Beispielhafte Operation in jeder Komponente>

Eine Operation in den oben erwähnten Komponenten wird in Verbindung mit den Flußdiagrammen der Fig. 5 bis 9 beschrieben.

[Operation des Transaktionsverwalters (TM)]

Wie im Flußdiagramm von Fig. 5 gezeigt ist, wartet der Transaktionsverwalter (TM) 10 auf eine Anforderung, wie z. B. den Start, den Abbruch, die Festschreibung, die Ressource- Gewinnen-Anforderung, die Systemverklemmung-Meldung und die Neuversuch-Meldung (Schritt 101). Der Abbruch und die Festschreibung, die hierin verwendet werden, beinhalten diejenigen, die von anderen Computersystemen gemeldet werden. Wenn irgendeine dieser Anforderungen empfangen wird (Schritt 102), weist dann der Transaktionsverwalter (TM) 10 die Verarbeitung gemäß dem Typ der Anforderung zu.
Wenn die beim Schritt 102 empfangene Anforderung Start ist, wird diese Transaktion (auf die der Bequemlichkeit halber als T(i, x) verwiesen wird) in dem Transaktionsverwalter (TM) 10 selbst registriert (Schritt 103), und der Transaktionsverwalter wartet auf eine folgende Anforderung.
Wenn die beim Schritt 102 empfangene Anforderung ein Abbruch oder eine Festschreibung ist, wird die abzubrechende oder festzuschreibende Transaktion (auf die der Bequemlichkeit halber als T(i, x) verwiesen wird) gelöscht (Schritt 104). Als nächstes gibt der Transaktionsverwalter (TM) 10 eine Ressource-Freigeben-Anforderung an den Ressourcenverwalter (RM) 11 aus (Schritt 105). Wenn vom Ressourcenverwalter (RM) 11 eine Antwort auf die Ressource-Freigeben-Anforderung empfangen wird (Schritt 106), fordert der Transaktionsverwalter (TM) 10 den Systemverklemmungsdetektor (DD) 15 auf, den Graph zu löschen (Schritt 107). Anschließend bestimmt der Transaktionsverwalter (TM) 10, ob die in Frage kommende Anforderung von seinem eigenen Computersystem stammt (Schritt 108). Falls die Anforderung vom anderen Computersystem übertragen wurde, wird zu dieser Zeit keine Operation vorgenommen. Falls im Gegensatz dazu die Anforderung von seinem eigenen Computersystem stammt, wird dem anderen Computersystem eine Festschrei bung oder ein Abbruch gemeldet (Schritt 109). Das die Meldung empfangende Computersystem führt dann eine Verarbeitung gemäß Schritten 104 bis 107 aus.
Wenn die beim Schritt 102 empfangene Anforderung eine Ressource-Gewinnen-Anforderung ist, liefert der Transaktionsverwalter (TM) 10 die Ressource-Gewinnen-Anforderung an den Ressourcenverwalter (RM) 11 (Schritt 110). Wenn eine Antwort auf die Anforderung vom Ressourcenverwalter (RM) 11 empfangen wird (Schritt 111), sendet der Transaktionsverwalter (TM) 10 eine Antwort auf die Transaktion (Schritt 112).
Wenn die beim Schritt 102 empfangene Anforderung eine Systemverklemmung-Meldung ist, wählt der Transaktionsverwalter (TM) 10 zuerst die abzubrechende Transaktion aus den Transaktionen in der Systemverklemmungssituation aus (Schritt 120). Im einzelnen werden alle Transaktionen in der Systemverklemmungsbeziehung (worauf hierin der Bequemlichkeit halber als T(i, x), T(j, y) verwiesen wird) in der Systemverklemmung- Meldung spezifiziert. Der Transaktionsverwalter (TM) 10 wählt folglich die abzubrechende Transaktion auf der Grundlage der benannten (spezifizierten) Transaktionen aus, die in der Systemverklemmung-Meldung enthalten sind. Demgemäß wird dem Transaktionsverwalter (TM) 10 erlaubt, eine Transaktion in einem anderen Computersystem als die abzubrechende Transaktion zu spezifizieren. Anschließend meldet der Transaktionsverwalter (TM) 10 der ausgewählten Transaktion, daß die Transaktion abzubrechen ist (Schritt 121). Falls die ausgewählte Transaktion im anderen Computersystem ist, meldet der Transaktionsverwalter (TM) 10 durch den Transaktionsverwalter (TM) 10 des anderen Computersystems der ausgewählten Transaktion, daß die Transaktion abzubrechen ist.
Wenn die beim Schritt S102 empfangene Anforderung eine Neuversuch-Meldung ist, liefert der Transaktionsverwalter (TM) 10 zunächst die Ressource-Gewinnen-Anforderung an den Ressourcenverwalter (RM) 11 (Schritt 130). Wenn von dem Ressourcenverwalter (RM) 11 eine Antwort auf diese Anforderung empfangen wird (Schritt 131), sendet der Transaktionsverwalter (TM) 10 eine Antwort zurück zur Transaktion (Schritt 131)

[Operation des Ressourcenverwalters (RM)]

Wie aus dem in Fig. 6 gezeigten Flußdiagramm ersichtlich ist, wartet zunächst der Ressourcenverwalter (RM) 11 auf die Ressource-Gewinnen-Anforderung und die Ressource-Freigeben- Anforderung (Schritt 201). Wenn irgendeine der Anforderungen erzeugt und empfangen wird (Schritt 202), versucht der Ressourcenverwalter (RM) 11, die in der Ressource-Gewinnen- Anforderung gezeigte Ressource zu verriegeln, und registriert die Beziehung in der Ressource-Verwaltungstabelle T1 (Schritt 203). Mit anderen Worten, der Ressourcenverwalter (RM) 11 registriert, welche Transaktion versucht, welche Ressource zu verriegeln.
Anschließend bestimmt der Ressourcenverwalter (RM) 11, ob die Anforderung eine Ressource-Gewinnen-Anforderung oder eine Ressource-Freigeben-Anforderung ist (Schritt 204). Wenn die Anforderung eine Ressource-Gewinnen-Anforderung ist, liefert der Ressourcenverwalter (RM) 11 die Verriegelung-Gewinnen- Anforderung an den Verriegelungsverwalter (LM) 12 (Schritt 205). Wenn im Gegensatz dazu die Anforderung die Ressource- Freigeben-Anforderung ist, liefert der Ressourcenverwalter (RM) 11 die Verriegelung-Freigeben-Anforderung an den Verriegelungsverwalter (LM) 12 (Schritt 206).
Nach Empfangen einer Antwort (OK/NEIN) vom Verriegelungsverwalter (LM) 12 auf die Verriegelung-Gewinnen-Anforderung oder die Verriegelung-Freigeben-Anforderung (Schritt 207) sendet der Ressourcenverwalter (RM) 11 eine Antwort (OK/NEIN) zurück zum Transaktionsverwalter (TM) 10 (Schritt 208).

[Operation des Verriegelungsverwalters (LM)]

Wie aus dem in Fig. 7 gezeigten Flußdiagramm ersichtlich ist, empfängt als Antwort auf die Anforderung beim Schritt 205 oder Schritt 206 in Fig. 6 vom Ressourcenverwalter (RM) 11 (Schritt 301) der Verriegelungsverwalter (LM) 12 die Anforderung (Schritt 302). Anschließend bestimmt der Verriegelungsverwalter (LM) 12, ob die Anforderung eine Verriegelung- Gewinnen-Anforderung oder ein Verriegelung-Freigeben ist (Schritt 303). Wenn die Anforderung die Verriegelung- Gewinnen-Anforderung ist, bestimmt der Verriegelungsverwalter (LM) 12, ob es möglich ist, die Verriegelung zu gewinnen (Schritt 304). Falls die Verriegelung auf der Ressource verfügbar ist, registriert der Verriegelungsverwalter (LM) 12 die Verriegelungssituation in der Verriegelung-Verwaltungs tabelle T2 (Schritt 305). Falls es andererseits unmöglich ist, die Verriegelung auf der Ressource zu gewinnen, was angibt, daß es eine "Wartebeziehung" gibt, fordert der Verriegelungsverwalter (LM) 12 den Systemverklemmungsdetektor (DD) 15 auf, die Beziehung zwischen der anfordernden Transaktion und der Gewartet-Auf-Transaktion (die Transaktion, auf die die anfordernde Transaktion wartet) als ein Warten-Auf-Graph (WFG) in der Warten-Auf-Graph-Tabelle T3 zu registrieren (Schritt 306).
Anschließend meldet der Verriegelungsverwalter (LM) 12 dem Ressourcenverwalter (RM) 11, daß er dabei gescheitert ist, die Ressource zu verriegeln (d. h. "NEIN") (Schritt 309). Falls beim Schritt 303 bestimmt wird, daß die Anforderung eine Ressource-Freigeben-Anforderung ist, löscht dann der Verriegelungsverwalter (LM) 12 die Registrierung der Verriegelung von der Verriegelung-Verwaltungstabelle T2 (Schritt 307). Der Verriegelungsverwalter (LM) 12 sendet dann eine Antwort (d. h. "OK"), die einen Abschluß der Registrierung oder die Löschung angibt, an den Ressourcenverwalter (RM) 11 (Schritt 308).

[Operation des Systemverklemmungsdetektors (DD)]

Wie aus dem in Fig. 8 veranschaulichten Flußdiagramm ersichtlich ist, empfängt der Systemverklemmungsdetektor (DD) 15 die Graph-Registrieranforderung, die Graph-Löschanforderung und die Neuversuch-Meldung bei der Anforderungswarteschlange-Empfangseinheit (QR) 14. Demgemäß nimmt als Antwort auf die Anforderung (Schritt 401) der Systemverklemmungsdetektor (DD) 15 die Anforderung von der Anforderungswarteschlange-Empfangseinheit (QR) 14 auf (Schritt 402), um den Typ der Anforderung zu bestimmen (Schritt 403).
Wenn die Anforderung auf die Graph-Registrierung gerichtet ist, registriert zunächst der Systmeverklemmungsdetektor (DD) 15 den Warten-Auf-Graph in der Warten-Auf-Graph-Tabelle T3 (Schritt 404). Falls als Ergebnis eines Durchsuchens der Warten-Auf-Graph-Tabelle T3 gefunden wird, daß der gleiche Graph darin schon registriert wurde, registriert der Systemverklemmungsdetektor (DD) 15 den Graph zu diesem Zeitpunkt nicht. Als nächstes folgt der Systemverklemmungsdetektor (DD) 15 dem registrierten Graph hoch bis zu dessen oberstem Ende (Schritt 405). Gemäß diesem Ergebnis bestimmt der Systemver klemmungsdetektor (DD) 15, ob eine Schleife gebildet ist (Schritt 406). Falls eine Schleife gebildet ist, benachrichtigt der Systemverklemmungsdetektor (DD) 15 den Transaktionsverwalter (TM) 10 von der Systemverklemmung (Schritt 407). Falls keine Schleife gebildet ist, bestimmt der Systemverklemmungsdetektor (DD) 15, ob das oberste Ende des Graphen eine Transaktion in seinem eigenen Computersystem ist (Schritt 408). Falls das Ende einer Transaktion in seinem eigenen Computersystem ist, kehrt die Steuerung dann zu Schritt 401 zurück. Falls andererseits das oberste Ende des Graphen eine Transaktion in einem anderen Computersystem ist, sendet der Systemverklemmungsdetektor (DD) 15 den in Frage kommenden Graph an den Systemverklemmungsdetektor (DD) 15 des anderen Computersystems, um ihn zu veranlassen, den Graph in der Warten-Auf-Graph-Tabelle T3 des anderen Computersystems zu registrieren (Schritt 409).
Wenn die Anforderung beim Schritt 403 darauf gerichtet ist, den Graph zu löschen, sucht der Systemverklemmungsdetektor (DD) 15 die Warten-Auf-Graph-Tabelle T3 durch, um den in Frage kommenden Graph zu finden (Schritt 410). Wenn der in Frage kommende Graph gefunden ist, löscht der Systemverklemmungsdetektor (DD) 15 diesen Graph (Schritt 411). Anschließend liefert der Systemverklemmungsdetektor (DD) 15 eine Neuversuch-Meldung an den Transaktionsverwalter (TM) 10, um der Transaktion, die in dem gelöschten Graph als wartend angegeben war, zu melden, daß sie die Ressource wieder anfordern soll, auf die sie gerade wartete (Schritt 412). Wenn die Anforderung beim Schritt 403 eine Neuversuch-Anforderung ist, löscht der Systemverklemmungsdetektor (DD) 15 den Graph der Transaktion, die erneut versucht werden soll (Schritt 420). Der Systemverklemmungsdetektor (DD) 15 liefert dann eine Neuversuch-Meldung an den Transaktionsverwalter (TM) 10 (Schritt 421).

[Operation des Überwachungszeitgebers (WT)]

Wie aus dem in Fig. 9 veranschaulichten Flußdiagramm ersichtlich ist, sucht der Überwachungszeitgeber (WT) 13 sequentiell die Transaktionen (wie z. B. T(i, x)), die in der Warten-Auf-Graph-Tabelle T3 registriert sind (Schritt 501). Anschließend bestimmt der Überwachungszeitgeber (WT) 13, ob die Transaktion x in der "Wartebeziehung" ist (Schritt 502).
Falls die gesuchte Transaktion nicht in der "Wartebeziehung" ist, wird der Schritt 501 wieder ausgeführt. Falls andererseits die gesuchte Transaktion in der "Wartebeziehung" ist, beginnt der Überwachungszeitgeber (WT) 13, die Zeit zu zählen. Wenn eine vorbestimmte Zeit verstrichen ist (Schritt 503), liefert der Überwachungszeitgeber (WT) 13 eine Neuversuch-Meldung an den Systemverklemmungsdetektor (DD) 15 (Schritt 504). Wenn die "Wartebeziehung" beim Schritt 503 eliminiert ist, bevor die vorbestimmte Zeit verstrichen ist, wird der Schritt 501 wieder ausgeführt (Schritt 502).

< Spezifische Beispiele der Systemverklemmung-Detektion>

Als nächstes werden für drei verschiedene Fälle Beispiele der durch die oben erwähnten Komponenten ausgeführten Systemverklemmung-Detektion beschrieben.

[Beispiel 1 Detektion einer Systemverklemmung zwischen zwei Transaktionen, die beide im "eigenen" Computersystem sind]

Beispiel 1 bezieht sich auf eine Systemverklemmung- Detektion in einem Computersystem in dem Fall, in welchem die beiden "systemverklemmten" Transaktionen beide im Computersystem 1 (dem "eigenen" Computersystem) sind. Im einzelnen werden die folgenden Operationen ausgeführt. Dieses Beispiel zeigt auf, daß eine Übermittlung mit anderen Computersystemen in diesem Fall nicht eingerichtet ist.
(1) Zunächst wird angenommen, daß eine Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 von einer Einleitung der Transaktion benachrichtigt.
(2) Der Transaktionsverwalter (TM) 10 registriert die Transaktion T(1, 1).
(3) Separat wird angenommen, daß eine Transaktion T(1, 2) den Transaktionsverwalter (TM) 10 von einer Einleitung der Transaktion benachrichtigt.
(4) Der Transaktionsverwalter (TM) 10 registriert die Transaktion T(1, 2).
(5) Es wird angenommen, daß die Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 nach der Ressource A fragt.
(6) Der Transaktionsverwalter (TM) 10 erzeugt dann eine Anforderung, um die Ressource A zu gewinnen, an den Ressourcenverwalter (RM) 11.
(7) Der Ressourcenverwalter (RM) 11 erzeugt eine Anforderung, um eine Verriegelung auf der Ressource A zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(8) Der Verriegelungsverwalter (LM) 12 sendet zum Ressourcenverwalter (RM) 11 OK zurück, falls die Ressource A nicht verriegelt ist.
(9) Der Ressourcenverwalter (RM) 11 sendet eine Antwort OK an den Transaktionsverwalter (TM) 10.
(10) Andererseits wird angenommen, daß die Transaktion T(1, 2) den Transaktionsverwalter (TM) 10 nach der Ressource B fragt.
(11) Der Transaktionsverwalter (TM) 10 erzeugt dann eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(12) Der Ressourcenverwalter (RM) 11 erzeugt eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(13) Der Verriegelungsverwalter (LM) 12 sendet zum Ressourcenverwalter (RM) 11 OK zurück, falls die Ressource B nicht verriegelt ist.
(14) Der Ressourcenverwalter (RM) 11 sendet eine Antwort OK an den Transaktionsverwalter (TM) 10.
(15) Zur gleichen Zeit wird angenommen, daß die Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 nach der Ressource B fragt.
(16) Der Transaktionsverwalter (TM) 10 erzeugt dann eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(17) Der Ressourcenverwalter (RM) 11 erzeugt eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(18) Die Ressource B wurde jedoch schon durch die Transaktion T(1, 2) verriegelt, so daß die Transaktion T(1, 1) auf die Transaktion T(1, 2) wartet. Dementsprechend fordert der Verriegelungsverwalter (LM) 12 den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(1, 1) → T(1, 2)
zu registrieren. Der Systemverklemmungsdetektor (DD) 15, der die Anforderung empfängt, registriert den Graph in der Warten-Auf-Graph-Tabelle T3.
(19) Andererseits wird angenommen, daß die Transaktion T(1, 2) den Transaktionsverwalter (TM) 10 nach der Ressource A fragt.
(20) Der Transaktionsverwalter (TM) 10 erzeugt dann eine Anforderung, um die Ressource A zu gewinnen, an den Ressourcenverwalter (RM) 11.
(21) Der Ressourcenverwalter RM (11) macht eine Anforderung, um eine Verriegelung auf der Ressource A zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(22) Die Ressource A wurde jedoch schon durch die Transaktion T(1, 1) verriegelt, so daß die Transaktion T(1, 2) auf die Transaktion T(1, 1) wartet. Dementsprechend fordert der Verriegelungsverwalter (LM) 12 den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(1, 2) → T(1, 1)
zu registrieren. Der die Anforderung empfangende Systemverklemmungsdetektor (DD) 15 registriert den Graph in der Warten-Auf-Graph-Tabelle T3.
(23) Der Systemverklemmungsdetektor (DD) 15 detektiert die Schleife und meldet dem Transaktionsverwalter (TM) 10 das Vorhandensein der Systemverklemmung.

[Beispiel 2 Detektion der Systemverklemmung zwischen zwei Transaktionen in verschiedenen jeweiligen Computersystemen]

Beispiel 2 beinhaltet einen Fall, in dem die Systemverklemmung zwischen zwei Computersystemen (System 1 und System 2) verursacht wird. Dieses Beispiel zeigt auf, daß eine Übermittlung zwischen den Systemen zu Zwecken der Systemverklemmung-Detektion nur einmal vorgenommen wird.
(1) Zunächst wird angenommen, daß eine Transaktion T(1, 1) des Systems 1 den Transaktionsverwalter (TM) 10 des Systems 1 von einer Einleitung der Transaktion benachrichtigt.
(2) Der Transaktionsverwalter (TM) 10 des Systems 1 registriert die Transaktion T(1, 1).
(3) Es wird angenommen, daß die Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 des Systems 1 nach der Ressource A fragt.
(4) Der Transaktionsverwalter (TM) 10 des Systems 1 macht dann eine Anforderung, um die Ressource A zu gewinnen, an den Ressourcenverwalter (RM) 11.
(5) Der Ressourcenverwalter (RM) 11 des Systems 1 macht eine Anforderung, um eine Verriegelung auf der Ressource A zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(6) Der Verriegelungsverwalter (LM) 12 des Systems 1 sendet zum Ressourcenverwalter (RM) 11 OK zurück, falls die Ressource A nicht verriegelt ist.
(7) Der Ressourcenverwalter (RM) 11 des Systems 1 sendet eine Antwort OK an den Transaktionsverwalter (TM) 10.
(1)' Separat wird angenommen, daß eine Transaktion T(2, 1) des Systems 2 den Transaktionsverwalter (TM) 10 des Systems 2 von der Einleitung der Transaktion benachrichtigt.
(2)' Der Transaktionsverwalter (TM) 10 des Systems 2 registriert die Transaktion T(2, 1).
(3)' Es wird angenommen, daß die Transaktion T(2, 1) den Transaktionsverwalter (TM) 10 des Systems 2 nach der Ressource B fragt.
(4)' Der Transaktionsverwalter (TM) 10 des Systems 2 erzeugt eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(5)' Der Ressourcenverwalter (RM) 11 des Systems 2 erzeugt eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(6)' Der Verriegelungsverwalter (LM) 12 des Systems 2 sendet zum Ressourcenverwalter (RM) 11 OK zurück, falls die Ressource B nicht verriegelt ist.
(7)' Der Ressourcenverwalter (RM) 11 des Systems 2 sendet eine Antwort OK an den Transaktionsverwalter (TM) 10.
(8) Zu dieser Zeit wird angenommen, daß die Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 des Systems 1 nach der Ressource B fragt.
(9) Der Transaktionsverwalter (TM) 10 des Systems 1 macht dann eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(10) Der Ressourcenverwalter (RM) 11 des Systems macht eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(11) Die Ressource B wurde jedoch schon durch die Transaktion T(2, 1) des Systems 2 verriegelt, so daß die Transaktion T(1, 1) auf die Transaktion T(2, 1) wartet. Dementspre chend fordert der Verriegelungsverwalter (LM) 12 des Systems 1 den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(1, 1) → T(2, 1)
zu registrieren.
(12) Als Antwort auf diese Anforderung sendet der Systemverklemmungsdetektor (DD) 15 des Systems 1 den Graph
T(1, 1) → T(2, 1)
an das System 2. Zur gleichen Zeit registriert der Systemverklemmungsdetektor (DD) 15 des Systems 1 den Graph in der Warten-Auf-Graph-Tabelle T3 des Systems 1.
(13) Der Systemverklemmungsdetektor (DD) 15 des Systems 2 empfängt den Graph
T(1, 1) → T(2, 1)
und registriert ihn in der Warten-Auf-Graph-Tabelle T3 des Systems 2.
(14) Anschließend wird angenommen, daß eine Transaktion T(2, 1) den Transaktionsverwalter (TM) 10 des Systems 2 nach der Ressource A fragt.
(15) Der Transaktionsverwalter (TM) 10 des Systems 2 macht dann eine Anforderung, um die Ressource A zu gewinnen> an den Ressourcenverwalter (RM) 11.
(16) Der Ressourcenverwalter (RM) 11 des Systems 2 macht eine Anforderung, um die Verriegelung auf der Ressource A zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(17) Die Ressource A wurde jedoch schon durch die Transaktion T(1, 1) des Systems 1 verriegelt, so daß die Transaktion T(2, 1) auf die Transaktion T(1, 1) wartet. Dementsprechend fordert der Verriegelungsverwalter (LM) 12 des Systems 2 den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(2, 1) → T(1, 1)
zu registrieren.
(18) Der Systemverklemmungsdetektor (DD) 15 des Systems 2 detektiert die Schleife und benachrichtigt den Transaktionsverwalter (TM) 10 des Systems 2 vom Vorhandensein der Systemverklemmung.

[Beispiel 3 Eine Nachricht wird während einer Detektion der Systemverklemmung zwischen zwei Transaktionen in verschiedenen jeweiligen Computersystemen verloren]

Beispiel 3 befaßt sich mit einem Fall, in dem eine Nachricht aufgrund eines zwischen zwei Computersystemen (System 1 und System 2) verursachten Übermittlungsfehlers verloren wird.
(1) Zunächst wird angenommen, daß eine Transaktion T(1, 1) des Systems 1 den Transaktionsverwalter (TM) 10 des Systems 1 von einer Einleitung der Transaktion benachrichtigt.
(2) Der Transaktionsverwalter (TM) 10 des Systems 1 registriert die Transaktion T(1, 1).
(3) Es wird angenommen, daß die Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 des Systems 1 nach der Ressource A fragt.
(4) Der Transaktionsverwalter (TM) 10 des Systems 1 macht dann eine Anforderung, die Ressource A zu gewinnen, an den Ressourcenverwalter (RM) 11.
(5) Der Ressourcenverwalter (RM) 11 des Systems 1 macht eine Anforderung, um eine Verriegelung auf der Ressource A zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(6) Der Verriegelungsverwalter (LM) 12 des Systems 1 sendet zum Ressourcenverwalter (RM) 11 OK zurück, falls die Ressource A nicht verriegelt ist.
(7) Der Ressourcenverwalter (RM) 11 des Systems 1 sendet eine Antwort OK an den Transaktionsverwalter (TM) 10.
(1)' Separat wird angenommen, daß eine Transaktion T(2, 1) des Systems 2 den Transaktionsverwalter (TM) 10 des Systems 2 von der Einleitung der Transaktion benachrichtigt.
(2)' Der Transaktionsverwalter (TM) 10 des Systems 2 registriert die Transaktion T(2, 1).
(3)' Es wird angenommen, daß die Transaktion T(2, 1) den Transaktionsverwalter (TM) 10 des Systems 2 nach der Ressource B fragt.
(4)' Der Transaktionsverwalter (TM) 10 des Systems 2 macht eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(5)' Der Ressourcenverwalter (RM) 11 des Systems 2 macht eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(6)' Der Verriegelungsverwalter (LM) 12 des Systems 2 sendet zum Ressourcenverwalter (RM) 11 OK zurück, falls die Ressource B nicht verriegelt ist.
(7)' Der Ressourcenverwalter (RM) 11 des Systems 2 sendet eine Antwort OK an den Transaktionsverwalter (TM) 10.
(8) Zu diesem Zeitpunkt wird angenommen, daß die Transaktion T(1, 1) den Transaktionsverwalter (TM) 10 des Systems 1 nach der Ressource B fragt.
(9) Der Transaktionsverwalter (TM) 10 des Systems 1 macht dann eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(10) Der Ressourcenverwalter (RM) 11 des Systems 1 macht eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(11) Die Ressource B wurde jedoch schon durch die Transaktion T(2, 1) des Systems 2 verriegelt, so daß die Transaktion T(1, 1) auf die Transaktion T(2, 1) wartet. Dementsprechend fordert der Verriegelungsverwalter (LM) 12 des Systems 1 den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(1, 1) → T(2, 1)
zu registrieren.
(12) Als Antwort auf diese Anforderung registriert der Systemverklemmungsdetektor (DD) 15 des Systems 1 den Graph in der Warten-Auf-Graph-Tabelle T3 des Systems 1. Zur gleichen Zeit sendet der Systemverklemmungsdetektor (DD) 15 des Systems 1 den Graph
T(1, 1) → T(2, 1)
an das System 2.
(13) Der übertragene Inhalt kommt jedoch nicht beim System 2 an, weil er als Folge eines Übermittlungsfehlers verloren wird.
(14) Anschließend wird angenommen, daß die Transaktion T(2, 1) den Transaktionsverwalter (TM) 10 des Systems 2 nach der Ressource A fragt.
(15) Der Transaktionsverwalter (TM) 10 des Systems 2 macht dann eine Anforderung, um die Ressource A zu gewinnen, an den Ressourcenverwalter (RM) 11.
(16) Der Ressourcenverwalter (RM) 11 des Systems 2 macht eine Anforderung, um eine Verriegelung auf der Ressource A zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(17) Die Ressource A wurde jedoch schon durch die Transaktion T(1, 1) des Systems 1 verriegelt, so daß die Transaktion T(2, 1) auf die Transaktion T(1, 1) wartet. Dementsprechend fordert der Verriegelungsverwalter (LM) 12 des Systems 2 den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(2, 1) → T(1, 1)
zu registrieren. Zu diesem Zeitpunkt ist die Systemverklemmungssituation tatsächlich herbeigeführt. Diese Systemverklemmung kann jedoch aufgrund des Verlusts der Nachricht nicht direkt detektiert werden. Demgemäß wird die Systemverklemmung fortgesetzt.
(18) Nach einer vorbestimmten Zeit wird der Überwachungszeitgeber (PC) 13 des Systems 1 betätigt, um eine Neuversuch- Meldung zum Systemverklemmungsdetektor (DD) 15 des Systems 1 zu erzeugen.
(19) Der Systemverklemmungsdetektor (DD) 15 des Systems benachrichtigt dann den Transaktionsverwalter (TM) 10 vom Neuversuch einer Transaktion T(1, 1).
(20) Gemäß der Neuversuch-Meldung erzeugt der Transaktionsverwalter (TM) 10 des Systems 1 eine Anforderung, um die Ressource B zu gewinnen, an den Ressourcenverwalter (RM) 11.
(21) Der Ressourcenverwalter (RM) 11 des Systems 1 erzeugt wieder eine Anforderung, um eine Verriegelung auf der Ressource B zu gewinnen, an den Verriegelungsverwalter (LM) 12.
(22) Die Ressource B wurde jedoch schon durch die Transaktion T(2, 1) des Systems 2 verriegelt, so daß die Transaktion T(1, 1) auf die Transaktion T(2, 1) wartet. Demgemäß fordert der Verriegelungsverwalter (LM) 12 des Systems 1 wieder den Systemverklemmungsdetektor (DD) 15 auf, den Graph
T(1, 1) → T(2, 1)
zu registrieren.
(23) Als Antwort auf diese Anforderung registriert der Systemverklemmungsdetektor (DD) 15 des Systems 1 den Graph in der Warten-Auf-Graph-Tabelle T3 des Systems 1. Zur gleichen Zeit sendet der Systemverklemmungsdetektor (DD) 15 des Systems 1 wieder den Graph
T(1, 1) → T(2, 1)
an das System 2.
(24) Der Systemverklemmungsdetektor (DD) 15 des Systems 2 empfängt den Graph
T(1, 1) → T(2, 1)
und registriert ihn in der Warten-Auf-Graph-Tabelle T3 des Systems 2. Folglich kann der Verlust des ursprünglichen Graphen wettgemacht werden.
(25) Der Systemverklemmungsdetektor (DD) 15 des Systems 2 detektiert die Schleife und benachrichtigt den Transaktionsverwalter (TM) 10 des Systems 2 vom Vorhandensein der Systemverklemmung.
Wie oben erwähnt wurde, ist gemäß dieser Ausführungsform der Verriegelungsverwalter (LM) 12 zum Verwalten einer Verriegelungssituation auf einer Ressource durch eine Aufgabe (Transaktion) vom Systemverklemmungsdetektor (DD) 15 getrennt, und sie können in asynchroner Weise zueinander betrieben werden. Wenn eine neue Aufgabe (Transaktion) erzeugt wird, die eine Ressource anfordert, wird demgemäß ermöglicht, daß sie, ohne durch den Systemverklemmungsdetektor (DD) zu gehen, betätigt wird, falls die Verriegelung ohne Warten erhalten werden kann. Dies trägt zum sanften und effektiven Betrieb des Systems bei, was die Verarbeitungsgeschwindigkeit erhöht. Selbst wenn die Verriegelung nicht erhalten werden kann, ist außerdem die Wirkung davon weniger bedeutend, weil die Registrierung der Verriegelungssituation (Graph) und die Detektion der Systemverklemmung asynchron mit Verriegelungsanforderungen vorgenommen werden.
Der Effekt eines Durchführens der Systemverklemmung- Detektion in solch einem System kann daher reduziert werden.
Wenn die vorliegende Erfindung für ein verteiltes System verwendet wird, muß ein System eine Übermittlung mit einem anderen System zum Detektieren einer Systemverklemmung nur einrichten, wenn es mit dem anderen System unter eine Wartebeziehung kommt. Demgemäß wird eine externe Übermittlung durch ein System für eine Systemverklemmung-Detektion nicht eingerichtet, wenn die systemverklemmten Transaktionen auf ihr eigenes System beschränkt sind. Selbst wenn mehr als ein System an der Systemverklemmung beteiligt ist, kann die Systemverklemmung oft mit einer Übermittlung detektiert werden, weil 90% oder mehr der Systemverklemmungen zwischen zwei Systemen verursacht werden. Demgemäß ist es möglich, die Gemeinkosten-Zeit zu reduzieren, die für eine Übermittlung erforderlich ist, die notwendig ist, um die Systemverklemmungen zu detektieren, was einen effektiveren Betrieb des Systems erlaubt.
In einer Ausführungsform, in der eine Wartezeit-Überwachungseinheit (WT) 13 vorgesehen ist, kann außerdem der Überwachungszeitgeber (WT) 13 eine weitere Chance zum Detektieren einer Systemverklemmung bieten, selbst wenn eine Nachricht während einer Übermittlung der Nachricht in dem verteilten System verzögert oder verloren wird. Folglich können Systemverklemmungen sicherer detektiert werden.
Es ist offensichtlich, daß die so beschriebene Erfindung auf viele Arten variiert werden kann. Die vorliegende Erfindung schließt alle derartigen Variationen ein, die in den Umfang der beiliegenden Ansprüche fallen.

Claims

1. Verarbeitungssystem, in welchem eine Mehrzahl von Aufgaben (100; 200) einen Satz gemeinsamer Ressourcen (101; 201; 20) verwendet, mit:

einem Aufgabenverwaltungsmittel (102; 202; 10) zum Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten;

einem Verriegelungsverwaltungsmittel (103; 203; 12) zum Verwalten, welche Ressource durch welche Aufgabe verriegelt wird, und betreibbar, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, um eine Wartebeziehungsangabe zu erzeugen, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet;

einem Registriermittel (105; 205) zum Registrieren solch einer erzeugten Wartebeziehungsangabe; und

einem Systemverklemmung-Detektiermittel (104; 204; 15), das auf der Basis solcher, in dem Registriermittel registrierter Wartebeziehungsangaben betreibbar ist, um eine Systemverklemmungsbedingung zu detektieren, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine Ressource erwartet, die durch eine andere der Aufgaben der Gruppe verriegelt ist, und eine weitere Verarbeitung nicht ausführen kann;

dadurch gekennzeichnet, daß das Systemverklemmung- Detektiermittel betreibbar ist, um eine Systemverklemmung- Detektieroperation zum Detektieren solch einer Systemverklemmungsbedingung unabhängig von dem Aufgabenverwaltungsmittel und dem Verriegelungsverwaltungsmittel durchzuführen, und auch in dem Fall betreibbar ist, daß eine Wartebeziehungsangabe durch das Verarbeitungssystem während solch einer Operation erzeugt wird, um eine Registrierung der Angabe bis zum Abschluß der Operation zurückzuhalten.

2. Verarbeitungssystem zur Verwendung in einem verteilten Multitasking-Gerät, in welchem eine Mehrzahl solcher Verarbeitungssysteme verteilt ist und in welchem eine Mehrzahl von Aufgaben (100; 200) einen Satz gemeinsamer Ressourcen (101; 201, 20) verwendet, welches Verarbeitungssystem umfaßt:

ein Aufgabenverwaltungsmittel (102; 202; 10) zum Verwalten einer Ausführung der Aufgaben, um eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten;

ein Verriegelungsverwaltungsmittel (103; 203; 12) zum Verwalten, welche Ressource durch welche Aufgabe verriegelt wird, und betreibbar, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, um eine Wartebeziehungsangabe zu erzeugen, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet;

ein Übermittlungsmittel (104; 204; 15), das, wenn in dem beanspruchten Verarbeitungssystem die erste Aufgabe gerade durchgeführt wird und die zweite Aufgabe in einem anderen Verarbeitungssystem des Geräts gerade durchgeführt wird, betreibbar ist, um die Wartebeziehungsangabe dem anderen System mitzuteilen;

ein Registriermittel (105; 205) zum Registrieren solcher Wartebeziehungsangaben, die durch das Verriegelungsmittel erzeugt wurden oder von einem anderen Verarbeitungssystem des Geräts empfangen wurden; und

ein Systemverklemmung-Detektiermittel (104; 204; 15), das auf der Basis solcher, in dem Registriermittel registrierter Wartebeziehungsangaben betreibbar ist, um eine Systemverklemmungsbedingung zu detektieren, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine Ressource erwartet, die durch eine andere der Aufgaben der Gruppe verriegelt ist, und eine weitere Verarbeitung nicht ausführen kann;

gekennzeichnet durch ein Wartezeit-Überwachungsmittel (206; 13), das betreibbar ist, um zu detektieren, wenn solch eine registrierte Wartebeziehungsangabe für eine vorbestimmte Zeit fortdauert; und

ein Neuversuch-Meldungsmittel (206; 204; 13; 15), das betreibbar ist, wenn solch eine fortdauernde Wartebeziehungsangabe detektiert wird, um zu veranlassen, daß eine Neuversuch- Meldung auf die Aufgabe angewendet wird, deren Anforderung veranlaßte, daß die fortdauernde Wartebeziehungsangabe erzeugt wurde, welche Meldung dazu dient, der Aufgabe zu mel den, daß sie die Anforderung wieder machen soll, so daß die betreffende Wartebeziehungsangabe dem anderen Verarbeitungssystem wieder mitgeteilt werden kann.

3. System nach Anspruch 1 oder 2, worin das Registriermittel eine Tabelle (105; 205) enthält, in der solch eine erzeugte Wartebeziehungsangabe registriert ist.

4. Verarbeitungssystem nach Anspruch 3, wenn als an Anspruch 1 angefügt gelesen, zur Verwendung in einem verteilten Multitasking-Gerät, in welchem eine Mehrzahl solcher Verarbeitungssysteme verteilt ist, worin, wenn solch eine Wartebeziehungsangabe erzeugt wird, für welche die ersten und zweiten Aufgaben beide durch das beanspruchte Verarbeitungssystem gerade ausgeführt werden, die betreffende Wartebeziehungsangabe exklusiv in der Tabelle des Registriermittels des beanspruchten Verarbeitungssystems registriert wird.

5. Verarbeitungssystem nach Anspruch 3, wenn als an Anspruch 2 angefügt gelesen, worin, wenn solch eine Wartebeziehungsangabe erzeugt wird, für welche die ersten und zweiten Aufgaben beide gerade durch das beanspruchte Verarbeitungssystem ausgeführt werden, die betreffende Wartebeziehungsangabe exklusiv in der Tabelle des Registriermittels des beanspruchten Verarbeitungssystems registriert wird.

6. Verarbeitungssystem nach Anspruch 4 oder 5, worin, wenn solch eine Wartebeziehungsangabe erzeugt ist, für welche die erste Aufgabe durch das beanspruchte Verarbeitungssystem gerade ausgeführt wird und die zweite Aufgabe durch ein anderes der Verarbeitungssysteme des Geräts gerade ausgeführt wird, das beanspruchte Verarbeitungssystem betreibbar ist, um die betreffende Wartebeziehungsangabe dem anderen Verarbeitungssystem für eine Registrierung in der Registriermittel- Tabelle des Systems mitzuteilen, um dadurch zu ermöglichen, daß ein anderes System ein Vorhandensein oder Nichtvorhandensein solch einer Systemverklemmungsbedingung detektiert.

7. Verarbeitungssystem nach Anspruch 4, 5 oder 6, worin, wenn solch eine Wartebeziehungsangabe erzeugt wird, für welche die zweite Aufgabe durch das beanspruchte Verarbeitungssystem gerade ausgeführt wird und die erste Aufgabe durch ein anderes der Verarbeitungssysteme des Geräts gerade ausgeführt wird, das beanspruchte Verarbeitungssystem betreibbar ist, um von dem anderen Verarbeitungssystem die betreffende Wartebe ziehungsangabe zu empfangen und sie in seiner Registriermittel-Tabelle zu registrieren und das Vorhandensein oder Nichtvorhandensein solch einer Systemverklemmungsbedingung mittels Durchsuchen der Tabelle zu detektieren.

8. System nach einem der Ansprüche 3 bis 7, worin das Systemverklemmung-Detektiermittel nach Erzeugung solch einer Wartebeziehungsangabe betreibbar ist, um zu veranlassen, daß die Wartebeziehungsangabe in der Tabelle registriert wird, und das Vorhandensein oder Nichtvorhandensein der Systemverklemmungsbedingung mittels Durchsuchen der Tabelle zu detektieren.

9. System nach einem der Ansprüche 3 bis 8, worin das Verriegelungsverwaltungsmittel veranlaßt, daß die Wartebeziehungsangabe in der Tabelle registriert wird, und eine Systemverklemmung-Detektieranweisung an das Systemverklemmung- Detektiermittel nur ausgibt, wenn die Wartebeziehungsangabe durch eine Ressource-Gewinnen-Anforderung veranlaßt wird, und worin das Verriegelungsverwaltungsmittel eine Ausführung der Aufgabe für eine Ressource-Gewinnen-Anforderung nicht suspendiert, was nicht zur Folge hat, daß eine Wartebeziehungsangabe erzeugt wird.

10. System nach einem der Ansprüche 3 bis 9, worin die Registrierung der Wartebeziehungsangabe aus der Tabelle gelöscht wird, wenn detektiert wird, daß für die betreffende Angabe die erste Aufgabe nicht länger in einer Wartebeziehung mit der zweiten Aufgabe steht.

11. System nach einem der vorhergehenden Ansprüche, worin das Systemverklemmung-Detektiermittel eine Anforderungswarteschlange-Empfangseinheit (14) zum Empfangen einer Anforderung zum Registrieren einer Wartebeziehungsangabe aufweist, die eine Anweisung angibt, um die Systemverklemmungsbedingung zu detektieren.

12. System nach einem der vorhergehenden Ansprüche, worin die Wartebeziehungsangabe angibt, daß die erste Aufgabe auf eine Freigabe der durch die zweite Aufgabe verriegelten Ressource wartet.

13. System nach einem der Ansprüche 1 bis 11, worin die Wartebeziehungsangabe angibt, daß die erste Aufgabe auf eine Beendigung der zweiten Aufgabe wartet, die die durch die erste Aufgabe angeforderte Ressource verriegelt.

14. System nach einem der vorhergehenden Ansprüche, worin das Aufgabenverwaltungsmittel die Aufgaben durch ein Zweiphasen-Verriegelungssystem verwaltet, in welchem die Verriegelung kontinuierlich hergestellt ist, wenn eine bestimmte Verarbeitung beginnt, Daten zu verriegeln, während die Verriegelung kontinuierlich freigegeben ist, wenn sie beginnt, die Verriegelung freizugeben.

15. System nach einem der vorhergehenden Ansprüche, ferner einschließend eine Verriegelungstabelle zum Registrieren einer Beziehung zwischen einer Aufgabe und einer durch die Aufgabe verriegelten Ressource.

16. System nach Anspruch 1, zur Verwendung in einem verteilten Multitasking-Gerät, in welchem eine Mehrzahl solcher Verarbeitungssysteme verteilt ist, ferner mit:

einem Übermittlungsmittel (104; 204; 15), das, wenn die erste Aufgabe in dem beanspruchten Verarbeitungssystem gerade ausgeführt wird und die zweite Aufgabe in einem anderen Verarbeitungssystem des Geräts gerade ausgeführt wird, betreibbar ist, um die Wartebeziehungsangabe dem anderen Verarbeitungssystem mitzuteilen, und das Registriermittel ferner betreibbar ist, um solche Wartebeziehungsangaben zu registrieren, die von solch einem Übermittlungsmittel eines anderen Verarbeitungssystems des Geräts empfangen wurden;

einem Wartezeit-Überwachungsmittel (206; 13), das betreibbar ist, um zu detektieren, wenn solch eine registrierte Wartebeziehungsangabe für eine vorbestimmte Zeit fortdauert; und

einem Neuversuch-Meldung-Mittel (206; 204; 13; 15), das, wenn solch eine fortdauernde Wartebeziehungsangabe detektiert wird, betreibbar ist, um zu veranlassen, daß eine Neuversuch- Meldung auf die Aufgabe angewendet wird, deren Anforderung veranlaßte, daß die fortdauernde Wartebeziehungsangabe erzeugt wurde, welche Meldung dazu dient, der Aufgabe zu melden, daß sie die Anforderung wieder machen soll, so daß die betreffende Wartebeziehungsangabe dem anderen Verarbeitungssystem wieder mitgeteilt werden kann.

17. Verteiltes Multitasking-Gerät, in welchem eine Mehrzahl von Verarbeitungssystemen verteilt ist, jedes ein Verarbeitungssystem nach einem der vorhergehenden Ansprüche seiend.

18. Gerät nach Anspruch 17, worin jedes Verarbeitungssystem ein Verarbeitungssystem nach einem der Ansprüche 3 bis 10 oder einem der Ansprüche 11 bis 16 ist, wenn als an Anspruch 3 angefügt gelesen, und worin, wenn durch ein erstes (SYSTEM i) der Verarbeitungssysteme solch eine Wartebeziehungsangabe erzeugt wird, für welche Angabe die erste Aufgabe durch das erste System (SYSTEM i) gerade ausgeführt wird und die zweite Aufgabe durch ein zweites (SYSTEM j) der Verarbeitungssysteme des Geräts gerade ausgeführt wird, die Wartebeziehungsangabe in der Registriermittel-Tabelle des ersten (SYSTEM i) registriert wird, und für jedes der ersten und zweiten Systeme das Systemverklemmung-Detektiermittel in dem betreffenden System, wenn eine der Aufgaben, die durch das betreffende System (z. B. SYSTEM i) gerade ausgeführt wird, auf eine der Aufgaben wartet, die durch das andere System (SYSTEM j) der ersten und zweiten Systeme gerade ausgeführt wird, betreibbar ist, um mit dem anderen System (SYSTEM j) zu kommunizieren, um zu veranlassen, daß solche, in der Registriermittel-Tabelle des anderen Systems (SYSTEM j) registrierte Wartebeziehungsangaben zu seinem eigenen System übertragen werden, und um das Systemverklemmung-Detektiermittel in seinem eigenen System (SYSTEM i) zu veranlassen, solche übertragenen Angaben von dem anderen System (SYSTEM j) und die in der Registriermittel-Tabelle seines eigenen Systems registrierte Angabe zu verwenden, um dem Systemverklemmung-Detektiermittel zu ermöglichen, das Vorhandensein oder Nichtvorhandensein der Systemverklemmungsbedingung zu bestimmen.

19. Gerät nach Anspruch 17 oder 18, worin eine in einem Verarbeitungssystem i gerade ausgeführte Aufgabe x als T(i, x) definiert ist und eine in einem anderen Verarbeitungssystem j gerade ausgeführte Aufgabe y als T(j, y) definiert ist und in der Registriermittel-Tabelle die Wartebeziehungsangabe, die angibt, daß die Aufgabe T(i, x) auf die Aufgabe T(j, y) wartet, in der Form T(i, x) → T(j, y) registriert ist und die Wartebeziehungsangabe, die angibt, daß die Aufgabe T(j, y) auf die Aufgabe T(i, x) wartet, in der Form T(j, y) → T(i, x) registriert ist, und, wenn diese beiden Wartebeziehungsangaben in der Tabelle registriert sind, eine Schleife T(i, x) → T(j, y) → T(i, x) detektiert wird, woraufhin die Systemverklemmungsbedingung detektiert ist.

20. Verarbeitungsverfahren zur Verwendung in einem Verarbeitungssystem, in welchem eine Mehrzahl von Aufgaben einen Satz gemeinsamer Ressourcen verwendet, mit den Schritten:

Verwalten einer Ausführung der Aufgaben, um so eine parallele Ausführung von zwei oder mehr der Aufgaben zu gestatten;

Verwalten, welche Ressource durch welche Aufgabe verriegelt wird, und, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, Erzeugen einer Wartebeziehungsangabe, die angibt, daß die erste Aufgabe auf die zweite Aufgabe wartet;

Registrieren solch einer erzeugten Wartebeziehungsangabe; und

Detektieren, basierend auf solchen registrierten Wartebeziehungsangaben, einer Systemverklemmungsbedingung, in welcher für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine Ressource erwartet, die durch eine andere der Aufgaben der Gruppe verriegelt ist, und eine weitere Verarbeitung nicht ausführen kann;

dadurch gekennzeichnet, daß eine Systemverklemmungsoperation zum Detektieren solch einer Systemverklemmungsbedingung unabhängig von der Aufgabenverwaltung und Verriegelungsverwaltung durchgeführt wird, und in dem Fall, daß eine Wartebeziehungsangabe während solch einer Operation erzeugt wird, eine Registrierung der Angabe bis zum Abschluß der Operation zurückgehalten wird.

21. Verarbeitungsverfahren zur Verwendung in einem verteilten Multitasking-Gerät, in welchem eine Mehrzahl von Verarbeitungssystemen verteilt ist und in welchem eine Mehrzahl von Aufgaben einen Satz gemeinsamer Ressourcen verwendet, welches Verarbeitungsverfahren die Schritte umfaßt:

Verwalten, welche Ressource durch welche Aufgabe verriegelt ist, und, wenn eine erste der Aufgaben eine Anforderung für eine Ressource macht, die durch eine zweite der Aufgaben schon verriegelt ist, Erzeugen einer Wartebeziehungsangabe, die angibt, daß die erste Auf gabe auf die zweite Aufgabe wartet;

wenn die erste Aufgabe in einem ersten der Verarbeitungssysteme gerade durchgeführt wird und die zweite Aufgabe in einem zweiten der Verarbeitungssysteme des Geräts gerade ausgeführt wird, Übermitteln der Wartebeziehungsangabe von dem ersten zu dem zweiten Verarbeitungssystem;

Registrieren solcher Wartebeziehungsangaben, die erzeugt oder von einem anderen Verarbeitungssystem des Geräts empfangen wurden; und

Detektieren, auf der Grundlage solcher registrierter Wartebeziehungsangaben, einer Systemverklemmungsbedingung, in der für eine Gruppe von Aufgaben, die aus mindestens zwei Aufgaben der Mehrzahl besteht, jede Aufgabe der Gruppe solch eine Ressource erwartet, die durch eine andere der Aufgaben der Gruppe verriegelt ist, und eine weitere Verarbeitung nicht ausführen kann;

gekennzeichnet durch Detektieren, im ersten Verarbeitungssystem, wenn solch eine registrierte Wartebeziehungsangabe für eine vorbestimmte Zeit fortdauert, und, wenn solch eine fortdauernde Wartebeziehungsangabe detektiert wird, Anwenden einer Neuversuch-Meldung auf die Aufgabe, deren Anforderung bewirkte, daß die fortdauernde Wartebeziehungsangabe erzeugt wurde, welche Meldung dazu dient, der Aufgabe zu melden, daß sie die Anforderung wieder machen soll, so daß die betreffende Wartebeziehungsangabe dem zweiten Verarbeitungssystem wieder mitgeteilt werden kann.