Was ist ein Betriebssystem?

Der Begriff „Betriebssystem" wird in zwei verschiedenen Bedeutungen verwendet, die sorgfältig unterschieden werden müssen.

Das Betriebssystem im engeren Sinne stellt den Rahmen bereit, in dem alle Software-Komponenten mit der Hardware und untereinander interagieren können. Es sorgt dafür, dass Programme auf der Hardware laufen können, ohne sich gegenseitig unkontrolliert zu stören, und kapselt Hardwaredetails. Wenn von „Linux-Kernel" oder „Windows-Kernel" gesprochen wird, ist das Betriebssystem im engeren Sinne gemeint.

Das Betriebssystem im weiteren Sinne umfasst zusätzlich alle Werkzeuge, die man im Alltag als Teil des Systems wahrnimmt: Shell, Konfigurationsprogramme, Desktop-Oberfläche, Browser, Dateimanager. Eine Linux-Distribution ist ein typisches Beispiel. Der Trend geht dahin, immer mehr Funktionalität mit dem Betriebssystem auszuliefern.

Semesterübersicht der Themen

Einfache Datentypen und feste Integer-Typen

In C ist ein Typ nicht nur eine „Kategorie“, sondern bestimmt, wie viele Bytes gelesen oder geschrieben werden und wie diese Bytes interpretiert werden. Besonders bei Betriebssystem-APIs ist das wichtig, weil dort Dateigrößen, Offsets, Pufferlängen, Adressen und Rückgabewerte exakt passen müssen.

Typ-Aliase mit typedef

typedef erzeugt keinen neuen inkompatiblen Typ, sondern einen weiteren Namen für denselben Typ. Das ist nützlich, wenn lange Deklarationen lesbarer werden sollen, zum Beispiel bei structs oder Funktionspointern.

/* Alias für int: int_t und int sind derselbe Typ */
typedef int int_t;

int   a = 7;
int_t b = a;       // OK

typedef int *pint_t;

int value = 25;
pint_t p = &value;
*p = 30;

typedef int (*function_t)(pint_t);

int calculate(pint_t p);

function_t callback = calculate;
int y = callback(&value);

Adressen, Dereferenzierung und Pointer-Arithmetik

Eine Adresse allein sagt nur, wo im Speicher etwas liegt. Der Pointer-Typ sagt zusätzlich, wie der Speicher an dieser Adresse interpretiert wird. Bei T *p bedeutet *p: Lies oder schreibe ab Adresse p genau sizeof(T) Bytes als Wert vom Typ T.

sizeof, Arrays und Strings

sizeof liefert die Anzahl Maschinenbytes eines Objekts oder Typs. Im normalen Vorlesungskontext wird das als Compilezeit-Eigenschaft betrachtet. Für Puffer, Arrays und Dateiformate ist sizeof zentral, weil damit Größen robust berechnet werden können.

#include <stdint.h>
#include <stddef.h>

uint64_t u = 9;
size_t a = sizeof u;           // 8
size_t b = sizeof(uint64_t);   // 8

uint32_t values[10];
size_t bytes = sizeof values;                  // 10 × 4
size_t count = sizeof values / sizeof values[0];

Strings richtig vergleichen

C-Strings sind Arrays aus char, die mit '\0' enden. Ein Vergleich mit == vergleicht bei char * nur die Adressen, nicht den Inhalt der Zeichenketten.

char const *a = "OST";
char const *b = "OST";

if (a == b) {              // vergleicht Pointer-Adressen
    /* nicht als inhaltlicher Stringvergleich benutzen */
}

if (strcmp(a, b) == 0) {   // vergleicht Inhalte
    /* Strings sind gleich */
}

const bei Pointern lesen

Bei Pointer-Deklarationen ist entscheidend, ob das Zielobjekt konstant ist oder der Pointer selbst. Eine einfache Leseregel ist: von rechts nach links lesen.

struct, Padding und Alignment

Mit struct werden mehrere Werte zu einem zusammenhängenden Objekt gebündelt. Der Punktoperator . greift auf Member eines Objekts zu; der Pfeiloperator -> greift über einen Pointer auf Member zu.

typedef struct {
    int x;
    int y;
} point_t;

point_t p = { .x = 10, .y = 20 };
point_t *pp = &p;

p.x = 11;        // direkter Zugriff
pp->y = 21;      // gleichbedeutend mit (*pp).y = 21

Ein struct ist nicht immer genau so groß wie die Summe seiner sichtbaren Member. Compiler dürfen Padding-Bytes einfügen, damit Member an passenden Adressen liegen. Das nennt man Alignment.

Übung 1: Bilddaten in C

Die erste Übung verbindet die C-Wiederholung direkt mit einer Fallstudie: Bilder werden programmatisch erzeugt. Das BMP-Format wird bereitgestellt; im Fokus stehen gemeinsame Datenstrukturen, Pointer-Übergabe, Funktionspointer und Bitoperationen.

Aufgabe 1: gemeinsame Bildtypen in image.h

#include <stdint.h>

/* Ein Pixel: je 1 Byte für Rot, Grün, Blau */
typedef struct {
    uint8_t red;
    uint8_t green;
    uint8_t blue;
} rgb_t;

/* Ausschnitt eines späteren Fraktals */
typedef struct {
    double center_x;
    double center_y;
    double size;
} window_t;

/* Vorwärtsdeklaration, falls image_t erst später vollständig definiert wird */
typedef struct image image_t;

/* Dateiformat-spezifische open-Funktion, z. B. open_bmp_image */
typedef image_t *(*open_image_func_t)(char const *filename, uint32_t size);

Aufgabe 2: Farbverlauf erzeugen

Die Funktion paint_background läuft über alle Pixel des Bildes und setzt die Farbe über einen Funktionspointer in der image_t-Struktur. Dadurch werden struct-Pointer und der Operator -> praktisch verwendet.

#define SIZE 256

void paint_background(image_t *image) {
    for (uint32_t y = 0; y < SIZE; ++y) {
        for (uint32_t x = 0; x < SIZE; ++x) {
            uint8_t r = 255 - y;
            uint8_t g = x;
            uint8_t b = (x + y) / 2;

            rgb_t color = { r, g, b };
            image->set_pixel(image, x, y, color);
        }
    }
}

Aufgabe 3: Bilddaten mit Bitoperationen interpretieren

Die vorgegebenen Pixel sind platzsparend in 16-Bit-Werten codiert. Der oberste Bitbereich enthält die x-Koordinate, danach folgt die y-Koordinate, und die letzten zwei Bits bilden den Index in der Farbtabelle. Zusätzlich wird der Bildpunkt an der x-Achse gespiegelt, also auch bei SIZE - y - 1 gesetzt.

uint16_t value = pixel_data[i];

uint8_t x     = (value >> 8) & 0x7F;  // Bits 14..8, MSB ignoriert
uint8_t y     = (value >> 2) & 0x3F;  // Bits 7..2
uint8_t index =  value       & 0x03;  // Bits 1..0

rgb_t color = color_table[index];
image->set_pixel(image, x, y, color);
image->set_pixel(image, x, SIZE - y - 1, color);  // Spiegelung an der x-Achse

Empfohlene Bearbeitung der Übungen

Die Übungen sind bewusst praktisch. Der größte Lerneffekt entsteht nicht durch bloßes Lesen der Lösung, sondern durch eigenes Debugging und schrittweises Verstehen.

1. Zuerst selbst versuchen und Compiler-/Laufzeitfehler ernst nehmen.
2. Danach Hinweise oder Lösungsansätze mit Kolleginnen und Kollegen besprechen.
3. Erst dann die Musterlösung anschauen.
4. Die Lösung anschließend noch einmal selbstständig implementieren, bis sie ohne Copy-Paste verstanden ist.

API vs. ABI – die zwei Ebenen einer Schnittstelle

Bei Betriebssystemen werden häufig zwei Begriffe vermischt: API und ABI. Beide beschreiben Schnittstellen, aber auf unterschiedlichen Ebenen.

Was ist ein Systemaufruf?

Anwendungsprogramme laufen im User Space und haben keinen direkten Zugriff auf Hardware oder privilegierte Kernel-Strukturen. Um Dienste des Betriebssystems zu nutzen, muss eine Anwendung einen Systemaufruf (System Call) ausführen.

Technisch gibt es auf x86-64 einen einzigen syscall-Befehl. Da es viele verschiedene Kerneldienste gibt, muss jeder Dienst mit einem Code versehen werden, der in einem Register übergeben wird. Weitere Parameter folgen in anderen Registern.

Beispiel: Unter Linux/x86-64 hat der System Call exit die Nummer 60. Die Syscall-Nummer wird in rax/eax übergeben; der erste Parameter, also der Exit-Status, steht in rdi. Der Befehl syscall löst dann den kontrollierten Übergang in den Kernel aus. Diese Registerkonvention ist ABI- und architekturabhängig; portable Programme verwenden deshalb normalerweise C-/POSIX-Funktionen wie exit(), read() oder write() statt direkter Assembler-Systemaufrufe.

Privilege Levels, User-Mode und Kernel-Mode

Moderne Betriebssysteme stützen sich auf einen Hardwaremechanismus: Code läuft nicht immer mit denselben Rechten. Normale Anwendungen laufen im User-Mode; der Betriebssystemkern läuft im Kernel-Mode. Nur im Kernel-Mode dürfen privilegierte Instruktionen ausgeführt und geschützte Ressourcen direkt verwaltet werden.

Warum reichen Benutzerrechte wie root nicht?

Auch ein Prozess, der als root läuft, läuft zunächst im User-Mode. root beschreibt eine Berechtigung im Sicherheitsmodell des Betriebssystems; Kernel-Mode beschreibt dagegen einen CPU-Privilege-Level. Ein Root-Prozess darf mehr System Calls erfolgreich ausführen, darf aber trotzdem nicht beliebige Kernel-Instruktionen direkt ausführen.

Kernel-Architekturen: Microkernel, monolithischer Kernel, Unikernel

Die Vorlesung kontrastiert mehrere Architekturideen. Entscheidend ist jeweils, wie viel Funktionalität im privilegierten Kernel-Mode liegt und wie oft zwischen User-Mode und Kernel-Mode gewechselt werden muss.

Die Shell als Betriebssystem-Interface

Die Shell ist ein normales Programm, das es erlaubt, über Texteingabe Betriebssystemfunktionen aufzurufen. Sie benötigt keine besonderen Rechte, sondern nur einen Eingabe-Stream und einen Ausgabe-Stream. Es gibt viele Shell-Varianten mit jeweils eigener Syntax, zum Beispiel bash, zsh oder fish.

Beim Start eines Programms zerlegt die Shell die Eingabe in einzelne Argumente. Leerzeichen trennen Argumente; Quotes sorgen dafür, dass Leerzeichen Teil eines Arguments bleiben.

$ gcc -c abc.c
$ echo "ein Argument mit Leerzeichen"

POSIX

POSIX (Portable Operating System Interface) ist ein Standard, der viele Betriebssystemfunktionen spezifiziert. Die POSIX-API liegt sehr nah am Kernel und wird in C über standardisierte Bibliotheksfunktionen genutzt. Ein Großteil von BSYS 2 bewegt sich an dieser Schnittstelle. Für diesen Vorlesungsteil sind besonders wichtig: Shell-Verhalten, Programmargumente, Umgebungsvariablen, Man Pages und C-nahe API-Funktionen.

