KSP Aufgabe 8

Statten Sie Ihre VM mit einem kompaktierenden Garbage-Collector nach dem "Stop & Copy"-Verfahren aus!

Vorbereitungen

1. Legen Sie beim Programmstart den Stack dynamisch mit malloc() an. Sehen Sie eine Kommandozeilenoption "--stack n" vor, die einen Stack mit n KiB bereitstellt (ACHTUNG: n * 1024 Bytes, NICHT Stack Slots, NICHT n * 1000 Bytes). Der Defaultwert soll n = 64 sein, falls diese Kommandozeilenoption nicht angegeben wird. Hinweis: Sie werden moeglicherweise Ihren Test auf Stackoverflow anpassen muessen!

2. Legen Sie beim Programmstart mit malloc() dynamisch einen eigenen Heap an, dessen Groesse man durch die Kommandozeilenoption "--heap n" festlegen kann. Dabei soll n die Gesamtgroesse des Heaps in KiB sein (ACHTUNG: n * 1024 Bytes, NICHT n * 1000 Bytes). Der Defaultwert soll n = 8192 sein, falls diese Kommandozeilenoption nicht angegeben wird.

3. Teilen Sie den Heap in zwei gleich grosse Haelften. Aendern Sie das Anlegen von Objekten so ab, dass Sie den benoetigten Speicherplatz fortlaufend von einer Haelfte des Heaps nehmen. Brechen Sie Ihr Programm ab, wenn diese Haelfte erschoepft ist.

Garbage Collector

1. Programmieren Sie einen kompaktierenden Garbage-Collector nach dem Verfahren "Stop & Copy", der anstelle des Programmabbruchs einen Sammeldurchlauf ausfuehrt. Steht nach dem Durchlauf immer noch nicht genuegend Platz fuer die verlangte Allokation zur Verfuegung, sollte Ihre VM mit einer passenden Fehlermeldung terminieren. Hinweise: Als "Broken Heart Flag" laesst sich sehr gut das zweithoechste Bit der "size"-Komponente benutzen. Der eigentliche "Forward Pointer" (= Byte-Offset in den Zielhalbspeicher, wo sich das kopierte Objekt befindet) belegt die restlichen 30 Bits. Das geht problemlos, da die "size"-Komponente bei bereits kopierten Objekten nicht mehr benoetigt wird. Die Zeiger zu den "Root-Objekten" findet man an allen Stellen in unserer VM, die Objektreferenzen halten: der statische Datenbereich, das Return-Value-Register, diejenigen Stack-Slots, die auf Objekte verweisen, und - nicht vergessen! - die vier Komponenten des Big-Integer-Prozessors "bip".

2. Da man beim Integrieren eines Garbage-Collectors leicht einmal einen eigentlich zu verfolgenden Zeiger vergessen kann, stellen Sie eine Kommandozeilenoption "--gcpurge" zur Verfuegung, die bewirkt, dass direkt nach einem Sammeldurchlauf der alte Halbspeicher mit Nullen ueberschrieben wird. So sollten sich Fehler der genannten Art schneller bemerkbar machen.

3. Instrumentieren Sie Ihren Garbage-Collector so, dass man mit der Kommandozeilenoption "--gcstats" beim Sammeldurchlauf die folgenden Werte angezeigt bekommt: Anzahl der seit dem letzten Durchlauf angelegten Objekte (sowie die davon belegte Zahl von Bytes), Anzahl lebender Objekte (sowie die davon belegte Zahl von Bytes), freier Platz nach dem Sammeldurchlauf (Bytes im momentan benutzten Halbspeicher). Sie sollten nach dem Ausfuehren der "halt"-Instruktion den Garbage-Collector einmal explizit aufrufen, damit man auch fuer kleine Programme mit wenig Speicherbedarf, die den GC sonst nicht triggern wuerden, diese statistischen Angaben erhaelt.

4. Der Instruktionssatz ist gegenueber Aufgabe 7 unveraendert; auch der Compiler und der Assembler bleiben exakt gleich (bis auf die Versionsnummern).

