Kein Folientitel

DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Inhalt
•
•
•
•
•
•
Sperrsynchronisation (Mutex)
Reihenfolgensynchronisation
Semaphore
Verklemmungen
• Deadlocks
• Livelocks
Prioritäteninversion
Prioritätenvererbung
Weitere Beispiele für die Semaphore-Operationen
REQ und REL:
Seite 1
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich
•
Synchronisation ist notwendig, wenn Tasks abhängig voreinander sind, weil sie
gemeinsame Betriebsmittel benutzen, wie z.B. Daten, Geräte oder Programme.
•
2 grundlegende Varianten der Synchronisation:
•
Sperrsynchronisation (wechselseitiger Ausschluss, Mutual Exclude (Mutex))
stellt sicher, dass zu einem Zeitpunkt immer nur eine Task auf ein gemeinsames
Betriebsmittel zugreift.
•
Reihenfolgensynchronisation regelt die Reihenfolge auf gemeinsame
Betriebsmittel
•
Bereiche, in denen Tasks synchronisiert werden müssen, heißen kritische Bereiche.
•
Busy-Waiting ist das Hauptproblem der Software-Lösungen und der Hardwareunterstützten Lösungen zur Durchsetzung des wechselseitigen Ausschlusses.
•
Gesucht werden daher Synchronisationsmechanismen, die Busy-Waiting verhindern.
Dies ist nur auf Betriebssystemebene möglich, da dort Prozesse blockiert und wieder
auf bereit gesetzt werden können..
Seite 2
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore als Lösung
Einführung einer Semaphore, die aus:
–
einer Zählvariablen (Warteschlange) und aus
–
zwei nicht unterbrechbaren (atomaren)
Operationen P(S) und V(S) besteht.
s := s-1;
if (s < 0)
then „Ordne Prozess an
Position –s der
Assoziierten
Warteschlange ein“;
Notationen:
P(S) = passeeren = Verringern um den Wert 1:
Request, wait, down, aquire, …
V(S) = vrijgeven = Erhöhen um den Wert 1:
Release, up, signal, …
s := s+1;
if (s <= 0)
then „Wecke den ältesten
Wartenden Prozess und
sende ihn in den
kritischen Bereich“;
Seite 3
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore zur Synchronisation
•
Bei Standardbetriebssystemen: Bereitmachen einer beliebigen wartenden Task bei V
•
Bei Echtzeitbetriebssystemen: Bereitmachen der höchstprioren wartenden Task bei V
Request
Release
Zähler := Zähler - 1
Zähler := Zähler + 1
Zähler<0 ?
Zähler<1 ?
ja
Task blockieren
ja
eine blockierte Task
bereit machen
Seite 4
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore zur Synchronisation
•
Lösung des wechselseitigen
Ausschlusses mit einem
binären Semaphore
•
Begriff binärer Semaphor
resultiert daraus, dass es
nur zwei Zustände gibt.
Da es nur darauf ankommt, ob
kritischer Bereich frei ist oder
nicht, sind andere Werte
(negative oder größer 1)
nicht nötig:
–
S = 1, wenn kritischer
Bereich frei ist,
–
S = 0, wenn kritischer
Bereich belegt ist.
Initialisiere
Semaphore S = 1
Task 1
Task 2
REQ S
Zugriff auf
geschützte
Betriebsmittel
REQ S
Task 2
blockiert
Task 2 freigegeben
REL S
Zugriff auf
geschützte
Betriebsmittel
REL S
Seite 5
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore zur Synchronisation
•
Reihenfolge-Synchronisation
mit zwei binären Semaphoren
•
Anfangswert = 1 garantiert,
dass dieser Prozess als
Erster beginnt
Task 1
Task 2
Initialisiere
Semaphore S1=0
Initialisiere
Semaphore S2=1
REQ S1
REQ S2
Task 1
blockiert
Aktivität Task 2
REL S1
Task 1 freigegeben
Aktivität Task 1
REQ S2
Task 2
blockiert
REL S2
Task 2 freigegeben
Aktivität Task 2
REQ S1
Task 1
blockiert
Task 1 freigegeben
REL S1
Seite 6
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore zur Synchronisation
•
•
•
•
•
•
•
Erzeuger-/Verbraucher
Synchronisation mit zwei
Zählsemaphoren (Zähler > 1):
Svoll: erzeugte Objekte
für Verbraucher und
Sleer: Freie Plätze für
Objekte des Erzeugers
Svoll = 0 bedeutet
Lager ist leer (Aus einem
leeren Lager kann nichts entnommen
werden)
Sleer = 0 bedeutet
Lager ist voll (In ein
volles Lager kann nichts
deponiert werden)
Sleer+Svoll ist invariant.
Zusätzlich ist beim Erzeugen
und Verbrauchen noch ein MUTEX
zu implementieren
Task "Erzeuger"
Task "Verbraucher"
Initialisiere
Semaphore
Sleer = n
Initialisiere
Semaphore
Svoll = 0
REQ Sleer
REQ Svoll
Erzeuge Objekt
Verbrauche Objekt
REL Svoll
REL Sleer
Seite 7
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore zur Synchronisation
Reader-Writer-Problem:
•
Writer sind Prozesse, die schreiben dürfen, Reader Prozesse, die Anfragen stellen
•
1 Schreiber, n Leser
•
Es dürfen mehrere Leser gleichzeitig auf den Daten lesen.
•
Wenn der Schreiber auf den Daten schreibt, darf kein Leser lesen.
•
Wenn ein Leser liest, darf der Schreiber nicht schreiben (in seinen kritischen Abschnitt eintreten).
•
Schreiber hat Priorität, d.h. wenn der Schreiber in seinen kritischen Abschnitt eintreten will, darf
kein Leser vor ihm mehr in seinen kritischen Abschnitt eintreten.
1. Reader-Writer-Problem: Kein Reader muss auf eine Eintrittserlaubnis warten; es sei denn, ein Writer
befindet sich im kritischen Bereich. Problem: Reader können das System monopolisieren, und
Writer kommt nicht dazu, sein Update durchzuführen -> Verklemmung (starvation) bezüglich
Writer.
2. Reader-Writer-Problem: Sobald ein Writer wartet, wird neuen Readern der Zugang verwehrt. Die
Writer können das System monopolisieren.
3. Reader-Writer-Problem: Fairness durch alternierende Lese- und Schreibphasen: Ist gerade
Lesephase und meldet sich ein Writer an, werden keine neuen Reader mehr zugelassen. Sobald
alle Reader fertig sind, darf der Writer zugreifen. Ist gerade eine Schreibphase und meldet sich
ein Reader an, wird das Ende dieser Schreibphase abgewartet und dann eine Lesephase
gestartet.
Seite 8
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Semaphore zur Synchronisation
Lösung für das 1. Reader-Writer-Problem:
•
Semaphore s für die Schreib- und w für die Lesephase
•
Variable n zählt Anzahl der gleichzeitig aktiven Leser
•
Funktionen:
–
Semaphore s wird mit 1 initialisiert und
wird sowohl von Reader- als auch von
Writerprozessen verwendet, um Writern
einen exklusiven Zugriff zu ermöglichen.
–
Semaphor w stellt sicher, dass ein Update
von n ungestört erfolgen kann.
wait() entspr. REQ
signal() entspr. REL
Readerprozess
Writerprozess
Seite 9
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Übung zum wechselseitigen Ausschluss: Zwei Task A und B (mit absteigender Priorität,
A hat die höchste) benutzen exklusiv zwei gemeinsame Speicherbereiche, die jeweils
durch eine Semaphore geschützt werden (gestr. Linie = Programmcode, nT =
Ausführungsdauer).
Tragen Sie den zeitlichen Verlauf
mit den entsprechenden
Taskzuständen (blockiert = wartet
auf Sema, ablaufwillig = durch
höhere Prio verdrängt) der zwei
Tasks im Bereich 0<=t<=20T ein,
wobei sie zwei Fälle unterscheiden:
• Fall 1: Task A wird bei T=5t und B
bei T=0t gestartet
• Fall 2: Task A wird bei T=2t und B
bei T=0t gestartet
Die zwei Semaphore S1 und S2
sind mit 1 initialisiert.
Task A (Prio 1)
Task B (Prio 2)
T
T
REQ S2
REQ S1
2T
REQ S1
3T
REL S1
2T
2T
REQ S2
3T
REL S2
2T
REL S2
REL S1
T
T
END
END
Seite 10
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Übung: Formular zum Zeichnen der Soll-Abläufe
laufend
Task A
blockiert
ablaufwillig
laufend
Task B
blockiert
ablaufwillig
5
10
15
20
Seite 11
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen
2 Arten
•
Deadlocks (Blockierung, Deadly Embrace): mehrere auf die Freigabe von
Betriebsmittel wartende Tasks blockieren sich gegenseitig
–
Deadlocks entstehen, wenn falsch programmiert wurde oder
–
wenn die Reihenfolge der REQ/REL-Anweisungen falsch gewählt wurde
•
Livelocks (Starvation, Aus-/Verhungern): eine Task wird durch andere Tasks ständig
an der Ausführung gehindert.
–
Beispiel: eine hochpriore Task verhindert ständig die Ausführung einer
niederprioren Task
–
Auch hochpriore Tasks können „Opfer“ von Livelocks werden, Problem der
Prioritäteninversion
Seite 12
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen
•
Beispiel 1: Deadlock durch kreuzweise Betriebsmittelbelegung
Task 1
Task 2
REQ S(DruckTab)
REQ S(TempTab)
REQ S(TempTab)
REQ S(DruckTab)
DruckTab schreiben
TempTab lesen
TempTab schreiben
DruckTab lesen
REL S(DruckTab)
REL S(TempTab)
REL S(TempTab)
REL S(DruckTab)
Tabellen drucken
•
•
Ablauf: Task 1: REQ SD; Task 2: REQ ST; Task 2: REQ SD; Task 2: blockiert;
Task 1: REQ ST; Task 1: blockiert.
Gegenmaßnahme: Vergabe der Betriebsmittel in gleicher Reihenfolge
Seite 13
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen
•
2 Lösungen für die kreuzweise Betriebsmittelbelegung:
•
Task 11 mit Task 2
•
Task 12 mit Task 2
Task 2
REQ S(TempTab)
Task 11
REQ S(DruckTab)
Task 12
REQ S(DruckTab)
REQ S(TempTab)
DruckTab schreiben
REQ S(DruckTab)
REL S(DruckTab)
DruckTab schreiben
REQ S(TempTab)
TempTab schreiben
TempTab schreiben
REL S(DruckTab)
REL S(TempTab)
REL S(TempTab)
TempTab lesen
DruckTab lesen
REL S(TempTab)
REL S(DruckTab)
Tabellen drucken
Seite 14
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Initialisiere
Semaphore S = 1
Verklemmungen
•
Beispiel 2: Deadlock durch
Programmierfehler
Task 1
•
Gegenmaßnahme: höhere
Synchronisationskonstrukte
(z.B. Monitore)
Task 2
REQ S
Zugriff auf
geschützte
Betriebsmittel
REQ S
REQ S
Zugriff auf
geschützte
Betriebsmittel
REL S
Seite 15
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen
•
Beispiel 3: Deadlock durch Programmierfehler (Erzeuger/Verbraucher-Problem)
Erzeuger
•
Verbraucher
While (true) {
While (true) {
Initialisierung:
REQ SWait;
REQ SProd;
SWait = 1
REQ SFree;
REQ SWait;
SFree = 2
/*erzeuge Produkt*/
/*verbrauche Produkt*/
SProd = 0
REL SWait;
REL SWait;
REL SProd; }
REL SFree; }
Wie ist der Programmierfehler zu beheben?
Seite 16
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen
•
Beispiel 3: Deadlock durch Programmierfehler (Erzeuger/Verbraucher-Problem)
•
Ablauf:
SWait=0
SProd=1
SFree=1
Erzeuger: REQ SWait;
Erzeuger: REQ SFree;
SWait=0
SWait=0
SProd=0
SFree=2
SProd=1
Erzeuger: REL SWait;
SWait=0
SWait=1
SFree=1
SProd=1
SFree=0
Erzeuger: REL SWait;
Erzeuger: REL SProd;
SWait=1
SWait=1
SProd=0
SFree=1
SProd=2
SFree=0
Erzeuger: REL SProd;
Erzeuger: REQ SWait;
SWait=1
SWait=0
SProd=1
SFree=1
Erzeuger: REQ SWait;
SProd=2
SProd=2 SFree=-1
Erzeuger: ist blockiert
SFree=0
Erzeuger: REQ SFree;
SProd=0
SWait=0
Verbraucher: REQ SProd;
SWait=0
SProd=1 SFree=-1
Verbraucher: REQ SWait;
SWait=-1
SProd=1
Free=-1
Verbraucher: ist blockiert
SFree=0
Erzeuger: REQ SFree;
Seite 17
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen
•
Beispiel 4: Deadlock durch ungünstigen Speicherzugriff
•
Annahme: Speicherverfügbarkeit = 200 kB
Task 1
•
•
Task 2
…
…
80 kB
70 kB
…
…
60 kB
90 kB
…
…
Verklemmung, wenn sich beide Tasks zwischen der ersten und zweiten
Speicheranforderung befinden, da nur noch 50 kB verfügbar sind.
Gegenmaßnahme: Virtueller Speicher
Seite 18
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen (Prioritäteninversion)
Task 1
hohe
Priorität
Task 1 versucht,
Mutex zu belegen,
wird blockiert
Task 1
Task 2
niedere
Priorität
Mutex
Task 2 gibt
Mutex frei
Task 2 belegt
Mutex
Prioritäteninversion
Task 2
Ruhe
Zeit
Ereignis
für Task 2
Ereignis
für Task 1
Seite 19
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Verklemmungen (Prioritäteninversion)
Livelock
Task 1 versucht,
Mutex zu belegen,
wird blockiert
Task 1
hohe
Priorität
Mutex
Task 2
mittlere
Priorität
Task 1
Task 2
Task 3
niedere
Priorität
Task 3 belegt
Mutex
Livelock, Task 1 ist
längerfristig blockiert
Task 3
Ruhe
Zeit
Ereignis
für Task 3
Ereignis
für Task 1
Ereignis
für Task 2
Seite 20
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Vermeidung von Deadlocks
2 Klassen von Methoden zur Deadlockverhinderung (Deadlock Prevention)
•
Indirekte Methoden (Erfüllung von 3 Bedingungen für den Eintritt eines Deadlocks):
•
1. Bedingung: Mutual Exclusion, d.h. mind. 2 Prozesse und 2 Betriebsmittel
•
2. Bedingung: Hold and Wait, d.h. ein Prozess muß ein Betriebsmittel behalten, während er
auf ein weiteres Betriebsmittel wartet
•
3. Bedingung: No Preemption, d.h. ein Betriebsmittel kann einem Prozess, der sie behält,
nicht wieder entzogen werden.
•
Direkte Methoden (Betrachtung der genauen Deadlock-Situation):
•
Circular Wait, d.h. es existiert eine geschlossene Kette von Prozessen, so dass jeder
Prozess mindestens ein Betriebsmittel behält, das von einem anderen Prozess der Kette
gebraucht wird.
fordert an
Betriebsmittel A
belegt von
Prozess 1
Prozess 2
belegt von
fordert an
Betriebsmittel B
Seite 21
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Vermeidung von Verklemmungen durch Prioritätenvererbung
•
Vermeidung des Livelocks
Task 1 versucht,
Mutex zu belegen,
wird blockiert
Task 3 gibt
Mutex frei
Task 1 ist
fertig
Task 1
Task 2
Task 3 belegt
Mutex
Prioritätenvererbung,
Task 3 erhält die
Priorität von Task 1
(daher keine Unterbrechung durch Task 2)
Task 3
Ruhe
Zeit
Ereignis
für Task 3
Ereignis
für Task 1
Ereignis
für Task 2
Seite 22
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Vermeidung von Verklemmungen durch Prioritätenvererbung
•
Vermeidung durch das priority ceiling protocol (Prioritätsobergrenze)
Deadlocks entstehen auch dadurch, dass
sich Tasks gegenseitig blockieren, wenn sie
auf mehrere kritische Bereiche zugreifen
müssen (s. Übung Seite 10); jeder kritische
Bereich wird dabei durch eine Semaphore
geschützt.
Task 1
hohe
Priorität
Mutex 1
Task 2
niedere
Priorität
Mutex 2
Regel:
Möchte ein Prozess eine Ressource nutzen, so wird zuerst geprüft, ob diese verfügbar ist: ist die
Ressource bereits vergeben, so wird die Anforderung verweigert und der Prozess blockiert an dieser
Ressource, ist die Ressource verfügbar, so wird die aktuelle Prioritätsschranke des Systems geprüft: hat
der Prozess eine höhere Priorität als die aktuelle Prioritätsschranke, so bekommt er die Ressource
zugeteilt, hat er keine höhere Priorität, so bekommt er die Ressource nur dann, wenn er schon die
Ressource, die die aktuelle Prioritätsschranke des Systems begründet, besitzt. Ansonsten wird ihm die
Ressource verweigert.
Blockiert ein Prozess an einer Ressource, so erbt der Prozess, der diese Ressource momentan besitzt,
die (höhere) Priorität des anfragenden Prozesses. Der Prozess, der die Ressource schon besitzt, wird
nun unter dieser Priorität weiterverarbeitet, bis er alle Ressourcen freigegeben hat, deren
Prioritätsschranke größer oder gleich der geerbten Priorität ist.
Seite 23
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Übung (s. vorne): gegenseitiges Blockieren beim Zugriff auf kritische Bereiche
Soll-Ablauf ohne priority ceiling protocol (pcp)
REQ S2
REQ S1
laufend
Task A
blockiert
ablaufwillig
laufend
Task B
blockiert
ablaufwillig
5
10
REQ S1
REQ S2
15
20
Seite 24
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
Lösungen der Übungsaufgaben (Kap 7)
Übung: Kein gegenseitiges Blockieren beim Zugriff auf kritische Bereiche
Soll-Ablauf mit priority ceiling protocol (pcp)
Hier blockiert Task A
und Task B
bekommt die Prio 1
REL S1 REL S2
REQ S1
REQ S2
laufend
Task A
Hier hat Task B alle
Ressourcen
freigegeben und gibt
damit die Prio zurück.
blockiert
ablaufwillig
laufend
Task B
blockiert
ablaufwillig
5
REQ S1
REQ S2
10
REL S2
REL S1
15
20
Seite 25
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Betriebssystem-unterstützte Lösungen)
Semaphore sind eine „low-level“-Lösung, die erhebliche Disziplin vom Programmierer
verlangt. Eine komfortablere Lösung bieten Monitore.
•
Ein Monitor ist eine Sammlung von Prozeduren, Variablen und Datenstrukturen (mit
einer assoziierten Warteschlange).
•
Prozesse können die Prozeduren des Monitors aufrufen, aber keine internen Daten
ändern.
•
Monitore besitzen die Eigenschaft,
dass immer nur genau ein Prozess
einen Monitor benutzen kann.
•
Monitore sind Konstrukte einer
Programmiersprache und erfordern
daher spezielle Compiler,
die Maschinenbefehle generieren,
die z.B. den wechselseitigen Ausschluss
im Monitor garantieren
(nicht mehr der Programmierer).
Seite 26
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
Die Abarbeitung von Monitorprozeduren wird von Zustandsvariablen (condition
variables) abhängig gemacht, auf die zwei Operationen wirken
–
wait(cond) veranlasst einen Prozess, sich schlafen zu legen, d.h. sich an das
Ende der assoziierten Warteschlange einzureihen. (ähnlich REQ)
–
signal(cond) weckt den ältesten Prozess in der Warteschlange. (ähnlich REL)
•
Unterschied zu Semaphor: signal hat keine Wirkung, wenn zum Zeitpunkt des
Absendens kein Prozess wartet, d.h. sie gehen verloren.
•
Mit anderen Worten: signal(cond) signalisiert das Eintreffen der Bedingung cond und
wait(cond) realisiert das Warten von Prozessen aufgrund des Nichterfülltseins von
cond.
•
Da sich immer nur ein Prozess im Monitor befindet, werden die wait und signal-Operationen
atomar ausgeführt.
Seite 27
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
Beispiel:
Seite 28
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
Problem: Was passiert, wenn Prozess A während Monitorbenutzung ein Signal setzt,
auf das ein anderer Prozess B wartet, d.h. nach der signal-Operation können sich
zwei Prozesse im Monitor befinden?
•
3 Lösungen sind möglich:
–
1. Lösung (Brinch Hansen): Die signal-Operation ist immer die letzte Operation
eines Prozesses im Monitor, d.h. die Operation wird abgeschlossen, bevor ein
anderer Prozess erweckt wird.
–
2. Lösung (Hoare): Der Signalgeber-Prozess wird gesperrt, bis der erweckte
Prozess den Monitor verlassen hat.
–
3. Lösung: Der Prozess wird erst erweckt, nachdem der Signalgeber-Prozess
den Monitor verlassen hat.
•
Kein Königsweg: Die verwendete Semantik muss explizit festgelegt werden; Beste
Lösung: signal-Operation immer ans Ende einer Monitorprozedur setzen.
Seite 29
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
Erzeuger/Verbraucher-Problem:
Seite 30
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
3. Reader-Writer-Problem:
ankommender Reader
erhält Priorität vor später
ankommenden Writern
und umgekehrt.
Seite 31
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
3. Reader-Writer-Problem
Seite 32
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
3. Reader-Writer-Problem
Seite 33
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
Ablaufbeispiel für das 3. Reader-Writer-Problem
Seite 34
DHBW Stuttgart, Studiengang Elektrotechnik, 5. HJ, Vorlesung: Realzeitsysteme
Nov 2016
7) Task-Synchronisation
Kritischer Bereich (Monitore)
•
Ablaufbeispiel für das 3. Reader-Writer-Problem
Seite 35

Download Report