Zur Erinnerung Versuch 2 als Softwarelösung
Warum scheiterte dieser Versuch?
Weil Testen und Setzen von Flags nicht in einem einzigen Schritt durchführbar:
Prozesswechsel zwischen Testen und Setzen ist möglich. WS 2009/10 * /* Prozess 0 */
wiederhole
{
solange (flag[1] = true)
tue nichts;
flag[0] := true;
/* kritischer Abschnitt */
flag[0] := false;
/* nichtkrit. Abschnitt */
} /* Prozess 1 */
wiederhole
{
solange (flag[0] = true)
tue nichts;
flag[1] := true;
/* kritischer Abschnitt */
Flag[1] := false;
/* nichtkrit. Abschnitt */
}
Wechselseitiger Ausschluss in Hardware
Neues Konzept:
Einführung atomarer Operationen.
Hardware garantiert atomare Ausführung.
Testen und Setzen zusammen bilden eine atomare Operation:
Definiere neuen Befehl TSL: Test and Set Lock.
Da TSL ein einziger Befehl ist, kann ein Prozesswechsel nicht zwischen Testen und Setzen erfolgen (nicht “mitten im Befehl”).
WS 2009/10 *
Wechselseitiger Ausschluss in Hardware
Befehl TSL RX, LOCK mit Speicheradresse LOCK und Register RX hat folgende Wirkung:
RX = Speicher[LOCK]; Speicher[LOCK] := 1
Ein Befehl, d.h. atomare Ausführung.
Prozesse, die Zugriff auf den kritischen Abschnitt erhalten wollen, führen folgende Befehle aus:
enter_region: TSL, RX, LOCK // kopiere Lock-Variable und setze Lock CMP RX, #0 // War Lock-Variable = 0? (CMP = compare) JNE enter_region // Wenn Lock schon gesetzt war -> Schleife (JNE = jump if not equal)
... // Fortfahren und Betreten des krit. Abschnitts
Prozesse, die den kritischen Abschnitt verlassen, führen folgenden Befehl aus:
STOREI LOCK, #0 // Speicher[LOCK] := 0 (STOREI = store immediate) WS 2009/10 *
Wechselseitiger Ausschluss im Betriebssystem
Folgerung:
Um aktives Warten zu verhindern, muss wechselseitiger Ausschluss ins Betriebssystem integriert werden!
Idee: Statt aktiv zu warten, blockiere Prozesse einfach!
Neuer Systemaufruf sleep(lock)
Nach Verlassen des kritischen Abschnitts weckt der verlassende Prozess einen anderen Prozess auf, der auf Erlaubnis wartet, den kritischen Abschnitt zu betreten (sofern ein solcher Prozess vorhanden ist).
Neuer Systemaufruf wakeup(lock)
Parameter lock wird nur gebraucht, um Aufrufe für den gleichen kritischen Abschnitt einander zuzuordnen.
Eine Warteschlange pro kritischem Abschnitt WS 2009/10 *
Mutex
Mutex = Mutual Exclusion
Vor dem Eintritt in einen kritischen Abschnitt wird die Funktion mutex_lock(lock) aufgerufen.
testset(lock) führt atomare TSL-Operation aus; liefert true gdw. Lockvariable vorher 0 war.
WS 2009/10 * function mutex_lock(lock)
{
solange (testset(lock) = false)
{
sleep(lock);
}
return;
}
Mutex
Nach Verlassen des kritischen Abschnitts wird mutex_unlock(lock) aufgerufen.
Es muss eine Warteschlange für Prozesse geben, die auf lock warten.
Nach wakeup(lock) wird der erste Prozess in der Queue bereit (aber nicht notwendigerweise aktiv -> Scheduler-Algorithmus!).
Die Variable lock heißt Mutexvariable bzw. kurz Mutex. WS 2009/10 * function mutex_unlock(lock)
{
unset(lock); // lock wird freigegeben
wakeup(lock);
return;
}
Das Produzenten-Konsumenten Problem
Typisches Problem bei nebenläufigen Prozessen:
Gemeinsamer Puffer
Einige Prozesse schreiben in den Puffer (“Produzenten”)
Einige Prozesse lesen aus dem Puffer (“Konsumenten”)
Prozedur insert_item schreibt Objekt in Puffer.
Prozedur remove_item entfernt Objekt aus Puffer.
Puffergröße ist beschränkt und Puffer kann leer sein.
Wenn Puffer voll ist, dann sollten Produzenten nicht einfügen. Aus Effizienzgründen: Blockieren der Produzenten, die einfügen wollen.
Wenn Puffer leer ist, sollten Konsumenten nichts entfernen. Aus Effizienzgründen: Blockieren der Konsumenten, die entfernen wollen. WS 2009/10 *
Das Produzenten-Konsumenten Problem
Lösungsansatz:
Gemeinsame Variable count für die Anzahl der Elemente im Puffer
Initialer Wert 0
sleep() und wakeup()
Anfangs schlafen die Konsumenten (Puffer ist leer).
WS 2009/10 *
Das Produzenten-Konsumenten Problem
WS 2009/10 * Prozedur producer
{
...
wiederhole
{
item = produce_item(); //produziere nächstes Objekt
wenn (count = MAX_BUFFER) //schlafe, wenn Puffer
sleep(producer); //voll
insert_item(item) // Einfügen in Puffer
count = count + 1;
wenn (count = 1) // wenn Puffer vorher leer:
wakeup(consumer); // wecke Konsumenten
}
}
Das Produzenten-Konsumenten Problem
WS 2009/10 * Prozedur consumer
{
...
wiederhole
{
wenn (count = 0) // schlafe, wenn Puffer
Sleep(consumer); // leer
item = remove_item(); // Entferne aus Puffer
count = count -1;
wenn (count = MAX_BUFFER – 1) // wenn Puffer voll
wakeup(producer); // wecke Produzenten
consume_item(item); // konsumiere Objekt
}
} Ist diese Lösung korrekt???
Das Produzenten-Konsumenten Problem
Mögliche Probleme:
Zwei Konsumenten: 1 Element im Puffer
Konsument 1 entnimmt Element und wird unterbrochen bevor er count auf 0 setzen kann.
Konsument 2 wird aktiv aber der Puffer ist leer! (count immer noch 1)
Fehler!
Zwei Konsumenten: Puffer ist voll.
count == MAX_BUFFER
Konsument 1 entnimmt Element und führt count = count–1; aus und wird dann unterbrochen (count == MAX_BUFFER-1).
Konsument 2 wird aktiv, entnimmt ein Element und reduziert count.
Problem: Produzent wird nie mehr geweckt, da Bedingung
wenn (count = MAX_BUFFER – 1)
nie mehr erfüllt wird! WS 2009/10 *
Das Produzenten-Konsumenten Problem
Ein Produzent und ein Konsument
Konsument gibt Prozessor ab nach
wenn(count = 0)
wenn Puffer leer ist
Dann fügt der Produzent ein Objekt ein, count = 1.
Aufwecken des Konsumenten geht verloren, da er noch gar nicht schläft.
Nach nächstem Prozesswechsel: Konsument schläft für immer.
Wenn Puffer voll wird, schläft auch der Produzent für immer.
Deadlock
Problem:
wenn (count = 0) sleep(consumer)
ist keine atomare Operation! WS 2009/10 *
Das Produzenten-Konsumenten Problem
Die elegante Lösung des Produzenten-Konsumenten Problems ist die Nutzung eines Semaphor.
Dijkstra (1965)
Entwickelt zur Synchronisation von Prozessen.
Konzept:
Integer-Variable mit drei Operationen:
Initialisierung mit nicht-negativen Wert
down() Operation
up() Operation WS 2009/10 *
Wechselseitiger Ausschluss mit Semaphoren
Voraussetzungen:
Es existiert ein Semaphor s.
countS ist auf 1 initialisiert.
n Prozesse sind gestartet, konkurrieren um kritischen Abschnitt. WS 2009/10 * /* Prozess i */
wiederhole
{
down(s);
/* kritischer Abschnitt */
up(s);
/* nichtkritischer Abschnitt */
}
Wechselseitiger Ausschluss mit Semaphoren
Beispiel:
Semaphor wird mit 1 initialisiert.
Prozess 1 geht in kritischen Abschnitt:
down(s) -> Semaphor-Zähler wird 0
Prozess 2 will in den kritischen Abschnitt:
down(s) -> Semaphor-Zähler wird -1
Prozess 2 wird blockiert und in die Warteschlange eingefügt.
Prozess 3 will in den kritischen Abschnitt:
down(s) -> Semaphor-Zähler wird -2
Prozess 3 wird blockiert und in die Warteschlange eingefügt.
Prozess 1 verlässt kritischen Abschnitt:
up(s) -> Semaphor-Zähler wird -1
Zähler <= 0, d.h. ein Prozess wird der Warteschlange entnommen und wird bereit.
WS 2009/10 *
Wechselseitiger Ausschluss mit Semaphoren
Auf 1 initialisierte Semaphore heißen binäre Semaphore.
Behandlung mehrfach nutzbarer Ressourcen (m-fach) ist möglich:
durch Initialisierung countS = m.
Interpretation von counts:
Falls countS ≥ 0:
countS gibt die Anzahl der Prozesse an, die down(s) ausführen können ohne zu blockieren (wenn nicht zwischenzeitlich up(s) ausgeführt wird).
Falls countS < 0:
|countS| ist die Anzahl der wartenden Prozesse in queueS.
WS 2009/10 *
Das Produzenten-Konsumenten Problem mit Semaphoren
Comments