Computer-Systeme Teil 14: Synchronisationwi.f4.htw-berlin.de/users/messer/LV/WI-GWI-RABS/Folien/CS-14/14-CS... · Computer-Systeme – WS 12/13 - Teil 14/Synchronisation 3 Übersicht

Computer-Systeme – WS 12/13 - Teil 14/Synchronisation 14.01.2013 1

Computer-Systeme

Teil 14: Synchronisation

Überarbeitete Version

Computer-Systeme – WS 12/13 - Teil 14/Synchronisation 2

Literatur

http://de.wikipedia.org/wiki/Semaphor_(Informatik)[14-5]

Tanenbaum, Andrew: Moderne Betriebssysteme. 2. Auflage, Hanser, 1995

[14-4]

Siegert, Hans-Jürgen; Baumgarten, Uwe: Betriebssysteme. 5. Auflage, Oldenbourg, 2001

[14-3]

Dannegger, Christian; Geugelin-Dannegger, Patricia: Parallele Prozesse unter UNIX. Hanser, 1991

[14-2]

Werner, Dieter: Theorie der Betriebssysteme. Hanser, 1992[14-1]


Übersicht

• Grundbegriffe• enter und leave• Dekker's Algorithmus• lock und unlock• Semaphoren• Monitore


Hinführung I

• In diesem Teil werden grundsätzliche Prinzipien bzw. Probleme von Parallelität von Operationen auf gemeinsam benutzte Betriebsmittel, insbesondere RAM betrachtet.

• Bisher gingen wir von folgender Struktur aus:

• Alle Geräte (ION) können per DMA auf den RAM zugreifen und Interrupts senden.

RAM

CPU IOnIO2IO1

Bus

…


Hinführung II

• Nun verallgemeinern wir auf beliebig viele CPUs:

• Der RAM mit dem Bus bietet atomare, also unteilbareLese/Schreib-Operationen an, die nur sequentiell ablaufen. D.h. zu einem Zeitpunkt kann immer nur eine CPU/Gerät auf den RAM zugreifen. Alle anderen Geräte/CPUs müssen warten.

RAM

CPU1 CPU2 CPUn

Bus

IOnIO2IO1 ……


Annahmen I

• Alle Instruktionen der CPUs sind durch Interrupts nicht unterbrechbar, d.h. wenn eine CPU einen Interruptfeststellt, so führt sie die aktuelle Instruktion vollständig aus bevor sie mit der Behandlung des Interrupts beginnt.

• Während einer Instruktion hat die CPU die volle Kontrolle über den Bus bzw. Zugriff auf den RAM, d.h. niemand kann den Bus der CPU wegnehmen noch parallel benutzen.

• Dass heißt:– Für 1-CPU-Maschinen: Nur zwischen den Instruktionen kann

ein Threadwechsel stattfinden, keine Parallelität– Für N-CPU-Maschinen: Für jede einzelne CPU kann nur

zwischen den Instruktionen ein Threadwechsel stattfinden, aber untereinander haben alle CPUs volle Parallelität

• Hinweis: Per Timer-Interrupt kann ein Thread seine CPU verlieren.


Annahmen II

• Für DMA-fähige Geräte gilt folgendes:– Der Vorgang des Kopierens von Blöcken in oder aus dem RAM wird

in Teile zerlegt.– Für jeden Teil erhält das Gerät den Bus atomar.

• Grund: Wenn der vollständige DMA-Vorgang den Bus belegen würde, würden die Wartezeiten der anderen Geräte/CPUs auf den Bus zu lange dauern.

• Nicht-DMA-fähige Geräte brauchen wir hier nicht zu betrachten, denn diese greifen nicht auf den RAM zu.

Aus Gründen der Vereinfachung betrachten wir in diesem Teil nurdie Zugriffe auf den RAM. Dieselben Probleme treten aber auchbeim Zugriff auf Plattenblöcke etc. auf.


Hinführung III

Assertiona != 0

Assertiona= a'-1

.......b:= a;......b:= b-1;......a:= b;.......

......IF a != 0 THEN

......b:= c/a;......

FI.......

Thread A Thread B

Variable a

Zugriff

KritischeAbschnitte

Falls vorhera = 1 war ...


Bemerkungen

• Assertion = Zusicherung = Bedingung, die bei einem korrekten Programm immer erfüllt sein muss

