Vorschläge für (kleine) C Übungsaufgaben

Hier ist eine kleine Sammlung an Vorschlägen für Übungsaufgaben in C. Diese Aufgaben bzw. Probleme haben an sich nichts mit dem offiziellem Übungsbetrieb von SP zu tun, aber ich kann mir diese dennoch gerne anschauen und dazu Kommentare geben. Es sollte nicht gesagt werden müssen, aber die meisten Aufgaben (besonders wenn diese schwerer sind), sind nicht C-spezifisch und können in beliebigen anderen Systemsprachen (C++, Ada, OCaml, Rust, D, usw.) bearbeitet werden.

Warnung (?): Für die meisten Aufgaben habe ich keine Musterlösungen, und man sollte auch nicht mit der Mentalität an eine Lösung angehen. Dieses ist eher eine Frage der τέχνη, als der Technik.

Ich empfehle hierüber hinaus auch meine Links zu C Seite sollte man mehr über die Sprache und verwandte Themen erfahren wollen.

Einfache Aufgaben

Diese Aufgaben sollen gemütlich machbar sein wenn man bereits in C drin ist, und wenn nicht sehe ich es als eine gute Aufwärmung an. Da diese vom Umfang her recht klein sind, lohnt es sich die Aufgaben mehrfach, mit verschiedenen Ansätzen auszuprobieren.

Das Programm head

Es handelt sich hierbei um ein Standard-Werkzeug im Werkzeugkasten einen Unix-Nutzers. Die Prämisse ist einfach, lese und gebe die ersten 10 Zeilen der Eingabe aus, terminiere erfolgreich. Dabei ist die Eingabe entweder ein Kommandozeilen-Argument (d.h. fopen), oder die Standardeingabe (d.h. stdin).

Bonus: Als Optionale Erweiterung, kann man versuchen ein numerischen Flag robust zu verarbeiten. Bei dem Aufruf head -20, sollen die ersten 20 Zeilen eingelesen werden.

Das Programm tail

Eine kleine Variation auf der vorherigen Aufgabe (head), nur gibt diese die letzten 10 Zeilen aus. Auch hier kann man optional ein numerischen Flag verarbeiten.

Das Programm tac

Aufbauen auf den vorherigen Aufgaben, sollte es möglich sein tac zu Schreiben. Tac ist eine Umkehr von cat, im Sinne, dass es die Eingabe (bzw. übergebene Dateien auf der Kommandozeile) in umgekehrter Reihenfolge ausgibt: Zuerst die letzte Zeile, dann die zweit-letzte, usw.

Bonus: Implementiere die -s Option, welche es erlaubt zur Laufzeit beliebige Zeichen als Line-Delimiter zu interpretieren, anstatt nur Line feeds (\n). Siehe herzu getdelim(3).

Das Programm wc

Ein weiteres Werkzeug welches leicht zum selbst-implementieren ist, ist der word counter. Die Eingabe (wieder eine Datei oder die Standard-Eingabe) wird dabei eingelesen, und das Programm zählt mit wie viele Zeichen (ASCII), Wörter (getrennt mit Leerzeichen, hier kann isspace aus ctype.h hillfreich sein) und Zeilen auftreten. Diese drei Werte werden nacheinander Ausgegeben:

cip1e1$ cat the-file
Print newline, word, and byte counts for each FILE, and a total line if
more than one FILE is specified.  A word is a non-zero-length  sequence
of characters delimited by white space.
cip1e1$ wc the-file
3  32 184	the-file

Außerdem kann man sich mit den Flags -c, -w bzw. -l entscheiden die Ausgabe einzuschränken auf nur die Informationen die einen interessieren.

Ein Verschlüsselungs-Programm

Mit einer Verschlüsselung deiner Wahl, schreibe ein Programm welches text auf der Standard-Eingabe einliest, und den verschlüsselten Text auf der Standard-Ausgabe ausgibt. Hierzu kann man eine einfache Klassische-Chiffre benutzen wie rot13 (empfohlen) oder Vigenère anschauen. Schreibe auch ein Programm welches den verschlüsselten Text wieder entschlüsselt.

Bonus: Schreibe das Programm so, dass je nachdem wie das Programm aufgerufen wird (bspw. encrypt zbw. decrypt), der richtige Modus benutzt wird.

Bonus²: Benutze eine kryptographische Bibliothek wie OpenSSL oder libsodium.

Eine alternative zu strtok

Die Funktion strtok ist durchaus Kontrovers, aufgrund des impliziten globalen Zustands. Im Nachhinein können wir uns überlegen wie man das hätte besser machen können. Ich schlage hierzu diese Signatur vor:

int ftoken(FILE *in, void (*f)(char *t), int (*tok)(int c));

Die Idee hier ist, dass wir direkt von einem Datenstrom in lesen, und anstatt wie mit strtok Token mittels einer Disjunktion von Zeichen von einander zu trennen ("abc", heißt ließ ein Token bis a, b oder c auftritt), benutzen wir eine Funktion tok, welches mit jedem Zeichen c nacheinander Aufgerufen wird, und drei Werte zurückgeben kann:

• = 0, ließt weiter, es wurde noch kein Token gefunden
• > 0, es handelt sich bei c um ein Trennzeichen
• < 0, die Funktion ftoken soll insgesamt zurückkehren

Wurde ein Token ganz gelesen (Rückgabewert von tok ist ≤ 0), wird eine Zeichenkette an die Funktion f übergeben.

Die Aufgabe besteht daraus, diese Funktion oder eine Variation deiner Wahl zu implementieren.

Das Programm fmt

Das Programm fmt (kurz für format) ließt Prosa auf der Standard-Eingabe ein, und bricht Sätze bei Möglichkeit um, so dass alle Zeilen in einem Paragraphen nicht mehr als $COLUMNS viele Spalten auf dem Terminal einnehmen. Die Umgebungsvariable $COLUMNS kann mittels der Funktion getenv(3) abgefragt werden.

Ein RPN Taschenrechner (aka Das Programm dc)

Historisch waren Taschenrechner in Postfixnotation praktisch weil man keine Klammern braucht um arithmetische Ausdrücke eindeutig einzulesen. Während 2 * 3 / 4 entweder als (2 * 3) / 4 oder 2 * (3 / 4), ist bei 2 3 * 4 / eindeutig, dass es sich um den ersten Fall handelt.

Diese Aufgabe besteht daraus ein solches Programm zu implementieren. Man kann dabei die Argumente direkt aus argv einlesen (wobei * unpraktisch ist, weil globbing) oder wie dc die Argumente von der Standard-Eingabe verarbeiten.

