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.

Definition: Semaphor

{{#index:Semaphor|P()-Operation|up()-Operation|V()-Operation|down()-Operation}}

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. 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().

Arbeitsweise eines Semaphors

{{#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.

Zweck eines binären Semaphors

{{#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.

Definition: Mutex

{{#index:Mutex}}

Definition

Unter einem Mutex (als Abkürzung für MUTal EXclusion, auf deutsch: gegenseitiger Ausschluss) versteht man einen binären Semaphor.

Zweck eines Zählsemaphors

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.

Beispiel

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:

• Glatz 2010, Kapitel 4.3.3
• Tanenbaum 2009, Kapitel 2.3.5
• Wikipedia: http://de.wikipedia.org/wiki/Erzeuger-Verbraucher-Problem
• http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/erzver/erzver.html

{{#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:

• Tanenbaum 2009, Kapitel 2.5.1
• Wikipedia: http://de.wikipedia.org/wiki/Speisende_Philosophen

Bevor jedoch näher auf diese Probleme eingegangen werden kann, ist zunächst noch genauer auf die atomaren Operationen P() und V() einzugehen.

Atomare Operationen auf Semaphore

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:

Hinweis

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.

Weblinks

• Edsger Wybe Dijkstra;
  niederländischer Informatiker; *11. Mai 1930 bis †6. August 2002
• Co-Operating Sequential Processes - Wissenschaftlicher Aufsatz

---

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