Nebenläufige Programmierung

Mina Nikolova

Übersicht

Was ist Nebenläufigkeit? Anwendungen Grundlegende Begriffe Problemme Mechanismen zur Synchronisation Programmiersprachen

• CML• Alice• Java

Einführung

Grosse Systemen fordern Nebenläufigkeit

Mehrere Folgen von Aktionen werden gleichzeitig ausgeführt

Prozess – sequentielle Ausführung von Aktionen

Thread – „light-weight“ Prozess

Nebenläufigkeit

Multi-Programmierung• Ein Prozessor führt mehrere Prozesse parallel aus• Ein Prozess wird sequentiell ausgeführt• Teile eines Pozesses werden zw. Abschnitten

anderer Prozesse ausgeführt

Multiprozessor-Programmierung• Zwei oder mehrere Prozessoren teilen gemeinsamen

Speicher oder sind in einem Netzwerk verbunden• Prozesse, die auf den verschiedenen Prozessoren

ausgeführt werden, können miteinander kommunizieren

Anwendungen

Ein Programm arbeitet während ein anderes Programm auf ein Ereignis wartet

Window Systeme zeigen parallel verschiedene Fenster auf dem Display

Prozesse auf verschiedenen Prozessoren können zusammenarbeiten und Probleme lösen

Ein Prozessor kann weiterarbeiten,falls ein anderer Prozessor abstürtzt

Grundlegende Begriffe

Kommunikation• gemeinsam benutzte Variablen, Datenstrukturen,

Dateien• Nachrichtenaustausch durch Kommunikationskanäle

Kooperation - veranlaßt einen Prozess auf einen anderen zu warten oder signalisiert einem Prozess

weiterzuarbeiten Atomarität – atomare Aktion darf nicht während ihrer

Ausführung unterbrochen werden

Grundlegende Begriffe (cont.)

Kritischer Abschnitt – Abschnitt eines Programms, der lesend oder schreibend gemeinsame Daten verarbeitet

procedure sign_up(person)begin

number := number + 1;

list[number] := person;end;

cobeginsign_up(fred);sign_up(bill);

coend;

kritischer Abschnitt

cobegin\coend – Aktionen in diesem Block werden nebenläufig ausgeführt

Probleme

Nichtdeterminismus • ein Programm produziert verschiedene Ausgaben

mit derselben Eingabe

Schwer zu testen • viele mögliche Ausführungen eines Programms

• nur selten auftretende Fehler

Deadlock - ein Prozess kann wegen des Zustandes eines anderen Prozesses nicht mehr arbeiten

Mechanismen zur Synchronisation

Semaphore (Edsger W. Dijkstra,1968)

• schützt gemeinsame Daten.Jeder Prozess benutzt folgende Prozeduren, damit er die Daten benutzen darf :

• wait Prozedur auf Semaphore s- Prozess darf entweder den kA betreten oder wird

unterbrochen und in einer Warteschlange eingeordnet • signal Prozedur auf Semaphore s

- Prozess verläßt den kA und erlaubt Prozesse aus der Warteschlange den kA zu betreten

Locks• Prozess testet eine Lock Variable und wartet, wenn sie

gesetzt ist, oder betritt den kA

Mechanismen zur Synchronisation(cont)

Monitore (Brinch-Hansen, Dahl, Dijkstra, Hoare) • ähneln abstraktem Datentyp, dessen Operationen die

Synchronisation sicherstellen • private Daten • Menge von Prozeduren

aktiver Prozess ruft Prozeduren des Monitors auf

P1

P2

P3

MONITOR

. . . Eingangswarteschlange

Anforderungen an einer Programmiersprache

Kontrollstrukturen• Threads• Kommunikationsabstraktionen

- synchronisierte Kommunikation- gepufferte, asynchrone Kommunikationskanäle,

die die Nachrichtenreihenfolge behalten

• gegenseitiger Ausschluß – nur ein Prozess darf sich zum Zeitpunkt im kA befinden

Programmiersprachen

CML Alice Java Erlang MPD ADA Actors Concurrent Pascal Cobegin/coend

Threads • CML Prozesse• Programm besteht zuerst aus einem Thread

- spawn : (unit unit) thread_id

Kommunikation zw. Threads• Kommunikationskanäle

• synchron, geordnet, ungepuffert- channel : unit ´a chanchannel() kreiert einen Kanal, der mit Werten vom Typ ´a

kommuniziert

Concurrent ML (Reppy, Gansner)

Concurrent ML (cont)

