Parallele Prozesse

Concurrent Programming

Eine Unterrichtseinheit für die 12. Klasse Informatik

🎯

Ziele

  • Grundlagen paralleler Prozesse verstehen
  • Synchronisation und Kommunikation von Prozessen
  • Probleme erkennen und lösen (Deadlocks)
  • Eigene nebenläufige Programme entwickeln
👥

Zielgruppe

12. Klasse Informatik (Oberstufe)

Umfang: 4-8 Unterrichtsstunden

📚

Vorkenntnisse

Hilfreich, aber nicht notwendig:

  • Endliche Automaten
  • Lernumgebung Kara (ETH Zürich)
Kapitel 1

Einführung und Grundbegriffe

🍳 Beispiel 1: Sepp und Max im Stress

Max kocht ein Dreiminuten-Ei, wäscht Salat, lässt den Pizza-Teig aufgehen und schlägt Rahm für die Creme zum Dessert.

Sepp schneidet Zwiebeln, um sie später anzudämpfen, siedet Tomaten, damit sie sich häuten, kocht Reis und muss aufpassen, dass der Zucker, den er für ein Karamell-Töpfchen einkocht, nicht anbrennt.

Ganz schön stressig für die beiden! Zum Glück hat jeder seinen eigenen Arbeitsplatz, so kommen sie sich nicht gegenseitig in die Quere.

📝 Arbeitsaufträge

  1. Inwiefern arbeiten Sepp und Max gleichzeitig und unabhängig voneinander? Inwiefern kann man von zweierlei Arten der Gleichzeitigkeit sprechen?
  2. Nenne weitere Beispiele gleichzeitig ablaufender Alltagsprozesse.
  3. Gib Beispiele für Gleichzeitigkeit bei der Computernutzung an.

💡 Merkzettel: Nebenläufigkeit

Nebenläufigkeit (engl. concurrency = Gleichzeitigkeit):

Mehrere Vorgänge, Objekte oder Prozesse heißen nebenläufig, wenn sie voneinander unabhängig bearbeitet werden können.

  • Zentrale, moderne Programmiertechnik der Informatik
  • Spezialfall: Parallele Verarbeitung
  • Parallele Prozesse = nebenläufige Prozesse, die gleichzeitig in einem Computersystem ablaufen
  • parallel = nebenläufig + gleichzeitig!
  • Gegenteil: Sequentielle Verarbeitung (nacheinander)
Kapitel 2

Synchronisation und Konfliktmanagement

🍳 Fortsetzung: Sepp und Max bereiten ein Menü zu

Max ist für die Vorspeise und das Dessert zuständig, während sich Sepp um das Hauptgericht kümmert.

📝 Arbeitsauftrag

Überlege, ob auch Abhängigkeiten zwischen den beiden bestehen könnten. Wenn ja, welche? Und wie müssten Sepp und Max dann zusammenarbeiten?

⚠️ Beispiel 2: Sepp und das kleine Pfännchen

Sepp will Zwiebeln anbraten und Zucker einkochen. Für beide Arbeiten braucht er ein kleines Pfännchen. Leider ist sein Arbeitsplatz etwas spärlich ausgestattet, und so hat er nur ein einziges, geeignetes Pfännchen.

📝 Arbeitsaufträge

  1. Warum kann man davon sprechen, dass sich für Sepp Konflikte beim Kochen ergeben?
  2. Übertrage das Beispiel auf die Informatik und nenne mögliche Konflikte und Konfliktlösungen bei der Computernutzung.

💡 Merkzettel: Synchronisation

1
Parallele Prozesse können indirekt voneinander abhängig sein

→ Synchronisation (= Abstimmung paralleler Vorgänge aufeinander)

2
Aufgrund knapper Betriebsmittel können Konflikte auftreten

→ Konfliktmanagement (z.B. durch wechselseitigen Ausschluss)

🚨 Beispiel 3: Sepp und Max beim Aufräumen (Deadlock)

Die Küche ist aufgeräumt, die beiden Köche müssen nur noch den Boden wischen. Jeder möchte möglichst rasch nach Hause gehen.