Programmargumente

Programmargumente sind explizite Informationen, die beim einzelnen Programmaufruf übergeben werden. Sie eignen sich für Dinge, die sich von Aufruf zu Aufruf ändern: Quellcodedateien, Optionen, Ausgabedateien, Modi oder Passwörter in Übungsaufgaben.

Shell-Zerlegung

Die Shell erzeugt aus einer Eingabe eine Folge von Strings. Für

$ gcc -c abc.c

entsteht konzeptionell:

Quotes verändern nicht den Inhalt des späteren Strings durch „magische Markierungen“, sondern nur die Zerlegung durch die Shell. Das Argument "ein Argument" landet im Programm als ein einziger nullterminierter String.

argc und argv in C

Die übliche Signatur der main-Funktion lautet:

int main(int argc, char *argv[])
{
    /* ... */
}

• argv[0] enthält normalerweise den Programmnamen bzw. den Namen, unter dem das Programm aufgerufen wurde.
• Die eigentlichen Argumente beginnen bei argv[1].
• Das letzte echte Argument liegt bei argv[argc - 1].
• argv[argc] ist ein Nullpointer und markiert das Ende des Arrays.

Argumente sicher durchsuchen

In Übung 2 wird ein Passwort-Argument gesucht. Zentral ist die Indexgrenze:

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
    for (int i = 1; i < argc; ++i) {
        if (strcmp(argv[i], "-Bsys2") == 0) {
            puts("Richtig");

            if (i + 1 < argc) {
                printf("Folgeargument: %s\n", argv[i + 1]);
            } else {
                puts("Fehler: Nach -Bsys2 folgt kein Argument.");
            }
            return 0;
        }
    }

    puts("Falsch");
    return 1;
}

Umgebungsvariablen

Umgebungsvariablen sind implizite Informationen, die ein Prozess beim Start erhält. Sie werden typischerweise vom Elternprozess, zum Beispiel der Shell, an den Kindprozess weitergegeben. Sie eignen sich für Einstellungen, die über viele Programmaufrufe hinweg gleich bleiben, etwa PATH, HOME oder projektspezifische Variablen.

Form eines Environment-Eintrags

Ein Environment-Eintrag ist ein nullterminierter String mit mindestens einem Gleichheitszeichen. Entscheidend ist das erste Gleichheitszeichen.

Speicherlayout mit environ

Das Environment liegt konzeptionell ähnlich wie argv im Speicher: ein Array aus Pointern auf nullterminierte Strings. Das Array endet mit einem Nullpointer.

getenv: Wert abfragen

#include <stdio.h>
#include <stdlib.h>

void print_value_of(char const *key)
{
    char *value = getenv(key);

    if (value == NULL) {
        printf("Environment variable '%s' does not exist.\n", key);
    } else {
        printf("Value of variable '%s' is: %s\n", key, value);
    }
}

setenv und unsetenv

#include <stdlib.h>

int setenv(char const *key, char const *value, int overwrite);
int unsetenv(char const *key);

setenv erhält Key und Value getrennt. Existiert der Key bereits, entscheidet overwrite, ob der alte Wert ersetzt wird.

Wichtig: Änderungen gelten nur für den aktuellen Prozess und für danach gestartete Kindprozesse. Bereits laufende Prozesse, insbesondere die Shell, werden dadurch nicht rückwirkend geändert.

putenv: vollständigen String einsetzen

#include <stdlib.h>

int putenv(char *string);  /* string hat Form KEY=VALUE */

Der subtile Unterschied: setenv kopiert Key und Value; putenv übernimmt den übergebenen String direkt in das Environment. Wird dieser String später verändert, ändert sich damit auch die Umgebungsvariable.

#include <stdio.h>
#include <stdlib.h>

char bsys_var[] = "BSYS_VAR=myvalue";

int main(void)
{
    putenv(bsys_var);
    puts(getenv("BSYS_VAR"));   /* myvalue */

    bsys_var[9] = '_';          /* Value-Teil wird verändert */
    bsys_var[10] = '_';

    puts(getenv("BSYS_VAR"));   /* __value */
}

environ direkt ausgeben

Für produktiven Code verwendet man normalerweise getenv, setenv und unsetenv. Für die Übung ist environ aber nützlich, um das Speicherlayout sichtbar zu machen.

#include <stdio.h>

extern char **environ;

void print_env(void)
{
    printf("&environ = %p\n", (void *)&environ);
    printf("environ  = %p\n", (void *)environ);

    for (char **p = environ; *p != NULL; ++p) {
        printf("&entry=%p entry=%p string=%s\n",
               (void *)p, (void *)*p, *p);
    }
}

Übung 2: Was muss die HTML-Zusammenfassung abdecken?

Die Übung zu dieser Vorlesung prüft genau die Verbindung aus Speicherlayout, POSIX-API und C-Programmierung. Für die Prüfungsvorbereitung sollten diese Punkte sicher sitzen:

Das Modul unterscheidet zwei Aspekte von Dateisystemen: die API (wie Anwendungen Dateien benutzen) und die Implementierung auf dem Datenträger (ext2, ext4 – siehe Kapitel 11 & 12). Anwendungen müssen in der Regel nichts über die interne Struktur wissen.

Grundbegriffe

Eine Datei besteht aus Nutzdaten und Metadaten. Metadaten umfassen Name, Größe, Zugriffsrechte, Zeitstempel u.a. Dateiendungen sind für das Betriebssystem meist nicht entscheidend; entscheidend sind Magic Numbers – spezifische Bytekombinationen am Anfang der Nutzdaten, die den Typ kennzeichnen (z.B. 7F 45 4C 46 = ELF).

Verzeichnisse bilden eine Hierarchie mit einem einzigen Wurzelverzeichnis (/ unter POSIX, C:\ unter Windows). Pfade können absolut (beginnen am Root), relativ (relativ zum Arbeitsverzeichnis) oder kanonisch (absolut, bereinigt von .. und Symlinks) sein.

Zugriffsrechte werden für drei Kategorien vergeben: Owner, Group und Other – jeweils mit read (r), write (w) und execute/search (x).

POSIX File API

Die POSIX-API arbeitet mit File-Deskriptoren – ganzzahligen Indices in die File-Descriptor-Tabelle des Prozesses. Drei Standard-Deskriptoren existieren von Beginn an: 0 (stdin), 1 (stdout), 2 (stderr).

Datei öffnen und schließen

/* Öffnen – gibt File-Deskriptor (≥ 0) oder -1 bei Fehler zurück */
int open(char const *path, int flags, ...);

/* Wichtige Flags: */
O_RDONLY    // nur lesen
O_WRONLY    // nur schreiben
O_RDWR      // lesen und schreiben
O_CREAT     // Datei anlegen falls nicht vorhanden (dann: mode-Arg nötig)
O_APPEND    // vor jedem Schreiben ans Ende springen
O_TRUNC     // Datei beim Öffnen auf Länge 0 setzen

/* Beispiel: */
int fd = open("myfile.dat", O_WRONLY | O_CREAT, S_IRWXU);

/* Schließen */
int close(int fd);

Lesen und Schreiben

ssize_t read(int fd, void *buffer, size_t n);
ssize_t write(int fd, void const *buffer, size_t n);

Positionierung im File

/* Offset setzen */
off_t lseek(int fd, off_t offset, int whence);
// whence: SEEK_SET (absolut), SEEK_CUR (relativ), SEEK_END (vom Ende)

/* Lesen/Schreiben mit explizitem Offset – Offset des FD bleibt unverändert */
ssize_t pread(int fd, void *buf, size_t n, off_t offset);
ssize_t pwrite(int fd, void const *buf, size_t n, off_t offset);

Fehlerbehandlung

Bei Fehler setzen POSIX-Funktionen die globale Variable errno. Zur Ausgabe einer Fehlermeldung:

#include <errno.h>
#include <string.h>
#include <stdio.h>

char *msg = strerror(errno);      // Fehlermeldung als String
perror("open");                    // "open: No such file or directory"

Vollständiges Beispiel: Datei kopieren

#define N 32
char buf[N];

int src = open(spath, O_RDONLY);
int dst = open(dpath, O_WRONLY | O_CREAT | O_TRUNC, S_IRWXU);

ssize_t n;
while ((n = read(src, buf, N)) > 0) {
    ssize_t written = 0;
    while (written < n) {                          // Schleife für partielle writes!
        ssize_t w = write(dst, buf + written, n - written);
        if (w < 0) { /* Fehlerbehandlung */ break; }
        written += w;
    }
}
if (n < 0) { /* Lesefehler behandeln */ }

close(src);
close(dst);

Windows-Vergleich

C-Stream-API

Die C-API (fopen, fread, fwrite, fprintf, …) liegt über der jeweiligen Betriebssystem-API und bietet eine weitgehend plattformunabhängige, gepufferte, zeichenorientierte Abstraktion. Sie ist portabler als direkte POSIX- oder Windows-Aufrufe, funktioniert aber nicht in allen Details identisch: Pfadsyntax, Text-/Binärmodus, Zeilenenden und Fehlerdetails können sich je nach Betriebssystem unterscheiden.

Prüfungsnahe Ergänzung: Dateisystem-API aus Folien, Transkript und Übung 3

Dieser Abschnitt ergänzt die bisherige Zusammenfassung um die praktischen Teile aus der Übung: Dateien vergleichen, kopieren und mit der C-Stream-API zeichenweise auswerten. Der Schwerpunkt liegt auf dem Zusammenhang zwischen den Vorlesungskonzepten File-Descriptor, Offset, Stream, Pufferung und Fehlerbehandlung.

Übung 3, Aufgabe 1: zwei Dateien mit POSIX vergleichen

Zwei Dateien sind genau dann gleich, wenn sie gleich lang sind und jedes Byte übereinstimmt. Die Übung arbeitet blockweise mit zwei Heap-Puffern von 4 KiB. Entscheidend ist nicht ein Dateiname oder eine Endung, sondern der tatsächliche Byteinhalt.

/* Kernidee von read_and_compare_one_block */
ssize_t n1 = read(fd1, buffer1, size);
ssize_t n2 = read(fd2, buffer2, size);

if (n1 < 0 || n2 < 0) {
    return -1;              /* echter Lesefehler */
}
if (n1 != n2) {
    return -1;              /* eine Datei ist länger/kürzer */
}
if (memcmp(buffer1, buffer2, (size_t)n1) != 0) {
    return -1;              /* gleicher Umfang, aber andere Bytes */
}
return n1;                  /* 0 bedeutet: beide gleichzeitig EOF */

Übung 3, Aufgabe 2: Datei mit POSIX kopieren

Das Kopieren ist der Vergleichsaufgabe ähnlich, verwendet aber nur einen Puffer: lesen aus der Quelle, schreiben in das Ziel. Prüfungsrelevant ist hier besonders, dass write weniger Bytes schreiben kann als angefordert. Robust ist deshalb eine kleine Hilfsfunktion, die weiterschreibt, bis der ganze Block geschrieben wurde.

