28
04.12.15 1 Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II Betriebssysteme Teil 9: Synchronisation – Teil II

Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

  • Upload
    others

  • View
    5

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

04.12.15 1Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II

Betriebssysteme

Teil 9: Synchronisation – Teil II

Page 2: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 2

Übersicht

• Semaphoren (binäre und allgemeine)

• Ereignis-Variablen

• Monitore

Page 3: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 3

Kritischer Abschnitt – Wiederholung

....

.... Code ....

....enter(Klassenname);

.... Code .... .... .... Code ....leave(Klassenname);

....

.... Code ....

....

PrologVerfahren zur Koordinierung

EpilogVerfahren zur Freigabe

Kritischer Abschnitt (grau)

• enter(Klassenname):Betreten eines kritischen Abschnitts

• leave(Klassenname): Verlassen eines kritischen Abschnitts

Page 4: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 4

Alternative Implementierungen von enter/leave()

enter()/leave()

Busy Waiting1..N CPUsSpezialinstruktionenInterrupts erlaubt

Busy Waiting1..N CPUs

Interrupts erlaubt

Kein Busy Waiting 1 CPU

Interrupts verboten

Dekker Spezialinstruktionen Disable Interrupts

Wenn enter() und leave() mit einer dieser Methoden implementiertwerden, so sollen diese Methoden lock() und unlock() genannt werden.

Page 5: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Wir haben noch zwei Probleme…

• Das Busy Waiting ist CPU-Zeit-Verschwendung.Hier wäre es gut, im Wartefall per continue() einen anderen Thread zu aktivieren.

• Ohne Busy Waiting geht es nur mit Abschalten der Interrupts und nur bei einer CPU. Das hat aber den möglichen Verlust von Interrupts zur Folge.

• Am besten ist es, ohne Abschalten von Interrupts die CPU effizient zu nutzen.

Genau hierzu hatte Edsger Dijkstraeine Idee: Semaphoren.

Damit betreten wir den Ebene derkomplexen Mechanismen.

Zusammengesetzte Mechanismen

Komplexe Mechanismen

Einfache Mechanismen

Page 6: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 6

Semaphoren - Zwei Ideen

• Anstatt den gesamten kritischen Abschnitt mit einem lock()-unlock()-Paar zu sperren, wird nur der Code von enter() und leave() gesperrt.

Dadurch reduziert sich die Wahrscheinlichkeit für Kollisionen innerhalb eines kritischen Abschnitts.Der kritische Abschnitt ist dann immer noch geschützt, wird aber wie normaler Code ausgeführt.Wir haben damit zwei „Stufen“:– Innerhalb der Routinen enter() und leave()

– Zwischen den Aufrufen enter() und leave()

• Alle in enter() wartenden Threads verlieren die CPU und erhalten sie erst dann wieder, wenn der Thread den kritischen Abschnitt betreten darf.

D.h. das Warten in enter() wird wie das Warten auf I/O realisiert.

Page 7: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 7

Semaphoren - (Eisenbahn-)Signale I

• Eine Semaphore S besteht aus:– Es gibt eine globale Variable state zur Repräsentation des

Belegungszustandes.Diese hat initial die Anzahl der gleichzeitig im kritischen Abschnitt erlaubten Threads, z.B. 1. Im Falle von 1 können Boole'sche Variablen benutzt werden.

– Weiterhin gibt es eine Warteschlange q mit den wartenden Threads ohne eine Priorität (First Come First Serve: FCFS).Diese Warteschlange ist initial leer.

• Operationen der Semaphore S:– p(S) realisiert das Betreten

p steht für passeer, probeeren (Niederländisch).

– v(S) realisiert das Verlassenv steht für vrijgeven, verhogen (Niederländisch).

Wenn die maximale Anzahl der Threads im kritischen Abschnitt 1 ist, werdendiese Semaphoren binär genannt, da es nur zwei Zustände für den Zustandstate gibt. Diese werden im folgenden behandelt.

