PatentDe  


Dokumentenidentifikation DE69831732T2 29.06.2006
EP-Veröffentlichungsnummer 0000961972
Titel VERFAHREN UND GERÄT ZUM KORRIGIEREN VON FEHLERN IN EINEM RECHNERSYSTEM
Anmelder Transmeta Corp., Santa Clara, Calif., US
Erfinder KLAIBER, Alex, Mountain View, US;
BEDICHEK, Robert, Palo Alto, US;
KEPPEL, David, Seattle, US
Vertreter Rummler, F., Dipl.-Ing.Univ., Pat.-Anw., 81669 München
DE-Aktenzeichen 69831732
Vertragsstaaten AT, BE, CH, DE, DK, ES, FI, FR, GB, GR, IE, IT, LI, LU, MC, NL, PT, SE
Sprache des Dokument EN
EP-Anmeldetag 13.02.1998
EP-Aktenzeichen 989050513
WO-Anmeldetag 13.02.1998
PCT-Aktenzeichen PCT/US98/02673
WO-Veröffentlichungsnummer 0098038575
WO-Veröffentlichungsdatum 03.09.1998
EP-Offenlegungsdatum 08.12.1999
EP date of grant 28.09.2005
Veröffentlichungstag im Patentblatt 29.06.2006
IPC-Hauptklasse G06F 11/00(2006.01)A, F, I, 20051017, B, H, EP
IPC-Nebenklasse G06F 11/16(2006.01)A, L, I, 20051017, B, H, EP   G06F 11/36(2006.01)A, L, I, 20051017, B, H, EP   

Beschreibung[de]
HINTERGRUND DER ERFINDUNG Gebiet der Erfindung

Diese Erfindung betrifft Computersysteme und insbesondere Systeme für die schnelle und akkurate Fehlerbeseitigung in Computersystemen.

Geschichte des Standes der Technik

Es ist oft wünschenswert, Fehler in einem Computerprozess oder einem Computersystem zu erkennen. Zu diesem Zweck wird in der Regel das Verhalten des konstruierten Systems (das "Testsystem") mit Modellen eines Systems (das "Referenzsystem") verglichen, von denen man weiß, dass sie korrekt funktionieren. Wenn das Verhalten des Testsystems mit dem Verhalten des Referenzsystems übereinstimmt, so wird davon ausgegangen, dass das Testsystem richtig funktioniert. Wenn das Verhalten der Systeme sich unterscheidet, so wurde ein Fehler festgestellt.

Es gibt viele Möglichkeiten, das Verhalten zweier Systeme zu vergleichen. Eine davon ist, jedes System zu veranlassen, einen Strom interner oder externer Ereignisse, wie beispielsweise Vorgangsaufrufe, Zustandsübergänge oder Bussignale, zu erzeugen und die beiden Ströme miteinander zu vergleichen. Es kann aber sein, dass einige Ereignisströme zu schwierig zu erfassen sind, als dass ein Vergleich der Ereignisströme praktikabel wäre. Bei anderen Ereignisströmen kann das Erfassen zu teuer sein. Wieder andere Ereignisströme sind vielleicht zu grob strukturiert, um Fehler in brauchbarer Weise orten zu können. Bei einigen Ereignisströmen hängen die Ereignisse möglicherweise zu sehr von den Systemimplementierungen ab und können damit unvergleichbar sein.

Eine weitere Vergleichstechnik besteht darin, beide Systeme arbeiten zu lassen, den Zustand der Systeme während des Betriebes aufzuzeichnen und dann den Zustand der Systeme zu vergleichen. Beim Zustandsvergleich können sich die gleichen Arten von Problemen einstellen wie beim Vergleich von Ereignisströmen. Der Zugriff auf einige Zustände kann teuer oder unmöglich sein oder zu sehr von den Implementierungsdetails der beiden Systeme abhängen.

Es können verschiedene Verfahren verwendet werden, um den Vergleich von Zuständen oder Ereignissen zu bewerkstelligen. Wenn das Referenzsystem vom informalen oder nicht-ausführbaren Typ ist, so war das Verfahren üblicherweise eine Ad-hoc-Suche nach verschiedenen Testzuständen oder Ereignissen, die nicht mit Zuständen oder Ereignissen übereinstimmen, die vom Referenzsystem erzeugt wurden. Natürlich besteht bei diesem Verfahren die große Gefahr, wichtige Probleme, die im Testsystem vorliegen, zu übersehen.

Wenn es sich bei dem Referenzsystem um eine ausführbare Spezifikation handelt, so wäre es wünschenswert, wenn man die beiden Systeme einfach gleichzeitig laufen lassen und den Zustand in jedem Augenblick vergleichen könnte, um Unterschiede festzustellen. Die oben angesprochenen Probleme erschweren dies noch.

Der exakte Vergleich des Systemzustands nach jedem Schritt ist nicht generell möglich. Erstens unterscheiden sich das Testsystem und das Referenzsystem zwangsläufig auf die eine oder andere Weise (wie beispielsweise Funktion, Implementierung oder Leistung), so dass der Gesamtzustand der Systeme sich nicht jederzeit vergleichen lässt. Bei einigen Systemen ist der Gesamtzustand möglicherweise niemals vergleichbar. Beispielsweise ist es oft wünschenswert, den Zustand eines Testsystems, das sich vom Referenzsystem erheblich unterscheidet, so zu vergleichen, als würde man ein Anwendungsprogramm von einem Typ von Prozessor, der ein erstes Betriebssystem ablaufen lässt, zu einem anderen Typ von Prozessor, der ein zweites Betriebssystem ablaufen lässt, übertragen. Worauf es ankommt, ist, dass das Testsystem die gleichen Endergebnisse hervorbringt wie das Referenzsystem. Da sich die Prozessoren und Betriebssysteme voneinander unterscheiden, unterscheiden sich wahrscheinlich auch die Operationen, die in jedem Augenblick des Betriebes der beiden Systeme ausgeführt werden (und damit auch der Zustand).

Zweitens kann es in einem unvertretbar hohen Maße teuer sein, den Zustand nach jeder Operation durch jedes System wiederholt zu vergleichen. Um den Zustand der beiden Systeme zu vergleichen, müssen der gesamte Speicher (eventuell einschließlich des Speichers der zweiten Ebene) und alle Register der beiden Systeme verglichen werden, um zu sehen, ob sie einander gleichen. Die bloße Größe des Zustandsvergleichs macht dies teuer.