ssize_t write_all(int fd, char const *buf, size_t n) {
    size_t written = 0;

    while (written < n) {
        ssize_t r = write(fd, buf + written, n - written);
        if (r < 0) {
            return -1;
        }
        written += (size_t)r;
    }

    return (ssize_t)written;
}

Damit wird die Kopierschleife konzeptionell sehr einfach:

while ((n = read(src_fd, buffer, buffer_size)) > 0) {
    if (write_all(dst_fd, buffer, (size_t)n) < 0) {
        /* Fehler behandeln */
        break;
    }
}

Übung 3, Aufgabe 3 und 4: C-API, Laufzeitvergleich und wc-ähnlicher Zähler

Mit der C-API ist das Kopierprogramm kürzer, weil die Bibliothek selbst puffert. Die Übung verwendet dafür die einfache Zeichen-Schleife mit fgetc und fputc. Bei sehr großen Dateien kann die POSIX-Variante mit großen Blöcken schneller wirken; auf modernen Systemen können beide Varianten durch Betriebssystem-Cache und libc-Pufferung aber ähnlich schnell sein.

int c;
while ((c = fgetc(in)) != EOF) {
    if (fputc(c, out) == EOF) {
        /* Schreibfehler behandeln */
        break;
    }
}

if (ferror(in)) {
    /* EOF war nicht die Ursache, sondern ein Lesefehler */
}

Der Wortzähler aus Aufgabe 4 lässt sich als einfacher Zustandautomat formulieren. Gezählt wird ein neues Wort genau dann, wenn ein Nicht-Whitespace-Zeichen gelesen wird, während man vorher „außerhalb eines Wortes“ war.

int in_word = 0;
size_t lines = 0;
size_t words = 0;

while ((c = fgetc(file)) != EOF) {
    if (c == '\n') {
        ++lines;
    }

    if (isspace((unsigned char)c)) {
        in_word = 0;
    } else if (!in_word) {
        ++words;
        in_word = 1;
    }
}

Ein Programm ist passiv – es ist eine Datei, die Instruktionen beschreibt. Ein Prozess ist aktiv – er ist eine laufende Instanz eines Programms mit eigenem Zustand, Adressraum und Betriebssystem-Ressourcen. Mehrere Prozesse können dasselbe Programm gleichzeitig ausführen, sind aber voneinander vollständig isoliert.

Process Control Block (PCB) & Kontextwechsel

Das Betriebssystem speichert alle Informationen eines Prozesses im Process Control Block (PCB). Dazu gehören:

• Registerinhalte (beim Unterbrechen gespeichert)
• Instruction Pointer
• Flags
• MMU-Konfiguration / Page-Table-Pointer
• Liste offener File-Deskriptoren
• Prozess-ID (PID) und Parent-Prozess-ID (PPID)

Bei einem Kontextwechsel speichert das Betriebssystem den Kontext von Prozess A im PCB von Prozess A und stellt den Kontext von Prozess B aus dem PCB von Prozess B wieder her. Für beide Prozesse wirkt es, als liefen sie ununterbrochen weiter.

Prozess-Hierarchie

Unter POSIX hat jeder Prozess außer Prozess 1 genau einen Parent-Prozess. Prozess 1 ist der erste Prozess des Systems (früher init, heute oft systemd). Daraus ergibt sich eine Baumstruktur – die Prozesshierarchie, sichtbar über pstree.

Prozess-APIs: fork, exec, exit, wait

fork – Prozess duplizieren

#include <unistd.h>
pid_t fork(void);

fork erzeugt eine Kopie des aktuellen Prozesses. Nach dem Aufruf laufen beide Prozesse ab der nächsten Instruktion weiter. Der Rückgabewert unterscheidet:

• Im Parent: PID des Child-Prozesses (> 0)
• Im Child: 0
• Bei Fehler: -1 (nur im Parent)

pid_t new_pid = fork();

if (new_pid > 0) {
    /* Parent-Code: new_pid ist die PID des Childs */
} else if (new_pid == 0) {
    /* Child-Code */
} else {
    /* Fehlerbehandlung: errno enthält den Grund */
}

Ist fork eine „exakte Kopie“?

Konzeptionell ja, identisch aber nein. Nach fork() existieren zwei Prozesse, die ab derselben Stelle weiterlaufen. Der Child erhält jedoch eine neue PID. Die PID ist also gerade nicht gleich. Auch der Rückgabewert von fork() ist unterschiedlich, damit Parent und Child verschiedene Codepfade ausführen können.

Die exec-Familie – Programmimage ersetzen

Mit exec wird das laufende Programmimage durch ein anderes ersetzt. Der Prozess bleibt derselbe (gleiche PID), führt aber danach ein neues Programm aus. Bei Erfolg kehrt exec nicht zurück.

exit – Prozess beenden

void exit(int code);   // kehrt nicht zurück

wait / waitpid – auf Child warten

pid_t wait(int *status);
pid_t waitpid(pid_t pid, int *status, int options);

wait blockiert bis irgendein Child endet; waitpid wartet auf ein bestimmtes Child. Der Status wird über Makros ausgewertet:

if (WIFEXITED(status)) {
    int code = WEXITSTATUS(status);  // eigentlicher Exit-Code
}

Parameter von waitpid: pid > 0 wartet auf genau diesen Child; pid == -1 entspricht wait (irgendein Child).

Typischer fork-exec-wait Ablauf

pid_t pid = fork();
if (pid == 0) {
    /* Child: anderes Programm laden */
    execvp("ls", argv);
    perror("exec failed");   // nur erreicht bei Fehler
    exit(1);
}
/* Parent wartet auf Child */
int status;
waitpid(pid, &status, 0);

Wie erzeugt man wirklich einen neuen Subprozess?

Ein neuer Subprozess entsteht typischerweise in zwei Schritten: Zuerst erzeugt fork() einen Child-Prozess. Danach ersetzt der Child mit exec... sein Programmimage durch das gewünschte Programm. Der Parent behält seine PID und kann mit waitpid() auf genau diesen Child warten.

char *args[] = { "ls", "-l", NULL };
pid_t pid = fork();

if (pid == 0) {
    /* Child: neues Programm starten */
    execvp(args[0], args);
    perror("execvp");  // nur bei Fehler erreicht
    _exit(127);       // im Child nach exec-Fehler lieber _exit
}

if (pid > 0) {
    int status;
    waitpid(pid, &status, 0);
}

Was passiert, wenn man close vergisst?

close(fd) entfernt genau einen File-Deskriptor aus der Deskriptor-Tabelle eines Prozesses. Das zugrunde liegende Kernel-Objekt verschwindet erst, wenn keine Deskriptor-Kopie mehr darauf zeigt. Nach fork() existieren diese Kopien oft in Parent und Child.

Zombie-Prozesse & Orphan-Prozesse

Was ist daran schlimm?

Der Loader

Der Loader ist die Komponente des Betriebssystems, die ein Executable und seine dynamischen Bibliotheken in den Hauptspeicher lädt. Er analysiert die Binärdatei, mappt Code- und Datensegmente in den Adressraum und stellt sicher, dass alle benötigten Symbole aufgelöst sind.

Der Loader lädt keine statischen Bibliotheken – diese wurden bereits zur Linkzeit eingebunden und sind unsichtbar. Unter Linux läuft der Ladevorgang über den Systemaufruf sys_execve, der eine Liste von Binary Handlers prüft. Der wichtigste Handler ist der ELF-Loader.

Das ELF-Format

ELF (Executable and Linking Format) ist das Standard-Binärformat unter Linux und anderen UNIX-artigen Systemen. Es beschreibt, wie ausführbarer Code, Daten und Metainformationen in einer Datei abgelegt sind.

Eine ELF-Datei beginnt mit einem ELF-Header, der Informationen über die Architektur, den Einstiegspunkt und die Lage der anderen Tabellen enthält. Es gibt zwei Sichten:

Bibliotheken: statisch vs. dynamisch

Statische Bibliotheken (.a)

Statische Bibliotheken sind Archive von Objektdateien (.o). Der Linker kopiert nur die benötigten Teile direkt in das erzeugte Executable. Das erzeugte Binary ist vollständig eigenständig, aber größer.

# Erzeugen einer statischen Bibliothek:
ar rcs libmylib.a module1.o module2.o

# Einbinden beim Linken:
gcc main.o -L. -lmylib -o programm

Dynamische Bibliotheken (.so)

Dynamische Bibliotheken werden zur Laufzeit vom Loader geladen. Mehrere Prozesse können denselben Code-Teil einer Bibliothek im Speicher teilen. Updates der Bibliothek wirken für alle Programme, ohne sie neu kompilieren zu müssen.

# Erzeugen einer dynamischen Bibliothek (PIC erforderlich):
gcc -shared -fPIC -o libmylib.so module1.o module2.o

# Einbinden beim Linken:
gcc main.o -L. -lmylib -o programm

Was passiert beim Bauen und Starten?

Prüfungsnahe Ergänzung: Toolchain, Linker und Loader

Dieser Abschnitt ergänzt die Folien- und Transkriptteile, die in der ursprünglichen Zusammenfassung nur knapp enthalten waren. Wichtig ist die Trennung zwischen Übersetzen, Linken und Laden: Der Compiler erzeugt aus einer Translation Unit Objektcode, der Linker verbindet Objektdateien und Bibliotheken, und der Loader bringt das fertige Programm beim Start in den virtuellen Adressraum.

Dynamisches Linken, GOT/PLT und die dl-API

Dynamisches Linken hat zwei Varianten: Bibliotheken können beim Programmstart automatisch geladen werden, oder ein Programm lädt Module explizit zur Laufzeit. Für die zweite Variante verwendet man unter POSIX/Linux die dl-API.

#include <dlfcn.h>

void *handle = dlopen("./plugin.so", RTLD_NOW);
if (!handle) { /* dlerror() ausgeben */ }

int (*plugin_fn)(int) = (int (*)(int)) dlsym(handle, "run");
if (!plugin_fn) { /* dlerror() ausgeben */ }

int result = plugin_fn(42);
dlclose(handle);

Übung 5: ELF-Dateien lesen und Section Header verstehen

Die Übung zu Programme & Bibliotheken prüft nicht nur Begriffe, sondern den Umgang mit echten Binärdaten. Man soll ELF-Header und Section Header dekodieren und daraus ableiten, wo Tabellen liegen, wie groß ein Eintrag ist und welche Sektionen ausführbaren Code enthalten.

typedef struct {
    uint32_t name_offset;
    uint32_t type;
    uint64_t flags;
    uint64_t offset;
    uint64_t size;
} section_header_t;

/* Schema der Übung:
   1. ELF-Header lesen.
   2. e_shoff/e_shentsize/e_shnum verwenden.
   3. Array für Section Header auf dem Heap anlegen.
   4. Section-String-Table über e_shstrndx finden.
   5. Namen und Typen ausgeben und mit readelf vergleichen. */

Motivation: Warum Threads?

Das Prozessmodell isoliert Prozesse vollständig. Das ist gut für Sicherheit und Stabilität, aber macht die Realisierung paralleler Abläufe innerhalb einer Anwendung aufwändig: Der Overhead für Prozesskopieren ist groß, gemeinsame Ressourcen sind schwer zu teilen.