Bonus: Unterstütze symbolische Arithmetik, wo nicht-Zahlen als undefinierte Werte interpretiert werden. So soll a 2 3 * zu 6 a reduziert, und a a - zu 0.

Ein Deduplikations Programm

Es kommt gelegentlich vor, dass man auf einem Dateisystem mehere Dateien hat mit dem gleichen Inhalt, welche sich auch nicht ändern mit der Zeit (Urlaubsbilder, PDF Dateien, etc.). Dennoch verbraucht jede Instanz einer Datei den Speicherplatz einzeln. Man kann mit Hard Links den Speicherverbrauch optimieren, wenn man diese Dateien alle auf den gleichen Index-Knoten verweisen lässt.

Da es umständlich ist dieses händisch zu erledigen, die Arbeit aber recht mechanisch ist, eignet es sich ein Programm zu schreiben. Hier ist beispielsweise eine Shell-Pipeline, mit welcher, rekursiv alle Dateien im jetzigen Verzeichnis abgesucht werden, und alle Dateien mit dem gleichen Inhalt (oder zumindest dem gleichen MD5 Hashwert) aufeinander gelinkt werden:

find . -type f -print0 | xargs -0 md5sum | sort | awk -F' ' '$1 == LH { print "ln -f", LF, $2; } { LH = $1; LF = $2 }' | sh

Diese Aufgabe besteht darin, diese gleiche Funktionalität in C zu implementieren. Man kann unter der Annahme arbeiten, dass sich der Inhalt von den Dateien nicht ändert während das Programm läuft, und wenn Duplikate gefunden werden, dann wird die neue Datei mit unlink(2) entfernt, und dann mit link(2) ein Hard-Link erstellt.

Bonus: Bestimme Duplikate nebenläufig, und stelle sicher dass es keine Wettlaufsituationen im Programm gibt. Hier auch die Erinnerung, dass Valgrind benutzt werden kann um diese zu erkennen (siehe Helgrind).

Das Programm nc

Mit dem Programm nc (netcat) kann man sich an einen Server verbinden, und die Kommunikation direkt einsehen und kontrollieren. Hier zum Beispiel, wird die Verbindung mit einem HTTP Server aufgemacht und nachdem man die Anfrage abschickt, antwortet der Server mit der Website:

cip1e1$ nc example.com 80
GET / HTTP/1.1
Host: example.com
Accept: */*

HTTP/1.1 200 OK
Age: 524466
Cache-Control: max-age=604800
Content-Type: text/html; charset=UTF-8
...

Die Schwierigkeit im Gegensatz zu den Aufgaben in SP1 wie der snail, ist dass man gleichzeitig auf der Standard Eingabe wie auch der Netzwerk Eingabe lauschen muss, und die Nachrichten gleich weiterleitet. Dazu muss ein Systemaufruf wie poll(2) benutzt werden: Es sagt blockiere gleichzeitig auf mehreren Datei-Deskriptoren bis zumindest eines bereit ist. Damit kann man gleich Nachrichten vom Server darstellen, und Benutzer-eingaben verschicken — ganz ohne Fäden.

Die Aufgabe ist nun diese Client-Seitige Grundfunktionalität von nc selbst zu implementieren.

Bonus: Unterstütze auch den -l Flag, mit dem nc auch als Single-Shot Server benutzt werden kann.

Aufwendigere Aufgaben

Hier kann man etwas mehr Zeit damit verbringen, sich zu überlegen wie man die Aufgabe angeht, bevor man anfängt etwas zu schreiben. Die Übung, im Kopf über komplexere Probleme nachzudenken, und vorherzusehen wo Probleme (Algorithmischer oder Sprach-technischer) Art auftreten werden, ist über C oder SP hinaus wertvoll. Dennoch sollte es in allen fällen möglich sein eine mehr oder weniger elegante Lösung zu finden.

Das Programm grep

Das Programm Grep ist ein Kanonisches C-Programm, welches sich unter Informatikern sogar als Verb durchgesetzt hat (Grep mal nach foo ist ein objektiv normaler Satz). Der Name geht auf den Ursprünglichen Unix-Editor zurück, aber die wesentliche Funktionalität ist, dass ein Regulärer Ausdruck eingelesen wird, und als Filter angewandt wird auf alle Zeilen der Standard Eingabe. Nur die Zeilen, welche dem Regulärem Ausdruck genügen, werden auf der Standard Ausgabe auch ausgegeben.

cip1e1$ cat the-file
Print newline, word, and byte counts for each FILE, and a total line if
more than one FILE is specified.  A word is a non-zero-length  sequence
of characters delimited by white space.
cip1e1$ grep FILE the-file
Print newline, word, and byte counts for each FILE, and a total line if
more than one FILE is specified.  A word is a non-zero-length  sequence

Hier wurde nach dem einfachen Regulärem Ausdruck FILE gesucht. Komplizierter Ausdrücke wie ^f[^a]*.{2,10} werden auch unterstützt.

Implementiere diese Aufgabe, und benutze hierzu die Funktionen aus regex.h.

Eine Regular-Expression Engine

Passend zu der vorherigen Aufgabe, kann man sich auch überlegen wie Reguläre Ausdrücke tatsächlich implementiert werden. Dabei muss man Theorie und Praxis voneinander unterschieden: Wenn man ab*(c|d)? (a gefolgt von einer beliebigen Anzahl von bs, und danach optional ein c oder d) sieht, handelt es sich zunächst nur um eine Darstellung, welches äquivalent auch in der Darstellung eines endlichen Zustands-Automaten gezeichnet werden kann:

Die wichtige Einsicht aus der Theorie der formalen Sprachen ist, dass ein Regulärer Ausdruck aus drei komplexen und drei atomaren Bestandteilen besteht:

1. Konkatenation: Wenn $S$ und $T$ Reguläre Ausdrücke sind, dann ist die Verkettung $ST$ dieser beiden auch ein Regulärer Ausdruck.
2. Disjunktion: Wenn $S$ und $T$ Reguläre Ausdrucke sind, dann ist die Vereinigung beider $S|T$ auch ein Regulärer Ausdruck.
3. Repetition (aka. Kleenesche Hülle): Wenn $S$ ein Regulärer Ausdruck ist, dann ist die beliebige Wiederholung von $S$ ($S^{*}$) ein Regulärer Ausdruck.
4. Die leere Menge $\varnothing$, welcher keine Eingabe genügt.
5. Das leere Wort $\epsilon$, welches jeder Eingabe genügt.
6. Die Buchstaben des Eingabe-Alphabets, beispielsweise ASCII.

Alle anderen Konstruktionen die man aus regex.h kennt (+, {1,3}, [[:alnum:]]), können aus diesen Bausteinen hergeleitet werden.

Es ist interessant sich aus dieser Theorie selbst eine Implementierung herzuleiten, aber man kann sich auch einen Artikel von Russ Cox oder Rob Pike zu dem Thema durchlesen (mehr Theorie kann in Introduction to Automata Theory, Languages, and Computation nachgelesen werden, verfügbar in der Uni-Bibliothek) um eine gute Idee davon zu bekommen, wie dieses elegant und effizient umgesetzt werden kann.

Auf dieser Grundlage kann man sich überlegen wie eine Funktion mit dieser Signatur

bool re_match(struct regexp *re, char *input);

struct regexp {
     enum re_type {    /* wer "enum" nicht kennt, siehe. */
	  RE_CONCAT, RE_DISJUNCT, RE_REPEAT, RE_EMPTY_SET, RE_EMPTY_WORD, RE_LITERAL
     } type;
     union {           /* wer "union" nicht kennt, siehe. */
	  struct re_concat     { struct regexp *s, *t; } concat;
	  struct re_disjunct   { struct regexp *s, *t; } disjunct;
	  struct re_repeat     { struct regexp *s; }    repeat;
	  struct re_literal    { char c; }             literal;
     } content;
};

