Assignment Chef icon Assignment Chef
All German tutorials

Programming lesson

Synchronisation in C mit Monitoren: Ein Tutorial zur Verkehrssteuerung für autonome Fahrzeuge

Lerne, wie man mit POSIX-Threads und Monitoren eine sichere Kreuzungssteuerung für autonome Autos implementiert. Inklusive Deadlock-Vermeidung und Helgrind-Analyse.

Synchronisation C Monitor Programmierung POSIX Threads Verkehrssteuerung autonome Fahrzeuge Deadlock Vermeidung Helgrind Analyse Condition Variable Mutex Lock Kreuzungssteuerung Implementierung C Programmierung Übung Multithreading Tutorial Autonome Autos Kreuzung Csc369 Assignment Hilfe Parallelprogrammierung Beispiel Smart City Verkehr Ressourcenverwaltung Threads

Einführung in die Synchronisation mit Monitoren

In der heutigen Welt der autonomen Fahrzeuge ist die Synchronisation von entscheidender Bedeutung. Stell dir vor, du entwickelst eine Verkehrssteuerung für eine Kreuzung, an der selbstfahrende Autos aus verschiedenen Richtungen ankommen. Ohne eine sorgfältige Koordination könnten Fahrzeuge kollidieren oder in einer Deadlock-Situation stecken bleiben. Dieses Tutorial führt dich durch die Implementierung eines Monitors in C, der genau solche Probleme löst. Wir nutzen POSIX-Threads (pthreads), Mutexe und Condition-Variablen, um eine sichere und effiziente Kreuzungssteuerung zu realisieren.

Das Problem: Autonome Autos an einer Kreuzung

Stell dir eine typische Kreuzung mit vier Einfahrten (Norden, Süden, Osten, Westen) vor. Jedes Auto hat eine eindeutige ID, eine Einfahrtsrichtung und eine Ausfahrtsrichtung. Die Aufgabe besteht darin, die Autos so durch die Kreuzung zu lotsen, dass:

  • Keine zwei Autos gleichzeitig denselben Kreuzungsquadranten belegen.
  • Autos in derselben Spur in der Reihenfolge ihres Eintreffens die Kreuzung passieren.
  • Kein Deadlock auftritt, also alle Autos irgendwann durchkommen.

Dieses Szenario ist nicht nur für die Programmierausbildung relevant, sondern auch ein aktuelles Thema in der KI-Entwicklung und der Smart-City-Planung. Ähnliche Probleme treten bei der Ressourcenverwaltung in Multithread-Anwendungen auf, etwa in Datenbanken oder Betriebssystemen.

Der Monitor-Ansatz in C

Ein Monitor ist ein Konzept aus der parallelen Programmierung, das den Zugriff auf gemeinsame Ressourcen kontrolliert. In C implementieren wir einen Monitor mit Mutexen und Condition-Variablen. Unser Monitor für die Kreuzung enthält drei Hauptmethoden:

  • init_intersection(): Initialisiert alle benötigten Datenstrukturen.
  • car_arrive(): Ein Auto trifft an der Kreuzung ein und wird in die entsprechende Spur eingereiht.
  • car_cross(): Das Auto betritt die Kreuzung, sobald der Weg frei ist.

Zusätzlich gibt es eine Hilfsfunktion compute_path(), die den Pfad durch die Kreuzung berechnet.

Implementierung der Datenstrukturen

Zunächst definieren wir die benötigten Typen und globalen Variablen:

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

enum direction { NORTH = 0, SOUTH = 1, EAST = 2, WEST = 3 };

// Struktur für ein Auto
typedef struct {
    int id;
    enum direction in_dir;
    enum direction out_dir;
} Car;

// Spur: Warteschlange für Autos einer Einfahrt
typedef struct {
    Car **cars;
    int head;
    int tail;
    int size;
    int count;
    pthread_mutex_t lock;
    pthread_cond_t cond;
} Lane;

// Kreuzungsstruktur
typedef struct {
    Lane lanes[4];
    pthread_mutex_t quad_locks[4]; // 4 Quadranten
    // Weitere Felder für Zustandsinformationen
} Intersection;

Intersection inter;

Jede Spur hat einen eigenen Mutex und eine Condition-Variable, um die Reihenfolge der Autos zu gewährleisten. Die Quadranten der Kreuzung werden durch separate Mutexe geschützt, um parallele Durchfahrten zu ermöglichen.

Initialisierung der Kreuzung

In init_intersection() initialisieren wir alle Mutexe und Condition-Variablen:

void init_intersection() {
    for (int i = 0; i < 4; i++) {
        pthread_mutex_init(&inter.lanes[i].lock, NULL);
        pthread_cond_init(&inter.lanes[i].cond, NULL);
        inter.lanes[i].head = 0;
        inter.lanes[i].tail = 0;
        inter.lanes[i].size = 100; // Puffergröße
        inter.lanes[i].count = 0;
        inter.lanes[i].cars = malloc(sizeof(Car*) * inter.lanes[i].size);
        pthread_mutex_init(&inter.quad_locks[i], NULL);
    }
}

Auto ankommen lassen (car_arrive)

Wenn ein Auto ankommt, wird es in die entsprechende Spur eingereiht. Dabei muss die Reihenfolge eingehalten werden. Wir verwenden einen Ringpuffer:

void *car_arrive(void *arg) {
    Car *car = (Car*) arg;
    int lane_idx = car->in_dir;
    pthread_mutex_lock(&inter.lanes[lane_idx].lock);
    // Warten, bis Platz in der Spur ist
    while (inter.lanes[lane_idx].count == inter.lanes[lane_idx].size) {
        pthread_cond_wait(&inter.lanes[lane_idx].cond, &inter.lanes[lane_idx].lock);
    }
    // Auto in die Spur einfügen
    inter.lanes[lane_idx].cars[inter.lanes[lane_idx].tail] = car;
    inter.lanes[lane_idx].tail = (inter.lanes[lane_idx].tail + 1) % inter.lanes[lane_idx].size;
    inter.lanes[lane_idx].count++;
    printf("Auto %d in Spur %d angekommen\n", car->id, lane_idx);
    pthread_mutex_unlock(&inter.lanes[lane_idx].lock);
    return NULL;
}

Auto die Kreuzung überqueren lassen (car_cross)

Dies ist der komplexeste Teil. Ein Auto darf die Kreuzung nur betreten, wenn:

  • Es das erste Auto in seiner Spur ist.
  • Der Pfad durch die Kreuzung frei ist (d.h. alle Quadranten auf dem Pfad sind nicht belegt).

Wir implementieren dies mit einer Condition-Variable pro Spur und einer Warteschlange für wartende Autos. Zuerst berechnen wir den Pfad:

int *compute_path(enum direction in_dir, enum direction out_dir) {
    // Gibt ein Array mit den Quadranten-IDs zurück, die das Auto durchfährt
    // Beispiel: in_dir=NORTH, out_dir=EAST → Quadranten 0 und 1
    // Hier vereinfacht: 0=Nordost, 1=Südost, 2=Südwest, 3=Nordwest
    int *path = malloc(sizeof(int) * 2);
    // Logik zur Pfadberechnung (vereinfacht)
    path[0] = in_dir;
    path[1] = out_dir;
    return path;
}

Die car_cross-Funktion muss nun warten, bis das Auto an der Reihe ist und der Pfad frei ist:

void *car_cross(void *arg) {
    Car *car = (Car*) arg;
    int lane_idx = car->in_dir;
    pthread_mutex_lock(&inter.lanes[lane_idx].lock);
    // Warten, bis dieses Auto das erste in der Spur ist
    while (inter.lanes[lane_idx].cars[inter.lanes[lane_idx].head] != car) {
        pthread_cond_wait(&inter.lanes[lane_idx].cond, &inter.lanes[lane_idx].lock);
    }
    // Pfad berechnen
    int *path = compute_path(car->in_dir, car->out_dir);
    int num_quads = 2; // Annahme: immer 2 Quadranten
    // Quadranten in Reihenfolge sperren
    for (int i = 0; i < num_quads; i++) {
        pthread_mutex_lock(&inter.quad_locks[path[i]]);
    }
    // Jetzt Kreuzung betreten
    printf("Auto %d überquert Kreuzung\n", car->id);
    // Nach Durchfahrt: Quadranten freigeben
    for (int i = num_quads-1; i >= 0; i--) {
        pthread_mutex_unlock(&inter.quad_locks[path[i]]);
    }
    free(path);
    // Auto aus der Spur entfernen
    inter.lanes[lane_idx].head = (inter.lanes[lane_idx].head + 1) % inter.lanes[lane_idx].size;
    inter.lanes[lane_idx].count--;
    // Nächstes Auto benachrichtigen
    pthread_cond_signal(&inter.lanes[lane_idx].cond);
    pthread_mutex_unlock(&inter.lanes[lane_idx].lock);
    return NULL;
}

Deadlock-Vermeidung

Ein Deadlock kann auftreten, wenn zwei Autos jeweils einen Quadranten blockieren und auf den anderen warten. Um das zu vermeiden, müssen wir die Quadranten in einer festen Reihenfolge sperren (z.B. immer von Nord nach Süd). In unserem Beispiel ist die Reihenfolge durch die Pfadberechnung bereits vorgegeben. Wichtig ist, dass alle Threads die Quadranten in derselben globalen Reihenfolge anfordern.

Testen mit Helgrind

Helgrind ist ein Valgrind-Tool, das Synchronisationsfehler erkennt. Um es zu nutzen, kompilieren wir das Programm mit -g und führen es aus:

gcc -g -o traffic traffic.c -lpthread
valgrind --tool=helgrind ./traffic

Ein sauberer Helgrind-Bericht zeigt keine Data Races oder Deadlocks an. Falls Fehler auftreten, helfen die Meldungen, die genaue Stelle zu identifizieren. Du kannst auch absichtlich Fehler einbauen, um die Ausgabe zu studieren.

Trend-Beispiel: Wie ein E-Sports-Turnier funktioniert

Stell dir vor, die Kreuzung ist wie ein E-Sports-Turnier mit vier Teams. Jedes Team (Auto) muss nacheinander durch verschiedene Phasen (Quadranten) gehen. Die Condition-Variable sorgt dafür, dass kein Team die Bühne betritt, bevor das vorherige fertig ist. Ähnlich wie bei League of Legends-Matches, wo Spieler in einer festgelegten Reihenfolge handeln, verhindert die Synchronisation Kollisionen und sorgt für einen fairen Ablauf.

Zusammenfassung

In diesem Tutorial hast du gelernt, wie man mit POSIX-Threads und Monitoren eine Verkehrssteuerung für autonome Fahrzeuge implementiert. Du kennst jetzt die Grundlagen der Synchronisation, Deadlock-Vermeidung und den Einsatz von Helgrind. Dieses Wissen ist nicht nur für die Universitätsaufgabe relevant, sondern auch für die Entwicklung von Multithread-Anwendungen in der Industrie.