Schließlich kann es sein, dass einige Zustandsinformationen nicht verfügbar sind, beispielsweise ein Zustand in nicht-lesbaren Prozessorregistern oder ein Zustand, der implizit in einem der Systeme dargestellt ist. Darum muss der Vergleich oft selektiv erfolgen.

Doch obgleich der Zustandsvergleich an allen Punkten während der Ausführung schwierig ist, ist es möglich, Punkte auszuwählen, an denen die Ergebnisse des Test- und des Referenzsystems sich gleichen sollten. An diesen Punkten kann ein Zustandsvergleich erfolgen. Bis heute wurde aber noch kein automatisiertes oder schnelles Verfahren zum Vergleichen von Systemen ersonnen.

Es ist wünschenswert, ein Verfahren und eine Vorrichtung zum schnellen Erkennen von Fehlern in einem Testsystem bereitzustellen.

Insbesondere ist es wünschenswert, ein Verfahren und eine Vorrichtung zum Erkennen von Fehlern in einem Computerprozess oder einem Computersystem bereitzustellen.

Terayama, F. und Mitarbeiter, "Self-checking and recovering microprocessor G100FTS for fault-tolerant systems", Custom Integrated Circuits Conference, 1993, Tagungsbericht der IEEE 1993, San Diego, CA, USA, 9.–12. Mai 1993, New York, NY, USA, IEEE, 9. Mai 1993, Seiten 421 bis 424, offenbart einen anwendungsspezifischen Prozessor, der zwei Mikroprozessoren integriert, von denen einer die Master-Operation und der andere die Prüfoperation ausführt. Es werden Zustände der beiden Mikroprozessoren verglichen, und wenn ein Fehler festgestellt wird, so wird der Betrieb angehalten, zu einem zuvor gespeicherten Zustand zurückgefahren und erneut ausgeführt. Auf diese Weise werden fehlerhafte Mikroprozessoren entdeckt.

Kurzdarstellung der Erfindung

Aspekte der Erfindung sind in den begleitenden Ansprüchen dargestellt.

Bei einer besonderen Ausführungsform wird die Ausführung von Abschnitten der Befehlsfolge zwischen auswählbaren vergleichbaren Punkten auf dem Referenzsystem und auf dem Testsystem automatisch wiedergegeben, wenn ein Unterschied bei dem verglichenen Zustand der Systeme entdeckt wird.

Diese und weitere Merkmale der Erfindung werden anhand der folgenden detaillierten Beschreibung in Verbindung mit den Zeichnungen, bei denen in den verschiedenen Ansichten gleiche Elemente mit gleichen Bezugszahlen versehen sind, besser verstanden.

Kurze Beschreibung der Zeichnungen

1 ist ein Blockschaubild eines Systems, das gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung konstruiert wurde.

2 ist ein Blockschaubild einer Ausführungsform eines Systems, das gemäß der vorliegenden Erfindung konstruiert wurde.

3 ist ein Schaubild, das einen Prozess gemäß der vorliegenden Erfindung veranschaulicht.

Detaillierte Beschreibung

Wenden wir uns nun 1 zu, wo ein Blockschaubild einer Vorrichtung veranschaulicht ist, die gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung konstruiert wurde. Bevorzugte Ausführungsformen der vorliegenden Erfindung verwenden einen Steuermechanismus 10, der Befehle von einem Programm 12 empfängt, das er auf einem Testsystem 15 ausführen soll, und ein oder mehrere Referenzsysteme 16, die Eingabe-/Ausgabe-Geräte oder Modelle 18 verwenden. Das Programm 12 kann eine Hardware oder ein Softwareprogramm oder -prozess oder eine Variation davon sein. Das Testsystem 15 und das Referenzsystem 16 können jeweils Hardware, Software oder eine Kombination daraus sein. Der Steuermechanismus 10 steuert die Ausführung des Programms 12 sowohl durch das Testsystem 15 als auch durch das Referenzsystem 16. Das Programm 12 ist in der Figur zwar als separate Entität gezeigt, doch es kann auch in die Systeme eingebettet sein oder von außerhalb des Systeme eingespeist werden. Das Programm 12 kann für jedes der Systeme unterschiedliche Darstellungen aufweisen, muss aber auf irgend einer Stufe die gleichen Ergebnisse errechnen. Bei dem Steuermechanismus 10 kann es sich um eine beliebige Steuerung handeln, die geeignet ist, das Programm 12 in Schritten ablaufen zu lassen und den Zustand der beiden Systeme in Schritten zu lesen oder zu verifizieren.

Prinzipiell wäre es möglich, das Programm 12 dergestalt auszuführen, dass es in einzelnen Schritten ausgeführt wird, und den Zustand der Systeme bei jedem Schritt zu vergleichen. Es ist aber oft unvertretbar teuer, eine große Menge an Zustandsdaten bei jedem Schritt zu vergleichen. Außerdem ist ein einfaches schrittweises Voranschreiten vielleicht gar nicht möglich. Beispielsweise können einige Ergebnisse durch ein System in einer bestimmten Reihenfolge errechnet werden und durch ein anderes System in einer anderen Reihenfolge. Statt dessen verwenden Ausführungsformen der vorliegenden Erfindung den Steuermechanismus 10 zur Ausführung mehrerer oder vieler Schritte in dem Test- und dem Referenzsystem. Somit kann der Steuermechanismus eine bekannte und oftmals große Anzahl von Schritten des Programms 12 in dem Testsystem 15 ausführen und dann die Ausführung der Schritte in dem Referenzsystem 16 wiederholen. Dann kann ein Zustandsvergleich vorgenommen werden. Durch Ausführen einer Anzahl von Schritten vor dem Vergleich amortisieren sich die Kosten des Vergleichs über mehrere Schritte, und Ausführungsformen der vorliegenden Erfindung sind ebenso in der Lage, Fehler in Systemen zu finden, die keine identischen Berechnungen bei jedem Schritt ausführen.

