Paradigmen der Programmierung NebenläufigkeitProf. Dr. Christian KohlsInformatik, Soziotechnische Systeme

3. Synchronisation sequentieller und paralleler Aufgaben• Erzeuger – Verbraucher - Muster• Ringpuffer mit Semaphoren• Phasenbezogene Mechanismen / Synchronisationspunkte• Programme in Aufgaben organisieren• Futures, Callables und Executors• Thread Pools• Performance und Skalierbarkeit

Erzeuger-Verbraucher-Muster

Tellerabtrocknen

Tellerwaschen

Geschirr sortieren

Statistik führenLogfile schreiben

Dokument analysierenAntwort berechnen

Dateien einlesenRequest empfangen

…

Erzeuger-Verbraucher-Muster

Tellerabtrocknen

Tellerwaschen

Geschirr sortieren

Statistik führenLogfile schreiben

Dokument analysierenAntwort berechnen

Dateien einlesenRequest empfangen

…

Erzeuger-Verbraucher-Muster

Tellerabtrocknen

Tellerwaschen

Geschirr sortieren

Statistik führenLogfile schreiben

Dokument analysierenAntwort berechnen

Dateien einlesenRequest empfangen

…

Erzeuger-Verbraucher-Muster

Tellerabtrocknen

Tellerwaschen

Geschirr sortieren

Statistik führenLogfile schreiben

Dokument analysierenAntwort berechnen

Dateien einlesenRequest empfangen

…

Erzeuger-Verbraucher-Muster

Tellerabtrocknen

Tellerwaschen

Geschirr sortieren

Erzeuger-Verbraucher-Muster

Tellerabtrocknen

Tellerwaschen

Geschirr sortieren

Tellerwaschen

Erzeuger-Verbraucher-Muster

Wenn die Produzenten zu wenig Arbeit generieren muss ggf. das Verhältnis geändert werden

Achtung:Wenn Produzenten zuviel Arbeit generieren, die von den Konsumenten nicht bewältigt wird, dann muss die Produktion gedrosselt werden.

Lösung: Bounded Queues – Begrenzte Warteschlangen (z.B. Ringspeicher)

Erzeuger-Verbraucher-Muster

Ziele: • Trennung von Aufgabenerstellung (Erzeugen) und Aufgabenausführung (Verbrauchen)

• Trennung zwischen unabhängigen Arbeitsschritten

• Platzieren von Arbeitsaufträgen in einer Todo-Liste für späteres Bearbeiten

Vereinfacht die Entwicklung:Codeabhängigkeiten zwischen Produzent und Verbraucher werden reduziert

Vereinfacht das Workload Management:Daten können mit unterschiedlicher Geschwindigkeit erzeugt/verbraucht werden können

Erzeuger-Verbraucher-Muster

Varianten:Ein Produzent – Mehrere Verbraucher (z.B. Aufteilen der Liste in Einzelaufgaben, Dateien einlesen, Analyse verteilen)

Mehrere Produzenten – Ein Verbraucher (z.B. Apfelkorb, Logfile, Zusammenführen von Teilergebnissen)

Mehrere Produzenten – Mehrere Verbraucher(z.B. Web-Crawler: mehrere Seiten parallel Laden, mehrere Seiten parallel analyisieren)

Beziehungen sind relativ: Eine Aktivität kann sowohl Verbraucher wie auch Erzeuger sein

Bounded Queues

• Mächtiges Resourcemanagementwerkzeug für zuverlässige Anwendungen

• Programme werden robuster

• Drosseln von Aktivitäten, die mehr Arbeit produzieren als bewältigt werden können

• Am Besten gleich zu Anfang einplanen und nicht erst wenn das System an die Grenzen stösst!

Serielle Threadsicherheit durch Weitergabe des Objektbesitzes:Produzent gibt Objekt in Queue und sollte nicht länger darauf verweisen,Verbraucher nimmt Objekt aus Queue

Nur Produzent ODER Verbrauchern besitzen eine Referenz auf das Objekt, so dass immer nur ein Thread darauf zugreift!

Einsatzbereite Bibliotheksklassen: BlockingQueue als neuer Collectiontypimplementiert u.a. als ConcurrentLinkedQueue

Live Codebeispiele

• BoundedBuffer Implementierung mit Semaphoren