Ein Thread ist ein eigenständiger Ausführungsstrang innerhalb eines Prozesses. Alle Threads eines Prozesses teilen:

• Denselben Adressraum (Heap, globale Variablen)
• Dieselben File-Deskriptoren
• Dieselben Signal-Handler

Jeder Thread hat jedoch einen eigenen: Stack, Instruction Pointer, Register-Zustand und Thread-ID.

Worker-Modell: Aufgabenqueue + mehrere Threads

Ein sehr häufiges Muster ist ein Worker Pool: Ein Hauptthread legt Arbeitspakete in eine Queue. Mehrere Worker-Threads holen sich jeweils das nächste Paket, bearbeiten es und schreiben das Ergebnis zurück. Wichtig ist, dass die Queue synchronisiert wird, z.B. mit Mutex und Condition Variable.

Konzeptionelles Zeitdiagramm

Die Ausführung überlappt sich: Drei Worker können drei unabhängige Jobs parallel bearbeiten. Trotzdem ist nicht alles automatisch schneller: Queue-Zugriffe, Ergebnislisten und gemeinsam genutzte Daten müssen geschützt werden, und zu viele Threads erzeugen Scheduling-Overhead.

while (running) {
    pthread_mutex_lock(&queue_mutex);
    while (queue_empty && running)
        pthread_cond_wait(&queue_not_empty, &queue_mutex);

    job = pop_job();
    pthread_mutex_unlock(&queue_mutex);

    process(job);  // lange Arbeit ohne Queue-Mutex
}

POSIX Threads (pthreads)

Thread erstellen

#include <pthread.h>

int pthread_create(
    pthread_t *thread_id,        // Out-Parameter: ID des neuen Threads
    pthread_attr_t const *attr,  // Attribute (NULL = Standard)
    void *(*start_function)(void *),  // Startfunktion
    void *argument               // Argument für Startfunktion
);
// Gibt 0 bei Erfolg zurück, sonst Fehlercode

/* Typische Startfunktion: */
void *thread_func(void *arg) {
    struct MyData *data = (struct MyData *)arg;
    /* ... */
    return NULL;
}

Thread-Lebenszyklus und wichtige Funktionen

/* Warten bis Thread beendet ist, Rückgabewert abholen: */
int pthread_join(pthread_t tid, void **return_value);

/* Thread selbst beenden: */
void pthread_exit(void *return_value);

/* Anderen Thread beenden anfordern (nicht für normalen Gebrauch): */
int pthread_cancel(pthread_t tid);

/* Ressourcen automatisch freigeben wenn Thread endet: */
int pthread_detach(pthread_t tid);

/* Eigene Thread-ID abfragen: */
pthread_t pthread_self(void);

Thread-Attribute

pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setstacksize(&attr, 1 << 16);   // 64 KB Stack
pthread_create(&tid, &attr, start_fn, arg);
pthread_attr_destroy(&attr);

Thread-Local Storage (TLS)

Mit dem Schlüsselwort _Thread_local (C11) oder __thread (GCC-Extension) kann eine globale Variable als thread-lokal deklariert werden. Jeder Thread bekommt dann eine eigene Kopie dieser Variable.

_Thread_local int per_thread_counter = 0;

Amdahls Regel: Warum Threads nicht beliebig skalieren

Threads erzeugen Parallelität innerhalb eines Prozesses, aber sie beschleunigen nur die Anteile eines Programms, die tatsächlich parallel ausgeführt werden können. Amdahls Regel beschreibt diese Grenze: Ein serieller Anteil bleibt seriell, egal wie viele Prozessoren vorhanden sind.

In der Übung besteht der Algorithmus aus fünf Teilen mit insgesamt 100 ms. Die nicht parallelisierbaren Teile dauern zusammen 50 ms. Damit ist der serielle Anteil \(s = \frac{50}{100} = \frac{1}{2}\).

Speicherlayout: Was Threads teilen und was nicht?

Das Transkript betont den Unterschied zu Prozessen: Threads sind keine isolierten Programme, sondern Ausführungsstränge im selben virtuellen Adressraum. Deshalb sehen sie denselben Code, dieselben globalen Variablen und denselben Heap, besitzen aber jeweils eigenen Stack und Registerzustand.

Thread Local Storage mit pthread_key_t

Die einfache Variante übergibt dem Thread direkt einen Pointer auf eine Parameterstruktur. Die Übung zeigt zusätzlich Thread Local Storage über die pthread-API. Das ist dann nützlich, wenn eine tief verschachtelte Funktionskette auf thread-spezifische Daten zugreifen muss, ohne dass jeder Funktionsaufruf die Parameter weiterreichen muss.

static pthread_key_t thread_local_data_key;

/* Im Master-Thread: Key anlegen, free als Destructor registrieren */
pthread_key_create(&thread_local_data_key, free);

void *run_calculation_thread(void *arg) {
    pthread_setspecific(thread_local_data_key, arg);
    unpack_and_calculate_julia();
    return NULL;
}

void unpack_and_calculate_julia(void) {
    thread_parameters_t *p = pthread_getspecific(thread_local_data_key);
    calculate_julia(p->image, p->window, p->exponent,
                    p->real, p->imaginary, p->iterations);
}

/* Am Ende des Programms */
pthread_key_delete(thread_local_data_key);

Übung 6: Prozesse, Argumente, Umgebungsvariablen und Threads verbinden

Die Übung verbindet die vorherigen Kapitel mit Threads. Zuerst wird der Fraktalgenerator mit getrennten Programmen umgesetzt: Der Master startet Worker-Prozesse und übergibt Parameter entweder als Programmargumente oder als Umgebungsvariablen. Danach wird dieselbe Fallstudie mit Threads umgesetzt, wodurch die Parameter direkt über Speicherpointer oder TLS übergeben werden können.

Scheduling löst das Problem, wie der Prozessor auf mehrere ausführungsbereite Threads aufgeteilt wird. Es kommt immer dann zum Einsatz, wenn mehr Threads laufen wollen als CPUs zur Verfügung stehen.

Thread-Zustände und Ready-Queue

Begriffe, die in Scheduling-Aufgaben oft vorausgesetzt werden

Durchgerechnetes Scheduling-Beispiel mit Diagrammen

Gegeben sind vier Jobs auf einer CPU. Alle Zeiten sind abstrakte Zeiteinheiten.

Für diese Tabelle gilt: kleinere Prioritätszahl = höhere Priorität.

FCFS: nicht präemptiv

SJF: nicht präemptiv

Bei Zeit 0 ist nur A vorhanden, deshalb läuft A zuerst vollständig. Danach wird jeweils der kürzeste verfügbare Job gewählt.

SRTF: präemptives SJF

SRTF (Shortest Remaining Time First) unterbricht den laufenden Job, wenn ein Job mit kürzerer Restlaufzeit ankommt.

Round Robin mit Zeitscheibe q = 3

Präemptives Priority Scheduling

Bei gleicher Priorität wird hier FCFS innerhalb derselben Priorität angenommen.

MLFQ-Idee als Diagramm

Wichtige Begriffe

Ein Prozessor-Burst ist der Zeitraum, in dem ein Thread Instruktionen ausführt (ohne Unterbrechung). I/O-lastige Threads haben viele kurze Bursts; CPU-lastige Threads haben wenige lange Bursts.

Präemptives Scheduling kann einem laufenden Thread den Prozessor entziehen. Kooperatives Scheduling wartet, bis der Thread den Prozessor freiwillig abgibt. Busy-Wait soll vermieden werden (verschwendet CPU-Zeit, verhindert Energiesparzustände).

First Come, First Served (FCFS)

Threads werden in der Reihenfolge ihres Eintreffens in der Ready-Queue abgearbeitet. FCFS ist nicht präemptiv: Ein Thread läuft, bis er blockiert oder endet.

Problem: Convoy-Effekt. Kurze Threads können sehr lange hinter einem langen Thread warten. FCFS ist für interaktive Systeme ungünstig.

Shortest Job First (SJF)

Wählt den Thread mit dem kürzesten nächsten Prozessor-Burst. SJF ergibt unter idealen Bedingungen optimale durchschnittliche Wartezeit. Kann kooperativ oder präemptiv (= Shortest Remaining Time First, SRTF) eingesetzt werden.

Round-Robin Scheduling (RR)

Präemptive Variante von FCFS mit einer festen Zeitscheibe (Time Slice), typischerweise 10 bis 100 ms. Ein Thread darf laufen, bis:

• er fertig ist,
• er blockiert (wartet), oder
• seine Zeitscheibe erschöpft ist → er wird hinten in die Ready-Queue eingereiht.

Prioritätsbasiertes Scheduling

Jeder Thread erhält eine Priorität. Threads mit höherer Priorität laufen vor Threads mit niedrigerer Priorität. Threads gleicher Priorität werden nach FCFS behandelt. SJF ist ein Spezialfall: kurzer Burst = hohe Priorität.

Multi-Level Feedback Queue (MLFQ)

MLFQ verwendet mehrere Ready-Queues mit unterschiedlichen Prioritäten und Zeitscheiben. Höhere Queues haben kleinere Zeitscheiben. Erschöpft ein Thread seine Zeitscheibe, sinkt seine Priorität (er wandert in eine niedrigere Queue mit größerer Zeitscheibe). Threads, die freiwillig warten, bleiben in ihrer Queue.

Effekt: Threads mit kurzen Bursts (interaktive Threads) bleiben automatisch in hohen Queues mit schneller Reaktionszeit; CPU-intensive Threads wandern in niedrige Queues.

Scheduling-Vergleich

POSIX Scheduling-APIs

/* Nice-Wert (Linux): beeinflusst statische Priorität */
int nice(int increment);
int getpriority(int which, id_t who);
int setpriority(int which, id_t who, int prio);

Race Conditions und Critical Sections

Sobald mehrere Threads denselben Speicher lesen und schreiben, können Race Conditions entstehen: Das Ergebnis hängt von der konkreten Ausführungsreihenfolge der Instruktionen ab und ist nicht reproduzierbar.

Warum ++counter nicht atomar ist: Auf Maschinenebene besteht die Operation typischerweise aus drei Schritten. Ein Kontextwechsel zwischen diesen Schritten erzeugt einen Race:

t0: Thread A liest counter in rax   → rax_A = 5
t1: Thread A erhöht rax             → rax_A = 6
t2: Thread B liest counter in rax   → rax_B = 5  ← liest alten Wert!
t3: Thread B erniedrigt rax         → rax_B = 4
t4: Thread A schreibt zurück        → counter = 6
t5: Thread B schreibt zurück        → counter = 4  ← Update von A verloren!

Eine Critical Section ist ein Codebereich, in dem auf gemeinsamen Zustand zugegriffen wird. Alle Threads, die auf dieselben geteilten Daten zugreifen, müssen ihre Critical Sections koordinieren.

Anforderungen an Synchronisationsmechanismen

Jeder Synchronisationsmechanismus muss drei Eigenschaften erfüllen:

1. Gegenseitiger Ausschluss (Mutual Exclusion): Immer nur ein Thread in der Critical Section
2. Fortschritt: Wenn keine Critical Section belegt ist, muss in endlicher Zeit entschieden werden, wer eintreten darf
3. Begrenztes Warten: Kein Thread darf beliebig oft übergangen werden

