Semaphore

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

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.

Erzeuger-Verbraucher-Problem

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

Philosophenproblem

{{#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, sind zunächst die atomaren Operationen P() und V() zu erläutern.

Atomare Operationen auf Semaphore

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.

• Falls ja: verringere den Wert der Zählvariablen um 1 und verlasse die Funktion wieder (der kritische Abschnitt darf also betreten werden).

• Falls nein: Der aufrufende Prozess wird angehalten (blockiert) und in die Warteschlange des Semaphors s eingereiht (der kritische Abschnitt darf noch nicht betreten werden).

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.

Aufgabe 1

Aufgabe

 Aufg. : Irgendwas

Was ist beim Erzeuger-Verbraucher-Problem das "Irgendwas"?

Aufgabe 2

Aufgabe

 Aufg. : Operationen auf Semaphore

Erkennst du, dass die Funktionsnamen down() und up() Sinn machen? Erläutere warum!

Warum hat Dijkstra die Funktionen ursprünglich P() und V() genannt?

Aufgabe 3

Aufgabe

 Aufg. : Operationen nicht atomar?

Was könnte passieren, wenn die Operationen P() und V() nicht atomar realisiert werden? Erläutere anhand eines Beispiels!

Wie kann ein Betriebssystem dafür sorgen, dass die Operationen P() und V() atomar realisiert werden? Recherchiere und diskutiere in deiner Lerngruppe!

Dieses Kapitel wird in der weiterführenden Literatur behandelt:

Hinweis

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}