Der Steuermechanismus 10 führt ein Vergleichsprädikat (einen zu bewertenden Ausdruck) aus, der eine Bewertung hinsichtlich wahr oder falsch vornimmt. Das Vergleichsprädikat braucht nicht in der Steuerung 10 eingebettet zu sein und kann je nach den zu testenden Systemen, der Art der analysierten Fehler und Kompromissen zwischen der Leistung und der Genauigkeit der Fehlerortung variieren. Außerdem kann sich das Vergleichsprädikat während der Ausführung ändern. Wenn beispielsweise das Referenzsystem und das Testsystem beides Prozessoren sind, so kann das Vergleichsprädikat häufig eine Schnellprüfung der vom Benutzer einsehbaren Register beider Prozessoren ausführen und kann ebenfalls periodisch eine teurere, aber auch umfassender Prüfung versteckter Register und Speicher ausführen.

Es ist zu beachten, dass sowohl das Testsystem als auch das Referenzsystem einen Zustand haben können, der nie für einen Vergleich verwendet wird und der darum im Vergleich ignoriert wird. Gleichermaßen kann jedes System einen Zustand auf verschiedene Weise darstellen, dergestalt, dass das Vergleichsprädikat oder sein Surrogat eine Zustandsumwandlung vornehmen müssen, um den Vergleich auszuführen. Der Begriff des "Zustandes" kann dahingehend ausgeweitet werden, dass er den Zustand eines Ereignisprotokolls beinhaltet, um sich des Ereignisstrom-Debugging bedienen zu können. Beispielsweise kann das Prädikat Elemente in einem zeitgestempelten Eingangs-/Ausgangs-Protokoll vergleichen, um zu gewährleisten, dass das externe Verhalten beider Systeme das gleiche ist. Schließlich kann das Prädikat genäherte Informationen errechnen, beispielsweise eine Prüfsumme und eine zyklische Redundanzprüfung (ZRP) einer Gruppe von Werten, anstatt alle Werte explizit zu vergleichen.

Das Steuerprogramm 10 steuert die Ausführung auf der Grundlage einer Anzahl von Prämissen. Zunächst wird man erkennen, dass, wenn das gleiche Programm 12 durch zwei Systeme korrekt ausgeführt wird, die einzelnen Befehle, die durch die beiden Systeme ausgeführt werden, verschieden sein können, es aber Punkte gibt, wo bestimmte Teile der Zustände der beiden Systeme äquivalent sein müssen, wenn das Testsystem und das Referenzsystem jeweils korrekt funktionieren, so dass sie zu den gleichen Ergebnissen kommen. Diese Punkte werden in der vorliegenden Spezifikation als "vergleichbare Punkte in virtueller Zeit" oder einfach als "vergleichbare Punkte" bezeichnet. Ein Referenzsystem kann beispielsweise ein einfacher Prozessor (wie beispielsweise ein RISC-Prozessor) in Kombination mit einem Simulator sein, der dafür verwendet wird, einen komplexen Prozessor (wie beispielsweise einen CISC-Prozessor) zu emulieren, während ein Testsystem ein solcher komplexer Prozessor sein kann. Das Referenzsystem führt in der Regel mehrere Befehle aus, um das Verhalten eines einzelnen Befehls im Testsystem zu imitieren. Folglich ist der Zustand des Referenzsystems nur zu Zeiten vergleichbar, die ganzen Befehlen entsprechen, die in dem Testsystem ausgeführt werden.

Ausführungsformen der vorliegenden Erfindung basieren außerdem auf der Erkenntnis, dass – auf einer bestimmten Stufe – die Operationen korrekt funktionierender Computersysteme deterministisch sind. Wenn also eine Befehlsfolge in einem Prozessor abzulaufen begonnen hat, so werden die Ergebnisse dieser Befehle durch den anfänglichen Maschinenzustand determiniert, mit Ausnahme von Ereignissen, die außerhalb der Befehlsfolge liegen, wie beispielsweise Interrupts und Eingabe-/Ausgabe-Operationen. Nur diese externen Operationen können eine Änderung der Art und Weise bewirken, in der das Programm im System ausgeführt wird. Um bei einigen Ausführungsformen diese Änderungen auszuschalten, nutzen das Referenzsystem und das Testsystem das Verhalten einer einzelnen Gruppe von Vorrichtungsmodellen gemeinsam. Das vereinfacht eine Vielzahl von Zustandsvergleichsproblemen. Ein weiterer Vorteil ist, dass die Fehlerbeseitigung mit einer einzelnen Gruppe von Vorrichtungen beträchtlich schneller sein kann als mit separaten Vorrichtungen für beide Systeme. Ausführungsformen der vorliegenden Erfindung nehmen externe Ereignisse von den Vorrichtungsmodellen 18 und lassen sie durch das Testsystem und das Referenzsystem gemeinsam nutzen. Der Steuermechanismus 10 gewährleistet, dass die externen Ereignisse dem Testsystem und dem Referenzsystem an den gleichen vergleichbaren Punkten in virtueller Zeit dargeboten werden, so dass externe Ereignisse die gleichen Auswirkungen haben. Folglich führen die beiden Systeme 15 und 16 theoretisch Programme aus, die bei identischen externen Ereignissen identische Ergebnisse erbringen. Es sollte jedoch klar sein, dass zwischen jeweils zwei vergleichbaren Punkten, an denen externe Ereignisse geschehen, eine große Anzahl vergleichbarer Punkte vorhanden sein kann.

Die Erkenntnis, dass bei korrekt funktionierenden Computersystemen – sobald der Ablauf einer Befehlsfolge in einem Prozessor begonnen hat – die Ergebnisse dieser Befehle determiniert werden (mit Ausnahme von Ereignissen, die außerhalb der Befehlsfolge liegen, und der Ausschaltung asynchroner externer Ereignisse), erlaubt Vergleiche an vergleichbaren Punkten in virtueller Zeit während der Ausführung des Programms durch die beiden Systeme. Der Steuermechanismus 10 vergleicht periodisch einen Abschnitt des Zustands des Referenzsystems und des Testsystems. Wenn Teile des Zustands der Systeme an einem vergleichbaren Punkt variieren (gemäß dem Vergleichsprädikat nicht kompatibel sind), so ist man auf einen Fehler (eine "Divergenz" genannt) gestoßen. Zu der Divergenz kann es an einem beliebigen Punkt seit dem letzten Zustandsvergleich gekommen sein. Das Erkennen einer Divergenz unter Verwendung vergleichbarer Punkte, an denen genügend Zustandsdaten in sinnvoller Weise zur Verfügung stehen, um Systemfehler zu erkennen, stellt merkliche Fortschritte gegenüber Fehlererkennungssystemen nach dem Stand der Technik dar.

