Emulator programmieren: Mit Software das Verhalten von Hardware nachbilden
Die Programmteile zur Emulation von Hardwarekomponenten sind mehr oder weniger schnell programmiert. Wie kommt dann aber alles zusammen? Gar nicht so leicht, denn in einem Chip arbeiten alle Komponenten parallel. Gelegentlich beeinflussen sie einander, die meiste Zeit arbeiten sie aber unabhängig voneinander. Während sie unabhängig arbeiten, erledigen sie eine gewisse Menge ihrer jeweiligen Aufgaben.
Ein Emulator muss die zeitlichen Abhängigkeiten zwischen den Komponenten nachbilden, um die Funktion des Originalsystems überzeugend zu imitieren. Ein weiteres Problem ist, dass das emulierende System meist wesentlich leistungsfähiger ist als das emulierte. Wir nehmen hier wieder den Gameboy als Beispiel, der führt maximal einen Befehl pro Prozessortakt aus. Superskalare Prozessoren(öffnet im neuen Fenster) , wie sie seit Jahrzehnten in Computern und seit Jahren auch Smartphones üblich sind, können mehrere Befehle pro Takt ausführen. Zudem takten sie um ein Mehrtausendfaches höher.
Ein Spiel, das mehrere hundert Mal schneller läuft, als es sollte, macht aber wenig Spaß. Wir benötigen eine Lösung für die beiden zuvor genannten Probleme - und werden uns damit andere, neue Probleme einhandeln. Aber auch die lassen sich lösen.
Parallelität der Hardware
Ein Emulator muss zuerst einmal dafür sorgen, dass die zeitlichen Zusammenhänge zwischen den einzelnen Komponenten erhalten bleiben. Am besten verstehen lässt sich das an einem konkreten Beispiel. Die Grafikeinheit erzeugt zeilenweise das dargestellte Bild. Während des Großteils dieser Zeit hat die CPU keinen Zugriff auf den Grafikspeicher und kann entsprechend auch keine Änderungen vornehmen. Das ist erst am Ende der Zeile während des horizontalen Strahlrücklaufs (horizontal blank) möglich.
Dann kann das ausgeführte Programm Änderungen vornehmen, die sich auf die Grafik auswirken. Viele Spiele nutzen das für Effekte. Der Emulator muss sicherstellen, dass in beiden Phasen der Zeilenausgabe - während der Pixelausgabe und des Strahlrücklaufs - die CPU genauso viele Befehle ausführen kann, wie sie es auf einem Gameboy könnte. Problematischer als zu viele ausgeführte Befehle ist es, wenn der emulierte Prozessor weniger Befehle ausführen kann als die echte Hardware. Denn dann können Berechnungen noch nicht abgeschlossen sein und sich anders auswirken als beim Original.
Genau dafür haben wir doch viele Prozessorkerne! Oder?
Es mag intuitiv erscheinen, die Parallelität der Hardware zu erreichen, indem jede Komponente mittels Thread(öffnet im neuen Fenster) auf einem eigenen Prozessorkern emuliert wird. Threads zerlegen ein Programm in mehrere, parallel abzuarbeitende Teile auf, die allerdings noch immer im selben Adressraum liegen und so mit wenig Aufwand kommunizieren und Daten austauschen können. Theoretisch wäre es also denkbar, einfach jede Hardwarekomponente durch einen Prozessorkern abarbeiten zu lassen. Der Ansatz hat allerdings ein Problem: Die einzelnen Threads müssen sehr oft aktiviert werden und führen teils nur wenige Befehle aus.
Das funktioniert zwar, ist aber ziemlich ineffizient. Denn die Prozessverwaltung (Scheduling) eines Betriebssystems verteilt die Prozessorzeit aus Effizienzgründen nicht in beliebig kleinen Teilen (Zeitscheiben). Hierfür gibt es eine Untergrenze, bei Linux ist sie variabel und liegt im Bereich einiger Millisekunden(öffnet im neuen Fenster) . Keiner der Abläufe in der Gameboy-Hardware dauert so lang. Da zudem die emulierende Hardware wesentlich leistungsfähiger ist als die originale, benötigen die entsprechenden Programmteile weniger Zeit, als sie es in der Hardware täten.
Die einzelnen Threads warten also viel, und wenn ein Thread für einen kürzeren Zeitraum warten muss, als das Betriebssystem ihn anbietet, geschieht das mit busy waiting(öffnet im neuen Fenster) . Dabei verbringt der Prozess die Zeit bis zur nächsten Aktivierung in einer Warteschleife und belegt weiterhin die von ihm genutzten Ressourcen. Schlimmer noch: Da ihm vom Betriebssystem irgendwann der Prozessor weggenommen wird, läuft er dann eine ganze Weile gar nicht.
Die Synchronisation eines solchen Systems wäre der reinste Horror. Abgesehen davon nutzt es mehr Rechenzeit als benötigt wird und verhindert, dass Prozessorkerne heruntertakten oder in einen Stromsparmodus versetzt werden. Die Lösung des Problems ist eine eigene Prozessverwaltung für die sehr kurzen Ausführungsintervalle von teils wenigen Dutzend Mikrosekunden.
Eigene Prozessverwaltung
Für die Ablaufplanung der Emulation der einzelnen Hardwarekomponenten auf das Betriebssystem zu setzen, funktioniert also nicht - dabei haben wir noch nicht einmal betrachtet, wie die einzelnen Threads synchronisiert werden könnten. Ein echtzeitfähiges Betriebssystem könnte theoretisch helfen, dann läuft der Emulator aber fast nirgendwo mehr.
Bei einem echtzeitfähigen Betriebssystem läuft die Prozessplanung etwas anders als bei einem normalen Linux oder Windows. Hier kann für Echtzeitprozesse angegeben werden, mit welcher Frequenz diese ausgeführt werden sollen. Das ist genau, was der Emulator braucht. Also habe ich einfach selbst eine Prozessverwaltung programmiert. Natürlich eine wesentlich einfachere als die eines Betriebssystems, sie umfasst nur eine einfache Komponente für die Prozessverwaltung und ein Interface für die Threads. Die Klasse, welche die Prozessverwaltung realisiert, wird Scheduler genannt, weil sie einen Zeitplan (Schedule) erstellt und umsetzt.
Die einzelnen Threads laufen innerhalb eines Betriebssystemprozesses. Damit entfällt die Synchronisation, weil innerhalb des Prozesses die Abarbeitung Befehl für Befehl erfolgt. Die Prozessverwaltung, die ich implementiert habe, aktiviert jeweils die passende Hardwarekomponente. Außerdem habe ich auf kooperatives Multitasking gesetzt.
Kooperation macht Prozessverwaltung einfach
Kooperatives Multitasking bedeutet, dass Threads nicht von der Prozessverwaltung der Prozessor weggenommen wird. Stattdessen prüfen sie selbst, ob sie weiter laufen dürfen. Das vereinfacht die Implementierung deutlich, da kein sogenannter Kontextwechsel stattfindet. Die Prozessverwaltung ruft lediglich eine Funktion des Thread-Interfaces auf und erlaubt dem Thread damit, für eine gewisse Zeit Befehle auszuführen.
Der aktive Thread prüft regelmäßig, ob er bereits länger aktiv war, als er durfte, und beendet in diesem Fall einfach die Funktion. Dadurch müssen keine Register gesichert werden, was im Fall von nicht-kooperativem Multitasking der Fall wäre. Betriebssysteme setzen das üblicherweise nicht um, denn es sorgt beim Programmieren für mehr Aufwand. Programmiererinnen und Programmierer sollen sich nicht mit den Details des Betriebssystems befassen müssen - das erledigt seinen Job leise im Hintergrund. Allerdings kann ein Programm dem Betriebssystem mitteilen, dass es aktuell nichts zu tun hat und seine Ausführung erst nach einer gewissen Zeit fortsetzen möchte.
Zwei Arten von Hardware
Bei genauer Betrachtung zeigt sich allerdings, dass es zwei verschiedene Arten von Hardwareprozessen gibt. Der Prozessor des Gameboy bildet nämlich eine Ausnahme, da er die anderen Komponenten - Grafik- und Soundhardware sowie den Timer - steuert. Sie geben dem Prozessor zwar über Programmunterbrechungen (Interrupts) Rückmeldungen, was sie gerade tun, das erfolgt aber nur zu vorhersehbaren Zeiten.
Daher habe ich zwei verschiedene Arten von Threads definiert. Die eine bezeichne ich als Echtzeit-Threads, die zu festen Zeiten aktiviert werden müssen. Darunter fällt alle Hardware bis auf den Prozessor. Für die anderen ist mir kein guter Name eingefallen, weshalb ich sie einfach als Threads bezeichnet habe. Die beiden Arten von Threads haben unterschiedliche Eigenschaften: Bei den normalen Threads vergeht für jede ausgeführte Operation Zeit, bei den Echtzeit-Threads nicht. Mit einer kleinen Ergänzung klingt das nicht mehr ganz so absurd: Es vergeht keine virtuelle Zeit - mehr dazu im nächsten Abschnitt.
Mit diesem Ansatz wird das Scheduling recht einfach. Es werden lediglich zwei Listen benötigt, eine für die Echtzeit-Threads, eine zweite für die normalen. Die Prozessverwaltung misst die virtuelle Zeit und prüft zuerst, ob ein Echtzeit-Thread abgearbeitet werden muss. Hat die virtuelle Uhr den Ausführungszeitpunkt eines Echtzeit-Threads erreicht, wird dieser aktiviert. Falls nicht, bestimmt sie die virtuelle Zeit bis zur Ausführung des nächsten Echtzeit-Threads, dann wird jeder normale Thread für diesen Zeitraum aktiviert.
Die Echtzeit-Threads teilen der Prozessverwaltung nach jeder Ausführung mit, zu welcher virtuellen Zeit sie das nächste Mal aktiviert werden sollen. Implementiert werden sie von den jeweiligen Funktionseinheiten - Grafik, Sound und Timer. Die Prozessverwaltung bleibt damit von den Details der Hardware unabhängig. Um die Liste mit den Echtzeit-Threads einfach prüfen zu können, ist sie nach den Ausführungszeiten sortiert - der nächste abzuarbeitende Echtzeit-Thread steht also immer an erster Stelle. Damit kommen wir zur Bedeutung der virtuellen Zeit.
Zeitsynchronisation
Nachdem die Synchronisation zwischen den einzelnen Hardwarekomponenten geklärt ist, kommen wir zum nächsten Problem: Das emulierende System ist viel zu schnell. Hier kommt die virtuelle Zeit ins Spiel. Der Emulator kann, selbst unoptimiert, auf einem halbwegs modernen Prozessor viel mehr Anweisungen pro Sekunde ausführen als der echte Gameboy. Er muss also regelmäßig angehalten werden.
Das funktioniert, indem der Emulator dem Betriebssystem mitteilt, dass er für einen gewissen Zeitraum nichts zu tun hat. Wer mit C/C++ programmiert, würde das mittels nanosleep()(öffnet im neuen Fenster) tun, Javas Thread.sleep()(öffnet im neuen Fenster) nutzt die Funktion der Beschreibung nach ebenfalls. Dabei müssen aber zwei Randbedingungen beachtet werden: Die erste ist, dass die Mindestschlafdauer ausreichend lang ist. Der Prozess schläft nämlich mindestens so lang wie angegeben, aber immer ein Vielfaches an Betriebssystem-Zeitscheiben. Ich habe als Mindestschlafdauer 10 ms gewählt und lege den Prozess auch nur für das Vielfache dieser Zeit schlafen - was gut funktioniert.
Die zweite Randbedingung hängt mit der virtuellen Zeit zusammen. Mit ihr bestimmt die Prozessverwaltung, wie lange ein echter Gameboy für die Abarbeitung einer Folge von Prozessorbefehlen gebraucht hätte. Daraus ermittelt er die Zeit, die hätte vergehen sollen und vergleicht sie mit der Zeit, die tatsächlich vergangen ist.
Virtuelle Zeit ist einfacher, als sie klingt
Die virtuelle Uhr des Emulators ist einfach eine 64-Bit-Ganzzahl (Integer). Jede emulierte Anweisung erhöht sie. Dafür enthält die entsprechende Klasse eine Konstante, die die Anzahl der für die Anweisung benötigten Takte des Gameboy-Prozessors enthält. Das ist so einfach, weil der Prozessor kein Pipelining unterstützt, die Dauer jeder Anweisung also von den vorherigen unabhängig ist.
Jetzt muss also nur noch regelmäßig geprüft werden, ob die virtuelle Zeit von der realen um mehr als 10 ms abweicht. Und hier kommen wir zum eigentlichen Problem: Wie oft sollte das geprüft werden? Um zu prüfen, muss nämlich jedes Mal die aktuelle (reale) Zeit angefordert werden. Das bedeutet den Aufruf einer Betriebssystemfunktion - unter Linux clock_gettime() - was ineffizient ist, wenn es zu oft geschieht.
Wird allerdings zu selten geprüft, führt das zu einer großen Differenz zwischen virtueller und realer Zeit. Das Ergebnis ist, dass der Emulator stockt und schlecht reagiert. Ich habe mich für 25 Prüfungen pro Sekunde entschieden, das liefert ganz gute Ergebnisse. Aber ich hatte noch eine bessere Idee - dachte ich.
Windows macht komische Sachen
Denn eigentlich wäre es doch cleverer, möglichst oft und kurz zu schlafen, um die Abweichung zwischen realer und virtueller Zeit klein zu halten. Dadurch würde das Stocken der Emulation weiter verringert, idealerweise würde auch der Prozessor weniger hoch- und runtertakten. Da unbekannt ist, wie viele Gameboy-Takte emuliert werden können, bis die Abweichung 10 ms übersteigt, muss das ausprobiert werden. Der Emulator versucht, die Anzahl emulierter Takte des Gameboy-Prozessors so anzupassen, dass danach die Zeitdifferenz etwa 10 ms beträgt.
Unter Linux hat das super funktioniert, aber als ich den Emulator unter Windows ausgeführt habe, wurde er immer langsamer. Der Grund dafür kann entweder mein zu simpler Algorithmus sein oder sich in den Implementierungsdetails des Windows-Schedulers finden. Da ich aber eine funktionierende Lösung hatte, habe ich das nicht weiter verfolgt. Und ich muss dazu sagen: Zuletzt habe ich das mit Windows 7 ausprobiert, möglicherweise wäre es bei neueren Versionen anders.
Bild und Ton müssen stimmen
Durch die Synchronisation von virtueller und realer Zeit führt der Emulator zwar genauso viele Anweisungen pro Sekunde aus wie ein echter Gameboy. Allerdings legt er dabei kurze Sprintsequenzen hin und macht dann Pause. Das führt dazu, dass Sound und Bilder früher fertig sind als auf der realen Hardware - und auch nicht in gleichmäßigen Abständen.
Um zu verstehen, warum das ein Problem ist, müssen wir uns zuerst ansehen, wie Sound- und Bilddaten ausgegeben werden. Der jeweiligen Hardware - Audio-Codec und Grafikkarte - ist jeweils ein Speicherbereich (Puffer genannt) zugeordnet, aus dem sie die auszugebenden Daten entnimmt. Der sorgt dafür, dass nicht jedes Sound-Sample und jedes Pixel zu einer exakten Zeit bereitgestellt werden muss. Die jeweiligen Anwendungen können so schon einmal vorarbeiten. Einen entscheidenden Unterschied gibt es: Bei der Grafik umfasst der Puffer nur ein Bild, da jedes Bild mehrere MByte benötigt, ein Sound-Sample hingegen nur vier Byte.
Beim Sound fängt der vorhandene Puffer die diskontinuierliche Ausführung des Emulators also bereits ab. Wird der Anzeigepuffer zwischen zwei Aktualisierungen des Bildschirms mehrmals geschrieben, wird nur das zuletzt geschriebene Bild dargestellt. Alle anderen gehen verloren - und das macht die Effekte einiger Spiele kaputt.
Für Spezialeffekte ist jedes Bild wichtig
Aufgefallen ist mir das bei Zelda - Link's Awakening(öffnet im neuen Fenster) . Läuft man hier mit den Pegasusstiefeln gegen ein Hindernis, wackelt das Bild. Beträgt die Bildrate nicht die auf dem Gameboy üblichen knapp 60 Bilder pro Sekunde, ist der Effekt total entstellt. Statt harmonisch zu vibrieren, bewegt sich das Bild ungelenk hin und her.
Das ist nur einer von vielen Effekten, die mit der Grafik-Hardware des Gameboy realisiert werden. Oft wird ein 3D-Effekt vorgegaukelt, indem parallaxe Ebenen verwendet oder eine perspektivische Verkürzung nachgebildet werden. Bei parallaxen Ebenen bewegen sich Teile des Bildes langsamer, wodurch sie weiter entfernt erscheinen. Die perspektivische Verkürzung erzeugt den Eindruck, auf eine zweidimensionale Ebene zu blicken. Am bekanntesten ist der Effekt von Mario Cart, auf dem Gameboy nutzt ihn beispielsweise F1 Race(öffnet im neuen Fenster) .
Mehr Threads helfen doch
Also habe ich Erzeugung und Darstellung der Bilder getrennt. Für die Darstellung ist ein eigener Thread zuständig - diesmal ein echter Betriebssystem-Thread. Er nutzt einen Timer, um zu festen Zeiten aktiviert zu werden - knapp 60 Mal pro Sekunde. So werden die Einzelbilder exakt mit der gleichen Rate angezeigt wie auf dem Gameboy. Die Bilder bekommt der Anzeige-Thread über eine FIFO (First-In-First-Out-Warteschlange), so dass sie in der korrekten Reihenfolge dargestellt werden und nicht verloren gehen.
Für den Sound habe ich das gleiche gemacht, wenn auch nicht aus einer konkreten Notwendigkeit heraus. Schließlich existiert hier bereits ein Puffer für die auszugebenden Samples. Allerdings kann das Schreiben in diesen Puffer blockieren, wenn er voll ist. Dadurch wird der Prozess automatisch schlafen gelegt, was die Zeitverwaltung durchkreuzen würde - also habe ich dem vorsorglich einen Riegel vorgeschoben. Ein paar Kleinigkeiten fehlen noch, dann ist der Emulator auch schon fertig.
Letzte Schritte und Fazit
Zum fertigen Emulator fehlen nur noch wenige Details. Einige davon sind eher kosmetischer Natur, beispielsweise, dass der Emulator pausiert wird, wenn sein Fenster nicht den Eingabefokus hat. Das ist einfach umzusetzen, da jede grafische Oberfläche Methoden anbietet, die einem Fenster Ereignisse zu seinem Zustand mitteilen. Verliert das Fenster den Fokus, wird die Emulation pausiert, bis es ihn zurückerhält.
Dann ist da noch die Auswahl der ROMs(öffnet im neuen Fenster) . Dafür hatte ich mal eine Datenbank geplant, das erscheint mir aber mittlerweile übertrieben. Stattdessen würde ich einfach ein festes Verzeichnis durchsuchen, da im ROM alle relevanten Informationen zu finden sind (mehr dazu im ersten Teil ). Ist der ROM ausgewählt, können alle zu ihm gehörenden Modul-RAM-Dateien gesucht und die gewünschte ausgewählt werden.
Etwas ganz Wichtiges fehlt allerdings noch: Bislang lässt sich das emulierte Spiel gar nicht steuern. Die Tasten des Gameboys werden mittels eines Registers als 2-x-4-Matrix abgefragt. Dafür wird eines von zwei Bits gesetzt, wodurch vier der acht Tasten gelesen werden. Hier ist mal wieder spezieller Code notwendig. Wird eines der Auslese-Bits gesetzt, setzt er die vier Ergebnis-Bits auf null oder eins - abhängig davon, ob entsprechende Tasten auf der Tastatur gedrückt sind.
Was hat es mir gebracht?
Als Informatiker hatte der Emulator für mich einen besonderen Reiz: Ich konnte hier einen großen Teil des Wissens aus dem Studium nutzen. Seien es Datenstrukturen - auch wenn eine sortierte Liste keine große Herausforderung ist - oder Betriebssysteme. Ich habe mich mit Dingen auseinandergesetzt, zu denen ich vorher keinen großen Bezug hatte, wie dem Linux-Scheduler.
Natürlich kommt auch eine große Portion Rechnerarchitektur ins Spiel. Auch hier konnte ich Dinge praktisch nutzen, die ich aus Vorlesungen und Praktika kannte. Einige unerwartete Dinge kamen hinzu, beispielsweise hatte ich erstmals Kontakt mit einem digitalen Filter - was mich motiviert hat, mich in das Thema einzuarbeiten. Auch zu Dingen, die man normalerweise ganz alltäglich nutzt und nie bemerkt, bekam ich einen praktischen Bezug, wie zur Abtastratenkonvertierung.
Nicht zuletzt hat mich das Projekt zum Staunen gebracht, wie viel mit wenig Silizium und Software entstehen kann. Aus den wirklich einfachen Möglichkeiten der Hardware entstehen mit einigen Tricks interessante Effekte. Zwar sind sie kein Vergleich zu aktueller Technik, beleben jedoch die Spiele ungemein. Und das Beste: Alles, was im Prozessor vorgeht, ist innerhalb kurzer Zeit verständlich.