|
|
| Zeile 23: |
Zeile 23: |
| </p> | | </p> |
|
| |
|
| <br /> | | <div class="autoit_do_not_print"> |
| | |
| == Arbeitsweise eines Semaphors ==
| |
| <p>
| |
| <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.
| |
| </p>
| |
| <p>
| |
| Die Integer-Variable von <span style="font-family:Courier">s</span> 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.
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Zweck eines binären Semaphors ==
| |
| <p>
| |
| <loop_index>mutal exclusion|gegenseitiger Ausschluss|wechselseitiger Ausschluss</loop_index>
| |
| Ein binärer Semaphor ist geeignet, um [[Kritischer Abschnitt|kritische Abschnitte]] vor gleichzeitigem Betreten zu sichern. Man spricht in diesem Zusammenhang von einem ''wechselseitigen Ausschluss'' (auf englisch: ''mutal exclusion'') der beteiligten Prozesse.
| |
| </p>
| |
| | |
| <br />
| |
| == Definition: Mutex ==
| |
| <p>
| |
| <loop_index>Mutex</loop_index>
| |
| <loop_area type="definition">
| |
| <p>
| |
| Unter einem '''Mutex''' (als Abkürzung für '''MUTual EXclusion''', auf deutsch: '''gegenseitiger Ausschluss''') versteht man einen binären Semaphor.
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Zweck eines Zählsemaphors ==
| |
| <p>
| |
| 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 [[Kritischer Abschnitt|kritischen Abschnitt]] dar, und muss geschützt werden.
| |
| </p>
| |
| <p>
| |
| <loop_area type="example">
| |
| <p>
| |
| In einer Bibliothek stehen beispielsweise fünf Ausgaben des Buchs <cite>Tanenbaum+2009</cite>. Damit können maximal fünf Personen dieses Buch ausleihen. Das "Irgendwas" ist in diesem Beispiel das Buch. Eine Person repräsentiert einen Prozess.
| |
| </p>
| |
| <p>
| |
| 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.
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| == Erzeuger-Verbraucher-Problem ==
| |
| <p>
| |
| <loop_index>Producer-Consumer-Problem|Erzeuger-Verbraucher-Problem|Probem, Erzeuger-Verbraucher|Problem, Producer-Consumer</loop_index>
| |
| Ein ähnliches und oft verwendetes Beispiel ist das sogenannte '''Producer-Consumer-Problem''' (auf deutsch: '''Erzeuger-Verbraucher-Problem'''). Es ist beispielsweise beschrieben bei:
| |
| * <cite>Glatz+2010</cite>, Kapitel 4.3.3
| |
| * <cite>Tanenbaum+2009</cite>, Kapitel 2.3.5
| |
| * Wikipedia: http://de.wikipedia.org/wiki/Erzeuger-Verbraucher-Problem
| |
| </p>
| |
| | |
| <br />
| |
| == Philosophenproblem ==
| |
| <p>
| |
| <loop_index>Dining-Philosophers-Problem|Problem der speisenden Philosophen|Philosophenproblem|Problem, Philosophenproblem|Problem, speisende Philosophen</loop_index>
| |
| Sehr bekannt ist auch das '''Dining-Philosophers-Problem''' (auf deutsch: '''Problem der speisenden Philosophen''' oder kurz: '''Philosophenproblem'''). Es wurde von [http://de.wikipedia.org/wiki/Edsger_W._Dijkstra Edsger Wybe Dijkstra] in seinem Aufsatz [http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF Hierarchical ordering of sequential processes] veröffentlicht. Es ist u.a. beschrieben bei:
| |
| * <cite>Tanenbaum+2009</cite>, Kapitel 2.5.1
| |
| * Wikipedia: http://de.wikipedia.org/wiki/Speisende_Philosophen
| |
| </p>
| |
| | |
| <br />
| |
| <p>
| |
| Bevor jedoch näher auf diese Probleme eingegangen werden kann, sind zunächst die atomaren Operationen <span style="font-family:Courier">P()</span> und <span style="font-family:Courier">V()</span> zu erläutern.
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Atomare Operationen auf Semaphore ==
| |
| <p>
| |
| Möchte ein Prozess in seinen kritischen Abschnitt eintreten, so muss er zunächst die Funktion '''<span style="font-family:Courier">P(s)</span>''' (bzw. '''<span style="font-family:Courier">down(s)</span>''') aufrufen. Hier wird geprüft, ob die Zählvariable des übergebenen Semaphors '''<span style="font-family:Courier">s</span>''' noch einen Wert größergleich Eins (>=1) besitzt.
| |
| </p>
| |
| <p>
| |
| * Falls ja: verringere den Wert der Zählvariablen um 1 und verlasse die Funktion wieder (der kritische Abschnitt darf also betreten werden).
| |
| </p>
| |
| <p>
| |
| * Falls nein: Der aufrufende Prozess wird angehalten ([[Prozesszustände|blockiert]]) und in die Warteschlange des Semaphors '''<span style="font-family:Courier">s</span>''' eingereiht (der kritische Abschnitt darf noch nicht betreten werden).
| |
| </p>
| |
| <p>
| |
| Am Ende der Bearbeitung eines kritischen Abschnitts muss der betreffende Prozess die Funktion '''<span style="font-family:Courier">V(s)</span>''' (bzw. '''<span style="font-family:Courier">up(s)</span>''') aufrufen. Der Wert der Zählvariable des übergebenen Semaphors '''<span style="font-family:Courier">s</span>''' 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 [[Prozesszustände|bereit]]. Bei der nächsten Zuteilung der CPU kann dieser damit seinen kritischen Abschnitt betreten.
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Aufgabe 1 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Operationen auf Semaphore">
| |
| <p>
| |
| Erkennst du, dass die Funktionsnamen <span style="font-family:Courier">down()</span> und <span style="font-family:Courier">up()</span> Sinn machen? Erläutere warum!
| |
| </p>
| |
| <p>
| |
| Warum hat Dijkstra die Funktionen ursprünglich <span style="font-family:Courier">P()</span> und <span style="font-family:Courier">V()</span> genannt?
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Aufgabe 2 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Operationen nicht atomar?">
| |
| <p>
| |
| Was könnte passieren, wenn die Operationen <span style="font-family:Courier">P()</span> und <span style="font-family:Courier">V()</span> '''nicht''' atomar realisiert werden? Erläutere anhand eines Beispiels!
| |
| </p>
| |
| <p>
| |
| Wie kann ein Betriebssystem dafür sorgen, dass die Operationen <span style="font-family:Courier">P()</span> und <span style="font-family:Courier">V()</span> atomar realisiert werden? Überlege, recherchiere und diskutiere in deiner Lerngruppe!
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Aufgabe 3 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Applet zum wechselseitigen Ausschluss">
| |
| <p>
| |
| An der FH Köln wird ein [http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/ Semaphor Workshop] mit Java-Applets bereitgestellt, anhand derer der wechselseitige Ausschluss mit Hilfe eines binären Semaphors (Mutex) nachvollzogen werden kann. Probiere es aus!
| |
| </p>
| |
| <p>
| |
| <small>http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/waus/waus.html</small>
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Aufgabe 4 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Irgendwas">
| |
| <p>
| |
| Was ist beim [[Semaphore#Erzeuger-Verbraucher-Problem|Erzeuger-Verbraucher-Problem]] das "[[Semaphore#Zweck_eines_Z.C3.A4hlsemaphors|Irgendwas]]"?
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| == Aufgabe 5 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Applet zum Erzeuger-Verbraucher-Problem">
| |
| <p>
| |
| An der FH Köln wird ein [http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/ Semaphor Workshop] mit Java-Applets bereitgestellt anhand derer das Erzeuger-Verbraucher-Problem durchgespielt werden kann. Probiere es aus!
| |
| </p>
| |
| <p>
| |
| <small>http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/erzver/erzver.html</small>
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br />
| |
| <p>
| |
| <loop_index>Reihenfolgedurchsetzung|Problem, Reihenfolgedurchsetzung</loop_index>
| |
| 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'''.
| |
| </p>
| |
| | |
| <br />
| |
| | |
| == Aufgabe 6 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Reihenfolgedurchsetzung">
| |
| <p>
| |
| An der FH Köln wird ein [http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/ Semaphor Workshop] mit Java-Applets bereitgestellt anhand derer das Problem der Reihenfolgedurchsetzung durchgespielt werden kann. Probiere es aus!
| |
| </p>
| |
| <p>
| |
| <small>http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/reihenf/reihenf.html</small>
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
| | |
| <br /> | | <br /> |
| <hr /> | | <hr /> |
| <sub>Diese Seite steht unter der [http://creativecommons.org/licenses/by/3.0/deed.de Creative Commons Namensnennung 3.0 Unported Lizenz] [http://creativecommons.org/licenses/by/3.0/deed.de http://i.creativecommons.org/l/by/3.0/80x15.png] | | <sub>Diese Seite steht unter der [http://creativecommons.org/licenses/by/3.0/deed.de Creative Commons Namensnennung 3.0 Unported Lizenz] [http://creativecommons.org/licenses/by/3.0/deed.de http://i.creativecommons.org/l/by/3.0/80x15.png] |
| </sub> | | </sub> |
| | </div> |