DE69511796T2

DE69511796T2 - Progressives Wiederholungsverfahren und Vorrichtung mit wiederverwendbaren Softwaremodulen zur Softwareausfallbeseitigung in Nachrichten übertragenden Multiprozessanwendungen

Info

Publication number: DE69511796T2
Application number: DE69511796T
Authority: DE
Inventors: Wesley Kent Fuchs; Yennun Huang; Chandra Mohan Kintala; Yi-Min Wang
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1994-06-22
Filing date: 1995-06-14
Publication date: 2000-04-20
Anticipated expiration: 2015-06-15
Also published as: DE69511796D1; CA2150059A1; EP0691610B1; US5440726A; EP0691610A1; JP3290052B2; CA2150059C; JPH0830476A

Description

Technisches Gebiet

Die vorliegende Erfindung betrifft ein System zum Umgehen von Softwarefehlern in Anwendungen, bei denen Nachrichten weitergeleitet werden, und insbesondere ein Verfahren und eine Vorrichtung zum Umgehen von Softwarefehlern auf der Grundlage eines progressiven Wiederholungsversuchsverfahrens, das den Umfang der Wiederherstellung allmählich vergrößert, bis der Softwarefehler umgangen ist.

Allgemeiner Stand der Technik

Die Benutzer von Softwareanwendungen verlangen zunehmend, daß die Software fehlertolerant ist. Insbesondere achten Benutzer auf zwei Komponenten der Fehlertoleranz: Verfügbarkeit und Datenkonsequenz der Anwendung. Zum Beispiel verlangen Benutzer von Telekommunikationsvermittlungssystemen, daß die Vermittlungssysteme fortwährend verfügbar sind. Bei Übertragungen, bei denen finanzielle Transaktionen beteiligt sind, wie zum Beispiel für Geldautomaten von Banken, verlangen Kunden jedoch auch den höchsten Grad der Datenkonsequenz.
Aufgrund der komplexen und temporalen Beschaffenheit der Verschachtelung von Nachrichten und Berechnungen in einem verteilten System, das eine Mehrzahl gleichzeitig laufender Prozesse ausführt, wird jedoch kein Ausmaß der Verifizierung, Validierung und Prüfung während dem Debugging der Software alle Softwarefehler erkennen und beseitigen und völlige Gewißheit der Verfügbarkeit und Datenkonsequenz dieser Anwendung ergeben. Dementsprechend haben sich Restfehler aufgrund von ungeprüften Grenzbedingungen, nicht, erwarteten Ausnahmen und unerwarteten Ausführungsumgebungen schon als sich dem Prüf- und Debug-Prozeß entziehend gezeigt und manifestieren sich bei einer Auslösung während der Programmausführung und verursachen einen Absturz oder ein Hängen des Anwendungsprozesses, wodurch Dienstunterbrechungen verursacht werden.
Es ist deshalb wünschenswert, über effektive Online-Wiederholungsversuchsmechanismen zur automatischen Erkennung und Umgehung solcher Softwarefehler zu verfügen, um eine Wiederherstellung nach Soff twareausfällen zu ermöglichen. Mehrere Untersuchungen haben gezeigt, daß viele Softwarefehler in Produktionssystemen ein transientes Verhalten aufweisen. Dementsprechend besteht die einfachste Möglichkeit zur Wiederherstellung nach solchen Ausfällen in dem Neustart des Anwendungsprozesses und dadurch in der Ausführung desselben Prozesses unter verschiedenen Bedingungen. Dieser Ansatz wird oft als Umgebungs-Diversity bezeichnet. Der Neustart eines Systems umfaßt jedoch oft eine umfassende Initialisierungsprozedur und kann somit eine potentiell beträchtliche Dienstunterbrechung erfordern.
Um somit die verlorene Zeit während des Neustarts eines Systems zu minimieren, wurden zahlreiche Fixpunkt- und Wiederholungs-Wiederherstellungsverfahren zur effizienteren Wiederherstellung nach transienten Hardwareausfällen vorgeschlagen. Für eine allgemeine Besprechung von Fixpunkt- und Wiederholungs- Wiederherstellungsverfahren siehe R. Koo und S. Toueg, "Checkpointing and Rollback-Recovery for Distributed Systems", IEEE Trans. Software Eng., Band SE-13, Nr. 1, S. 23-31 (Jan. 1987). Im allgemeinen ist ein Fixpunkt eine periodische Sicherungskopie von Daten, die einem Anwendungsprozeß zugeordnet sind, wodurch der Anwendungsprozeß von dem Fixpunkt aus neu gestartet werden kann, der in einem Sicherungsspeichergerät gespeichert wurde.
Es wurden jedoch nur wenige oder überhaupt keine Fixpunkt- und Wiederholungs-Wiederherstellungsverfahren zur Wiederherstellung nach transienten Softwareausfällen vorgeschlagen. Es wird vorgebracht, daß die bereits für Wiederherstellung nach transienten Hardwareausfällen entwickelten Wiederholungsverfahren auch zur Wiederherstellung nach Softwarefehlern eingesetzt werden können, indem Nachrichtenwiederholung und Nachrichtenumordnung zur Umgehung von Softwarefehlern ausgenutzt werden.
Aus der obigen Besprechung ist klar, daß ein progressives Wiederholungsversuchssystem zum Umgehen von transienten Softwarefehlern benötigt wird, das den Umfang der Wiederholung minimiert, darunter die Anzahl von bei der Wiederholung beteiligten Prozessen und die Gesamt-Wiederholungsdistanz, zur Erzielung einer schnelleren Wiederherstellung. Weiterhin wird ein Wiederherstellungssystem benötigt, das die Wiederholungsdistanz und die Anzahl betroffener Prozesse progressiv vergrößert, wenn ein vorheriger Wiederholungsversuch erfolglos ist, um den Grad der Unbestimmtheit bei jedem Wiederholungsversuchsschritt allmählich zu vergrößern.

Kurze Darstellung der Erfindung

Allgemein wird gemäß einem Aspekt der Erfindung ein fehlertolerantes Rechensystem bereitgestellt, um eine Mehrzahl gleichzeitiger Anwendungsprozesse zu überwachen, die mittels eines Nachrichten- Weiterleitungsmechanismus kommunizieren. Das fehlertolerante Rechensystem erkennt Fehler in einem Anwendungsprozeß, die einen Absturz oder ein Hängen des Anwendungsprozesses verursachen. Danach leitet das fehlertolerante Rechensystem eine Wiederherstellung des Anwendungsprozesses durch einen progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus ein, der den Umfang der Wiederherstellung allmählich vergrößert, wenn ein vorheriger Wiederholungsversuchsschritt bei der Umgehung des erkannten Fehlers erfolglos bleibt.
Gemäß einem weiteren Aspekt der Erfindung enthält das fehlertolerante Rechensystem mindestens eine Überwachungsvorrichtung zur Überwachung von Anwendungsprozessen. Zusätzlich enthält die Überwachungsvorrichtung ein Neustart-Teilsystem zur Ausführung von Wiederherstellungsalgorithmen, das versucht, erkannte Fehler zu umgehen.
Gemäß einem Merkmal der Erfindung kann ein Anwendungsprozeß fehlertolerant gemacht werden, indem geeignete Funktionen aus einer fehlertoleranten Bibliothek in den Code für den Anwendungsprozeß eingeführt werden. Vorzugsweise enthält die fehlertolerante Bibliothek eine Herzschlag-Funktion, die eine Herzschlagnachricht in spezifizierten Intervallen zu der Überwachungsvorrichtung sendet, die anzeigt, daß der zugeordnete Prozeß immer noch aktiv ist. Wenn die Überwachungsvorrichtung vor dem Ende des spezifizierten Intervalls kein weiteres Signal aus dem Anwendungsprozeß empfängt, dann nimmt die Überwachungsvorrichtung an, daß der Anwendungsprozeß hängt oder abgestürzt ist.
Zusätzlich enthält die fehlertolerante Bibliothek eine speicherkritische Funktion, die eine Angabe der kritischen Daten in einem Anwendungsprozeß ermöglicht. Zusätzlich wird eine Fixpunkt-Funktion in der fehlertolerante Bibliothek bereitgestellt, die jedesmal, wenn die Fixpunkt-Funktion für den Anwendungsprozeß ausgeführt wird, die angegebenen kritischen Daten in einen Bereich von nichtflüchtigem Speicher kopiert. Die fehlertolerante Bibliothek enthält vorzugsweise außerdem eine Wiederherstellungs-Funktion, die es einem Anwendungsprozeß ermöglicht, die Fixpunkt- Daten aus dem nichtflüchtigen Speicher während einer Wiederherstellungsbetriebsart wiederherzustellen.
Die fehlertolerante Bibliothek enthält vorzugsweise außerdem eine fehlertolerante Schreibfunktion ftwrite, die jede ausgegebene Nachricht in einer Sender-Protokolldatei protokolliert, bevor die Nachricht durch den Anwendungsprozeß übertragen wird. Wenn sich ein Anwendungsprozeß in einer normalen Betriebsart befindet, dann sendet die Funktion ftwrite Nachrichten zu anderen Prozessen und fügt die Informationen für jede gesendete Nachricht in die Sender-Protokolldatei ein.
In einem Wiederherstellungszustand vergleicht die Funktion ftwrite nachdem eine protokollierte Nachricht verarbeitet ist jede frisch erzeugte Nachricht mit der entsprechenden Nachricht in der Sender-Protokolldatei, um die Annahme der stückweisen Bestimmtheit zu überprüfen. Wenn die während der Wiederherstellung erzeugte Nachricht mit der in der Sender-Protokolldatei während der vorherigen Ausführung gespeicherten Nachricht identisch ist, dann muß die Nachricht nicht wiederholt werden. Wenn die Nachrichten jedoch nicht identisch sind, dann ist ein nichtdeterministisches Ereignis eingetreten, und der Umfang der Wiederherstellung muß vergrößert werden.
Die fehlertolerante Bibliothek enthält vorzugsweise außerdem eine fehlertolerante Lesefunktion ftread, die Eingangsnachrichten in einer Empfänger- Protokolldatei protokolliert, bevor sie durch den empfangenden Anwendungsprozeß verarbeitet werden. Wenn sich ein Anwendungsprozeß in einer normalen Betriebsart befindet, dann liest die Funktion ftread Daten aus einem Kommunikationskanal und protokolliert die empfangene Nachricht in der Empfänger-Protokolldatei.
In einem Wiederherstellungszustand werden die Eingangsdaten aus der Empfänger-Protokolldatei bis zu der Wiederherstellungslinie gelesen, bevor jegliche Daten aus einem normalen Eingangskanal gelesen werden können. Bei einer bevorzugten Ausführungsform prüft die Funktion ftread die Fixpunkt-Intervallzahl des Senders, die jeder empfangenen Nachricht zugeordnet ist, und leitet einen Fixpunkt des zugeordneten empfangenden Anwendungsprozesses ein, wenn die Fixpunkt- Intervallzahl des Senders größer als die aktuelle Fixpunkt-Intervallzahl des Empfängers ist, wodurch global konsequente Fixpunkte sichergestellt werden. Zusätzlich leitet die Funktion ftread, wenn sie eine Fixpunkt-Steuernachricht empfängt, in einem koordinierten Fixpunkt-Schema einen Fixpunkt des Anwendungsprozesses ein.
Das Protokollieren von durch jeden Anwendungsprozeß empfangenen Nachrichten in dem Nachrichtenprotokoll plaziert effektiv einen "logischen" Fixpunkt am Ende des folgenden Zustandsintervalls, was zur Mini mierung des Dominoeffekts der Wiederholungsfortpflanzung dient, die tendenziell weitere Prozesse an der Wiederherstellung beteiligen würde.
Gemäß einem weiteren Merkmal der Erfindung wird ein Wiederholungsfortpflanzungsalgorithmus bereitgestellt, der den Umfang der Wiederherstellung minimiert, indem die Wiederherstellungslinie am letzten konsequenten aktuellen oder logischen Fixpunkt für jeden der besagten überwachten Prozesse berechnet wird, der noch nicht verworfen wurde.
Gemäß einem weiteren Merkmal der Erfindung werden Nachrichten in den Nachrichtenprotokollen während einer Wiederherstellungsbetriebsart auf die folgende Weise klassifiziert: Nachrichten, die durch den zugeordneten Prozeß zwischen seinem letzten aktuellen Fixpunkt und der berechneten Wiederherstellungslinie empfangen und verarbeitet wurden, werden als deterministische Nachrichten klassifiziert, und Nachrichten in den Nachrichtenprotokollen, die vor der berechneten Wiederherstellungslinie gesendet und nach der Wiederherstellungslinie empfangen wurden, werden als im Übergang befindliche Nachrichten klassifiziert. Alle anderen Nachrichten in dem Nachrichtenprotokoll werden während einer Wiederherstellungsbetriebsart verworfen.
Gemäß noch einem Merkmal der Erfindung wird ein progressiver Wiederholungsversuchsalgorithmus, der Prinzipien der vorliegenden Erfindung realisiert, nach der Erkennung eines Fehlers in einem Anwendungsprozeß ausgeführt, um zu versuchen, den fehlerhaften Prozeß wiederherzustellen. Der progressive Wiederholungsversuchsalgorithmus minimiert den Umfang der Wiederherstellung, darunter die Anzahl von Prozessen, die bei der Wiederherstellung beteiligt sind, und die Gesamt-Wiederholungsdistanz. Der progressive Wiederholungsversuchsalgorithmus schreitet nur dann zu einem nachfolgenden Schritt fort, wenn der vorherige Schritt bei der Umgehung des erkannten Fehlers erfolglos blieb. Der progressive Wiederholungsversuchsalgorithmus umfaßt die folgenden Schritte: Empfänger-Neuwiedergabe, Empfänger-Umordnung, Sender-Neuwiedergabe, Sender- Umordnung und Wiederholung mit großem Umfang bis zu einem global konsequenten Fixpunkt.
Die in den angefügten Ansprüchen definierte Erfindung sowie weitere Merkmale und Vorteile der Erfindung werden durch Bezugnahme auf die ausführliche Beschreibung und die Zeichnungen besser verständlich.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Blockschema eines fehlertoleranten Rechensystems gemäß der vorliegenden Erfindung;
Fig. 2a und 2b zeigen einen Kommunikationsgraph sowie eigentliche Fixpunkte und logische Fixpunkte;
Fig. 3 zeigt einen Kommunikationsgraph sowie eine Neustart- und Wiederherstellungslinie und die Klassifizierung von Nachrichten;
Fig. 4a zeigt eine Fehlertoleranz-Prozeßliste, die aktuelle Informationen für jeden überwachten Anwendungsprozeß führt, der in dem fehlertoleranten Rechensystem von Fig. 1 abläuft;
Fig. 4b zeigt eine Knotenliste, die eine Liste jedes der Verarbeitungsknoten führt, die gerade in einer Mehrfachknotenumgebung des fehlertoleranten Rechensystems von Fig. 1 aktiv sind;
Fig. 5a und 5b zeigen eine Empfänger- bzw. Sender-Protokolldatei, die Informationen über jede durch einen zugeordneten Anwendungsprozeß empfangene bzw. gesendete Nachricht führt;
Fig. 6a bis 6f zeigen ein Kommunikationsmuster für eine Mehrzahl gleichzeitiger Anwendungsprozesse und wie die Prozesse durch die verschiedenen Schritte des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus von Fig. 7 beeinflußt werden;
Fig. 7 ist ein Flußdiagramm eines beispielhaften progressiven Wiederholungsversuchs-Wiederher stellungsalgorithmus, der durch das Neustart-Teilsystem bei der Wiederherstellung nach einem erkannten Fehler eingesetzt wird;
Fig. 8 ist ein Flußdiagramm einer beispielhaften Empfänger-Neuwiedergabe-Subroutine, die während Schritt 1 des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus von Fig. 7 eingesetzt wird;
Fig. 9 ist ein Flußdiagramm einer beispielhaften Empfänger-Umordnungs-Subroutine 900, die während Schritt 2 des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus von Fig. 7 eingesetzt wird;
Fig. 10 ist ein Flußdiagramm einer beispielhaften Sender-Neuwiedergabe-Subroutine, die während Schritt 3 des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus von Fig. 7 eingesetzt wird;
Fig. 11 ist ein Flußdiagramm einer beispielhaften Sender-Umordnungs-Subroutine, die während Schritt 4 des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus von Fig. 7 eingesetzt wird;
Fig. 12 ist ein Flußdiagramm einer beispielhaften Großumfangs-Wiederholungs-Wiederversuchs- Subroutine, die während Schritt S des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus von Fig. 7 eingesetzt wird;
Fig. 13 ist ein Flußdiagramm einer beispielhaften Prozeß-Nachrichtenprotokoll-Subroutine, die während der Schritte 2 bis 5 des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus von Fig. 7 eingesetzt wird;
Fig. 14a und 14b zeigen zusammen ein Flußdiagramm einer beispielhaften deterministischen Wiedergabe-Subroutine, die durch die Prozeß- Nachrichtenprotokoll-Subroutine von Fig. 13 während der Wiederherstellung eingesetzt wird, um die Nachrichten in den Nachrichtenprotokollen von Fig. 5a und 5b deterministisch neu wiederzugeben; und
Fig. 15a und 15b zeigen zusammen ein Flußdiagramm eines beispielhaften Wiederherstellungslinienberechnungsalgorithmus, der durch den zentralen Wiederherstellungskoordinator bei der Berechnung einer neuen Wiederherstellungslinie für verschiedene Schritte des progressiven Wiederholungsversuchs-Wiederherstel - lungsalgorithmus von Fig. 7 eingesetzt wird.

Ausführliche Beschreibung

Fig. 1 zeigt ein fehlertolerantes Rechensystem 5 gemäß der vorliegenden Erfindung. Im folgenden wird besprochen, daß das fehlertolerante Rechensystem 5 Einrichtungen zur Überwachung einer Mehrzahl gleichzeitiger Anwendungsprozesse bereitstellt, die mittels eines Nachrichten-Weiterleitungsmechanismus kommunizieren. Das fehlertolerante Rechensystem 5 erkennt Fehler in einem Anwendungsprozeß, die einen Absturz oder ein Hängen des Anwendungsprozesses verursachen. Danach leitet das fehlertolerante Rechensystem 5 eine Wiederherstellung des Anwendungsprozesses ein. Gemäß einem Merkmal der Erfindung wird ein progressiver Wiederholungsversuchs-Wiederherstellungsalgorithmus eingesetzt, der den Umfang der Wiederherstellung allmählich vergrößert, wenn ein vorheriger Wiederholungsversuchsschritt erfolglos bleibt.
Das fehlertolerante Rechensystem 5 kann in einer Umgebung, die aus einem einzelnen Knoten besteht, der eine Mehrzahl von Prozessen ausführt, oder als Alternative in einer Umgebung, die aus einer Mehrzahl verbundener Knoten besteht, die jeweils einen oder mehrere Prozesse ausführen (siehe Fig. 1) implementiert werden. Es ist zu bemerken, daß die natürliche Redundanz einer Umgebung mit mehreren Knoten einen verbesserten Mechanismus zur Erkennung von und Wiederherstellung nach Ausfällen der Hardware oder des Betriebssystems eines gegebenen Knotens liefert, was nachfolgend in einem Abschnitt mit dem Titel Betrieb mit mehreren Knoten besprochen wird. Wenn somit ein fehlertoleranter Prozeß auf einem Knoten auf die nachfolgend beschriebene Weise auf einem anderen Knoten neu gestartet werden kann, dann toleriert der Prozeß Fehler der Hardware und des Betriebssystems auf dem ersten Knoten.

Systemarchitektur

