Der klassische Begriff fehlerfreier Software bezieht sich auf die formal und, logisch korrekte Lösung einer bestimmten Aufgabe: Ein Programm soll so beschaffen und implementiert sein, daß es in sich keine Fehler enthält und sich auch durch falsche Eingaben des Benutzers keine Abstürze provozieren lassen. Nun ist aber schon in der Redeweise vom "Bug", der Wanze, die nach altväterlicher Mär in den Relais eines Computers der (wievielten?) Generation herumkrabbelte und die Programmierer zur Verzweiflung trieb, ausgesprochen, daß es auch Ursachen für Systemzusammenbrüche gibt, die "von außen" kommen. Unter fehlertoleranter Software versteht man Code, der solche widrigen Außenbedingungen bis zu einem gewissen Grad hinnehmen kann. Flaviu Christian, Mitarbeiter des IBM Research Laboratory in San José, beschrieb in einem Vortrag zur JCIT, welchen Bedingungen fehlertolerante Software genügen muß und wie sich der Grad ihrer Zuverlässigkeit quantifizieren läßt.

Es gibt drei Gründe, warum Computersysteme unzuverlässig sein können: Fehler der Software, der Hardware oder des Anwenders. Während - wenigstens im Prinzip Fehler beim Softwareentwurf durch geeignete Prüf- und Testverfahren vermieden werden können, lassen sich Hardware- und Anwenderfehler nicht im voraus ausschließen und müssen toleriert werden.

Der Ansatz von Christian, auf dessen axiomatische Formulierung hier verzichtet wird, geht von der Idee aus, daß das Auftreten eines Hardware-Fehlers und ein korrekter Funktionsaufruf durch den Anwender im Prinzip das gleiche sind: Zustandsänderungen des Systems. Wenn man sich diese Sichtweise zu eigen macht, kann man Fehler einfach als eine weitere Klasse von Operationen auffassen, deren das System "fähig" ist und die in zufälligen Zeitabständen von der Systemumgebung "aufgerufen" werden. Zugegeben, die Macken des blöden Kastens nicht als ärgerliche Ausnahme zu sehen, sondern als Regel zu akzeptieren und damit umzugehen, ist nicht ganz einfach für jemanden, der seinen Widersacher in solchen Fällen am liebsten mit einem Tritt zur Räson bringen würde. Das folgende Beispiel zeigt aber, daß mit diesem Ansatz Computersysteme geschaffen werden können, deren Zuverlässigkeit zwar nicht 100 Prozent ist, bei denen aber das Fehlerrisiko auf ein akzeptables, vorausberechenbares Maß beschränkt werden kann.

Der Fehler gehört zum System

Als Beispiel soll ein Verwaltungssystem für einen Massenspeicher entworfen werden, das die Integrität der gespeicherten Informationen trotz Systemzusammenbrüchen oder Fehlern des physischen Speichermediums wahrt, Das System soll aus Prozessor, Hauptspeicher und Magnetplatten bestehen. Im Gegensatz zur Software, die eine mathematische Abstraktion ist und keinem physikalischen Verschleiß unterliegt, können bei diesen Komponenten durch mechanische, chemische oder elektromagnetische Phänomene Fehler hervorgerufen werden. Die Aufgabe fehlertoleranter Software besteht darin, diese zufälligen Fehlfunktionen so zu maskieren, daß sie den eigentlichen Programmablauf nicht beeinflußen.

Bei einer idealen Speicherplatte und diesem Ziel soll man mit dem Entwurf möglichst nahe kommen sollte der an einer bestimmten Adresse gespeicherte Block jederzeit gelesen werden können. Tatsächlich können elektromagnetische Vorgänge oder Prozessorzusammenbrüche während eines Updates die gespeicherte Information beschädigen oder zerstören. Es wird angenommen, daß das System in der Lage ist, einen derartigen, in Mitleidenschaft gezogenen Block durch einen Parity-Check zu entdecken und als unlesbar zu kennzeichnen.