• Threadsichere „Apfelernte“ mit Java

Wettlaufsituation

Threadsicherer Puffer

Bessere Apfelernte

• Semaphore sind eine atomare Operation, die sowohl für das Sperren kritischer Abschnitte, als auch für das Warten auf Bedingungen verwendet werden kann (wird daher auch in BS behandelt).

• Eine Semaphore (=Ampel) verwaltet eine Anzahl vor “Eintrittskarten”

• Konzept basiert auf 2 Operationen P (= proberen, testen) und V (= verhogen, erhöhen).

• P: wenn die Semaphore >0 (Eintrittskarten verfügbar) wird sie erniedrigt, stellt aber keine Barriere dar. Ist sie <= 0, so muss der Thread warten. (häufiger Name: acquire() )

• V: die Semaphore wird um 1 erhöht (Eintrittskarte zurückgeben). Wenn dabei der Zähler auf 1 springt, wird ein wartender Thread freigegeben. (häufiger Name: release() )

• Dieser Mechanismus heißt zählende Semaphore (Alternative: binäre Semaphore).

Semaphore (Funktionsweise)

• Semaphoren werden oft eingesetzt um – zu begrenzen, wie viele Threads auf eine Ressource zugreifen können– Ressourcennutzung zu beschränken

• Semaphoren mit nur einer Eintrittskarte sind (fast) wie Sperren (Locks)

• Unterschied: die Semaphore kann von anderen Threads freigeben werden (Threads besitzen die Semaphoren nicht!)

Eine Semaphore kann als einzige Synchronisationsprimitive verwendetwerden. Das sollte man aber nicht tun – Sie ist da sinnvoll, wo derZugang zu einenm Codeabschnitt von einer bestimmten Anzahlabhängt (s. Beispiel)

Semaphore (Einsatzgebiete)

Synchronisation

Bisher betrachtet: Die Synchronisation von sequentiellen Aufgaben mit Produzent-Verbraucher-Muster mit Bounded Queues und Semaphoren

Wie gehen wir mit parallelen Aufgaben um?Wie führen wir Teilergebnisse wieder zusammen?

Beispiel Actors: Aufteilen von Listen und wieder zusammenführen

Datenparallelität und ForkJoin

Phasenbezogene Mechanismen

Vielen nebenläufigen Lösungen ist gemeinsam, dass es immer bestimmtePunkte gibt, an denen die Abläufe mehrerer Threads abgestimmt werdenmüssen:

Ein oder mehrere Threads warten darauf, dass eine Anzahl Threads einenbestimmten Zustand erreicht haben.

Synchronisatoren haben Methoden, um diesen Zustand zu ändern, abzufragen und effizient darauf zu warten, dass der Zielstatus erreicht ist (keine Idle-Schleife!)

CountDownLatchZwei Threads synchronisisieren sich an bestimmten Stellen und tauschen dabei Daten aus. Latches warten auf Ereignisse

CyclicBarrier Barrieren warten darauf, dass mehrere Threads einen Synchronisationspunkt

erreichen, z.B. Simulationen oder Spiele

Live Code-Beispiele

• „Birthday Problem“

• Berechnung durch Simulation statt statistischer Formel

• Viele Berechnungen notwendig

• Parallele Berechnung für verschiedene Gruppengrößen

Latches: Durchgangstore

Verzögerung der Fortführung eines Prozesses bis ein neuer Status erreicht ist

Funktioniert wie ein Tor:Solange der Endzustand nicht erreicht ist, ist das Tor geschlossen, niemand kann weiter

Wenn Endzustand erreicht ist, dann werden alle Threads weitergelassen

Sobald ein Tor offen ist (Endzustand erreicht), kann es nicht wiedergeschlossen werden (es muss ein neuer Latch erzeugt werden)

Ziele:• Sicherstellen, dass nicht weitergearbeitet wird bis andere (vorhergehende) Aktivitäten vollständig abgeschlossen sind• Sicherstellen, dass eine Aktivität nicht startet bevor alle Resourcen initialisiert sind• Sicherstellen, dass ein Service nicht startet bevor andere (von diesem Service benötigte) Services gestartet sind• Warten bis alle anderen Aktivitäten bereit sind für den nächsten Schritt (z.B. Synchronisation von Simulationen oder Spielen)