Wie in Fig. 1 gezeigt, enthält eine bevorzugte Ausführungsform des hier beschriebenen fehlertoleranten Rechensystems 5 eine Mehrzahl von Verarbeitungsknoten, wie zum Beispiel die Knoten 10 und 12. Als Alternative kann das fehlertolerante Rechensystem 5 aus einem einzigen Knoten mit einer einzelnen Verarbeitungseinheit bestehen, die in der Lage ist, eine Mehrzahl gleichzeitiger Prozesse durch Implementierung eines Zeitwechselmechanismus auf eine bekannte Weise auszuführen.
Jeder Knoten, wie zum Beispiel die Knoten 10 und 12, können als eine Workstation oder als ein anderes Vielzweckrechengerät ausgeführt werden, das aus mindestens einer Verarbeitungseinheit, wie zum Beispiel den Verarbeitungseinheiten 50, 52 und 54, und einer Speichereinheit, wie zum Beispiel den Speichereinheiten 55 und 57, besteht. Als Alternative können einer oder mehrere der Verarbeitungsknoten, wie zum Beispiel die Knoten 10 und 12, als ein festzugeordneter programmgesteuerter Prozessor, wie zum Beispiel als eine Telekommunikationsvermittlung, ausgeführt werden.
In einer Ausführungsform sind einer oder mehrere Knoten in dem fehlertoleranten Rechensystem 5, wie zum Beispiel der Knoten 10, als parallele Verarbeitungseinheiten, zum Beispiel als eine Parallelverarbeitungs-Workstation mit der Fähigkeit zur Ausführung einer Mehrzahl gleichzeitiger Prozesse ausgeführt. Jede der Verarbeitungseinheiten 50, 52, 54 führt einen gleichzeitigen Prozeß, wie zum Beispiel die Prozesse P&sub0; bis PN und PA, aus.
Wenn ein Knoten, zum Beispiel der Knoten 10, eine Mehrzahl von Prozessoren, zum Beispiel die Prozessoren 50 und 52, enthält, dann kann jeder Prozessor über seine eigene festzugeordnete Speichereinheit verfügen oder eine gemeinsam benutzte Speichereinheit 55 mit anderen Prozessoren in demselben Knoten 10 teilen (siehe Fig. 1). Die Speichereinheit 55 jedes Knotens, wie zum Beispiel der Knoten 10 und 12, enthält typischerweise Bereiche von flüchtigem Speicher 40, 42 und nichtflüchtigem Speicher 44, 46. Bei einer bevorzugten Ausführungsform verfügt jeder Prozeß über separat zugeteilte Bereiche von flüchtigem und nichtflüchtigem Speicher in der Speichereinheit 55, wie zum Beispiel die Speicherbereiche 40 und 44 für den Prozeß P&sub0; (siehe Fig. 1). Bekanntlich ist flüchtiger Speicher ein Bereich von unstabilem Speicher, der nicht in der Lage ist, ohne fortwährende Stromversorgung Informationen zu halten.
Der flüchtige Speicherbereich 40, der jedem Prozeß zugeordnet ist, enthält vorzugsweise einen Abschnitt 80 zur Speicherung des Softwarecodes, der dem jeweiligen Anwendungsprozeß zugeordnet ist. Der Codeabschnitt 80, der einem gegebenen Anwendungsprozeß zugeordnet ist, enthält typischerweise Anwendungscode 81 und fehlertolerante Bibliotheksfunktionen 82, die durch den Anwendungscode aufgerufen werden. Die Fehlertoleranz-Bibliotheksfunktionen 82, die nachfolgend in einem Abschnitt mit dem Titel Fehlertoleranz- Bibliotheksfunktionen besprochen werden, sind Bibliotheksfunktionen auf Benutzerebene, die in einer hohen Programmiersprache, wie zum Beispiel der Programmiersprache C, geschrieben sind. Die Fehlertoleranz-Bibliotheksfunktionen 82 können in einem Anwendungsprozeß verwendet werden, um in dem Prozeß gemäß einem Merkmal der vorliegenden Erfindung Fehlertoleranz zu implementieren. Bei einer bevorzugten Ausführungsform wird der Anwendungscode, der Routinen aus der fehlertoleranten Bibliothek 82 aufruft, während des Compilierens mit den aufgerufenen Funktionen zusammengebunden.
Zusätzlich enthält der jedem Prozeß zugeordnete flüchtige Speicherbereich 40 einen Datenabschnitt 84 zur Speicherung der Daten, die dem entsprechenden Anwendungsprozeß zugeordnet sind. Bei einer nachfolgend besprochenen bevorzugten Ausführungsform enthält die fehlertolerante Bibliothek 82 eine speicherkritische Funktion, durch die ein Benutzer angeben kann, daß bestimmte Daten, die einem Anwendungsprozeß zugeordnet sind, kritische Daten sind, die vorzugsweise durch das fehlertolerante Rechensystem 5 in einem Bereich des kritischen Speichers 85 gespeichert werden. Daten in dem Anwendungsprozeß, die der Benutzer nicht als kritische Daten angibt, werden in einem Bereich des nichtkritischen Speichers 86 gespeichert.
Gemäß einem Merkmal der Erfindung, das nachfolgend besprochen wird, enthält die fehlertolerante Bibliothek 82 eine Fixpunkt-Funktion, die, wenn sie durch einen Anwendungsprozeß aufgerufen wird, eine Kopie der durch den Benutzer angegebenen kritischen Daten 85 aus dem flüchtigen Speicher 40 in einem Bereich 88 des nichtflüchtigen Speichers 44 speichert, bei dem es sich um ein stabiles Speichergerät handelt, das Informationen auch bei Abwesenheit der Stromversorgung halten kann. Der nichtflüchtige Speicher 44 kann ein Teil der Speichereinheit 55 oder eines abgesetzten Dateisystems sein. In einer Mehrfachknotenumgebung wird die Kopie des kritischen Speichers 88 vorzugsweise zusätzlich zu dem primären Knoten auf die nachfolgend besprochene Weise auf Sicherungsknoten gespeichert.
Gemäß einem weiteren Merkmal der Erfindung wird durch das fehlertolerante Rechensystem 5 ein Nachrichtenprotokoll geführt, um Informationen über Nachrichten zu speichern, die durch jeden Prozeß gesendet und empfangen werden, wie zum Beispiel eine Kopie der Inhalte aller Nachrichten und Informationen über die Reihenfolge, in der jede Nachricht durch den Anwendungsprozeß verarbeitet wurde. Bei einer bevorzugten Ausführungsform werden, wie nachfolgend in Verbindung mit Fig. 5a bzw. 5b besprochen wird, eine Empfänger- Protokolldatei 90 und eine Sender-Protokolldatei 92 separat für jeden Prozeß geführt, um Informationen über Nachrichten zu speichern, die durch den zugeordneten Prozeß empfangen bzw. gesendet werden.
Bei einer bevorzugten Ausführungsform sendet der zentrale Wiederherstellungskoordinator 75 bei jedem erfolgreichen global konsequenten Fixpunkt eine Nachricht an alle Prozesse, die jeden Prozeß auffordert, eine neue Empfänger- und Sender-Protokolldatei 90, 92 zu öffnen. Auf diese Weise speichern die aktuellen Empfänger- und Sender-Protokolldateien 90, 92 für jeden Anwendungsprozeß nur Informationen über die Nachrichten, die durch den zugeordneten Anwendungsprozeß seit dem letzten global konsequenten Fixpunkt empfangen wurden.
Dementsprechend kann, wie nachfolgend besprochen wird, bei der Erkennung eines Fehlers in einem Anwendungsprozeß eine protokollgestützte Wiederherstellung mit der vorliegenden Erfindung implementiert werden, indem der fehlerhafte Prozeß von dem letzten in der kritischen Speicherkopie 88 gespeicherten Fixpunkt aus neu gestartet wird, und dann Nachrichten aus den Nachrichtenprotokollen 90, 92, die seit dem letzten Fixpunkt gesendet oder empfangen wurden, neu wiedergegeben werden, um den Prozeßzustand bis zu dem Punkt, an dem der Fehler erkannt wurde, zu rekonstruieren.
Die Verarbeitungseinheiten 50, 52 und die Speichereinheit 55 eines einzelnen Knotens, wie zum Beispiel des Knotens 10, werden durch einen Bus 60 oder Prozeßkommunikationseinrichtungen (IPC-Einrtchtungen, IPC - Inter Process Communication) auf dem lokalen Knoten für die Kommunikation im Knoten auf bekannte Weise verbunden. Zusätzlich kann über das Kommunikationsnetz 65 und die Datenstrecken 67-71 auf wohlbekannte Weise für die Kommunikation zwischen Knoten jeder Knoten 10, 12 mit anderen Knoten und einem zentralen Wiederherstellungskoordinator 75, der nachfolgend besprochen wird, verbunden werden.
Wie in Fig. 1 gezeigt enthält jeder Knoten, wie zum Beispiel der Knoten 10, eine Überwachungsvorrichtung 15, die einen Fehlererkennungsüberwacher 20 zur Überwachung von Prozessen enthält, die auf dem entsprechenden Knoten ablaufen. Die Überwachungsvorrichtung 15 führt eine Fehlertoleranz-Prozeßliste 25, die nachfolgend in Verbindung mit Fig. 4a weiter besprochen wird und diejenigen Prozesse auflistet, die auf dem entsprechenden Knoten 10 ablaufen, der durch die Überwachungsvorrichtung 15 überwacht werden sollte.
Der Fehlererkennungsüberwacher 20 der Überwachungsvorrichtung 15 überwacht fortwährend jeden in der Fehlertoleranz-Prozeßliste 25 aufgelisteten Anwendungsprozeß, wie zum Beispiel den Prozeß P&sub0;, um zu bestimmen, ob der Prozeß hängt oder abgestürzt ist. Die durch den Fehlererkennungsüberwacher 20 durchgeführte Überwachung kann entweder aktiv oder passiv sein. Bei einer aktiven Überwachungsanordnung kann die Überwachungsvorrichtung 15 jeden überwachten Anwendungsprozeß abfragen, um seinen Zustand zu bestimmen, indem periodisch unter Verwendung der IPC-Einrichtungen auf dem lokalen Knoten 10 eine Nachricht zu dem Prozeß gesendet und der Rückgabewert bewertet wird, um zu bestimmen, ob dieser Prozeß immer noch aktiv ist.
Bei einer passiven Überwachungsanordnung enthält jeder Anwendungsprozeß eine Funktion aus der fehlertoleranten Bibliothek 82, die nachfolgend besprochen wird und in vorgegebenen Intervallen eine Herzschlagnachricht zu der Überwachungsvorrichtung 15 sendet, die anzeigt, daß der zugeordnete Prozeß immer noch aktiv ist. Wenn die Überwachungsvorrichtung 15 vor dem Ende des vorgegebenen Intervalls kein weiteres Signal von dem Anwendungsprozeß empfängt, dann nimmt die Überwachungsvorrichtung 15 an, daß der Anwendungsprozeß hängt oder abgestürzt ist.
Die Überwachungsvorrichtung 15 enthält außerdem ein Neustart-Teilsystem 30 zur Ausführung des progres siven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 gemäß der vorliegenden Erfindung, der nachfolgend in Verbindung mit Fig. 7 bis 14 besprochen wird. Nachfolgend wird weiter besprochen, daß das Neustart-Teilsystem 30 bei Erkennung eines Fehlers in einem Anwendungsprozeß durch den Fehlererkennungsüberwacher 20 versucht, den fehlerhaften Anwendungsprozeß auf die nachfolgend beschriebene Weise durch Einleiten eines Neustarts des fehlerhaften Anwendungsprozesses an seinem letzten Fixpunkt wiederherzustellen, und dann die in der Empfänger- und der Sender-Protokolldatei 90, 92 protokollierten Nachrichten seit dem letzten Fixpunkt neu zu verarbeiten, um den fehlerhaften Anwendungsprozeß bis zu dem Zustand zu führen, in dem der Absturz erkannt wurde.
Der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700, der Fixpunktoperationen, Wiederholung, Nachrichtenneuwiedergabe und Nachrichtenumordnung einsetzt, minimiert gemäß einem Merkmal der Erfindung die Anzahl von Prozessen, die bei einer Wiederherstellung beteiligt sind, sowie die Gesamt-Wiederholungsdistanz. Der progressive Wiederholungsversuchs-Wiederherstellungsalgorichmus 700 besteht, wie nachfolgend in Verbindung mit Fig. 7 bis 14 besprochen, aus einer Anzahl von Wiederholungsversuchsschritten, die den Umfang der Wiederholung allmählich erhöhen, wenn ein vorheriger Wiederholungsversuchsschritt erfolglos bleibt.
Bei einer bevorzugten Ausführungsform wird ein zentraler Wiederherstellungskoordinator 75 eingesetzt, um eine Menge von global konsequenten Fixpunkten aufrechtzuerhalten, um den Umfang einer Wiederholungsfortpflanzung zu minimieren und die nachfolgend besprochene Wiederherstellungslinie während einer Wiederherstellungsbetriebsart zu berechnen. Vorzugsweise enthält der zentrale Wiederherstellungskoordinator 75 eine Kopie der Fehlertoleranz-Prozeßliste 25, die alle Anwendungsprozesse auflistet, die gerade durch das fehlertolerante Rechensystem 5 überwacht werden, und wo jeder Prozeß abläuft.
Zusätzlich enthält der zentrale Wiederherstellungskoordinator 75 vorzugsweise einen globalen- Fixpunktkoordinator 77 zur Aufrechterhaltung einer Menge von konsequenten globalen Fixpunkten. Ein globaler Fixpunkt ist eine Menge von Fixpunkten mit einem Fixpunkt aus jedem überwachten Anwendungsprozeß. Gemäß der Wiederholungsfortpflanzungsregel muß, wenn ein Sender einer Nachricht zu seinem letzten Fixpunkt zurückfährt und das Senden einer Nachricht rückgängig macht, der Empfänger dieser Nachricht ebenfalls zurückfahren, um den Empfang der Nachricht rückgängig zu machen.
Somit ist ein konsequenter globaler Fixpunkt ein globaler Fixpunkt, der keine zwei Fixpunkte enthält, die die Wiederholungsfortpflanzungsregel verletzen.
Bei einer Ausführungsform wird immer dann, wenn ein Fixpunkt eingeleitet und erfolgreich durch einen Prozeß mit der nachfolgend besprochenen Fixpunkt- Funktion ausgeführt wird, der zentrale Wiederherstellungskoordinator 75 benachrichtigt. Der zentrale Wiederherstellungskoordinator 75 sendet danach vorzugsweise eine Nachricht an alle anderen überwachten Anwendungsprozesse, damit diese entsprechende Fixpunkte aufnehmen, um zu garantieren, daß die resultierende Menge von Fixpunkten konsequent ist.
Zusätzlich können global konsequente Fixpunkte sichergestellt werden, indem kommunikationsveranlaßte Fixpunkte implementiert werden, wobei ein Prozeß, der eine Nachricht empfängt, einen Fixpunkt annimmt, wenn die Fixpunkt-Intervallzahl des Senders, die in den Nachrichtenkopfinformationen angegeben wird, größer als die Fixpunkt-Intervallzahl des Empfängers ist. Danach sendet die dem Empfängerprozeß zugeordnete Überwachungsvorrichtung 15 eine Anzeige des neuen Fixpunkts zu dem globalen-Fixpunktkoordinator 77 des zentralen Wiederherstellungskoordinators 75.
Bei einer alternativen Ausführungsform kann ein unkoordiniertes Fixpunktsystem, das eine nachlässige Fixpunktkoordination einsetzt, implementiert werden. Für eine Besprechung eines nachlässigen Fixpunkt- Koordinationsverfahrens siehe Yi-Min Wang und W. Kent Fuchs, "Lazy Checkpoint Coordination for Bounding Rollback Propagation", Proc. IEEE Symposium Reliable Distributed Systems, S. 78-85 (Okt. 1993).
Zusätzlich enthält der zentrale Wiederherstellungskoordinator 75 vorzugsweise außerdem ein Wiederherstellungslinienberechnungsteilsystem 79, das einen Wiederherstellungslinienberechnungsalgorithmus 1500 implementiert, der nachfolgend in Verbindung mit Fig. 15a und Fig. 15b ausführlich besprochen wird.

Wiederherstellungskonzepte und -definitionen