Page 8: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 8

Semaphoren - (Eisenbahn-)Signale II

• Operationen auf der Warteschlange q:– enqueue():

Schlafen legen des Aufrufers (continue()) und Einreihen in eine Warteschlange

– dequeue():Ein Thread wird aus der Warteschlange geholt und fortgesetzt.Welcher dies ist, entscheidet die Schedulingstrategiehier: FCFS (First Come First Serve, FIFO)

– empty():Abfrage, ob Warteschlange leer ist: liefert true, falls leer.

Page 9: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 9

Benutzung der Semaphoren I

Page 10: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 10

Benutzung der Semaphoren II

• Im Bereich mit der Farbe Lila können mehrere Threads parallel arbeiten.

• Im hellgrauen Bereich wird mit Sperren erreicht, dass nur ein Thread zu einem Zeitpunkt arbeiten kann.

• Im dunkelgrauen Bereich kann Dank p() und v() nur ein Thread zu einem Zeitpunkt arbeiten, ohne dass ein Sperren oder ein Busy Waiting erfolgt.

Durch dieses Verfahren wird der Bereich des Sperrens/Busy Waitingserheblich reduziert und damit effizienter gemacht.

Page 11: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 11

Implementierung der binären Semaphoren I

p(Semaphor S) { lock(S); IF S.state THEN S.state:= false; ELSE S.enqueue(); FI; unlock(S);}

v(Semaphor S) { lock(S); IF S.empty()THEN S.state:= true; ELSE S.dequeue(); FI; unlock(S);}

Bereich derSperrung durchlock/unlock

Bereich derSperrung durchlock/unlock

Hier wird angenommen, dass Semaphor eine Klasse ist, die selbst wieder dieKlasse Queue (mit enqueue und dequeue) benutzt.

Page 12: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 12

Implementierung der binären Semaphoren II

• Wenn die Variable state true ist, heißt das, dass der kritische Abschnitt leer ist und betreten werden kann.

• Nach einem dequeue() laufen eventuell zwei Threads parallel:– der Thread, der das dequeue() ausgeführt hat– der Thread, der durch das dequeue() aus der Warteschlange geholt

wurde

• Der frisch aus der Warteschlange geholte Thread läuft direkt nach der Stelle seines früheren enqueue() weiter.

• Alle Threads führen den selben Code aus, d.h. kein separater Code wie in dem Verfahren von Dekker.

• Damit keine Deadlocks auftreten:– enqueue() macht direkt vor dem Suspendieren ein unlock(S)– dequeue() macht direkt nach dem Fortsetzen ein lock(S)

Page 13: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 13

Implementierung der binären Semaphoren III - Queue

enqueue(Semaphor S) { Sich selbst in die Queue eintragen In Thread-Tabelle auf "Waiting" setzen unlock(S); continue(Scheduler); lock(S);}

dequeue(Semaphor S) { Einen Thread aus der Queue holen In Thread-Tabelle auf "Ready" setzen}

Wiederaufsetz-punkt nach demWarten

Jetzt erst Abgabeder Kontrolle

Aufgrund dieses lock(S)wartet derfrisch aufgeweckte Thread darauf, dasssein Aufwecker das v() verlässt

Page 14: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 14

Allgemeiner Semaphor

Die Steuervariable stateenthält die Anzahl derThreads, die nocheintreten dürften.

p(Semaphor S) { lock(S); IF S.state>0 THEN S.state--; ELSE enqueue(S); FI; unlock(S);}

v(Semaphor S) { lock(S); IF empty(S) THEN S.state++; ELSE dequeue(S); FI; unlock(S);}

https://de.wikipedia.org/wiki/Semaphor_%28Informatik%29

Page 15: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 15

Ereignis-Flags I

• Ereignis-Flag = Event = logische Variable, deren Zustand die Erfüllung einer Bedingung anzeigt

