Lernziel

Anwendung von Programmfäden und Semaphoren

Aufgabenbeschreibung

Im Rahmen dieser Aufgabe sollt ihr eine OO/MPStuBS-Anwendung eurer Wahl implementieren. Dabei sollten möglichst mehrere Fäden zum Einsatz kommen, die über eine Semaphore synchronisiert werden.

Vorgabe

Die umfangreiche Vorgabe enthält einen Zufallszahlengenerator, ein Dateisystem sowie einen Grafikmodus.

Zufallszahlengenerator

Der Pseudozufallszahlengenerator in Random muss zu Beginn mit einem Anfangswert initialisiert werden, und liefert danach mit jedem Aufruf von Random::number() eine "zufällige" Zahl zurück.

Dateisystem

Zur Vereinfachung der Datenverwaltung beinhaltet die Vorgabe ein Minix (3) Dateisystem.

Dieses kann entweder über den ATA Treiber die (QEMU-) Festplatte oder einen temporären Datenträger im Arbeitsspeicher (z.B. die vom Bootloader übermittelte initrd) eingebunden werden. Bei der zweiten Variante können Änderungen nicht persistent über Rechnerneustarts gespeichert werden, dennoch sollte diese Variante für den Testrechner verwendet werden.

Das Dateisystem benötigt eine dynamische Speicherverwaltung mit den malloc() und free() , welche – sofern nicht bereits geschehen – implementiert werden muss. Eine einfache Implementierung wie die Halde aus der Grundlagenvorlesung Systemprogrammierung ist natürlich ausreichend, allerdings sollte man darauf achten, dass der dafür statisch allokierte Speicherblock ausreichend groß ist (min. 16 MB).

Ein Abbild mit einem Megabyte speicher kann einfach mit den typischen Linux Boardmittel erstellt werden:

dd if=/dev/zero of=~/file.img bs=1MiB count=1
mkfs.minix -3 /dev/loop0  # optional --inodes <number>

Um Daten aufzuspielen (oder abzurufen) muss das Abbild eingebunden werden (z.B. mit mount ~/file.img /mnt/tmp/), was jedoch im CIP aufgrund Sicherheitsbedenken (und mangels funktionierendem FUSE-Dateisystem) nicht ohne weiteres möglich ist. Als üblicher Ausweg bietet sich libguestfs an, welches intern mit einer virtuellen Maschine arbeitet und dadurch eine Bearbeitung ermöglicht.

Die Vorgabe enthält allerdings in fs/tool eine Anwendung, welches die selbe Implementierung des Dateisystems wie das Betriebssystem nutzt um direkt auf ein Abbild zuzugreifen – komplett ohne besondere Privilegien können mit FTP-artigen Befehlen die Dateien und Ordner kopiert und modifziert werden.

Zur Vereinfachung sind Übersetzung und Aufruf des FSTool bereits in eurem Makefile wegabstrahiert: Alle Dateien im Ordner ./initrd/ werden automatisch in eine neue initiale Ramdisk (unter build/initrd.img) gepackt, zusammen mit etwa einen Megabyte freien Speicher – das Verzeichnis kann mittels INITRD_DIR und der freie Speicher in Bytes mit INITRD_FREE geändert werden.

Ebenfalls kümmert sich das Makefile um die korrekte Übergabe der Ramdisk an QEMU/KVM bzw. dem Bootloader auf dem Testrechner.

Wenn ihr nun das Dateisystem in eurem Betriebssystem verwenden wollt, müsst ihr zuerst die Ramdisk (mit der Speicheraddresse aus den Multiboot-Informationen) als blockorientiertes Geräte initialisieren, bevor ihr das eigentliche Dateisystem einhängen könnt:

#include "fs/ramdisk.h"
#include "fs/vfs.h"
// ...
void main() {
    // ...
    Ramdisk ramdisk;
    int error = VFS::mount("minix", &ramdisk, "");
    if (error != 0) {
        DBG << "Error mounting ramdisk (minix): " << -error << endl;
        return 1;
    }
    // ...
}

Danach könnt ihr mit den POSIX-artigen Schnittstellen ( VFS::open / VFS::read usw ) auf die Dateien zugreifen.

Grafikmodus

Mit VESAGraphics habt ihr eine einfache Schnittstelle zu den VESA BIOS Extensions, einem grundlegenden Grafikmodus. Wenn ihr diesen verwenden wollt, müsst ihr dazu jedoch noch ein wenig Hand anlegen:

Analog zu CGA_Screen benötigt ihr ein globales Objekt der Klasse Guarded_VESAGraphics (sinnigerweise in der main.cc) und ruft im Rahmen der Systeminitalisierung die Methode Guarded_VESAGraphics::init() auf. Mit Guarded_VESAGraphics::find_mode() könnt ihr nun nach den Kriterien Auflösung und Farbtiefe einen Grafikmodus aussuchen und falls ein valider Modus gefunden wird diesen mit Guarded_VESAGraphics::set_mode() setzen.