Ausführungsformen der vorliegenden Erfindung können außerdem automatisch den Fehlerbereich verkleinern, indem sie über eine virtuelle Zeit seit dem letzten Zustandsvergleich, bei dem Zustandsidentität angezeigt wurde, sucht. Zu diesem Zweck wird die Ausführung des Programms am frühesten vergleichbaren Punkt, an dem eine Abweichung der Zustände festgestellt wird, angehalten. Dank der Fähigkeit, externe Ereignisse, die während Ausführung und Wiedergabe gemeinsam genutzt werden können, aufzuzeichnen und wiederzugeben, ist es möglich, an einen früheren vergleichbaren Punkt zurückzukehren und anschließend eine Ausführung in Vorwärtsrichtung zu wiederholen und zu den gleichen Ergebnissen zu gelangen. Dies ermöglicht die "Wiedergabe" eines Abschnitts des Programms, der ausgeführt wurde und in dem ein Fehler geschah. Um die Wiedergabe zu unterstützen, prüft der Steuermechanismus 10 periodisch das Test- und das Referenzsystem an zuvor ausgewählten vergleichbaren Punkten während der Ausführung des Programms durch die Systeme oder zeichnet den Zustand des Test- und des Referenzsystems an zuvor ausgewählten vergleichbaren Punkten während der Ausführung des Programms durch die Systeme auf. Der Betrieb der Systeme kann dann an einen älteren Prüfpunkt zurückgeführt werden, wo eine Abweichung erkannt wurde, und das Programm 12 kann dann vorwärts zum gewünschten vergleichbaren Punkt ausgeführt werden.

Ein Prüfpunkt braucht nicht den gesamten Systemzustand zu erfassen, er muss aber genügend Zustandsdaten liefern, um die Ausführung erneut zu starten. Den Zustand an mehr Stellen zu prüfen, führt im Allgemeinen zu einer höheren Fehlerbeseitigungsgenauigkeit. Das punktuelle Prüfen kann mit beliebigen Perioden von "niemals" bis "bei jedem Schritt" erfolgen. Das Ändern des Prüfpunktintervalls wirkt sich auf die Leistung sowohl der Vorwärtsausführung als auch der Wiedergabe aus. Die Wiedergabe stützt sich außerdem auf ein Protokoll externer Ereignisse. Wenn die Ausführung für eine Wiedergabe gestartet wird, so werden die externen Ereignisse dem Protokoll entnommen, um ein deterministisches Verhalten bei der Wiedergabe zu gewährleisten.

Es sind viele Suchtechniken möglich. Welche man am besten wählt, kann beispielsweise von den Relativgeschwindigkeiten von Vorwärtsausführung und Wiedergabe, des Zustandsvergleichs und dergleichen abhängen. Des Weiteren kann, wenn ein Fehler erkannt wird, der Steuermechanismus 10 zur Verwendung eines umfassenderen oder genaueren Zustandsvergleichsprädikats umschalten. Bei einer Ausführungsform kann der Steuermechanismus 10 eine binäre Suche in virtueller Zeit wie folgt ausführen. Der Steuermechanismus 10 kann den Beginn der Wiedergabe auf einen früheren vergleichbaren Punkt einstellen, an dem ein Zustandsvergleich erfolgreich war, wahrscheinlich der letzte Vergleich auf einem strengsten Niveau. Die große Anzahl an vergleichbaren Punkten, die es zwischen jeweils zwei vergleichbaren Punkten geben kann, an denen es zu externen Ereignissen kommt, erlaubt eine relativ fein strukturierte Isolation von Fehlern, nachdem eine Abweichung erkannt wurde. Der Steuermechanismus 10 kann das Ende der Wiedergabe auf den vergleichbaren Punkt setzen, an dem der Zustandsvergleich nicht erfolgreich war, und kann dann die Wiedergabe des Programms zu einem vergleichbaren Zwischenpunkt auf halbem Weg zwischen Anfang und Ende ausführen. Der Zustand der Systeme wird dann an diesem Zwischenpunkt erneut verglichen. Wenn der Zustandsvergleich an dem Zwischenpunkt nicht erfolgreich ist, so wird das Ende der Wiedergabe auf den vergleichbaren Zwischenpunkt gesetzt, und die Suche geht weiter, wobei die Wiedergabe an demselben Anfangspunkt beginnt und zu einem zweiten vergleichbaren Zwischenpunkt auf halbem Weg zwischen dem Anfang und dem neuen Endpunkt fortgeführt wird. Der Zustand der Systeme wird dann an dem Zwischenpunkt erneut verglichen. Wenn der Zustandsvergleich erfolgreich ist, so wird der Beginn auf den vergleichbaren Zwischenpunkt gesetzt, und die Suche geht weiter. Auf diese Weise wird die Suche nach einem Fehler rasch eingegrenzt.

Es gibt verschiedene Umstände, die die Suche beenden können. Beispielsweise kann der Steuermechanismus 10 die Divergenzsuche beenden, wenn der Suchbereich so klein wird, dass er nicht weiter verkleinert werden kann. An diesem Punkt wird die Divergenz als "gefunden" betrachtet. Der kleinste Bereich hängt von dem Test- und dem Referenzsystem und von dem ausgeführten Programm ab. Der Fehler kann dem Benutzer gemeldet werden.

Die Art und Weise, in der der Steuermechanismus 10 das Test- und das Referenzsystem von asynchronen externen Ereignissen isoliert, indem sowohl dem Test- als auch dem Referenzsystem dieselben externen Ereignisse dargeboten werden, bietet eine Reihe von Vorteilen neben der Fähigkeit, eine Übereinstimmung zu gewährleisten und die Wiedergabeausführung des Programms 12 zu ermöglichen. Beispielsweise kann der Steuermechanismus über beliebige Segmente der Ausführung des Programms 12 selektiv die Rate und die Verteilung externer Ereignisse über beliebige Segmente der Ausführung des Programms 12 verändern. Dadurch kann der Steuermechanismus Testsituationen wie beispielsweise ungewöhnlich hohe Eintreffraten für externe Ereignisse erzeugen.

