Verkehrssimulation mit Threads und Semaphoren in C

Einführung in die Verkehrssimulation mit Threads

In diesem Tutorial lernst du, wie du das Traffic-Problem aus der ADS103-Aufgabe mit C-Threads löst. Du wirst Mutexe, Bedingungsvariablen und Semaphoren einsetzen, um eine faire und effiziente Verkehrssteuerung zu implementieren. Das Besondere: Du analysierst die Fairness der Warteschlangen und vergleichst die Implementierungen. Aktuelle Beispiele aus der Spieleentwicklung (z.B. Minecraft-Server mit vielen Spielern) oder Cloud-Computing (z.B. PrairieLearn) zeigen, wie wichtig solche Konzepte sind.

Grundlagen: Threads und Synchronisation

Ein Thread ist ein leichter Prozess, der parallel arbeiten kann. In der Simulation repräsentiert jeder Thread ein Auto, das versucht, in eine Straße einzufahren. Dabei müssen zwei Bedingungen eingehalten werden:

Es dürfen sich nie mehr als drei Autos gleichzeitig in der Straße befinden.
Autos aus entgegengesetzten Richtungen (Ost und West) dürfen sich nicht gleichzeitig in der Straße befinden.

Diese Einschränkungen erfordern eine sorgfältige Synchronisation. Du wirst Mutexe verwenden, um den Zugriff auf gemeinsame Daten zu schützen, und Bedingungsvariablen, um Threads auf ein Ereignis warten zu lassen – vergleichbar mit einer Ampel, die Autos passieren lässt, wenn die Straße frei ist.

Implementierung mit Mutexen und Bedingungsvariablen

Beginne mit der Datei traffic.c. Erstelle N Threads (z.B. N=20) und weise jedem eine zufällige Richtung zu. Jeder Thread durchläuft eine Schleife, in der er versucht, in die Straße einzufahren. Während er in der Straße ist, ruft er uthread_yield() N-mal auf, um andere Threads zu simulieren. Danach verlässt er die Straße und ruft erneut uthread_yield() N-mal auf, bevor er den nächsten Versuch startet.

// Pseudocode für einen Thread
void* car(void* arg) {
    for (int i = 0; i < ITERATIONS; i++) {
        mutex_lock(&lock);
        while (street_full() || opposite_direction()) {
            cond_wait(&cond, &lock);
        }
        enter_street();
        mutex_unlock(&lock);
        
        // In der Straße
        for (int j = 0; j < N; j++) uthread_yield();
        
        mutex_lock(&lock);
        leave_street();
        cond_signal(&cond);
        mutex_unlock(&lock);
        
        for (int j = 0; j < N; j++) uthread_yield();
    }
    return NULL;
}

Wichtig: Du musst die Belegungszähler mit assert überprüfen und die Wartezeiten in einem Histogramm festhalten. Das Histogramm zeigt, wie oft ein Thread eine bestimmte Anzahl von Wartezyklen erlebt hat. Ein Overflow-Bucket erfasst Wartezeiten, die den vordefinierten Bereich überschreiten.

Semaphor-Implementierung: Ein fairerer Ansatz?

Kopiere deine Lösung nach traffic_sem.c und ersetze alle Mutexe und Bedingungsvariablen durch Semaphoren. Ein Semaphor ist ein Zähler, der von Threads atomar erhöht oder verringert werden kann. Hier verwendest du ein binäres Semaphor als Mutex und ein zählendes Semaphor zur Steuerung der Straßenkapazität.

// Semaphor-Initialisierung
sem_init(&mutex, 0, 1);         // Binäres Semaphor als Mutex
sem_init(&capacity, 0, 3);      // Maximal 3 Autos in der Straße
sem_init(&direction_lock, 0, 1); // Nur eine Richtung gleichzeitig

Der wesentliche Unterschied: Bei Semaphoren gibt es keine FIFO-Warteschlange wie bei Bedingungsvariablen. Wenn ein Thread sem_post aufruft, wird ein wartender Thread geweckt – aber es kann passieren, dass ein anderer, nicht wartender Thread das Semaphor vor dem geweckten Thread erhält. Dieses Rennen führt zu Unfairness. In der Praxis siehst du, dass einige Threads deutlich länger warten als andere – ähnlich wie bei einem Online-Spiel, bei dem manche Spieler wegen Netzwerklatenz benachteiligt werden.