#include "syscall/guarded_vesagraphics.h"
char buffer1[1280*1024*4];
char buffer2[1280*1024*4];
Guarded_VESAGraphics vesa(buffer1, buffer2);
// ...
void main() {
    // ...
    vesa.init();
    VBEModeData_t* mode = vesa.find_mode(1024, 768, 24);
    if (mode != 0) {
        vesa.set_mode(mode);
    }
    // ...
}

Jetzt müsst ihr noch dafür sorgen, dass der Inhalt der Puffer auch in den Speicher der Grafikkarte geschrieben wird. Dazu dient die Methode VESAGraphics::scanout_frontbuffer . Diese ruft ihr entweder als Teil des Zeichenloops auf, immer dann wenn ein neuer Frame fertiggezeichnet wurde, oder führt sie im Watch-Epilog (dort allerdings die Variante ohne Guard) aus, was dafür sorgt, dass der Framebuffer der Grafikkarte mit einer festen Frequenz aktualisiert wird. Wenn ihr die mitgelieferte Beispielapplikation (VesaExample ) ohne Modifikationen ausführen wollt, dann müsst ihr zweitere Variante implementieren.

Damit die Systemlast durch den Scanout nicht zu hoch wird, empfielt es sich, den Scanout nicht bei jedem Timerinterrupt durchzuführen, ca. 20ms (entspricht maximal 50 Bilder pro Sekunde) sind ein tragbarer Kompromiss zwischen der Bildschirmaktualisierungsfrequenz und dem Overhead durch die vielen Kopiervorgänge. Dabei könnt ihr die Timerfrequenz im Bereich von 1ms belassen, den Scanout dann aber nur noch entsprechend jedes zwanzigste Mal durchführen (alternativ den Timer erhöhen). FPS zeigt eine einfache Möglichkeit die Bildwiederholungsrate zu messen.

Die bereitgestellten Grafikprimitiven ermöglichen Zeichnen von Linien und Rechtecken auf dem Bildschirm, die Ausgabe von Text (wie Title ) mit verschiedenen Schriftarten – und auch eine direkte Pixelmanipulation (Beispiel Fire).

Einbinden von Bitmaps

Wenn man analog zum Beispielprogramm Pong eigene Bitmaps einbinden möchte, so kann man diese mit GIMP einfach als C-Sourcecode (*.c) exportieren. Dabei sollte man keine Glib Typen verwenden. In der .c Datei findet man dann die entsprechenden Binärdaten in einem struct (identisch mit GIMP), welches die Grafikbibliothek als darstellen kann.

Achtung: Durch die Verwendung von Bitmapgraphiken direkt im Sourcecode kann das erzeugte Systemimage jedoch sehr groß werden.

Einbinden von PNG

Das Problem mit der den großen Binärdateien lässt sich durch die Verwendung von verlustfrei komprimierten PNG-Datein lösen. Allerdings benötigt die auf uPNG basierende Bibliothek eine dynamische Speicherverwaltung, welche (falls nicht bereits zuvor für die Festplatte geschehen) noch implementiert werden muss.

Achtung: Die Bibliothek unterstützt nur RGB und Graustufenbilder (mit und ohne Alphakanal) – jedoch keine Bilder mit angepasster Farbpalette.

Die Datei kann entweder mittels xxd -i bild.png > bild.c als statisches Datenarray im C-Sourcecode gespeichert und eingebunden werden, oder man verwendet einfach das Dateisystem indem man das Bild nach ./initrd/bild.png legt. Danach kann man es in dem Betriebssystem mit /bild.png als Pfadangabe für ein neues PNG Objekt.

Achtung: Da das Entpacken von komprimierten Bildern ressourcenintensiv ist, muss für ausreichend Speicher – sowohl Stack als auch Heap – gesorgt werden!

Die von der Grafikbibliothek bereitgestellten Methoden erlauben auch eine einfache Verwendung von Spritesheets, wodurch einfach Animationen dargestellt werden können (siehe Cat)

Lösungen früherer Jahre

Die Lösungen für Aufgabe 7 aus den Vorjahren findet ihr auf dem Testrechner im CIP-Pool im Netzwerkbootmenü unter Ruhmeshalle.

Zu beachten: Leider sind aufgrund des Umstiegs auf die neuen Testhardware (Intel Core i-Serie, welche etwas empfindlicher auf den Standard reagiert als die vorherige Intel Core 2-Serie) einige der alten Beispiele auf den Testrechnern nicht mehr lauffähig. Diese können jedoch (zum Teil) noch mit QEMU/KVM gestartet werden: kvm -kernel /proj/i4bs/halloffame/13_schach.elf