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.
Semaphore werden genutzt um sicherzustellen, dass sich nur ein Prozess zur Zeit in seinem kritischen Abschnitt befindet.
{{#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.
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|mutal exclusion|gegenseitiger Ausschluss}}
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.
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 also beendet wurde.
Ein ähnliches und oft verwendetes Beispiel ist das sogenannte Producer-Consumer-Problem (auf deutsch: Erzeuger-Verbraucher-Problem). Es ist beispielsweise beschrieben bei:
Möchte ein Prozess in seinen kritischen Abschnitt eintreten, so muss er zunächst die Operation P(s) aufrufen (alternativ: down(s)).
Dieses Kapitel wird in der weiterführenden Literatur behandelt:
Weiterführende Literatur
{{#index:Semaphore|Dijkstra|Edsger Wybe Dijkstra}} 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