Für eine ausführliche Besprechung von Wiederherstellungskonzepten und -definitionen, siehe Yi-Min Wang et al., "Progressive Retry Technique for Software Error Recovery in Distributed Systems", Proc. of 23d IEEE Conf. on Fault-Tolerant Computing Systems (FTCS), S. 138-144 (Juni 1993).
Wenn der Fehlererkennungsüberwacher 20 einen Fehler in einem Prozeß, wie zum Beispiel dem in Fig. 2a gezeigten Prozeß Pa, an dem mit "F&sub1;" markierten Punkt erkennt, dann leitet das Neustart-Teilsystem 30 der Überwachungsvorrichtung 15 eine Wiederholung des Prozesses Pa von dem letzten, dem Prozeß Pa zugeordneten Fixpunkt Ca,4 aus ein, indem die letzten Fixpunktdaten, die dem Prozeß Pa zugeordnet sind, aus der kritischen Speicherkopie 88 wiederhergestellt werden. Das Wiederholen des Prozesses Pa von seinem Fixpunkt Ca,4 aus macht das Senden der Nachricht Ma rückgängig.
Dementsprechend muß der Prozeß Pb ebenfalls zu einem Zustand vor dem Empfang von Ma zurückfahren, um den Empfang der Nachricht Ma rückgängig zu machen, um der Wiederholungsfortpflanzungsregel zu genügen, die angibt, daß, wenn ein Sender zurückfährt und das Senden einer Nachricht rückgängig macht, der Empfänger ebenfalls zurückfahren muß, um den Empfang der Nachricht rückgängig zu machen. Andernfalls wird die Nachricht Ma in dem fehlertoleranten Rechensystem 5 als "empfangen aber noch nicht gesendet" verzeichnet, was zu einer Inkonsequenz des Systemzustands führt.
Der Prozeß Pa kann jedoch gemäß einem Merkmal der Erfindung den Zustand rekonstruieren, von dem aus Ma erzeugt wurde, wodurch die Ausführung von Pb auf der Grundlage des Empfangs von Ma gültig bleiben kann. Somit muß der Prozeß Pb nicht zurückfahren, um den Empfang der Nachricht Ma rückgängig zu machen. Dies kann erzielt werden, indem die nachfolgend besprochene Annahme der stückweisen Bestimmtheit und die Nachrichten, die für den Prozeß Pa in der Empfänger- und Sender- Protokolldatei 90, 92 seit dem letzten eigentlichen Fixpunkt protokolliert wurden, eingesetzt werden.
Obwohl der Empfang jeder Nachricht durch einen Prozeß ein unvorhersehbares oder nichtdeterministisches Ereignis ist, sagt die Annahme der stückweisen Bestimmtheit aus, daß die Prozeßausführung zwischen zwei beliebigen aufeinanderfolgenden empfangenen Nachrichten, die als ein Zustandsintervall bezeichnet werden, deterministisch ist. Wenn also ein Prozeß sowohl den Nachrichteninhalt als auch die Verarbeitungsreihenfolge der empfangenen Nachrichten protokolliert hat, dann ermöglicht die deterministische Neuwiedergabe der Nachrichten in dem Protokoll eine Zustandsrekonstruktion des entsprechenden Prozesses. Jedesmal, wenn eine Nachricht durch einen Prozeß empfangen wird, wird, wie bereits erwähnt, das nichtdeterministische Ereignis in der Empfänger- Protokolldatei 90 protokolliert, wodurch effektiv ein "logischer" Fixpunkt am Ende des folgenden Zustandsintervalls plaziert wird. Auf diese Weise dienen die zusätzlichen "logischen" Fixpunkte zur Minimierung des Dominoeffekts der Wiederholungsfortpflanzung, der tendenziell andere Prozesse an der Wiederherstellung beteiligen könnte.
Der letzte eigentliche Fixpunkt Ca,6, der dem Prozeß Pa zugeordnet ist, ermöglicht wie in Fig. 2b gezeigt die Wiederherstellung des Prozeßzustands an dem Punkt, an dem der Fixpunkt aufgenommen wurde.
Zusätzlich plazieren das Nachrichtenprotokoll und die Annahme der stückweisen Bestimmtheit effektiv "logische" Fixpunkte La,1, La,2 und La,3 am Ende des Zustandsintervalls, das durch jede empfangene Nachricht gestartet wird, aufgrund der Möglichkeit der Zustandsrekonstruktion. Somit fährt der Prozeß Pa zwar physikalisch zu dem Fixpunkt Ca,6 in Fig. 2b zurück, kann aber "logisch" zu dem letzten "logischen" Fixpunkt La,3 zurückfahren, und muß deshalb das Senden der Nachricht M4 nicht rückgängig machen. Dementsprechend muß der Prozeß Pb nicht an der Wiederholung des Prozesses Pa beteiligt sein.
Obwohl die "physikalische Wiederholungsdistanz" die Wiederholungserstreckung jedes einzelnen Prozesses bestimmen kann, steuert somit jedoch die "logische Wiederholungsdistanz" die Erstreckung der Wiederholungsfortpflanzung auf anderen Prozessen und damit die Anzahl von bei der Wiederherstellung beteiligten Prozessen.
Obwohl die Annahme der stückweisen Bestimmtheit ausgenutzt werden kann, um den Umfang einer Wiederholung zu begrenzen, ist sie möglicherweise nicht über die gesamte Ausführung hinweg gültig. Zum Beispiel können einige nichtdeterministische Ereignisse von Funktionen der Echtzeit abhängen und nicht einfach aufgezeichnet und neu wiedergegeben werden. Zum Beispiel könnte ein bestimmter Prozeß eine bestimmte Nachricht nur dann senden, wenn es vor 14 Uhr ist. Dementsprechend sollte, wenn eine Wiederherstellung kurz nach 14 Uhr eingeleitet wird, die Nachricht nicht regeneriert werden. Einfach alle Nachrichten in dem Nachrichtenprotokoll neu wiederzugeben, ist somit möglicherweise nicht akkurat.
Gemäß einem Merkmal der Erfindung, das ausführlich nachfolgend besprochen wird, werden somit die durch einen Prozeß während der Wiederherstellung regenerierten Nachrichten mit den durch den Prozeß in dem Nachrichtenprotokoll während der anfänglichen Ausführung gespeicherten Nachrichten verglichen, um die Annahme der stückweisen deterministischen Ausführung zu verifizieren. Zum Beispiel wird, wie in Fig. 2b gezeigt, bei der Regeneration der Nachricht M&sub4; während einer Wiederherstellungsbetriebsart die durch den Prozeß Pa regenerierte Nachricht mit der in der Sender- Protokolldatei 92 während der anfänglichen Bearbeitung gespeicherten Nachricht verglichen. Wenn die Nachrichten identisch sind, dann wird die Annahme der stückweisen Bestimmtheit validiert, und die Nachricht muß nicht erneut zu dem Prozeß Pb übertragen werden. Somit muß der Prozeß Pb nicht an der Wiederholung beteiligt sein. Wenn jedoch bestimmt wird, daß die regenerierte Nachricht M4 nicht mit der in der Sender- Protokolldatei 92 gespeicherten Nachricht identisch ist, dann muß ein dazwischentretendes nichtdeterministisches Ereignis eingetreten sein. Somit kann der Prozeß Pa seinen Zustand nur bis zu dem letzten eigentlichen oder logischen Fixpunkt rekonstruieren, der sich vor dem nichtdeterministischen Ereignis befindet, wie zum Beispiel dem logischen Fixpunkt La.1, der in Fig. 2b gezeigt ist. Somit werden alle logischen Fixpunkte nach dem nichtdeterministischen Ereignis La,2 und La,3 nicht verfügbar und müssen verworfen werden. Der Prozeß Pa muß somit das Senden der Nachricht M4 rückgängig machen, und der Prozeß Pb muß zu seinem letzten logischen Fixpunkt vor dem Empfang der Nachricht M4, nämlich dem logischen Fixpunkt Lb,1 zurückfahren.
Gemäß einem weiteren Merkmal der Erfindung versuchen bestimmte Schritte des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700, die nachfolgend weiter besprochen werden, Softwarefehler zu umgehen, indem bestimmte Nachrichten in der Empfänger- Protokolldatei 90 eines oder mehrerer Anwendungsprozesse umgeordnet werden. Somit ist es wichtig, zu erfassen, welche Nachrichten umgeordnet werden können und welche Nachrichten in ihrer ursprünglichen Reihenfolge neu wiedergegeben werden müssen, um Korrektheit sicherzustellen.
Um den Zustand von Prozessen, die hei einer Wiederherstellung bis zu der Wiederherstellungslinie 310 beteiligt sind, zu rekonstruieren, kann das fehlertolerante Rechensystem 5, wie in Fig. 3 gezeigt, die Prozesse von der Neustartlinie 302 aus neu starten, bei der es sich um den letzten eigentlichen Fixpunkt für jeden Prozeß vor der Wiederherstellungslinie 310 handelt, indem die kritische Speicherkopie 88, die jedem Fixpunkt zugeordnet ist, wiederhergestellt wird. Die Wiederherstellungslinie 310, die vorzugsweise durch den oben besprochenen zentralen Wiederherstellungskoordinator 75 berechnet wird, wird an der letzten verfügbaren, global konsequenten Menge logischer oder eigentlicher Fixpunkte positioniert.
Nachrichten, die vor der Neustartlinie 302 verarbeitet wurden, wie zum Beispiel die Nachricht M1, werden als veraltete Nachrichten bezeichnet und sind für die Wiederherstellung nutzlos. Sowohl die Nachrichteninhalte als auch die Verarbeitungsreihenfolge von Nachrichten, die zwischen der Neustartlinie 302 und der Wiederherstellungslinie 310 empfangen und verarbeitet wurden, müssen in der Empfänger-Protokolldatei 90 protokolliert werden. Diese Nachrichten werden als deterministische Nachrichten bezeichnet und sie müssen in ihrer ursprünglichen Reihenfolge für die deterministische Rekonstruktion nach einem Neustart neu wiedergegeben werden, um die Wiederherstellungslinie 310 zu erreichen.
Bei Nachrichten, die vor der Wiederherstellungslinie 310 gesendet wurden und nach der Wiederherstellungslinie 310 durch den Empfänger verarbeitet wurden, die als im Übergang befindliche Nachrichten bezeichnet werden, wie zum Beispiel die Nachrichten M&sub4; und M&sub5;, sind nur die Nachrichteninhaltsinformationen in den Protokollen gültig. Die Verarbeitungsreihenfolge für im Übergang befindliche Nachrichten wird entweder nicht protokolliert oder ist ungültig. Die im Übergang befindlichen Nachrichten breiten sich effektiv immer noch in den Kommunikationskanälen aus und können deshalb aufgrund von unbekannten Übertragungsverzögerungen in einer willkürlichen Reihenfolge eintreffen. Im Übergang befindliche Nachrichten sind die einzigen Nachrichten, die umgeordnet werden können.
Als letztes wird das Senden von nach der Wiederherstellungslinie 310 gesendeten Nachrichten, die als Waisennachrichten bezeichnet werden, wie zum Beispiel die Nachrichten M&sub6; und M&sub7;, und deren Empfang mit Bezug auf die Wiederherstellungslinie rückgängig gemacht. Somit werden Waisennachrichten bei der Wiederholung ungültig gemacht und sollten durch den Empfängerprozeß verworfen werden. Andernfalls ist die Wiederherstellungslinie inkonsequent.

Datenstrukturen zur Implementierung von Fehlertoleranz

Die Fehlertoleranz-Prozeßliste 25 in Fig. 4a führt Informationen über diejenigen Prozesse, die gerade durch das fehlertolerante Rechensystem 5 überwacht werden. Bei einer bevorzugten Ausführungsform wird durch die Überwachungsvorrichtung 15 jedes Knotens eine identische Kopie der Fehlertoleranz-Prozeßliste 25 aufrechterhalten. Die Fehlertoleranz-Prozeßliste 25 führt eine Mehrzahl von Zeilen, wie zum Beispiel die Zeilen 405, 407, 409 und 411, die jeweils einem überwachten Anwendungsprozeß zugeordnet sind. Für jeden in der Spalte 420 aufgelisteten Anwendungsprozeß enthält die Fehlertoleranz-Prozeßliste 25 in der Spalte 425 eine Anzeige des IPC-Ports des lokalen Knotens, der für die Kommunikation mit dem Prozeß eingesetzt werden sollte.
In einer Mehrfachknotenumgebung enthält die Fehlertoleranz-Prozeßliste 25 vorzugsweise die Spalten 430 und 435 zur Anzeige des primären Knotens, auf dem jeder Anwendungsprozeß ablaufen sollte, wenn der primäre Knoten aktiv ist, und eine Liste von Sicherungsknoten für den Anwendungsprozeß, für den Fall, daß der primäre Knoten nicht arbeitet, sowie in Spalte 440 eine Anzeige des aktuellen Knotens, auf dem der zugeordnete Anwendungsprozeß abläuft.
Die Fehlertoleranz-Prozeßliste 25 enthält außerdem in der Spalte 445 eine Anzeige der kritischen Dateien, wie zum Beispiel die kritische Speicherkopie 88 und die Empfänger- und die Sender-Protokolldateien 90, 92, die jedem Prozeß zugeordnet sind. Als letztes kann die Fehlertoleranz-Prozeßliste 25 als Option in der Spalte 448 eine Zeitgrenze enthalten, die bei einer passiven Fehlererkennungsüberwachungsanordnung der maximale Zeitzustand ist, den die Überwachungsvorrichtung 15 zwischen Herzschlagnachrichten warten sollte, bevor sie zu dem Schluß kommt, daß der Anwendungsprozeß hängt.
In einer Mehrfachknotenumgebung führt jede Überwachungsvorrichtung 15 in dem fehlertoleranten Rechensystem 5 vorzugsweise eine Knotenliste 32 (Fig. 4b), die jeden der Knoten auflistet, die gerade in dem fehlertoleranten Rechensystem 5 aktiv sind. Bei einer bevorzugten Ausführungsform überwacht vorzugsweise jeder Knoten in der Knotenliste 32, wie zum Beispiel die Knoten 10 und 12, den nächsten Knoten, der in der Knotenliste 32 aufgeführt ist. Somit bestimmt die Reihenfolge der Knoten in der Knotenliste 32 die Ringkonfiguration. Wenn ein Knoten außer Betrieb genommen wird, dann wird diese Information vorzugsweise zu jedem überlebenden Knoten auf die nachfolgend beschriebene Weise gesendet, damit die Knotenliste 32, die in jedem Knoten gespeichert ist, entsprechend aktualisiert werden kann.
Wie bereits erwähnt wird jede Nachricht, die durch einen Anwendungsprozeß empfangen oder gesendet wird, vorzugsweise in Empfänger- und Sender-Protokolldateien 90 bzw. 92 protokolliert. Eine in Fig. 5a gezeigte Empfänger-Protokolldatei 90 wird vorzugsweise für jeden durch das fehlertolerante Rechensystem 5 überwachten Prozeß geführt, um Informationen für jede durch den zugeordneten Prozeß empfangene Nachricht zu speichern. Vorzugsweise wird beim Empfang durch den Anwendungsprozeß und vor der Verarbeitung jede Nachricht in der Empfänger-Protokolldatei 90 protokolliert. Die Empfänger-Protokolldatei 90 führt eine Mehrzahl von Zeilen, wie zum Beispiel die Zeilen 502, 504 und 506, die jeweils einer durch den zugeordneten Prozeß seit dem letzten erfolgreichen Fixpunkt empfangenen Nachricht entsprechen. Für jede in der Spalte 520 aufgeführte empfangene Nachricht enthält die Empfänger-Protokolldatei 90 in Spalte 522 eine Anzeige der Nachrichtengröße und in Spalte 524 eine Anzeige der Nachrichteninhalte. Die Informationen in den Spalten 522 und 524 können für einen Vergleich in einer Wiederherstellungsbetriebsart verwendet werden, um die Annahme der stückweisen Bestimmtheit auf eine nachfolgend beschriebene Weise zu verifizieren. Es wird bemerkt, daß die in Spalte 520 erscheinende Nachrichtenkennung nur für Zwecke der Beschreibung dient.
Zusätzlich enthält die Empfänger-Protokolldatei 90 in Spalte 526 eine Anzeige der Prozeßkennung des Senders, die während der Systeminitialisierung durch die Überwachungsvorrichtung 15 des lokalen Knotens des Senders oder durch den zentralen Wiederherstellungskoordinator 75 zugewiesen werden kann, sowie in Spalte 528 eine Anzeige der Fixpunkt-Intervallzahl des Senders und in Spalte 530 eine Anzeige der logischen Fixpunktzahl des Senders. Die Informationen in den Spalten 528 und 530 werden in einer Wiederherstellungsbetriebsart für die Wiederholungsfortpflanzung eingesetzt, um die Wiederherstellungslinie auf eine nachfolgend beschriebene Weise zu bestimmen. Wie nachfolgend besprochen, wird die Fixpunkt-Intervallzahl des Senders jedesmal erhöht, wenn ein Fixpunkt erfolgreich für den zugeordneten Anwendungsprozeß ausgeführt wird, und die logische Fixpunktzahl des Senders wird jedesmal erhöht, wenn eine neue Nachricht durch den Sender empfangen wird.
Als letztes kann die Empfänger-Protokolldatei 90 als Option in Spalte 532 eine Anzeige einer Bezugskennnummer enthalten, die jeder Nachricht zugeord net ist. Die Bezugskennnummer kann in dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus verwendet werden, um zu steuern, ob die aus demselben Sender empfangenen Nachrichten umgeordnet werden können. Bei einer Ausführungsform können Nachrichten, die sich in der Empfänger-Protokolldatei 90 aus demselben Sender mit derselben Bezugskennnummer befinden, nicht umgeordnet werden. Nachrichten aus demselben Sender mit nicht denselben Bezugskennnummern können umgeordnet werden.
Bei einer bevorzugten Ausführungsform wird jedesmal, wenn der zugeordnete Prozeß einen Fixpunkt erfolgreich ausführt, ein "Dummy"-Eintrag vorzugsweise in der Empfänger-Protokolldatei 90 plaziert. Auf diese Weise können Nachrichten in der Empfänger- Protokolldatei 90 der richtigen Fixpunkt-Intervallzahl des Empfängers zugeordnet werden, damit seit dem letzten eigentlichen Fixpunkt empfangene Nachrichten während bestimmter Schritte des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 identifiziert werden können.
Ähnlich wird eine Sender-Protokolldatei 92, die in Fig. 5b gezeigt ist, vorzugsweise für jeden durch das fehlertolerante Rechensystem 5 überwachten Prozeß geführt, um Informationen für jede durch den zugeordneten Prozeß gesendete Nachricht zu speichern. Die Sender-Protokolldatei 92 führt eine Mehrzahl von Zeilen, wie zum Beispiel die Zeilen 552, 554, 556 und 558, die jeweils einer durch den zugeordneten Prozeß seit dem letzten erfolgreichen Fixpunkt gesendeten Nachricht entsprechen. Für jede in der Spalte 570 aufgelistete gesendete Nachricht enthält die Sender- Protokolldatei 92 in der Spalte 572 eine Anzeige der Nachrichtengröße und in Spalte 574 eine Anzeige der Nachrichteninhalte. Die Informationen in den Spalten 572 und 574 können für einen Vergleich in einer Wiederherstellungsbetriebsart auf die nachfolgend beschriebene Weise verwendet werden. Es wird bemerkt, daß die in Spalte 570 erscheinende Nachrichtenkennung nur für Zwecke der Beschreibung dient.
Zusätzlich enthält die Sender-Protokolldatei 92 in Spalte 576 eine Anzeige der Prozeßkennung des Empfängers, die während der Systeminitialisierung durch die Überwachungsvorrichtung 15 des lokalen Knotens des Empfängers oder durch den zentralen Wiederherstellungskoordinator 75 zugewiesen werden kann, sowie in Spalte 578 eine Anzeige der logischen Fixpunktzahl des Senders. Wie oben besprochen, wird die logische Fixpunktzahl des Senders jedesmal erhöht, wenn eine neue Nachricht durch den Sender empfangen wird.
Die in Fig. 5a bzw. 5b gezeigten Empfänger- und Sender-Protokolldateien 90 und 92 wurden mit Informationen für den Prozeß P&sub2; angereichert, die nachfolgend in Verbindung mit Fig. 6a bis 6f besprochen werden.

Mehrfachknotenbetrieb