Semaphore

Ein Semaphor ist ein nichtnegativer Zähler mit zwei atomaren Operationen:

• wait (P, down): Wenn Zähler > 0, verringern und fortfahren; sonst blockieren
• post (V, up): Zähler erhöhen; wartende Threads wecken

Semaphore eignen sich besonders für Producer-Consumer-Probleme, um freie und belegte Pufferplätze zu zählen:

#include <semaphore.h>

sem_t free_slots, filled_slots;
sem_init(&free_slots, 0, BUFFER_SIZE);  // BUFFER_SIZE freie Plätze
sem_init(&filled_slots, 0, 0);           // 0 befüllte Plätze

/* Producer: */
sem_wait(&free_slots);   // freien Platz belegen
buffer[w] = item;
sem_post(&filled_slots); // befüllten Platz signalisieren

/* Consumer: */
sem_wait(&filled_slots); // auf befüllten Platz warten
item = buffer[r];
sem_post(&free_slots);   // Platz freigeben

Producer-Consumer-Problem ausführlich

Das Producer-Consumer-Problem ist eines der wichtigsten Standardprobleme der Nebenläufigkeit. Ein oder mehrere Producer erzeugen Datenpakete, ein oder mehrere Consumer verarbeiten sie. Weil beide Seiten unterschiedlich schnell sein können, liegt dazwischen ein begrenzter Puffer, häufig als Ringpuffer.

Ringpuffer: Schreibindex w und Leseindex r

Ein Ringpuffer ist ein Array fester Größe. w zeigt auf die nächste Schreibposition, r auf die nächste Leseposition. Nach dem letzten Feld springt der Index mit Modulo-Rechnung wieder auf den Anfang:

Naive Lösung: Busy-Waiting

Eine einfache Lösung prüft ständig, ob der Puffer voll oder leer ist. Das funktioniert konzeptionell, ist aber ineffizient, weil ein wartender Thread weiter CPU-Zeit verbraucht.

/* Producer: wartet aktiv, falls der Puffer voll ist */
while (next_w == r) { }       // Busy-Wait: CPU wird weiter belastet
buffer[w] = item;
w = (w + 1) % BUFFER_SIZE;

/* Consumer: wartet aktiv, falls der Puffer leer ist */
while (r == w) { }            // Busy-Wait
item = buffer[r];
r = (r + 1) % BUFFER_SIZE;

Versuch mit counter: scheinbar besser, aber Race Condition

Ein zusätzlicher Zähler counter scheint das Problem zu lösen: counter == 0 bedeutet leer, counter == BUFFER_SIZE bedeutet voll. Der kritische Punkt ist aber: ++counter und --counter sind in C nicht automatisch atomar.

Das verlorene Update zeigt: Ein gemeinsamer Zähler muss synchronisiert werden. Ohne Schutz entsteht ein Data Race, und das Ergebnis hängt vom zufälligen Timing der Kontextwechsel ab.

Korrekte Standardlösung: zwei Semaphore + ein Mutex

Die robuste Lösung trennt zwei Aufgaben:

• free_slots zählt freie Pufferplätze. Startwert: BUFFER_SIZE.
• used_slots zählt belegte Pufferplätze. Startwert: 0.
• Ein mutex schützt den eigentlichen Ringpuffer und die Indizes w und r.

#include <pthread.h>
#include <semaphore.h>

#define BUFFER_SIZE 16
item buffer[BUFFER_SIZE];
int w = 0;  // nächste Schreibposition
int r = 0;  // nächste Leseposition

sem_t free_slots;   // freie Plätze
sem_t used_slots;   // belegte Plätze
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void init(void) {
    sem_init(&free_slots, 0, BUFFER_SIZE);
    sem_init(&used_slots, 0, 0);
}

void *producer(void *arg) {
    while (1) {
        item x = produce_item();

        sem_wait(&free_slots);          // blockiert, wenn Puffer voll
        pthread_mutex_lock(&mutex);     // exklusiver Zugriff auf Ringpuffer

        buffer[w] = x;
        w = (w + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&used_slots);          // ein belegter Platz mehr
    }
}

void *consumer(void *arg) {
    while (1) {
        sem_wait(&used_slots);          // blockiert, wenn Puffer leer
        pthread_mutex_lock(&mutex);     // exklusiver Zugriff auf Ringpuffer

        item x = buffer[r];
        r = (r + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&free_slots);          // ein freier Platz mehr

        consume_item(x);
    }
}

Warum zwei Semaphore und nicht nur ein Mutex?

Kleines Rechenbeispiel mit BUFFER_SIZE = 4

Wichtig: Die Semaphorwerte beschreiben nicht direkt die Indexpositionen, sondern die Anzahl freier bzw. belegter Plätze. Die Modulo-Rechnung bewegt nur w und r im Kreis.

Zeitdiagramm: schneller Producer, langsamer Consumer

Wenn der Producer schneller ist, füllt er den Puffer. Sobald free_slots == 0 ist, blockiert er in sem_wait(&free_slots). Erst wenn der Consumer ein Element entnimmt und sem_post(&free_slots) ausführt, kann der Producer weiterlaufen.

Typische Fehler in Producer-Consumer-Lösungen

Alternative mit Message Passing / Rendezvous

Bei blockierendem Senden und blockierendem Empfangen entsteht ein Rendezvous: Der Producer wartet beim Senden, bis ein Consumer empfangen kann, und der Consumer wartet, bis eine Nachricht verfügbar ist. Dadurch wird Producer-Consumer ohne gemeinsamen Speicher lösbar.

/* Producer über Message Queue Q */
while (1) {
    message msg = produce_next();
    send(Q, &msg);       // blockiert ggf., wenn Queue voll oder Rendezvous nötig
}

/* Consumer über Message Queue Q */
while (1) {
    message msg;
    receive(Q, &msg);    // blockiert, bis Nachricht vorhanden ist
    consume_next(&msg);
}

Merksatz für die Prüfung: Semaphoren zählen Zustände („freie Plätze“, „belegte Plätze“), Mutexe schützen gemeinsame Daten („Puffer, Indizes, Counter“). Beides zusammen ergibt die klassische Lösung für den begrenzten Producer-Consumer-Puffer.

Mutexe

Ein Mutex (Mutual Exclusion Lock) ist der einfachste Mechanismus zum Schutz einer Critical Section. Er hat genau zwei Zustände: frei und belegt. Ein Mutex kann als binärer Semaphor implementiert werden.

POSIX Mutex API

#include <pthread.h>

pthread_mutex_t mutex;

/* Initialisieren (attr=NULL für Standard-Attribute): */
pthread_mutex_init(&mutex, NULL);

/* Sperren (blockiert bis verfügbar): */
pthread_mutex_lock(&mutex);

/* Sperren nicht-blockierend (EBUSY wenn belegt): */
pthread_mutex_trylock(&mutex);

/* Entsperren: */
pthread_mutex_unlock(&mutex);

/* Aufräumen: */
pthread_mutex_destroy(&mutex);

Verwendungspattern

void *thread_function(void *args) {
    while (running) {
        /* Nichtkritische Arbeit */

        pthread_mutex_lock(&mutex);
        ++counter;                 /* Critical Section */
        pthread_mutex_unlock(&mutex);

        /* Weitere nichtkritische Arbeit */
    }
    return NULL;
}

Mutex-Attribute (POSIX)

Über pthread_mutexattr_t können konfiguriert werden:

• pshared: Prozessübergreifende Nutzung (Standard: nur innerhalb eines Prozesses)
• Typ: z.B. rekursiv (erlaubt mehrfaches Lock durch denselben Thread)
• Priority Inheritance: Aktiviert Priority-Inheritance (s.u.)
• Priority Ceiling: Feste Mindestpriorität während Lock gehalten wird

Priority Inversion & Priority Inheritance

Priority Inversion

Szenario mit drei Threads (Low A, Mid B, High C), Mutex M:

1. Thread A (low) hält Mutex M
2. Thread C (high) benötigt Mutex M → muss warten
3. Thread B (mid) wird ready → verdrängt Thread A
4. Thread B läuft, obwohl Thread C (high) wartet – effektive Prioritäten sind invertiert!

Priority Inheritance (Lösung)

Wenn Thread C auf Mutex M wartet, erhält Thread A vorübergehend die Priorität von C. A kann den Mutex schnell freigeben, C kann weiterlaufen. Nach Freigabe verliert A die geerbte Priorität wieder.

Signale

Signale sind ein einfacher Mechanismus, um einen Prozess von außen zu unterbrechen. Ein Signal transportiert nur eine Nummer – keine Nutzdaten. Das Verhalten ähnelt einem Interrupt: Das Betriebssystem unterbricht den Prozess, führt den Signal-Handler aus und setzt den Prozess fort (sofern der Handler ihn nicht beendet).

Signal-Handler

Jeder Prozess hat für jedes Signal einen Handler. Beim Start setzt das Betriebssystem Standard-Handler in drei Kategorien:

• Ignore: Signal wird ignoriert
• Terminate: Programm wird normal beendet
• Abnormal Terminate: Programm wird beendet + Core Dump erzeugt

Wichtige Signale

Signal-Handler ändern mit sigaction

struct sigaction sa = {0};
sa.sa_handler = my_handler;          // Handler-Funktion
sigemptyset(&sa.sa_mask);           // Keine weiteren Signale blockieren

sigaction(SIGTERM, &sa, NULL);

/* Handler-Funktion: */
void my_handler(int sig) {
    running = 0;   // z.B. sauberes Beenden signalisieren
}

Signale aus C senden

raise(SIGABRT);              // an eigenen Prozess
kill(pid, SIGTERM);          // an anderen Prozess
pthread_kill(tid, SIGUSR1);  // an bestimmten Thread

Pipes und Named Pipes (FIFOs)

Eine Pipe ist ein unidirektionaler Byte-Strom zwischen Prozessen. Man kann sie sich wie ein Förderband im Kernel vorstellen: Ein Prozess schreibt Bytes am write end hinein, ein anderer Prozess liest dieselben Bytes am read end wieder heraus. Die Reihenfolge ist FIFO: Was zuerst geschrieben wurde, wird zuerst gelesen.

Das Konzept: read end, write end und Kernel-Puffer

pipe(fd) erzeugt zwei File-Deskriptoren im aktuellen Prozess:

Was passiert bei pipe() und fork()?

Eine anonyme Pipe wird meistens vor einem fork() erzeugt. Danach besitzen Parent und Child zunächst beide Pipe-Enden, weil fork() die File-Deskriptor-Tabelle kopiert. Die Deskriptor-Nummern sind dann in beiden Prozessen gleich, zeigen aber auf dasselbe Pipe-Objekt im Kernel.

Warum close() bei Pipes so wichtig ist

Bei Pipes entscheidet der Kernel anhand der noch offenen Enden, ob ein Prozess blockieren soll, EOF sieht oder ein Fehler entsteht. Deshalb reicht es nicht, nur im richtigen Prozess zu lesen oder zu schreiben: Die nicht benötigten Enden müssen wirklich mit close() geschlossen werden.

Minimaler Ablauf: Child schreibt, Parent liest

Das folgende Muster ist der Standardfall. Wichtig ist nicht nur read und write, sondern vor allem das frühe Schließen des jeweils falschen Endes.