CountDownLatch• CountDownLatch ist eine flexible Implementierung für viele

Situationen

• Erlaubt es einem oder mehreren Threads so lange zu warten bis eine bestimmte Anzahl Events aufgetreten ist (z.B. n Teilergebnisse vorliegen)

• countDown Methode dekrementiert den Counter wenn das Ereignis eingetreten ist

• der Zähler ist zu Beginn ungleich 0

• await() blockiert bis der Zähler 0 ist (oder Wartezeit abgelaufen oder der wartenende Thread unterbrochen – interrupt – wird)

Live Code-Beispiel

Futures in Scala

Erinnern Sie sich an Actors aus dem Praktikum…Lösung mit Futures ist einfacher, da geblockt wird bis alle Teilergebnisse da sind(Warten auf das Ergebnis, also blockieren bis alle Ergebnisse da sind)

Vorteil: Keine Probleme mit der Reihenfolge der ListenProblem: keine weiteren Ereignisse empfangen

Callables und Futures in Java• Erlauben Methodenaufrufe in separaten Threads auszuführen.

• Oft im Zusammenhang mit weiteren Bibliotheksklassen (Executors, ExecutorService, FutureTask).

• Problem von Runnables: keine Rückgabewerte -> Lösung Callables

Hier landen alle Exceptions im aufrufenden Thread !!

Futures in Java

Das Verhalten von Future.get() hängt vom Status der Aufgabe ab:- wenn fertig (completed), dann gibt get() das Resultat sofort- sonst blockiert get bis die Aufgabe erledigt ist (completed Status erreicht)

Callable kann man sich wie ein Runnable vorstellen, aber mit Result

Programme bestehen aus Aufgaben

• Fast alle nebenläufigen Anwendungen organisieren die Ausführung von Aufgaben

• Aufgaben werden nicht nacheinander in einem Thread (z.B. main) ausgeführt sondern nebenläufig

• Aufteilung in verschiedene, klar gekapselte Aufgaben hat folgende Vorteile:– Vereinfachung der Programmorganisation

(statt monolithischer Klötze)

– Fehlerbehebung ist einfacher aufgrund von Transaktiongsgrenzen

– Ermöglicht Nebenläufigkeit da parallele Bearbeitung einzelner, klar voneinander getrennter Aufgaben möglich ist.

Organisation eines Programms in Aufgaben• Erster Schritt: Identifzierung sinnvoll abgegrenzter

Aufgaben

• Ideal: Unabhängige Aufgaben, Arbeit hängt nicht ab von– Zustand– Rückgabewerten– Seiteneffekten– Anderen Aufgaben

• Je unabhängiger, desto nebenläufiger!

• Unabhängige Aufgaben können immer parallel ausgeführt werden wenn genug Ressourcen vorhanden sind!

• Kleine Aufgaben verbessern:– Flexibilität für den Scheduler– Besseres Load Balancing

Codebeispiel Webserver Single/Multithread

Responsiveness / Reaktionsfreudigkeit:Wenn ein Request sehr lange blockiert sieht es so aus,als wenn der Service nicht mehr verfügbar ist (down).

Passiert z.B. bei intensivem Zugriff auf Datenbanken oder Festplatte

CPU ist nicht ausgelastet während auf I/O gewartet wird – dabei könnten schon weitere Anfragen beantwortet werden!

Daher besser: mehrere Threads 1. Ansatz: für jede Verbindung ein Thread

Codebeispiel Webserver Single/Multithread

Paralleler Server• Handler sind Threads, die bei Bedarf (geht vom Client aus) vom

Server zur Erledigung einer Aufgabe gestartet werden. Sie übernehmen nach dem Start die restliche Kommunikation mit dem Client. Die Handler haben untereinander keine direkte Kommunikation. Sie benutzen oft gemeinsame Objekte (z.B. Datenbank)

Konsequenzen der Multithread-Lösung

• Aufgaben abarbeiten ist vom main Thread genommen, so dass dieser weiterarbeiten kann

• Neue Verbindungen können schneller bearbeitet werden

• Neue Verbindungen können bearbeitet werden, bevor andere Request abgearbeitet sind

• Aufgaben können parallel bearbeitet werden, mehrer Requests können gleichzeitig bedient werden