Der Trick der Theorie besteht wie gesagt darin, Fehlfunktionen wie diese einfach als Operationen des Systems zu fassen. Man könnte dazu zum Beispiel eine Operation namens "Decay" definieren, die von der Systemumgebung aufgerufen und auf die Platte angewandt wird, und die den Inhalt einer genau bestimmbaren Zahl von Adressen unlesbar macht. Eine wichtige Eigenschaft dieser Operation, ist es, daß sie in zufälligen Zeitabständen auftritt. Für die spätere Quantifizierung der Zuverlässigkeit muß bekannt sein, wie oft "Decay" in einem bestimmten Zeitraum wahrscheinlich aufgerufen wird. Diese Zahlen werden ja auch bei normalen Anwenderoperationen ermittelt, um beispielweise die Effizienz alternativen Implementierungen miteinander zu vergleichen. Für das Beispiel gehen wir davon aus, daß Zuverlässigkeitstests ergeben haben, daß der Hardwarefehler nachwirkungsfrei ist, das heißt wirklich nur vom Zufall abhängt und angenommen - alle 20 Tage auftritt. Dann lautet die erste Zuverlässigkeitshypothese:

- Die Zeitspanne zwischen zwei Decay-Aufrufen ist exponential verteilt mit einem Erwartungswert von a = 20 Tagen.

Für die I/O-Operationen des Anwenders nach einem Decay-Aufruf gilt dann folgendes: Wenn der zu lesende Block einen Parityfehler hat, wird er als unlesbar gemeldet; andernfalls wird der Block gelesen und an die Adresse, an der er gespeichert war, zurückgegeben. Die Schreiboperation ist von einem vorherigen Decay-Aufruf unabhängig, also in dieser Beziehung immer erfolgreich.

Ein Crash wird eingeplant

Die zweite Art Fehler, die eine Massenspeicherverwaltung beeinflußen kann, sind Prozessorzusammenbrüche. So ein Crash kann während der Abarbeitung jedes Programms auftreten. Es wird hier von einem nicht-permanenten Hauptspeicher ausgegangen, das heißt bei einem Systemzusammenbruch geht der Inhalt des Hauptspeichers verloren. Dagegen ist eine Magnetplatte ein Permanentspeicher. Wenn ein Crash nicht gerade während eines Schreibvorgangs auftritt, bleibt der Zustand vor dem Zusammenbruch erhalten. Wieder wird angenommen, daß im Falle eines gestörten Schreibvorgangs der Fehler durch einen Parity-Check erkannt und der entsprechende Block als unlesbar gekennzeichnet wird.

Systemzusammenbrüche sind genau so zufällig, wie das Auftreten von Plattenfehlern. Mit Zuverlässigkeitstests kann man die Crash-Rate ermitteln. Sie sollte über einen bestimmten Zeitraum hinweg konstant sein, damit sichergestellt ist, daß die Zusammenbrüche tatsächlich zufällig und hardware-bedingt und nicht vom Wetter abhängig sind - oder gar von einer Wanze, die in ... Nehmen wir für unser Beispiel an, Systemzusammenbrüche treten durchschnittlich alle gamma = 4 Tage auf und eine Magnetplatte sei im allgemeinen nur von jedem zwanzigsten (0 = 20) Crash betroffen. Dann lautet die zweite Zuverlässigkeitshypothese:

- Die Zeitspanne zwischen zwei durch Systemzusammenbrüche verursachten Schreibfehlern ist expotential verteilt mit einem Erwartungswert von gamma0 = 4 x 20 = 80 Tage.

Die beiden Zuverlässigkeitshypothesen drücken die statistischen Annahmen aus, die über die Eigenschaften der Systemumgebung gemacht werden können. Die Hardwarefehler, die ein fehlertolerantes System wegstecken können soll, sind also zu charakterisieren durch die exakte Beschreibung ihrer Wirkung auf das System und der Häufigkeit ihres Auftretens.