#define CON(s_, t_) &((struct regexp) { .type = RE_CONCAT,   .content.concat   = { .s = s_, .t = t_ }})
#define DIS(s_, t_) &((struct regexp) { .type = RE_DISJUNCT, .content.disjunct = { .s = s_, .t = t_ }})
#define REP(s_)	    &((struct regexp) { .type = RE_REPEAT,   .content.repeat   = { .s = s_ }})
#define EMP	    &((struct regexp) { .type = RE_EMPTY_SET })
#define EPS	    &((struct regexp) { .type = RE_EMPTY_WORD })
#define LIT(c_)	    &((struct regexp) { .type = RE_LITERAL,  .content.literal  = { .c = c_ }})

struct regexp *re_example1 = CON(LIT('a'), CON(REP(LIT('b')), DIS(DIS(LIT('c'), LIT('d')), EPS)));

Bonus: Definiere die oben erwähnten, fehlenden POSIX Metazeichen als zusätzliche Makros-Definitionen, basierend auf den obigen sechs primitiven.

Ein Parser für Regular Expression Notation

Weiter aufbauend auf den letzten zwei Aufgaben, wäre es interessant die umständliche Syntax von struct regexp automatisch aus einer Zeichenkette generieren zu können. Die Komplikation ist, dass zunächst eine lineare Darstellung von einem Regulärem Ausdruck als Kontext-Freie Sprache aufgefasst werden kann, also in anderen Worten, man muss zählen (in diesem Fall Klammern) um ein Wort richtig zu erkennen.

Man stelle sich also eine Funktion mit dem Prototypen

struct regexp *re_parse(char *regexp);

Ein weiterer Vorschlag wäre es einen fertigen Parser Generator zu verwenden wie Lex/Yacc (bzw. die GNU Implementierungen Flex/Bison). Siehe hier für eine schöne Einführung zu diesen allgemeinen Werkzeugen.

Bonus: Schreibe die Aufgabe grep von oben um, um re_parse und re_match zu benutzen.

Ein Brainf*** Interpreter

Unter dem Begriff Esoterische Programmiersprachen verstehen sich meist Turing-Vollständige (d.h. nicht schwächer oder mächtiger als alle anderen gängigen Programmiersprachen), welche aber absichtlich umständlich zum benutzen sind. Der prominenteste Vertreter dieser Familie ist Brainf***, gekennzeichnet durch den starken Kontrast zwischen wie einfach die Sprache ist und wie unleserlich und unpraktisch diese ist. Hier ein Beispiel, dieses Programm gibt Hello World! aus:

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]
<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[
<++++>-]<+.[-]++++++++++.

Eine Erklärung der Sprache, sollte auf dem obigen Link zu finden sein. Die zentrale Idee ist, dass jedes Ziehen eine Bedeutung hat, aber nur 8 verschiedene Zeichen haben einen Effekt. Alles andere kann verworfen werden als Kommentar. Die Zeichen manipulieren ein Speicher-band (+ und -), die Position eines Schreib-Lese Kopfs (> und <), den Kontroll-Fluss der Ausführung ([ und ]), oder die Ein-/Ausgabe (. und ,).

Die Aufgabe besteht darin ein Interpreter für diese Sprache zu schreiben. Eine Sammlung von Programmen zum testen findet sich hier. 

Eine Virtuelle Maschine mit eigener Recherarchitektur

Nach der letzten Aufgabe, sollte man ein gutes Gefühl für wie eine Maschine basierend auf Instruktionen in C nachgebildet werden kann. Nun wäre es nett dieses etwas komplizierter zu machen, indem das Vokabular dieser Maschine ausgeweitet wird. Anstatt nur acht verschiedene Zeichen zu interpretieren, soll es in dieser Aufgabe darum gehen eine eigene Recherarchitektur zu entwerfen. Welche Befehle intrinisch Kodiert werden ist frei und darf nach Geschmack entschieden werden.

Es empfiehlt sich eine Stack oder eine Register-Register-Architektur zu wählen. Das Ziel sollte es sein binären Code aus einer Eingabe (bspw. eine Datei welche über argv übergeben wird) zu interpretieren. Hierzu eignet sich der Einsatz von Bitfeldern:

struct instr {
  enum { MOV, ADD, SUB, /* ... */, CALL, RET } cmd : 16;
  union {
    struct {
      unsigned arg0 : 16;
      unsigned arg1 : 16;
      unsigned arg2 : 16;
    } args;
    struct {
      unsigned arg : 32;
    } addr;
    /* ... */
  } args : 48;
}

Versuche verschiedene Arten von Befehlen zu implementieren:

Daten/Arithmetische Operationen

In anderen Worten, die gewöhnlichen Operationen auf Daten wie Addition, Subtraktion, Multiplikation, Division mit/ohne Rest, Vergleiche, etc. Dieses kann erweitert werden mit Vektor-Operationen oder Operationen auf zusätzlichen Datentypen wie Symbolen.

Hauptspeicher Operationen