Der Steuermechanismus 10 kann des Weiteren eine "Störungsanalyse" ausführen, indem er ein Ausführungssegment, in dem ein erfolgreicher Zustandsvergleich stattgefunden hat, wiederholt. Jedes Mal, wenn die Ausführung wiederholt wird, kann der Anfangszustand oder die Einspeisung externer Ereignisse geändert werden, jedoch in solcher Weise, dass sich das Endergebnis der Ausführung nicht ändert. Wenn der Endzustand sich von Durchgang zu Durchgang doch ändert, so wurde ein Fehler entdeckt. Die oben angesprochenen Fehlerisolationstechniken können dafür verwendet werden, die Fehlerstelle zeitlich anhand eines Vergleichs mit Referenzsystemen einzugrenzen. Beispielsweise kann man einen kritischen Abschnitt des Programms 12 mehrere Male ablaufen lassen, und jedes Mal kann der Steuermechanismus 10 einen Interrupt bei einem anderen Befehl in der Folge ausgeben oder den anfänglichen Inhalt von Caches im Test- oder im Referenzsystem ändern.

Ausführungsformen der Erfindung sind dafür beschaffen, mit Systemen unterschiedlicher Komplexitätsgrade zu funktionieren. Beispielsweise kann das Testsystem Registerumbenennungs- oder ähnliche Techniken zur Leistungssteigerung verwenden. Einige Daten können sich bei einem System in einem Hardware- oder Software-Cache und bei einem anderen System im Hauptspeicher befinden, oder sie können implizit in einem einzigen System dargestellt sein (was die Rekonstruktion der betreffenden Daten erfordert, um einen Zustandsvergleich zu bewirken). Um den Zustand zu vergleichen, ruft das Vergleichsprädikat Surrogate im Referenzsystem und im Testsystem auf, um den Zustand anhand des Namens anstatt anhand des Ortes zu vergleichen.

Es gibt viele Ausführungsformen der vorliegenden Erfindung. Bei einer Ausführungsform ist das Referenzsystem 16 ein einfacher Decodier- und Abfertigungsinterpretierer, während das Testsystem die gleichen Eingabeprogramme unter Verwendung dynamischer Kompilierung von virtuellem Maschinencode zu nativem Maschinencode ausführt. Um vergleichbare Punkte in virtueller Zeit beizubehalten, inkrementiert das Referenzsystem die virtuelle Zeit für jeden eingeholten Befehl, während das Testsystem die virtuelle Zeit unter Verwendung von Instrumentierungscode inkrementiert, der in jeden dynamisch kompilierten Block eingefügt wurde. Das Vergleichsprädikat vergleicht nur den Zustand für die virtuelle Maschine, die von jedem System ausgeführt wird.

Eine besonders brauchbare Ausführungsform der vorliegenden Erfindung, die in 2 gezeigt ist, verwendet ein Softwaresteuerungsprogramm 20, das über ein Debuggerprogramm 14 Befehle von einem Programm 12 erhält, das es auf den zwei verschiedenen Systemen ausführen soll. Bei dem Debuggerprogramm 14 kann es sich um ein beliebiges brauchbares Programm handeln, das in der Lage ist, ein Mittel bereitzustellen, mit dem das Programm in Schritten abgearbeitet werden kann und der Zustand des Systems, auf dem das Programm läuft, in gewünschten Inkrementen getestet werden kann. Das Steuerprogramm 20 steuert die Operationen sowohl eines Referenzsystems 16 als auch des Testsystems 15 bei der Ausführung des Programms 12.

Bei dieser Ausführungsform der Erfindung simuliert das Testsystem 15 einen Prozessor, der ein Übersetzungsprogramm 13 verarbeitet, das Befehle des Programms 12 dynamisch in Befehlsreihen übersetzt, die der Prozessor ausführen kann, um Ergebnisse der Befehle des Programms 12 zu erbringen. Bei der Ausführung des Programms 12 mittels des Debuggers 14 veranlasst das Steuerprogramm 20 das System 16, eine bekannte und oft große Anzahl der ursprünglichen Befehle des Programms 12 auszuführen, und wiederholt dann die Ausführung dieser Befehle unter Verwendung des Systems 15.

Das Steuerprogramm 20 steuert die gesamte Ausführung durch die beiden Systeme 15 und 16. In 2 empfängt die Debuggersoftware 14 eine Befehlsfolge von dem Programm 12, von dem man weiß, dass es auf einem bestimmten Computersystem läuft, wie beispielsweise einem Computer, der mit einem Intel X86-Mikroprozessor arbeitet. Ein Steuerprogramm 20, das gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung geschrieben ist, bildet eine typische Computersystemschnittstelle zur Debuggersoftware 14 und steuert die Anwendung der Befehle auf das Test- und das Referenzsystem 15 bzw. 16. Das Steuerprogramm 20 stellt die gleiche Schnittstelle für die Debuggersoftware 14 dar wie die Systeme 15 und 16 für das Steuerprogramm 20. Das Steuerprogramm 20 setzt sich auch zwischen die Systeme 15 und 16 und deren Vorrichtungen 18, um das Protokollieren und Wiedergeben von externen Ereignissen zu besorgen.