Die tatsächlichen Lese- und Schreiboperationen sind, wie man feststellen muß, nur ziemlich grobe Annäherungen an die idealen I/O-Operationen, die man gerne hätte. Das Ziel muß deshalb darin bestehen, eine zuverlässigere (abstrakte) Platte zu konstruieren, die dem Anwender die Auswirkungen der hinderlichen Operationsaufrufe durch die feindliche Außenwelt sozusagen verheimlicht. Dies soll verwirklicht werden, indem physisch, zwei Platten benutzt werden, die redundant sind, also beide die gleichen Informationen enthalten. Der Zustand der abstrakten Platte soll dann immer vollständig definiert sein, das heißt zu jeder Adresse soll ein lesbarer Block existieren. Außerdem sollen die Schreiboperationen auf der abstrakten Platte störungsfrei in bezug auf Systemzusammenbrüche sein, das heißt eine wegen eines Crashs abgebrochene Schreiboperation soll entweder den Speicherzustand unverändert lassen oder einen neuen korrekten Zustand ergeben.

Gefährlicher Status quo minus

Der Zustand der abstrakten Platte hängt demnach von den Zuständen der beiden physischen Platten ab. Wie wirken sich die beiden zu tolerierenden Fehlfunktionen auf dieses abstrakte Speichersystem aus? Eine Decay-Operation kann von einem fehlerfreie All-Perfect-Status, bei dem alle Blöcke auf beiden Platten lesbar sind, zu einem Status führen, bei dem nur einige Blöcke einer der beiden Platten unlesbar sind. Dieser Zustand ist zwar immer noch brauchbar - die zerstörte Information existiert ja noch auf der anderen Platte -, aber gefährlich, weil eine zweite Decay-Operation angewandt auf die zweite Platte auftreten kann.

Um dies zu vermeiden, muß eine zusätzliche Operation, entworfen werden, die die Fehler, die durch, die erste Decay-Operation verursacht wurden, repariert und die abstrakte Platte in einen All-Perfect-Status bringt, bevor ein zweiter Plattenfehler oder ein Crash auftritt. Nennen wir diese Wartungsoperation RECovery.

Es gibt also vier Operationen, die von den verschiedenen, Anwendern aufgerufen werden können:

- die Lese- und Schreiboperationen des Anwenders,

- die Decay-Operation der Systemumgebung und

- die RECovery-Operation der regelmäßigen Wartung.

Mit diesen vier Operationen heißt das System der abstrakten Platte für uns genau dann fehlertolerant, wenn folgende Bedingungen erfüllt werden:

- Wenn ein Plattenfehler auftritt, während sich das System im All-Perfect-Zustand befindet, ändert das nichts an dem sichtbaren abstrakten Zustand.

- Schreiboperationen bleiben von Prozessorzusammenbrüchen unbeeinflußt.

- Ein Crash während eines Reparaturvorgangs soll toleriert werden. Mit anderen Worten: Jede Reihe von erfolglosen Reparaturversuchen, die von einer gelungenen RECovery-Operation abgeschlossen wird, sollte das System in All-Perfect-Status bringen.

Es werden zwei unabhängige physische Platten eingesetzt, um eine zuverlässigere abstrakte Platte zu konstruieren. Dazu müssen jetzt drei der vier oben genannten Operationen implementiert werden, nämlich die Lese-, Schreib- und RECovery-Operationen. Die korrekte Implementierung der vierten Operation Decay wird der Systemumgebung überlassen. Halten wir jedoch noch einmal fest, daß die beiden Platten physisch unabhängig sein sollen, die Decay-Operation also immer nur eine der beiden Platten in Mitleidenschaft zieht.

Die Leseoperation wird wie folgt festgelegt: Zuerst wird versucht, die erste Platte zu lesen. Ist der Versuch erfolgreich, wird die Information an den Anwender übergeben; andernfalls wird versucht, die zweite Platte zu lesen.

