Semaphoren: Synchronisation und Philosophendiner

Semaphoren

Synchronisation ist ein Werkzeug, um das Problem der kritischen Abschnitte und Synchronisationsprobleme zu lösen. Eine Semaphore ist eine Integer-Variable, auf die nur durch zwei Operationen zugegriffen werden kann: WAIT und SIGNAL. Wenn ein Prozess den Wert verändert, können andere dies nicht gleichzeitig tun. Die Semaphore wird mit einem nicht-negativen Wert initialisiert. Durch WAIT (auch P genannt) wird der Wert vermindert; wird der Wert negativ, so wird der Prozess blockiert. Durch SIGNAL (auch V genannt) wird der Wert erhöht; wenn der Wert nicht mehr negativ ist, wird ein blockierter Prozess entsperrt.

Die Definition ist:

P(s) {
    while (s <= 0) ;   /* busy wait */
    s--;
}

V(s) {
    s++;
}

Betriebssysteme verwenden Semaphoren, um den Zugang zu einem kritischen Abschnitt oder die gemeinsame Nutzung von Ressourcen zu kontrollieren. Die Semaphore wird auf einen Wert initialisiert, der der Anzahl der verfügbaren Ressourcen entspricht. Jeder Prozess, der eine Ressource nutzen möchte, führt eine WAIT-Operation auf der zugehörigen Semaphore aus; wenn er die Ressource freigibt, führt er eine SIGNAL-Operation aus. Wenn die Anzahl 0 ist, sind alle Ressourcen benutzt, und Prozesse, die Ressourcen verwenden wollen, werden gesperrt, bis der Zähler wieder größer als 0 ist.

Umsetzung

Eines der allgemeinen Probleme ist, dass, wenn ein Prozess kein Mittel zur Verfügung hat, der Prozess aktiv wartet ("busy waiting") und dadurch CPU-Zyklen verschwendet werden. Um dieses Problem zu vermeiden, verwendet man das Blockier-/Weck-Verfahren: Wenn ein Prozess keine Ressource zur Verfügung hat, blockiert er sich selbst und wird in eine Warteschlange eingereiht. Dabei wird eine Blockierungsfunktion (z. B. sleep) aufgerufen, und der Prozess wechselt in den Zustand "wartend". Die Kontrolle geht an den CPU-Scheduler, der einen anderen Prozess zur Ausführung auswählt.

Ein blockierter Prozess wird wieder gestartet, wenn ein anderer Prozess eine SIGNAL-Operation auf der betreffenden Semaphore ausführt. Dabei erfolgt eine Wakeup-Operation, die den Zustand des Prozesses von "wartend" auf "bereit" ändert. Dieser Prozess wird dann in die Ready-Warteschlange gestellt.

Das Problem der Philosophen

Stellen Sie sich fünf Philosophen vor, die ihr Leben mit Denken und Essen verbringen. Sie teilen einen runden Tisch mit fünf Plätzen, einen für jeden Philosophen. In der Mitte des Tisches steht eine Schale mit Reis und fünf einzigartige Essstäbchen. Wenn ein Philosoph denkt, interagiert er nicht mit seinen Nachbarn. Wenn ein Philosoph hungrig wird, versucht er, die beiden benachbarten Stäbchen zu nehmen. Er kann jedoch nur ein Stäbchen zurzeit nehmen und kann kein Stäbchen nehmen, das bereits in den Händen eines anderen ist. Wenn er beide Stäbchen hat, kann er essen; nach dem Essen legt er die Stäbchen zurück und beginnt wieder zu denken.

Dies ist ein klassisches Synchronisationsproblem und ein Beispiel für eine große Klasse von Nebenläufigkeitssteuerungsproblemen. Es veranschaulicht die Notwendigkeit, mehrere Ressourcen mehreren Prozessen zuzuordnen. Als Lösung kann jedes Stäbchen durch eine Semaphore dargestellt werden. Versucht ein Philosoph, ein Stäbchen zu nehmen, führt er WAIT auf der zugehörigen Semaphore aus; die Freigabe der Stäbchen erfolgt mittels SIGNAL.