In einer Mehrfachknotenumgebung überwacht jede Überwachungsvorrichtung 15 vorzugsweise außerdem die Überwachungsvorrichtung 15 eines anderen Knotens auf eine kreisförmige Weise zur Erkennung von Knotenausfällen. Für eine Besprechung der Fehlertoleranz in einer Mehrfachknotenumgebung siehe die eigene US- Patentanmeldung Nr. 07/954 549 mit dem Titel "Apparatus and Method for Fault-Tolerant Computing", 30. 9. 1992; und R. Bianchini, Jr. und R. Buskens, "An Adaptive Distributed System-Level Diagnosis Algorithm and Its Implementation", Proc. of 21st IEEE Conf. on Fault Tolerant Computing Systems (FTCS), S. 222-29 (Juli 1991)
Im allgemeinen überwacht in einer Mehrfachknotenumgebung die Überwachungsvorrichtung 15 in jedem Knoten den Status von Anwendungsprozessen, die lokal auf dem entsprechenden Knoten ablaufen, sowie den Status von mindestens einem weiteren Knoten. Die Überwachungsvorrichtung 15 enthält vorzugsweise eine Knotenliste 32, die oben in Verbindung mit Fig. 9:b besprochen wird, mit der angezeigt werden kann, welchen Knoten bzw. welche Knoten die Überwachungsvorrichtung 15 überwacht. Vorzugsweise ist der Überwachungsvorrichtung 15 in jedem Knoten eine identische Kopie der Knotenliste 32 verfügbar. Wenn ein erster Knoten ausfällt, dann wird dies durch die Überwachungsvorrichtung 15 auf einem anderen Knoten erkannt, die über den ersten Knoten wacht. Die wachende Überwachungsvorrichtung 15 sendet eine Nachricht zu den überlebenden Knoten, um anzuzeigen, daß die Knotenliste 32 so modifiziert werden sollte, daß sie den Verlust des ausgefallenen Knotens widerspiegelt. Zusätzlich sollten die in der Spalte 435 der Fehlertoleranz-Prozeßliste 25 angegebenen Sicherungsknoten für jeden Prozeß, der auf dem ausgefallenen Knoten unmittelbar vor dem erkannten Ausfall ablief, die entsprechenden Prozesse neu starten.
Damit eine Überwachungsvorrichtung 15 in einem Knoten einen Anwendungsprozeß von einem anderen Knoten neu startet, muß die Überwachungsvorrichtung 15 jedoch über eine Kopie des Zustands dieses Prozesses verfügen. Somit enthält, wie bereits erwähnt, jeder Knoten einen nichtflüchtigen Speicher 44 zur Aufrechterhaltung von Kopien des Zustands von Prozessen, die auf dem lokalen Knoten ablaufen, darunter eine Fixpunktkopie des kritischen Speichers 88 jedes Prozesses, sowie die Empfänger- und Sender-Protokolldateien 90, 92 für jeden lokalen Prozeß. Zusätzlich wird in einer Mehrfachknotenumgebung der Prozeßzustand aus dem primären Knoten zu dem Sicherungsknoten kopiert, der der wachenden Überwachungsvorrichtung 15 zugeordnet ist. Bei einer bevorzugten Ausführungsform werden Kopien durch die Überwachungsvorrichtung 15 in dem überwachten Knoten hergestellt und jedesmal dann zu der wachenden Überwachungsvorrichtung 15 gesendet, wenn eine wesentliche Veränderung der kritischen Speicherkopie 88 oder der Protokolldateien 90, 92 für den entsprechenden Anwendungsprozeß eintritt.
Aus dem Obigen ist offensichtlich, daß jeder Überwachungsvorrichtung 15 bekannt sein muß, wo jeder überwachte Anwendungsprozeß in dem fehlertoleranten Rechensystem 5 zu einem bestimmten Zeitpunkt abläuft. Diese Informationen sind vorzugsweise in der Spalte 440 der Fehlertoleranz-Prozeßliste 25 enthalten, von der jede Überwachungsvorrichtung 15 eine identische Kopie besitzt. Die Fehlertoleranz-Prozeßliste 25 kann konsequent gehalten werden, indem bewirkt wird, daß jede Überwachungsvorrichtung 15 eine Nachricht zu allen anderen Überwachungsvorrichtungen 15 sendet, wenn sie einen überwachten Prozeß startet oder neu startet, und bewirkt wird, daß jede Überwachungsvorrichtung 15 auf eine solche Nachricht reagiert, indem sie die Fehlertoleranz-Prozeßliste 25 wie durch die Nachricht angegeben aktualisiert.
Wenn ein zuvor ausgefallener Knoten in den Betrieb zurückkehrt, dann erhält die Überwachungsvorrichtung 15 in diesem Knoten eine Kopie der Knotenliste 32 und der Fehlertoleranz-Prozeßliste 25 aus der Überwachungsvorrichtung 15 in einem anderen Knoten. Die Fehlertoleranz-Prozeßliste 25, die oben in Verbindung mit Fig. 4a besprochen wurde, zeigt an, welche Knoten gerade die für den zuvor ausgefallenen Knoten lokalen Anwendungsprozesse ausführen, und die Speicherstelle der Zustandsdateien, die den Zustand der lokalen Prozesse enthalten, die notwendig sind, um diese Prozesse neu zu starten. Die Überwachungsvorrichtung 15 erhält Kopien der Dateien aus den Knoten, die gerade die Prozesse ausführen, und startet die Prozesse mit den Zustandskopien neu. Wie bereits erwähnt, sendet die Überwachungsvorrichtung 15, wenn sie einen Prozeß neu startet, eine Nachricht zu den anderen Überwachungsvorrichtungen 15 in dem fehlertoleranten Rechensystem 5, und wenn der neugestartete Prozeß auf einer Überwachungsvorrichtung 15 abläuft, dann beendet diese Überwachungsvorrichtung 15 den Ablauf des Prozesses und modifiziert ihre Fehlertoleranz-Prozeßliste 25, um anzuzeigen, daß der Prozeß nun auf dem ordnungsgemäßen primären Knoten abläuft. Alle anderen Überwachungs vorrichtungen 15 modifizieren einfach ihre Fehlertoleranz-Prozeßlisten 25 auf die gerade gezeigte Weise. Fehlertoleranz-Bibliotheksfunktionen Gemäß einem Merkmal der Erfindung kann ein Anwendungsprozeß fehlertolerant gemacht werden, indem entsprechende Funktionen aus der Fehlertoleranz- Bibliothek 82 in den Code für den Anwendungsprozeß eingefügt werden. Wie bereits erwähnt, enthält die fehlertolerante Bibliothek 82 vorzugsweise eine Herzschlag-Funktion, die beim Aufruf durch einen Anwendungsprozeß eine Herzschlagnachricht in vorgegebenen Intervallen zu der Überwachungsvorrichtung 15 sendet, die anzeigt, daß der zugeordnete Prozeß immer noch aktiv ist. Wenn die Überwachungsvorrichtung 15 vor dem Ende des vorgegebenen Intervalls kein weiteres Signal von dem Anwendungsprozeß empfängt, dann nimmt die Überwachungsvorrichtung 15 an, daß der Anwendungsprozeß hängt oder abgestürzt ist.
Zusätzlich enthält die fehlertolerante Bibliothek 82 eine speicherkritische Funktion, die es einem Benutzer erlaubt, selektiv vorzugeben, welche Daten in dem Anwendungsprozeß kritische Daten sind, die dann jedesmal, wenn eine Fixpunkt-Funktion durch den Anwendungsprozeß ausgeführt wird, in einen Bereich von nichtflüchtigem Speicher 44 kopiert werden.
Somit werden bei einem Aufruf einer Fixpunkt- Funktion durch einen Anwendungsprozeß die kritischen Daten vorzugsweise auf einem stabilen Speichergerät gespeichert. Zusätzlich wird bei jeder erfolgreichen Fixpunkt-Ausführung die Fixpunkt-Intervallzahl des zugeordneten Anwendungsprozesses, bei der es sich um das Intervall zwischen zwei aufeinanderfolgenden Fixpunkten handelt, vorzugsweise erhöht. Wenn die Fixpunkt- Funktion erfolgreich durchgeführt wurde, dann wird eine Nachricht mit dem Fixpunkt-Dateinamen, der Prozeßkennung und der aktuellen Fixpunkt-Intervallzahl zu der Überwachungsvorrichtung 15 gesendet. Auf diese Weise kann die Überwachungsvorrichtung 15 diese Informationen einsetzen, um die Fixpunktdatei auf einen oder mehrere Sicherungsknoten zu duplizieren und den globalen Fixpunkt-Koordinator 77 von dem neuen Fixpunkt in einer koordinierten Fixpunktumgebung zu benachrichtigen. Dies bewirkt vorzugsweise, daß der globale Fixpunkt- Koordinator 77 einen globalen Fixpunkt der übrigen überwachten Prozesse einleitet.
Zusätzlich enthält die fehlertolerante Bibliothek 82 vorzugsweise eine Wiederherstell-Funktion, die es einem Anwendungsprozeß ermöglicht, die Fixpunkt- Daten aus der kritischen Speicherkopie 88 während einer Wiederherstellungsbetriebsart auf die nachfolgend beschriebene Weise wiederherzustellen.
Die fehlertolerante Bibliothek 82 enthält vorzugsweise außerdem eine fehlertolerante Schreibfunktion, die nachfolgend als ftwrite bezeichnet wird, die jede Ausgangsnachricht in der Sender- Protokolldatei 92 protokolliert, bevor die Nachricht durch den Anwendungsprozeß übertragen wird. In einer Mehrfachknotenumgebung werden die Ausgangsdaten ebenfalls durch die Überwachungsvorrichtung 15 auf eine Sicherungsmaschine dupliziert und protokolliert. Wenn sich ein Anwendungsprozeß in einer normal-Betriebsart befindet, dann sendet die Funktion ftwrite Nachrichten zu anderen Prozessen und fügt die Informationen für jede gesendete Nachricht in die Sender-Protokolldatei 92 ein.
Jede Nachricht, die durch die Funktion ftwrite gesendet wird, enthält vorzugsweise eine Nachrichtenkennung, die Prozeßkennung des Senders, die Fixpunkt-Intervallzahl und die logische Fixpunktzahl des Senders und als Option eine Bezugskennnummer. Mit · der Fixpunkt-Intervallzahl können koordinierte Fixpunkte implementiert werden. Wie bereits erwähnt, kann mit der Bezugskennnummer angezeigt werden, ob Nachrichten aus demselben Sender umgeordnet werden können.
In einer Wiederherstellungsbetriebsart wird jedoch nach der Verarbeitung einer protokollierten Nachricht die Funktion ftwrite ausgeführt, um jede frisch erzeugte Nachricht mit der entsprechenden Nachricht in der Sender-Protokolldatei 92 auf eine nachfolgend beschriebene Weise zu vergleichen, um die Annahme der stückweisen Bestimmtheit zu verifizieren. Wenn die während der Wiederherstellung erzeugte Nachricht mit der in der Sender-Protokolldatei 92 während der vorherigen Ausführung gespeicherten Nachricht identisch ist, dann muß die Nachricht nicht erneut übertragen werden. Wenn die Nachrichten jedoch nicht identisch sind, dann ist ein nichtdeterministisches Ereignis eingetreten, und der Umfang der Wiederherstellung muß auf eine nachfolgend beschriebene Weise vergrößert werden.
Die fehlertolerante Bibliothek 82 enthält vorzugsweise außerdem eine fehlertolerante Lesefunktion, die nachfolgend als ftread bezeichnet wird, die Eingangsnachrichten in der Empfänger-Protokolldatei 90 protokolliert, bevor sie durch den Empfänger- Anwendungsprozeß verarbeitet werden. In einer Mehrfachknotenumgebung werden die Eingangsdaten außerdem durch die Überwachungsvorrichtung 15 auf einer Sicherungsmaschine dupliziert und protokolliert. Wenn sich ein Anwendungsprozeß in einer normal-Betriebsart befindet, dann liest die Funktion ftread Daten aus einem IPC- Kanal und protokolliert die empfangene Nachricht in der Empfänger-Protokolldatei 90.
In einem Wiederherstellungszustand werden die Eingangsdaten jedoch aus der Empfänger-Protokolldatei 90 bis hin zu der Wiederherstellungslinie 310 gelesen, bevor jegliche Daten aus einem regulären Eingangskanal auf die nachfolgend beschriebene Weise gelesen werden können. Bei einer bevorzugten Ausführungsform prüft die Funktion ftread die jeder empfangenen Nachricht zugeordnete Fixpunkt-Intervallzahl des Senders und leitet einen Fixpunkt des zugeordneten Empfänger-Anwendungsprozesses ein, wenn die Fixpunkt-Intervallzahl des Senders größer als die aktuelle Fixpunkt-Intervallzahl des Empfängers ist, wodurch global konsequente Fixpunkte sichergestellt werden. Wenn die Funktion ftread eine Fixpunkt-Steuernachricht aus dem zentralen Wiederherstellungskoordinator 75 empfängt, leitet die Funktion ftread zusätzlich einen Fixpunkt des Anwendungsprozesses ein.
Fig. 6a bis 6f zeigen ein Kommunikationsmuster für eine Mehrzahl gleichzeitiger Anwendungsprozesse und zeigen, wie die Prozesse durch die verschiedenen Schritte des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beeinflußt werden, der nachfolgend in Verbindung mit Fig. 8 bis 11 besprochen wird. Im folgenden wird während der Besprechung des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zur Erläuterung jedes Schrittes des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 auf Fig. 6a bis 6f Bezug genommen.
Fig. 6a bis 6f setzen die folgenden Konventionen ein, um die verschiedenen Wiederherstellungskonzepte zu erläutern. Das Pluszeichen "+", das jedem Prozeß zugeordnet ist, zeigt die zeitliche Position des letzten eigentlichen Fixpunktes für jeden Prozeß an. Ein Pluszeichen in einem Quadrat zeigt die zeitliche Position der logischen Fixpunkte für jeden Prozeß an. Ein Quadrat ohne Pluszeichen zeigt den letzten gültigen logischen Fixpunkt an, der die Wiederherstellungslinie für jeden Prozeß bildet. Als letztes zeigt ein Pluszeichen in einem Kreis den letzten eigentlichen Fixpunkt an, wenn der zugeordnete Prozeß an dem aktuellen Schritt der progressiven Wiederholungsversuchs-Wiederherstellung beteiligt ist.

Progressiver Wiederholungsversuchs-Wiederherstellungsalgorithmus

Der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700, der die Prinzipien der vorliegenden Erfindung realisiert, wird im Schritt 701 eingeleitet (siehe Fig. 7). Während Schritt 705 wird wiederholt eine Prüfung durchgeführt, bis der Fehlererkennungsüberwacher 20 der Überwachungsvorrichtung 15 einen Fehler in einem überwachten Anwendungsprozeß erkennt. Wenn während Schritt 705 ein Fehler erkannt wird, dann wird während Schritt 710 geprüft, ob der aktuelle erkannte Fehler derselbe wie der zuvor erkannte Fehler für diesen Prozeß ist. Bei einer Ausführungsform wird angenommen, daß ein Fehler, der innerhalb eines vordefinierten Zeitschwellenwerts eines vorherigen Fehlers für denselben Prozeß erkannt wird, derselbe Fehler ist. Wenn während Schritt 710 bestimmt wird, daß der aktuelle erkannte Fehler nicht derselbe wie der etwaige zuvor erkannte Fehler für diesen Prozeß ist, dann ist dies der erste Versuch, diesen Fehler zu beheben, und das progressive Wiederholungsversuchsverfahren sollte im Schritt 1 gestartet werden, um eine Wiederherstellung des fehlerhaften Prozesses zu versuchen.
Somit wird eine Zählervariable N, die steuert, welcher Schritt des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus 700 gerade abläuft, während Schritt 715 auf 1 gesetzt, was anzeigt, daß der erste Schritt des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus 700 versucht werden sollte. Wenn jedoch während Schritt 710 bestimmt wird, daß der aktuelle erkannte Fehler derselbe Fehler wie der zuvor erkannte Fehler für diesen Prozeß ist, dann waren vorherige Versuche zur Behebung dieses Fehlers erfolglos. Dementsprechend sollte der Umfang des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 vergrößert werden, um eine Wiederherstellung des fehlerhaften Prozesses zu versuchen. Somit wird während Schritt 720 die Zählervariable N um 1 erhöht, was anzeigt, daß der nächste Schritt des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 versucht werden sollte.
Während Schritt 725 wird geprüft, ob der aktuelle Wert der Zählervariablen N gleich eins ist. Wenn während Schritt 725 bestimmt wird, daß der Wert der Zählervariablen N gleich eins ist, dann wird eine Sicherungskopie der Empfänger-Protokolldatei 90, die dem fehlerhaften Prozeß zugeordnet ist, anfänglich während Schritt 730 hergestellt. Während jeder Schritt des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 versucht wird, werden Informationen in der Empfänger-Protokolldatei 90 verworfen. Die Sicherungskopie der Empfänger-Protokolldatei 90 ermöglicht somit vorzugsweise erforderlichenfalls den Zugriff auf die Informationen.
Die nachfolgend in Verbindung mit Fig. 8 besprochene Wiedergabe-Subroutine 800, bei der es sich um Schritt 1 des progressiven Wiederholungsversuchsverfahren handelt, wird während Schritt 735 ausgeführt. Danach schreitet die Programmsteuerung zum Schritt 795 weiter, in dem der progressive Wiederholungsversuchs- Wiederherstellungsalgorithmus 700 beendet wird. Der fehlerhafte Prozeß nimmt dann die normale Programmausführung wieder auf, um zu versuchen, den zuvor erkannten Softwarefehler zu umgehen. Wenn der Fehler während der zweiten Ausführung nicht umgangen wird, dann wird beim nächsten erkannten Fehler der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 erneut eingeleitet und schreitet zum Schritt-2-Wiederholungsversuch weiter.
Wenn jedoch während Schritt 725 bestimmt wurde, daß der Wert der Zählervariablen N nicht gleich eins ist, dann wird während Schritt 740 geprüft, ob der Wert der Zählervariablen N gleich zwei ist. Wenn während Schritt 740 bestimmt wird, daß der Wert der Zählervariablen N gleich zwei ist, dann ist die wahrscheinliche Quelle des Fehlers eine aus einem anderen Prozeß empfangene Nachricht. Somit werden vorzugsweise eine Kopie der Fixpunktdatei und die Empfänger- und Sender- Protokolldateien 90 und 92 während Schritt 745 für ein Offline-Debugging in eine Verfolgungsdatei kopiert. Die nachfolgend in Verbindung mit Fig. 9 besprochene Empfänger-Umordnungs-Subroutine 900, bei der es sich um Schritt 2 des progressiven Wiederholungsversuchsverfahrens handelt, wird dann während Schritt 750 ausgeführt. Danach schreitet die Programm steuerung zum Schritt 795 weiter, in dem der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beendet wird. Alle überwachten Prozesse nehmen dann die normale Programmausführung wieder auf, um eine Umgehung des zuvor erkannten Softwarefehlers zu versuchen. Wenn der Fehler nicht umgangen wird, dann wird der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beim nächsten erkannten Fehler erneut eingeleitet und schreitet zum Schritt 3 Wiederholungsversuch weiter.
Wenn jedoch während Schritt 740 bestimmt wird, daß der Wert der Zählervariablen N nicht gleich zwei ist, dann wird während Schritt 755 geprüft, ob der Wert der Zählervariablen N gleich drei ist. Wenn während Schritt 755 bestimmt wird, daß der Wert der Zählervariablen N gleich drei ist, dann wird die Sender-Wiedergabe-Subroutine 1000, die nachfolgend in Verbindung mit Fig. 10 besprochen wird und bei der es sich um Schritt 3 des progressiven Wiederholungsversuchsverfahrens handelt, während Schritt 760 ausgeführt. Danach schreitet die Programmsteuerung zum Schritt 795 weiter, in dem der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beendet wird. Alle überwachten Prozesse nehmen die normale Programmausführung wieder auf, um zu versuchen, den Fehler zu umgehen. Wenn der Fehler nicht umgangen wird, dann wird der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beim nächsten erkannten Fehler erneut eingelesitet und schreitet zum Schritt 4 Wiederholungsversuch weiter.
Wenn jedoch während Schritt 755 bestimmt wird, daß der Wert der Zählervariablen N nicht gleich drei ist, dann wird während Schritt 765 geprüft, ob der Wert der Zählervariablen N gleich vier ist. Wenn während Schritt 765 bestimmt wird, daß der Wert der Zählervariablen N gleich vier ist, dann wird die nachfolgend in Verbindung mit Fig. 11 besprochene Sender- Umordnungs-Subroutine 1100, bei der es sich um Schritt 4 des progressiven Wiederholungsversuchsverfahrens han delt, während Schritt 770 ausgeführt. Danach schreitet die Programmsteuerung zum Schritt 795 weiter, in dem der progressive Wiederholungsversuchs-Wiedesrherstel - lungsalgorithmus 700 beendet wird, bis der nächste Fehler erkannt wird.
Wenn jedoch während Schritt 765 bestimmt wird, daß der Wert der Zählervariablen N nicht gleich vier ist, dann wird während Schritt 775 geprüft, ob der Wert der Zählervariablen N gleich fünf ist. Wenn während Schritt 775 bestimmt wird, daß der Wert der Zählervariablen N gleich fünf ist, dann wird die nachfolgend in Verbindung mit Fig. 12 besprochene Wiederholungsversuchs-Subroutine 1200 mit Wiederholung mit großem Umfang, bei der es sich um Schritt S des progressiven Wiederholungsversuchsverfahrens handelt, während Schritt 780 ausgeführt. Danach schreitet die Programmsteuerung zum Schritt 795 weiter, in dem der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beendet wird, bis der nächste Fehler erkannt wird.
Wenn jedoch während Schritt 775 bestimmt wird, daß der Wert der Zählervariablen N nicht gleich fünf ist, dann wird während Schritt 785 geprüft, ob der Wert der Zählervariablen N größer als fünf ist. Wenn während Schritt 785 bestimmt wird, daß der Wert der Zählervariablen N größer als fünf ist, dann war der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 nicht in der Lage, den fehlerhaften Prozeß wiederherzustellen. Somit sollte das System während Schritt 790 mit einer vollen Neuinitialisierung neu gestartet werden. Als Alternative kann während Schritt 790 eine Fehler- oder Warnnachricht erzeugt werden, die anzeigt, daß der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 den fehlerhaften Prozeß nicht erfolgreich wiederhergestellt hat. Danach schreitet die Programmsteuerung zum Schritt 795 weiter, in dem der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 beendet wird, bis der nächste Fehler erkannt wird.

Schritt 1 - Empfänger-Wiedergabe

Wie bereits erwähnt, führt der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 während Schritt 1 des progressiven Wiederholungsversuchsverfahrens die Empfänger-Wiedergabe-Subroutine 800 aus. Die Empfänger-Wiedergabe-Subroutine 800 beginnt im Schritt 801 (siehe Fig. 8). Die Empfänger-Wiedergabe- Subroutine (Schritt 1) 800 stellt den fehlerhaften Prozeß bis zum letzten Fixpunkt wieder her und versucht dann, den Fehler durch Wiedergabe der empfangenen Nachrichten seit dem letzten eigentlichen Fixpunkt in der Empfänger-Protokolldatei 90 des fehlerhaften Prozesses zu umgehen. Bei einer bevorzugten Ausführungsform wird dies durch Ausführung der nachfolgend in Verbindung mit Fig. 14a und 14b besprochenen deterministischen Wiedergabe-Subroutine 1400 für den fehlerhaften Prozeß während Schritt 820 implementiert.
Wie oben besprochen, wird jede Nachricht vorzugsweise protokolliert, bevor sie verarbeitet wird. Somit werden alle Nachrichten, die durch den fehlerhaften Prozeß vor dem erkannten Fehler gesendet oder empfangen werden, in den Empfänger- und Sender- Protokolldateien 90 und 92 des fehlerhaften Prozesses protokolliert. Somit können die protokollierten Nachrichten unter Verwendung der deterministischen Wiedergabe-Subroutine 1400 wiedergegeben werden, und der fehlerhafte Prozeß kann seinen Zustand bis zu dem Punkt, an dem er den Fehler erkannt hat, rekonstruieren.
Wenn ein Fehler für den Prozeß P&sub2; durch den Fehlererkennungsüberwacher 20 der Überwachungsvorrichtung 15 an dem mit "F" markierten Punkt erkannt wird, leitet das Neustart-Teilsystem 30 der Überwachungsvorrichtung 15 wie in Fig. 6a gezeigt den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 ein, um zu versuchen, den Fehler zu umgehen. Während Schritt 1 Wiederholungsversuch gibt die deterministische Wiedergabe-Subroutine 1400 alle Nachrichten in der Empfänger-Protokolldatei 90 des Prozesses P&sub2; wieder und versucht, den Fehler auf der Grundlage des Konzepts der Umgebungsdiversity zu umgehen. In manchen Fällen können durch bestimmte Umgebungsfaktoren, wie zum Beispiel einander ausschließende Konflikte, Unverfügbarkeit von Betriebsmitteln, unerwartete Signale und dergleichen, die zum Zeitpunkt der Ausführung der Wiederherstellung möglicherweise nicht mehr vorliegen, transiente Ausfälle verursacht werden, und Schritt-1--Wiederholungsversuch kann erfolgreich sein.
Wie nachfolgend besprochen, wird gemäß einem Merkmal der vorliegenden Erfindung die Gültigkeit der Annahme der stückweisen Bestimmtheit durch die deterministische Wiedergabe-Subroutine 1400 verifiziert, indem alle Nachrichten ausgewertet werden, die durch den Prozeß P&sub2; während der deterministischen Wiedergabe erzeugt werden. Wenn eine während der Wiederherstellung neu erzeugte Nachricht nicht mit der Nachricht übereinstimmt, die während der anfänglichen Verarbeitung in der Sender-Protokolldatei 92 gespeichert wurde, dann muß ein nichtdeterministisches Ereignis eingetreten sein.
Zum Beispiel gibt die deterministische Wiedergabe-Subroutine 1400 wie in Fig. 6b gezeigt alle Nachrichten in den Nachrichtenprotokollen von P&sub2; bis zur Nachricht Mf wieder. Nach der Neuerzeugung der Nachricht Mf bestimmt die deterministische Wiedergabe-Subroutine 1400, daß ein nichtdeterministisches Ereignis e eingetreten ist (siehe unten), wodurch die vorherige Version der Nachricht Mf, die erzeugt wurde, ungültig wird. Somit kann der Prozeß P&sub2; nur seinen Zustand bis zu dem logischen Fixpunkt rekonstruieren, der unmittelbar vor dem nichtdeterministischen Ereignis e liegt, und alle logischen Fixpunkte nach dem nichtdeterministischen Ereignis werden unverfügbar und müssen verworfen werden. Dementsprechend muß der Prozeß P&sub2; das Senden der Nachricht Mf sowie der Nachricht Mg rückgängig machen, um zu dem logischen Fixpunkt L2,a zurückzufahren und somit den Prozeß P&sub1; an der Wiederherstellung zu beteiligen, was durch die neue Wiederherstellungslinie 310 in Fig. 6b gezeigt wird. Der Prozeß P&sub1; muß zu dem letzten logischen Fixpunkt vor den ungesendeten Nachrichten Mg und Mf, nämlich zu dem logischen Fixpunkt L1,3 zurückfahren. Es ist zu beachten, daß eine solche Abweichung von der vorherigen Ausführung eine zusätzliche Möglichkeit zur Umgehung eines Softwarefehlers bietet, der einen transienten Ausfall verursacht.
Nach der Ausführung der deterministischen Wiedergabe-Subroutine 1400 während Schritt 820 (Fig. 8) kehrt die Programmsteuerung während Schritt 840 zu dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zurück, und die normale Ausführung für den fehlerhaften Prozeß wird wieder aufgenommen. Wenn der zuvor erkannte Fehler umgangen wird, dann fährt die Programmsteuerung fort. Wenn der Fehler jedoch nicht umgangen wurde, dann erkennt der Fehlererkennungsüberwacher 20 den Fehler erneut und leitet den progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus 700 mit Schritt 2 Wiederholungsversuch erneut ein.