Fairness-Analyse: Warum Semaphoren unfair sein können

In der Bedingungsvariablen-Implementierung werden wartende Threads in einer FIFO-Warteschlange gespeichert. Wenn ein Thread signalisiert wird, wird der älteste wartende Thread geweckt. Allerdings kann ein neu ankommender Thread, der noch nicht gewartet hat, die Mutex-Sperre vor dem geweckten Thread erhalten. Dadurch springt er vor und der geweckte Thread muss sich wieder hinten anstellen. Dieses Problem wird durch die uthread_yield()-Schleife nach dem Verlassen der Straße reduziert, aber nicht eliminiert.

Bei Semaphoren gibt es keine solche FIFO-Garantie. Die Semaphor-Warteschlange ist oft nicht FIFO (je nach Implementierung). Dadurch ist die Unfairness noch ausgeprägter. Du wirst in deinem Histogramm sehen, dass die Wartezeiten stärker streuen – einige Threads warten sehr kurz, andere sehr lang. Dies ist ein wichtiger Unterschied, den du in deiner Assignment-Abgabe beschreiben solltest.

Thread-Pool-Konzept: Effizienz durch Wiederverwendung

Ein Thread-Pool ist ein Designmuster, bei dem eine feste Anzahl von Threads erstellt wird, die wiederholt Aufgaben ausführen. Statt für jede Aufgabe einen neuen Thread zu erzeugen (teuer!), werden die Aufgaben in eine Warteschlange gestellt und von den Pool-Threads abgearbeitet. Dies wird in Cloud-Diensten wie PrairieLearn oder Webservern verwendet.

In deiner Simulation könntest du einen Thread-Pool einsetzen, um die Anzahl der gleichzeitig aktiven Autos zu begrenzen. Das verhindert, dass zu viele Threads um die CPU konkurrieren und das System überlasten. Der Pool stellt sicher, dass nie mehr Threads laufen als Kerne vorhanden sind – ähnlich wie ein Server-Farm bei einem großen Event wie der Fußball-WM nur eine begrenzte Anzahl von Anfragen parallel bearbeitet.

Praktische Tipps für die Implementierung

Teste mit kleinen N (z.B. N=2) und wenigen Iterationen, um Logikfehler zu finden.
Verwende assert, um die Belegungsbedingungen zu prüfen: assert(num_east <= 3 && num_west <= 3 && (num_east == 0 || num_west == 0));
Zähle die Belegungszustände (1 Ost, 2 Ost, 3 Ost, 1 West, 2 West, 3 West) und gib sie am Ende aus.
Das Histogramm für Wartezeiten sollte eine Größe von z.B. 20 haben. Jeder Thread misst seine Wartezeit als Differenz zwischen dem Zeitpunkt, an dem er zu warten beginnt, und dem Zeitpunkt, an dem er in die Straße einfährt.
Achte auf kritische Abschnitte: Zugriffe auf das Histogramm und die Zähler müssen mit Mutex geschützt werden.

Beispielausgabe

Belegungsstatistik:
1 Ost: 150
2 Ost: 80
3 Ost: 20
1 West: 140
2 West: 70
3 West: 15

Wartezeiten-Histogramm (max 20):
 0: 100
 1: 80
 2: 60
 ...
Overflow: 5

Zusammenfassung

In diesem Tutorial hast du gelernt, wie man eine Verkehrssimulation mit Threads in C umsetzt. Du kennst nun die Unterschiede zwischen Mutex/Bedingungsvariablen und Semaphoren und weißt, wie Fairness durch die Synchronisationsmechanismen beeinflusst wird. Das Thread-Pool-Konzept rundet das Bild ab und zeigt, wie solche Techniken in der Praxis eingesetzt werden – von Spiele-Servern bis zu Cloud-Plattformen. Viel Erfolg bei deiner Assignment-Abgabe!