Virtuelle Speicherverwaltung - Eine Fallstudie
Auch wenn der TT standardmäßig nur mit 4 MByte TT-RAM ausgeliefert wird, lassen sich Anwendungen realisieren, die mehr als 4 MByte Speicherplatz benötigen. Dies ist auch ohne Speichererweiterung denkbar, denn der TT erlaubt die sogenannte „virtuelle Speicherverwaltung“.
Die Tendenz ist eindeutig: Mit wachsender Größe des Hauptspeichers wächst auch der Speicherbedarf von Programmen. Galt es früher noch als utopisch, mehr als 640 kByte RAM zu benötigen, so stellt dieser Wert heute eher eine Untergrenze dar. Diejenigen, die bereits mit MS-DOS Bekanntschaft gemacht haben, können ein Lied davon singen.
Der Atari ST wird schon seit langem mit mindestens einem MByte Speicher ausgeliefert. Die neuen Rechnergenerationen von Atari, unter denen der MegaSTE und der TT zu verstehen sein sollen, bieten standardmäßig bereits zwei bzw. vier Megabyte Hauptspeicher. Dies sollte doch eigentlich für die meisten Anwendungen ausreichen, oder?
Speicherhunger
Nun, man sollte diese Frage nicht einfach bejahen. So spricht die Entwicklung auf dem ST-Sektor eine deutliche Sprache. Waren für den ST bis vor kurzem 4 MByte RAM das Maximum, so sind inzwischen Speichererweiterungen auf dem Markt, die eine Aufrüstung auf bis zu 12 MByte ermöglichen. Die Preise für solche Lösungen bewegen sich momentan jedoch noch jenseits von Gut und Böse. Der TT kann alles in allem auf bis zu 26 MByte aufgerüstet werden. Unter TOS ist dieser Speicherausbau sicherlich nicht notwendig, aber da ist ja auch noch UNIX ...
Apropos UNIX: Dieses Betriebssystem, das in Zukunft nicht mehr nur für Workstations und Großrechner von Bedeutung sein dürfte, erlaubt es, unabhängig von der Größe des Hauptspeichers nahezu beliebig große Anwendungen zu realisieren. Dies geschieht durch Ausnutzung einer speziellen Technik zur Speicherorganisation, nämlich der virtuellen Speicherverwaltung.
Aufklärung
Hinter diesem Schlagwort steckt ein von der Idee her recht einfaches Prinzip. Benötigt ein Programm ungewöhnlich viel Speicherplatz (z.B. zum Bearbeiten von gescannten Vorlagen), so kann es im Hauptspeicher auch bei Geräten mit mehr als 4 MByte RAM eng werden.
Ähnlich sieht es aus, wenn sich mehrere Programme gleichzeitig im Speicher befinden. Dabei muß es sich nicht,'wie vom ST her bekannt, ausschließlich um ein Hauptprogramm sowie einige residente Programme (z.B. Accessories) handeln, sondern es können durchaus mehrere Hauptprogramme gleichzeitig ablaufen. So erlaubt es das Programm MULTIGEM, verschiedene Programme auf ST oder TT quasi nebeneinander laufen zu lassen.
Wird nun mehr Speicherplatz benötigt, als das RAM hergibt, werden durch die virtuelle Verwaltung Speicherbereiche, die momentan nicht benötigt werden, auf die Festplatte ausgelagert. So wird Speicherplatz frei, der anschließend für neue Daten verwendet werden kann. Die Festplatte wird also als Speichererweiterung verwendet.
Leicht gesagt
Der eine oder andere Leser dürfte nun ins Grübeln geraten. Schließlich nützt es nichts, einen Datenbereich einfach auf die Platte zu schreiben, um diesen Speicherblock ohne Einschränkungen für neue Daten verwenden zu können. Bei näherer Überlegung stößt man auf einige Schwierigkeiten:
- Der neu benötigte Speicherbereich muß an einer ganz bestimmten Stelle im Hauptspeicher zur Verfügung gestellt werden, nämlich genau dort, wo das aktive Programm Speicher erwartet.
- Wer soll wie entscheiden, welcher Speicherbereich zur Zeit benötigt wird und welcher nicht?
- Das laufende Programm darf von allen Manipulationen nichts merken, denn nur so bleibt die Kompatibilität gewahrt.
Auf dem Atari ST wird man mit Sicherheit keine brauchbare Antwort auf diese Fragen finden. Beim TT sieht die Sache dagegen schon anders aus. Das kann dem TT-Besitzer natürlich nur recht sein, denn irgendwo muß sich die Preisdifferenz zwischen den beiden Rechnern ja auch in der Leistung niederschlagen.
Der 68030 macht’s möglich
In vorangegangenen Ausgaben der ST-Computer wurden Programme vorgestellt, die mit Hilfe der im 68030-Prozessor integrierten PMMU ungewöhnliche Speichermanipulationen vornehmen. Auch die virtuelle Speicherverwaltung gehört in diesen Rahmen. Der 68030 ist für solche Tricks aufgrund spezieller MMU-Befehle geradezu prädestiniert.
Daß es überhaupt möglich ist, Speicherbereiche bestimmter Größe (beim TT im Normalfall Pages von 32 kByte) unter Einsatz von Deskriptoren an einer beliebigen Stelle im Hauptspeicher einzublenden, wurde bereits in [1] und [2] demonstriert. Somit kann Speicherplatz an genau der Stelle zur Verfügung gestellt werden, an der neuer Speicher benötigt wird. Hierzu genügt eine Manipulation von Seitendeskriptoren. Wie erfährt man aber nun, wann an welcher Stelle im Adreßraum Speicherplatz zur Verfügung gestellt werden muß? Durch das Auftreten eines Busfehlers!
Busfehler erwünscht
Eigentlich mag es der Atari-An wender gar nicht, wenn sich während der Arbeit ein solcher Fehler in Form zweier Bomben Luft macht. Systemabstürze sind halt stets unangenehm. Aber gerade die Tatsache, daß auch der Zugriff auf nicht vorhandenes RAM odereinen ungültigen Deskriptor zu einer Exception in Form eines Busfehlers führt, ist für die virtuelle Speicherverwaltung von Bedeutung. Ein speicherresidentes Programm kann auf diesen Fehlerzustand reagieren und den Fehler möglicherweise beheben. Wird also ein Busfehler dadurch hervorgerufen, daß Software auf einen RAM Bereich zugreift, der momentan nicht im Speicher vorhanden ist, kann ein geeignetes Programm den Fehler analysieren und den benötigen Speicherblock zur Verfügung stellen. Dafür muß natürlich ein anderer Speicherbereich geopfert, also auf die Festplatte geschrieben werden. Wird nun im weiteren Programmverlauf auf eben diesen Bereich zugegriffen, wird nach dem gleichen Schema verfahren. Es wird also wieder ein Bereich des TT-RAMs auf die Platte geschrieben, und der ursprünglich ausgelagerte Block wird an alter Stelle wieder in den Speicher geholt.
Busfehler != Busfehler
Für die virtuelle Verwaltung des TT-RAMs kann ein Busfehler also ein Zeichen dafür sein, daß ein Speicherblock benötigt wird, der sich momentan nicht im Hauptspeicher befindet. Allerdings ist nicht auszuschließen, daß die Exception durch einen Fehlerzustand hervorgerufen wurde, der mit der für uns interessanten Speicherverwaltung überhaupt nichts zu tun hat.
Zunächst geht es also darum, die Ursache des Busfehlers näher zu analysieren. Dabei ist eine bestimmte Fehlerquelle von besonderer Bedeutung: ein ungültiger Seitendeskriptor.
Wie bereits in den vorausgegangenen Ausgaben der ST-Computer erläutert, ist ein Seitendeskriptor Bestandteil einer Tabelle, die definiert, wie der logische dem physikalischen Speicher zugeordnet werden soll. Da es verschiedene Arten von Deskriptoren gibt (Seiten- und Tabellendeskriptoren), werden diese anhand der niederwertigen beiden Bits des Deskriptors unterschieden. Sind beide Bits 0, kann die MMU keine Zuordnung vornehmen, es liegt ein ungültiger Deskriptor vor. Anders ausgedrückt: Es gibt keinen Hinweis darauf, wie der logische Speicher, der durch diesen Deskriptor beschrieben wird, auf den physikalischen Speicher abgebildet werden soll.
Das Vorliegen eines ungültigen Deskriptors kann nun unter Programmkontrolle von anderen Ursachen für einen Busfehler unterschieden werden. Es läßt sich nämlich feststellen, ob der Zugriff auf eine bestimmte Adresse zu einem gültigen oder ungültigen Deskriptor führt. Ist der Deskriptor gültig, handelt es sich in der Tat um einen echten Busfehler. Ein ungültiger Deskriptor dagegen kann dazu verwendet werden, eine virtuell verwaltete Speicherseite zu markieren, die sich momentan nicht im Hauptspeicher befindet.
Ein wichtiger Test
Um die Ursache eines Busfehlers zu ermitteln, muß die Gültigkeit der Adresse, die den Fehler hervorgerufen hat, überprüft werden. Diese Aufgabe erfüllen MMU-Befehle des Typs PTEST. PTESTR überprüft die Möglichkeit, einen Lesezugriff auf eine bestimmte Adresse durchzuführen, PTESTW kümmert sich um Schreibzugriffe. Die Syntax für diese Befehle ist recht ungewöhnlich, da bis zu vier Parameter möglich sind. Allgemein haben die PTEST-Befehle die folgende Form:
PTEST <fc>,<ea>,#level[,An]
fc stellt den Zustand der Function Code Bits FC0-FC3 dar, der für den Test zugrunde gelegt werden soll. Diese Bits erlauben nähere Aussagen über einen Buszugriff, so z.B., ob dieser aus dem Supervisor- oder User-Modus heraus erfolgte. Nähere Informationen finden sich in der Fachliteratur [3].
ea enthält die Adresse, deren Zulässigkeit überprüft werden soll. Nach einem Busfehler befindet sich diese Adresse mit dem Offset 16 auf dem Interrupt-Stack des 68030.
level gibt an, bis zu welcher Ebene die Deskriptortabellen durchsucht werden sollen, um die Gültigkeit der Adresse ea festzustellen. Eine 7 sorgt dafür, daß der zugehörige Seitendeskriptor bei Bedarf bis zur letzten Tabllenebene gesucht wird. Bei einer 0 werden nur diejenigen Deskriptoren berücksichtigt, die sich im Adress Translation Cache (ATC) der PMMU befinden. (Dies sind beim 68030 bis zu 22, bei der PMMU 68851 bis zu 64 Einträge.)
Die Angabe eines Adreßregisters An ist schließlich optional. Wird ein Register spezifiziert, wird die Adresse des Deskriptors, der für die getestete Adresse zuständig ist, in diesem Adreßregister abgelegt.
Per PTEST kann überprüft werden, ob ein Speicherzugriff auf eine gültige Adresse führt. Nach der Befehlsausführung werden zudem einige Bits im MMU-Statusregister gesetzt.
Das MMU-Statusregister
Neben dem Prozessor-Statusregister SR, das Bestandteil aller Prozessoren der 68000-Familie ist, findet sich das PSR (auch MMUSR genannt) nur bei Prozessoren mit eingebauter PMMU (also 68030 und 68040) sowie natürlich bei den externen MMUs. Der Befehl PTEST erlaubtes, diverse Bits in diesem Register gemäß der Gültigkeit einer Adresse zu setzen oder zurückzusetzen:
B (BUSERR): Dieses Bit zeigt an, daß die getestete Adresse einen Busfehler verursachte, als deren Deskriptor gesucht wurde.
L (Limit Violation): Liegt eine Limit-Überschreitung bei einen Deskriptor im Langformat vor, wird dieses Bit gesetzt.
S (Supervisor Only): Es ist möglich, Speicherseiten gegen einen Zugriff aus dem User-Modus zu schützen. Wird versucht, eine solche Seite dennoch im User Modus anzusprechen, wird das S-Bit aktiviert.
W (Write Protected): Das W-Bit besagt, daß auf eine Adresse, die nur zum Lesen freigegeben ist, ein Schreibzugriff erfolgen sollte.
I (Invalid): Dieses Bit ist für die virtuelle Verwaltung des Speichers von besonderer Bedeutung. Es zeigt an, daß die PMMU bei der Adreßberechnung auf einen ungültigen Deskriptor gestoßen ist.
M (Modified): Wurde die Speicherseite, in der sich die getestete Adresse befindet, verändert, so wird dies im M-Bit vermerkt.
T (Transparent Translation): Bit T zeigt an, daß sich die getestete Adresse in einem Speicherbereich befindet, der transparent (also gar nicht) übersetzt wird.
2-0 (Table Levels): In diesen Bits findet sich eine Information über die Ebene der Deskriptortabelle, in der sich der für die getestete Adresse zuständige Seitendeskriptor befindet.
Die restlichen Bits sind beim 68030 nicht belegt und lediglich für die PMMU 68851 von Bedeutung.
Da der 68030 im Vergleich zur PMMU 68851 nur über einen eingeschränkten MMU-Befehlssatz verfügt, lassen sich die einzelnen Flags des Statusregisters dummerweise nicht direkt testen. Zunächst muß das PSR in den Speicher übertragen werden. Anschließend kann der gewünschte Test auf den im Speicher abgelegten Wert des Statusregisters angewendet werden. Dabei geht es für uns nur um das Invalid-Bit, das anzeigt, ob der Deskriptor, dessen Adresse sich in A0 befindet, gültig ist. Sollte dies der Fall sein, muß die normale Busfehler-Routine aufgerufen werden. Andernfalls muß die virtuelle Speicherverwaltung in Aktion treten.
tst.b ttflg
beq nott ;bei ST unsinnig-
ptestr #7,[16(sp)],#7 ;Deskriptor prüfen
pmove psr,Status
btst #2,Status
beq nott ;gültiger Deskriptor-
jmp ([oldvec]) ;alten Vektor anspringen
nott:
hier kann die eigene Busfehler-
Behandlung erfolgen
Neue Busfehler-Behandlung
Seitenwechsel
Wie kann eine solche Aktion aussehen? Der PTEST-Befehl hat bereits die Adresse des ungültigen Deskriptors geliefert, der für den Busfehler verantwortlich ist. Somit ist bekannt, welche Speicherseite vom zur Zeit laufenden Programm benötigt wird. Nun stellt sich die Frage, welche Seite aus dem Speicher ausgelagert werden soll. Eine eindeutige Antwort gibt es hier nicht, nur einige Theorien, die sich jedoch nicht alle in die Praxis umsetzen lassen [4].
Man kann zeigen, daß die optimalste Lösung genau die Speicherseite verwirft, auf die am längsten nicht mehr zugegriffen werden wird. Aber wie so oft läßt sich das theoretisch beste Verfahren praktisch nicht realisieren. Wer kann schon in die Zukunft schauen? Ähnlich günstig wäre es, genau die Speicherseite zu verwerfen, auf die am längsten nicht mehr zugegriffen wurde. Die Sache hat jedoch ebenfalls einen Haken: Es läßt sich programmtechnisch kaum feststellen, um welche Seite es sich handelt.
Realisierbar ist es jedoch, die Seite zu bestimmen, die sich bereits am längsten im Speicher befindet und diese dann auf der Festplatte unterzubringen. Zu welcher Zeit eine Page in den Speicher transferiert wurde, kann in Form einer Tabelle vermerkt werden. Ein Nachteil dieser FIFO-Methode (First In, First Out) liegt aber auf der Hand: Bei der am längsten im Speicher verweilenden Seite kann es sich durchaus um eine Seite handeln, die sehr häufig angesprochen wird. Die Wahrscheinlichkeit, daß diese Seite gleich nach dem Auslagern wieder benötigt wird, kann somit recht hoch sein.
Eine Chance für die Seite
Einen Mechanismus zur Seitenverwaltung, der programmtechnisch realisierbar ist und zusätzlich in einem gewissen Rahmen berücksichtigt, daß häufig benutzte Seiten möglichst nicht ausgelagert werden sollten, stellt das „Second-Chance“-Verfahren dar.
Die grundlegende Idee ist uns anhand der bereits angestellten Überlegungen nicht mehr neu: Seiten, die bereits lange im Speicher verweilen, werden bevorzugt auf die Platte verbannt. Hierzu wird eine Liste geführt, in der alle Seiten in der Reihenfolge ihrer Verweilzeit aufgeführt sind. Wurde die erste Speicherseite in dieser Liste jedoch, seitdem sie das letzte Mal überprüft wurde, wieder referenziert, wird sie zunächst am Ende der Liste eingeordnet. Dabei wird das Used-Bit dieser Seite zurückgesetzt. Nun wird überprüft, ob die nächste Seite der Liste inzwischen wieder benutzt wurde usw. Irgendwann kommt eine Speicherseite an die Reihe, bei der das U-Bit nicht gesetzt ist. Dies kann durchaus diejenige Seite sein, die zunächst am Ende der Liste eingeordnet wurde, meist wird es sich jedoch um eine wenig benutzte andere Seite handeln.
Wer schreibt, der bleibt
Wird eine Speicherseite verworfen, darf diese natürlich nicht gleich mit neuen Daten überschrieben werden. Zunächst einmal muß überprüft werden, ob auf diese Page zwischenzeitlich ein Schreibzugriff durchgeführt wurde, der die Seite verändert haben könnte. In diesem Fall ist das Modified-Bit im Seitendeskriptor gesetzt. Daraus folgt, daß diese Speicherseite vor weiteren Aktionen auf die Festplatte geschrieben werden muß.
Speicher-Pfuscherei
Nachdem die zu verwerfende Seite (falls notwendig) auf der Platte gesichert wurde, kann deren Seitendeskriptor durch das Löschen der beiden niederwertigen Deskriptor-Bits für ungültig erklärt werden. Ein Zugriff auf diese Speicherseite zu einem späteren Zeitpunkt wird nun in einem Busfehler enden, der dann natürlich wieder per Software abgefangen werden kann.
Nun sind zunächst 32 kByte RAM frei geworden, die an anderer Stelle im Hauptspeicher eingesetzt werden können. Keine Frage, wo sich diese Stelle befindet: natürlich dort, wo der Busfehler hervorgerufen wurde. Hierzu wird der Deskriptor der Speicherseite, bei deren Zugriff der Fehler verursacht wurde, mit der physikalischen Adresse des frei gewordenen Speicherblocks versehen. Durch dieses Vorgehen lassen sich also ganze Speicherseiten im Hauptspeicher hin- und herschieben. Dabei können im Adreßraum des TT-RAMs durchaus Lücken entstehen, an denen sich kein RAM befindet. Eine ungewöhnliche Situation, aber die PMMU macht's möglich.
Neue Daten braucht die Page
Alle Operationen, die das Manipulieren des logischen Adreßraums betreffen, sind nun abgeschlossen. Nun muß noch der ursprüngliche Inhalt der neuen Speicher Seite restauriert werden. Diese Daten befinden sich auf der Festplatte, falls diese Seite vorher schon einmal benötigt wurde. Erfolgte nach der Initialisierung der virtuellen Verwaltung noch kein Zugriff auf diese Page, braucht sie auch nicht nachgeladen zu werden.
Wurde die neue Seite bereits angesprochen, wird diese von der Platte geladen. Nun sollte die Ursache für den Busfehler beseitigt sein. Schließlich befindet sich an der Zugriffsadresse ein RAM-Bereich, der genau die Daten enthält, die vom laufenden Programm an dieser Stelle erwartet werden. Somit kann die Busfehler-Exception beendet werden. Hierzu dient der RTE-Befehl, der den 68030 dazu veranlaßt, den fehlerhaften Buszyklus zu wiederholen. Diese Möglichkeit sieht der 68000 des Atari ST übrigens nicht vor. Zwar existiert auch bei diesem Prozessor das RTE-Kommando, eine erneute Ausführung von Befehlen ist jedoch nicht vorgesehen.
Hinweise für Programmierer
Virtuelle Speicherverwaltung sollte auf dem TT ohne größere Kompatibilitätsprobleme möglich sein. Fehler entstehen lediglich dann, wenn ein Programm Interrupt-Vektoren, die periodisch aufgerufen werden, ins TT-RAM legt. Wird eine Speicherseite, auf die ein solcher Vektor zeigt, ausgelagert, so führt dies beim nächsten Interrupt zu Problemen. Häufig ist es dann nicht schnell genug möglich, die benötigten Daten nachzuladen. Dies wird mit einem Absturz quittiert. Ein Programm, das virtuelle Speicherverwaltung ermöglicht, sollte es deshalb erlauben, einzelne Speicherseiten gegen das Auslagern auf Platte zu schützen. In diesen Speicherseiten können dann Interrupt-Routinen oder resetfeste Programme installiert werden. Um keine Inkompatibilitäten zu provozieren, sollten Programme, die eine eigene Busfehler-Behandlung besitzen, auf eine virtuelle Verwaltung des TT-RAMs vorbereitet sein. Tritt ein Busfehler auf, muß geprüft werden, ob der Fehler tatsächlich durch nicht vorhandenes RAM oder nur durch einen ungültigen Deskriptor entstanden ist. Im letzten Fall darf der Programmablauf nämlich auf keinen Fall abgebrochen werden. Stattdessen muß der alte Busfehler-Vektor angesprungen werden. Falls die Exception nicht durch einen ungültigen Deskriptor hervorgerufen wurde, liegt ein Fehler vor, der nicht von einer virtuellen Speicherverwaltung aufgefangen werden kann. Nur in diesem Fall sind eigene Routinen zur Fehleranalyse erlaubt.
Also, Programmierer aufgepaßt! Um solchen Schwierigkeiten, die eine virtuelle Verwaltung des TT-RAM erschweren, aus dem Weg zu gehen, schlage ich eine Routine gemäß dem abgedrucken Assembler-Listing vor. Anhand des MMU-Statusregisters wird hier zunächst die Ursache der Busfehler-Exception überprüft. Handelt es sich um einen für die virtuelle Speicherverwaltung angelegten ungültigen Deskriptor, so muß die ursprüngliche Busfehler-Routine angesprungen werden. Nur wenn der Fehler anderweitig verursacht wurde, dürfen eigene Routinen in Aktion treten.
Auch dann, wenn Sie mit einem ST arbeiten, sollten Sie die obigen Hinweise beherzigen, die TT-Anwender werden es Ihnen danken.
Man beachte
Abschließend noch ein Nachtrag zu dem in Heft 4 vorgestellten Patch für den TEMPUS-Editor [5]. Herrn G. Bruhn verdanke ich den Hinweis, daß der Absturz auf dem TT beim Verlassen von TEMPUS möglicherweise gar keiner ist. Beim TT ist die externe Synchronisation (in der Vergangenheit des öfteren als Bildschirmschoner mißbraucht) dann eingeschaltet, wenn Bit 0 des Video-Registers $FF820A gelöscht ist. Beim ST besagt dieser Zustand genau das Gegenteil. Atari hat also die Bedeutung dieses Bits geändert. Dieser Umstand dürfte ein mehr als ausreichendes Argument dafür sein, zu anderen Methoden beim Dunkelschalten des Bildschirms zu greifen. Empfehlenswert ist das Invertieren des Bildes bei Monochrommonitoren oder das Ändern der Farbpalette bei Farbmonitoren.
Literatur
[1] „TT-Tuning - Speed Without The Price" ST-Computer 3!91
[2] „Speichermanipulationen" ST-Computer 5/91
[3] Steve Wilhams, „68030 Assemblv Language Reference“, Addison-Wesley Publishing Company Inc.
[4] Script zur Vorlesung „Betriebssysteme“, Uni Kaiserslautern
[5] „TT-Manipulation auf 24 Bit", ST-Computer 4/91
Uwe Seimet