Schritt 2 - Empfänger-Umordnung

Wie bereits erwähnt, führt der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 während Schritt 2 des progressiven Wiederholungsversuchsverfahrens die Empfänger-Umordnungs-Subroutine 900 aus. Die Empfänger-Umordnungs-Subroutine 900 beginnt im Schritt 901 (siehe Fig. 9).
Wenn der Schritt-1-Wiederholungsversuch erfolglos war, dann wird der Fehler höchstwahrscheinlich durch die aus anderen Prozessen empfangenen Nachrichten verursacht. Um den Umfang der Wiederholung zu minimieren, versucht Schritt 2 Wiederholungsversuch zunächst, lokal andere mögliche Szenarios bezüglich der empfangenen Nachrichten zu simulieren, ohne die Sender tatsächlich zu beteiligen.
Die Übertragungsverzögerungen ankommender Kommunikationskanäle sind im allgemeinen unvorhersehbar. Somit kann von Nachrichten, die aus verschiedenen Prozessen empfangen werden, im allgemeinen nicht angenommen werden, daß sie in einer bestimmten Reihenfolge ankommen. Somit kann die Nachrichtenumordnung durch den fehlerhaften Prozeß eingesetzt werden, um verschiedene Nachrichtenankunftsreihenfolgen zu simulieren. Es ist jedoch zu beachten, daß Nachrichten aus demselben Sender eine Verarbeitung in derselben Reihenfolge erfordern können.
Wie nachfolgend besprochen, versucht der fehlerhafte Prozeß, alle empfangenen Nachrichten, die in der Empfänger-Protokolldatei 90 des fehlerhaften Prozesses aufgelistet sind, umzuordnen. Die Empfänger- Umordnung-Subroutine (Schritt 2) 900 verwirft anfänglich die Verarbeitungsreihenfolgeninformationen während Schritt 910 für alle Nachrichten in der Empfänger-Protokolldatei 90 des fehlerhaften Prozesses, die seit dem letzten eigentlichen Fixpunkt durch den fehlerhaften Prozeß empfangen wurden. Dies dient zur Invalidierung aller logischen Fixpunkte für den fehlerhaften Prozeß nach der ersten empfangenen Nachricht.
Danach überträgt die Überwachungsvorrichtung 15, die dem fehlerhaften Prozeß zugeordnet ist, während Schritt 920 zu dem zentralen Wiederherstellungskoordinator 75 eine Anforderung zur Neuberechnung der Wiederherstellungslinie 310 für eine Schritt-2- Wiederherstellung mit einer Anzeige des fehlerhaften Prozesses. Die Art und Weise der Verarbeitung der Anforderung und der Neuberechnung der Wiedesrherstellungslinie durch den zentralen Wiederherstellungskoordinator 75 wird nachfolgend in Verbindung mit Fig. 15a und 15b besprochen.
Wenn der zentrale Wiederherstellungskoordinator 75 die Wiederherstellungslinie neu berechnet hat, sendet er die neuberechneten Wiederherstellungslinieninformationen zu jedem überwachten Anwendungsprozeß.
Bei Empfang der neuberechneten Wiederherstellungslinie verarbeitet jeder überwachte Prozeß die Wiederherstellungslinie im wesentlichen parallel und bestimmt die entsprechende Reaktion, wie durch die Verarbeitungszweige 930 und 940 in Fig. 9 für die Prozesse P&sub0; bzw. PN gezeigt.
Der Prozeß P&sub0; empfängt die gesendete Wiederherstellungslinie 310 aus dem zentralen Wiederherstellungskoordinator 75 während Schritt 950. Danach wird während Schritt 960 die nachfolgend in Verbindung mit Fig. 13 besprochene Prozeß-Nachrichtenprotokoll- Subroutine 1300 für den Prozeß P&sub0; ausgeführt.
Da die Verarbeitungsreihenfolgeninformationen für alle Nachrichten in der Empfänger-Protokolldatei 90 des fehlerhaften Prozesses verworfen wurden, sind die logischen Fixpunkte des fehlerhaften Prozesses nach der ersten empfangenen Nachricht nicht mehr verfügbar.
Somit muß das Senden aller durch den fehlerhaften Prozeß gesendeten Nachrichten rückgängig gemacht werden, und die Empfänger von etwaigen ungesendeten Nachrichten müssen am Schritt-2-Wiederholungsversuch teilnehmen.
Wenn wiederum ein Fehler für den Prozeß P&sub2; durch den Fehlererkennungsüberwacher 20 der Überwachungsvorrichtung 15 an dem mit "F" markierten Punkt erkannt wird, dann leitet das Neustart-Teilsystem 30 der Überwachungsvorrichtung 15, wie in Fig. 6c gezeigt, erneut den progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus 700 ein, um zu versuchen, den Fehler zu umgehen. Wenn der Fehler derselbe wie der zuvor erkannte Fehler ist, dann leitet der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 den Schritt-2-Wiederholungsversuch ein. Da die logischen Fixpunkte des fehlerhaften Prozesses P&sub2; nach seiner ersten empfangenen Nachricht nicht mehr verfügbar sind, wird die Wiederherstellungslinie durch den zentralen Wiederherstellungskoordinator 75 wie in Fig. 6c gezeigt gesetzt. An der Wiederherstellung ist der Prozeß P&sub1; beteiligt, da das Senden der Nachrichten Mg und Mf rückgängig gemacht wurde.
Wie nachfolgend besprochen, werden die Nachrichten in den Nachrichtenprotokollen der Prozesse P&sub2; und P&sub1; durch die Prozeß-Nachrichtenprotokoll- Subroutine 1300 auf die nachfolgend in Verbindung mit Fig. 13 beschriebene Weise verarbeitet, um zu versuchen, den Softwarefehler zu umgehen.
Wie in Fig. 9 gezeigt, empfängt und verarbeitet der Prozeß PN die gesendete Wiederherstellungslinie 310 während der Schritte 970 und 980, die durch den Prozeß PN im wesentlichen parallel zu der Verarbeitung des Prozesses P&sub0; und aller anderen überwachten Prozesse verarbeitet werden.
Nachdem alle überwachten Prozesse die Verarbeitung der neuberechneten Wiederherstellungslinie 310 abgeschlossen haben, kehrt die Programmsteuerung während Schritt 990 zu dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zurück, und die normale Ausführung wird für jeden überwachten Prozeß Po bis PN fortgesetzt. Wenn der zuvor erkannte Fehler umgangen wird, dann fährt die Programmsteuerung fort. Wenn der Fehler nicht. umgangen wird, dann erkennt der Fehlererkennungsüberwacher 20 den Fehler erneut und leitet den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 dieses Mal mit Schritt 3 als Versuch erneut ein.

Schritt 3 - Sender-Wiedergabe

Wie bereits erwähnt, führt der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 während Schritt 3 des progressiven Wiederholungsversuchsverfahrens die Sender-Wiedergabe-Subroutine 1000 aus. Die Sender-Wiedergabe-Subroutine (Schritt 3) 1000 beginnt im Schritt 1001 (siehe Fig. 10). Die Sender- Wiedergabe-Subroutine (Schritt 3) 1000 verwirft anfänglich während Schritt 1010 alle Nachrichten in der Empfänger-Protokolldatei 90 des fehlerhaften Prozesses, die durch den fehlerhaften Prozeß seit dem letzten eigentlichen Fixpunkt empfangen wurden. Wie nachfolgend beschrieben, senden die Sender dieser verworfenen Nachrichten dann diese Nachrichten erneut zu dem fehlerhaften Prozeß, um zu versuchen, den Fehler in dem fehlerhaften Prozeß zu umgehen.
Die dem fehlerhaften Prozeß zugeordnete Überwachungsvorrichtung 15 sendet dann während Schritt 1020 zu dem zentralen Wiederherstellungskoordinator 75 eine Anforderung zur Neuberechnung der Wiederherstellungslinie 310 für eine Schritt-3-Wiederherstellung mit einer Anzeige des fehlerhaften Prozesses. Die Art und Weise der Verarbeitung der Anforderung und der Neuberechnung der Wiederherstellungslinie durch den zentralen Wiederherstellungskoordinator 75 wird nachfolgend in Verbindung mit Fig. 15a und 15b besprochen.
Wenn der zentrale Wiederherstellungskoordinator 75 die Wiederherstellungslinie neu berechnet hat, sendet er die neuberechneten Wiederherstellungslinieninformationen zu jedem überwachten Anwendungsprozeß. Beim Empfang der neuberechneten Wiederherstellungslinie verarbeitet jeder überwachte Prozeß die Wiederherstellungslinie im wesentlichen parallel und bestimmt die entsprechende Reaktion, wie durch die Verarbeitungszweige 1030 und 1040 in Fig. 10 für die Prozesse P&sub0; bzw. PN gezeigt.
Der Prozeß P&sub0; empfängt die gesendete Wiederherstellungslinie 310 aus dem zentralen Wiederherstellungskoordinator 75 während Schritt 1050. Danach wird die nachfolgend in Verbindung mit Fig. 13 besprochene Prozeß-Nachrichtenprotokoll-Subroutine 7.300 während Schritt 1060 für den Prozeß P&sub0; ausgeführt. Mit der Prozeß-Nachrichtenprotokoll-Subroutine 1300 können die Sender der verworfenen Nachrichten für den Empfang durch den fehlerhaften Prozeß bestimmte Nachrichten in einer potentiell verschiedenen Reihenfolge erneut senden, was zur Umgehung des Fehlers dienlich sein kann.
Wenn ein Fehler für den Prozeß P&sub2; durch den Fehlererkennungsüberwacher 20 der Überwachungsvorrichtung 15 an dem mit "F" markierten Punkt erkannt wird, dann leitet das Neustart-Teilsystem 30 der Überwachungsvorrichtung 15, wie in Fig. 6d gezeigt, den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 ein, um zu versuchen, den Fehler zu umgehen. Während Schritt 3 Wiederholungsversuch bewirkt die Prozeß- Nachrichtenprotokoll-Subroutine 1300, daß die Sender der verworfenen Nachrichten diese Nachrichten erneut senden.
Wie nachfolgend besprochen, führt die Prozeß- Nachrichtenprotokoll-Subroutine 1300 die deterministische Wiedergabe-Subroutine 1400 aus, um die deterministischen Nachrichten wiederzugeben. Die deterministische Wiedergabe-Subroutine 1400 wertet alle Nachrichten aus, die durch den Prozeß P&sub2; während der deterministischen Wiedergabe erzeugt werden, um zu verifizieren, daß die Annahme der stückweisen Bestimmtheit gültig ist. Wenn eine während der Wiederherstellung erneut hergestellte Nachricht nicht mit der Nachricht übereinstimmt, die während der anfänglichen Bearbeitung in der Sender-Protokolldatei 92 gespeichert wurde, dann muß ein nichtdeterministisches Ereignis eingetreten sein.
Zum Beispiel gibt die deterministische Wiedergabe-Subroutine 1400, wie in Fig. 6e gezeigt, alle Nachrichten in den Nachrichtenprotokollen von P&sub3; bis zur Nachricht Ma wieder. Bei der erneuten Herstellung der Nachricht Ma bestimmt die deterministische Wiedergabe-Subroutine 1400 auf eine nachfolgend beschriebene Weise, daß ein nichtdeterministisches Ereignis e eingetreten ist, wodurch die vorherige Version der Nachricht Ma, die erzeugt wurde, nicht mehr gültig ist. Somit kann der Prozeß P&sub3; seinen Zustand nur bis zu dem logischen Fixpunkt L3,1 rekonstruieren, der unmittelbar vor dem nichtdeterministischen Ereignis e liegt, und alle logischen Fixpunkte nach dem nichtdeterministischen Ereignis werden unverfügbar und müssen verworfen werden. Dementsprechend muß der Prozeß P&sub3; zu dem logischen Fixpunkt L3,1 zurückfahren und das Senden der Nachrichten Ma, Md und Ms rückgängig machen und somit den Prozeß P&sub4; an der Wiederherstellung beteiligen, was durch die neue Wiederherstellungslinie 310 in Fig. 6e gezeigt wird.
Wie in Fig. 10 gezeigt, empfängt und verarbeitet der Prozeß PN die gesendete Wiederherstellungslinie 310 während der Schritte 1070 und 1080, die durch den Prozeß PN im wesentlichen parallel zu der Verarbeitung des Prozesses P&sub0; und aller anderen überwachten Prozesse verarbeitet wird.
Nachdem alle überwachten Prozesse die Verarbeitung der neuberechneten Wiederherstellungslinie 310 abgeschlossen haben, kehrt die Programmsteuerung während Schritt 1090 zu dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zurück, und die normale Ausführung wird für jeden überwachten Prozeß P&sub0; bis PN fortgesetzt. Wenn der zuvor erkannte Fehler umgangen wird, dann fährt die Programmsteuerung fort. Wenn der Fehler nicht umgangen wird, dann erkennt der Fehlererkennungsüberwacher 20 den Fehler erneut und leitet den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 dieses Mal mit Schritt 4 als Versuch erneut ein.

Schritt 4 - Sender-Umordnung

Wie bereits erwähnt, führt der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 während Schritt 4 des progressiven Wiederholungsversuchsverfahrens die Sender-Umordnungs-Subroutine 1100 aus. Die Sender-Umordnungs-Subroutine (Schritt. 4) 1100 beginnt im Schritt 1101 (siehe Fig. 11). Während Schritt 4 Wiederholungsversuch vergrößert der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 den Umfang der Wiederherstellung und den Grad der Unbestimmtheit, indem Prozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben, an der Wiederherstellung beteiligt werden, und bewirkt wird, daß diese die im Übergang befindlichen Nachrichten in ihrer Empfänger-Protokolldatei 90 umordnen, bevor sie sie erneut verarbeiten. Während der erneuten Verarbeitung der umgeordneten im Übergang befindlichen Nachrichten können die Prozesse, die zuvor Nachrichten zu dem fehlerhaften Prozeß gesendet haben, wieder Nachrichten zu dem fehlerhaften Prozeß senden.
Die dem fehlerhaften Prozeß zugeordnete Überwachungsvorrichtung 15 verwirft dann anfänglich die Verarbeitungsreihenfolgeninformationen während Schritt 1110 für alle Nachrichten in der Empfänger- Protokolldatei 90 nach dem logischen Fixpunkt, der vor der ersten zu dem fehlerhaften Prozeß gesendeten Nachricht liegt, für alle Prozesse, die seit dem letzten eigentlichen Fixpunkt Nachrichten zu dem fehlerhaften Prozeß gesendet haben. Dies dient zur Invalidierung aller logischen Fixpunkte nach der ersten zu dem fehlerhaften Prozeß gesendeten Nachricht seit dem letzten eigentlichen Fixpunkt für alle Prozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben.
Danach sendet die dem fehlerhaften Prozeß zugeordnete Überwachungsvorrichtung 15 während Schritt 1120 zu dem zentralen Wiederherstellungskoordinator 75 eine Anforderung zur Neuberechnung der Wiederherstellungslinie 310 für eine Schritt-4-Wiederherstellung mit einer Anzeige des fehlerhaften Prozesses. Die Art und Weise der Verarbeitung der Anforderung und der Neuberechnung der Wiederherstellungslinie durch den zentralen Wiederherstellungskoordinator 75 wird nachfolgend in Verbindung mit Fig. 15a und Fig. 15b besprochen. Während einer Schritt-4-Wiederherstellung verwirft der zentrale Wiederherstellungskoordinator 75 im allgemeinen alle logischen Fixpunkte nach der ersten Nachricht, die zu dem fehlerhaften Prozeß gesendet wurde, für alle die Prozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben.
Wenn der zentrale Wiederherstellungskoordinator 75 die Wiederherstellungslinie neu berechnet hat, sendet er die neuberechneten Wiederherstellungslinieninformationen zu jedem überwachten Anwendungsprozeß.
Bei Empfang der neuberechneten Wiederherstellungslinie verarbeitet jeder überwachte Prozeß die Wiederherstellungslinie im wesentlichen parallel und bestimmt die entsprechende Reaktion, wie durch die Verarbeitungszweige 1130 und 1140 in Fig. 11 für die Prozesse P&sub0; bzw. PN gezeigt.
Der Prozeß P&sub0; empfängt die gesendete Wiederherstellungslinie 310 aus dem zentralen Wiederherstellungskoordinator 75 während Schritt 1150. Danach wird die nachfolgend in Verbindung mit Fig. 13 besprochene Prozeß-Nachrichtenprotokoll-Subroutine 1300 während Schritt 1160 für den Prozeß P&sub0; ausgeführt.
Wie in Fig. 6f gezeigt, wurden alle logischen Fixpunkte nach der ersten zu dem fehlerhaften Prozeß gesendeten Nachricht für die Prozesse, die Nachrichten zu dem fehlerhaften Prozeß P&sub2; gesendet haben, verworfen. Somit muß der Prozeß P&sub1; logisch zu dem logischen Fixpunkt L1,1 zurückfahren, und der Prozeß P&sub2; muß logisch zu dem logischen Fixpunkt L3,1 zurückfahren. Da der Prozeß P&sub2; das Senden der Nachricht Ms rückgängig machen muß, muß der Prozeß P&sub4; an der Wiederholung teilnehmen. Wie in Fig. 11 gezeigt, empfängt und verarbeitet der Prozeß PN die gesendete Wiederherstellungslinie 310 während der Schritte 1170 und 1180, die durch den Prozeß PN im wesentlichen parallel zu der Verarbeitung des Prozesses P&sub0; und aller anderen überwachten Prozesse verarbeitet wird.
Nachdem alle überwachten Prozesse die Verarbeitung der neuberechneten Wiederherstellungslinie 310 abgeschlossen haben, kehrt die Programmsteuerung während Schritt 1190 zu dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zurück, und die normale Ausführung wird für jeden überwachten Prozeß P&sub0; bis PN fortgesetzt. Wenn der zuvor erkannte Fehler umgangen wird, dann fährt die Programmsteuerung fort. Wenn der Fehler nicht umgangen wird, dann erkennt der Fehlererkennungsüberwacher 20 den Fehler erneut und leitet den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 dieses Mal mit Schritt S als Versuch erneut ein.

Schritt 5 - Wiederholung mit großem Umfang