Operationen auf Kanälen- send : (´a chan * ´a) unit

- receive : ´a chan ´a

c = channel();

Beispiel:

spawn (fn()=> … <A> … send(c,3); … <B> …);spawn (fn()=> … <C> … recv c; … <D> …);

<A>

<C>

send/receive

<D>

<B>Ergebnis

Concurrent ML (cont)

Events • mächtiges Konzept für Nebenläufigkeit• verzögerte Aktionen, die der Synchronisation dienen • ´a event : Typ einer Aktion, die einen Wert vom Typ ´a

liefert, wenn sie ausgeführt wird• sync : ´a event ´a - synchronisieren auf einem

Event recvEvt : ´a chan ´a event - receive Event fun receive(ch) = sync (recvEvent (ch)); Ein Thread empfängt Werte von einem Kanal durchSynchronisierung auf einem receive Event für diesen Kanal

Bsp.:

Synchronisierter gemeinsamer Speicher• Konzept für koordinierte Zuweisungen von

gemeinsam benutzten Speicherzellen- Sp Zelle ist anfangs leer

Wenn die Zelle schon voll ist, darf ihr kein Thread Wertezuweisen.Wenn sie leer ist,darf nicht mehr gelesenwerden

Concurrent ML (cont)

leer put 4

4

volltake

Alice

Threads • mehrere Threads können nebenläufig laufen

• werden durch spawn kreiert

Future• kommt als Resultat des spawn Ausdrucks

• ist ein Platzhalter für das Ergebnis der nebenläufigen Berechnung

• wird später durch das fertige Resultat ersetzt fun fib (0 | 1) = 1

| fib n = fib (n-1) + fib (n-2) val n = spawn fib 35

val n : int = _future

inspect nval it : unit = ()

Future n wird als Resultat zurückgegeben

Zuerst wird _future auf dem Display gezeigtWenn das Ergebnis fertig ist, wird _future ersetzt

Alice (cont)

Data-flow Synchronisation• mächtiger Mechanismus für nebenläufige

Programmierung- Futures werden als Werte übergeben- Der Thread, der den Wert der Future fordert,

wird blockiert, bis das Ergebnis die Future ersetzt

- Wenn eine nebenläufige Berechnung eine Exception produziert, „fails“ die Future und wenn sie angefordert wird, liefert die die Exception

Java

Threads • Objekte der Klasse Thread

- start : ertsellt einen neuen Thread durch Ausführung der run Methode von JVM

- interrupt : suspendiert einen Thread und wirfft in ihm eine Exception

Kommunikation zw. Threads• Zuweisen\Lesen gemeinsamer Variablen

• Aufrufen von Methoden von gem. Objekten

Java (cont)

Synchronisation• Locks

- sichern den gegenseitigen Ausschluß bei Nutzung eines Objektes

- Objekte können synchronisierte Methoden haben

- Beim Aufruf einer synchronisierten Methode eines Objekts :

synchronized (object) {statements

}

Der Thread tested das Lock des Objekts, setzt es und führt die Statements aus

Wenn das Lock schon gesetzt ist, muss erwarten bis es wieder verfügbar ist

Java (cont)

• Wait set - eine Form von Semaphore für jedes Objekt

wait - Thread suspendiert sich

notify - Thread „weckt“ anderen Thread

notifyAll - „weckt“ alle Threads vom wait set

• Thread termination- join - Methode, die einen Thread darauf warten

läßt, daß ein anderer Prozess terminiert,damit der Thread z.B. die Ergebnisse vom Prozess nutzen kann

benutzen das Wait set eines Objekts zur Synchronisation

Java (cont)

Synchronisierte Methoden , Beispiel (Lea)class LinkedCell { // Lisp-style cons cell containing

protected double value; // value and link to next cellprotected LinkedCell next;public LinkedCell (double v, LinkedCell t) {

value = v; next = t;}public synchronized double getValue() {

return value;}public synchronized void setValue(double v) {

value = v; // assignment not atomic}public LinkedCell next() { // no synch needed

return next;}

Zusammenfassung

Nebenläufigkeit• wichtiges Konzept in der Informatik

• schwer und aufwendig korrekt zu benutzen CML

• Threads, Events Alice

• Futures, Data-flow Synchronisation Java

• Threads,Synchronisation

Literaturhinweisen

Mitchell, Concepts in Programming Languages, Cambridge University Press 2003

The Alice Team, The Alice System, Online Manual, 2003

Gert Smolka, Concurrent Constraint Programming Based on Functional Programming. Programming Languages and Systems 1-11, 1998