Es gibt viele Möglichkeiten, vergleichbare Punkte in virtueller Zeit beizubehalten. Bei einer Ausführungsform wird das Programm 12 durch ein Übersetzungsprogramm 13 in Befehle für einen Befehlssatz übersetzt, der auf dem Testsystem 15 ausgeführt wird. Das Testsystem 15, das einen Mikroprozessor, der mit diesem Übersetzungsprogramm 13 kombiniert ist, beinhaltet, ist dafür konstruiert, Programme eines Befehlssatzes auszuführen, der ursprünglich dafür vorgesehen ist, in einem Mikroprozessor ausgeführt zu werden, der durch das Referenzsystem 16 definiert wird. Um die Festlegung von vergleichbaren Punkten in virtueller Zeit zu ermöglichen, an denen der Zustand der Ursprungsprogramms 12 und die Befehle, die von dem Übersetzungsprogramm 13 übersetzt wurden, die gleichen sind, bildet das Übersetzungsprogramm 13 die Punkte in der Übersetzung ab, die mit dem Ende jedes Befehls des Programms 12 übereinstimmen und die somit die vergleichbaren Punkte anzeigen, die zum Vergleichen der beiden Simulationsmodelle 15 und 16 verwendet werden können. Das Steuerprogramm 20 hält nach diesen vergleichbaren Punkten Ausschau, wenn es bestimmt, wann und wo es die Ausführung der Befehlsfolgen auf den Systemen 15 und 16 beginnt und beendet.

Zusätzlich zur Verwendung dieser Zeitbereichsabbildung stellt das Steuerprogramm 20 ein Mittel zum Erkennen der Abbildung des Adressraumes der beiden Simulationsmodelle 15 und 16 an den vergleichbaren Punkten in der Ausführung des Programms 12 durch die beiden Systeme 15 und 16 bereit. Beispielsweise kann das eine oder das andere der Systeme Registerumbenennungs- oder ähnliche Techniken verwenden, um die Verarbeitung zu beschleunigen. Um die Übereinstimmung der Zustände mittels der beiden Systeme 15 und 16 zu testen, müssen die Register ermittelt werden, die tatsächlich Daten enthalten, die die gleichen sein müssen. Gleichermaßen können in einem System Speicherdaten in einem Prozessorcache, aber noch nicht im Speicher gespeichert werden, während in dem anderen System die gleichen Daten vielleicht schon im Hauptspeicher gespeichert wurden. Auch hier muss wieder der richtige Speicher verglichen werden, um brauchbare Ergebnisse zu erhalten. Bei einer Ausführungsform fragt das Steuerprogramm 20 die von ihm kontrollierten Systeme nach abstrakten Registern oder Speichernamen ab. Surrogate im Test- und im Referenzsystem verwenden private Abbildungen von abstrakten Namen zu Speicherorten, um die gewünschten Daten bereitzustellen.

Nachdem sie mit diesen beiden Abbildungen versehen wurde, wird eine ausgewählte Befehlsfolge vom Programm 12 durch die Debuggersoftware 14 an das Steuerprogramm 20 zur Ausführung gesandt. Die Debuggersoftware 14 ermöglicht in der Regel die Fähigkeit, ein Programm in Folgen auszuführen, die von einem Nutzer festgelegt wurden, und Zustände des ausführenden Modells zu ausgewählten Zeiten zu ermitteln, aber ist nicht in der Lage, Vergleiche zwischen der Ausführung eines Programms auf einem System oder einem anderen anzustellen. Die Debuggersoftware 14 sendet die Befehlsfolge an das Steuerprogramm 20. Das Steuerprogramm 20 sendet die Befehlsfolge an das Referenzsystem 16, das die Befehlsfolge abarbeitet. Das Steuerprogramm 20 zeichnet den Zustand des Systems 16 am Anfang der Folge auf, bevor es die Ausführung der Folge auf dem System 16 beginnt. Während die Befehlsfolge auf dem System ausgeführt wird, zeichnet das Steuerprogramm 20 jedes externe Ereignis auf und versieht es mit einem Zeitstempel. Somit zeichnet das Steuerprogramm 20 jede Eingabe-/Ausgabe-Operation auf, einschließlich der Befehle, Adressen und Daten, die zu einer simulierten Eingabe-/Ausgabevorrichtung 18 übertragen wurden, und der Antworten, die von den simulierten Vorrichtungen 18 zu dem System 16 zurückgesandt wurden. Das Steuerprogramm 20 zeichnet außerdem jede Ausnahme auf, auf die das System 16 während der Folge reagiert.

Als nächstes führt das Steuerprogramm 20 die gleiche Befehlsfolge auf dem Testsystem 15 bis zum abschließenden vergleichbaren Punkt der Folge aus. Bei der Ausführung der Befehlsfolge werden die externen Operationen (Eingabe/Ausgabe oder Ausnahme), die für das Referenzsystem 16 aufgezeichnet wurden, aus dem Protokoll der Ergebnisse verwendet, die aus der Ausführung der Folge durch das System 16 gewonnen wurden. Wenn also das System 16 eine Eingabe-/Ausgabeoperation veranlasst hat, so wird die extern erzeugte Reaktion auf diese Operation dem System 15 zugeleitet. Auf diese Weise sind die Rücklaufwerte mit jenen identisch, die dem Referenzsystem 16 zugeführt wurden, so dass das Ergebnis innerhalb des Testsystems 15 das gleiche sein sollte wie das Ergebnis innerhalb des Systems 16. Gleichermaßen wird, wenn das System 16 einen Interrupt erhalten hat, der Interrupt durch das Steuerprogramm 20 aufgezeichnet und wird später dem Testsystem 15 zugeleitet, so dass seine Reaktion die gleiche sein sollte wie die Reaktion des Referenzsystems 16, wenn das Testsystem 15 korrekt arbeitet. Durch die Verwendung der externen Ereignisse, die bei der Ausführung des Programms 12 durch das System 16 protokolliert wurden, wird der Aufwand des Simulierens von Vorrichtungen vermieden, die mit dem zweiten Modell korrekt funktionieren; es wird gewährleistet, dass die externen Ereignisse, welche die Simulationen beeinflussen, identisch sind; und es wird dadurch die Möglichkeit ausgeschaltet, dass die Programmausführung infolge asynchroner externer Ereignisse schwankt.

Die Folge wird auf diese Weise auf dem System 15 vollendet. Dann wird der Zustand der beiden Systeme verglichen. Wenn der Zustand der beiden Systeme am Ende der Folge der gleiche ist, so wird eine zweite Befehlsfolge vom Programm 12 an den Debugger 14 zur Ausführung auf den beiden Systemen 15 und 16 geschickt.