Wenn alle lokalisierten Wiederholungsversuche, die während der Schritte 1 bis 4 des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 durchgeführt wurden, bei der Umgehung des Softwarefehlers bzw. der Softwarefehler erfolglos blieben, dann setzt der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 die global konsequente Menge von Fixpunkten ein, um eine Wiederholung mit großem Umfang zu implementieren.
Wie bereits erwähnt, führt der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 während Schritt S des progressiven Wiederholungsversuchsverfahrens die Wiederholungsversuchs-Subroutine 1200 mit Wiederholung mit großem Umfang aus. Die Wiederholungsversuchs-Subroutine mit Wiederholung mit großem Umfang (Schritt S) 1200 beginnt im Schritt 1201 (siehe Fig. 12). Die dem fehlerhaften Prozeß zugeordnete Überwachungsvorrichtung 15 sendet während Schritt 1220 zu dem zentralen Wiederherstellungskoordinator 75 eine Anforderung zur Neuberechnung der Wiederherstellungslinie 310 für eine Schritt-5-Wiederherstellung. Die Art und Weise der Verarbeitung der Anforderung und der Neuberechnung der Wiederherstellungslinie durch den zentralen Wiederherstellungskoordinator 75 wird nachfolgend in Verbindung mit Fig. 15a und Fig. 15b besprochen.
Wenn der zentrale Wiederherstellungskoordinator 75 die Wiederherstellungslinie neu berechnet hat, sendet er die neuberechneten Wiederherstellungslinieninformationen zu jedem überwachten Anwendungsprozeß. Bei Empfang der neuberechneten Wiederherstellungslinie verarbeitet jeder überwachte Prozeß die Wiederherstellungslinie im wesentlichen parallel und bestimmt die entsprechende Reaktion, die durch die Verarbei tungszweige 1230 und 1240 in Fig. 12 für die Prozesse P&sub0; bzw. PN gezeigt sind.
Der Prozeß P&sub0; empfängt die gesendete Wiederherstellungslinie 310 aus dem zentralen Wiederherstellungskoordinator 75 während Schritt 1250. Danach wird die nachfolgend in Verbindung mit Fig. 13 besprochene Prozeß-Nachrichtenprotokoll-Subroutine 1300 während Schritt 1260 für den Prozeß P&sub0; ausgeführt.
Ähnlich empfängt und verarbeitet der Prozeß PN die gesendete Wiederherstellungslinie 310 während der Schritte 1270 und 1280, die durch den Prozeß PN im wesentlichen parallel zu der Verarbeitung des Prozesses Po und aller anderen überwachten Prozesse verarbeitet werden.
Nachdem alle überwachten Prozesse die Verarbeitung der neuberechneten Wiederherstellungslinie 310 abgeschlossen haben, kehrt die Programmsteuerung während Schritt 1290 zu dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zurück, und die normale Ausführung wird für jeden überwachten Prozeß P&sub0; bis PN fortgesetzt. Wenn der zuvor erkannte Fehler umgangen wird, dann fährt die Programmsteuerung fort. Wenn der Fehler nicht umgangen wird, dann erkennt der Fehlererkennungsüberwacher 20 den Fehler erneut und leitet den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 dieses Mal mit einer Anforderung eines vollen Neustarts des Systems erneut ein.

Wiederherstellungs-Wiedergabesubroutinen

Wie bereits erwähnt, wird die Prozeß- Nachrichtenprotokoll-Subroutine 1300 für einen oder mehrere Prozesse während jedes Schrittes des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 ausgeführt. Die Prozeß- Nachrichtenprotokollsubroutine 1300 klassifiziert alle Nachrichten in der Empfänger-Protokolldatei 90 des zugeordneten Prozesses auf der Grundlage der neuberechneten Wiederherstellungslinie. Danach leitet die Prozeß-Nachrichtenprotokollsubroutine 1300 die Wiedergabe der deterministischen Nachrichten und das Neusenden der im Übergang befindlichen Nachrichten ein. Zusätzlich ordnet die Prozeß-Nachrichtenprotokollsubroutine 1300 die im Übergang befindlichen Nachrichten für den fehlerhaften Prozeß in einem Schritt-2- Wiederholungsversuch und für alle Prozesse um, die Nachrichten für einen Schritt-4-Wiederholungsversuch zu dem fehlerhaften Prozeß gesendet haben. Es ist zu beachten, daß die Prozeß-Nachrichtenprotokollsubroutine 1300 im wesentlichen parallel durch eine Anzahl verschiedener Anwendungsprozesse separat ausgeführt werden kann.
Ein gegebener Prozeß beginnt die Prozeß- Nachrichtenprotokollsubroutine 1300 im Schritt 1301. Während Schritt 1310 wird geprüft, ob der aktuelle Prozeßzustand des Anwendungsprozesses, der die Prozeß- Nachrichtenprotokollsubroutine 1300 ausführt, an der Wiederherstellungslinie liegt. Wenn während Schritt 1310 bestimmt wird, daß der aktuelle Prozeßzustand des Anwendungsprozesses, der die Prozeß-Nachrichtenprotokollsubroutine 1300 ausführt, bereits an der Wiederherstellungslinie liegt, dann muß der Anwendungsprozeß keine Verarbeitung zur Zustandsrekonstruktion durchführen. Somit kehrt die Programmsteuerung während Schritt 1380 zu der aufrufenden Funktion zurück.
Wenn jedoch während Schritt 1310 bestimmt wird, daß der aktuelle Prozeßzustand des Anwendungsprozesses, der die Prozeß-Nachrichtenprotokollsubroutine 1300 ausführt, nicht an der Wiederherstellungslinie liegt, dann werden alle Nachrichten in der Empfänger- Protokolldatei 90 des zugeordneten Anwendungsprozesses als deterministisch, im Übergang befindlich oder Waisenprozesse klassifiziert, so wie es oben in Verbindung mit Fig. 3 definiert wurde.
Alle Waisennachrichten für den Anwendungsprozeß, der die Prozeß-Nachrichtenprotokollsubroutine 1300 ausführt, die nicht mehr gültig sind, weil sie nach der Wiederherstellungslinie gesendet wurden, werden während Schritt 1330 verworfen.
Danach fährt der Anwendungsprozeß während Schritt 1340 zu seinem letzten eigentlichen Fixpunkt zurück und leitet dann die deterministische Wiedergabesubroutine 1400 ein, die nachfolgend in Verbindung mit Fig. 14a und 14b beschrieben wird, um die deterministischen Nachrichten für den Anwendungsprozeß bis zu der Wiederherstellungslinie wiederzugeben. Danach wird im Schritt 1350 geprüft, ob die der neuberechneten Wiederherstellungslinie beigefügte Nachricht anzeigt, daß der aktuelle Anwendungsprozeß seine im Übergang befindlichen Nachrichten umordnen sollte. Es ist zu beachten, daß der fehlerhafte Prozeß für den Schritt 2 Wiederholungsversuch seine Nachrichten umordnet, und die Prozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben, ihre Nachrichten für Schritt 4 Wiederholungsversuch umordnen. Bei einer bevorzugten Ausführungsform überträgt der zentrale Wiederherstellungskoordinator 75 einen Nachrichtenvektor mit der neuberechneten Wiederherstellungslinie, wie nachfolgend in Verbindung mit Fig. 15a und 15b besprochen wird. Der Nachrichtenvektor weist ein Feld für jeden überwachten Prozeß auf. Wenn ein bestimmter Prozeß seine im Übergang befindlichen Nachrichten umordnen sollte, dann wird das entsprechende Feld des Nachrichtenvektors vorzugsweise auf einen Binärwert von "01" gesetzt.
Bei einer bevorzugten Ausführungsform wird eine Mehrzahl von Optionen zur Umordnung der im Übergang befindlichen Nachrichten während der Wiederholungsversuche Schritt 2 und Schritt 4 bereitgestellt. Bei einer Vorgabe-Umordnungsoption werden die im Übergang befindlichen Nachrichten vorzugsweise mit verschiedenen Bezugskennungen auf eine zufällige Weise umgeordnet, es wird aber vorzugsweise die Reihenfolge der Nachrichten aus demselben Sender mit derselben Bezugskennung aufrechterhalten. Somit kann durch Angabe einer Bezugskennung beim Senden einer Nachricht die Nachrichtenabhängigkeit erforderlichenfalls erzwungen werden. Alternative Umordnungsoptionen können Nachrichten aus denselben Prozessen zusammengruppieren, Nachrichten ausführen, die das Freigeben von Betriebsmitteln anfordern, bevor Nachrichten, die die Zuteilung von Betriebsmitteln anfordern, ausgeführt werden, und können die Reihenfolge umkehren, wenn nur zwei Nachrichten in dem Nachrichtenprotokoll vorliegen.
Wenn während Schritt 1350 bestimmt wird, daß der aktuelle Anwendungsprozeß seine im Übergang befindlichen Nachrichten umordnen sollte, dann werden die Nachrichten angemessenerweise vor ihrer Wiedergabe und erneuten Verarbeitung während Schritt 1370 umgeordnet. Wenn jedoch während Schritt 1350 bestimmt wird, daß der aktuelle Anwendungsprozeß seine im Übergang befindlichen Nachrichten nicht umordnen sollte, dann werden die Nachrichten einfach zur Übertragung zu dem entsprechenden Anwendungsprozeß während Schritt 1360 erneut an den Kommunikationskanal übergeben. Danach schreitet die Programmsteuerung zum Schritt 1380 weiter, in dem die Steuerung zu der aufrufenden Funktion zurückkehrt.
Wie bereits erwähnt, wird die deterministische Wiedergabesubroutine 1400 während Schritt 1340 der Prozeß-Nachrichtenprotokollsubroutine 1300 ausgeführt, nachdem der Anwendungsprozeß zu seinem letzten eigentlichen Fixpunkt zurückgefahren wird. Die deterministische Wiedergabesubroutine 1400 gibt deterministisch alle deterministischen Nachrichten in der Empfänger- Protokolldatei 90 eines Anwendungsprozesses wieder, und erleichtert dadurch die Zustandsrekonstruktion. Zusätzlich enthält die deterministische Wiedergabesubroutine 1400 vorzugsweise einen Mechanismus zum Verifizieren der Annahme der stückweisen Bestimmtheit, der nachfolgend besprochen wird.
Die deterministische Wiedergabesubroutine 1400 beginnt im Schritt 1401. Danach ruft die deterministische Wiedergabesubroutine 1400 während Schritt 1410 die aktuelle Nachricht aus der Empfänger-Protokolldatei 90 des aktuellen Anwendungsprozesses ab und verarbeitet dann während Schritt 1415 die abgerufene Nachricht. Im Schritt 1420 wird geprüft, ob die Verarbeitung der aktuellen abgerufenen Nachricht durch den Anwendungsprozeß eine oder mehrere zu sendende Nachrichten erzeugt. Wenn im Schritt 1420 bestimmt wird, daß die Verarbeitung der aktuellen abgerufenen Nachricht durch den Anwendungsprozeß keine zu sendenden Nachrichten erzeugt, dann schreitet die Programmsteuerung zum Schritt 1445 weiter, der nachfolgend besprochen wird.
Wenn jedoch während Schritt 1420 bestimmt wird, daß die Verarbeitung der aktuellen abgerufenen Nachricht durch den Anwendungsprozeß mindestens eine zu sendende Nachricht erzeugt, dann wird während Schritt 1425 eine Prüfung durchgeführt, um die Annahme der stückweisen Bestimmtheit zu verifizieren, indem verifiziert wird, daß die während des aktuellen Schritts der Wiederherstellung erneut hergestellte Nachricht identisch mit der während der anfänglichen Ausführung in der Sender-Protokolldatei 92 gespeicherten Nachricht ist.
Wenn während Schritt 1425 bestimmt wird, daß die wiederhergestellte Nachricht mit der in der Sender- Protokolldatei 92 gespeicherten Nachricht identisch ist, dann wird während Schritt 1430 geprüft, ob die in der neuberechneten Wiederherstellungslinie enthaltene Nachricht anzeigt, daß der aktuelle Anwendungsprozeß tatsächlich die wiederhergestellten Nachrichten senden sollte, wenn die wiederhergestellte Nachricht, für den fehlerhaften Prozeß bestimmt ist. Es ist zu beachten, daß Prozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben, diese Nachrichten während Schritt 3 Wiederholungsversuch erneut senden. Bei einer bevorzugten Ausführungsform sendet der zentrale Wiederherstellungskoordinator 75 einen Nachrichtenvektor mit der neuberechneten Wiederherstellungslinie, was nachfolgend in Verbindung mit Fig. 15a und 15b besprochen wird. Der Nachrichtenvektor weist ein Feld für jeden überwachten Prozeß auf. Wenn ein bestimmter Prozeß während Schritt 3 Wiederholungsversuch Nachrichten erneut zu dem fehlerhaften Prozeß senden sollte, dann wird das entsprechende Feld in dem Nachrichtenvektor vorzugsweise auf einen binären Wert von "10" gesetzt.
Wenn während Schritt 1430 bestimmt wird, daß die in der neuberechneten Wiederherstellungslinie enthaltene Nachricht nicht anzeigt, daß der aktuelle Anwendungsprozeß tatsächlich die wiederhergestellten Nachrichten senden sollte, dann schreitet die Programmsteuerung zu dem nachfolgend besprochenen Schritt 1440 weiter, ohne die Nachricht zu übertragen. Wenn jedoch während Schritt 1430 bestimmt wird, daß die in der neuberechneten Wiederherstellungslinie enthaltene Nachricht anzeigt, daß der aktuelle Anwendungsprozeß tatsächlich die wiederhergestellten Nachrichten senden sollte und die wiederhergestellte Nachricht für den fehlerhaften Prozeß bestimmt ist, dann wird die Nachricht während Schritt 1435 zu dem fehlerhaften Prozeß übertragen.
Während Schritt 1440 wird geprüft, ob zusätzliche zu sendende Nachrichten auf der Grundlage der Verarbeitung der aktuellen empfangenen Nachricht vorliegen. Wenn während Schritt 1440 bestimmt wird, daß zusätzliche zu sendende Nachrichten auf der Grundlage der Verarbeitung der aktuellen empfangenen Nachricht vorliegen, dann kehrt die Programmsteuerung zu dem Schritt 1425 zurück und fährt auf die oben beschriebene Weise fort.
Wenn jedoch während Schritt 1440 bestimmt wird, daß keine zusätzlichen zu sendenden Nachrichten auf der Grundlage der Verarbeitung der aktuellen empfangenen Nachricht vorliegen, dann schreitet die Programmsteuerung zum Schritt 1445 weiter.
Während Schritt 1445 wird geprüft, ob zusätzliche zu verarbeitende deterministische Nachrichten in der Empfänger-Protokolldatei 90 vorliegen. Wenn während Schritt 1445 bestimmt wird, daß zusätzliche zu verarbeitende deterministische Nachrichten in der Empfänger-Protokolldatei 90 vorliegen, dann kehrt die Programmsteuerung zum Schritt 1415 zurück und fährt auf die oben beschriebene Weise fort.
Wenn jedoch während Schritt 1445 bestimmt wird, daß keine zusätzlichen zu verarbeitenden deterministischen Nachrichten in der Empfänger-Protokolldatei 90 vorliegen, dann kehrt die Programmsteuerung während Schritt 1447 zu der Prozeß-Nachrichtenprotokollsubroutine 1300 zurück.
Wenn jedoch während Schritt 1425 bestimmt wurde, daß die wiederhergestellte Nachricht nicht mit der in der Sender-Protokolldatei 92 gespeicherten Nachricht identisch ist, dann ist ein nichtdeterministisches Ereignis eingetreten, und die Annahme der stückweisen Bestimmtheit kann nicht befolgt werden. Somit werden alle logischen Fixpunkte für den aktuellen Anwendungsprozeß während Schritt 1450 (Fig. 14b) nach dem nichtdeterministischen Ereignis verworfen.
Die dem aktuellen Anwendungsprozeß zugeordnete Überwachungsvorrichtung 15 sendet dann während Schritt 1455 zu dem zentralen Wiederherstellungskoordinator 75 eine Anforderung zur Neuberechnung der Wiederherstellungslinie 310. Die Art und Weise der Verarbeitung und der Neuberechnung der Wiederherstellungslinie durch den zentralen Wiederherstellungskoordinator 75 wird nachfolgend in Verbindung mit Fig. 15a und 15b besprochen.
Wenn der zentrale Wiederherstellungskoordinator 75 die Wiederherstellungslinie neu berechnet hat, sendet er die neuberechneten Wiederherstellungslinieninformationen zu jedem überwachten Anwendungsprozeß. Bei Empfang der neuberechneten Wiederherstellungslinie verarbeitet jeder überwachte Prozeß die Wiederherstellungslinie im wesentlichen parallel und bestimmt die entsprechende Reaktion, wie durch die Verarbeitungszweige 1460 und 1465 in Fig. 14b für die Prozesse Po bzw. PN gezeigt.
Der Prozeß P&sub0; empfängt die gesendete Wiederherstellungslinie 310 aus dem zentralen Wiederherstellungskoordinator 75 während Schritt 1470. Danach wird die oben in Verbindung mit Fig. 13 besprochene Prozeß-Nachrichtenprotokoll-Subroutine 1300 während Schritt 1475 für den Prozeß P&sub0; erneut ausgeführt. Ähnlich empfängt und verarbeitet der Prozeß PN die gesendete Wiederherstellungslinie 310 während der Schritte 1480 und 1485, die durch den Prozeß PN im wesentlichen parallel zu der Verarbeitung des Prozesses P&sub0; und aller anderen überwachten Prozesse verarbeitet wird.
Nachdem alle überwachten Prozesse die Verarbeitung der neuberechneten Wiederherstellungslinie 310 abgeschlossen haben, kehrt die Programmsteuerung während Schritt 1490 zu dem progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zurück, und die normale Ausführung wird für jeden überwachten Prozeß P&sub0; bis PN fortgesetzt. Wenn der zuvor erkannte Fehler umgangen wird, dann fährt die Programmsteuerung fort. Wenn der Fehler nicht umgangen wird, dann erkennt der Fehlererkennungsüberwacher 20 den Fehler erneut und leitet erneut den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 ein.

Wiederherstellungslinienberechnung