• Analog zu Semaphoren ist jedem Ereignis-Flag eine Warteschlange für die wartenden Threads zugeordnet.

• Diese Threads warten auf das Erfüllen der Bedingung.

• Bei der Verwaltung von Ressourcen kommen folgende Operationen vor:– Belegen/Anfordern oder Verbrauchen der Ressource

– Freigeben der Ressource

• Bei der Implementierung helfen die Semaphoren.

• Bei Bedingungen, die nicht wie Betriebsmittel zugewiesen werden können, helfen Ereignis-Flags.

Page 16: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 16

Ereignis-Flags II

await(Event E) { lock(E); IF not E.cond THEN enqueue(E) FI; unlock(E);}

set(Event E) { lock(E); E.cond:= true; WHILE NOT empty(E) DO dequeue(E); OD; unlock(E);}

clear(Event E) { lock(E); E.cond:= false; unlock(E);}

Die Komponente condvom E repräsentiertdie Bedingung.

Es werden ALLEwartenden Threadsfreigegeben.

Page 17: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 17

Bemerkungen

• Das Warten auf Ereignisse ist eine Variante des Wartens auf das Ende von I/O, nur mit dem Unterschied, dass bei I/O eigentlich immer nur ein Thread wartet, hier können jedoch mehrere.

• Mit diesem Mechanismus– können Barrieren realisiert werden, bei denen mehrere Threads auf

einander warten bis sie weiter arbeiten.

– kann das Warten auf die Erbringung einer Dienstleistung eines anderen Threads realisiert werden.

Page 18: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 18

Monitore I

• Das Programmieren mit Semaphoren ist – aufwendig

– relativ fehlerhaft, da die kritischen Abschnitte über den Code verteilt sind: ein vergessenes v() erzeugt leicht einen Deadlock

• Idee:In die Programmiersprache ein "sicheres" Konstrukt integrieren und den Compiler die p()- und v()-Operationen generieren lassen: der Monitor

Zusammengesetzte Mechanismen

Komplexe Mechanismen

Einfache Mechanismen

Page 19: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 19

Monitore II

• Monitor = Abstrakter Datentyp mit allen dafür notwendigen Operationen sowie der Bedingung, dass immer nur ein Thread eine der Operationen zu einem Zeitpunkt ausführen kann.

• Hat ein Thread den Monitor betreten, so gehört er ihm bis er ihn verlassen hat oder in einer seiner Warteschlangen wartet.

• Die Idee stammt von C.A.R. HoareSiehe http://de.wikipedia.org/wiki/Monitor_(Informatik)

• Eine gute Implementierung stammt von Per Brinch-Hansen: realisiert in ConcurrentPascal (CPascal)Siehe

• Für Java dienten diese Monitore als Vorlage für die Thread-Implementierung in Java.

Page 20: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 20

Monitore III

MONITOR Name {Deklaration der lokalen VariablenOperation-1(Parameter) { ....}Operation-2(Parameter) { ....}....Operation-N(Parameter) { ....}Initialisierung der lokalen Variablen

}

Page 21: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 21

Monitore IV

• Entry Queue = Threads, die den Monitor betreten wollen, aber nicht dürfen

• Condition Queues = Hier warten Threads auf bestimmte Ereignisse

• Urgent Queue = hier warten Threads, die aufgrund des Eintretens von Ereignissen zusammen mit anderen aktiv werden wollen

Entry Queue

Monitor

Urgent Queue

Condition Queues

Page 22: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 22

Monitore V

• Wenn ein Thread innerhalb des Monitors auf die Arbeit eines anderen Threads in diesem Monitor warten muss, gibt er den Monitor dadurch frei, dass er in eine Condition-Queue kommt und dort schläft.Dadurch können andere Threads den Monitor betreten.

• Wenn der andere Thread gearbeitet hat, weckt dieser einen der Threads auf, die in der korrespondierenden Condition-Queue auf ihn gewartet hatten.

