 |
|
|
|
|
||||||||
 |
||||||||||||
|
||||||||||||
 |
||||||||||||
|
|
|
|
||
Erhöhung der Zuverlässigkeit von Rechnersystemen (Teil 3 von 4) Von Klaus Eppele Duplizierung Ein sowohl durch Hardware als auch durch Software realisierbares Fehlererkennungsverfahren stellt die bereits beschriebene NMR-Anordnung dar (siehe Teil 1 dieser Serie).
Hierbei werden die Ausgangswerte von N Modulen miteinander verglichen und versucht, Fehler durch eine Mehrheitsentscheidung zu kompensieren. Nutzt man diese Anordnung nicht zur Fehlermaskierung, sondern zur
Fehlererkennung, muß der Voter im Fehlerfall anstatt eine Mehrheitsentscheidung zu treffen nur ein Fehlersignal ausgeben. Für N=2 erhält man dann die Anordnung der „Verdopplung mit Vergleich“.
Bild 1: Verdopplung mit Vergleich Dieses sehr sichere Verfahren hat den Nachteil, daß ein mehr als zweifacher Aufwand nötig ist. Wegen der zunehmenden Verbilligung elektronischer Bauelemente kann dieser Nachteil für
kleinere Schaltungen, die nicht in zu großer Stückzahl hergestellt werden jedoch vernachlässigt werden. Ein weiteres Problem besteht darin, daß sich mit der Verdopplung der Module auch die Fehleranfälligkeit des
Systems verdoppelt, da sowohl die Fehler des urprünglichen, als auch Fehler des zusätzlichen Moduls zu einem Ausfall führen können. Beide Module müssen also immer voll funktionsfähig sein, was die Gesamtzuverlässigkeit
des Systems herabsetzt. Es ist deshalb wünschenswert, zusätzliche Module so einfach wie möglich zu entwerfen, da weniger komplexe Schaltungen in der Regel auch weniger störanfällig sind. Außerdem kann es vorkommen, daß
gleichartig gestörte Module identische falsche Ausgaben liefern, die durch einen Vergleich nicht als falsch erkannt werden können. Um den großen Schaltungsaufwand zu reduzieren und um gleichartige Fehler durch eine
diversitäre Auslegung der verwendeten Module verhindern zu können, wurden eine Vielzahl von Varianten der Methode der Verdopplung mit Vergleich entwickelt. Einige dieser Varianten sollen im folgenden näher erläutert
werden. Two-Rail-Logik Eine spezielle Variante für einen diversitären Aufbau stellt die sogenannte Two-Rail-Logik dar. Die Originalschaltung und ihre Verdopplung werden dabei als Logik mit inversen Ausgaben
ausgelegt, so daß in der Gesamtschaltung alle Signale stets echt und negiert vorliegen. Der erforderliche Schaltungsaufwand geht durch diese Maßnahme gegenüber der Ursprungsform von Verdopplung mit Vergleich etwas
zurück, ohne daß sich die Fehlererkennungseigenschaften verschlechtern. Diese Verbesserung beruht darauf, daß sich alle Negationen als einfache Leitungskreuzung zwischen der Originalschaltung und der komplementären
Verdopplung realisieren lassen. Der Entwurfsaufwand für die diversitäre Auslegung ist hier geringer, als wenn die Schaltung komplett neu entworfen werden müßte, da die Gatter der Originalschaltung in der zweiten
Schaltung nur durch ihr Komplement ersetzt werden müssen. Bild 2: Two-Rail-Logik Pseudoverdopplung Bei der Methode der Pseudoverdopplung werden die zu verarbeitenden Daten zweimal,
zeitlich hintereinander, von derselben Anordnung, aber auf verschiedenen Datenpfaden verarbeitet und nach entsprechender Zwischenspeicherung auf Gleichheit geprüft. Die erforderliche Schaltungsverdopplung wird dabei
hauptsächlich durch eine verlängerte Bearbeitungszeit ersetzt. Die gewünschte Diversität erreicht man durch die verschiedenartige Nutzung derselben Hardware. Bild 3: Pseudoverdopplung
Regeneration der Eingabesignale Kann für eine Schaltung die zugehörige rechtsinverse Schaltung gefunden werden, so realisiert eine Reihenschaltung von S und S-1 die identische Abbildung. Durch Vergleich der
ursprünglichen Eingabedaten mit der Ausgabe von S-1 ist dann das Erkennen von Fehlern möglich. Diese Methode bringt keine direkte Einsparung beim Entwurf des diversitären Systems. Man kann den Aufwand beim Entwurf von
S-1 jedoch dadurch senken, daß man für Schaltungen mit mehreren Eingängen und mehreren Ausgängen die Eingabesymbole nur für einige der Eingänge regeneriert und in Kauf nimmt, daß dann nur noch ein Teil der Fehler
erkannt wird. Bild 4: Regeneration der Eingabesignale Restklassenrechnung Ein bekannter Vertreter der verschiedenen algebraischen Verfahren ist die Fehlererkennung mittels Restklassenrechnung. Die zu
überprüfende Operation wird hierbei parallel modulo-p ausgeführt und das Ergebnis wird modulo-p verglichen. Die zusätzliche Schaltung kann gegenüber der Ursprungsschaltung wesentlich vereinfacht werden, da weniger
Stellen verarbeitet werden müssen. Setzt man z.B. p=3, dann ist nur die Verarbeitung von Wörtern der Wortbreite zwei erforderlich. Allerdings müssen die Eingänge und die Ausgänge modulo-p umgeformt werden, was man
beispielsweise mit ROMs (Read Only Memories) bewerkstelligen kann. Die Methode der Restklassenrechnung kann für alle Operationen verwendet werden, die im Körper der ganzen Zahlen homomorph zu den entsprechenden
Operationen in endlichen Zahlenbereichen sind. Die Fehlerüberdeckung ist nicht so gut wie bei der klassischen Methode der Verdopplung mit Vergleich. Bild 5: Restklassenrechnung Implikanten Bei dieser
Methode besteht die zweite Schaltung selbst aus zwei Teilen, dem 1-Implikant I1 und dem 0-Implikant I0. I1 heißt 1-Implikant der ursprünglichen Schaltung S, wenn für jede Belegung x der Eingänge gilt: wenn I1(x)=1, dann
folgt S(x)=1. Analog heißt I0 0-Implikant von S, wenn gilt: wenn I0(x)=1, dann folgt S(x)=0. Ein Fehler wird dann erkannt, wenn I1(x)=1 und S(x)=0, oder wenn I0(x)=1 und S(x)=1. Die wesentlichen Ideen bestehen nun
darin, I1 und I0 so zu wählen, daß sie sich einfach realisieren lassen. Dafür wird in Kauf genommen, daß nur ein Teil der Fehler in S erkannt wird. Bild 6: Implikanten Probabilistische Fehlererkennung Es
existieren verschiedene Fehlererkennungsverfahren, die einen Fehler nicht sicher, sondern nur mit einer gewissen Wahrscheinlichkeit erkennen können. Unter 'Probabilistischer Fehlererkennung' soll hier folgendes
Verfahren verstanden werden: Das Verhalten einer Schaltung S kann durch einen deterministischen endlichen Automaten M beschrieben werden. Die zur Überwachung nötige zweite Schaltung SA wird vereinfacht, indem man
durch eine Abstraktion A die Zustände von M zu Zustandsmengen zusammenfaßt und auch für die möglichen Eingabe- und Ausgabesignale Klassen bildet. Die Abstraktion A definiert damit einen indeterministischen Automaten MA,
der eine Vereinfachung des Automaten M darstellt, da er weniger Eingaben, Zustände und Ausgaben kennt. Sind die Wahrscheinlichkeiten der möglichen Eingaben von M bekannt, so kann man die Wahrscheinlichkeit der
möglichen Ausgabemenge von MA in Abhängigkeit von der jeweiligen Eingabemenge und der jeweiligen Zustandsmenge bestimmen. Liefert M eine falsche Ausgabe und fällt diese in eine Ausgabemenge von MA, deren
Wahrscheinlichkeit Null ist, so ist der Fehler erkannt; fällt sie in eine Ausgabemenge von MA. deren Wahrscheinlichkeit zwischen Null und Eins liegt, dann ist nicht sicher, ob ein Fehler vorliegt und man muß eventuell
erst noch weitere Ausgaben von M überprüfen, bevor man eine Entscheidung fällt. Es kann aufgrund der getroffenen Vereinfachungen auch geschehen, daß eine falsche Ausgabe nicht erkannt wird, wenn der Automat MA
eine Ausgabemenge vorsieht, die die falsche Ausgabe von M enthält. Bild 7: Probabilistische Fehlererkennung Die oben genannten Verfahren der Verdopplung erfordern vor allem zusätzliche Hardware. Aber auch ohne
zweifache Auslegung aller zu sichernden Komponenten ist die Methode der Verdopplung mit Vergleich einsetzbar, wenn man die zu sichernden Informationen zeitlich hintereinander von derselben bestehenden Hardware
verarbeiten läßt. Die Ersparnis an struktureller Redundanz muß dann jedoch mit einer erhöhten Zeitredundanz bezahlt werden. Wird die zeitliche Verdopplung von Signalen bei der Datenübertragung eingesetzt, wird
genaugenommen, wie bereits in Teil 2 erwähnt, eine Codierung vorgenommen, bei der jedes Datenwort auf ein Datenwort doppelter Länge mit idendischen Hälften abgebildet wird. Der Nachteil dieses Verfahrens liegt neben dem
erhöhten Zeitaufwand für die doppelte Verarbeitung vor allem darin, daß ein permanent gestörtes System auch bei mehrfacher Ausführung derselben Operation denselben Fehler liefert und deshalb durch einen Vergleich der
beiden gleichförmig gestörten Ergebnisse der Fehler nicht erkannt werden kann. Weist beispielsweise eine Busleitung eines parallelen Bussystems einen Ständig-0/1-Fehler auf, der zur Verfälschung eines Datums bei der
Übertragung führt, so wird der Fehler auch dann nicht erkannt, wenn dieses Datum ein weiteres Mal übertragen wird, da der permanente Ständig-0/1-Fehler das Datum bei jeder Übertragung in gleicher Weise verändert.
Transiente Fehler verfälschen meist nur eines der Datenwörter, so daß sich die zeitliche Verdopplung von Signalen deshalb vor allem zur Aufspürung transienter Fehler eignet. Um die Fehlerüberdeckung für permanente
Fehler zu erhöhen, wurden auch für die zeitliche Duplizierung verschiedene Varianten entwickelt, die ein Datenwort nicht nur verdoppeln, sondern zusätzlich die Verdopplung modifizieren. Beispielsweise setzt der
C.mmp-Multiprozessor eine Variante ein, die man als öswap-and-compareö bezeichnet. Hierbei geht das zweite Datenwort aus dem ersten hervor, indem man dessen beiden Byte vertauscht. Dieser Vorgang muß dann vor einem
Vergleich nochmals durchgeführt werden. Eine weitere Möglichkeit bietet die CD-Codierung, die ein Datenwort um dessen Komplement erweitert. Bei einer Datenübertragung werden das Datenwort und sein Komplement
hintereinander gesendet. Die Fehlererkennung wird hierbei gegenüber der klassischen Methode der Verdopplung mit Vergleich wesentlich erleichtert, da das zweite Datenwort ein Signalwechsel auf jeder Busleitung bewirken
muß und deshalb z.B. ein Leitungsbruch sofort erkannt werden kann. Die hierzu äquivalente Realisierung für die strukturelle Verdopplung stellt die bereits erwähnte Two-Rail-Logik dar. Bei der Rotation ergibt sich das
zweite Datenwort aus dem ursprünglichen Datenwort dadurch, daß man jedes Bit zyklisch um eine Stelle nach rechts oder nach links verschiebt. Erweitert man die Methode der Rotation um eine zusätzlichen Paritätssicherung,
kann der Empfänger bei einer Datenübertragung durch die zweifache Übertragung nicht nur Fehler erkennen, sondern auch einzelne Ständig-0/1-Fehler, sowie Und/Oder-Überbrückungsfehler selbständig beheben. Die doppelte
Übertragung von Daten zur Fehlererkennung kann auch dadurch erfolgen, daß der Empfänger jedes empfangene Datenwort zurücksendet und der Sender das ausgesendete mit dem zurückerhaltenen Datenwort vergleicht. Stellt der
Sender einen Fehler fest, wiederholt er die Übermittlung der gestörten Daten. Dieses Verfahren hat den Vorteil, daß die gesamte Kontrolle beim Sender liegt. Dieser wiederholt dieselben Daten so oft, bis sie aus seiner
Sicht korrekt übertragen wurden, oder bis eine vorgegebene Anzahl von m Übertragungsversuchen mißglückt ist. Dadurch paßt sich das System selbständig dem Fehleraufkommen im Übertragungskanal an. Ist die Übertragung nach
m Versuchen nicht geglückt, wird auf einen permanenten Fehler geschlossen und ein Fehlersignal generiert. Außerdem entfällt hierbei der Codieraufwand, den die anderen aufgeführeten Varianten verlangen. Nachteilig ist,
daß weitere Informations- und Zeitredundanz benötigt wird, da der Sender jetzt dem Empfänger jedesmal mitteilen muß, ob das letztgesendete Datum gültig war. Außerdem muß jeder Empfänger bei dieser Methode in der Lage
sein zu senden, und ein ständiges Umschalten der Übertragungsrichtung ist erforderlich. Abschließende Bemerkungen zur Verdopplung mit Vergleich Um die Zuverlässigkeit von Systemen noch weiter zu erhöhen kann
die Redundanz auch auf das mehrfache erhöht werden. Dies ist mit hohen Kosten verbunden, vor allem dann, wenn alle Komponenten diversitär ausgelegt sein sollen. Diversitäre Systeme erfordern eine exakte Synchronisation,
da sie aufgrund ihres unterschiedlichen Aufbaus auch meist unterschiedlich lange für die Bearbeitung derselben Aufgabe benötigen. Auch der Voter wird mit der Anzahl der Subsysteme immer aufwendiger und kann zur
Leistungsminderung des Systems führen, wenn er zu lange Zeit braucht, um die Ergebnisse der Subsysteme zu vergleichen. Um unnötige Redundanz zu vermeiden, sollte man untersuchen, ob bereits bestimmte Funktionen
doppelt im System vorliegen, die dann nur noch miteinander verglichen werden müssen. Beispielsweise existieren in der Am2901 ALU (arithmetisch logische Einheit) Funktionseinheiten, die A+B, AB und A XOR B berechnen.
Sollen diese Funktionen durch Verdopplung mit Vergleich gegen Fehler gesichert werden, so genügt es das XOR-Gatter zu verdoppeln, da dann wegen A XOR B = (A+B) XOR (AB) auch die korrekte Funktion der anderen beiden
Gatter überprüft werden kann. Fehlererkennung durch analytische Redundanz Analytische Redundanz ist gegeben, wenn einer Überwachungseinheit neben den Informationen, die sie direkt durch Beobachtung des
Systems erhält, noch weitere Kenntnisse über Zusammenhänge im System vorliegen, die sie zur Fehlererkennung verwenden kann. Die nötige Redundanz in Form zusätzlicher Intelligenz erfordert nur verhältnismäßig wenig
zusätzliche Hardware. Darüber hinaus lassen sich durch den Einsatz analytischer Redundanz weitere Vorteile bei der Fehlererkennung angeben. Erkennen von Ablauffehlern Eine häufig genutzte Form der Erkennung
von Ablauffehlern ist die sogenannte Operationszeitkontrolle. Sie ist anwendbar, wenn aus der Art der Abläufe, der Struktur der Daten oder der Schaltungen eines Systems ableitbar ist, daß spezielle Ereignisse mindestens
in einem bestimmten Abstand aufeinander folgen oder daß Operationen in einer vorgegebenen maximalen Zeit beendet sein müssen. Typische Anwendungsbeispiele dieses Verfahrens ist die Totmann-Schaltung, engl.
„Watchdog-Timer“, in Prozessormodulen. Ein Zähler, der je nach zu überwachendem Prozeß mit einem bestimmten Wert initialisiert wird, liefert ein Fehlersignal, wenn er nicht rechtzeitig durch eine Fertigmeldung des
Prozesses gestoppt wird. Um den Durchsatz des Systems nicht unnötig zu mindern und um kurze Fehlererkennungszeiten zu erhalten, muß man darauf achten, daß die erlaubten Höchstzeiten so knapp wie möglich bemessen
werden. Andere Formen der Ablaufüberwachung beziehen sich auf das Auffinden verbotener Steuerzustände oder das Erkennen von unerlaubten Zustandswechseln. Beispielsweise wird so überwacht, ob ein Modul auf den
gemeinsamen Bus zugreift, ohne daß ihm dieser zugeteilt wurde, oder ob mehrere Sender gleichzeitig auf einem bidirektionalen Datenbus senden. Zur Fehlererkennung muß man also die Systemabläufe kennen. Diese lassen
sich in einem Zustandsdiagramm zusammenfassen, dessen Komplexität direkt den nötigen Aufwand an analytischer Redundanz bestimmt. Man sollte deshalb überprüfen, ob man das Diagramm mittels geigneter Reduktionsverfahren
minimieren kann. Konsistenz und Zulässigkeiten Moderne Programmiersprachen bieten die Möglichkeit, variable Werte in ihrem Gültigkeitsbereich einzuschränken. Liefert das Rechenwerk falsche Ergebnisse, oder
treten Fehler bei der Datenübertragung auf, so kann man diese erkennen, wenn die vorgegebenen Grenzen für die Ergebnisse überschritten werden. So muß beispielsweise eine errechnete Wahrscheinlichkeit immer einen Wert
zwischen Null und Eins annehmen, oder es darf keine Division durch Null erfolgen. Kann eine Einschränkung der Gültigkeitsbereiche nicht erfolgen, so kann man oft mittels einer einfachen Überschlagsrechung überprüfen, ob
sich ein Ergebnis im Rahmen des Möglichen bewegt. Durch einfache Überwachungsschaltungen kann man schon auf der Hardwareebene direkt widersprüchliche Aktionen erkennen. Beispielsweise genügt eine UND-Verknüpfung des
„Write-Signals“ und des „Chip-Select-Signals“ eines Nur-Lese-Speichers um einen verbotenen Schreibzugriff zu erkennen. Auf ähnliche Weise kann man überprüfen, ob fälschlicherweise auf einem Speicher gleichzeitig gelesen
und geschrieben werden soll, oder ob eine Adresse größer ist als der vorhandene Speicherbereich. Zum Beispiel erkennt das Rechensystem DEC-PDP-11 nichtexistierende Adreßbereiche durch einen sogenannte
„nonexisting-memory-trap“. Ein weiterer Vorschlag ist, die Operationscodes auf ihre Gültigkeit hin zu überprüfen. Eine hohe Fehlerüberdeckung kann man hierbei schon durch eine einfache Schaltung erreichen, wenn man
überprüft, welche Operationscodes am häufigsten verwendet werden und in welche nicht erlaubten Operationscodes diese am wahrscheinlichsten verfälscht werden können. Die entsprechenden Übertragungsleitungen braucht man
dann nur auf das Auftreten dieser Kombinationen hin zu überprüfen. Das Auffinden der günstigsten Kombinationen geschieht beispielsweise mit Hilfe eines Karnaugh-Diagramms. Um Daten und Adressen unterscheiden zu können
kann man Adressen mit einer geraden Parität und Daten mit einer ungeraden Parität versehen. Dadurch können z.B. falsche Speicherzugriffe oder falsche Speicherinhalte erkannt werden. Weitere Informationen, die der
Fehlererkennung dienlich sein können, sind Kenntnisse über die Konfiguration des Systems, z.B. in Bezug auf belegte und unbelegte Steckplätze, über die zulässigen Kommunikationsbeziehungen, die aussagen, welche Art von
Kommunikation zwischen welchen Modulen erlaubt ist und über die Zugriffsrechte der Module. Im vierten und abschließenden Teil dieser Serie wird die Fehlererkennung durch Tests erläutert. Außerdem werden Aussagen zur
Fehlerbehandlung und Fehlerlokalisierung getroffen. Literatur
Autor improve Erschienen in Datacom 12/91, Seiten 120 - 128 |
||