Betriebssysteme (Betriebssystemtheorie) - Kapitel 4 - Synchronisation
Inhalte von Dr. E. Nadobnyh
4.1. Einführung
Grundbegriffe
1) Eine Nebenläufigkeit ist die parallele bzw. pseudoparallele Ausführung von Prozessen. Es gibt zwei Formen von
nebenläufigen Prozessen:
- voneinander unabhängige Prozesse, die nur um die gemeinsamen Betriebsmittel konkurrieren,
- voneinander abhängige Prozesse, die zur Erfüllung einer gemeinsamen Aufgabe kooperieren.
2) IPC (interprocess communication) ist eine Kooperation zwischen Prozessen oder Threads. IPC ist ein Oberbegriff für Synchronisation und Kommunikation.
3) Eine Synchronisation ist eine zeitliche Abstimmung der abhängigen Prozesse.
4) Eine Kommunikation ist ein Datenaustausch zwischen abhängigen Prozessen.
Klassifikation
Problem des wechselseitigen Ausschlusses
Synonyme: gegenseitiger Ausschluss, Mutual-Exclusion-Problem, Counter-Problem.
Das Problem entsteht im System mit mehreren Prozessen, die die gemeinsamen Ressourcen ändern können.
Eine verlorene Aktualisierung (Lost-Update) ist ein Datenverlust beim unkoordinierten Zugriff auf eine Ressource von mehreren nebenläufigen Prozessen.
Ein zeitkritischer Ablauf (Race Condition) ist eine Situation, bei der mehrere Prozesse:
- gemeinsame Betriebsmittel nutzen und
- das Ergebnis der Nutzung von der zeitlichen Reihenfolge der Operationen abhängt.
⇒ Demo 1.
Ein kritischer Bereich (kritischer Abschnitt) ist ein Codeabschnitt, in dem der Prozess eine gemeinsame Ressource ändert.
Ein wechselseitiger Ausschluss bedeutet, dass ein kritischer Bereich zu einer Zeit nur durch einen der Prozesse durchlaufen werden darf.
Die zeitliche Reihenfolge von Prozessen, die den kritischen Bereich betreten wollen, und die Betretensanzahl ist unwichtig.
Prozesse, die einen kritischen Abschnitt ausführen wollen, müssen warten, bis dieser frei ist. Es gibt zwei Möglichkeiten das Warten zu realisieren:
- aktives Warten und
- Blockierung.
Sperrvariable
1) Synonyme: Sperre, Lock, Spinlock.
2) Lösungsart. Diese Lösung wurde als Softwarelösung (Selbstverwaltungslösung) benannt. Dabei werden nur die traditionellen programmtechnischen Mittel verwendet.
3) Implementierung. Mehrere Prozesse oder Threads besitzen eine gemeinsame Sperrvariable, z.B.
int lock;
Der Zustand lock=0 bedeutet, dass sich kein Prozess im kritischen Bereich befindet.
4) Eintritt-Operation. Vor dem kritischen Bereich muss jeder Prozess folgende Anweisungen ausführen:
while(lock==1); lock=1;
Beide Anweisungen werden als eine Operation „Sperre testen und setzen“ bezeichnet.
5) Austritt-Operation. Hinter dem kritischen Bereich muss jeder Prozess die Operation „Sperre aufheben“ ausführen:
lock=0;
6) Aktives Warten (busy loop, Polling, Busy Waiting) ist ein ständiges Abfragen der Sperrvariable, z.B. in der Schleife:
while(lock==1);
7) Nachteil der Sperrvariable: Das ist die so genannte naive Lösung mit der gleichen Fehler-Ursache. Die Operation „Sperre testen und setzen“ kann unterbrochen werden und der Prozess kann umgeschaltet werden.
8) Nachteile der Softwarelösungen:
- Sie verwenden aktives Warten.
- Sie führen zu recht komplexen Programmsätzen, besonders bei mehreren Prozessen.
TSL -Befehl
Die meisten Prozessoren unterstützen einen speziellen Maschinenbefehl TSL (Test and Set Lock). Die Operation „Sperre testen und setzen“ wird in einem Befehl ununterbrechbar (atomar) implementiert. Diese Lösungsart wurde als Hardwarelösung benannt.
Die Nachteile:
1)Aktives Warten wird verwendet:
|
enter: |
TSL R1, LOCK | // kopiere LOCK in R1 |
| // und setze LOCK auf 1 | ||
| CMP R1, #0 | // war LOCK = 0 ? | |
| JNZ enter | // falls ≠ 0, zur Wiederholung | |
| // falls LOCK ≠ 0, ist KB gesperrt |
2) Die Lösung ist prozessorabhängig.
3) Der Maschinenbefehl wird vom Anwendungsprogrammierer kaum verwendet.
Prioritätsumkehrung
Ein aktives Warten kann die Ursache für den unendlichen Zyklus sein:
1) Ein Prozess L mit niedriger Priorität hat einen kritischen Bereich (KB) betreten.
2) Danach will ein Prozess H mit höherer Priorität den selben KB betreten.
3) Der Prozess H beginnt aktives Warten.
4) Nach Schedulingregel läuft der Prozess H immer, wenn er bereit ist.
5) Der Prozess L hat keine CPU-Zeit, um KB zu verlassen.
4.2. Semaphor
Definition
(Edsger Dijkstra, 1962)Ein Semaphor ist ein Betriebssystemobjekt für die Synchronisation von Prozessen.
Ein Semaphor realisiert das Eintritts- und Austrittsprotokoll des kritischen Bereiches und wurde zur Lösung des wechselseitigen Ausschlusses entwickelt. Ein Semaphor gehört zur Lösungsart, welche das Betriebssystem verwenden.
Analogie: Eingleisige Strecken im Eisenbahnnetz sind kritische Abschnitte. Eintritt und Austritt von Strecken müssen durch Semaphor geregelt werden.
Struktur
Ein Semaphor besitzt:
1) Eine Identität, z.B. Originalname. Mehrere Prozesse können ein Semaphor verwenden und durch die Identität von anderen Semaphoren unterscheiden.
2) Ein Markenzähler (Semaphorzähler) ist ein ganzzahliges Attribut. Er bestimmt, wie viele Prozesse noch in den kritischen Bereich dürfen. Bei der Semaphorerzeugung erhält der Zähler einen Initialwert.
3) Eine Warteschlange von blockierten Prozessen. Wenn ein Prozess nicht den kritischen Bereich betreten darf, wird er blockiert und in die Warteschlange angefügt.
4) Initialisierungsoperation bzw. Konstruktor, initialisiert den Semaphorzähler bei der Erzeugung.
5) Zwei berühmte Operationen bzw. Methoden: P und V.
Operationen
Die P -und V-Operationen werden als Eintritt- und Austritt-Operationen für einen kritischen Bereich vorgesehen.
Sie können als modernisierte Operationen „Sperre testen und setzen“ und „Sperre aufheben“ betrachtet werden. Prinzipielle Anforderungen an Operationen:
1) Die Operationen müssen unteilbar (atomar, ununterbrechbar) sein.
2) Die Operationen müssen den aufrufenden Prozess blockieren können.
Diese Anforderungen sind erfüllt, wenn die Operationen als Systemaufrufe angesprochen werden.
P – Operation
V – Operation
Legende: MZ-Markenzähler
Operationen-Synonyme
| Eintritt- Operation | Austritt- Operation | |
| von Dijkstra | P | V |
| Übersetzung | passieren | verlassen |
| Unix | sem_wait | sem_post |
| Windows | WaitForSingleObject | ReleaseSemaphore |
| Algol 68 | down | up |
| Java 5 | acquire | release |
| Binärer Semaphor | lock | unlock |
Operationen-Realisierung
Ein Semaphor kann im Betriebssystem oder in systemnaher Bibliothek realisiert werden.
Beispiel 1. Ein Semaphor, der im Betriebssystem Windows realisiert wurde, kann mittels den Systemaufrufen
angesprochen werden:
a) Erzeugung und Initialisierung
s1= CreateSemaphore(…, Initialwert, „Name“);
b) Zugang öffnen
s1 = OpenSemaphore(…, "Name");
c) Aufruf der P-Operation
WaitForSingleObject(s1, …);
d) Aufruf der V-Operation
ReleaseSemaphore(s1, ...);
Beispiel 2. Ein Semaphor, der in systemnaher Bibliothek realisiert wird, kann mittels Methodenaufrufen angesprochen werden:
a) Bibliothek
java.util.concurrent.Semaphore;
b) Erzeugung und Initialisierung
s1 = new Semaphore(Initialwert);
c) Aufruf der P-Operation
s1.acquire();
d) Aufruf der V-Operation
s1.release ();
Semaphortypen
Die Spezialisierung kommt durch den Initialisierungswert (I) des Markenzählers vor.
| I | Name und Beschreibung |
| N | Zählsemaphor (general semaphore). Ein Zählsemaphor wird z.B. in dem Erzeuger- Verbraucher-Problem verwendet. |
| 1 | Binärsemaphor (mutex, mutual exclusion). Ein binärer Semaphor wird zur Lösung des wechselseitigen Ausschlusses verwendet. |
| 0 | Schlafen/Wecken (sleep/wakeup). Der Prozess- Aufrufer wird blockiert bis er durch einen anderen Prozess aufgeweckt wird. Ein mit 0 initialisierter Semaphor wird für den Synchronisationspunkt bzw. Barriere verwendet. |
Verwendung
In folgendem Beispiel wird ein Windows-Semaphor zur Lösung des wechselseitigen Ausschlusses verwendet:
1) Zuerst erzeugt ein von Prozessen, z.B. „Prozess a“ einen Semaphor: CreateSemaphore(...);
2) Ein anderer Prozess, z.B. „Prozess b“ öffnet Zugang zu dem schon existierenden Semaphor: OpenSemaphore(...);
3) Beide Prozesse laufen pseudoparallel und schützen ein gesamten kritischen Bereich (KB):
Prozess a:
for(...)
{ WaitForSingleObject(...); //P
KB(...);
ReleaseSemaphore(...); //V
}
{ WaitForSingleObject(...); //P
KB(...);
ReleaseSemaphore(...); //V
}
Prozess b:
for(...)
{ WaitForSingleObject(...); //P
KB(...);
ReleaseSemaphore(...); //V
}
{ WaitForSingleObject(...); //P
KB(...);
ReleaseSemaphore(...); //V
}
⇒ Demo 2
Vorteile und Nachteile
1) Vorteile gegenüber der Softwarelösung und Hardwarelösung:
- Semaphoren sind universell. Die Operationen V und P sind getestet und fehlerfrei.
- Keine CPU-Zeit-Verschwendung, weil nur passives Warten verwendet wurde.
- Der wechselseitige Ausschluss ist garantiert, weil die Operationen unteilbaren sind.
2) Nachteile:
- Algorithmen mit Semaphoren sind schwierig zu verstehen und zu entwerfen.
- Bei der Programmierung werden leicht Fehler gemacht:
- wenn ein P vergessen wird, ist der wechselseitige Ausschluss nicht mehr garantiert,
- wenn ein V vergessen wird, kann dies zu einer Verklemmung führen.
4.3. Semaphor und Erzeuger-Verbraucher-Problem
Erzeuger-Verbraucher-Problem
Synonyme: Produzent–Konsument, Producer–Consumer, beschränkte Puffer-Problem.
Sachverhalt:
1) Einige Prozesse erzeugen, andere verbrauchen Datenelemente (Werte, Daten, Einträge).
2) Datenelemente werden im Lager (Puffer, FIFO-Speicher) abgelegt.
3) Die Anzahl der Plätze (Fächer) im Lager bzw. Lagerkapazität ist beschränkt.
4) Das Lager muss die Geschwindigkeitsunterschiede zwischen Erzeuger und Verbraucher ausgleichen.
Lager im gemeinsamen Speicher
Probleme
1) Wenn der Erzeuger einen neuen Eintrag im Lager ablegen möchte, das Lager aber schon voll ist, muss der Erzeuger blockiert (gesperrt, schlafen gelegt) werden.
2) Wenn der Verbraucher ein oder mehrere Einträge entfernt hat, muss der Erzeuger fortgesetzt werden.
3) Ähnlich geht es mit dem Verbraucher, wenn das Lager leer ist.
4) Das Problem des wechselseitigen Ausschlusses bleibt aktuell.
Besonderheiten der Steuerung
1) Bei dem Datenaustausch mittels des gemeinsamen Speichers kommen beide IPC zustande:
- Prozess-Synchronisation und
- Prozess-Kommunikation.
2) Die Synchronisation von Prozessen oder Threads bei den Zugriffen auf gemeinsamen Speicher ist die Aufgabe des Programmierers.
3) Im Erzeuger-Verbraucher-Problem gibt es zwei Arten der Synchronisation:
- Bedingte Synchronisation (Long Wait). Die Prozesse/Threads dürfen nur in der bestimmten zeitlichen Reihenfolge auf Ressourcen zugreifen.
- Der wechselseitige Ausschluss (Short Wait). Mehrere Prozesse dürfen nicht gleichzeitig auf eine Ressource zugreifen. Dabei ist die zeitliche Reihenfolge unwichtig.
Lösung mit den zwei Semaphoren
Attribute und Methoden der Klasse „Lager“:
Semaphore voll(1); //Lagerkapazität = 1
Semaphore leer(0); //Anzahl der Einträge = 0
void insert(int w)
{ //1.schlafe,wenn voll
voll.P();
//2.Erzeuger betritt KB
put(w);
//3.wecke,wenn leer
leer.V();
}
int remove()
{ //1.schlafe,wenn leer
leer.P();
//2.Verbraucher betritt KB
int w = get();
//3.wecke,wenn voll
voll.V();
return w;
}
Semaphore leer(0); //Anzahl der Einträge = 0
void insert(int w)
{ //1.schlafe,wenn voll
voll.P();
//2.Erzeuger betritt KB
put(w);
//3.wecke,wenn leer
leer.V();
}
int remove()
{ //1.schlafe,wenn leer
leer.P();
//2.Verbraucher betritt KB
int w = get();
//3.wecke,wenn voll
voll.V();
return w;
}
Methoden get und put greifen direkt auf die Datenstruktur und enthalten den kritischen Bereich (KB).
Sonderfall:
Wenn der Lager nur ein einzigen Platz besitzt (Lagerkapazität =1), kann die richtige Synchronisation nur mit zwei Semaphoren gewährleistet werden.
Ablauf:
1) Der Semaphor „voll“ sperrt den doppelten Erzeuger-Zugriff. Der Verbraucher darf den KB betreten, wenn der Erzeuger KB verlässt.
2) Der Semaphor „leer“ sperrt den doppelten Verbraucher-Zugriff. Der Erzeuger darf KB betreten, wenn der Verbraucher den KB verlässt.
3) Logischerweise sind nur die abwechselnden Zugriffe möglich. Beide Synchronisationsarten sind damit gewährleistet.
Lösung mit drei Semaphoren
Korrekte Lösung für beliebige Anzahl von Erzeuger, Verbraucher und Lagerkapazität. Attribute und Methode der Klasse „Lager“:
Semaphore voll(kap); //Lagerkapazität = kap
Semaphore leer(0); //Anzahl der Einträge = 0
Semaphore mutex(1); //Binärer Semaphor
void insert(int w)
{ voll.P();
mutex.P();
put(w); //KB
mutex.V();
leer.V();
}
int remove()
{ leer.P();
mutex.P();
int w = get(); //KB
mutex.V();
voll.V();
return w;
}
Semaphore leer(0); //Anzahl der Einträge = 0
Semaphore mutex(1); //Binärer Semaphor
void insert(int w)
{ voll.P();
mutex.P();
put(w); //KB
mutex.V();
leer.V();
}
int remove()
{ leer.P();
mutex.P();
int w = get(); //KB
mutex.V();
voll.V();
return w;
}
⇒ Demo 3.
4.4. Deadlock
Definition und Ursachen
Ein Deadlock (Verklemmung) ist eine Situation, wenn alle Prozesse einer Gruppe blockiert sind und ProzessAuslöser auch zu dieser Gruppe gehört. Ein Deadlock kann nur bei der Synchronisation auftreten.
Einige Ursachen:
1) Verkehrte Folge von Semaphoroperationen, z.B. in der Lösung des Erzeuger-Verbraucher-Problems.
2) Ungünstigen Reservierungsreihenfolgen bei der Betriebsmittelverwaltung durch das Betriebssystem oder durch den Benutzer.
Beispiel:
Ein Deadlock entsteht bei einer ungünstigen Reihenfolge der Betriebsmittelreservierung:
Legende: R1 und R2 sind Betriebsmittel bzw. Ressourcen.
⇒ Demo 4
Bedingungen
1) Exklusive Nutzung
Jedes Betriebsmittel muss durch genau einen Prozess belegt werden, z.B. Drucker, Plotter.
2) Wartebedingung
Prozesse belegen einige Betriebsmitteln und fordern weitere an.
3) Nichtentziehbarkeit
Die von einem Prozess belegten Betriebsmittel können ihm nicht zwangsweise entzogen werden.
4) Zyklische Wartebedingung
Zwei oder mehrere Prozesse bilden einen Anforderungszyklus.
Analogie aus dem Straßenverkehr:
1) Exklusive Nutzung. Nur ein Lastwagenzug kann die enge Strasse befahren.
2) Wartebedingung. Jeder Zug fordert zwei Strassen an.
3) Nichtentziehbarkeit. Der Zug kann nicht rückwärts fahren.
4) Anforderungszyklus. A wartet auf B und B wartet auf A.
Behandlung
Grundsätzlich gibt es vier Strategien, Deadlock zu behandeln:
1.Erkennung und Beseitigung (detect and recover )
2.Vermeidung (avoid)
3.Verhindern (prevent)
4.Ignorieren (ignore)
Achtung: Begriffsverwirrung bei Verhinderung vs. Vermeidung!
Erkennung und Beseitigung
Deadlocks werden zugelassen und das Betriebssystem versucht, sie zu erkennen und etwas dagegen zu unternehmen.
Bei möglichen Verklemmungen müssen einer oder mehrere der beteiligten Prozesse gewaltsam beendet werden.
Dieses Verfahren ist meistens nicht anwendbar, weil Daten verloren gehen können.
Vermeidung
Eine Deadlock-Gefahr wird regelmäßig überprüft.
Bei jeder Betriebsmittelanforderung wird der Restvorrat freier Betriebsmittel überprüft, ob der noch groß genug ist, um nach erfolgter Zuteilung bei wenigstens einem Prozeß den Maximalbedarf befriedigen zu können. Nur wenn das der Fall ist, erfolgt auch tatsächlich eine Zuteilung, sonst wird sie verweigert.
Dieses Verfahren ist anwendbar bei der Analyse des bereits entworfenen Programms, ob eine Deadlock-Gefahr existiert.
In Betriebssystemen wird es kaum benutzt, weil der maximale Betriebsmittelbedarf aller Prozesse im Voraus unbekannt sind.
Verhindern
Ein Deadlock wird unmöglich, wenn eine der vier Bedingungen nicht erfüllt ist.
Beispiele:
1) Verhinderung der Exklusive-Nutzung-Bedingung
Ein exklusives Betriebsmittel, z.B. Drucker, wird überhaupt nur von einem einzigen festgelegten Prozess benutzt, z.B. so genanntem Drucker-Dämon (Druckerspooler). Alle Zugriffe auf den Drucker gehen über den Dämon.
2) Verhinderung der Wartebedingung
Jeder Prozeß muss bei der Neuanforderung eines Betriebsmittels zunächst alle bisher belegten Betriebsmittel freigeben. Nur bei erfolgreicher Neuanforderung bekommt er auch alle bisherigen Betriebsmittel wieder zurück.
Dieses Verfahren wird im Betriebssystemen einiger Großrechner benutzt.
3) Verhinderung der Zyklische Wartebedingung
Alle Betriebsmittel werden durchnummeriert und jeder Prozess darf diese Betriebsmittel nur in aufsteigender Nummernreihenfolge reservieren. Dies stellt für die Praxis der Programmerstellung einen oft verwendbaren Ansatz dar.
Ignorieren
Deadlocks werden vom Betriebssystem nicht behandelt.
1) Dieser Strategie liegt der Annahme zu Grunde, dass Deadlocks relativ selten sind und sich daher der Aufwand für andere Behandlungsstrategien nicht lohnt.
2) Die meisten Betriebssysteme, darunter Unix und Windows, ignorieren das Problem.
3) Das Problem wird auf die Benutzer geschoben. Beispiele:
- Wenn Anwender möchte eine exklusive Datei benutzen, muss er diese Datei über einen eigenen binären Semaphor absichern.
- Falls ein Deadlock doch auftritt, muss der Benutzer oder Administrator das Problem selbst erkennen und irgendwie lösen.
4) Zumindest in Echtzeitsystemen ist diese Lösung nicht tragbar.
Deadlock - Überprüfung
Es gibt Algorithmen, mit denen man bei der Deadlock-Behandlung überprüfen kann, ob Deadlocks auftreten können.
Sie können in verschiedenen Zeitpunkten vom Betriebssystem oder vom Benutzer verwendet werden:
1) Bei der Analyse des bereits entworfenen Programms.
2) Bei jeder einzelnen Betriebsmittelanforderung.
3) In regelmäßigen Abständen.
4) Bei verdächtigen Symptomen, wenn z.B. viele Prozesse warten und die CPU unbeschäftigt ist.
Erkennungsalgorithmus
(Habermann, 1969)
Dabei ist es egal, in welcher kombinatorischen Reihenfolge die Prozesse markiert wurden.
4.5. Philosophenproblem
Das Problem der speisenden Philosophen
(E.W. Dijkstra, 1965)
1) Fünf Philosophen sitzen um einen Tisch herum.
2) Jeder hat einen Teller mit Spaghetti vor sich.
3) Zwischen den Tellern liegt je eine Gabel (5 Gabeln).
4) Zum Essen braucht ein Philosoph 2 Gabeln.
5) Ein Philosoph isst und denkt abwechselnd.
6) Wenn er hungrig wird, versucht er in beliebiger Reihenfolge die beiden Gabeln links und rechts von seinem Teller zu nehmen.
7) Hat er sie bekommen, isst er und legt sie dann wieder auf ihren Platz zurück.
Algorithmus des Philosophen
Fehlersituationen in Philosophenproblem
1) Eine verlorene Aktualisierung kann vorkommen, wenn nebeneinander sitzende Philosophen gleichzeitig zu derselben Gabel greifen. Beim Gabelzugriff sind Binärsemaphore erforderlich.
2) Ein Deadlock kann entstehen, wenn alle Philosophen eine Gabel schon haben und auf die andere Gabel warten.
3) Ein Philosoph kann verhungern, wenn einer seiner Nachbarn ständig isst.
Wegen mehreren Konfliktsituationen wurde das Philosophenproblem als die klassische Testaufgabe für Synchronisationsmechanismen verwendet.
Naive Lösung. Verhungern
Ein Verhungern (Starvation) ist eine Situation, in der alle Prozesse uneingeschränkt weiterlaufen, aber keine Fortschritte machen.
Jeder Philosoph nimmt linke Gabeln, wenn die frei ist, und legt diese zurück, wenn rechte Gabel besetzt ist. Danach wartet er eine Weile bis zum nächsten Versuch.
Wenn alle Philosophen ihre Versuche gleichzeitig machen, entsteht ein Verhungern. Dabei einige Philosophen können nie beide Gabeln erhalten.
⇒ Demo 5
Radikallösung
⇒ Demo 6
Eigenschaften:
- Durch mutex wird der Speisesaal als einen kritischen Bereich geschützt. Dabei stehen alle Gabeln jedem Philosoph zur Verfügung.
- Nur ein Philosoph darf essen. Alle andere werden beim Betreten des kritischen Bereiches blockiert.
Vorteile:
- Diese Lösung ist verklemmungsfrei.
- Das Verhungern ist ausgeschlossen.
Nachteil:
Geringe Nebenläufigkeit. Philosophen können nebenläufig denken, aber nicht essen.
Grundsätzlich könnten immer (N-1)/2 -Philosophen gleichzeitig essen, wo N die ungerade Anzahl von Philosophen ist.
Kellner-Lösung
1) Jeder der Gabeln wird eineindeutig ein binärer Semaphor zugeordnet.
2) Wenn ein Philosoph eine Gabel nehmen will, die gerade benutzt wird, wird der Philosoph blockiert.
3) Nachdem der Philosoph gegessen hat, werden Semaphoren von beiden Gabeln freigegeben.
4) Um mögliche Verklemmungen auszuschließen, kann ein Kellner (Pförtner, Gehilfe) eingeführt werden.
5) Der Kellner lässt immer nur vier Philosophen gleichzeitig in den Speisesaal. Dann hat zumindest ein Philosoph Zugriff auf zwei Gabeln.
Vorteile:
Die Lösung ist akzeptabel, Verklemmungen und Verhungern sind nicht möglich.
Sem kellner = new Sem (4);
Sem [] gabel = {new Sem (1), … }; //5 Mal
// i – Nummer des Philosophen
//N=5 -Anzahl von Philosophen
//Sem - Semaphor
void nehme(int i)
{
kellner.P();
gabel[i].P();
gabel[(i+1)%N].P();
}
void lege(int i)
{
gabel[(i+1)%N].V();
gabel[i].V();
kellner.V();
}
Sem [] gabel = {new Sem (1), … }; //5 Mal
// i – Nummer des Philosophen
//N=5 -Anzahl von Philosophen
//Sem - Semaphor
void nehme(int i)
{
kellner.P();
gabel[i].P();
gabel[(i+1)%N].P();
}
void lege(int i)
{
gabel[(i+1)%N].V();
gabel[i].V();
kellner.V();
}
⇒ Demo 7 und 8
4.6. Monitor
Grundidee:
1. Die Nutzung von Semaphoren ist recht fehleranfällig.
Beispiele:
V(); KB(); P(); oder P(); KB(); P();
Legende: KB - kritischer Bereich
2. Ein Monitor ist ein Konstrukt einer Programmiersprache.
Die Erzeugung und Anordnung von Aufrufen für Semaphoroperationen wird dem Compiler überlassen.
Definition
(Hoare und Brinch-Hansen, 1974)1) Ein Monitor ist ein Objekt (im Sinne der OOP), das die gemeinsamen Daten und die kritischen Bereiche zusammenfasst.
2) Ein Monitor kann nur von einem Prozess zu einer Zeit benutzt werden:
- Beim Eintritt in den Monitor muß der aktuelle Prozess warten, bis der Konkurrent den Monitor verlassen hat.
- Dafür wird jedem Monitor implizit ein binärer Semaphor und eine Monitor-Warteschlange (entry queue) zugeordnet.
3) Mit Hilfe des Monitors wird der wechselseitige Ausschluss automatisch realisiert.
Java-Monitor
1. Ein Java-Objekt ist automatisch ein Java-Monitor, wenn es
- eine synchronized-Methode oder
- einen synchronized-Codeblock enthält.
2. Beim Eintritt eines Threads in einen synchronized-Bereich sperrt dar implizite Semaphor alle synchronized-Bereiche des Objekts.
Nur ein Thread darf zu einer Zeit eine der Methoden aufrufen.
3. Java-Monitor ist jedoch kein reiner Monitor (nach Hoare und Brinch-Hansen):
- nicht alle public-Methoden zwingend als synchronized deklariert sein müssen,
- nicht nur private Variablen zugelassen sind.
Wechselseitiger Ausschluss mit dem Java-Monitor, Beispiel
Quelltextvor der Kompilierung
public class Konto {
int stand;
synchronized public void add (int b) {
stand += b;
}
synchronized public void sub (int b) {
stand -= b;
}
}
int stand;
synchronized public void add (int b) {
stand += b;
}
synchronized public void sub (int b) {
stand -= b;
}
}
Bytecode nach der Kompilierung
//add
P();
stand += b; //KB
V();
//sub
P();
stand += b; //KB
V();
P();
stand += b; //KB
V();
//sub
P();
stand += b; //KB
V();
Warten im Monitor
Grundidee:
Ein Monitor kann nicht nur für den wechselseitigen Ausschluss sondern auch für die Verwaltung von gemeinsamen Betriebsmitteln verwendet werden.
Realisierung:
Dafür benötigt ein Monitor zusätzliche Mittel, um Threads sperren zu können, falls Threads auf Betriebsmittel warten müssen:
1) Bedingungswarteschlange,
2) Methoden, welche auf diese Bedingungswarteschlange wirken.
Warten im Java-Monitor
1) Jedem Java-Monitor werden zwei namenlose Warteschlangen vom Compiler implizit angelegt:
- Eine Warteschlange (entry queue) beinhaltet die blockierte Threads, die den Monitor „von außen“ betreten wollen.
- den Monitor schon betreten haben und
- auf die Erfüllung einer Bedingung warten müssen.
2) Jeder Java-Monitor besitzt drei zusätzliche Methoden wait, notify und notifyAll, die:
- von der Klasse „Object“ geerbt werden,
- auf diese Bedingungswarteschlange wirken können,
- nur innerhalb von synchronized-Methoden aufgerufen werden dürfen, wann der Monitor bereits gesperrt ist.
Methode wait
1) Der Aufrufer-Thread wird schlafen gelegt, nämlich:
- wird blockiert,
- wird in die Bedingungswarteschlange des Monitors eingefügt,
- wird solange warten, bis er durch den Aufruf in einem anderen Thread von notify oder notifyAll aufgeweckt wird.
2) Der Monitor wird freigegeben. Sonst bleibt er für immer blockiert. Einem weiteren Thread wird erlaubt das Betreten des Monitors.
Methoden notify und notifyAll
1) Die Metode notify weckt einen Thread auf:
- Einer der Threads wird aus condition queue entfernt und in entry queue eingefügt.
- Der Java–Monitor garantiert kein FIFO. Durch notify wird ein beliebiger Thread aufgeweckt.
2) Der aufgeweckte Thread läuft nur dann weiter, wenn er nach dem Warten in entry queue diesen Monitor für sich sperren kann.
3) Ist die innere Warteschlange leer, bleibt der Aufruf ohne Wirkung.
4) Die Methode notifyAll weckt alle im Monitor blockierten Threads auf.
5) notify und notifyAll wirken nur auf diejenige Threads, die:
- in diesem Monitor sind und
- sich durch Aufruf der wait-Methode selbst blockiert haben.
Erzeuger-Verbraucher-Problem mit dem Monitor
Attribute und Methode der Klasse Lager:
int kap=5; //Lagerkapazität
int anz=0; //Anzahl der Einträge
synchronized void insert(int w) {
if(anz==kap) wait();
put(w); //KB
anz++;
if(anz==1) notify();
}
synchronized int remove() {
if(anz==0) wait();
int w=get(); //KB
anz--;
if(anz==kap-1) notify();
return w;
}
int anz=0; //Anzahl der Einträge
synchronized void insert(int w) {
if(anz==kap) wait();
put(w); //KB
anz++;
if(anz==1) notify();
}
synchronized int remove() {
if(anz==0) wait();
int w=get(); //KB
anz--;
if(anz==kap-1) notify();
return w;
}
⇒ Demo 9 und 10
Methoden get und put greifen direkt auf die Datenstruktur und enthalten den kritischen Bereich (KB).
Vorteile und Nachteile
1. Monitore sind strukturiert und damit wesentlich sicherer.
- Der gesamte Code, der den kritischen Bereich manipuliert, an einer Stelle zusammengefasst.
- Ein Monitor ist das höherstufige Synchronisationsprimitiv als Semaphor.
2. Die Nutzung des Monitors ist recht einfach.
- Der Compiler verwendet die richtige Reihenfolge von P- und V-Operationen.
- Monitore machen die Programmierung sehr viel fehlerunanfälliger als Semaphoren.
Nachteile:
1. Monitor ist ungeeignet für Systeme mit verteiltem Speicher.
2. Schachteln von Monitoren kann zu Deadlocks führen.
3. Monitore müssen von einer Programmiersprache angeboten werden, während Semaphore über Systemaufrufe realisiert werden können.
CategoryBSys