Während Sepp den Besen holt, bringt Max den Wassereimer. Als sich nun Max nach dem Besen umsieht, merkt er, dass Sepp sich diesen genommen hat. Sepp geht es genauso: Wie er sich den Wassereimer nehmen will, sieht er, dass Max diesen bereits hat.

„Gib mir den Besen!", ruft Max. „Nein", sagt Sepp, „ich will jetzt den Wassereimer!" Die beiden blockieren sich. Wenn keiner nachgibt, werden sie den Boden nie reinigen können.

📝 Arbeitsaufträge

  1. Was unterscheidet diesen Konflikt von dem vorangehenden? Wie kann der Konflikt gelöst werden?
  2. Übertrage das Beispiel auf die Informatik und nenne mögliche Konflikte und Konfliktlösungen.

💡 Merkzettel: Verklemmung

Der wechselseitige Ausschluss genügt nicht – parallele Prozesse können sich sogar gegenseitig blockieren!

Verklemmung (Deadlock): Zwei oder mehr Prozesse warten gegenseitig auf Ressourcen, die der jeweils andere hält.

Lösung: Blockaden müssen erkannt und aufgelöst werden (Schutz durch Prozesskommunikation)

📊 Strategien zur Vermeidung bzw. Lösung von Konflikten

Wechselseitiger Ausschluss (exklusiv)

  • Monitor (engl. to monitor = überwachen)
  • Kritische Abschnitte (Critical Section)
  • Konfliktmanagement
  • Prozesskommunikation

Zeitliche Synchronisation (inklusiv)

  • Meeting Room
  • Barriere (Barrier)
  • Gegenseitige Abstimmung (z.B. Warten)
Kapitel 3

Übungen mit MultiKara

🐞 MultiKara: Concurrent Programming

MultiKara ist eine Lernumgebung der ETH Zürich, mit der parallele Prozesse visuell programmiert und getestet werden können.

📝 Aufgabenblatt 1: Verkehrsproblem

Simuliere Verkehrssituationen mit mehreren Karas, die sich auf einer Straße begegnen.

Lernziele:

  • Grundlagen der Nebenläufigkeit
  • Kollisionsvermeidung
  • Scheduler und Prioritäten

📝 Aufgabenblatt 2: Busproblem

Mehrere Busse (Karas) müssen koordiniert an Haltestellen halten.

Lernziele:

  • Synchronisation von Prozessen
  • Warten und Signalisieren
  • Kritische Abschnitte

📝 Aufgabenblatt 3: Weitere Übungen

Aufgabe 1: Füllen eines Rechtecks mit mehreren Karas

Aufgabe 2: Erzeuger-Verbraucher-Problem

Lernziele:

  • Komplexe Synchronisation
  • Producer-Consumer-Pattern
  • Deadlock-Vermeidung

🎮 MultiKara Features

⚙️
Scheduler / Prioritäten

Steuere die Ausführungsreihenfolge der Karas

🎯
Geschwindigkeitskontrolle

Passe die Ausführungsgeschwindigkeit an (langsam bis schnell)

🔍
Visuelle Programmierung

Beobachte parallele Prozesse in Echtzeit

Kapitel 4

Tasks und Threads

💡 Zwei Arten von Gleichzeitigkeit

Wie bei unserem Einführungsbeispiel existieren auch in Computersystemen zwei Arten von Gleichzeitigkeit:

Beispiel TASK (Prozess) THREAD (Faden)
Kochen Gesamte Arbeit eines Koches Einzelne Tätigkeit eines Koches
Computer Gesamtes gestartetes Programm Nebenläufige Sequenz eines Programms
📦

TASK (Prozess)

Ein Task ist ein vollständiger, unabhängiger Prozess mit eigenem Speicherbereich.

  • Eigener Adressraum
  • Unabhängige Ausführung
  • Kommunikation über IPC (Inter-Process Communication)
🧵

THREAD (Faden)

Ein Thread ist ein Ablauffaden innerhalb eines Prozesses mit Zugriff auf den gleichen Speicherbereich.

  • Gemeinsamer Speicher mit anderen Threads
  • Leichtgewichtig (weniger Overhead)
  • Direkte Kommunikation möglich

📚 Wichtige Begriffe

Nebenläufigkeit (Concurrency)

Mehrere Aufgaben werden scheinbar gleichzeitig bearbeitet (durch schnelles Umschalten)