Bessere Antwortzeiten und besserer Durchsatz

ABER:• Taskhandling Code MUSS threadsicher sein! Z.B. durch lokale Objekte.• Overhead durch Thread Lifecycle Management

Kosten des Multithreadings

• Threads verbrauchen zusätzliche Ressourcen, insbesondere Speicher!• Stabilität: Es gibt ein Limit wie viele Threads erzeugt werden können (hängt von Parametern der JVM ab, und vom Speicher)• Bis zu einem bestimmten Punkt erhöhen mehr Threads auch den Durchsatz. Ab dann verlangsamen weitere Prozesse jedoch die Anwendung!• Und wieder gilt: dies mag beim Testen nicht vorkommen, aber bei Livesystemen, die lange laufen…

Fazit:Problem beim Single-Thread: Sequentielle Abarbeitung führt zu sehr schlechten Antwortzeiten

Problem beim Thread-Per-Task: schlechtes Ressourcenmanagement, Gefahr eines Crashes

Daher: Statt Threads selbst erzeugen, lieber auf das Executor-Framework zurückgreifen

Executor Interface

public interface Executor {

void execute (Runnable command);

}

Executor InterfaceStandardlösung für das Entkoppeln von

Tasksubmission und Taskexecution!

Aufgaben werden weiterhin als Runnable festgelegt

Bonus: ExecutorService erweitert Executor und hat Lifecycle Methoden sowie Hooks für Statistiken, Verwaltung und Monitoring

Basiert auf dem Produzent-Verbraucher-Muster

Es gibt bereits Standardimplementierung von Executor

Einfaches Ändern der Execution Policies

Thread Pools• Homogener Pool mit Arbeitsthreads• Jeder Arbeitsthread kann (nacheinander) Aufgaben

erledigen• Es werden nicht ständig neue Threads erzeugt• Wenn ein Thread stirbt (z.B. Fehler) kann ein neuer

Thread erzeugt werden• Aufgaben liegen in einer Warteschlange zum Abarbeiten• Ein Arbeitsthread arbeitet einfach:

– Hole dir die nächste Aufgabe (das nächste Runnable) von der Warteschlange

– Führe die Aufgabe aus (rufe run() auf)– Und so weiter (warte bis wieder Aufgaben in der Warteschlange

sind)

Fabrikmethoden für Executors• newFixedThreadPool: neue Threads werden erzeugt wenn neue

Aufgaben reinkommen bis zu einer maximalen Thread-Anzahl, danach werden Threads wiederverwendet

• newCachedThreadPool: kein starres Limit sondern Anzahl der Threads wird nach „Bedarf“ angepasst – bei vielen Aufgaben viele Threads, bei wenigen Aufgaben werden Threads aufgegeben

• newSingleThreadExecutor: Ausführung der Aufgaben in einem einzigen Thread (keine Nebenläufigkeit) entsprechend der Warteschlangenstrategie (FIFO, LIFO, Priorität)

• newScheduledThreadPool: Thread Pool mit fixierter Größe, mit dem sich verzögerte und periodische Aufgaben organisieren lassen (ähnlich wie Timer, aber fehlerresistenter)

Thread Pools - Vorteile• Wiederverwendung von Threads ist kostengünstiger als

ständig neue Threads zu erzeugen und freizugeben• Weniger Speicherbedarf! Nicht mehr für jede Aufgabe

ein zusätzlicher Thread! • Durch richtige Konfiguration erhält man immer genug

Threads, um die CPU in Arbeit zu halten während man keine Speicherproblem hat

• MEHR Stabilität!• „Degrades Gracefully“• Mehr Möglichkeiten für Tuning, Verwaltung, Monitoring,

Logging, Fehlerreporting

Executor – Execution Policies • Execution Policy für eine Aufgabengruppe lässt sich leicht ändern.

• Eine solche Policy legt fest, was, wo, wann und wie etwas ausgeführt wird:– In welchem Thread wird die Aufgabe ausgeführt?– In welcher Reihenfolge werden Aufgaben erledigt (FIFO, LIFO,

Priorisiert)?– Wie viele Aufgaben sollen max. nebenläufig bearbeitet werden?– Bei Überlastung: welche Aufgaben sollen aussortiert werden und wie

