Wiederholung : Erläutern Sie Beispiele für die drei Welten Betriebs-, Programmier- und Dienstleistungssysteme!
Metasteuerung
Prozesse können gemeinsam eine Aufgabe lösen
Synchronisation ist notwendig, da ein Prozess nicht in einen anderen „hineinschauen“ kann, und somit nicht erfahren kann, „wie weit“ dieser ist
Prozesse sind Steuerungen, die durch eine
Metasteuerung
Metasteuerung ist Teil des Betriebssystems
Was ist ein kritischer Abschnitt ?
Ein Kritischer Abschnitt ist ein zeitlicher Bereich, in welchem mindestens zwei Prozesse auf das gleiche Betriebsmittel zugreifen und mindestens eines davon schreibt. (Zeitkritischer Ablauf)
Ein kritischer Abschnitt ist eine Teilprozessfolge, in deren Verlauf Werte eines von einem Teilprozess genutzten Betriebsmittels durch einen anderen Prozess geändert werden könnten.
Was ist nötig, damit keine Inkonsistenz auftritt?
1. zu jedem Zeitpunkt darf nur ein Prozess im k. A. sein
2. kein Prozess im k. A. darf Prozesse außerhalb beeinflussen
3. alle Prozesse müssen in endlicher Zeit den k. A. betreten können, wenn sie es wollen
4. die Lösung muss unabhängig von externen Faktoren sein (Ausführungsgeschwindigkeit, Prozessoranzahl, ...)
Erläuterung von Begriffen
Die Verwaltung des kritischen Abschnitts kann zentral (durch eine zentrale Instanz wie das BS oder einen Server) oder dezentral (durch Kooperation der Prozesse selbst) erfolgen.
Atomare Funktionen sind Funktionen, die in ihrer Ausführung nicht durch Scheduling unterbrochen werden können. Ebenso können Speicherzugriffe, die sie eventuell ausführen, nicht gestört werden.
Für den k.A. sind immer zwei atomare Funktionen notwendig.
P() ... down() ... wait()
(passerr)
Wird beim Betreten des kritischen Abschnitts aufgerufen.
Teilt der Verwaltung (zentral oder dezentral) den Wunsch mit, den kritischen Abschnitt zu betreten.
P() wartet, bis der kritische Abschnitt frei ist, also keine andere Aktivität sich darin aufhält.
Kehrt P() zurück, betritt die Aktivität den k.A. – er ist somit für alle anderen Aktivitäten gesperrt.
V() ... up() ... signal()
(verlaat)
Wird beim Verlassen des kritischen Abschnitts aufgerufen.
Teilt der Verwaltung (zentral oder dezentral) mit, dass der kritische Abschnitt abgearbeitet wurde.
V() erlaubt, dass andere Aktivitäten den kritischen Abschnitt betreten.
Nachdem V() zurückgekehrt ist, hat die Aktivität den k.A. verlassen.
dezentrale Steuerung
P() und V() müssen bei der dezentralen Steuerung …
1. ... von den Prozessen selbst implementiert sein und aufgerufen werden und
2. ... über einen (hier nicht näher diskutierten) Kommunikationsmechanismus (evtuell IPC) verfügen (z.B. über eine gemeinsam genutzte Variable, die durch einen Prozess initialisiert wird).
Wie arbeitet Striktes Alternieren? (Ping Pong)
P1 |
P2 |
|
Initialisierung int var = 1; |
||
P(): | while (var == 2); | while (var == 1); |
/* kritischer Abschnitt */ | ||
V(): | var = 2; | var = 1; |
var gibt an, welcher Prozess den kritischen Abschnitt betreten darf
P2 kann erst beginnen, wenn P1 V() verlassen hat.
P1 muss immer zuerst ausgeführt werden.
Wenn P1 ausgeführt wurde, dann muss erst P2 abgearbeitet werden, bevor P1 den k.A. wieder betreten
kann und umgekehrt. „Ping-Pong“
Das heißt, mehrmaliges Betreten des k.A. hintereinander durch einen Prozess ist nicht möglich.
Variante 2
P1 |
P2 |
|
Initialisierung int var = 0; |
||
P(): | while (var == 1); | while (var == 1); |
/* kritischer Abschnitt */ | ||
V(): | var = 0; | var = 0; |
Beliebige Folge des Eintritts in den kritischen Abschnitt möglich.
Wird einem Prozess nach der While
-Schleife der Prozessor entzogen, dann können beide Prozesse gleichzeitig in den k.A. gelangen.Gibt es mehr als einen Prozessor, dann wird das Ganze noch kritischer.
V
erstoß gegen Punkt 1, da 2 Prozesse zur selben Zeit den k. A. betreten könnenVariante 3 Zwei Variablen
P1 |
P2 |
|
Initialisierung int var1 = Var2 = 0; |
||
P(): | while (var1 == 1); /*Warten*/ | while (var2 == 1); /*Warten*/ |
var1 = 1; | Var2 = 1; | |
/* kritischer Abschnitt */ | ||
V(): | var1 = 0; | var2 = 0; |
varx==0 Prozess x ist nicht im kritischen Abschnitt.
varx==1 Prozess x ist im kritischen Abschnitt.
komplexer als Variante 2, aber gleiches Fehlerpotenzial
Variante 4 Lifelock
P1 |
P2 |
|
Initialisierung int var1 = Var2 = 0; |
||
P(): | var1 = 1; | Var2 = 1; |
while (var1 == 1); /*Warten*/ | while (var2 == 1); /*Warten*/ | |
/* kritischer Abschnitt */ | ||
V(): | var1 = 0; | var2 = 0; |
Verstoß gegen Punkt 3, da im schlimmsten Fall keiner der beiden Prozesse den kritischen Abschnitt betreten kann („Verhungern“)
Variante 5 "Bitte nach Ihnen"
P1 |
P2 |
|
Initialisierung int var1 = Var2 = 0; |
||
m1: var1 = 1; | m2: var2 = 1; | |
if (var2 == 1) | while (var1 == 1); | |
{ | { | |
P(): | var1 = 0; | var2 = 0; |
goto m1 | goto m2 | |
} | } | |
/* kritischer Abschnitt */ | ||
V(): | var1 = 0; | var2 = 0; |
„Verhungern“ bei absolut gleichzeitigem Fortschreiten
Stellt ein Prozess fest, dass er nicht in den kritischen Abschnitt kann, so zieht er seine Anforderung kurzzeitig zurück, bevor er es wieder versucht.
Variante 6 Dekker-Algorithmus
P1 |
P2 |
|
Initialisierung int var1 = var2 = 0; |
||
int turn =1; |
||
var1 = 1; | var2 = 1; | |
if (var2 == 1) | while (var1 == 1); | |
{ | ||
P(): | var1 = 0; | var2 = 0; |
while ( turn == 2 ) | while ( turn == 1 ) | |
var1 = 1; | var2 = 1; | |
} | } | |
/* kritischer Abschnitt */ | ||
V(): | var1 = 0; turn = 2; | var2 = 0; turn = 1; |
„Dekker-Algorithmus“
Ist eine vollständige und korrekte Lösung.
Einführung einer 3. Variablen turn.
turn gibt an, welcher Prozess bei exakter Gleichzeitigkeit den Vorrang erhält.
Es ist immer der, der am längsten wartet.
Bei unterschiedlicher Abarbeitungszustand entspricht diese Variante ihrer Vorgängervariante.
Variante 6 Petersen-Algorithmus
P1 |
P2 |
|
Initialisierung int var1 = var2 = 0; |
||
int turn =1; |
||
var1 = 1; | var2 = 1; | |
if (var2 == 1) | while (var1 == 1); | |
{ | ||
P(): | var1 = 0; | var2 = 0; |
while ( turn == 2 ) | while ( turn == 1 ) | |
var1 = 1; | var2 = 1; | |
} | } | |
/* kritischer Abschnitt */ | ||
V(): | var1 = 0; turn = 2; | var2 = 0; turn = 1; |
MERKE: Alle dezentralen Lösungen haben den Nachteil, dass Prozessorzeit durch das “aktive” Warten “verschwendet” wird!
Stürzt ein Prozess im kritischen Abschnitt ab, so hat er ihn ja nicht verlassen, der k.A. bleibt belegt und die anderen sind automatisch deadgelockt.
Ein Semaphor ist eine nichtnegative Ganzzahl, mit der Verwaltungsinformationen von Prozessen (Threads) verbunden sind.
Quasistandard: Semaphor == 0 BM ist belegt
Semaphor > 0 BM ist frei
Beim kritischen Abschnitt gibt es maximal einen Benutzer, daher nimmt man hier binäre Semaphoren {0, 1}
Semaphoren haben Zeiger/Anker für die Prozesse in der Warteschlange (Liste), die durch die Semaphore als „wartend” gekennzeichnet werden und damit temporär aus dem Scheduling entfernt werden.
P() Semaphore prüfen, ob größer als 0 (BM frei); wenn ja, Wert der Semaphore dekrementieren, wenn nein, Prozess in Wartepool der Semaphore einreihen.
V() Befinden sich Prozesse im Wartepool der Semaphore? Wenn ja, einen beliebigen auswählen und wieder als „bereit“ markieren (also wieder ins Scheduling einbinden); wenn nein, Wert der Semaphore inkrementieren.
P(sem) //Probiere in kritischen Abschnitt einzutreten { if (sem == 0) sleep(sem); //Prozess auf wartend setzen sem--; } V(sem) //Verlasse kritischen Abschnitt { sem++; //Zugang wieder freigeben wakeup(sem); }sleep und wakup sind Systembefehle, welche einen Prozess Schlafenlegen oder Aufwecken.
Prozess A | Prozess B |
int sem = 1; //zwei Prozesse |
|
While (1) { P(sem); // kritischer Abschnitt V(sem); } |
While (1) { P(sem); // kritischer Abschnitt V(sem); } |
Beispiele:
Erzeuger-Verbraucher-Problem
Leser-Schreiber-Problem
Problem der wartenden Friseure
Problem der dinierenden Philosophen
Ein Prozess mit niedriger Priorität ist ein einem (durch P() und V() gesicherten) kritischen Abschnitt. Was passiert, wenn jetzt ein Prozess mit höherer Priorität ebenfalls diese k.A. betreten will? Welche Rolle spielt dabei die Anzahl vorhandener Prozessoren?
Ein Prozess befindet sich in einem kritischen Abschnitt, der Operationen auf den Speicher schützt. Er hat beim Betreten des Abschnittes P() aufgerufen, und wird beim Verlassen V() rufen. Was passiert, wenn ein weiterer Prozess diesen k.A. betreten will, ohne jedoch vorher P() zu rufen?
const N 100 //buffer size int mutex = 1 //Für Kritischen Abschnitt int empty = N //Anfangs leerer Buffer int full = 0 //noch keine Daten im Buffer void ErzeugerProzess() { int item; while(1) { iNode = CreateItem(); P(empty); P(mutex); Insert(item) //Critical Section V(mutex); //Mutex wieder erhöhen V(full); //full=full+1 } } void VerbraucherProzess() { int item; while(1) { P(full); P(mutex); Item = RemoveItem(); //Critical Section V(mutex); V(empty); MakeSomething(Item); } } Der Semaphor mutex verhindert, daß gleichzeitig Verbraucher und Erzeuger im kritischen Abschnitt sind. Denn falls der Erzeuger gerade eingetreten ist, ist der Semaphore mutex null. Versucht nun der Verbraucher in den kritischen Abschnitt einzutreten, muss er bei P(mutex) warten, da der mutex noch null ist. Um nun zu Verhindern das aus einer leeren Liste gelesen oder in eine volle geschrieben wird, werden hier elegant zwei weitere Semaphoren verwendet, welche das Vorhandensein von freien Plätzen (empty) und belegten Plätzen (full) zählen.