Operating System: Critical Regions

Study Notes

Vier Bedingungen für wechselseitigen Ausschluss:
- Kein Prozess soll gleichzeitig in zwei kritischen Regionen sein
- Keine Annahmen über Geschwindigkeiten oder Anzahl von CPUs
- Kein Prozess außerhalb seiner kritischen Region soll einen anderen Prozess blockieren
- Kein Prozess soll ewig auf den Zugriff zu seiner kritischen Region warten müssen
Kritische Regionen werden definiert als Programmteile, die auf gemeinsam genutzte Ressourcen zugreifen
Zu jedem Zeitpunkt darf nur ein Prozess Zugriff auf eine exklusiv verwendbare Ressource haben

Prozesse A und B, die jeweils in ihre kritische Region eintreten wollen
Prozess A betritt seine kritische Region vor Prozess B und blockiert dessen Versuch
Erst nach Austritt von Prozess A erhält Prozess B Zugriff zu seiner kritischen Region

Idee "Unterbrechungen sperren" scheitert, weil der rechnende Prozess nicht alle Unterbrechungen sperren darf
Idee "Sperrvariable einführen" scheitert, weil dies zu einer zusätzlichen kritischen Region führt

Peterson's Lösung für wechselseitigen Ausschluss:
- Jeder Prozess meldet sein Interesse in einem gemeinsamen Feld an
- Nur wenn der andere Prozess kein Interesse meldet, darf der Prozess in seine kritische Region eintreten
Spinlocks nennt man Sperren, die durch aktives Warten realisiert werden
Hardware-Unterstützung erleichtert den wechselseitigen Ausschluss

Entering and leaving a critical region using the TSL instruction
Unterstützung in der Hardware durch eine spezielle, unteilbare ISA-Instruktion namens TestAndSetLock (TSL)
Die TSL-Instruktion ist unteilbar, d.h. keine Unterbrechung zwischen Speicherzelle auslesen, Wert prüfen und neuen Wert zurück schreiben
Der Speicherbus ist gesperrt, sodass kein DMA-Transfer möglich ist und keine andere CPU auf den Speicher zugreifen kann

Producer-Consumer-Problem mit fataler Rassebedingung
Lösung mit Sperren für Prozesse, die ihre kritische Region nicht betreten können
Die down-Operation prüft, ob der Zähler > 0 ist und reduziert ihn um 1; bei Zähler = 0 blockiert sie den Prozess
Die up-Operation prüft, ob der Zähler 0 ist und weckt einen wartenden Prozess; bei > 0 wird der Zähler weiter erhöht

Zur Realisierung von gegenseitigem Ausschluss können binäre Semaphoren eingesetzt werden, die dann als Mutex bezeichnet werden
Mutexe dienen rein dem gegenseitigen Ausschluss und zählen nicht im Gegensatz zu Semaphoren
Die beiden Operationen mutex_lock und mutex_unlock arbeiten ähnlich wie down und up bei Semaphoren

Programmierung mit Semaphoren ist eine anspruchsvolle Aufgabe und kleine Fehler haben große Wirkung
Zur Vereinfachung der Programmierung korrekt synchronisierter Prozesse und Threads wurde ein höherstufiger Synchronisationsmechanismus namens Monitor eingeführt
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

Wartet auf ein Signal auf die Zustandsvariable, blockiert den Prozess im Monitor und ermöglicht einem anderen Prozess das Betreten des Monitors
Signal sendet ein Signal an den auf die entsprechende Zustandsvariable wartenden Prozess