Semaphore

Der niederländische Informatiker Edsger Wybe Dijkstra hat das Semaphor-Konzept in den 1960er-Jahren entwickelt, und in seinem Artikel Co-Operating Sequential Processes vorgestellt. Auf Wikipedia findet sich ein Hinweis zur Namensherkunft des Begriffs Semaphor.

Wie im weiteren Verlauf dieses Abschnitts noch zu sehen sein wird, können mit Hilfe des Semaphor-Konzepts eine Reihe von Problemen der Prozess-Synchronisation gelöst werden. Als großer Vorteil der Semaphore wird noch zu erkennen sein, dass sie dabei auf aktives Warten verzichten, und somit nicht den Nachteil der Verschwendung von CPU-Zeit haben.

Zunächst einige Definitionen:

Definition: Semaphor

Definition

Unter einem Semaphor versteht man eine Datenstruktur, welche einen ganzzahligen Zähler, sowie eine Warteschlange bereitstellt. Zusätzlich sind zwei atomare Operationen  P()  und  V()  auf diese Datenstruktur definiert.

Ein ganzzahliger Zähler ist in der Programmierung beispielsweise eine einfache Integer-Variable. Diese kann negative oder positive ganzzahlige Werte annehmen. Der ganzzahlige Zähler einer Semaphore hingegen kann keine negativen Werte annehmen.

Eine Warteschlange ist eine klassische Datenstruktur in der Informatik, die nach dem FIFO-Prinzip (First In, First Out) arbeitet. Sie dient hier zur geordneten Aufnahme von Prozessen.

Die Operation P() wird in einigen Quellen auch als down()-Operation betitelt, analog up() anstatt V().

Definition: Binärer Semaphor

Definition

Unter einem binären Semaphor versteht man einen Semaphor, dessen ganzzahliger Zähler nur die Werte 0 oder 1 annehmen kann.

Ein binärer Semaphor besitzt gemäß seiner Definition ebenso eine Warteschlange und auch die auf ihm operierenden P()- und V()-Operationen.

Definition: P()-Operation eines Semaphors

Definition

Die P()-Operation eines Semaphors ist als atomare Operation wie folgt definiert:

• Hat die Zählervariable einen positiven Wert (>0), dann verringere den Wert der Zählvariablen um 1.
• Wenn die Zählvariable den Wert 0 hat, dann blockiert die P()-Operation den aufrufenden Prozess und fügt ihn an das Ende ihrer Warteschlange hinzu.

Mit "blockieren" ist hier das Ändern des Prozesszustands des die P()-Operation aufrufenden Prozesses in den Zustand "Blockiert" gemeint.

Definition: V()-Operation eines Semaphors

Definition

Die V()-Operation eines Semaphors ist als atomare Operation wie folgt definiert:

• Wenn die Warteschlange nicht leer ist, dann entblockiere den ersten Prozess der Warteschlange.
• Ist die Warteschlange leer, dann erhöhe den Wert der Zählervariable um 1.

Mit "entblockieren" ist hier das Ändern des Prozesszustands des ersten Prozesses aus der Warteschlange in den Zustand "Bereit" gemeint.

Nach diesen grundlegenden Definitionen folgen mit dem Mutex und dem Zählsemaphor zwei konkretere Konzepte, anhand derer die Einsatzmöglichkeiten von Semaphoren gezeigt werden.

So geht es weiter:

Gliederung

3.2.11.3 Semaphore

3.2.11.3.1 Mutex

3.2.11.3.2 Zählsemaphor

Aufgabe 1

Aufgabe

 Aufg. 128: Warum up() und down()?

Erläutere warum es Sinn macht, dass die P()-Operation auch als down()-Operation betitelt wird, und warum analog die V()-Operation als up() betitelt wird.

Aufgabe 2

Aufgabe

 Aufg. 129: P() und V() sind atomar

Die P()- und V()-Operation ist jeweils als atomare Operation definiert.

Was bedeutet dies für die Ausführung dieser beiden Operationen?

Aufgabe 3

Aufgabe

 Aufg. 130: P() und V() und die Zustände

Wenn die P()-Operation ausgeführt wird, dann ändert sich gegebenenfalls der Zustand desjenigen Prozesses, der die P()-Operation aufgerufen hat.

• Von welchem alten Zustand in welchen neuen Zustand erfolgt hier ggf. die Änderung?

Wie ist das bei der V()-Operation? Ändert sich hier eventuell auch der Zustand des Prozesses, der die V()-Operation aufgerufen hat?

• Falls ja: Von welchem alten Zustand in welchen neuen Zustand erfolgt hier ggf. die Änderung?
• Falls nein: Was ändert sich dann?

Aufgabe 4

Aufgabe

 Aufg. 131: V()-Operation und die Warteschlange

In der Definition zur V()-Operation heisst es:

• Wenn die Zählvariable den Wert Null hat, dann entblockiere den ersten Prozess der Warteschlange.

Kann es passieren, dass der Wert der Zählvariablen gleich Null ist, aber kein Prozess entblockiert werden kann, weil die Warteschlange leer ist?

---

_{Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png}