| [gesichtete Version] | [gesichtete Version] |
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 26: | Zeile 26: | ||
==== Arbeitsweise eines Semaphors ==== | ==== Arbeitsweise eines Semaphors ==== | ||
<p> | <p> | ||
<loop_index>Semaphor, Arbeitsweise|Arbeitsweise Semaphor|binärer Semaphor|Semaphor, binär</loop_index> | <loop_index>Semaphor, Arbeitsweise|Arbeitsweise, Semaphor|binärer Semaphor|Semaphor, binär</loop_index> | ||
Zunächst wird eine Instanz '''<span style="font-family:Courier">s</span>''' eines Semaphors erstellt, diese steht mehreren Prozessen zur Synchronisation zur Verfügung. | Zunächst wird eine Instanz '''<span style="font-family:Courier">s</span>''' eines Semaphors erstellt, diese steht mehreren Prozessen zur Synchronisation zur Verfügung. | ||
</p> | </p> | ||
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.
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().
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 echt 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.
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.
Ein ähnliches und oft verwendetes Beispiel ist das sogenannte Producer-Consumer-Problem (auf deutsch: Erzeuger-Verbraucher-Problem). Es ist beispielsweise beschrieben bei:
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.
Erkennst du, dass die Funktionsnamen down() und up() Sinn machen? Erläutere warum!
Warum hat Dijkstra die Funktionen ursprünglich P() und V() genannt?
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? Überlege, recherchiere und diskutiere in deiner Lerngruppe!
An der FH Köln wird ein Semaphor Workshop mit Java-Applets bereitgestellt, anhand derer der wechselseitige Ausschluss mit Hilfe eines binären Semaphors (Mutex) nachvollzogen werden kann. Probiere es aus!
http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/waus/waus.html
Was ist beim Erzeuger-Verbraucher-Problem das "Irgendwas"?
An der FH Köln wird ein Semaphor Workshop mit Java-Applets bereitgestellt anhand derer das Erzeuger-Verbraucher-Problem durchgespielt werden kann. Probiere es aus!
http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/erzver/erzver.html
Bislang haben alle Beispiele die Zählvariable des Semaphors mit einem Wert größergleich Eins initialisiert. Man kann sie jedoch auch mit Null initialisieren und löst dadurch das Problem der Reihenfolgedurchsetzung.
An der FH Köln wird ein Semaphor Workshop mit Java-Applets bereitgestellt anhand derer das Problem der Reihenfolgedurchsetzung durchgespielt werden kann. Probiere es aus!
http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/reihenf/reihenf.html
Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png