• Um Probleme erkennen zu können, sollte folgendes angenommen werden:– Threads können aufgrund von Pausen andere überholen.– Threads können unterschiedliche Geschwindigkeiten haben.

• Zur Prüfung auf Korrektheit sind auch pathologische, gemeine Konstellationen auszudenken.

• Gibt es eine Konstellation, die zu einem Fehler führt, dann ist die Software fehlerhaft, auch dann, wenn die Wahrscheinlichkeit für derartige Probleme minimal ist.

• Ein Fehler liegt immer dann vor, wenn eine Zusicherung verletzt wird – dies gilt auch dann, wenn explizit keine Zusicherungen benutzt werden.


Das Problem

a:= 1;......

b:= a;......b:= b-1;

IF a != 0 THENa:= b;......

......b:= c/a;......

FI......

Das kann bei einer wie auch bei mehreren CPUs passieren.

Thread A Thread B

Bedeutet "Pause"


Kritische Abschnitte I

• Thread = Sequentiell ablaufende Software ohne eigenen, von anderen Threads getrennten Adressraum, d.h. alle Threadsteilen sich einen AdressraumJeder Thread kann auf alle Variablen aller anderen Threadszugreifen.

• Kritischer Abschnitt = Bereich im Code, bei dessen Ausführung Probleme mit anderen Threads auftreten können

In der Literatur wird häufig statt von Threads von Prozessen gesprochen, dann haben auch Prozesse diese Probleme.

Allgemein: Immer wenn Prozesse/Threads auf gemeinsameBetriebsmittel zugreifen, gibt es Abstimmungsprobleme.


Kritische Abschnitte II

• Kritische Abschnitte sind Code-Abschnitte, die (fast) nie gleich sind.

• Kritische Abschnitte beziehen sich immer auf Daten (Variablen, Geräte etc.).

• Alle kritischen Abschnitte, die sich auf dieselbe Menge von Variablen beziehen, werden zu einer Klasse zusammen gefasst.Mit anderen Worten: Wenn an mehreren Stellen auf dieselben Variablen aus verschiedenen Threads zugegriffen wird, so bilden alle diese Stellen jeweils kritische Abschnitte einer Klasse.

• Alle kritischen Abschnitte einer Klasse müssenuntereinander koordiniert werden.

• Kritische Abschnitte verschiedener Klassen brauchen nicht koordiniert zu werden.


Begriffe - Ganz allgemein

• Koordination = Abstimmung zwischen Threads, um Datenkonsistenz bei gleichzeitigem Zugriff zu erhalten

• Datenkonsistenz = Erfüllen von für die Problemlösung notwendigen Bedingungen an Datenwerte – die Assertions

• Synchronisation =– zeitliche Abstimmung hinsichtlich der Benutzung von

Ressourcen– Herstellen von "Gleichzeitigkeit"

• Ressource = Betriebsmittel = Hier: Adressierbarer SpeicherAllgemein: Etwas, was belegt oder verbraucht werden kann,z.B. CPU, Netz, Platte, Drucker (Papier)


Wechselseitiger Ausschluss

• Wechselseitiger Ausschluss = Mutual Exclusion = Ergebnis der Koordinierung zur Verhinderung von Problemen bei der gemeinsamen Benutzung von Variablen in kritischen Abschnitten

• Beim wechselseitigen Ausschluss werden Threads daran gehindert, eine Ressource zu benutzen, wenn diese durch einen anderen Thread belegt ist.Ressource ist hier die Menge der gemeinsam benutzten Variablen einer Klasse.

• Erst nach Freigabe kann ein anderer Thread die Ressource belegen.

• Wechselseitiger Ausschluss ist das Mittel, um Synchronisation zu realisieren.


Probleme des wechselseitigen Ausschlusses

• Deadlock = Warten auf ein Ereignis, das nicht eintreten kann

• Deadlock ist ein strukturell logisches Problem,Beispiel: You-after-you-Problem

• Starvation = Zu langes Warten auf ein mögliches Ereignis bzw.übermäßige Ungerechtigkeit zwischen Threads

• Starvation ist ein Scheduling-Problem, d.h. ein Problem der schlechten Zuweisung von Ressourcen an Threads (Scheduling)


Demonstrationsbeispiel – Dining Philosophers I

• Ein Philosoph isst entweder Spaghetti oder er denkt.Essen und Denken müssen sich abwechseln und nicht zu lange dauern(in beiden Fällen drohen sonst gesundheitliche Schäden).