5. Hier nun die endgueltige Version der Referenzimplementierung:
njvm

Testprogramme

Die folgenden zwei etwas groesseren Testprogramme muss Ihre VM (bei verschiedenen Heapgroessen) fehlerlos ausfuehren; dann wird sie mit guter Wahrscheinlichkeit auch als Hausuebung akzeptiert.

Die Faktorisierung grosser Zahlen

Dieses Ninja-Programm hilft, die folgende Frage zu beantworten: Gegeben sind die Zahlen 10^n+1 (n = 1..30). Was sind die Primfaktoren jeder Zahl?

Bemerkung: Man muss hier zwischen Tests auf Zusammengesetztheit, Primalitaetsbeweisen und Methoden zur Faktorisierung unterscheiden. Es gibt verschiedene Algorithmen in jedem der drei Gebiete. Ein gutes Buch, das auch diese Themen behandelt, ist [Henry Cohen: A Course in Computational Algebraic Number Theory, Springer 1993].

Ein kleines Computeralgebra-System

Computeralgebra-Systeme werden in ihrem Kern oft als Interpreter in einer LISP-aehnlichen Sprache implementiert. Deshalb wird hier njlisp zur Verfuegung gestellt, eine Re-Implementierung des alten muLISP-80-Systems in Ninja. Der Makefile dient zum Zusammenbauen und Laufenlassen. Da das System auf mehreren Ebenen interpretiert ablaeuft, und diese Interpreter alle geladen werden muessen, folgt eine kurze Erklaerung der Makefile-Targets, jeweils zusammen mit einem kleinen Beispiel:

1) "make": erzeugt die Binaerdatei njlisp.bin.

2) "make run": laesst njlisp laufen. Probieren Sie als Eingaben:
a) (PLUS 3 4)
b) (TIMES (PLUS 3 4) (DIFFERENCE 10 7))
c) (PUTD (QUOTE SQUARE) (QUOTE (LAMBDA (X) (TIMES X X))))
d) (SQUARE 12345)
e) (SQUARE (SQUARE (SQUARE 12345)))
f) (OBLIST)

3) "make musimp": laesst njlisp laufen und laedt das LISP-Programm musimp.lsp , das die mathematische Notation von Ausdruecken erlaubt und eine eigene Programmiersprache (mit gefaelligerer Syntax als LISP) zur Verfuegung stellt. Es werden dann interaktiv Eingaben erwartet, die berechnet und ausgegeben werden. Probieren Sie als Eingaben:
a) 123456789*987654321;
b) 1-2*3+4*5;
c) FUNCTION F(N), WHEN N=0 OR N=1, N EXIT, F(N-1)+F(N-2) ENDFUN;
d) F(10);
e) FUNCTION G(N), A:0, B:1, LOOP WHEN N=0, A EXIT, H:A+B, A:B, B:H, N:N-1 ENDLOOP ENDFUN;
f) G(100);

4) "make mumath": laedt nach musimp.lsp auch noch die Mathematik-Module arith.mus (rationale Arithmetik) und algebra.ari (elementare Algebra). Probieren Sie als Eingaben:
a) 5/9 + 7/12;
b) ((236 - 3*127) * -13) ^ 16;
c) GCD(861, 1827);
d) (-24) ^ (1/3);
e) (-4) ^ (1/2);
f) #E ^ (3 * #I * #PI / 2);
g) 5*X^2/X - 3*X^1;
h) (5*X)^3 / X;
i) EXPD((3*Y^2 - 2*Y + 5)^3);
j) FCTR(6*X^2*Y - 4*X*Y^2/Z);

Bemerkung: Das ist nur ein kleiner Ausschnitt aus dem Funktionsumfang des damaligen Systems, das auf Mikrocomputern mit maximal 64 KiB (!) Hauptspeicher lief. Es gab ca. 15 Pakete (wie die oben benutzten arith.mus und algebra.ari), die Aufgaben aus den Bereichen Matrizen, Gleichungen, Trigonometrie, Logarithmen, Differential- und Integralrechnung sowie Summen- und Grenzwertbildung loesen konnten.