int fd[2];
if (pipe(fd) == -1) { /* Fehler behandeln */ }
// fd[0] = read end, fd[1] = write end

pid_t pid = fork();
if (pid == 0) {                  /* Child: produziert Daten */
    close(fd[0]);                 // Child liest nicht
    write(fd[1], "Hallo
", 6);
    close(fd[1]);                 // EOF für Leser ermöglichen
    _exit(0);
} else {                            /* Parent: konsumiert Daten */
    close(fd[1]);                 // Parent schreibt nicht
    while ((n = read(fd[0], buf, sizeof buf)) > 0) {
        /* n gelesene Bytes verarbeiten */
    }
    close(fd[0]);
    waitpid(pid, NULL, 0);
}

Shell-Pipes: was bei cmdA | cmdB konzeptionell passiert

Eine Shell-Pipe ist keine Magie und auch keine temporäre Datei. Die Shell baut intern eine Pipe, startet zwei Prozesse und verdrahtet deren Standard-Streams mit dup2(). Danach ersetzt exec() die Child-Prozesse durch die eigentlichen Programme.

/* stark vereinfacht: linkes Kommando */
dup2(fd[1], STDOUT_FILENO);  // stdout von cmdA → write end
close(fd[0]);
close(fd[1]);
execlp("cmdA", "cmdA", NULL);

/* stark vereinfacht: rechtes Kommando */
dup2(fd[0], STDIN_FILENO);   // stdin von cmdB ← read end
close(fd[0]);
close(fd[1]);
execlp("cmdB", "cmdB", NULL);

Named Pipes / FIFOs

Eine Named Pipe oder FIFO funktioniert konzeptionell wie eine Pipe, besitzt aber einen Namen im Dateisystem. Dieser Name ist nur ein Treffpunkt: Die Daten werden nicht dauerhaft in dieser Datei gespeichert, sondern weiterhin durch einen Pipe-Puffer im Kernel transportiert.

mkfifo("/tmp/myfifo", S_IRUSR | S_IWUSR);

/* Prozess A: Schreiber */
int out = open("/tmp/myfifo", O_WRONLY);
write(out, msg, len);
close(out);

/* Prozess B: Leser */
int in = open("/tmp/myfifo", O_RDONLY);
read(in, buf, sizeof buf);
close(in);

/* Name im Dateisystem entfernen */
unlink("/tmp/myfifo");

Prüfungsmerksätze zu Pipes

• Pipe = Kernel-Puffer + zwei Deskriptoren, nicht normale Datei.
• fd[0] liest, fd[1] schreibt.
• Nach fork() haben Parent und Child zunächst beide Enden.
• Nicht benötigte Enden sofort schließen, sonst fehlen EOF/SIGPIPE und Programme können hängen.
• Shell-Pipes entstehen durch pipe(), fork(), dup2(), close() und exec().
• Named Pipes haben einen Pfad, speichern Daten aber nicht dauerhaft als Dateiinhalt.

Berkeley Sockets

Sockets sind File-Deskriptoren für Netzwerkkommunikation. Sie sind häufig bidirektional und unterstützen verschiedene Protokolle (TCP, UDP, Unix-Domain-Sockets).

Socket erzeugen

int socket(int domain, int type, int protocol);
// Typisch: */
socket(AF_INET, SOCK_STREAM, 0);   // IPv4 + TCP
socket(AF_INET, SOCK_DGRAM, 0);    // IPv4 + UDP
socket(AF_UNIX, SOCK_STREAM, 0);   // Unix-Domain-Socket

IPv4-Adresse angeben

struct sockaddr_in addr = {0};
addr.sin_family = AF_INET;
addr.sin_port = htons(8080);         // Host→Network Byte Order (Short)
inet_pton(AF_INET, "192.168.1.1", &addr.sin_addr.s_addr);

Server-Ablauf

int srv = socket(AF_INET, SOCK_STREAM, 0);
bind(srv, (struct sockaddr*)&addr, sizeof(addr));
listen(srv, 10);               // Warteschlange einrichten (nicht akzeptieren!)

while (running) {
    int client = accept(srv, NULL, NULL);  // neuer Socket pro Client
    /* lesen/schreiben auf client, dann close(client) */
}

Client-Ablauf

int sock = socket(AF_INET, SOCK_STREAM, 0);
connect(sock, (struct sockaddr*)&srv_addr, sizeof(srv_addr));
send(sock, buf, len, 0);    // entspricht write(sock, buf, len)
recv(sock, buf, len, 0);    // entspricht read(sock, buf, len)
close(sock);

Moderne Betriebssysteme isolieren Prozesse vollständig. Für Interprozesskommunikation (IPC) gibt es zwei grundlegende Paradigmen: Message Passing (Daten werden kopiert) und Shared Memory (gemeinsamer Speicher).

POSIX Message Queues

Message Queues sind systemweite, benannte Warteschlangen. Nachrichten haben eine Priorität; höher priorisierte Nachrichten werden zuerst zugestellt.

#include <mqueue.h>

/* Queue öffnen/erzeugen: */
mqd_t mq = mq_open("/meine_queue", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR, NULL);

/* Senden (blockiert wenn voll, außer O_NONBLOCK): */
mq_send(mq, msg, strlen(msg), 0);  // Priorität 0

/* Empfangen (blockiert wenn leer): */
mq_receive(mq, buf, sizeof(buf), &priority);
// buf muss mind. mq_msgsize groß sein!

/* Schließen und entfernen: */
mq_close(mq);
mq_unlink("/meine_queue");   // Name entfernen; offene Handles bleiben!

mq_attr – Queue-Konfiguration

struct mq_attr {
    long mq_flags;    // 0 oder O_NONBLOCK
    long mq_maxmsg;   // max. Anzahl Nachrichten in der Queue
    long mq_msgsize;  // max. Nachrichtengröße in Bytes
    long mq_curmsgs;  // aktuelle Anzahl Nachrichten
};

POSIX Shared Memory

Bei Shared Memory werden virtuelle Pages verschiedener Prozesse auf denselben physischen Frame gemappt. Änderungen eines Prozesses sind sofort für alle anderen sichtbar.

#include <sys/mman.h>

/* Shared Memory erzeugen/öffnen: */
int fd = shm_open("/myshm", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);

/* Größe festlegen: */
ftruncate(fd, sizeof(struct MyData));

/* In Adressraum einblenden: */
struct MyData *shm = mmap(NULL, sizeof(struct MyData),
    PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

close(fd);     // fd kann nach mmap geschlossen werden

/* Verwenden: */
shm->value = 42;

/* Aufräumen: */
munmap(shm, sizeof(struct MyData));
shm_unlink("/myshm");

Vergleich: Message Passing vs. Shared Memory

Zeichenkodierungen: ASCII, Codepages, Unicode

ASCII

ASCII (American Standard Code for Information Interchange) ist ein 7-Bit-Encoding mit 128 Zeichen (00h–7Fh). Es enthält 33 Kontrollzeichen, Ziffern, Interpunktion und lateinische Buchstaben. Die Tabelle ist so gestaltet, dass einfache Operationen möglich sind: Ziffer minus 30h = numerischer Wert; Groß/Kleinschreibung durch ein Bit umschaltbar.

Codepages

Da ASCII nur 128 Zeichen kennt, entstanden regionale 8-Bit-Erweiterungen. Das achte Bit erlaubt 128 zusätzliche Zeichen (80h–FFh). Das Problem: Die Erweiterungen sind inkompatibel. ISO 8859-1 (Westeuropa) und ISO 8859-5 (Kyrillisch) belegen E4h mit verschiedenen Zeichen. Ein Programm kann anhand der Bytes allein nicht erkennen, welche Codepage gemeint ist.

Unicode

Unicode weist jedem Zeichen eine eindeutige Nummer zu – den Code Point (CP). Der mögliche Bereich umfasst etwa 1'112'064 Code Points. Unicode 16.0 (Sept. 2024) definiert 154'998 Zeichen. Der Bereich D800h–DFFFh ist reserviert (nicht als Code Points nutzbar).

Wie ein Code Point als Bytes gespeichert wird, bestimmt das Encoding. Die Speichereinheit heißt Code Unit (CU).

Unicode-Encodings im Detail

UTF-32

32-Bit-Code-Units. Jeder Code Point entspricht genau einer Code Unit. Einfach, aber speicherintensiv. Endianness muss beachtet werden (UTF-32BE, UTF-32LE).

UTF-32 und Endianness genau gerechnet

UTF-32 ist konzeptionell einfach: Jeder Unicode-Code-Point wird als 32-Bit-Zahl gespeichert. Die Frage ist nur, in welcher Byte-Reihenfolge diese 32-Bit-Zahl im Speicher liegt.

/* 32-Bit-Codepoint x in Bytes zerlegen */
be[0] = (x >> 24) & 0xff;  be[1] = (x >> 16) & 0xff;
be[2] = (x >>  8) & 0xff;  be[3] =  x        & 0xff;

le[0] =  x        & 0xff;  le[1] = (x >>  8) & 0xff;
le[2] = (x >> 16) & 0xff;  le[3] = (x >> 24) & 0xff;

UTF-8

8-Bit-Code-Units (= Bytes). Kein Endianness-Problem. Rückwärtskompatibel mit ASCII. De-facto-Standard im Web (~90% aller Webseiten).

Das erste Byte gibt die Anzahl der Bytes an; Fortsetzungsbytes beginnen immer mit 10.

Berechnungsbeispiele

ä (U+00E4) in UTF-8: E4h = 1110 0100. Passt in 11 Bits → 2 Bytes.
110 00011 | 10 100100 = C3 A4

ặ (U+1EB7) in UTF-8: 1EB7h = 0001 1110 1011 0111. Benötigt 3 Bytes.
Nutzbits gruppieren: 0001 | 111010 | 110111
UTF-8-Bytes: 1110 0001 | 10 111010 | 10 110111 = E1 BA B7

UTF-16

16-Bit-Code-Units. Für Code Points ≤ FFFFh (außer D800h–DFFFh): direkte Darstellung. Für Code Points > FFFFh: Surrogate Pairs aus zwei Code Units.

Berechnung eines Surrogate Pairs für Code Point P ≥ 10000h:

Beispiel: Gotisch 𐌰 (U+10330)

Das ext2-Dateisystem

Geschichte der ext-Familie

Grundbegriffe

Ein Sektor ist die kleinste Übertragungseinheit der Hardware (traditionell 512 Byte, heute oft 4 KB). Ein Block besteht aus aufeinanderfolgenden Sektoren. In ext2 sind Blöcke typischerweise 1 KB, 2 KB oder 4 KB groß. Blöcke sind die zentrale Allokationseinheit.

Blockgruppen

Das gesamte Volume wird in Blockgruppen aufgeteilt. Jede Blockgruppe hat dieselbe Struktur:

Superblock

Der Superblock enthält alle zentralen Metadaten des Volumes und beginnt immer an Byte 1024 (wegen eventueller Bootdaten am Anfang). Seine Blocknummer hängt von der Blockgröße ab:

Inhalt des Superblocks u.a.: Anzahl freier/gesamter Inodes und Blöcke, Bytes pro Block und Inode, Blöcke und Inodes pro Gruppe, Zeitstempel, Statusbytes, Feature-Flags.

Sparse Superblocks

Ohne Sparse Superblocks enthält jede Blockgruppe eine Kopie von Superblock und Deskriptortabelle. Mit Sparse Superblocks nur in: Blockgruppe 0, Blockgruppe 1 und Gruppen, deren Nummer eine reine Potenz von 3, 5 oder 7 ist:

Gruppendeskriptor (32 Byte)

Beschreibt eine Blockgruppe: Blocknummer der Block-Bitmap, Blocknummer der Inode-Bitmap, Startnummer der Inode-Tabelle, Anzahl freier Blöcke und Inodes, Anzahl Verzeichnisse in der Gruppe.

Inodes

Jede Datei und jedes Verzeichnis wird durch einen Inode beschrieben. Der Inode enthält Metadaten (Dateityp, Größe, Rechte, Zeitstempel, Link-Zähler) und Verweise auf Datenblöcke. Der Name der Datei steht nicht im Inode, sondern im Verzeichniseintrag.

Inodes sind durchnummeriert (ab 1). Die Lokalisierung eines Inodes aus seiner Nummer:

Beispiel: Bei Inode 12345 und 8192 Inodes pro Gruppe gilt:

Blockverweis-Schema im Inode

Ein Inode enthält 15 Blockverweise (32-Bit-Nummern). Bei Blockgröße 4 KB (1024 Einträge pro Block):

• Verweise 0–11: direkt (12 Blöcke = 48 KB bei 4-KB-Blöcken)
• Verweis 12: einfach indirekter Block (enthält 1024 Blocknummern → Blöcke 12–1035)
• Verweis 13: doppelt indirekter Block (1024 × 1024 Blöcke)
• Verweis 14: dreifach indirekter Block (1024 × 1024 × 1024 Blöcke)

Verzeichnisse

Ein Verzeichnis ist ebenfalls ein Inode; seine Datenblöcke enthalten Dateieinträge variabler Länge (8–263 Byte):

• 4 Byte: Inode-Nummer
• 2 Byte: Länge des Eintrags (auf 4 Byte ausgerichtet)
• 1 Byte: Länge des Dateinamens
• 1 Byte: Dateityp (normal, Verzeichnis, Symlink, Device, …)
• 0–255 Byte: Dateiname (kein Null-Terminator)

Jedes Verzeichnis enthält automatisch . (eigener Inode) und .. (Elternverzeichnis-Inode). Das Wurzelverzeichnis hat immer Inode-Nummer 2.

Hardlinks und Symlinks

ext2-Rechenaufgaben: Vorgehen und Beispiele

1) Blockgröße aus dem Superblock

In ext2 wird die Blockgröße nicht direkt als 1024/2048/4096 gespeichert, sondern über einen Logarithmuswert.

2) Maximale Blöcke pro Blockgruppe