• Philosophen benötigen zum Essen zwei Gabeln (Erziehung).• Der Topf der Spaghetti ist unendlich groß.

Spaghetti

Philosoph 1

Philosoph 2

Philosoph 3

Philosoph 4

Gabel 4

Gabel 3Gabel 2

Gabel 1


Demonstrationsbeispiel – Dining Philosophers II

• Alle Philosophen benutzen denselben Algorithmus.• Zum Deadlock führt folgendes:

– Jeder nimmt die Gabel rechts.– Jeder wartet auf die Gabel links.

• Zu Starvation führt folgendes:– Jeder nimmt die Gabel rechts.– Wenn die fehlende Gabel links nicht verfügbar ist, legt er die rechte

Gabel zurück.– Es beginnt von vorn.

• Hinweise– Das Beispiel stammt von Edsger Dijkstra (1965)– Siehe http://en.wikipedia.org/wiki/Dining_philosophers_problem– Ursprünglich war es ein chinesisches Gericht und die Gabeln waren

Stäbchen.


Zeitpunkte der Synchronisation

• Vor dem kritischen Abschnitt ("pessimistische" Strategie)Vor dem Betreten wird sichergestellt, dass später keine Probleme auftreten können.

Beispiele: Semaphoren, Lock/Unlock

• Im kritischen Abschnitt ("optimistische" Strategie)Während der Aktivitäten innerhalb des kritischen Abschnittes wird auf Probleme geprüft.Gibt es sie, werden Verfahren durchgeführt, die den alten Zustand vor dem Konflikt wieder herstellen,und alles beginnt von vorn.

Beispiele: Ethernet, Transaktionen (Datenbanken)

Wir beschäftigen uns hier nur mit der ersten Gruppe.


Ebenen der Implementierungen

• Wir beginnen mit den einfachen Mechanismen und schreiten dann weiter in Richtung Komplexität voran.

• Einfach sind:– Algorithmus nach Dekker– Test-and-Set-Instruktionen zusammen mit Busy Waiting

Zusammengesetzte Mechanismen

Komplexe Mechanismen

Einfache Mechanismen


Kritischer Abschnitt I

....

.... Code ....

....enter(Klassenname);

.... Code ....

....

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

PrologVerfahren zur Koordinierung

EpilogVerfahren zur Freigabe

• Aus Gründen der Vereinfachung wird von zwei Threads A und B ausgegangen.

• Der Code in Freistilnotation ist auf diese Situation abgestimmt.• In der Praxis muss für jede Klasse ein abstrakter Datentyp mit

eigenen lokalen Variablen etc. benutzt werden.

Kritischer Abschnitt (grau)


Kritischer Abschnitt II

• In den beiden Routinen enter() und leave() wird ein Verfahren abgearbeitet, das die Synchronisation realisiert:

• Die Parameter (Klassenname) von enter() und leave() beziehen sich auf die Klasse der kritischen Abschnitte.

• Implementierungstechnisch sind dies Variablen (von einem Typ, der die Synchronisation realisiert), mit denen die Koordinierung durchgeführt wird.


Implementierungen von enter() und leave()

• Es gibt verschiedene Versionen für die Implementierungen, die jeweils Stärken und Schwächen haben.

• Es werden im folgenden zwei betrachtet.