Parallelverarbeitung (Parallelism)

Mehrere Aufgaben werden tatsächlich gleichzeitig auf verschiedenen Prozessorkernen ausgeführt

MultiTasking

Mehrere Tasks (Prozesse) laufen quasi-parallel auf einem System

MultiThreading

Mehrere Threads innerhalb eines Prozesses laufen quasi-parallel

🔍 Weitere Beispiele

Webbrowser

Task: Der gesamte Browser-Prozess

Threads:

  • UI-Thread (Benutzeroberfläche)
  • Netzwerk-Thread (Downloads)
  • Rendering-Thread (Seitendarstellung)
  • JavaScript-Thread

Textverarbeitung

Task: Das Textverarbeitungsprogramm

Threads:

  • Eingabe-Thread (Tastatur)
  • Rechtschreibprüfung-Thread
  • Autospeichern-Thread
  • Druck-Thread
Kapitel 5

Nebenläufigkeit in Java

Java bietet die Möglichkeit, einzelne Programmteile (Threads) quasi-parallel ablaufen zu lassen.

🔧 Thread-Erstellung in Java

Ein Thread ist in Java immer die Instanz einer Klasse, die das Interface Runnable implementiert hat.

Zwei Möglichkeiten zur Thread-Erstellung:

  1. Subklasse von Thread erstellen
  2. Interface Runnable implementieren

Methode 1: Subklasse von Thread