wird das System darüber benachrichtigt?– Was soll vor/nach Ausführung einer Aufgabe zusätzlich geschehen?– Wie werden Aufgaben abgebrochen/gecancelt?

Fazit:Statt new Thread(runnable).start() lieber einen Executor dazwischen schalten!!! Das gibt viel mehr Flexibilität.

PerformanceAufgepasst bei Datenparallelisierung vonhetereogenen Aufgaben:• Werden Aufgaben A und B zwischen zwei Workern aufgeteilt, aber A

braucht 10x solange wie B, dann ist der Gesamtzuwachs an Geschwindigkeit für den Prozess ist nur 9%.

• Richtig gute Geschwindigkeitszuwächse erreicht man, wenn man viele unabhängige und homogene Aufgaben hat, die nebenläufig bearbeitet werden können.

Richtige Poolgröße:• Für rechenintensive (CPU-Nutzung) reicht ein Threadpool von NCPU+1

(selbst rechenintensive Aufgaben pausieren manchmal)• Für I/O intensive Aufgaben sollten dagegen mehr Threads erzeugt werden,

damit ein anderer Thread die CPU nutzen kann während I/O Operationen ausgeführt werden!

• Andere Ressourcen: Memory, FileHandler, Socket Handler, Datenbankanbindungen

RTask = Wie viele Resourcen braucht jede Aufgabe? RAvailable = Anzahl vorhanden Ressourcen Anzahl sinnvoller Threads = RAvailable / RTask Bsp: wenn ich nur 10 DB-Anbindungen habe, dann bringen auch 20 Threads

nicht mehr Datenbankverbindungen

Probleme mit Thread Pools• Thread Pools funktionieren am Besten wenn die Aufgaben

homogen und unabhängig sind!

• Das Vermischen von lange und kurzlaufenden Aufgaben führt zum Verklumpen/Verstopfen des Pools: Es kann sein, dass nur noch die lange laufenden Aufgaben am Zug sind und die kurzen Aufgaben ewig in der Warteschleife sind! Nur mit sehr vielen Threads ist dies vermeidbar.

• Der Pool muss groß genug sein, so dass Aufgaben, die voneinander abhängen, auch alle abgearbeitet werden können ohne abgelehnt oder warten zu müssen.

• Starvation Deadlocks: Warten auf das Ergebnis anderer Aufgaben, die noch in der Queue sind.

• Confinement: Aufgaben, die threasicherheit durch confinement herstellen dürfen nur NACHEINANDER ausgeführt werden!

• Diese Anforderungen sollten DOKUMENTIERT werden, damit nicht später bei der Wartung diese Anforderungen verletzt werden!

Performance allgemein• Achtung: viele Techniken zur Performancesteigerung

erhöhen die Komplexität

• Lesbarkeit und Wartbarkeit des Programmcodes verschlechtert sich oft

• Performancegewinn wird oft überschätzt

• Tatsächlicher Performancegewinn sollte gemessen und nicht geschätzt werden…

• Schlechte Konfiguration kann sogar Performanceverlust bedeuten!

Bsp: Messen der Unterschiede für Birthday Problem Simulation

SkalierbarkeitFähigkeit die Durchsatzrate bzw. Kapazität zu erhöhen wenn weitere

Rechnerressourcen hinzugefügt werden (CPUs, Speicher, Datenspeicher, I/O Bandbreite).

Problem:• Viele der Tricks, die Performance in einer Single-Threaded-

Umgebung zu erhöhen sind problematisch für die Skalierbarkeit. (z.B. Caching, Reordering von Befehlen)

Verhältnis sequentieller und paralleler Aufgaben beeinflusst die Skalierbarkeit im Wesenlichen!

Amdahl's Law

Amdahl's Law• Amdahl wollte seinerzeit zeigen, dass sich Parallelverarbeitung

kaum lohnt.• Das Gesetz sagt aus, dass die Geschwindigkeitssteigerung durch

sequentielle Programmteile entscheidend begrenzt wird.

Speedup <= 1

Seq + ( 1 – Seq )

N

N = Anzahl ProzessorenSeq = Sequentieller Anteil des Programms

Paralleler Anteil = 1 – Seq. Anteil

• Wenn wir einen Rechner mit N Prozessoren ausnutzen wollen, brauchen wir eine hohe Parallelisierbarkeit.