Falls man sich für eine Register-Architektur entscheidet, sollte man grundsätzlich ein paar Register wie einen Akkumulator, einen Stack-Pointer, einen Program-Counter, ein Register mit Flags für Operationen mit Nebeneffekten haben und ein paar Allzweck-Register (die Betonung liegt hier auf sollen, es ist auch produktiv sich zu überlegen mit wie wenig man auskommen kann, bzw. was hilfreich ist). Zwischen diesen und dem simulierten Arbeitsspeicher (benutzt hierzu mmap(2), um den Speicher gleich in einer Datei einsehbar zu machen), sollten es Befehl(e) geben um Daten auszutauschen.

Controll-Fluss Operationen

Es wäre nützlich einen bedingten Sprung zu haben, damit man if und while nachbilden kann. Wie man in der letzten Aufgabe ggf. schon gesehen hat, braucht man dazu nicht mehr als eine Operation, aber es kann gemütlicher sein auch einen unbedingten Sprung direkt anzugeben, ohne den Flags-Register setzen zu müssen. Darüber hinaus, kann man sich noch Gedanken machen wie Funktionen in deiner ABI aufgerufen werden. Man kann ganz minimalistisch sein, und dem Benutzer jedes mal das Speichern der aktuellen stelle im Programm, die Übergabe und das aufräumen des Stacks überlassen, oder Instruktionen wie CALL und RET implementieren, und damit seine Architektur um ein einheitliches Vokabular erweitern.

Eingabe/Ausgabe Operationen

Um die Programme interessanter zu machen, wäre es wünschenswert Instruktionen zu haben welche Ausgabe generieren oder einlesen. Im einfachsten Fall sollte eine Abbildung auf die C Funktionen getchar/putchar ausreichen, aber man kann es beliebig Verkomplizieren. Wenn ein Befehl wie SYSCALL umgesetzt wird, kann man sich auch überlegen wie ein Schichtenmodell umgesetzt werden kann, um Programme in verschiedenen Privilegienstufen auszuführen.

Bonus: Implementiere eine Instruktion für Nicht-Determinismus, welches mittels fork die Maschine in zwei Prozessen auf deinem System verdoppelt, aber gleichzeitig auch versucht zwischen den Prozessen zu Synchronisieren (siehe semaphore.h) damit die Anzahl der Neben-läufigen parallel-Instanzen des Programms eine dynamisch/statisch definierte Grenze nicht überschreitet.

Einen eigenen Assembler

Nur weil wir eine eigene Recherarchitektur haben, müssen wir nicht alles Binärcode geschrieben werden (es ist aber durchaus möglich mit einem Hex-Editor). Der erste Schritt zu einer angenehmeren Benutzung wäre es ein Symbolischen Assembler zu haben, wo also Sprungmarken und Addressen nicht fix kodiert werden müssen, sondern bei der Übersetzung vom Assembler zum Binär-Code berechnet werden.

Die Befehle sollten genau zu der eigenen Rechner-Architektur passen, aber es ist auch erlaubt/wünschenswert komplexe Befehle beim Übersetzen auf primitive Operationen zu vereinfachen (bspw. sollte man sich zuvor dagegen entschieden haben CALL und RET zu implementieren, kann man es jetzt als eine Art Makro einfügen).

Das Einlesen sollte nicht zu kompliziert sein. Konventionell wäre es auf jeder Zeile einen Befehl zu haben. Das erste Wort deutet den Befehl an, und die restlichen Wörter sind dementsprechend Argumente. Eine Zwischenspeicherung wird notwendig sein, um Referenzen aufzulösen welche erst später auftauchen.

Eine graphische Anwendung

Bisher haben alle Aufgaben nur Textulle Effekte gehabt, nun soll es darum gehen die Fähigkeiten modernen (d.h. alles seit den 1980ern) auszunutzen und etwas zu zeichnen. Hier aber kommen wir bereits an die grenzen von POSIX und der klassischen Unix Paradigma, und man muss sich für eine Bibliothek entschieden. Die liegt hier zwischen low-level Bibliotheken wie X11lib oder XCB welche direkte Kontrolle auf ein Display-Server wie X11 erlauben, oder Bibliotheken wie SDL2 oder Cairo die auf einer etwas höheren Abstraktionsebene arbeiten. Man kann auch gleich ein ganzes graphische Toolkit benutzen, wie Tk, Qt oder GTK.

Diese Aufgabe ist eher Vage, denn der Hauptzweck ist sich mit verschiedenen Bibliotheken und ihren Schnittstellen zu beschäftigen, abzuwägen was einem gefällt und dann zu sehen wie man es tatsächlich benutzt. Insofern installiert, kann sich hier ein Werkzeug wie pkg-config gut eignen, um die notwendigen Compiler-Flags zu ermitteln:

cip1e1$ pkg-config --cflags cairo
-I/usr/include/cairo -I/usr/include/glib-2.0 -I/usr/lib/x86_64-linux-gnu/glib-2.0/include -I/usr/include/pixman-1 -I/usr/include/freetype2 -I/usr/include/libpng16 
cip1e1$ pkg-config --libs cairo
-lcairo

Wenn man eine Makefile benutzt, spezifisch mit GNU Make, kann man diese Ausgaben auch dynamisch bestimmen lassen:

CFLAGS  = -std=gnu11 -pedantic $(shell pkg-config --cflags cairo)
LDFLAGS = $(shell pkg-config --libs cairo)

Mögliche Anwendungen sind eine sich einfache, selbst-aktualisierende Analog-Uhr zu Zeichen oder die Mandelbrot Menge (siehe complex.h), idealerweise mit Maus-gesteuerter Zoom-Funktionalität, oder Conways Game of Life.

Das $N$-Körper Problem

Es handelt sich bei diesem klassischen Problem der physikalischen Mechanik um $n$ Punkte in einem Raum mit Masse, welche nach Newton gegenseitig Schwerkraft aufeinander auswirken. Allgemein ist das daraus entstehende Differenzialgleichungssystem nicht trivial zum lösen, aber wir interessieren uns hier nicht für die exakte Werte in Abhängigkeit von der Zeit, sondern nur um eine Numerische Approximation. Es gibt Zahlreiche sogenannte Runge-Kutta Methoden welche hierzu umgesetzt werden können.

Die Implementierung sollte nun von der Eingabe eine beliebige Anzahl an Objekten (Für 2D: $x$ und $y$ Koordinaten, und eine positive Masse) und auf der Ausgabe Zeile für Zeile die Position aller Punkte zu jedem Zeit-Schritt, welches durch ein Parameter $\Delta$ steuerbar sein soll.