Die Block-Usage-Bitmap einer Blockgruppe belegt einen Block. Jedes Bit beschreibt einen Block. Deshalb gilt:

3) Gruppendeskriptortabelle berechnen

Ein ext2-Gruppendeskriptor ist 32 Byte groß.

Beispiel: 1 GiB Dateisystem, Blockgröße 4 KiB.

4) Inode-Position genau berechnen

Gegeben: Inode 12345, 8192 Inodes pro Gruppe, Inodegröße 256 Byte, Blockgröße 4096 Byte.

Wenn die Inode-Tabelle der Blockgruppe bei Block T beginnt, liegt der gesuchte Inode also in Block T + 259, 2048 Byte nach Blockanfang.

5) Maximale Dateigröße über direkte/indirekte Blockverweise

Bei ext2 enthält ein Inode 12 direkte Verweise sowie je einen einfach, doppelt und dreifach indirekten Verweis. Wenn ein Blockverweis 4 Byte groß ist, passen in einen indirekten Block:

6) Verzeichniseintrag ausrechnen

Ein ext2-Verzeichniseintrag hat 8 Byte Fixanteil plus den Dateinamen und wird auf 4 Byte aufgerundet.

File-Holes und Sparse Files

Ein File-Hole ist ein logisch existierender Bereich, der nur Nullbytes enthält. In ext2 kann ein Blockverweis-Eintrag auf 0 stehen – das bedeutet, der Block ist nicht alloziert. Beim Lesen liefert das Betriebssystem Nullbytes. Sparse Files nutzen dies: Ihre logische Größe kann die Größe des belegten Speichers übertreffen, in Extremfällen sogar die Größe des gesamten Volumes.

Ergänzung Übungen: Unicode-Codierungen und ext2-Reader

Dieser Abschnitt ergänzt Kapitel 11 um die Teile, die in der Übung besonders wichtig sind: konkrete Unicode-Umrechnungen und der praktische Zugriff auf ein ext2-Disk-Image. Damit werden die Konzepte aus Folien und Transkript nicht nur erklärt, sondern auch als Rechen- und Implementationsschema sichtbar.

Unicode: Code Point → Code Units → Bytes

Beispiel: U+20AC EURO SIGN

U+20AC = 0010 0000 1010 1100
UTF-8-Muster für 3 Bytes:
1110xxxx 10xxxxxx 10xxxxxx

Gruppieren der Nutzbits:
0010 | 000010 | 101100

Einsetzen:
1110 0010   1000 0010   1010 1100
E2          82          AC

UTF-16-Surrogate knapp erklärt

Für Code Points oberhalb von U+FFFF reicht eine 16-Bit-Code-Unit nicht aus. Deshalb wird zuerst 0x10000 abgezogen. Die verbleibenden 20 Bits werden in zwei 10-Bit-Teile zerlegt: High Ten Bits und Low Ten Bits.

Die Byte-Reihenfolge der beiden 16-Bit-Code-Units hängt anschließend von Little Endian oder Big Endian ab. Das ist genau der Punkt, an dem sich die Konzepte Encoding und Endianess berühren.

ext2-Reader: vom Pfad zum Datenblock

Die ext2-Übung verwendet ein Disk-Image als Rohdatei. Anstatt über fopen oder normale Dateipfade des Host-Systems zu gehen, liest das Programm die ext2-Strukturen selbst. Die POSIX-Funktion pread ist dabei nur der Ersatz für eine echte blockbasierte Gerätelesefunktion.

/* ext2_read_block: ein globaler Block im Disk-Image */
ssize_t ext2_read_block(ext2_t *fs, uint32_t global_block_id, void *buffer) {
    off_t offset = (off_t)global_block_id * (off_t)fs->blocksize;
    return pread(fs->fd, buffer, fs->blocksize, offset);
}

/* direkter Teil der Blockabbildung */
uint32_t ext2_map_local_to_global_block_id(ext2_inode_t const *inode,
                                           uint32_t local_block_id) {
    if (local_block_id < 12) {
        return inode->i_block[local_block_id];
    }

    /* einfache, doppelte und dreifache Indirektion wären die Erweiterung */
    return 0;
}

ext4 (2008) erweitert ext2/ext3 um wesentliche Funktionen für Robustheit und Leistung. Es ist rückwärtskompatibel mit ext2/ext3-Features.

Journaling

Ohne Journaling kann ein Systemabsturz während eines Schreibvorgangs das Dateisystem in einem inkonsistenten Zustand hinterlassen. Journaling schreibt Änderungen zuerst in ein spezielles Journal (Write-Ahead-Log). Nach einem Absturz kann das Dateisystem das Journal durchgehen und angefangene Transaktionen entweder vollständig ausführen oder rückgängig machen.

Extents (Extent Trees)

ext2 verwendet für jeden Block einen einzelnen 32-Bit-Verweis (direkt/indirekt). Bei großen Dateien mit zusammenhängenden Blöcken ist das ineffizient: 1000 aufeinanderfolgende Blöcke benötigen 1000 einzelne Einträge.

ext4 verwendet stattdessen Extents: Ein Extent beschreibt einen zusammenhängenden Bereich als Tripel (erster logischer Block, erster physischer Block, Länge). Der Inode enthält einen Extent Tree mit bis zu 4 Einträgen direkt im Inode; für größere Dateien wird der Baum über zusätzliche Blöcke erweitert.

Extent Tree: Notation

• Blattknoten (Extent): (1. logischer Block, 1. physischer Block, Anzahl Blöcke)
• Indexknoten: (Blocknummer der Kinder, kleinste log. Blocknummer aller Kinder)
• Header: (Anzahl Einträge, Tiefe)

Beispiel: 4 MiB, alle Blöcke konsekutiv ab 1000h (4-KiB-Blöcke)

4 MiB = 2²² Byte = 1024 Blöcke = 400h Blöcke. Weil die Blöcke direkt hintereinander liegen, reicht ein einziger Extent:

Inode Extent Array:
  [0] = (1, 0)           ← Header: 1 Eintrag, Tiefe 0 (Blattknoten direkt)
  [1] = (0, 1000h, 400h) ← Extent: log. Block 0 → phys. Block 1000h, 400h Blöcke

Zum Vergleich benötigt die direkte/indirekte Adressierung von ext2 für dieselbe Datei: 12 direkte Datenblockverweise und zusätzlich einen einfach indirekten Block. Dieser indirekte Block könnte 400h Einträge speichern; tatsächlich genutzt werden hier aber nur 400h − 0Ch = 3F4h Einträge, weil die ersten 12 Datenblöcke bereits direkt im Inode adressiert werden.

ext4-Rechenbeispiele: Extents und Journal

1) Extent für konsekutive Blöcke

Gegeben: Datei mit 10 MiB, Blockgröße 4 KiB, physisch zusammenhängend ab Block 0x20000.

Im Vergleich zu ext2 müssten 2560 einzelne Datenblocknummern adressiert werden. ext4 beschreibt den gesamten zusammenhängenden Bereich mit einem einzigen Eintrag.

2) Fragmentierte Datei in mehrere Extents zerlegen

Man erzeugt immer dann einen neuen Extent, wenn die physische Fortsetzung nicht mehr direkt an den vorherigen physischen Block anschließt.

3) Kapazität eines Extent-Blocks abschätzen

Ein Extent-Header ist 12 Byte groß; ein Extent- oder Indexeintrag ebenfalls 12 Byte. Bei 4-KiB-Blöcken passen daher ungefähr:

Der Inode selbst hat im Feld i_block Platz für Header plus bis zu vier Extent-Einträge. Erst bei mehr Fragmenten oder größeren Bäumen werden zusätzliche Extent-Blöcke benötigt.

4) Journal-Ablauf bei Metadatenänderung

Weitere ext4-Features

• 64-Bit-Blocknummern: Unterstützung für sehr große Volumes
• Flexible Blockgruppen: Metadaten mehrerer Gruppen können zusammengefasst werden
• Delayed Allocation: Speicherzuweisung wird verzögert, um Fragmentierung zu reduzieren
• Checksummen: Für Metadaten und Journal
• Größere Inodes: Platz für erweiterte Attribute
• Multiblock-Allokation: Mehrere Blöcke auf einmal allozieren

Ergänzung Übung 12: direkte/indirekte Adressierung vs. Extent Trees