• Bei vielen Problemen (Simulation physikalischer Prozesse, Big Data) ist die Parallelisierbarkeit beliebig groß!

• Oft gilt: Sehr rechenintensive Anwendungen = sehr parallele Programme• Aber „normale“ Anwendungen sind kaum parallelisierbar !

Beispiel:Ein Programm benötigt 20 Stunden auf einem Prozessor95% lassen sich parallel bearbeiten, aber 1 Stunde (5 %) lässt sich nicht paralellisieren Dann läuft das Programm mind. 1 Stunde und der maximale Speedup ist 20!

Versteckte Sequentialität

• Aufgaben aus der Warteschlange nehmen• Warten auf Teilergebnisse und späteres

Zusammenführen• Warten auf dieselbe Sperre• Alle nebenläufigen Anwendungen haben

auch Punkte sequentieller Abhängigkeiten!

Seqentialität hat negative Auswirkungen auf die Skalierbarkeit

Reduzierung des Wettlaufs um Sperren

Neben logischen Abhängigkeiten ist die häufigste Ursache für Serialität das Warten mehrere Threads auf die gleiche Sperre

Häufig wird dabei unnötig gewartet, da zu viel gesperrt wird…

Wege diesen Wettlauf zu entschärfen:• Sperren möglichst kurz nutzen – nur solange wie nötig • Häufigkeit der Nutzung von Sperren reduzieren• Für unabhängige Daten auch verschiedene Sperren nutzen• Ausschließende Sperren durch andere Koordinationsmechanismen

ersetzen (z.B. atomare Objekte, Thread Confinement, ReadWriteLocks)

Granularität von Sperren

synchronized auf Methoden vermeiden: Es wird ein zu langer Block gesperrt

Auch unabhängige Ressourcen werden gesperrt (andere synchronized Methoden können nicht aufgerufen werden, auch wenn diese unabhängige Variablen verändern)

Lock Splitting: Verschieden Sperren für voneinander unabhängige Variablen

Lock Stripping: Verschiedene Sperren für voneinander unabhängige Datenbereiche (z.B. Arrays nicht mit einer Sperre sondern n Sperren schützen)

Nachteil: mehr Sperren erhöhen die Gefahr von Deadlocks aufgrund zirkulärer Abhängigkeiten

Implizites Lock Splitting durch delegieren an threadsichere Implementierungen, z.B. threadsichere Set Implementierung

Threadsichere Container• Die Containerklassen in java.util sind in der Regel nicht threadsicher (z.B. HashMap)!• Man kann aber für viele Fälle ganz einfach ein sicheres Objekt erzeugen:

Collections.synchronizedMapCollections.synchronizedListusw.

Map<String, Person> m = Collections.synchronizedMap(new HashMap<String,

Person>())

• Geschützt sind allerdings nur die elementaren Operationen (put, get). • Wenn mehrere Operationen zwingend zusammengehören, ist eine entsprechende

Synchronisation nötig!• Insbesondere muss die Anwendung eines Iterator per synchronized geschützt werden:

Set<String> s = m.keySet();synchronized (m) {

for (String x : m) ....

Performance Einbußen aufgrund hohen Grads der Serialisierung!Bessere Performance bieten die java.util.concurrent.* Collections,

z.B. java.util.concurrent.ConcurrentMap

Ausblick

Frameworks:

• Actors für Scala und Java mit akka

• Play Framework

• Servlets

• Node.js (serverseitiges JavaScript)

Kosten des Multithreadings• Koordination zwischen Threads: Sperren, Nachrichtenaustausch,

SpeichersynchronisationKontextwechsel kostet ZeitThreads erzeugen und abwickeln

• Scheduling Overhead

• Sinnvoles Multithreading bedeutet, dass der Performancezuwachs höher als die Kosten ist

• Ziel des Multithreadings: Bessere Performance durch– Effektivere Nutzung der zur Verfügung stehenden Ressourcen (kein

Leerlauf der CPU)– Einbinden zusätzlicher Ressourcen wenn diese zur Verfügung stehen

(mehrere CPUs auch nutzen)

Performance bedeutet: wie schnell und wie viel? Für Serveranwendung ist das „wie viel“ meist wichtiger als das „wie

schnell“.