Ein Werkzeug wie Gnuplot kann dazu benutzt werden, um die Ergebnisse zu visualisieren. Hier kann man auch mit Compiler-Optimierungen spielen, um zu sehen wie viel schneller (oder langsamer) das Programm ist wenn übersetzt mit -O1, -O2 oder -O3.

Bonus: Erweitere die Punkte zu Sphären welche aneinander stoßen können.

Bonus²: Zeichne die Resultate der Simulation in Echtzeit mit einer graphischen Methode aus der letzten Aufgabe.

Sunob: Eine Vereinfachung des Problems nennt sich Patched conic approximation, womit das Gesammtproblem auf mehere 2-Körper Probleme reduziert werden, und damit der Rechenaufwand beachtlich schrumpft.

Ein IRC-Bot

Das IRC Protokoll ist ein standardisiertes Protokol, bis heute noch in (machen) Informatiker-Kreisen populär ist, vor allem im Free Software milieu. Ein Grund hierfür, neben dem offenen Aufbau und der Vielzahl an Clients, ist wie relativ einfach es ist das Protokol zu implementieren.

Eine Übersicht über das Client-Server Protokol lässt sich hier, und wer eine Übersicht zur Netzwerkprogrammierung in C Braucht kann Beej's Guide to Network Programming anschauen. Im wesentlichen braucht man wissen, dass IRC über TCP stattfindet, wobei sich ein Client an ein IRC Server wie irc.fau.de am Port 6666 (es gibt auch andere Ports, je nach Server und anderen Details) verbindet. Die Kommunikation kann dann so aussehen:

:Uni-Erlangen.DE 020 * :Please wait while we process your connection.
NICK johnnyb
USER johnnyb -1 * :Mr Goode
:Uni-Erlangen.DE 001 johnnyb :Welcome to the Internet Relay Network johnnyb!-johnny@my-host.net
:Uni-Erlangen.DE 002 johnnyb :Your host is Uni-Erlangen.DE, running version 2.11.2p3
...
JOIN #rocknroll
:mayb!maybellene@somewhere.com PRIVMSG #rocknroll :Hey there Johnny!
PRIVMSG #rocknroll :Hi mayb
...

Mit diesem Hintergrund, besteht die Aufgabe darin ein IRC Bot zu implementieren, d.h. ein Programm welches sich an IRC Netz verbindet, einem Kanal beitritt und auf gewisses Nachrichten reagiert. Die Funktionalität steht einem frei, aber hier sind ein paar Vorschläge:

• Ein Gruß-Bot, welches auf ein Hallo mit Hallo antwortet.
• Ein rot13-Bot, welches auf jede Nachricht welche mit !rot13 anfängt, mit der rot13-verschlüsselten Nachricht antwortet.
• Ein Quote-Bot, welches sich die letzte Nachricht von jedem Nutzer merkt, und auf !quote foo mit der letzten Nachricht von dem Nutzer foo antwortet.

Ein Lisp-Interpreter

Die Programmiersprache Lisp ist im Kern von einer eleganten Einfachheit gekennzeichnet. Alle Objekte in der Sprache sind Ausdrücke, welche ausgewertet werden können. Im der klassischen Version (LISP 1.5, 1962) gibt es dabei zunächst zwei verschiedene Typen von Ausdrücken: Atomare Symbols und Komplexe Cons-Cells. Ein Symbol kann dargestellt werden durch eine beliebige Zeichenkette (nil, chess, make-derivation, q8, etc. wobei der Inhalt an sich keine Bedeutung hat) und eine Cons-Zelle kann zwei weitere Ausdrücke enthalten. Die Notation hierfür ist (left . right), und wenn im rechten Wert eine weitere Zelle enthalten ist oder das Symbol nil, wie in diesem Beispiel (chess . (nil . (q8 . nil))), dann kann man auch die Listen-Notationen benutzen und (chess nil q8) schreiben, und man nennt das Gesamt-Objekt auch eine Liste.

Die zentralen Operationen von einem Lisp Interpreter nennen sich eval (auswerten) und apply (anwenden). Bei der Auswertung eines Symbols wird in einem Kontext der Wert nachgeschlagen und zurückgegeben. Dieser Kontext wird während der Auswertung aufgebaut und besteht am Anfang nur aus vordefinierten werten. Die Auswertung von Listen wird als Funktionsaufruf interpretiert. Dabei werden erst alle Elemente der Liste — rekursiv — ausgewertet, und dann wenn das erste Element zu einem Funktions-Objekt ausgewertet wird, werden die restlichen Werte als Argumente auf dieses Objekt angewandt. Ein Funktions-Objekt ist dabei entweder ein Symbol welches einer Built-In Operationen fest zugewiesen ist, oder ein Liste der Form (lambda (arg0 arg1 ...) body), wo das erste Argument im Kontext mit dem Symbol arg0 assoziiert wird, das zweite Argument mit arg1, etc. während body ausgewertet wird, wonach diese Assoziationen aufgelöst werden.

Zu möglichen Built-In Operationen zählen cons, eine Funktion mit zwei Argumenten um eine neue Cons-Zelle zu erstellen, die Funktionen car und cdr um jeweils auf das erste und zweite Element einer übergebenen Cons-Zelle zuzugreifen, quote welches die Auswertung des ersten und einzigen Elements verweigert, cond oder if um bedingte Auswertung umzusetzen, das Prädikat atom um zu prüfen ob ein Objekt ein Symbol oder eine Cons-Zelle ist und eq um die Gleichheit (dh. die gleiche zugrundeliegende Darstellung) zu prüfen.

Diese Aufgabe kann mit oder ohne Parser (genau wie bei den Regulären Ausdrücken umgesetzt werden), und zunächst braucht man sich nicht mit Garbage Collection auseinanderzusetzen.

Bonus: Setze dich mit Garbage Collection auseinander.

Bonus²: Erweitere den Interpreter um Ganzzahlen und Arithmetische Operationen. Man sollte in der Lage sein den Ausdruck (+ 1 2) zu 3 auswerten zu lassen.

Bonus³: Erweitere den Interpreter um Zeichenketten (nicht Symbole!) und Vektoren, auf denen man auf genaue Elemente zugreifen und manipulieren kann. Auf dieser Basis kann man dann Eingabe/Ausgabe implementieren, und ein REPL in dem eigenen Lisp Interpreter schreiben.