• Dies beginnt mit einer schrittweisen Entwicklung des Algorithmus von DekkerIn den ersten Versionen sind Fehler, die in den späteren bereinigt werden.(siehe http://en.wikipedia.org/wiki/Dekker's_algorithm)

Bei diesen Algorithmen wird von zwei Threads und nur einemkritischen Abschnitt ausgegangen, so dass die Parameter für enter()und leave() wegfallen können, d.h. es gibt nur eine Klasse.


Dekker's Algorithmus I – 1. Versuch

enter() {WHILE turn = B DOOD;

}

leave() {turn:= B;

}

enter() {WHILE turn = A DOOD;

}

leave() {turn:= A;

}

Thread A Thread B

turn ist eine globale Variable, die initial auf A gesetzt ist.

Jeder Prozess gibt seinem Partner nach seiner Arbeit das Recht, denAbschnitt zu betreten – echt fair.


Dekker's Algorithmus II - Beurteilung

• Sieht eigentlich ganz gut aus, aber...• Problem 1: Wenn ein Prozess außerhalb des kritischen

Abschnittes beendet wird, entstehen Deadlocks.

Warum?Wenn die Variable turn(Klassenname) den Wert A hat und der Thread A nicht mehr existiert, dann kann B nie wieder in den kritischen Abschnitt, denn B wartet auf etwas, was nie eintreten wird, nämlich dass A etwas tut.

Die Idee des 2. Versuchs besteht darin, nicht mehr festzulegen,wer als nächstes eintreten kann, sondern wer eingetreten möchte.


Dekker's Algorithmus III - 2. Versuch

enter() {A-will:= true;WHILE B-will DOOD;

}

leave() {A-will:= false;

}

enter() {B-will:= true;WHILE A-will DOOD;

}

leave() {B-will:= false;

}

Thread A Thread B

Die beiden boole'schen Variablen A-will und B-will bildendie Klassenvariablen, initial sind beide false.Sie können atomar gelesen und geschrieben werden.


Dekker's Algorithmus IV - Beurteilung

• Funktioniert ganz gut, aber....• Problem 2:

Es entstehen durch exakte Parallelität Deadlocks.

Idee: Die Deadlocks lassen sich durch zeitweises Zurücknehmender Willenserklärung auflösen...

A-will:= true;WHILE B-will DOOD;

B-will:= true;WHILE A-will DOOD;

parallel


Dekker's Algorithmus V - 3. Versuch

enter() {A-will:= true;WHILE B-will DO

A-will:= false;// Chance für BA-will:= true;

OD;}

leave() {A-will:= false;

}

enter() {B-will:= true;WHILE A-will DO

B-will:= false;// Chance für AB-will:= true;

OD;}

leave() {B-will:= false;

}

Thread A Thread B


Dekker's Algorithmus VI - Beurteilung

• Bisher beste Lösung, aber...• Problem 3: Es kann Verhungern auftreten.

Warum?Wenn A viel schneller als B ist, dann nutzt A seine Chance nach der Freigabe durch B aus – B muss dann warten.Wenn dann A den Abschnitt verlässt und dann gleich wieder betritt, kann nun auch wieder A sich aufgrund der höheren Geschwindigkeit gegenüber B durchsetzen – Starvation für B.

Idee: Das bisherige durch die Priorisierung aus dem 1. Versuchkombinieren, d.h. derjenige, der warten muss, hat beim nächstenMal Priorität…


Dekker's Algorithmus - Die beste Lösung

enter() {A-will:= true;WHILE B-will DO

IF turn = B THENA-will:= false;WHILE turn = B DO OD;A-will:= true;

FI;OD;

}

leave() {turn:= B; A-will:= false;

}

enter() {B-will:= true;WHILE A-will DO

IF turn = A THENB-will:= false;WHILE turn = A DO OD;B-will:= true;

FI;OD;

}

leave() {turn:= A; B-will:= false;

}

Thread A Thread B


Bemerkungen

• Der vorgestellte Algorithmus hat die Eigenschaft,– dass er bei N-CPUs funktioniert, d.h. immer.– dass der wartende Thread Zeit in einer Schleife vertrödelt –

dies wird Busy Waiting genannt.

• enter() und leave() mit einer Implementierung, die BusyWaiting arbeitet, werden auch lock() und unlock() genannt.


• In der Praxis wird mit speziellen Instruktionen gearbeitet:Eine Test-and-Set-Instruktion liest, modifiziert und kopiert den alten Inhalt ununterbrechbar durch andere CPUs/Geräte.

• Was macht die Instruktion?Der 2. Parameter gibt die Adresse einer Speicherzelle an. Von dort wird der Wert gelesen und dann auf true (oder 1) gesetzt.

• Technisch wird dies über ein 1 Bit realisiert: dieses Bit wird auf 1 gesetzt und der frühere Wert wird in ein Register geschrieben.

Ununterbrechbare test-and-set-Instruktion I

Instruction TestAndSet(Addr b) {old:= b; // der alte Wert an Adresse bb:= true; // an die Adresse b wird true geschriebenreturn(old); // der ursprüngliche Wert wird geliefert

}


Ununterbrechbare test-and-set-Instruktion II

Instruction TestAndSet(Addr b) {old:= b;b:= true; return(old);

}

enter(class) {crit:= true;WHILE crit DO

crit:= TestAndSet(class);OD

}

leave(class) {class:= false;

}


enter()/leave() auf einem 1-CPU-System I

• Bei 1-CPU-Maschinen kann ein Wechsel der CPU zu einem anderen Thread innerhalb des kritischen Abschnitts nur nach einen Interrupt erfolgen.

• Zur Erinnerung: Ein Interrupt-Handler kann den Scheduleraufrufen, der dann die CPU einem anderen Thread zuweist.

• Daher gibt es die Nahe liegende, aber problematische Implementierung:

• Durch dieses Ausschalten der Unterbrechungen behält der aktuell laufende Thread in jedem Falle seine CPU und kann daher ungestört den kritischen Abschnitt durchlaufen.

enter(class) {disable_interrupts();

}

leave(class) {enable_interrupts();

}


enter()/leave() auf einem 1-CPU-System II

• Da das Ausschalten von Unterbrechungen zu Problemen aufgrund von Verlust von Interrupts führt, werden gezielt bestimmte Interrupt-Level (Prioritäten) verwendet:– Die CPU erhält einen Level.– Ein Interrupt kommt nur dann durch, wenn sein Level höher als

der der CPU ist.– Normalerweise ist der CPU-Level auf 0.

• Es wird dann nur soviel, wie unbedingt nötig gesperrt.• Das Abschalten der Interrupts ist eigentlich falsch, denn es

muss nur ein Threadwechsel (continue()) sowie das Ändern von Daten in den kritischen Abschnitten verhindert werden.


Alternative Implementierungen von enter/leave()

enter()/leave()

Busy Waiting1..N CPUsSpezialinstruktionenInterrupts erlaubt

Busy Waiting1..N CPUs

Interrupts erlaubt

Kein Busy Waiting1 CPU

Interrupts verboten

Dekker Spezialinstruktionen Disable Interrupts

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


Wir haben 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.





Semaphoren - Die Idee

• Anstatt den gesamten kritischen Abschnitt mit lock() und unlock() ineffizient zu schützen, wird damit nur das Innere von enter() und leave() geschützt.

• Der kritische Abschnitt ist dann immer noch geschützt, wird aber wie normaler Code ausgeführt.

• Wir haben damit zwei Stufen:– Innerhalb von enter() und leave()– Zwischen enter() und leave()


Semaphoren - (Eisenbahn-)Signale I

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

Belegungszustandes: true heißt frei, false belegt.Diese hat initial als Wert ein true.

– Weiterhin gibt es eine Warteschlange q mit den wartenden Threads ohne eine Priorität.Diese Warteschlange ist initial leer.

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

p steht für passeer, probeeren (Niederländisch). – v(S) realisiert das Verlassen

v steht für vrijgeven, verhogen (Niederländisch).

Diese Art der Semaphoren wird binär genannt, da es nur zweiZustände für den Zustand state gibt.


Semaphoren - (Eisenbahn-)Signale II

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

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

– dequeue():Irgendein Thread wird aus der Warteschlange geholt und fortgesetzt

– empty():Abfrage, ob Warteschlange leer ist


Benutzung der Semaphoren I

....

.... Code ....

....enter(Klassenname);

.... Code ....

....

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

....

.... Code ....

....p(Klassenname);

.... Code ....

....

.... Code ....v(Klassenname);........ Code ........

Kritische Abschnittemit Busy Waiting Eigentlicher

kritischer Abschnitt


Benutzung der Semaphoren II

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

• Im hellgrauen Bereich wird mit Busy-Waiting 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 BusyWaiting erfolgt.

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


Implementierung der 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);

}