• Da aber nur ein Thread zu einem Zeitpunkt im Monitor sein darf, kommt der aufweckende Thread in die Urgent-Queue.Der wartende hat dadurch die Priorität, denn er hat ja (lange) gewartet.

• Verlässt ein Thread den Monitor, so betreten die Threads der Urgent-Queue mit Priorität gegenüber der Entry-Queue jeweils einzeln den Monitor.

Page 23: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 23

Bedingungsvariablen im Monitor I

• Bedingungsvariable = logische Variable, deren Zustand an eine Bedingung gekoppelt ist:– True -> Bedingung erfüllt

– False -> Bedingung nicht erfüllt

• Die Bedingung selbst wird so im Code realisiert, dass bei der Erfüllung der Bedingung die Operation signalcond() ausgeführt wird.

• Das Warten auf die Erfüllung der Bedingung wird durch waitcond() initiiert.

• Manchmal werden die Operationen auch signal() und wait() genannt.

Dieses Konzept ist dasselbe wie das des Wartens auf Ereignisse.

Page 24: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 24

Bedingungsvariablen im Monitor II

• waitcond(Bedingungsvariable) bringt den aufrufenden Thread in die Warteschlange für diese Variable (Condition-Queue) und gibt damit Monitor frei

• signalcond(Bedingungsvariable)holt den am längsten wartenden Thread aus der Warteschlange, aktiviert ihn und setzt den Aufrufer in die Urgent-Queue

Der Aufrufer wird erst dann wieder aktiviert, wenn der von ihm befreite Thread den Monitor verlässt oder ihn durch Eintreten in eine Warteschlange (Condition-Queue) frei gibt.

Operationen mit Bedingungsvariablen

Was die Priorisierung in den Warteschlangen oder die Anzahl dergeweckten Threads durch ein signalcond() betrifft, gibt es unterschiedlicheRealisierungen der Monitor-Idee.

Page 25: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 25

Beispiel eines Monitors I

MONITOR Stack { elem[1..size] buffer; condition NotEmpty, NotFull; int tos:= 1; // top of stack

PROC push(elem element) { if tos > size then waitcond(NotFull); fi buffer[tos++]:= element; signalcond(NotEmpty); }

elem FUNC pop() { elem e; if tos <= 1 then waitcond(NotEmpty); fi e:= buffer[--tos]; signalcond(NotFull); return e; }}

tos hat den Indexwert oberhalb desobersten Elementes.

Page 26: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 26

Beispiel eines Monitors II - Erläuterungen

• Zwei Threads kommunizieren über diesen Monitor miteinander.

• Der Monitor tauscht die Reihenfolge der Elemente so, dass immer erst das letzte zuerst herausgeben wird.

• Die beiden Bedingungsvariablen regeln die Fälle des– Überlaufs (Stack ist voll)

– Unterlaufs (Stack ist leer)

• indem die betreffenden Threads bis zur Erfüllung folgender Bedingung schlafen gelegt werden:– Überlauf: warten bis Stack leerer geworden ist

– Unterlauf: warten bis Stack gefüllt wurde

Page 27: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

27Betriebssysteme – WS 2015/16 - Teil 11/IPC

Wo gibt es Monitore?

• In fast allen Sprachen gibt es keine Monitore; sie müssen dort „zu Fuß“ programmiert werden – was ihren Sinn in Frage stellt.

• Ausnahmen:– Concurrent Pascal

Siehe:� http://en.wikipedia.org/wiki/Concurrent_Pascal

� http://authors.library.caltech.edu/34677/1/06312840.pdf

� http://brinch-hansen.net/papers/1993a.pdf

– Modula2 (in Abwandlung)

– Mesa

– Java (in Abwandlung)

– Pascal-FC

Page 28: Betriebssysteme Teil 9: Synchronisation – Teil IIwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-09/09-BS...Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 5

Betriebssysteme – WS 2015/16 - Teil 9/Synchronisation II 28

Nach dieser Anstrengung etwas Entspannung....