Bonus⁴: Implementiere in diesem Interpreter ein Programm welches einfache symbolische Differenzierung macht. Der Ausdruck (+ (^ x 2) (sin x) sollte durch die Auswertung der Funktion (deriv (quote (+ (^ x 2) (sin x))) (quote x)) zu (+ (* 2 x) (cos x)) ausgewertet werden. Hier wäre es auch praktisch die Kurzschreibweise 'a für (quote a) zu dem Parser hinzuzufügen.

Eine Bignum Bibliothek

Unter dem Begriff Bignum verstehen sich Datentypen, welche Zahlen darstellen können, die über der Wortbreite eines System kodiert werden können. So kann auf einem 64-Bit System mit Zweierkomplement ein long ein Wert in dem Intervall $[2^{63};2^{63}-1]$ sein, und nicht darüber hinaus. Je nach Anwendung, kann man mit dem approximate counting algorithm noch einiges ausschöpfen, aber wenn man genaue Werte braucht, und bereit ist mit Laufzeit und Speicher zu zahlen, verwaltet man den Speicher einer Zahl dynamisch und implementiert verschiedene Arithmetische Operationen händisch. Diese Art von Big-Number Arithmetik wird OOTB von vielen Sprachen bereits angeboten, aber ist vom grundsätzlichem Aufwand nicht zu schwer in C zu implementieren.

Eine naive und einfache Implementierung kann Zahlen als Strings darstellen: "0", "42" oder "18446744073709551616". Etwas effizienter ist es eine höhere Basis zu benutzen (anstatt nur die Zeichen 0 bis 9 aus char zu benutzen, kann man ganz uint64_t verwenden), und möglichst viel Rechnerei auf einmal erledigen, ohne Logik dazwischen. Die Aufgabe soll daraus bestehen, zu überlegen wie man einen solchen Datentypen darstellen will, und dann arithmetische Operationen darauf zu implementieren. Hier ein paar Vorschläge für eine Schnittstelle:

#ifndef BN_H
#define BN_H

#include <stdbool.h>
#include <sys/types.h>

typedef struct bignum bn;

bn *bn_make();

void bn_inc(bn *);
void bn_dec(bn *);

bn *bn_add(bn *, bn *);
bn *bn_sub(bn *, bn *);
bn *bn_mul(bn *, bn *);
bn *bn_div(bn *, bn *);

bn *bn_abs(bn *);

bool bn_eq(bn *, bn*);
bool bn_lt(bn *, bn*);
bool bn_lte(bn *, bn*);
bool bn_gt(bn *, bn*);
bool bn_gte(bn *, bn*);

bn *bn_mod(bn *, bn*);
bn *bn_exp_mod(bn *, bn*, bn*);

bool bn_str(char *, size_t);

#endif /* BN_H */

Schwerere Aufgaben

Ob hier noch der Begriff kleine Übungsaufgabe zutreffend ist, ist durchaus kontrovers. Abhängig vom Eigenenthusiasmus und C-Kenntnissen, sollten diese Aufgaben eher von Enthusiasten bearbeitet werden, welche auch bereit sind sich für eine Lösung mit Themen über C und SP hinaus zu beschäftigen. Daher sollte das Bearbeiten dieser Aufgaben den allgemeinsten Nebenwert haben.

Ein Prolog-Interpreter

Noch eine kleine und elegante Sprache ist Prolog, die klassische Logik Programmiersprache, wo deklarativ Lösungen für Probleme beschrieben werden, und eine Anfrage dann systematisch von dem System gelöst wird — bzw. versucht wird zu lösen, weil Prolog eine Turing-Vollständige Sprache ist, und daher nicht immer terminieren muss.

Ein Prolog Programm besteht aus eine Folge von Regeln (eng. Clauses). Jede Regel, hat die Form A. (für Axiome) oder A :- B für Implikation (Um A, zu folgern, muss B sichergestellt werden). Diese können sich gegenseitig aufeinander und auf sich selbst beziehen, wie in diesem klassischem Beispiel

parents(uranus, gaia, rhea).
parents(uranus, gaia, cronus).
parents(cronus, rhea, zeus).
parents(cronus, rhea, hera).
parents(cronus, rhea, demeter).
parents(zeus, leto, artemis).
parents(zeus, leto, apollo).
parents(zeus, demeter, persephone).

man(uranus).
man(cronus).
man(zeus).
man(apollo).
man(artemis).

woman(gaia).
woman(rhea).
woman(leto).
woman(demeter).
woman(persephone).
woman(hera).

father(X,Y) :- parents(X,_,Y).
mother(X,Y) :- parents(_,X,Y).

parent(X,Y) :- father(X,Y); mother(X,Y). % "φ; ψ" steht fuer φ oder ψ

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). % "φ, ψ" steht fuer φ und B

Wenn man kein Klassiker ist, dann ist das letzte Beispiel nur ganz nett. Hier also ein anderes Beispiel, eines interessanteren Prolog Programms. Es setzt das Problem Eine Regular-Expression Engine von oben mehr oder weniger genau wie in der Angabe beschrieben um:

match([A|Rest], A, Rest) :-	%literal
    atom(A).
match(Str, (A/B), Rest) :-	%disjunction
    match(Str, A, Rest);
    match(Str, B, Rest).
match(Str, [], Str).		%concatenation
match(Str, [A|B], Rest) :-
    match(Str, A, Mid),
    match(Mid, B, Rest).
match(Str, *(_), Str).		%repetition
match(Str, *(A), Rest) :-
    match(Str, A, Mid),
    match(Mid, *(A), Rest).

match(Str, Re) :- match(Str, Re, []), !.

?- match([a], [a,*(b),(c/d/[])]).
true.

?- match([a,b], [a,*(b),(c/d/[])]).
true.

?- match([a,b,b,b], [a,*(b),(c/d/[])]).
true.

?- match([a,b,b,b,c], [a,*(b),(c/d/[])]).
true.

?- match([a,b,b,b,c,d], [a,*(b),(c/d/[])]).
false.

?- match(L, [a,*(b),(c/d/[])], []).
L = [a, c] ;
L = [a, d] ;
L = [a] ;
L = [a, b, c] ;
L = [a, b, d] ; ...

Der Kern eines Prolog Interpreters besteht aus den Mechanismen der Unifikation und Backtracking. Bei der Unifikation wird versucht mittels struktureller Gleichheit offene Variablen aufzulösen. Bei der Query

X = 2.

?- ancestor(X, zeus).
X = cronus ;
X = rhea ;
X = uranus ;
X = uranus ;
X = gaia ;
X = gaia.