Die Schreiboperation schreibt wegen der nötigen Redundanz einfach nacheinander auf beide Platten. Damit hat die Schreiboperation eine wichtige Eigenschaft: Wenn sich das System im All-Perfect-Status befindet, kann ein Crash während einer Schreiboperation nur zur Zerstörung eines Blocks fühen. Falls ein Crash genau nach der ersten und vor der zweiten Schreiboperation auftritt, sind die Informationen an der betreffenden Adresse unterschiedlich. Die beiden Platten sind sozusagen phasenverschoben: Während die erste Platte bereits aktualisiert ist, enthält die zweite noch die alte Information.

Als drittes ist die RECovery-Operation zu implementieren. Diese vergleicht paarweise den Inhalt gleicher Adressen der ersten und zweiten Platte. Wenn ein Block auf einer Platte nicht lesbar ist, wird der an der entsprechenden Adresse gespeicherte Inhalt der zweiten Platte an diese Adresse geschrieben. Eine Platte ist praktisch immer das Back-up der anderen. Wenn beide Blöcke lesbar sind, sich aber unterscheiden, liegt eine Phasenverschiebung vor. So wie die Schreiboperation festgelegt ist, ist der Block der ersten Platte immer der aktuellere und wird auf die zweite Platte übertragen.

Wieder ist für die Quantifizierung der Zuverlässigkeit die Statistik gefragt: Nehmen wir an, die durchschnittliche Reparaturzeit betrage p=0.2 Stunden, also 12 Minuten.

Für die so festgelegten Operationen ist die Forderung nach Fehlertoleranz, so wie sie oben in den drei Bedingungen definiert wurde, erfüllt. Es läßt sich sogar zeigen, daß eine RECovery-Operation auch dann noch erfolgreich ist, wenn auf beiden Platten ein Fehler aufgetreten ist, also zwei Decay-Aufrufe so kurz hintereinander stattgefunden haben, daß kein Wartungslauf dazwischen lag. Allerdings dürfen dafür die Adressen der zerstörten Blocks der einen Platte nicht identisch mit den Fehleradressen der zweiten Platte sein. Sobald aber durch zwei aufeinanderfolgende Plattenfehler Blocks mit identischen Adressen unlesbarwerden, kann das System sich nicht mehr selbst reparieren. Derartige Fehler müssen dann vom Anwender toleriert (und repariert) werden.

Zuverlässigkeitsanalyse

Als letzter Schritt soll errechnet werden, wie oft die RECovery-Operation aufgerufen werden muß, damit das System eine gewisse Zuverlässigkeit erreicht. Es wurde eben gezeigt, daß das System "sich selbst repariert", solange nicht beide Platten, gleichzeitig in Mitleidenschaft gezogen sind. Legen wir einen Zuverlässigkeitsgrad von lambda = 99,7 Prozent fest, das heißt die Wahrscheinlichkeit, daß das System sich in einem irreparablen Zustand befindet, soll kleiner als 0,003 sein.

Für die Berechnung kommen wie um einige einfache Formalisierungen nicht herum: Es sei der Zustand einer Platte mit 1 gekennzeichnet, wenn sie fehlerfrei ist; andernfalls mit 2. Dann ist der Zustand des abstrakten Systems ein kontinuierlicher stochastischer Prozeß, der die Werte (1,1), (1,2), (2,1) und (2,2) annehmen kann. Der Einfachheit halber wird davon ausgegangen, daß alle Zeitabstände, die mit den Zustandsänderungen dieses Prozesses verbunden sind, exponential verteilt sind, Unter dieser Annahme ist der Zustand der abstrakten Platte ein sogenannter Markovscher Prozeß, auf den die Methoden der Ausgleichsrechnung angewandt werden können.

Nach den vorher aufgestellten Zuverlässigkeitshypothesen treten die Zustandsänderungen (1,j) - > (2,j) oder (i,1) - > (i,2) in konstanten Abständen auf. Die relative Häufigkeit von Fehlfunktionen des Systems beträgt dann:

