Kritische Regionen in der Informatik

Study Notes

Vier Bedingungen für den gegenseitigen Ausschluss:
- Kein Prozess darf gleichzeitig in der kritischen Region sein
- Keine Annahmen über Geschwindigkeiten oder Anzahl von CPUs
- Kein Prozess außerhalb seiner kritischen Region darf einen anderen blockieren
- Kein Prozess darf ewig auf den Eintritt in die kritische Region warten
Kritische Regionen vermeiden Ressourcenkonflikte durch wechselseitigen Ausschluss
Ein Prozess darf nur dann in die kritische Region eintreten, wenn keine anderen Prozesse darin sind

Petersons Lösung für den gegenseitigen Ausschluss:
- Jeder Prozess meldet sein Interesse an der kritischen Region an
- Nur wenn der andere Prozess kein Interesse mehr hat, darf der Prozess in die kritische Region eintreten
Spinlocks sind nur in wenigen Ausnahmefällen sinnvoll
Hardware-Unterstützung erleichtert den gegenseitigen Ausschluss

Sleep und Wakeup verwenden Prozesse, die ihre kritische Region nicht betreten können
Sleep blockiert den aufrufenden Prozess, bis auf ihn ein Wakeup-Aufruf erfolgt
Erzeuger-Verbraucher-Problem:
- Der Erzeuger legt sich schlafen, wenn der Puffer voll ist
- Der Verbraucher legt sich schlafen, wenn der Puffer leer ist
- Wettlaufsituation: Der Zugriff auf den Zähler kann zu Rennen führen

Semaphoren verwenden Zähler von Weckrufen, um den gegenseitigen Ausschluss zu ermöglichen
down-Operation: Prüft, ob der Zähler > 0 ist und reduziert ihn um 1; bei Zähler = 0 blockiert sie den Prozess
up-Operation: Prüft, ob der Zähler 0 ist und weckt einen wartenden Prozess; bei > 0 wird der Zähler weiter erhöht
Semaphoren lassen sich für den gegenseitigen Ausschluss und das Produzent-Konsument-Problem verwenden

Ein Monitor ist eine Sammlung von Funktionen und nur über diese Funktionen zugängliche interne Variablen
Ein Monitor zeichnet sich dadurch aus, dass zu jedem Zeitpunkt maximal ein Prozess im Monitor aktiv sein kann
Wait und signal sind Zusatzoperationen im Monitor:
- Wait wartet auf ein Signal auf die Zustandsvariable und blockiert den Prozess im Monitor
- Signal sendet ein Signal an den auf die entsprechende Zustandsvariable wartenden Prozess### Monitor
Eine Zustandsvariable zählt die Signal-Aufrufe nicht wie ein Semaphor, sodass Signale, auf die nicht gewartet wird, verloren gehen.
Ein entsprechender wait-Aufruf kehrt zurück, wenn ein Signal eintrifft, und der Prozess erhält den exklusiven Zugriff auf den Monitor zurück für die Programmfortsetzung.

Ein Monitor kann nur einen Prozess gleichzeitig aktiv haben.
Ein Puffer hat eine bestimmte Anzahl von Slots (N).
Ein Producer erstellt ein Item und gibt es an den Monitor zur Einfügung in den Puffer.
Ein Consumer nimmt ein Item aus dem Puffer und verarbeitet es.

Die Klasse ProducerConsumer enthält einen Monitor PCMonitor und zwei Threads Producer und Consumer.
Der Producer produziert ein Item und fügt es dem Puffer hinzu, wenn der Puffer nicht voll ist.
Der Consumer nimmt ein Item aus dem Puffer und verarbeitet es, wenn der Puffer nicht leer ist.
Wenn der Puffer voll oder leer ist, wird der Producer oder Consumer.sleep() und wird von einem anderen Thread geweckt.

Message Passing ist ein Mechanismus zur Interprozesskommunikation zwischen Computersystemen.
Nachrichten können im Gegensatz zu lokalen Signalen verloren gehen.
Das Senden einer Nachricht muss wiederholt werden können.
Empfangene Nachrichten müssen unterschieden werden können um Kopien zu entdecken.
Zur Abstimmung von Sender und Empfänger sind Bestätigungen nötig.

Beim Leser-Schreiber-Problem ist es akzeptabel, wenn mehrere Prozesse gleichzeitig lesen.
Wenn jedoch ein Prozess schreibenden Zugriff verlangt, dann darf kein anderer Prozess (nicht einmal lesend) zugreifen.
Leser und Schreiber erwirken exklusiven Zugriff auf ihre kritische Region durch Aufruf von down.
Die Leser unterhalten einen Referenzzähler rc der gleichzeitigen Leserzugriffe, den sie entsprechend erhöhen und vermindern.