Dass die Suche systematisch vorgeht hat zu heißen, dass wenn ein Komplexerer Ausdruck teilweise Unifiziert wurde, sich aber im späteren Verlauf herausstellt dass keine Gesamtlösung gefunden werden kann (bspw. X = chronus, in der Query ancestor(X, zeus), woman(X)), dann wird das System den Zustand der Unifikation so weit zurücksetzen, dass eine andere Lösung ausprobiert wird (bspw. X = rhea, was klappt) — in anderen Worten Tiefensuche!

Die Aufgabe besteht nun darin diesen Mechanismus grundsätzlich selbst zu implementieren. Genau wie auch zuvor, geht es in erster Instanz nicht um die Verarbeitung von echten Eingaben. Es sollte möglich sein eine Funktion

void prolog_query(struct term *query, struct prog *db);

struct term {
     enum {
	  VARIABLE, SYMBOL, FUNCTION,
     } type;
     union {
	  struct {
	       char *name;
	       struct term *val;
	  } variable;
	  struct {
	       char *name;
	  } symbol;
	  struct {
	       struct term *args;
	       unsigned n;
	  } function;
     } content;
};

struct clause {
     struct term *protasis;	/* wenn... */
     struct term *apodosis;	/* ...dann */
};

struct prog {
     struct clause **c;
     unsigned n;
};

Bonus: Echte Prolog Implementierungen basieren auf der so-genannten Warren Abstract Machine (WAM), einem Automaten Modell mit Primitiven für die Ausführung von Prolog-Programmen, vergleichbar mit Ladin's SECD Automaten für funktionale Programmierung. Mit Hilfe des Buchs Warren’s Abstract Machine, A Tutorial Reconstruction kann man sich in die Funktionsweise der Machine einlesen und selbst darüber nachdenken wie diese Methoden in deiner eigenen Implementierung genutzt werden können.

Ein Lisp-Übersetzer

Zuvor wurde vorgeschlagen einen Lisp Interpreter zu bauen, was der traditionelle Ansatz ist Lisp auszuführen, aber es ist bereits seit den 1960'ern' wurde Lisp zu Machinencode übersetzt. Interessant: In echten Lisp Systemen wie SBCL gehen sogar weiter und unterstützen incremental compilation, d.h. wo interpretierter und übersetzter Code interoperieren können.

Für diese Aufgabe, sollte es ausreichen einen einfachen Übersetzer ohne eine große Runtime zu schrieben, basierend auf dem Interpreter. Das ideale Ziel wäre es eine .lisp Datei in eine .s (Assembler) zu übersetzen, aber man kann auch ohne Parser direkt aus einem Fest-Kodiertem AST in der .c Datei übersetzen, und den Assembler auf der Standard Ausgabe ausgeben. Der Zielassembler ist wie immer egal, kann x86, RISC-V oder sein eigener sein. Schreibt man seinen AST direkt im Code, kann man auch mit dem TCC Compiler von Fabrice Bellard spielen, womit .c Programme direkt ausgeführt werden können.

Für den theoretischen Hintergrund kann ich es empfehlen sich den Artikel An Incremental Approach to Compiler Construction durchzulesen. Ghuloum beschreibt hier wie man Schritt für Schritt einen Komplexeren Übersetzer baut, welches größere und größere Fragmente der Sprache (in diesem Fall Scheme, einem Lisp Dialekt) umsetzt. Zusätzlich gibt es eine unvollendete Reihe von Artikeln welches sich dem gleichen Thema widmet. Das letzte Kapitel des Buchs The Structure and Interpretaion of Computer Programms (SICP) geht auch auf das Thema Compilation ein.

Allgemeine Bücher zu dem Thema sind Compilers: Principles, Techniques, and Tools (aka Drachenbuch) oder Modern Compiler Implementation in {Java,ML,C} (aka Tigerbuch).

Bonus: In der ersten Lisp Aufgabe wurde Dynamic Scoping beschrieben, d.h. dass das Binden einer Variable über den ganzen Aufrufsbaum sichtbar ist. Heutzutage (und seit 1936) ist Lexical Scoping, also Sichtbarkeit innerhalb eines Blocks aber nicht in der aufgerufenen Funktion. Versuchte den Compiler so zu schreiben, dass dieses richtige Closure unterstützt — was auch in Ghuloum, Abschnitt 3.9 beschrieben wird.

Eine Versions-Verwaltungs-System

Während Git heutzutage das populärste Versions-Verwaltungs-System ist, ist es nur eines von vielen, und keineswegs allgemein dominant. Mit Fossil hat man ein ganzes Projekt-Verwaltungs-System immer mit dabei und Mercurial (hg) hat einen interessanten Ansatz um Mengen von Revisionen auszudrücken.

Diese sind aber alle Verteile System, ohne einen zentralen Referenzpunkt. Zuvor haben Systeme wie CVS und Subversion zentralisierte Systeme umgesetzt, wo die meisten Operationen zugriff auf einen bestimmten Server gebraucht haben. Davor wiederum haben Systeme wie RCS (auf dem CVS basiert; als Beispiel: diese Seite ist mit RCS versioniert, siehe den $Id...$ ident-String unten) oder SCCS, welche die Versionierung von einzelnen, lokalen Dateien ermöglichten um Unix fehlen von Versionierten Datei Systemen zu umgehen — IMHO. Das letzte eignet sich gut als Übung:

Eine einfache Implementierung eines lokalen VCS muss in der Lage sein,

1. Selbstständig ein Repository erstellen (init)
2. Den Zustand einer Menge von Dateien zu speichern (commit)
3. Alte Versionen zu restaurieren (checkout)
4. Eine Liste von Versionen darstellen können (log)
5. Unterschiede zwischen Versionen Anzuzeigen (diff)

An diesen Punkten kann sich eine eigene Implementierung orientieren. Es ist nicht notwendig eine komplizierte oder effiziente Speicher-Struktur zu erfinden. Ein Vorschlag: Mann kann ein vorbestimmtes Verzeichnis wählen (.vc) und in diesem für jede Iteration den Inhalt des Verzeichnisses abspeichern (ohne das .vc-Verzeichnis). Die Verzeichnisse würden dann (alpha)numerisch aufsteigend sortiert die richtige Reihenfolge an Revisionen. Dann werden aus den obigen Punkten:

