{{#index:Semaphore|Dijkstra|Edsger Wybe Dijkstra}} 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.
{{#index:Semaphor|P()-Operation|up()-Operation|V()-Operation|down()-Operation}}
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. 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().
{{#index:Semaphor, Arbeitsweise|Arbeitsweise Semaphor|binärer Semaphor|Semaphor, binär}} Zunächst wird eine Instanz s eines Semaphors erstellt, diese steht mehreren Prozessen zur Synchronisation zur Verfügung.
Die Integer-Variable von s wird mit einem Wert größergleich 1 initialisiert. Bei einem Wert von genau 1 spricht man von einem binären Semaphor, bei Werten größer als 1 von einem Zählsemaphor. Beide Typen haben i.d.R. unterschiedliche Einsatzzwecke.
{{#index:mutal exclusion|gegenseitiger Ausschluss|wechselseitiger Ausschluss}} Ein binärer Semaphor ist geeignet, um kritische Abschnitte vor gleichzeitigem Betreten zu sichern. Man spricht in diesem Zusammenhang von einem wechselseitigen Ausschluss (auf englisch: mutal exclusion) der beteiligten Prozesse.
{{#index:Mutex}}
Unter einem Mutex (als Abkürzung für MUTal EXclusion, auf deutsch: gegenseitiger Ausschluss) versteht man einen binären Semaphor.
Ein Zählsemaphor ist geeignet, um eine begrenzte Anzahl von "Irgendwas" zu verwalten. Dieses "Irgendwas" kann entsprechend seiner Anzahl genutzt werden, aber nicht darüber hinaus. Der Zugriff auf "Irgendwas" stellt deshalb einen kritischen Abschnitt dar, und muss geschützt werden.
In einer Bibliothek stehen beispielsweise fünf Ausgaben des Buchs Tanenbaum 2009. Damit können maximal fünf Personen dieses Buch ausleihen. Das "Irgendwas" ist in diesem Beispiel das Buch. Eine Person repräsentiert einen Prozess.
Solange noch Ausgaben des Buchs in der Bibliothek vorhanden sind, kann es ausgeliehen werden. Sind alle Ausgaben verliehen, so muss die nächste ausleihwillige Person so lange warten, bis (mindestens) ein Buch abgegeben wurde, der Ausleihvorgang dafür also beendet wurde.
{{#index:Producer-Consumer-Problem|Erzeuger-Verbraucher-Problem}} Ein ähnliches und oft verwendetes Beispiel ist das sogenannte Producer-Consumer-Problem (auf deutsch: Erzeuger-Verbraucher-Problem). Es ist beispielsweise beschrieben bei:
{{#index:Dining-Philosophers-Problem|Problem der speisenden Philosophen|Philosophenproblem}} Sehr bekannt ist auch das Dining-Philosophers-Problem (auf deutsch: Problem der speisenden Philosophen oder kurz: Philosophenproblem). Es wurde von Edsger Wybe Dijkstra in seinem Aufsatz Hierarchical ordering of sequential processes veröffentlicht. Es ist u.a. beschrieben bei:
Bevor jedoch näher auf diese Probleme eingegangen werden kann, sind zunächst die atomaren Operationen P() und V() zu erläutern.
Möchte ein Prozess in seinen kritischen Abschnitt eintreten, so muss er zunächst die Funktion P(s) (bzw. down(s)) aufrufen. Hier wird geprüft, ob die Zählvariable des übergebenen Semaphors s noch einen Wert größergleich Eins (>=1) besitzt.
Am Ende der Bearbeitung eines kritischen Abschnitts muss der betreffende Prozess die Funktion V(s) (bzw. up(s)) aufrufen. Der Wert der Zählvariable des übergebenen Semaphors s wird um Eins erhöht, und falls sich in der Warteschlange des Semaphors ein (oder mehrere) Prozess(e) befinden, so entferne den ersten daraus und ändere seinen Zustand in bereit. Bei der nächsten Zuteilung der CPU kann dieser damit seinen kritischen Abschnitt betreten.
Dieses Kapitel wird in der weiterführenden Literatur behandelt:
Weiterführende Literatur
Mandl 2013 erläutert das Semaphor-Konzept in Kapitel 6.2.2. Die Lektüre dieser Quelle sei ausdrücklich empfohlen.
Studierende sind oftmals berechtigt, eine PDF-Version dieses Buches ohne entstehende Kosten über ihre Hochschulen von Springerlink zu beziehen.
Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png