Dieser Abschnitt ergänzt die ext4-Zusammenfassung um die konkreten Rechenmuster aus Übung 12. Ziel ist, dass man eine Datei sowohl im klassischen ext2-Schema mit direkten/indirekten Blocknummern als auch im ext4-Schema mit Extent Trees darstellen kann.

Notation aus der Übung

Fall A: 4 KiB-Datei ab Block 1000h

ext2 direkt:
  0 → 1000h

ext4 Extent Tree:
  0 → (1, 0)              Header: 1 Eintrag, Tiefe 0
  1 → (0, 1000h, 1)       ein Extent für genau einen Block

Fall B: 4 MiB, vollständig zusammenhängend ab 1000h

4 MiB bei 4-KiB-Blöcken sind 400h Datenblöcke. Bei ext2 werden die ersten 0Ch Blöcke direkt im Inode adressiert, der Rest liegt in einem einfach indirekten Block. Bei ext4 reicht ein einziger Extent.

ext2:
  Datenblöcke: 1000h … 13FFh
  0  → 1000h
  1  → 1001h
  …
  Bh → 100Bh
  Ch → 1400h               indirekter Block
  1400h.0    → 100Ch
  1400h.1    → 100Dh
  …
  1400h.3F3h → 13FFh

ext4:
  0 → (1, 0)               Header
  1 → (0, 1000h, 400h)    ein Extent beschreibt alle 400h Blöcke

Fall C: 4 MiB in vier zusammenhängenden 1-MiB-Bereichen

Jeder Bereich umfasst 100h Blöcke. Für ext4 passen genau vier Extents direkt in den Inode, weil dort nach dem Header noch vier 12-Byte-Einträge Platz haben.

Physische Bereiche:
  [1000h, 10FFh], [2000h, 20FFh], [3000h, 30FFh], [4000h, 40FFh]

ext2:
  0  → 1000h
  …
  Bh → 100Bh
  Ch → 1100h               indirekter Block, kleinste freie Metablocknummer > 1000h
  1100h.000h → 100Ch
  …
  1100h.0F3h → 10FFh
  1100h.0F4h → 2000h
  …
  1100h.3F3h → 40FFh

ext4:
  0 → (4, 0)               Header: 4 Extents, Tiefe 0
  1 → (0,    1000h, 100h)
  2 → (100h, 2000h, 100h)
  3 → (200h, 3000h, 100h)
  4 → (300h, 4000h, 100h)

Fall D: 4 MiB in 128-KiB-Bereichen

128 KiB entsprechen 20h Blöcken. Für 4 MiB braucht man also 20h Extents. Diese passen nicht mehr direkt in den Inode, weil dort nur vier Extents neben dem Header Platz haben. Deshalb wird im Inode ein Indexeintrag auf einen separaten Extent-Block verwendet.

ext2:
  Daten in 20h Paketen à 20h Blöcken:
  [1000h, 101Fh], [2000h, 201Fh], …, [2'0000h, 2'001Fh]

  0  → 1000h
  …
  Bh → 100Bh
  Ch → 1020h               indirekter Block
  1020h.0    → 100Ch
  …
  1020h.13h  → 101Fh
  1020h.14h  → 2000h
  …
  1020h.3F3h → 2'001Fh

ext4:
  0        → (1, 1)        Header im Inode: 1 Eintrag, Tiefe 1
  1        → (1020h, 0)    Indexknoten: Kinderblock 1020h, kleinster log. Block 0
  1020h.0  → (20h, 0)      Header im Extent-Block: 20h Extents, Tiefe 0
  1020h.1  → (0,    1000h, 20h)
  1020h.2  → (20h, 2000h, 20h)
  …
  1020h.20h → (3E0h, 2'0000h, 20h)

Rezept zum Lösen solcher Aufgaben

1. Dateigröße in Anzahl Datenblöcke umrechnen.
2. Physische Blockbereiche als Intervalle notieren, statt alle Blöcke auszuschreiben.
3. Für ext2: zuerst 12 direkte Einträge füllen, danach benötigte Metadatenblöcke an der kleinsten freien Blocknummer allozieren.
4. Für ext4: jedes physisch zusammenhängende Intervall wird ein Extent.
5. Wenn höchstens vier Extents entstehen, bleiben sie direkt im Inode. Bei mehr als vier Extents wird ein Indexeintrag und ein zusätzlicher Extent-Block benötigt.

Ziele und Grundidee

Das X Window System stellt unter Unix/Linux die klassische Basisinfrastruktur für grafische Oberflächen bereit. Es zeichnet nicht einfach „die ganze GUI“ selbst, sondern trennt mehrere Rollen: Anwendungen wollen Fenster und Inhalte darstellen, der X-Server steuert Display, Tastatur und Maus, und ein Window Manager verwaltet Platzierung, Dekoration und Verhalten der Fenster.

• GUI-Grundbegriffe: Fenster, Events, Mauszeiger, Fokus, Window Manager und Desktop.
• X-Architektur: Client/Server-Modell, X Protocol, Xlib, X-Ressourcen und Netzwerktransparenz.
• Programmierung: Display öffnen, Fenster erzeugen, Events selektieren, Event Loop schreiben, zeichnen und Fenster sauber schließen.

GUI-Basiskonzepte: programm- vs. ereignisgesteuert

Textorientierte Programme folgen oft einem programmgesteuerten Ablauf: Das Programm gibt etwas aus, wartet auf Eingabe und entscheidet dann, was als Nächstes passiert. GUIs funktionieren dagegen ereignisgesteuert: Das Programm wartet auf Ereignisse wie Mausklicks, Tastendrücke, Größenänderungen oder Neuzeichnen-Anforderungen und reagiert darauf.

Fenster, Maus und Window Manager

Ein Fenster ist im X-Konzept ein rechteckiger Bereich des Bildschirms. Fenster bilden eine Baumstruktur: Das Root Window ist die Wurzel und bedeckt den ganzen Screen. Top-Level-Windows von Anwendungen sind Kinder des Root Windows; Menüs, Buttons oder andere GUI-Elemente können weitere Kindfenster sein. Kindfenster werden auf den Bereich ihres Elternfensters begrenzt (clipping to the parent).

X-Architektur: Client, Server, Protokoll und Xlib

Die Begriffe sind bei X zunächst ungewohnt: Der X-Server läuft auf dem Rechner, an dem Display, Tastatur und Maus hängen. Der X-Client ist die Anwendung, die etwas anzeigen oder Events empfangen will. Dadurch können Clients lokal oder auf einem entfernten Rechner laufen. Diese Trennung ermöglicht Netzwerktransparenz.

Minimaler Xlib-Ablauf

#include <X11/Xlib.h>

Display *display = XOpenDisplay(NULL);      /* DISPLAY-Variable verwenden */
int screen = DefaultScreen(display);
Window root = RootWindow(display, screen);

Window window = XCreateSimpleWindow(
    display, root,
    50, 50,          /* x, y */
    400, 250,        /* width, height */
    1,               /* border width */
    BlackPixel(display, screen),
    WhitePixel(display, screen)
);

XSelectInput(display, window, ExposureMask | ButtonPressMask);
XMapWindow(display, window);                /* macht Fenster sichtbar */

X Protocol, Pufferung und Ressourcen

Das X Protocol definiert Nachrichten zwischen Client und Server. Es gibt vier wichtige Typen: Requests vom Client an den Server, Replies als Antworten, Events als spontane Meldungen vom Server an den Client und Errors als Fehlermeldungen. Requests werden clientseitig gepuffert, um Netzwerkverkehr zu reduzieren. Der Puffer wird zum Beispiel geleert, wenn ein Reply nötig ist, wenn der Client auf Events wartet oder wenn explizit XFlush() aufgerufen wird.

Event Handling

Ein X-Client erhält nicht automatisch alle Events. Er muss pro Fenster mit XSelectInput() festlegen, welche Ereignistypen ihn interessieren. Ohne Auswahl ist die Event-Maske leer. Eine wichtige Ausnahme sind ClientMessage-Events, die immer zugestellt werden können.

XEvent event;

while (!application->done) {
    XNextEvent(application->display, &event);

    switch (event.type) {
    case Expose:
        handle_expose_event(application, &event.xexpose);
        break;
    case ButtonPress:
        handle_button_press_event(application, &event.xbutton);
        break;
    case ClientMessage:
        handle_client_message_event(application, &event.xclient);
        break;
    }
}

Zeichnen: Pixmap, Colormap, Graphics Context

X zeichnet mit einfachen Grafikprimitiven in ein Ziel: entweder direkt in ein Fenster oder in eine Pixmap. Für fast alle Zeichenoperationen wird ein Graphics Context benötigt. Er enthält Eigenschaften wie Vordergrundfarbe, Hintergrundfarbe, Liniendicke und Füllmuster.

GC gc = XCreateGC(display, window, 0, NULL);

XDrawRectangle(display, window, gc, 20, 20, 260, 120);
XDrawString(display, window, gc, 40, 80,
            "Hallo X Welt", 12);

XFreeGC(display, gc);

Fenster schließen: Window Manager, Atoms und WM_DELETE_WINDOW

Der Schließen-Knopf gehört nicht zur eigentlichen Anwendung, sondern wird vom Window Manager bereitgestellt. X selbst weiß nicht automatisch, dass dieser Knopf „Programm beenden“ bedeuten soll. Deshalb gibt es ein Protokoll zwischen Window Manager und Client: Der Client registriert sich für WM_DELETE_WINDOW; beim Klick auf den Schließen-Knopf erhält er ein ClientMessage-Event.

Atom delete_atom = XInternAtom(display, "WM_DELETE_WINDOW", False);
XSetWMProtocols(display, window, &delete_atom, 1);

/* im Event-Handler */
if (event->type == ClientMessage &&
    (Atom)event->xclient.data.l[0] == delete_atom) {
    application->done = 1;
}

Übung 13: Was du aus dem Code verstehen musst

Die Übung vertieft die Xlib-Konzepte an einem kleinen C-Programm. Das Programm erzeugt ein Fenster mit schwarzem Rahmen auf weißem Grund, verarbeitet Events und wird anschließend um Textausgabe, Window-ID und Mausklick-Zähler erweitert.

Prüfungsschema für das Übungsprogramm

struct Application {
    Display *display;       /* Verbindung zum X-Server */
    Window window;          /* ID der serverseitigen Window-Ressource */
    GC gc;                  /* ID des Graphics Context */
    Atom delete_atom;       /* Atom für WM_DELETE_WINDOW */
    int done;               /* Abbruchbedingung der Event Loop */
    int counter;            /* Übungserweiterung: Mausklicks zählen */
};

/* Reihenfolge */
new_Application();          /* alloziert + initialisiert X-Ressourcen */
execute();                  /* XNextEvent + dispatch_event */
delete_Application();       /* gibt Ressourcen frei */

Kurzvergleich: X11 und Wayland-Kontext

In den Materialien wird Wayland nur kurz als Ersatz für das X Protocol genannt. Für diese Zusammenfassung genügt daher der Kontext: X11 trennt X-Server, X-Clients, Window Manager und Protokoll sehr stark und erlaubt Netzwerktransparenz. Moderne Systeme verwenden häufig Wayland-basierte Compositoren, aber die hochgeladenen Folien und Übungen prüfen vor allem das Verständnis der X11-Architektur und der Xlib-Programmierung.