- Um die internen Abläufe eines Computers und die Ausführung von Programmiersprachen zu verstehen, wird auf der pädagogischen LC-3-Architektur ein Assemblerprogramm ausgeführt, indem man selbst eine C-basierte VM mit etwa 250 Zeilen implementiert
- Das Ziel der Implementierung ist ein kleines Computermodell mit 65.536 16-Bit-Speicherstellen, 10 Registern, 16 Opcodes, Condition Flags, Trap-Routinen und speicherabgebildeten Registern
- Die Ausführungsschleife arbeitet als Fetch-Decode-Execute-Struktur: Sie liest die Anweisung, auf die
PCzeigt, erhöht ihn, dekodiert dann den Opcode und führt Anweisungen wieADD,LDI,BR,JMPundTRAPaus - Das Laden des Programms liest den ersten 16-Bit-Origin-Wert der Objektdatei, legt ihn im Speicher ab und führt Byte-Swapping durch, um das Big-Endian-Format von LC-3 an das auf den meisten modernen Computern verwendete Little-Endian-Format anzupassen
- Tastatureingaben und Konsolenausgaben werden über Trap-Routinen und die speicherabgebildeten Register
KBSR/KBDRverarbeitet; dafür ist unter Unix/macOS und Windows jeweils unterschiedlicher Code für die Eingabepufferung des Terminals nötig
Ziel und Voraussetzungen des Tutorials
- Es wird gezeigt, wie man eine LC-3-VM selbst implementiert und damit Assemblerprogramme ausführt
- Der endgültige Code umfasst in C rund 250 Zeilen; bereitgestellt werden
lc3.cfür Unix undlc3-win.cfür Windows - Vorausgesetzt werden grundlegende Kenntnisse zum Lesen von C oder C++ sowie binäre Arithmetik
- Der vollständige Code liegt im GitHub-Repo; das Tutorial selbst ist als Literate Program aufgebaut und verwebt Codeblöcke zur endgültigen Quelldatei
Was eine virtuelle Maschine tut
- Eine VM ist ein Programm, das sich wie eine CPU und einige Hardware-Komponenten verhält
- Führt arithmetische Operationen aus
- Liest und schreibt Speicher
- Interagiert mit I/O-Geräten
- Versteht ihre eigene Maschinensprache und führt Programme aus
- Je nach Zweck kann eine VM reale Hardware möglichst genau nachbilden oder eine neue virtuelle Architektur zur bequemeren Softwareentwicklung bereitstellen
- Die JVM ist ein typisches Beispiel für eine VM, die eine standardisierte Laufzeitplattform bietet; auf Geräten mit JVM können Java-, Kotlin- und Clojure-Programme ohne Änderungen ausgeführt werden
- Auch isolierte Ausführung ist ein wichtiger Einsatzzweck von VMs
- Bei der Garbage Collection kann die VM Stack- und Speicherreferenzen außerhalb des laufenden Programms beobachten
- Ethereum-Smart-Contracts laufen in einer VM ohne Zugriff auf Dateisystem, Netzwerk, Datenträger usw.
Aufbau der LC-3-Architektur
- Implementiert wird LC-3, das in Hochschulen zur Lehre von Rechnerarchitektur und Assemblersprache verwendet wird
- Der LC-3-Speicher hat 65.536 Adressen, an denen jeweils ein 16-Bit-Wert gespeichert wird
- Die Gesamtkapazität beträgt 128 KB
- In C wird dies als Array
uint16_t memory[MEMORY_MAX]dargestellt
- Insgesamt gibt es 10 Register
R0~R7: 8 allgemeine RegisterPC: Speicheradresse der als Nächstes auszuführenden AnweisungCOND: Condition Flag des zuletzt berechneten Ergebnisses
- Alle LC-3-Instruktionen sind 16 Bit lang; die linken 4 Bit bilden den Opcode
- Es sind 16 Opcodes definiert
- Dazu gehören
OP_BR,OP_ADD,OP_LD,OP_ST,OP_JSR,OP_AND,OP_LDR,OP_STR,OP_RTI,OP_NOT,OP_LDI,OP_STI,OP_JMP,OP_RES,OP_LEA,OP_TRAP
- Die Condition Flags geben das Vorzeichen des zuletzt berechneten Ergebnisses an
FL_POS: positivFL_ZRO: nullFL_NEG: negativ
Assembler und Maschinensprache
- Was die LC-3-VM tatsächlich ausführt, ist kein für Menschen lesbarer Assembler, sondern ein Array aus 16-Bit-Maschinenbefehlen
- Ein Assembler wandelt in Text geschriebenen LC-3-Assembler in 16-Bit-Binärbefehle um
- Das Beispiel
Hello Worldfolgt diesem Ablauf.ORIG x3000: Gibt die Speicheradresse an, an der das Programm geladen wirdLEA R0, HELLO_STR: Lädt die String-Adresse inR0PUTS: Gibt den String aus, auf denR0zeigtHALT: Stoppt das Programm.STRINGZ "Hello World!": Speichert die String-Daten im Programm selbst
.ORIGund.STRINGZsind keine CPU-Befehle, sondern Assembler-Direktiven- Bedingungen und Schleifen werden mit Sprungbefehlen umgesetzt, die eher
gotoähneln, etwaBRn LOOP
Kernablauf der Ausführungsschleife
- Die VM wiederholt immer denselben Ablauf
- Liest die Anweisung an der Adresse im
PC-Register - Erhöht
PC - Ermittelt den Opcode aus den oberen 4 Bit der Anweisung
- Führt den zum Opcode gehörenden Implementierungscode aus
- Liest anschließend die nächste Anweisung
- Liest die Anweisung an der Adresse im
- Die Standard-Startadresse ist
0x3000 - Manche Befehle verändern
PCdirekt und springen damit an eine andere Stelle im Kontrollfluss- Dank Sprung- und Verzweigungsbefehlen sind trotz des einfachen Inkrementierens von
PCSchleifen und bedingte Ausführung möglich
- Dank Sprung- und Verzweigungsbefehlen sind trotz des einfachen Inkrementierens von
- Die
main-Schleife ruft mitswitch (op)den Code für jeden Opcode auf- Behandelt werden
OP_ADD,OP_AND,OP_NOT,OP_BR,OP_JMP,OP_JSR,OP_LD,OP_LDI,OP_LDR,OP_LEA,OP_ST,OP_STI,OP_STR,OP_TRAP OP_RESundOP_RTIsind ungenutzte Opcodes und können mitabort()behandelt werden
- Behandelt werden
Wie Instruktionen implementiert werden
ADDaddiert zwei Werte, speichert das Ergebnis im Zielregister und aktualisiert die Condition FlagsADDhat zwei Modi- Registermodus: Der zweite Operand wird aus einem anderen Register gelesen
- Immediate-Modus: Der zweite Operand wird aus den unteren 5 Bit
imm5der Anweisung gelesen
- Werte, die wie
imm5kürzer als 16 Bit sind, müssen per Sign Extension auf 16 Bit erweitert werden- Positive Werte werden mit 0 aufgefüllt
- Negative Werte werden mit 1 aufgefüllt, damit der ursprüngliche Wert erhalten bleibt
- Befehle, die in Register schreiben, aktualisieren
R_CONDüberupdate_flags- Wenn der Wert 0 ist:
FL_ZRO - Wenn das höchstwertige Bit 1 ist:
FL_NEG - Sonst:
FL_POS
- Wenn der Wert 0 ist:
LDIist eine „Load Indirect“-InstruktionPCoffset9der Anweisung wird per Sign Extension erweitert- Zusammen mit dem aktuellen
PCergibt sich eine Speicheradresse - Der dort gespeicherte Wert wird erneut als Adresse verwendet, um die endgültigen Daten zu lesen
- Der gelesene Wert wird im Zielregister gespeichert und die Condition Flags werden aktualisiert
Wichtige Befehlssätze
- Arithmetik und Bitoperationen
ADD: AdditionAND: bitweises ANDNOT: bitweises NOT
- Kontrollfluss
BR: Vergleicht die Condition Flags mit den Condition-Bits der Anweisung und setzt entsprechendPCJMP: SetztPCauf den Wert des angegebenen RegistersRET: Laut Spezifikation ein eigenes Schlüsselwort, praktisch aber ein Spezialfall vonJMPJSR,JSRR: Speichern den aktuellenPCinR7und springen zur Position der Unterroutine
- Speicher lesen
LD: Liest von einer perPC-relativem Offset bestimmten AdresseLDI: Folgt zusätzlich einer indirekten Adresse und liest dannLDR: Liest von einer aus Basisregister und Offset berechneten AdresseLEA: Speichert die effektive Adresse selbst im Register
- Speicher schreiben
ST: Schreibt an eine perPC-relativem Offset bestimmte AdresseSTI: Schreibt über eine indirekte AdresseSTR: Schreibt an eine aus Basisregister und Offset berechnete Adresse
Trap-Routinen und I/O
- LC-3 stellt Trap-Routinen für gemeinsame Aufgaben und den Zugriff auf I/O-Geräte bereit
- Trap-Routinen lassen sich als Betriebssystem oder API von LC-3 betrachten
- Die Trap-Codes sind wie folgt definiert
TRAP_GETC = 0x20: Liest ein Zeichen von der Tastatur, ohne Echo im TerminalTRAP_OUT = 0x21: Gibt ein Zeichen ausTRAP_PUTS = 0x22: Gibt einen Word-String ausTRAP_IN = 0x23: Liest ein Zeichen und gibt es im Terminal mit Echo ausTRAP_PUTSP = 0x24: Gibt einen Byte-String ausTRAP_HALT = 0x25: Stoppt das Programm
- Im offiziellen LC-3-Simulator sind Trap-Routinen in Assembler geschrieben; in dieser VM werden sie als C-Funktionen implementiert
PUTSgibt Zeichen ab der inR0gespeicherten Adresse aus, bisx0000erreicht wird- LC-3-Strings speichern nicht wie C-Strings je 1 Byte pro Zeichen, sondern ein Zeichen pro Speicherstelle
- Da jede Speicherstelle 16 Bit hat, wird für die Ausgabe in C in
charkonvertiert
- Die Trap-Routine
HALTgibt"HALT"aus und setzt das Lauf-Flag auf 0, sodass die VM-Schleife endet
Laden von Programm-Images
- Wird ein LC-3-Assemblerprogramm in Maschinencode umgewandelt, entsteht eine Datei mit einem Array aus Befehlen und Daten
- Die ersten 16 Bit der Objektdatei sind der Origin und geben an, wo das Programm im Speicher platziert werden soll
- Der Loader liest zuerst den Origin und kopiert dann die restlichen Daten ab dieser Adresse in den Speicher
- LC-3-Programme liegen im Big-Endian-Format vor
- Da die meisten modernen Computer Little Endian verwenden, wird auf jedes geladene
uint16_tswap16angewendet - Auf Big-Endian-Computern wie älteren PPC-Macs darf nicht geswappt werden
- Da die meisten modernen Computer Little Endian verwenden, wird auf jedes geladene
read_imageöffnet die Datei im Binärmodus, ruftread_image_fileauf und schließt die Datei anschließend
Speicherabgebildete Register
- Spezielle Register, die nicht über die normale Registertabelle angesprochen werden, sind auf bestimmte Speicheradressen abgebildet
- In LC-3 müssen zwei speicherabgebildete Register implementiert werden
MR_KBSR = 0xFE00: Keyboard-Status-RegisterMR_KBDR = 0xFE02: Keyboard-Datenregister
KBSRzeigt an, ob eine Taste gedrückt wurde, undKBDRspeichert, welche Taste gedrückt wurdeGETCblockiert die Ausführung bis zur Eingabe;KBSRundKBDRerlauben dagegen Polling des Gerätezustands, damit Programme auch während des Wartens auf Eingaben reaktionsfähig bleiben- Speicher wird nicht direkt aus dem Array gelesen, sondern über
mem_read- Wenn die Adresse
MR_KBSRist, prüftcheck_key()den Tastaturstatus - Wenn eine Taste vorhanden ist, wird das höchstwertige Bit von
KBSRgesetzt und der Wert vongetchar()inKBDRgespeichert - Wenn keine Taste vorhanden ist, wird
KBSRauf 0 gesetzt
- Wenn die Adresse
Terminalbehandlung je nach Plattform
- Damit Tastatureingaben und Terminalverhalten korrekt funktionieren, sind plattformspezifische Einstellungen für die Eingabepufferung nötig
- Die Linux/macOS/UNIX-Implementierung verwendet
termios,selectusw.- Der Canonical Mode und Echo werden deaktiviert
- Mit
selectwird geprüft, ob Eingaben verfügbar sind
- Die Windows-Implementierung verwendet
GetStdHandle,GetConsoleMode,SetConsoleMode,_kbhitusw.- Echo und Zeileneingabe werden angepasst
- Mit
WaitForSingleObjectund_kbhitwird geprüft, ob eine Taste gedrückt wurde
- Beim Start des Programms wird
disable_input_buffering()aufgerufen, beim Beendenrestore_input_buffering() - Bei
SIGINTwerden die Terminaleinstellungen wiederhergestellt, ein Zeilenumbruch ausgegeben und das Programm beendet
Ausführung und Debugging der VM
- Ein Beispiel zum Bauen der VM:
gcc lc3.c -o lc3-vm
- Zum Ausführen wird eine assemblierte LC-3-Objektdatei als Argument übergeben
lc3-vm path/to/2048.obj
- Als Beispiele werden die Objektdateien
2048.objundrogue.objmitgeliefert - Das Beispiel 2048 wird mit den Tasten WASD gesteuert
- Wenn das Programm nicht korrekt funktioniert, liegt die Ursache wahrscheinlich in einer fehlerhaften Befehlsimplementierung
- Empfohlen wird, die LC-3-Assemblerquelle parallel zu lesen und mit einem Debugger die VM-Instruktionen Schritt für Schritt auszuführen
- Wenn an einer Stelle nicht zur erwarteten Anweisung gesprungen wird, sollten Spezifikation und Implementierung dieser Instruktion erneut geprüft werden
Optional: generische Implementierung auf Basis von C++
- Optional wird auch eine kürzere Implementierungstechnik in C++ behandelt
- Da mehrere Befehle wiederkehrende Arbeitsschritte wie Sign Extension,
PC-relative Offsets oder indirekte Adressberechnung teilen, kann man die Ausführung einer Instruktion als Pipeline kleiner Verarbeitungsschritte sehen - Mit C++-Templates und Bit-Flags lassen sich pro Opcode nur die tatsächlich benötigten Verarbeitungsschritte zur Compile-Zeit einbinden
- Dieser Ansatz reduziert Code-Duplizierung und ähnelt stärker der Verdrahtung echter Hardware, bei der jeder Verarbeitungsschritt physischen Platz auf dem Chip einnimmt
- Als Inspirationsquelle wird Bisqwits NES-Emulator genannt
Materialien und Beiträge
- atul-g hat eine Reference Card beigetragen, die das Verhalten des Gesamtsystems zusammenfasst
- Implementierungen in verschiedenen Sprachen sind über das GitHub-Topic
lc3gesammelt- Dazu gehören C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript und Zig
- Wer seine eigene Implementierung in der Liste sichtbar machen möchte, kann ihr einfach das GitHub-Topic
lc3zuweisen - Die Unterstützung für die Windows-Plattform wurde von inkydragon beigesteuert
- Im Projekt gibt es ein „good first issue“ zu Integrationstests
1 Kommentare
Meinungen auf Hacker News
Als Teenager habe ich in einem Einführungskurs in Informatik am Community College einen einfachen CPU-Befehlssatz entworfen, selbst eine virtuelle Maschine und einen Assembler gebaut und damit Assembly-Programme geschrieben und ausgeführt.
Es war überraschend einfach, und Computer wirkten danach deutlich weniger mysteriös.
Ich glaube, man könnte auf diese Weise alle Schichten des Computing lernen – vom Entwurf einer echten CPU für FPGAs bis hin zu einem einfachen Betriebssystem und Programmen, die darauf laufen.
Wenn man die von moderner IT geforderte Performance und Sicherheit ausklammert und nur das Ziel hat: „Es muss funktionieren“, ist dieses Gebiet erstaunlich simpel.
Wenn ich mich richtig erinnere, kommen mindestens Speichersegmentierung, Protected Mode und eine MMU dazu.
Es war ein einfacher Computer/Assembler, auf einem PDP in BASIC geschrieben, und eine der Aufgaben bestand darin, einfache Multiplikation zu implementieren, indem man in einer Schleife Additionen ausführt.
Ein Freund änderte stattdessen das Programm und baute einen neuen MUL-Befehl ein; der Lehrer fand das überhaupt nicht gut.
Wer neugierig ist und lernen will, kann sich solche Grundlagenschichten leicht aneignen; für Leute, die „schnell Geld verdienen und möglichst schnell jobfähig werden“ wollen, gilt das eher nicht.
Empfohlene Bücher:
Wenn jemand diese Bücher gelesen hat und etwas dazu sagen kann, wäre das für alle hilfreich.
Nintendo-Emulatoren, Hypervisoren mit VT-x, traditionelle Multitasking-Betriebssysteme, Interpreter für neue Skriptsprachen, SQL-Query-Optimierer, Regex-Matcher, Sicherheitswächter, die nicht vertrauenswürdigen Player-Code auf Gameservern ausführen – all das scheint kaum gemeinsame Anforderungen zu haben, und doch sind es alles virtuelle Maschinen.
Selbst im terminfo-Format, das Escape-Sequenzen für Zeichen-Zell-Terminals beschreibt, steckt eine stackbasierte virtuelle Maschine.
Wenn man tiefer blickt, sind virtuelle Maschinen das, was Computer im heutigen Sinn überhaupt zu Computern macht; auch Turings Entscheidungsproblem-Aufsatz von 1936 drehte sich darum, dass virtuelle Maschinen einander nachahmen können.
Nachdem ich Ben Eaters Breadboard-CPU-Serie gesehen habe, will ich eigentlich nur noch selbst eine CPU entwerfen und emulieren.
Ich wünschte, ich fände die Zeit, mich hinzusetzen und das zu entwerfen.
Bildungsarchitekturen wie die Brookshear Machine oder Little Computer ähneln realen Architekturen überhaupt nicht; ich halte sie nicht nur für nutzlos, sondern für schädlich.
Ich habe erlebt, dass Studierende, die Kurse mit solchen Systemen besucht hatten, ein stärker verzerrtes Verständnis von Computern hatten als Leute, die gar keinen Kurs besucht hatten.
Für die meisten Menschen, die ein bisschen lernen wollen, wie ihr Computer funktioniert, ist ein Betriebssystemkurs besser; und wenn auch dort nur Zeit für ein kurzes Tutorial ist, würde ich „Writing my own bootloader“ empfehlen.
https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
Das heißt nicht, dass das Tutorial „Write your own VM“ schlecht ist, sondern dass meiner Erfahrung nach für die meisten Leute, die so etwas machen würden, andere Themen hilfreicher sind.
Kannst du genauer erklären, warum LC-3 zum Lernen von Computerarchitektur schlecht ist?
Ich verstehe, dass es sich komplett von realer Hardware unterscheidet und übermäßig simpel ist, aber ich frage mich, ob es auch aus der Perspektive des Schreibens eines CPU-Emulators schlecht ist.
Es war eine Dezimalmaschine, wie sie in den 1960ern vielleicht gebaut worden wäre, aber seit den 1970ern hat niemand mehr so etwas gebaut.
Solche Systeme können viele Grundlagen vermitteln, aber die Techniken aus https://en.wikipedia.org/wiki/Hacker%27s_Delight hängen meist von üblichen Zahlendarstellungen ab und sind daher schwerer zu lernen.
Da ich mich nicht gut auskenne, habe ich kurz bei Wikipedia nachgesehen; nach dem Comic hatte ich etwas Seltsames erwartet, aber auf den ersten Blick wirkte es nicht so schockierend.
Es fühlt sich an wie eine Mischung aus s/360, etwas x86 und ein klein wenig ARM oder anderen RISC-Architekturen; es gibt viele Auslassungen und merkwürdige Stellen, aber das Ziel scheint zu sein, schnell zu einer funktionierenden Implementierung zu kommen.
Ich würde gern wissen, was es deiner Meinung nach für den Unterricht „nicht nur nutzlos, sondern schädlich“ macht.
In vielen Informatikkursen in Indien werden anscheinend immer noch 8086/8088 verwendet.
Insbesondere kann man über ein PC-relatives Wort in der Mitte einen doppelt indirekten Load machen.
Trotzdem muss Subtraktion aus Negation gebaut werden, und Negation wiederum aus NOT und ADD ,,#-1.
Angesichts des begrenzten Raums für Befehlscodierungen wäre NOT d,s = XOR d,s,#-1 vermutlich eine bessere Nutzung gewesen.
Wenn man es genau nimmt, ist das keine virtuelle Maschine, sondern ein Emulator.
Im beschreibenden Sinn kann der Begriff zwar passen, und vor der Ära der Hardware-Virtualisierung gab es auch eine gewisse Unschärfe, aber heute bezeichnet die bei weitem häufigste Verwendung von „Virtual Machine“ eine Umgebung, die Hardware-Virtualisierungsfunktionen wie VT-x nutzt.
Die JVM ist weit verbreitet, die Ethereum VM wird EVM genannt, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... beschreibt BPF und eBPF wiederholt als „virtual machines“, und https://webassembly.org/ beginnt mit „WebAssembly (abgekürzt Wasm) ist ein binäres Befehlsformat für eine stackbasierte virtuelle Maschine“.
„Virtuelle Maschine“ ist weiterhin die gebräuchlichste Bezeichnung für eine virtuelle Maschine.
Persönlich gefallen mir Ausdrücke wie „fictive machine“, „fictious machine“, „imaginary computer“ oder „fantastic automaton“ besser, aber sie dürften sich kaum durchsetzen.
Man kann nicht immer statt „virtuelle Maschine“ einfach „Emulator“ sagen.
wasmtime kann man vielleicht einen Emulator nennen, aber WebAssembly selbst als Emulator zu bezeichnen, ist nicht korrekt; WebAssembly ist die virtuelle Maschine, die wasmtime emuliert.
Auch Emulatoren als virtuelle Maschinen zu bezeichnen, ist üblich, und eine laufende Emulator-Instanz ist ebenfalls eine virtuelle Maschine in einem anderen Sinn.
Es ist ebenfalls berechtigt, Hardware-Virtualisierungsumgebungen „virtuelle Maschinen“ zu nennen, und das überschneidet sich in gewissem Maß mit dieser letzten Bedeutung.
Im aktuellen Umfeld mag diese Verwendung überwältigend häufig sein, aber anderswo muss das nicht zwangsläufig gelten.
Im reinsten Sinn ist eine virtuelle Maschine einfach nur ein konstruierter Computer und sagt nichts darüber aus, wofür sie verwendet wird oder wie sie funktioniert.
Der Artikel nennt zwar die Emulation klassischer Konsolen als Beispiel, aber nach der gegebenen Definition ist klar, dass sehr viel mehr virtuelle Maschinen möglich sind.
Der Kernpunkt ist, dass eine virtuelle Maschine ein abstraktes Konzept ist und es sehr viele Arten davon gibt.
Simulatoren, Emulatoren, Hypervisoren usw. sind alle virtuelle Maschinen, und es gibt auch seltsame Formen virtueller Maschinen, die noch keinen Namen haben.
Das ist nicht unhöflich gemeint, im Gegenteil: Ich möchte respektvoll sein und den Begriff für Menschen, die ihn gerade lernen, klarstellen.
„Virtuelle Maschine“ wird unabhängig vom Grund häufig für jede Software verwendet, die Maschinencode oder Bytecode ausführt.
Das kann Virtualisierung einschließen, wird aber auch oft für Sprach-Runtimes verwendet, etwa Javas JVM oder Rubys YARV (Yet Another Ruby VM).
Ein Bereich, in dem man den Begriff eher nicht so häufig hört, ist ausgerechnet die Emulation; das liegt auch daran, dass die meisten modernen Emulatoren eher dazu tendieren, die zu emulierende Software dynamisch neu zu kompilieren, statt ein komplettes System zu emulieren.
Java dürfte wohl als „bei weitem häufigste Verwendung“ durchgehen.