1. Erstellen eines .vc Verzeichnisses (siehe mkdir(2)) und Zustand initialisieren, bspw. eine Datei/Symlink welche auf die derzeit offene Revision verweist.
2. Erstellen eines Unterverzeichnisses in .vc und kopieren vom Inhalt.
3. Löschen des derzeitigen Checkouts (siehe unlink(2)), kopieren von einem Unterverzeichnis, und aktualisierung des internen Zustands in .vc.
4. Aufzählen von .vc-Unterverzeichnissen (siehe scandir(3))
5. Aufrufen eines Externen Prozesses wie diff auf zwei Verzeichnissen.

Diese können alle in einem Programm zusammen implementiert werden, in einzelnen ausführbaren Dateien mit oder ohne einer gemeinsamen Bibliothek.

Bonus: Speichere zusätzlich Nachrichten mit jeder Revision an, welche beim anzeigen von alten Revisionen dargestellt werden.

Bonus²: Um Speicherplatz zu sparen, kann man schauen ob zwischen zwei Revisionen der Datei-Inhalt sich nicht geändert hat, und dann Hard-Links erstellen, anstatt eine neue Datei zu benutzen.

Bonus³: Anstatt einen externen Prozess mit diff zu starten. Dazu kann man sich Eugene W. Myers's An O(ND) Difference Algorithm and Its Variations durchlesen. Aus dem Abstract:

The problems of finding a longest common subsequence of two sequences A and B and a shortest edit script for transforming A into B have long been known to be dual problems. In this paper, they are shown to be equivalent to finding a shortest/longest path in an edit graph. [...]

Einen Text-Editor

Ken Thompson hat der Legende nach UNIX™ in drei Wochen geschrieben gehabt, und in jeweils einer Woche einen Editor, einen Assembler und einen Kernel geschrieben (basierend auf früherer Arbeit). Einen Assembler haben wir ja bereits, der Kernel kommt noch, also fehlt ein Text Editor. Im Fall von Ken handelte es sich um den bereits erwähnten Zeileneditor Ed (wer es nicht kennt, die Bedienungsanleitung der GNU Implementierung von Ed bietet eine gute Einführung).

Es gibt und gab sehr viele Textbearbeitungsprogramme, von denen man sich inspirieren lassen kann. Der einfachste Ansatz ist es wahrscheinlich die Textfeld Implementierung eines bestehenden UI Toolkits als Basis zu verwenden, aber das selbstständige Implementieren eines Gap buffers, Piece tables oder Rope Datenstruktur wäre von didaktischem Interesse.

Entscheidet man sich für einen TUI editor, kann man herabsteigen in die wilde Welt von Terminal Emulatoren und derren Control Codes. Etwas Hilfe kann eine Bibliothek wie Ncurses verschaffen. Eine schöne Schritt-für-Schritt Einführung gibt die Build Your Own Text Editor Artikelserie. Das OpenBSD Projekt kommt mit zwei weitere, echte TUI Editoren welche zur Inspiration dienen können: vi (Portable) und mg (Portabel).

Bonus: Stelle sicher, dass der Editor UTF-8 Eingaben lesen kann. Sollte man das nicht alles selbst implementieren wollen, kann man sich die von Plan 9 inspirierete libutf Bibliothek anschauen.

Ein eigene Standard Bibliothek

Es ist eine interessante Diskussion, zu versuchen die Grenze zwischen einer Sprache und der Nicht-Sprache zu ziehen. Viele aber gewiss nicht alle Kritikpunkte an C wenden sich oft gegenüber den Funktionen der Standard-Bibliothek. Wenn man aber bedenkt, dass beim Übersetzen eines C Programms die Standard-Bibliothek ausgeschalten werden kann, ist es dann noch gerechtfertigt diese Kritik gegen C als ganzes zu richten? ^{Keine Ahnung.} In der Praxis ist auch oft zu sehen, dass viele Systeme eine eigene Standard-Bibliothek über C11/POSIX anbieten, teilweise um Portabilität über C hinaus umzusetzen, teilweise um häufige Operationen angenehmer zu machen.

Diese ist wieder eine Aufgabe der kreativen Eigeninitiative. Das Technische Problem ist es ein Programm richtig zu Bootstrappen, d.h. wenn Linux an das _start Symbol im Programmtext hinspringt, alles notwendige vorzubereiten (bspw. das einlesen von Befehlszeilen-Argumenten, aufsetzen von Standard-E/A, usw.) bevor die main-Funktion aufgerufen wird. Man sieht hier, dass man nicht mehr Portabel sein kann (außer man baut auf einer existierenden Standard-Bibliothek auf, aber wo ist da der Spaß?), also muss man bootstrapping Assembler schreiben. Man kann sich den LWN Artikel How programs get run hierzu anschauen.

Man ist bei dem gestalten der Schnittstelle gänzlich frei. Interessante Fragen sind unter anderem:

• Wie kann man eleganter mit Strings arbeiten?
• Welche Funktionalitäten wären hillfreich für Dateioperationen?
• Kann man die Speicherverwaltung robuster machen?

Siehe auch meine Sammlung von Standard Library Implementierungen.

Bonus: Implementiere eine Multithreading-Bibliothek analog zu pthread. Sich in Context switching einzulesen, kann hier helfen.

Ein Betriebsystem

Sollte die letzte Aufgabe implementiert haben dann hat man sich gut vorbereitet haben auf das Programmieren ohne Bibliotheken und Laufzeitumgebungen. vor allem die Bonusaufgabe mit Multithreading bearbeitet haben, folgt man den Fußstapfen von Linus Torvalds. Man hat sich bereits genug aufgewärmt, um ein kleines Beitreibsystem schreiben zu müssen. Bevor man zurückschreckt, sollte man sich daran erinnern, dass ein rudimentärer Kernel wesentlich weniger können muss, als Linux.

Bei der Betriebsystemprogrammierung kämpft man an zwei Fronten: Das erste ist die prinzipiellen Konzepte eines Betriebsystems zu verstehen (was eine CPU macht wenn diese gestartet wird, was Interrupts sind und wie man die handhabt, wie man seine Ressourcen initialisiert, wie man seine Ressourcen effizient Ausnutzt bspw. indem man es ermöglicht sich schlafen zu legen) aber auch die Architektur-Abhängigen Details (welche Register wie benutzt werden müssen, wie die Peripherie ansprechen muss und andere Details welche man auf OSDev.org nachlesen kann).

Es gibt zu dem Thema zahlreiche Einführungen und Bücher: Operating Systems: Three Easy Pieces, xv6: a simple, Unix-like teaching operating system, The little book about OS development.

Siehe auch meine Sammlung von Links zu allgemeinen Betriebsystem-Themen, oder besuche die Veranstaltung Betriebssysteme am i4.