class MeinThread extends Thread {
    @Override
    public void run() {
        // Code, der im Thread ausgeführt werden soll
        for (int i = 0; i < 10; i++) {
            System.out.println("Thread läuft: " + i);
            try {
                Thread.sleep(1000); // 1 Sekunde warten
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }
}

// Verwendung:
MeinThread thread = new MeinThread();
thread.start(); // Thread starten (nicht run() aufrufen!)

Methode 2: Runnable Interface

class MeineAufgabe implements Runnable {
    @Override
    public void run() {
        // Code, der im Thread ausgeführt werden soll
        for (int i = 0; i < 10; i++) {
            System.out.println("Runnable läuft: " + i);
            try {
                Thread.sleep(1000); // 1 Sekunde warten
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }
}

// Verwendung:
Thread thread = new Thread(new MeineAufgabe());
thread.start();

🔒 Synchronisation in Java

Die Synchronisation der Threads erfolgt mit:

synchronized

Etabliert einen Monitor für einen kritischen Bereich. Gleichzeitig darf nur ein Thread auf das Objekt zugreifen.

wait()

Legt den eigenen Prozess schlafen und gibt den Monitor für andere Prozesse frei.

notify()

Stößt die Prozesse, die durch wait() angehalten wurden, wieder an.

🍽️ Klassisches Beispiel: Producer-Consumer-Problem

Das Erzeuger-Verbraucher-Problem ist eine klassische Problemstellung der Prozesssynchronisation.

Szenario:

Ein Roboter (Erzeuger) füllt eine Kiste und legt sie auf einem Zwischenspeicherplatz mit begrenzter Kapazität ab. Die Kiste wird dann von einem zweiten Roboter (Verbraucher) abgeholt. Auf den Zwischenspeicherplatz darf immer nur ein Roboter zugreifen.

Depot-Klasse (Shared Resource)

class Depot {
    private int buffer;
    private boolean empty = true;

    // Synchronized: Nur ein Thread kann gleichzeitig zugreifen
    public synchronized int get() {
        // Warten, wenn Depot leer ist
        if (empty) {
            try {
                Thread.sleep(1000); // 1 Sekunde warten
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
        
        System.out.println("Abgeholt: " + buffer);
        empty = true;
        notify(); // Producer aufwecken
        return buffer;
    }

    public synchronized void put(int value) {
        // Warten, wenn Depot voll ist
        if (!empty) {
            try {
                Thread.sleep(1000); // 1 Sekunde warten
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
        
        buffer = value;
        empty = false;
        System.out.println("Hinzugefügt: " + buffer);
        notify(); // Consumer aufwecken
    }
}

Consumer-Thread

class Consumer extends Thread {
    private Depot depot;

    public Consumer(Depot depot) {
        this.depot = depot;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10; i++) {
            depot.get(); // Wert aus Depot holen
            
            try {
                Thread.sleep(1000); // 1 Sekunde warten
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }
}

Producer-Thread

class Producer extends Thread {
    private Depot depot;

    public Producer(Depot depot) {
        this.depot = depot;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10; i++) {
            depot.put(i); // Wert ins Depot legen
            
            try {
                Thread.sleep(1000); // 1 Sekunde warten
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }
}

Hauptprogramm

public class ProducerConsumerDemo {
    public static void main(String[] args) {
        // Gemeinsames Depot erstellen
        Depot depot = new Depot();
        
        // Producer und Consumer erstellen
        Producer producer = new Producer(depot);
        Consumer consumer = new Consumer(depot);
        
        // Threads starten
        producer.start();
        consumer.start();
        
        // Auf Beendigung warten
        try {
            Thread.sleep(1000); // 1 Sekunde warten
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        
        System.out.println("Fertig!");
    }
}

🍴 Klassisches Problem: Speisende Philosophen

Das Philosophenproblem ist ein klassisches Beispiel für die Notwendigkeit einer Prozess-Synchronisation.

Szenario:

Es sitzen fünf Philosophen an einem runden Tisch, und jeder hat einen Teller mit Spaghetti vor sich. Zum Essen von Spaghetti benötigt jeder Philosoph zwei Gabeln. Allerdings sind nur fünf Gabeln vorhanden, die zwischen den Tellern liegen.

Das Problem:

  • Jeder Philosoph greift zuerst die linke, dann die rechte Gabel
  • Wenn alle gleichzeitig ihre linke Gabel nehmen, wartet jeder auf die rechte
  • Niemand kann essen → Deadlock!

Lösungsansätze:

  • Maximal 4 Philosophen gleichzeitig am Tisch
  • Asymmetrische Lösung (ein Philosoph greift erst rechts)
  • Beide Gabeln atomar (gleichzeitig) aufnehmen
  • Timeout-Mechanismus

Philosophen-Problem: Gabel-Klasse

class Gabel {
    private boolean verfuegbar = true;
    private int nummer;

    public Gabel(int nummer) {
        this.nummer = nummer;
    }

    public synchronized void aufnehmen() throws InterruptedException {
        while (!verfuegbar) {
            wait(); // Warten, bis Gabel frei ist
        }
        verfuegbar = false;
        System.out.println("Gabel " + nummer + " aufgenommen");
    }

    public synchronized void ablegen() {
        verfuegbar = true;
        System.out.println("Gabel " + nummer + " abgelegt");
        notify(); // Wartende Philosophen benachrichtigen
    }
}

Philosophen-Klasse

class Philosoph extends Thread {
    private int nummer;
    private Gabel linkeGabel;
    private Gabel rechteGabel;

    public Philosoph(int nummer, Gabel links, Gabel rechts) {
        this.nummer = nummer;
        this.linkeGabel = links;
        this.rechteGabel = rechts;
    }

    private void denken() throws InterruptedException {
        System.out.println("Philosoph " + nummer + " denkt");
        sleep((int)(Math.random() * 1000));
    }

    private void essen() throws InterruptedException {
        System.out.println("Philosoph " + nummer + " isst");
        sleep((int)(Math.random() * 1000));
    }

    @Override
    public void run() {
        try {
            for (int i = 0; i < 5; i++) {
                denken();
                
                // Gabeln aufnehmen
                linkeGabel.aufnehmen();
                rechteGabel.aufnehmen();
                
                essen();
                
                // Gabeln ablegen
                linkeGabel.ablegen();
                rechteGabel.ablegen();
            }
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }
}

✅ Best Practices für Thread-Programmierung

1️⃣
Minimiere kritische Abschnitte

Halte synchronized-Blöcke so kurz wie möglich

2️⃣
Vermeide Deadlocks

Definiere eine feste Reihenfolge für das Sperren von Ressourcen

3️⃣
Nutze höhere Abstraktionen

Verwende java.util.concurrent (ExecutorService, CountDownLatch, etc.)

4️⃣
Teste gründlich

Thread-Probleme sind oft schwer reproduzierbar

5️⃣
Dokumentiere Thread-Safety

Markiere Klassen und Methoden klar als thread-safe oder nicht