KritischerAbschnitt

KritischerAbschnitt


Implementierung der 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 Threadsparallel:– 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 läuft direkt nach

dessen früheren enqueue() weiter.• Alle Prozesse führen denselben Code aus, d.h. kein separater

Code wie in dem Beispielverfahren von Dekker.

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


Implementierung der Semaphoren III

enqueue(Semaphor S) {Sich selbst in die Queue eintragenIn Thread-Tabelle auf "Waiting" setzenunlock(S);continue(Scheduler);lock(S);

}

dequeue(Semaphor S) {Einen Thread aus der Queue holenIn 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


Monitore I

• Das Programmieren mit Semaphoren ist – aufwändig– relativ fehlerhaft, da die p() und v() über den Code verteilt sind

und manchmal ein v() oder ein p() vergessen oder zuviel ausgeführt wird.

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





Monitore II

• Monitor = Abstrakter Datentyp mit allen für eine Klasse vorhandenen Operationen sowie der Bedingung, dass immer nur ein Thread eine der Operationen ausführen kann.

• Hat ein Thread den Monitor betreten, so gehört er ihm bis er ihn verlassen hat oder in einer Warteschlange 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 CPascal

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


Monitore III

MONITOR Name {Deklaration der lokalen VariablenOperation-1(Parameter) {

....}Operation-2(Parameter) {

....}....Operation-N(Parameter) {

....}Initialisierung der lokalen Variablen

}


Monitore II

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

• Condition Queues = Hier warten Threads auf bestimmte Ereignisse

• Urgent Queue: Stack für kurzzeitig wartenden Prozesse

Entry Queue

Monitor

Urgent Queue

Condition Queues


Bedingungsvariablen 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 in den Code gesteckt, dass bei der Erfüllung der Bedingung die Operation signalcond() ausgeführt wird.

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


Bedingungsvariablen II

• Waitcond(Bedingungsvariable)bringt den aufrufenden Thread in die Warteschlange für diese Variable und gibt damit Monitor vorübergehend 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 vorübergehend frei gibt.

Operationen auf Bedingungsvariablen


Reader/Writer mit Monitoren I

Thread P1 Thread P2 ReaderWriter

Zirkulärer Puffer

• Writer:– In einen freien Bereich werden Daten geschrieben.– Dann werden diese vom Writer für den Reader frei gegeben.

• Reader:– Die vom Writer geschriebenen Daten werden entnommen.– Der nun ausgelesene Bereich wird für den Writer frei gegeben.

Reader/Writer-Mechanismen gehören zu den Standard-Verfahrender Inter-Prozess-Kommunikation.


Idee des Zirkulären Puffers I

Out

Invom Writerbewegt

vom Readerbewegt

Noch nichtverarbeitet

Basis

Limit

Zeigt auf nächstesByte (read)

Zeigt auf nächstes

Byte (write)


Idee des Zirkulären Puffers II

• Es gibt zwei Zeiger, die als Index in einem Array fungieren:– Der In-Zeiger zeigt auf das Array-Element, das als nächstes

vom Writer beschrieben wird, das erste freie Element also.– Der Out-Zeiger zeigt auf das Array-Element, das als nächstes

vom Reader gelesen werden soll, also das nächste Element.

• Die Variable count gibt die Belegung des Puffers wieder.• MOD ist der Modulo-Operator, dessen Anwendung dafür

sorgt, dass beide Zeiger In und Out sich immer innerhalb der erlaubten Array-Grenzen bewegen.


Reader/Writer mit Monitoren II – Teil 1

MONITOR Buffer {elem[0..size-1] Buffer;INT count;INT In, Out; CONDITION NonEmpty, NonFull;

writeBuffer(elem what) {IF count = size THEN WAITCOND(NonFull); FIBuffer[In]:= what;In:= (In+1) MOD size;count++;SIGNALCOND(NonEmpty);

}


Reader/Writer mit Monitoren III – Teil 2

Elem readBuffer(){IF count = 0 THEN WAITCOND(NonEmpty); FIwhat:= Buffer[Out];Out:= (Out+1) MOD size;count--;SIGNALCOND(NonFull);return(what);

}

/* Initialisierung */Count:= In:= Out:= 0;

}

Dies ist eine typische Ring-Puffer-Lösung zur Interprozesskommunikation.


Bemerkungen

• Es gibt zwei Bedingungsvariablen:– NonEmpty symbolisiert die Bedingung, dass der Puffer nicht

leer ist, d.h. es ist irgendetwas enthalten– NonFull symbolisiert die Bedingung, dass der Puffer nicht

vollständig gefüllt ist, d.h. es gibt noch Platz

• Wenn nun ein Thread etwas in den Puffer schreiben will, muss vorher Platz da sein. Ist der Puffer voll, legt er sich aufdas Ereignis, dass mindestens für ein Element Platz ist, schlafen.

• Wenn ein Thread etwas aus dem Puffer lesen will, muss mindestens ein geschriebener Eintrag vorhanden sein. Wenn nicht, so legt er sich auf das Ereignis schlafen, dass etwas in den Puffer geschrieben wurde.


Nach dieser Anstrengung etwas Entspannung....

Documents

Computer-Systeme Teil 14: Synchronisationwi.f4.htw-berlin.de/users/messer/LV/WI-GWI-RABS/Folien/CS-14/14-CS... · Computer-Systeme – WS 12/13 - Teil 14/Synchronisation 3 Übersicht