Wenn die Ausführung einer Befehlsfolge von dem Programm 12 zu verschiedenen Zuständen am vergleichbaren Punkt im Test- und im Referenzsystem führt, so wird das Programm 12 ab einem früheren vergleichbaren Prüfpunkt in der Ausführung, an dem der Vergleich einen identischen Zustand ergab, erneut abgespielt. Bei der im vorliegenden Text beschriebenen konkreten Ausführungsform lässt man den Prozess in einem binären Suchmodus in der oben erläuterten Weise erneut ablaufen. Bei der Wiedergabe der Ausführung einer vorangegangenen Befehlsfolge ist es nützlich, das Protokoll der externen Ereignisse, die zuvor während der Ausführung durch das Referenzsystem aufgezeichnet wurden, zu verwenden, um Veränderungen bei den externen Ereignissen für die Ausführung auf beiden Systemen auszuschalten. Wenn eine erste Hälfte der Folge zum gleichen Zustand an einem mittleren vergleichbaren Punkt führt, so wird eine erste Hälfte der zweiten Hälfte der Befehlsfolge für das Test- und das Referenzsystem wiedergegeben. Dieses binäre Testen von Abschnitten der Folge wird so fortgesetzt, dass der Divergenzpunkt der beiden Simulationen rasch isoliert wird.

Wie zu erkennen ist, ermöglicht dieses binäre Testen auf Fehler in der Ausführung einer Befehlsfolge ein sehr schnelles Isolieren des Fehlerpunktes. Die Suche zur Isolierung von Fehlern braucht keine binäre Suche zu sein. Wenn beispielsweise das Ausführen des Programms weniger zeitaufwändig ist als die Umkehrung des Programms, um einen jüngsten vergleichbaren Punkt zu finden, an dem die Zustände übereinstimmten, so kann es schneller sein, kleinere Abschnitte des Programms wiederzugeben und dadurch die Anzahl der Male zu verringern, die erforderlich sind, um das Programm zur Fehlerisolierung umzukehren. In jedem Fall gestattet die Fähigkeit, die beiden Modelle im Wesentlichen parallel durch eine lange Befehlsfolge, die in der Länge variieren kann, unter der Steuerung des Bedieners oder des Steuerprogramms ablaufen zu lassen, eine sehr schnelle und präzise Fehlerbeseitigung in dem Slave-Simulationsmodell ohne den mühsamen Schritt-für-Schritt-Prozess, den der Stand der Technik verlangt.

Obgleich Ausführungsformen der vorliegenden Erfindung anhand einer bevorzugten Ausführungsform beschrieben wurden, versteht es sich, dass der Fachmann verschiedene Modifikationen und Änderungen vornehmen könnte.