Wie bereits erwähnt, sendet die den fehlerhaften Prozeß überwachende Überwachungsvorrichtung 15 bei jedem der Schritte 2 bis 5 des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 dem zentralen Wiederherstellungskoordinator 75 Anforderungen zur Neuberechnung der Wiederherstellungslinie. Der zentrale Wiederherstellungskoordinator 75 verarbeitet diese Anforderungen durch Ausführen des Wiederherstellungslinienberechnungsalgorithmus 1500, der in Fig. 15a und Fig. 15b gezeigt ist. Der Wiederherstellungslinienberechnungsalgorithmus 1500 beginnt im Schritt 1505 beim Empfang einer Anforderung für eine Berechnung der Wiederherstellungslinie. Wie bereits erwähnt, enthalten Wiederherstellungslinienberechnungsanforderungen eine Anzeige des aktuellen Schritts des progressiven Wiederholungsversuchs- Wiederherstellungsalgorithmus 700 und eine Anzeige des fehlerhaften Prozesses.
Danach setzt der Wiederherstellungslinienberechnungsalgorithmus 1500 während Schritt 1510 einen Nachrichtenvektor zurück, der mit der neuberechneten Wiederherstellungslinie gesendet wird. Es ist zu beachten, daß der Nachrichtenvektor bei einer bevorzugten Ausführungsform ein Feld für die Übertragung einer Nachricht zu jedem überwachten Anwendungsprozeß enthält. Ein binärer Nachrichtenwert von 00 zeigt vorzugsweise an, daß sich der zugeordnete Anwendungsprozeß in einer normal-Betriebsart befindet. Ein binärer Nachrichtenwert von 01 zeigt vorzugsweise an, daß der zugeordnete Anwendungsprozeß die Nachrichten in seiner Empfänger-Protokolldatei 90 umordnen sollte, bevor sie wiedergegeben und erneut verarbeitet werden. Als letztes zeigt ein binärer Nachrichtenwert von 10 vorzugsweise an, daß der zugeordnete Anwendungsprozeß tatsächlich während Schritt 3 Wiederholungsversuch Nachrichten erneut zu dem fehlerhaften Anwendungsprozeß senden sollte.
Während Schritt 1515 wird geprüft, ob der Wert der Zählervariablen N, die durch den progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 gesteuert wird und die aktuelle Schrittnummer bestimmt, gleich zwei ist. Wenn während Schritt 1515 bestimmt wird, daß der Wert der Zählervariablen N gleich zwei ist, dann berechnet der zentrale Wiederherstellungskoordinator 75 die Wiederherstellungslinie zum ersten Mal neu, um eine Wiederherstellung nach dem aktuellen Fehler zu bewirken. Es ist zu beachten, daß der zentrale Wiederherstellungskoordinator 75 an der Schritt 1 Wiederherstellung nicht beteiligt ist.
Somit sendet der zentrale Wiederherstellungskoordinator 75 während Schritt 1520 eine Nachricht zu allen überwachten Anwendungsprozessen, die die Abhängigkeitsinformationen für alle Nachrichten in ihrer Empfänger-Protokolldatei 90 anfordert. Der zentrale Wiederherstellungskoordinator 75 empfängt während Schritt 1525 die übertragenen Abhängigkeitsinformationen aus jedem überwachten Prozeß.
Es ist zu beachten, daß der fehlerhafte Prozeß die Verarbeitungsreihenfolgeninformationen für die Nachrichten in seiner Empfänger-Protokolldatei 90 nach dem letzten eigentlichen Fixpunkt während der Ausführung der Empfänger-Umordnungssubroutine (Schritt 2) 900 verworfen hat, um die logischen Fixpunkte nach der ersten empfangenen Nachricht zu invalidieren. Dementsprechend sollte der Wiederherstellungslinienberechnungsalgorithmus 1500 während Schritt 1528 die logischen Fixpunkte für den fehlerhaften Prozeß aus den Abhängigkeitsinformationen nach der ersten durch den fehlerhaften Prozeß seit seinem letzten eigentlichen Fixpunkt empfangenen Nachricht entfernen.
Während Schritt 2 Wiederholungsversuch sollte nur der fehlerhafte Prozeß Nachrichten in seiner Empfänger-Protokolldatei 90 umordnen. Dementsprechend setzt der Wiederherstellungslinienberechnungsalgorithmus 1500 während Schritt 1530 das Nachrichtenvektorfeld für den fehlerhaften Prozeß auf den binären Wert "01", der anzeigt, daß der fehlerhafte Prozeß seine im Übergang befindlichen Nachrichten in seiner Empfänger- Protokolldatei 90 umordnen sollte, bevor er sie wiedergibt und wieder verarbeitet. Danach schreitet die Programmsteuerung zum Schritt 1570 weiter (Fig. 15b).
Wenn jedoch während Schritt 1515 bestimmt wurde, daß der Wert der Zählervariablen N nicht gleich zwei ist, dann wird während Schritt 1535 geprüft, ob der Wert der Zählervariablen N gleich drei ist. Es ist zu beachten, daß für Schritt 3 Wiederholungsversuch der Wiederherstellungslinienberechnungsalgorithmus 1500 dieselbe Wiederherstellungslinie konstruiert, die für Schritt 2 Wiederholungsversuch bestimmt wurde, obwohl der Nachrichtenvektor modifiziert wird. Wenn während Schritt 1535 bestimmt wird, daß der Wert der Zählervariablen N gleich drei ist, dann setzt der Wiederherstellungslinienberechnungsalgorithmus 1500 während Schritt 1540 das Nachrichtenvektorfeld für alle überwachten Anwendungsprozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben, auf den binären Wert "10", der anzeigt, daß diese Prozesse tatsächlich die deterministischen Nachrichten in ihrer Empfänger-Protokolldatei 90 neu senden sollten. Danach schreitet die Programmsteuerung zum Schritt 1570 weiter (Fig. 15b). Wenn jedoch während Schritt 1535 bestimmt wurde, daß der Wert der Zählervariablen N nicht gleich drei ist, dann wird während Schritt 1545 geprüft, ob der Wert der Zählervariablen N gleich vier ist. Wenn während Schritt 1545 bestimmt wird, daß der Wert der Zählervariablen N gleich vier ist, dann entfernt der Wiederherstellungslinienberechnungsalgorithmus 1500 während Schritt 1550 für alle Prozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben, alle logischen Fixpunkte nach der ersten zu dem fehlerhaften Prozeß gesendeten Nachricht aus dem nachfolgend besprochenen Kommunikationsgraph.
Danach setzt der Wiederherstellungslinienberechnungsalgorithmus 1500 während Schritt 1555 für alle überwachten Anwendungsprozesse, die Nachrichten zu dem fehlerhaften Prozeß gesendet haben, das Nachrichtenvektorfeld auf den binären Wert "01", der anzeigt, daß diese Prozesse die im Übergang befindlichen Nachrichten in ihrer Empfänger-Protokolldatei 90 umordnen sollten, bevor sie sie wiedergeben und wieder verarbeiten. Danach schreitet die Programmsteuerung zum Schritt 1570 weiter (Fig. 15b).
Wenn jedoch während Schritt 1545 bestimmt wurde, daß der Wert der Zählervariablen N nicht gleich vier ist, dann wird während Schritt 1560 (Fig. 15b) geprüft, ob der Wert der Zählervariablen N gleich fünf ist. Wenn während Schritt 1560 bestimmt wird, daß der Wert der Zählervariablen N gleich fünf ist, dann verwirft der Wiederherstellungslinienberechnungsalgorith mus 1500 während Schritt 1565 alle logischen Fixpunkte für alle überwachten Prozesse, um eine Wiederholung mit großem Umfang aller überwachten Prozesse von ihrem letzten konsequenten globalen Fixpunkt aus einzuleiten. Danach schreitet die Programmsteuerung zum Schritt 1570 weiter (Fig. 15b).
Wenn die Programmsteuerung den Schritt 1570 (Fig. 15b) erreicht hat, dann hat der Wiederherstellungslinienberechnungsalgorithmus 1500 bereits die Abhängigkeitsinformationen während seiner ersten Ausführung für Schritt 2 Wiederholungsversuch gesammelt und gegebenenfalls die Abhängigkeitsinformationen während der Schritte 1550 und 1565 für Schritt 4 und Schritt S Wiederholungsversuch modifiziert. Der Wiederherstellungslinienberechnungsalgorithmus 1500 konstruiert während Schritt 1570 einen Kommunikationsgraph unter Verwendung der gegebenenfalls modifizierten Abhängigkeitsinformationen und setzt dann während Schritt 1580 den Wiederholungsfortpflanzungsalgorithmus und den konstruierten Kommunikationsgraph ein, um die Wiederherstellungslinie neu zu berechnen. Für eine Besprechung eines geeigneten Verfahrens zur Konstruktion eines Kommunikationsgraphs und zur Anwendung des Wiederholungsfortpflanzungsalgorithmus zur Berechnung der Wiederherstellungslinie, siehe Yi-Min Wang und W. Kent Fuchs, "Lazy Checkpoint Coordination for Bounding Rollback Propagation", Proc. IEEE Symposium Reliable Distributed Systems, S. 78-85 (Okt. 1993).
Danach sendet der Wiederherstellungslinienberechnungsalgorithmus 1500 die neuberechnete Wiederherstellungslinie zusammen mit dem Nachrichtenvektor zu allen überwachten Anwendungsprozessen zur Verarbeitung auf die oben beschriebene Weise.

Fehlerumgehung durch Nachrichtenumordnung

Wenn Informationen bezüglich der Beschaffenheit eines bestimmten Fehlers gewonnen werden können, kann es angemessen sein, direkt zu den Umordnungsschritten des progressiven Wiederholungsversuchs-Wiederherstel lungsalgorithmus 700 fortzuschreiten. Es ist zu beachten, daß die Wiedergabeschritte des progressiven Wiederholungsversuchs-Wiederherstellungsalgorithmus 700, nämlich Schritte 1 und 3, zur Umgehung von Softwarefehlern in Anwendungsprozessen mit nichtdeterministischem Verhalten geeignet sind. Die Wiedergabeschritte eignen sich jedoch nicht für die Umgehung von Fehlern in Anwendungsprozessen, die deterministisches Verhalten aufweisen, oder anders ausgedrückt, Anwendungsprozesse, die sich bei denselben gegebenen Eingaben auf dieselbe Weise verhalten. Dementsprechend sollte die Wiederherstellung für einen bestimmten Anwendungsprozeß, von dem bekannt ist, daß er deterministisches Verhalten aufweist, direkt zu den Umordnungsschritten, nämlich den Schritten 2 und 4, fortschreiten.
Bei einer Ausführungsform kann die fehlertolerante Bibliothek 82 eine Funktion enthalten, die beim Aufruf durch einen Anwendungsprozeß ein nichtdeterministisches Bit setzt, das anzeigt, daß der Prozeß zum Teil nichtdeterministisches Verhalten enthält, wie zum Beispiel ein zeitabhängiges Ereignis, ein Versagen eines Systemaufrufs oder eine Signalunterbrechung. Dementsprechend kann das Neustart- Teilsystem 30 bei Erkennung eines Fehlers in dem Anwendungsprozeß durch den Fehlererkennungsüberwacher 20 den Wert des nichtdeterministischen Bit auswerten, um zu bestimmen, ob das Bit durch den Anwendungsprozeß gesetzt wurde. Wenn das Bit gesetzt wurde, dann sollte die Wiederherstellung mit einem Schritt 1 Wiederholungsversuch beginnen. Wenn das Bit jedoch nicht gesetzt wurde, sollte die Wiederherstellung direkt zu den Umordnungsschritten fortschreiten, die zur Umordnung der Folge der durch den fehlerhaften Prozeß empfangenen Eingangssignale dienen. Es ist zu beachten, daß die Folgeeingangssignale, die durch den fehlerhaften Prozeß empfangen werden, Nachrichten, Dateien, Ereignisse, Operationen oder andere Daten sein können.
Zusätzlich sollte eine Wiederherstellung nach Softwarefehlern, von denen bekannt ist, daß sie das Ergebnis eines Betriebsmittelzuteilungsproblems sind, wie zum Beispiel eines Engpasses von Betriebsmitteln, ebenfalls direkt zum Schritt 2 Umordnung fortschreiten. Wenn zum Beispiel ein System nur zwei Dateidescriptoren besitzt und das System drei aufeinanderfolgende Anforderungen zur Öffnung von Dateien ohne dazwischentretende Anforderungen zum Schließen einer Datei empfängt, dann erschöpft das System die Dateidescriptoren, was zu einem Betriebsmittelzuteilungsproblem führt. Wenn das System jedoch die Folge seiner Eingangssignale umordnen würde, könnten einige Anforderungen zum Schließen von Dateien vor der dritten Anforderung zum Öffnen einer Datei verarbeitet werden, wodurch der Softwarefehler umgangen wird.
Außerdem sollte eine Wiederherstellung nach Softwarefehlern, von denen bekannt ist, daß sie das Ergebnis von Überlauffehlern (racing bugs) sind, bei denen der Prozeß annimmt, daß die Eingangssignale in einer bestimmten Reihenfolge eintreffen, sie aber tatsächlich in einer anderen Reihenfolge eintreffen, ebenfalls zum Schritt 2 Umordnung fortschreiten. Wenn die Folge von Eingangssignalen umgeordnet wird, können sie auf diese Weise die ordnungsgemäße Reihenfolge annehmen und dadurch den Softwarefehler umgehen.

Beispiele

Schritt 1 Wiederholungsversuch - Beispiel

Wenn ein System mehrere Prozesse enthält, die auf gemeinsam benutzte Datenstrukturen zugreifen, und der Verriegelungsmechanismus zur Sicherstellung des Zugriffs mit gegenseitiger Ausschließung einen Fehler enthält oder nicht im System vorliegt, dann besteht die Möglichkeit, daß ein Prozeß versucht, eine Datenstruktur zu lesen, während ein anderer Prozeß die Datenstruktur aktualisiert, indem er zum Beispiel die Zeiger manipuliert, um einen neuen Datenknoten einzufügen. In einem solchen Fall empfängt der lesende Prozeß einen Segmentierungsverletzungsfehler, der durch die Überwachungsvorrichtung 15 erkannt wird, die dann eine Wiederherstellung einleitet. Wenn der lesende Prozeß neu gestartet wurde und die Anforderungsnachricht zum Zugriff auf dieselbe Datenstruktur während eines Schritt- 1-Wiederholungsversuchs erneut wiedergibt, dann hat die Leseoperation Erfolg, weil der Prozeß, der clie Datenstruktur aktualisiert, wahrscheinlich die Aktualisierung beendet hat.
Es ist zu beachten daß, obwohl diese Art von Fehler vermieden werden könnte, indem ein Verriegelungsmechanismus zur Garantierung des Zugriffs mit gegenseitiger Ausschließung bereitgestellt wird, eine Verriegelung mit grober Auflösung zu einer unnötigen Blockierung der Leserprozesse führt, und eine Verriegelung mit feiner Auflösung eine große Verschlechterung der Leistung hervorrufen und zusätzliche Softwarekomplexität einführen kann. Somit stellt die Nachrichtenwiedergabe von Schritt 1 des progressiven Wiederholungsversuchsverfahrens eine zuverlässige und effiziente Alternative zu dem Verriegelungsmechanismus zur Behandlung des Gleichzeitigkeitsproblems bereit.

Schritt 2 Wiederholungsversuch - Beispiel

Ein Dateisystem zum Halten von Dateien setzt oft drei Hauptoperationen ein: Öffnen einer Datei, Beschreiben einer Datei und Schließen einer Datei. Da die Anzahl von Dateidescriptoren, mit denen eine Datei identifiziert werden kann, begrenzt ist, könnten dem Dateisystem die Dateidescriptoren ausgehen. Dementsprechend muß das Dateisystem mitverfolgen, wieviele Dateien gerade offen sind. Wenn alle Dateidescriptoren verwendet werden, tritt eine Grenzbedingung ein. Wenn der Betriebsmittelverwalter, der die Grenzbedingung behandelt, einen Fehler aufweist, dann hängt das Dateisystem jedesmal, wenn die Grenzbedingung auftritt.
Das folgende Beispiel zeigt, wie die Schritt-2- Nachrichtenumordnung die Grenzbedingung in dem Dateisystem umgehen kann, wobei der Befehl O&sub1; das Öffnen der Datei 1 darstellt, der Befehl W&sub1; das Schreiben von Daten in die Datei 1 darstellt und der Befehl C&sub1; das Schließen der Datei 1 darstellt, und das Dateisystem höchstens 2 offene Dateien auf einmal aufweisen kann. Wenn das Dateisystem die folgende Befehlssequenz empfängt:
O&sub1; O&sub2; W&sub1; W&sub2; O&sub3; W&sub3; C&sub1; C&sub2;
dann tritt das Dateisystem in die Grenzbedingung ein, wenn es O&sub3; verarbeitet, und hängt. Der Softwarefehler wird durch die Überwachungsvorrichtung 15 erkannt, die einen Neustart des fehlerhaften Prozesses einleitet. Es ist zu beachten, daß dieser Fehler durch einen Schritt-1-Wiederholungsversuch nicht umgangen wird, weil die Grenzbedingung immer noch auftritt, wenn die Nachrichten aus der Empfänger-Protokolldatei 90 in derselben Reihenfolge wiedergegeben werden. Somit schreitet der progressive Wiederholungsversuchs-Wiederherstellungsalgorithmus 700 zu einem Schritt-2-Wiederholungsversuch fort. Die Nachrichtensequenz kann während einem Schritt-2-Wiederholungsversuch folgendermaßen umgeordnet werden:
O&sub1; W&sub1; C&sub1; O&sub2; W&sub2; C&sub2; O&sub3; W&sub3;.
Wenn diese umgeordneten Nachrichten dann durch den fehlerhaften Prozeß wiedergegeben und wieder verarbeitet werden, dann tritt die Grenzbedingung nicht auf, und der Softwarefehler wird umgangen.

Schritt 3 Wiederholungsversuch - Beispiel

In einem Querverbindungssystem wird ein Kanalsteuerüberwacherprozeß (CCM-Prozeß, CCM - Channel Control Monitor) eingesetzt, um die verfügbaren Kanäle in einer Telekommunikationsvermittlung mitzuverfolgen. Der CCM-Prozeß empfängt Nachrichten von zwei anderen Prozessen: einem Kanalzuteilungsprozeß (CA-Prozeß, CA - Channel Allocation), der die Kanalzuteilungsanforderungen sendet, und einem Kanal-Zuteilungsauflösungsprozeß (CD-Prozeß, CD - Channel Deallocation), der die Kanal-Zuteilungsauflösungsanforderungen sendet. Eine Grenzbedingung für den CCM-Prozeß tritt ein, wenn alle Kanäle belegt sind und der Prozeß zusätzliche Zutei lungsanforderungen empfängt. Wenn die Grenzbedingung eintritt, wird eine Aufräumprozedur aufgerufen, um einige Kanäle freizugeben oder weitere Anforderungen zu blockieren. Wenn die Aufräumprozedur jedoch einen Softwarefehler enthält, dann kann die Aufräumprozedur abstürzen, wenn der Fehler ausgelöst wird.
Das folgende Beispiel zeigt, wie die Schritt-3- Nachrichtenwiedergabe eingesetzt werden kann, um den Fehler zu umgehen, wobei die Anzahl verfügbarer Kanäle gleich 5 ist, der Befehl r&sub2; die Anforderung zweier Kanäle darstellt und der Befehl f&sub2; das Freigeben zweier Kanäle darstellt. Aufgrund der Grenzbedingung könnte die folgende Befehlssequenz einen Absturz des CCM- Prozesses verursachen:
Somit stürzt der CCM-Prozeß beim Empfang des r&sub1;-Befehls ab, wodurch die Grenzbedingung eintritt. Wenn jedoch der CCM-Prozeß die Nachricht f&sub2; vor dem Absturz empfängt und protokolliert, dann kann der CCM-Prozeß sich wiederherstellen, indem er die Nachrichtenprotokolle umordnet. Wenn der CCM-Prozeß jedoch vor dem Protokollieren des f&sub2;-Befehls abstürzt, dann ist das Umordnen der Nachrichten r&sub2;, r&sub3; und r&sub1; während eines Schritt-2-Wiederholungsversuchs nicht hilfreich. In diesem Fall bleibt die lokale Wiederherstellung von CCM erfolglos, und CA und CD werden aufgefordert, ihre Nachrichten neu zu senden (Schritt 3).
Aufgrund der Unbestimmtheit bei der Planungs- und Übertragungsverzögerung des Betriebssystems können die Nachrichten während Schritt 3 Nachrichtenwiedergabe in einer anderen Reihenfolge am CCM-Prozeß ankommen. Zum Beispiel könnte der CCM-Prozeß die Nachrichten in der folgenden Reihenfolge empfangen:
r&sub2; f&sub2; r&sub3; f&sub3; r&sub1; f&sub1;
die nicht zu der Grenzbedingung führt, so daß der Schritt 3 Wiederholungsversuch erfolgreich ist.

Schritt 4 Wiederholungsversuch - Beispiel

Als das vierte Beispiel werden die Signalleitpunkte (SRPs - Signal Routing Points) in einem Vermittlungssystem verwendet. Die Aufgabe von SRPs besteht darin, Datenpakete aus der Ursprungsvermittlung zu der Zielvermittlung zu lenken. Jeder SRP besitzt einen integrierten Überlaststeuermechanismus (OC-Mechanismus), der OC-Nachrichten zu anderen SRPs aussendet, um als Vorsichtsmaßnahme den ankommenden Verkehr zu reduzieren, wenn die Anzahl von Paketen in seinem Puffer einen Schwellenwert überschreitet. Man nehme an, daß beim normalen Betrieb der SRP-X Datenpakete, die für eine bestimmte Vermittlung bestimmt sind, entweder durch SRP-A oder SRP-B lenken kann. Wenn SRP-X eine OC-Nachricht aus dem SRP-A empfängt, beginnt er die Lenkung aller solchen Pakete durch SRP-B, um eine potentielle Überlastung von SRP-A zu vermeiden. Gleichzeitig empfängt die direkt mit SRP- B verbundene Vermittlung jedoch einen plötzlichen Anstieg von Dienstanforderungen. Diese beiden Arten von Verkehr füllen den Puffer von SRP-B schnell, und der Prozeß stürzt aufgrund eines Softwarefehlers ab, bevor ein Überlaststeuermechanismus eingeleitet werden kann.
Lokale Wiederholungsversuche von SRP-B durch Nachrichtenwiedergabe und Umordnung während der Schritte 1 bis 3 können keine Wiederherstellung nach dem Fehler bewirken, weil sie den Überlastzustand nicht umgehen können. Der Schritt-3-Wiederholungsversuch, an dem die SRP-X-Nachrichtenwiedergabe beteiligt ist, führt immer noch zu demselben Ausfall. Durch Umordnung der zu lenkenden Pakete und der OC-Nachricht aus SRP-A leitet SRP-X dann den Schritt-4-Wiederholungsversuch ein. Dies verzögert effektiv die Verarbeitung der OC- Nachricht und reduziert den Verkehr durch SRP-B, um SRP-B eine Chance zur Wiederherstellung zu geben. Die potentielle Überlastung für SRP-A tritt entweder niemals ein oder kann elegant ohne Verursachung eines Softwareausfalls behandelt werden.
Es versteht sich, daß die hier gezeigten und beschriebenen Ausführungsformen und Varianten nur beispielhaft die Prinzipien der vorliegenden Erfindung darstellen, und daß Fachleute vielfältige Modifikationen implementieren können, ohne vom Schutzbereich der Erfindung abzuweichen.