S=(1/(24alpha))+(1/(24gamma0))

Dabei sind 24alpha und 24gamma 0 die mittlere Zeit zwischen zwei Decay-Aufrufen beziehungsweise Prozessorzusammenbrüchen gemessen in Stunden.

Sei 2beta die durchschnittliche Zeit (in Stunden) zwischen zwei aufeinanderfolgenden RECovery-Aufrufen, dann ist die relative Häufigkeit von Reparaturaktionen, das heißt der Zustandsänderungen (1,2) - > (1,1) oder (2,1) - > (1,1):

r=(1/(beta+))

Wobei beta die durchschnittliche Zeit zwischen dem Auftreten eines Fehlers (Decay oder, Crash) und einem RECovery-Aufruf ist und die Dauer dieser Operation angibt (in unserem Beispiel 0.2 Stunden).

Schließlich wird angenommen, daß, wenn das System den (nicht tolerierbaren) Zustand (2,2) erreicht hat, die notwendigen Reparaturarbeiten die dann nicht mehr von dem System selbst durchgeführt werden können - durchschnittlich = 1 Stunde brauchen. Die relative Häufigkeit des Übergangs von (2,2) nach (1,1) ist demnach

R =(1/(beta+))

Die vorhandenen stochastischen Informationen über den Zustand des abstrakten Systems können in einem Diagramm dargestellt werden. Kreise kennzeichnen dabei die vier möglichen Zustände, Pfeile symbolisieren die möglichen Zustandsänderungen. Wenn man mit pij die Wahrscheinlichkeit eines bestimmten Zustands bezeichnet, erhält man aus dem Diagramm folgende Gleichungen (1,2) und (2,1) sind gleich wahrscheinlich, deswegen ist P 12 = P21:

2s*p11 = 2r*p12 + R*p22

s*p12 + r*p012 = s*p11

R*p22 = 2s*p12

Die pij erfüllen die Normalgleichung:

p11 + 2p12 + P22 = 1

Als Zuverlässigkeitsgrad wurde 99,7 Prozent verlangt, das heißt die Wahrscheinlichkeit, daß sich das System in einem der drei Zustände (1,1), (1,2) und (2,1) befindet, muß größer als 99,7 Prozent sein:

p11 + 2p12 >=lambda

Dieses System von Gleichungen und Ungleichungen muß nach beta aufgelöst werden. Wenn eine Lösung existiert, heißt das, daß die Zuverlässigkeitsbedingungen erfüllt werden können. Wenn es mehrere Lösungen gibt, ist die größte von Interesse. Sie bedeutet, daß RECovery am seltensten aufgerufen werden muß.

Für unser Beispiel ergibt sich bei einem verlangten Zuverlässigkeitsgrad von 99,7 Prozent ein (maximales) beta = 12. Das heißt, daß zwischen zwei RECovery-Aufrufen höchstens zwölf Stunden vergehen dürfen, damit das System nicht in den unerwünschten Zustand kommt, in dem beide Platten in Mitleidenschaft gezogen sind. Man braucht also einen Wartungslauf pro Tag.

Das in diesem Beispiel verwendete System war relativ einfach. Abgesehen davon, daß sich der theoretische Aufwand bei komplexeren Systemen erheblich erhöht, gibt es noch zusätzliche Punkte, die zu beachten wären. Zum Beispiel könnte man die Wahrscheinlichkeit, daß bei den Zuverlässigkeitshypothesen Fehler gemacht wurden, mit einberechnen; über geeignete Fehlermodelle ließe sich auch noch streiten.

Ohnehin kann man verlässliche Angaben über die Art und Häufigkeit von Fehlern nur bei schon länger eingesetzter Hardware machen. Wenn es also auch noch eine Reihe von Problemen zu lösen gibt, so ist wegen der ständig zunehmenden Verluste, die durch Computerfehler verursacht werden, mit einem steigenden Interesse an fehlertoleranten Lösungen zu rechnen.