Anspruch[de]
  1. System zum Korrigieren von Fehlern in einem Computersystem, umfassend:

    ein Testsystem (15), in dem Fehler korrigiert werden sollen;

    ein Referenzsystem (16); und

    einen Steuermechanismus (20) zum Ausführen eines Programms (12) auf dem Referenzsystem und dem Testsystem, wobei der Steuermechanismus Folgendes beinhaltet:

    ein Mittel zum Ausführen von Befehlsfolgen des Programms auf dem Referenzsystem und auf dem Testsystem;

    ein Mittel zum Erkennen und Aufzeichnen von Zuständen des Referenzsystems und des Testsystems an vergleichbaren Punkten bei der Ausführung des Programms; und

    ein Mittel zum Vergleichen des erkannten Zustands des Referenzsystems und des Testsystems an auswählbaren vergleichbaren Punkten in der Befehlsfolge, einschließlich des Endes der Befehlsfolge;

    wobei das System dadurch gekennzeichnet ist, dass es des Weiteren Folgendes umfasst:

    ein Mittel zum Wiedergeben der Ausführung von Abschnitten der Befehlsfolge zwischen auswählbaren vergleichbaren Punkten sowohl auf dem Referenzsystem als auch auf dem Testsystem, wenn ein Unterschied bei verglichenen Zuständen der Systeme erkannt wird, wobei das Wiedergabemittel auf das Erkennen eines Unterschieds bei verglichenen Zuständen in der Weise reagiert, dass es einen Abschnitt der Befehlsfolge, der wiedergegeben werden soll, zurücksetzt, und wobei das Wiedergabemittel eine Suche zwischen einem letzten vergleichbaren Punkt, an dem die Zustände zu einem korrekten Vergleich im Test- und im Referenzsystem führten, und dem vergleichbaren Punkt, an dem der Unterschied bei den verglichenen Zuständen entdeckt wurde, ausführt.
  2. System nach Anspruch 1, wobei es sich bei der ausgeführten Suche um eine binäre Suche handelt.
  3. System nach Anspruch 1 oder Anspruch 2, wobei der Steuermechanismus (20) des Weiteren ein Mittel zum Einspeisen von externen Ereignissen in das Referenzsystem (16) umfasst, das des Weiteren ein Mittel zum Aufzeichnen von externen Ereignissen, die durch das Mittel zum Einspeisen von externen Ereignissen in das Referenzsystem (16) eingespeist wurden, umfasst; und wobei der Steuermechanismus (20) ein Mittel zum Verwenden von aufgezeichneten externen Ereignissen des Referenzsystems (16) als externe Ereignisse für das Testsystem (15) bei der Ausführung von Befehlsfolgen umfasst.
  4. System nach Anspruch 3, wobei der Steuermechanismus (20) ein Mittel zum Abändern der externen Ereignisse und der vergleichbaren Punkte, an denen externe Ereignisse eingespeist werden, umfasst.
  5. System nach Anspruch 1, wobei der Steuermechanismus (20) des Weiteren ein Mittel zum Einspeisen von externen Ereignissen in das Referenzsystem (16) umfasst, das des Weiteren ein Mittel zum Aufzeichnen von externen Ereignissen, die durch das Mittel zum Einspeisen von externen Ereignissen in das Referenzsystem eingespeist wurden, umfasst; und wobei der Steuermechanismus (20) ein Mittel zum Verwenden von aufgezeichneten externen Ereignissen des Referenzsystems als externe Ereignisse für das Referenzsystem (16) und das Testsystem (15) bei der Wiedergabe der Ausführung von Befehlsfolgen umfasst.
  6. System nach einem der vorangehenden Ansprüche, wobei das Mittel zum Erkennen und Aufzeichnen von Zuständen des Referenzsystems (16) und des Testsystems (15) an vergleichbaren Punkten bei der Ausführung des Programms Surrogatwerte erkennt und aufzeichnet, die Zustände in dem Referenzsystem (16) und dem Testsystem (15) repräsentieren.
  7. System nach Anspruch 1, wobei der Steuermechanismus (20) ein Mittel zum Wiedergeben der Ausführung von Abschnitten zwischen auswählbaren vergleichbaren Punkten der Befehlsfolge sowohl auf dem Referenzsystem als auch auf dem Testsystem, während die Anwendung von externen Ereignissen verändert wird, umfasst.
  8. System nach einem der vorangehenden Ansprüche, wobei das Mittel zum Vergleichen des erkannten Zustands des Referenzsystems und des Testsystems an auswählbaren vergleichbaren Punkten in der Befehlsfolge, einschließlich des Endes der Befehlsfolge, in der Lage ist, einen anderen Zustand auszuwählen.
  9. Computergestütztes Verfahren zum Erkennen von Fehlern in Computersystemen, das folgende Schritte umfasst:

    – Ausführen von Befehlsfolgen eines Softwareprogramms sowohl auf einem Referenzsystem (16) als auch auf einem Testsystem (15);

    – Erkennen und Aufzeichnen von Zuständen des Referenzsystems (16) und des Testsystems (15) an vergleichbaren Punkten bei der Ausführung des Programms;

    – Vergleichen des erkannten Zustands des Referenzsystems (16) und des Testsystems (15) an auswählbaren vergleichbaren Punkten in der Befehlsfolge, einschließlich des Endes der Befehlsfolge,

    gekennzeichnet durch:

    – Wiedergeben der Ausführung von Abschnitten der Befehlsfolge zwischen auswählbaren vergleichbaren Punkten sowohl auf dem Referenzsystem (16) als auch auf dem Testsystem (15) in Reaktion auf das Erkennen eines Unterschieds bei verglichenen Zuständen der Systeme, und

    – Durchführen einer Suche zwischen einem letzten vergleichbaren Punkt, an dem die Zustände zu einem korrekten Vergleich im Testsystem (15) und im Referenzsystem (16) führten, und dem vergleichbaren Punkt, an dem der Unterschied bei den verglichenen Zuständen entdeckt wurde.
  10. Computergestütztes Verfahren nach Anspruch 9, wobei der Schritt des Wiedergebens der Ausführung von Abschnitten zwischen auswählbaren vergleichbaren Punkten der Befehlsfolge sowohl auf dem Referenzsystem (16) als auch auf dem Testsystem (15), wenn ein Unterschied bei einem verglichenen Zustand der Systeme erkannt wird, das Ausführen einer binären Suche zwischen einem letzten vergleichbaren Punkt, an dem ein Zustand in dem Testsystem (15) und in dem Referenzsystem (16) korrekt verglichen wurde, und dem vergleichbaren Punkt, an dem der Unterschied bei dem verglichenen Zustand entdeckt wurde, beinhaltet.
  11. Computergestütztes Verfahren nach Anspruch 9, wobei der Schritt des Wiedergebens der Ausführung von Abschnitten zwischen auswählbaren vergleichbaren Punkten der Befehlsfolge sowohl auf dem Referenzsystem (16) als auch auf dem Testsystem (15), wenn ein Unterschied bei einem verglichenen Zustand der Systeme erkannt wird, das Ausführen einer binären Suche zwischen einem letzten vergleichbaren Punkt, an dem ein Zustand in dem Test- und dem Referenzsystem korrekt verglichen wurde, und dem vergleichbaren Punkt, an dem der Unterschied bei dem verglichenen Zustand entdeckt wurde, beinhaltet, wobei die Suchtechnik so ausgewählt wird, dass die Suchgeschwindigkeit erhöht wird.
  12. Computergestütztes Verfahren nach einem der Ansprüche 9 bis 11, wobei der Schritt des Erkennens und Aufzeichnens eines Zustands des Referenzsystems (16) und des Testsystems (15) an vergleichbaren Punkten bei der Ausführung des Programms das Erkennen und Aufzeichnen von Surrogatwerten beinhaltet, die Zustände in dem Referenzsystem (16) und dem Testsystem (15) repräsentieren.
  13. Computergestütztes Verfahren nach einem der Ansprüche 9 bis 12, das des Weiteren folgende Schritte enthält:

    Einspeisen von externen Ereignissen in das Referenzsystem (16);

    Aufzeichnen von externen Ereignissen, die von dem Mittel zum Einspeisen von externen Ereignissen in das Referenzsystem (16) eingespeist wurden; und

    Verwenden von aufgezeichneten externen Ereignissen des Referenzsystems als externe Ereignisse für das Testsystem (15) bei der Ausführung von Befehlsfolgen.
  14. Computergestütztes Verfahren nach Anspruch 13, das des Weiteren den Schritt des Abänderns der externen Ereignisse und der vergleichbaren Punkte, an denen externe Ereignisse eingespeist werden, umfasst.
  15. Computergestütztes Verfahren nach einem der Ansprüche 9 bis 12, das des Weiteren folgende Schritte umfasst:

    Einspeisen von externen Ereignissen in das Referenzsystem (16);

    Aufzeichnen von externen Ereignissen, die in das Referenzsystem (16) eingespeist wurden; und

    Verwenden von aufgezeichneten externen Ereignissen des Referenzsystems (16) als externe Ereignisse für das Referenzsystem (16) und das Testsystem (15) beim Wiedergeben der Ausführung von Befehlsfolgen.
  16. Computergestütztes Verfahren nach Anspruch 9, wobei der Schritt des Wiedergebens der Ausführung der Folge von Abschnitten zwischen auswählbaren vergleichbaren Punkten der Befehlsfolge sowohl auf dem Referenzsystem (16) als auch auf dem Testsystem (15) das Verändern der Anwendung von externen Ereignissen beinhaltet.
  17. Computergestütztes Verfahren nach einem der Ansprüche 9 bis 16, wobei der Schritt des Vergleichens des erkannten Zustands des Referenzsystems und des Testsystems an auswählbaren vergleichbaren Punkten in der Befehlsfolge, einschließlich des Endes der Befehlsfolge, das Auswählen des zu vergleichenden Zustands beinhaltet.
Es folgen 3 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com