Claims

1. Vorrichtung zum Umgehen von Fehlern in einem Anwendungsprozeß (5), wobei die besagte Fehlerumgehungsvorrichtung mindestens einen Prozessor zur Ausführung einer Mehrzahl von gleichzeitig laufenden Anwendungsprozessen (10, 12) umfaßt, gekennzeichnet durch folgendes:

eine Überwachungseinrichtung (15), die einen Fehlererkennungsüberwacher (20) zum Überwachen von einem oder mehreren der besagten Anwendungsprozesse und ein Neustart-Teilsystem (30), das zur Ausführung eines Wiederherstellungsalgorithmus (700) für progressive Wiederholung zum Umgehen eines durch den besagten Überwacher erkannten Fehlers in einem der besagten Anwendungsprozesse angeordnet ist, enthält; und

eine Speichervorrichtung (55) zum Speichern einer Mehrzahl von fehlertoleranten Bibliotheksfunktionen (82), die von einem oder mehreren der besagten Anwendungsprozesse aus aufgerufen werden können, um die besagte Anwendung fehlertolerant zu machen, wobei die besagte fehlertolerante Bibliothek folgendes enthält:

eine Fixpunktfunktion zum periodischen Durchführen einer Fixpunktkontrolle von mit einem Anwendungsprozeß verbundenen Daten;

eine Wiederherstellfunktion zum Wiederherstellen der fixpunktmarkierten Daten aus dem nichtflüchtigen Speicher (44) während eines Wiederherstellungsmodus;

eine fehlertolerante Schreibfunktion zum Protokollieren jeder durch die besagten Anwendungisprozesse erzeugten Ausgangsnachricht in einer Senderprotokolldatei (92), bevor die besagte Nachricht durch den Anwendungsprozeß übertragen wird, wobei die besagte fehlertolerante Schreibfunktion einen Mechanismus zum Unterdrücken einer oder mehrerer der besagten Ausgaben während eines Wiederherstellungsmodus enthält; und

eine fehlertolerante Lesefunktion zum Protokollieren jeder durch die besagten Anwendungsprozesse empfangenen Eingangsnachricht in einer Empfängerprotokolldatei (90), bevor sie durch den empfangencien Anwendungsprozeß verarbeitet werden, wobei die besagte fehlertolerante Lesefunktion Daten aus einem Kommunikationskanal ausliest und die empfangene Nachricht in einem normalen Modus in der Empfängerprotokolldatei protokolliert und wobei die Eingangsdaten während eines Wiederherstellungsmodus aus der besagten Empfängerprotokolldatei ausgelesen werden.

2. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei die besagte fehlertolerante Bibliothek weiterhin eine Herzschlagfunktion enthält, die in angegebenen Zeitabständen eine Herzschlagnachricht zum besagten Fehlererkennungsüberwacher (20) sendet, die anzeigt, daß der zugehörige Prozeß noch aktiv ist, und wobei der besagte Fehlererkennungsüberwacher einen Fehler erkennt, wenn das besagte Herzschlagsignal vom besagten Anwendungsprozeß nicht vor Ende des besagten angegebenen Zeitabstands empfangen wird.

3. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei die besagte fehlertolerante Bibliothek weiterhin eine kritische Speicherfunktion enthält, die clie Angabe von kritischen Daten in einem Anwendungsprozeß erlaubt, und wobei die besagte Fixpunktfunktion nur die besagten angegebenen kritischen Daten kopiert.

4. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei die besagte fehlertolerante Schreibfunktion jede neu erzeugte Nachricht während des besagten Wiederherstellungsmodus mit der besagten entsprechenden Nachricht in der besagten Senderprotokolldatei (92) vergleicht, um die stückweise deterministische Annahme nachzuprüfen.

5. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei die besagte fehlertolerante Lesefunktion eine in jeder empfangenen Nachricht enthaltene Fixpunktintervallnummer des Senders überprüft und eine Fixpunktkontrolle des besagten zugehörigen empfangenden Anwendungsprozesses einleitet, wenn die besagte Fixpunktintervallnummer des Senders größer als die besagte aktuelle Fixpunktintervallnummer des Empfängers ist, wodurch konsequente globale Fixpunkte sichergestellt werden.

6. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei der besagte progressive Wiederholungsversuchsalgorithmus eine Mehrzahl von Wiederholungsversuchsschritten enthält, die allmählich den Umfang der Wiederherstellungswiederholung vergrößern, wenn der besagte erkannte Fehler nicht durch einen vorherigen Wiederholungsversuchsschritt umgangen wird.

7. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei der besagte progressive Wiederholungsversuchsalgorithmus folgende Schritte umfaßt:

Durchführen eines Empfänger-Wiedergabeschrittes zum Rückführen des besagten fehlerhaften Prozesses zu dem besagten letzten Fixpunkt, der mit dem besagten Prozeß verbunden ist, und zum Wiedergeben der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die durch den besagten fehlerhaften Prozeß seit dem besagten letzten Fixpunkt bis zum besagten Punkt des besagten erkannten Fehlers empfangen wurden;

Durchführen eines Empfänger-Umordnungsschrittes, wenn der besagte Empfänger-Wiedergabeschritt nicht den besagten Softwarefehler umgeht, wobei mindestens zwei der besagten empfangenen Nachrichten im besagten Nachrichtenprotokoll des besagten fehlerhaften Prozesses vor ihrer Wiedergabe umgeordnet werden;

Durchführen eines Sender-Wiedergabeschrittes, wenn der besagte Softwarefehler nicht durch den besagten Empfänger-Umordnungsschritt umgangen wird, wobei eine oder mehrere der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die durch den besagten fehlerhaften Prozeß nach seinem letzten Fixpunkt empfangen wurden, verworfen werden und wobei jeder der besagten sendenden Prozesse, die die besagten verworfenen Nachrichten zum besagten fehlerhaften Prozeß sandten, wäh rend des besagten Sender-Wiedergabeschrittes Nachrichten zum besagten fehlerhaften Prozeß neu senden;

Durchführen eines Sender-Umordnungsschrittes, wenn der besagte Softwarefehler nicht durch den besagten Sender-Wiedergabeschritt umgangen wird, wobei jeder der besagten sendenden Prozesse, die Nachrichten zum besagten fehlerhaften Prozeß sandten, die vom fehlerhaften Prozeß seit seinem letzten Fixpunkt empfangen wurden, vor Wiedergabe der besagten Nachrichten mindestens zwei der besagten Nachrichten in seinem Nachrichtenprotokoll umordnet; und

Durchführen eines Wiederholungsschrittes großen Umfangs, wenn der besagte Softwarefehler nicht durch den besagten Sender-Umordnungsschritt umgangen wird, wobei der besagte Wiederholungsschritt großen Umfangs jeden der besagten überwachten Prozesse zum letzten konsequenten globalen Fixpunkt zurückfährt.

8. Fehlerumgehungsvorrichtung nach Anspruch 1, wobei der besagte progressive Wiederholungsversuchsalgorithmus einen Wiederholungsfortpflanzungsalgorithmus zur Berechnung einer Wiederherstellungslinie (310) am letzten verfügbaren Ist- oder logischen Fixpunkt für jeden der besagten überwachten Prozesse, der nicht verworfen worden ist, einsetzt, wobei der besagte Wiederholungsfortpflanzungsalgorithmus die Wiederholungsfortpflanzungsregel erzwingt, wobei die besagten Nachrichten in den besagten Nachrichtenprotokollen, die von den besagten zugehörigen Prozessen zwischen dem besagten letzten Ist-Fixpunkt des besagten zugehörigen Prozesses und der besagten berechneten Wiederherstellungslinie empfangen und verarbeitet wurden, deterministische Nachrichten sind, wobei die besagten Nachrichten in den besagten Nachrichtenprotokollen, die vor der besagten berechneten Wiederherstellungslinie gesandt und nach der besagten Wiederherstellungslinie empfangen wurden, im Durchlauf befindliche Nachrichten sind, wobei der besagte progressive Wiederholungsversuchsalgorithmus folgende Schritte umfaßt:

Durchführen eines Empfänger-Wiedergabeschrittes zur Wiederherstellung des besagten fehlerhaften Prozesses zu seinem letzten Fixpunkt und zur Wiedergabe der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die vom besagten fehlerhaften Prozeß seit dem besagten letzten Fixpunkt bis zum Funkt des erkannten Fehlers empfangen wurden;

Durchführen eines Empfänger-Umordnungsschrittes, wenn der besagte Softwarefehler nicht durch den besagten Empfänger-Wiedergabeschritt umgangen wird, wobei der besagte Empfänger-Umordnungsschritt weiterhin folgende Schritte umfaßt:

Verwerfen der besagten Verarbeitungsordnungsinformationen für die besagten Nachrichten im besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die nach seinem letzten Fixpunkt empfangen wurden;

Berechnen der besagten Wiederherstellungslinie;

Umordnen der besagten im Durchlauf befindlichen Nachrichten im besagten Nachrichtenprotokoll des besagten fehlerhaften Prozesses; und

Wiedergeben der besagten deterministischen Nachrichten und Wiedergeben oder Wiedereinreichen der besagten im Durchlauf befindlichen Nachrichten in den besagten Nachrichtenprotokollen jedes der besagten überwachten Prozesse, deren aktueller Prozeßzustand sich nicht an der besagten Wiederherstellungslinie befindet;

Durchführen eines Sender-Wiedergabeschrittes, wenn der besagte Softwarefehler nicht durch den besagten Empfänger-Umordnungsschritt umgangen wird, wobei der besagte Sender-Wiedergabeschritt weiterhin folgende Schritte umfaßt:

Verwerfen der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die vom besagten fehlerhaften Prozeß nach dem letzten, für den besagten fehlerhaften Prozeß durchgeführten Fixpunkt empfangen wurden; und

Wiedergeben der besagten deterministischen Nachrichten und Neueinreichen der besagten im Durchlauf befindlichen Nachrichten in besagten Nachrichtenprotokollen jedes der besagten überwachten Prozesse, deren aktueller Prozeßzustand sich nicht an der besagten Wiederherstellungslinie befindet, wobei jeder der besagten sendenden Prozesse, die während der Anfangsverarbeitung die besagten verworfenen Nachrichten zum besagten fehlerhaften Prozeß sandten, von neuem während des besagten Sender-Wiedergabeschrittes Nachrichten zum besagten fehlerhaften Prozeß sendet;

Durchführen eines Sender-Umordnungsschrittes, wenn der besagte Softwarefehler nicht durch den besagten Sender-Wiedergabeschritt umgangen wird, wobei der besagte Sender-Umordnungsschritt weiterhin folgende Schritte umfaßt:

Verwerfen der besagten Verarbeitungsordnungsinformationen für jede von denjenigen Nachrichten in den besagten, mit dem besagten sendenden Prozeß verbundenen Nachrichtenprotokollen, die vom besagten sendenden Prozeß nach dem logischen Fixpunkt empfangen wurden, der vor der ersten Nachricht, die seit dem letzten, mit dem besagten fehlerhaften Prozeß verbundenen Fixpunkt vom besagten sendenden Prozeß zum besagten fehlerhaften Prozeß gesandt wurde, liegt;

Neuberechnen der besagten Wiederherstellungslinie;

Umordnen der besagten im Durchlauf befindlichen Nachrichten in den besagten, mit den besagten sendenden Prozessen verbundenen Nachrichtenprotokollen; und

Wiedergeben der besagten detesrministischen Nachrichten und Wiedergeben oder Neueinreichen der besagten im Durchlauf befindlichen Nachrichten in den besagten Nachrichtenprotokollen jedes der besagten überwachten Prozesse, deren aktueller Prozeßzustand sich nicht an der besagten Wiederherstellungslinie befindet;

9. Verfahren zum Bewirken, daß ein Anwendungsprozeß fehlertolerant wird, gekennzeichnet durch folgende Schritte:

Aufrufen von Funktionen in der besagten Anwendungsfunktion aus einer fehlertoleranten Bibliothek (82), um die besagte Anwendung fehlertolerant zu machen, wobei die besagte fehlertolerante Bibliothek folgendes enthält:

eine Wiederherstellfunktion zum Wiederherstellen der fixpunktmarkierten Daten aus dem nichtflüchtigen Speicher während eines Wiederherstellungsmodus;

eine fehlertolerante Schreibfunktion zum Protokollieren jeder durch die besagten Anwendungsprozesse erzeugten Ausgangsnachricht in einer Senderprotokolldatei (92), bevor die besagte Nachricht durch den Anwendungsprozeß übertragen wird, wobei die besagte fehlertolerante Schreibfunktion einen Mechanismus zum Unterdrücken einer oder mehrerer der besagten Ausgaben während eines Wiederherstellungsmodus enthält; und

eine fehlertolerante Lesefunktion zum Protokollieren jeder durch die besagten Anwendungsprozesse empfangenen Eingangsnachricht in einer Empfängerprotokolldatei (90), bevor sie durch den empfangenden Anwendungsprozeß verarbeitet werden, wobei die besagte fehlertolerante Lesefunktion Daten aus einem Kommunikationskanal ausliest und die empfangene Nachricht in einem normalen Modus in der Empfängerprotokolldatei protokolliert und wobei die Eingangsdaten während eines Wiederherstellungsmodus aus der besagten Empfängerprotokolldatei ausgelesen werden;

Überwachen des besagten Anwendungsprozesses auf Softwarefehler; und

Ausführen eines Wiederherstellungsalgorithmus (700) für progressive Wiederholung bei Erkennung eines Fehlers während des besagten Überwachungsschrittes, um den besagten fehlerhaften Prozeß wiederherzustellen, wobei der besagte progressive Wiederholungsversuchsalgorithmus eine Mehrzahl von Wiederholungsversuchsschritten enthält, die allmählich den Umfang der Wiederherstellungswiederholung vergrößern, Nenn der besagte erkannte Fehler nicht durch einen vorhergehenden Wiederholungsversuchsschritt umgangen wird"

10. Fehlerumgehungsverfahren nach Anspruch 9, wobei die besagte fehlertolerante Bibliothek weiterhin eine Herzschlagfunktion enthält, die in angegebenen Zeitabständen eine Herzschlagnachricht zum besagten Fehlererkennungsüberwacher sendet, die anzeigt, daß der zugehörige Prozeß noch aktiv ist, und wobei der besagte Fehlererkennungsüberwacher einen Fehler erkennt, wenn das besagte Herzschlagsignal vom besagten Anwendungsprozeß nicht vor Ende des besagten angegebenen Zeitabstands empfangen wird.

11. Fehlerumgehungsverfahren nach Anspruch 9, wobei die besagte fehlertolerante Bibliothek weiterhin eine kritische Speicherfunktion enthält, die die Angabe von kritischen Daten in einem Anwendungsprozeß erlaubt, und wobei die besagte Fixpunktfunktion nur die besagten angegebenen kritischen Daten kopiert.

12. Fehlerumgehungsverfahren nach Anspruch 9, wobei die besagte fehlertolerante Schreibfunktion jede neu erzeugte Nachricht während des besagten Wiederherstellungsmodus mit der besagten entsprechenden Nachricht in der besagten Senderprotokolldatei vergleicht, um die stückweise deterministische Annahme nachzuprüfen.

13. Fehlerumgehungsverfahren nach Anspruch 9, wobei die besagte fehlertolerante Lesefunktion eine in jeder empfangenen Nachricht enthaltene Fixpunktintervallnummer des Senders überprüft und eine Fixpunktkontrolle des besagten zugehörigen empfangenden Anwendungsprozesses einleitet, wenn die besagte Fixpunktintervallnummer des Senders größer als die besagte aktuelle Fixpunktintervallnummer des Empfängers ist, wodurch konsequente globale Fixpunkte sichergestellt werden.

14. Fehlerumgehungsverfahren nach Anspruch 9, wobei der besagte progressive Wiederholungsversuchsalgorithmus eine Mehrzahl von Wiederholungsversucheschritten enthält, die allmählich den Umfang der Wiederherstellungswiederholung vergrößern, wenn der besagte erkannte Fehler nicht durch einen vorherigen Wiederholungsversuchsschritt umgangen wird.

15. Fehlerumgehungsverfahren nach Anspruch 9, wobei der besagte progressive Wiederholungsversuchsalgorithmus folgende Schritte umfaßt:

Durchführen eines Empfänger-Wiedergabeschrittes zum Rückführen des besagten fehlerhaften Prozesses zu dem besagten letzten Fixpunkt, der mit dem besagten Prozeß verbunden ist, und zum Wiedergeben der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die durch den besagten fehlerhaften Prozeß seit dem besag ten letzten Fixpunkt bis zum besagten Punkt des besagten erkannten Fehlers empfangen wurden; Durchführen eines Empfänger-Umordnungsschrittes, wenn der besagte Empfänger-Wiedergabeschritt nicht den besagten Softwarefehler umgeht, wobei mindestens zwei der besagten empfangenen Nachrichten im besagten Nachrichtenprotokoll des besagten fehlerhaften Prozesses vor ihrer Wiedergabe umgeordnet werden;

Durchführen eines Sender-Wiedergabeschrittes, wenn der besagte Softwarefehler nicht durch den besagten Empfänger-Umordnungsschritt umgangen wird, wobei eine oder mehrere der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die durch den besagten fehlerhaften Prozeß nach seinem letzten Fixpunkt empfangen wurden, verworfen werden und wobei jeder der besagten sendenden Prozesse, die die besagten verworfenen Nachrichten zum besagten fehlerhaften Prozeß sandten, während des besagten Sender-Wiedergabeschrittes Nachrichten zum besagten fehlerhaften Prozeß neu senden;

Durchführen eines Wiederholungsschrittes großen Umfangs, wenn der besagte Softwarefehler nicht durch den besagten Sender-Umordnungsschritt umgangen wird, wobei der besagte Wiederholungsschritt großen Umfangs jeden der besagten überwachten Prozesse zur letzten konsequenten globalen Fixpunkt zurückfährt.

16. Fehlerumgehungsverfahren nach Anspruch 9, wobei der besagte progressive Wiederholungsversuchsalgorithmus einen Wiederholungsfortpflanzungsalgorithmus zur Berechnung einer Wiederherstellungslinie (310) am letzten verfügbaren eigentlichen oder logischen Fixpunkt für jeden der besagten überwachten Prozesse, der nicht verworfen worden ist, einsetzt, wobei der besagte Wiederholungsfortpflanzungsalgorithmus die Wiederholungsfortpflanzungsregel erzwingt, wobei die besagten Nachrichten in den besagten Nachrichtenprotokollen, die von den besagten zugehörigen Prozessen zwischen dem besagten letzten Ist-Fixpunkt des besagten zugehörigen Prozesses und der besagten berechneten Wiederherstellungslinie empfangen und verarbeitet wurden, deterministische Nachrichten sind, wobei die besagten Nachrichten in den besagten Nachrichtenprotokollen, die vor der besagten berechneten Wiederherstellungslinie gesandt und nach der besagten Wiederherstellungslinie empfangen wurden, im Durchlauf befindliche Nachrichten sind, wobei der besagte progressive Wiederholungsversuchsalgorithmus folgende Schritte umfaßt:

Durchführen eines Empfänger-Wiedergabeschrittes zur Wiederherstellung des besagten fehlerhaften Prozesses zu seinem letzten Fixpunkt und zur Wiedergabe der besagten Nachrichten in dem besagten, mit dem besagten fehlerhaften Prozeß verbundenen Nachrichtenprotokoll, die vom besagten fehlerhaften Prozeß seit dem besagten letzten Fixpunkt bis zum Punkt des erkannten Fehlers empfangen wurden;

Berechnen der besagten Wiederherstellungslinie;

Neuberechnen der besagten Wiederherstellungslinie;

Wiedergeben der besagten deterministischen Nachrichten und Wiedergeben oder Neueinreichen der besagten im Durchlauf befindlichen Nachrichten in den besagten Nachrichtenprotokollen jedes der besagten überwachten Prozesse, deren aktueller Prozeßzustand sich nicht an der besagten Wiederherstellungslinie befindet;