Operating System: Critical Regions

Kritische Regionen

• 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

Wechselseitiger Ausschluss mit kritischen Regionen

• 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

Trugschlüsse

• 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

Wechselseitiger Ausschluss mit Busy Waiting

• 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

TSL-Instruktion

• 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

Sleep and Wakeup

• 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

Mutex

• 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

Monitore

• 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

Wait und Signal

• 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