Semaphor (Informatik)

Stichpunkte

Allgemein
	von dem nur eine begrenzte Zahl zur Verfügung stehen
	bei denen mehrere Prozesse ein Betriebsmittel verwenden wollen
	Ein Semaphor (griech.: "Zeichenträger") ist eine Datenstruktur zur Lösung von Problemen
	dass nur ein einziges Exemplar dieses Betriebsmittels zur Verfügung steht
	Der häufigste Sonderfall ist
	Bei der Art des Betriebsmittels kann es sich um verschiedenste Ressourcen (z.B
	CPUs) oder Programmteile (sogenannte kritische Regionen) handeln
	wie er zur Nachrichtenübertragung in früheren Jahrhunderten eingesetzt wurde
	später auch eine Verkehrsampel
	Ursprünglich bezeichnet das Wort Semaphor einen Signalmast mit beweglichen Flügeln
	Auch bei der Eisenbahn wurden die Formsignale als Semaphore bezeichnet
	Der Informatiker Edsger W
	Dijkstra hat Semaphore erstmals im Jahre 1965 bei der Implementation seines Betriebssystems verwendet. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Probleme bei mehreren Prozessen 1.1 Teilen von globalen Ressourcen 1.2 Interprozesskommunikation/Prozesssynchronisation 2 Dijkstras Lösung 3 Implementation 4 Vermeidung von Warteschleifen [Bearbeiten]
Probleme bei mehreren Prozessen
	In Mehrprozess-Systemen und Mehr-Prozessor-Systemen treten die folgenden Probleme auf
	die mit Hilfe von Semaphoren gelöst werden können: [Bearbeiten]
Teilen von globalen Ressourcen
	Speicher
	Prozessoren sind beschränkt
	Ressourcen wie Drucker
	Stehen z
	so muss der Zugriff auf diese Drucker geregelt werden
	B. drei gleiche Drucker zur Verfügung
	Es können maximal drei Druckaufträge parallel ausgeführt werden
	so muss er auf das Ende eines Auftrags warten. [Bearbeiten]
	Will ein vierter Prozess drucken
Interprozesskommunikation/Prozesssynchronisation
	Zugriffe auf thread-globalen Speicher müssen bei möglichem Zugriff aus mehreren Threads gekapselt werden
	Bei Single-Prozessor-Systemen sind u.U. noch Tricks in Form von temporärem Unterdrücken von Interrupts oder Taskwechseln oder atomic Read-Modify-Write-Befehlen möglich
	Spätestens bei Mehrprozessorsystemen sind Semaphoren und entsprechend abgestimmte Programme notwendig
	gleichzeitiges Lesen und Schreiben zu Inkonsistenzen der gelesenen Daten
	Auf eine Datenstruktur sind folgende Zugriffsarten möglich: ein oder mehrere Lese-Threads exakt ein Schreib-Thread keine Zugriffe Mehrere Schreibzugriffe gleichzeitig führen zu inkonsistenten Daten
	müssen Datenstrukturen um Semaphoren oder kritische Abschnitte erweitert werden
	Um das zu verhindern
	die vor Zugriff auf die eigentliche Struktur geholt und wieder zurückgegeben werden. [Bearbeiten]
Dijkstras Lösung
	Die Datenstruktur verfügt über einen Zähler und eventuell eine Prozess-Warteschlange sowie über die Methoden wait und signal
	Zunächst verwendete Dijkstra die Bezeichnungen P und V
	wobei jeder Prozess eine Ressource verbraucht
	Es wird festgelegt
	wieviele kritische Prozesse existieren dürfen
	Die Zahl der noch freien Ressourcen wird im Zähler festgehalten
	Jeder wait-Aufruf verringert den Zähler
	so reiht die Methode wait den letzten Prozess in eine Warteschlange ein
	Wird der Zähler Null
	Manchmal wartet der Prozess auch in einer Schleife
	Die Methode signal erhöht den Zähler
	Wenn der Zähler wieder positiv wird
	wird der an der ersten Position befindliche Prozess aus der Warteschlange geholt
	Eine andere Möglichkeit zur Synchronisation von kritischen Prozessen sind Monitore
	das gesetzt sein kann oder nicht
	was auch binärer Semaphor oder Mutex genannt wird
	Im einfachsten Fall besteht ein Semaphor aus einem Bit
	löscht das Semaphor-Bit
	Ein Prozess
	der einen kritischen Bereich betritt
	Dies verhindert das Betreten des Bereichs durch andere Prozesse
	wenn der Prozess den kritischen Bereich verlässt
	Der Semaphor wird wieder gelöst
	Wartende Prozesse werden dann nacheinander aktiviert
	können die Druckaufträge über ein Semaphor mit dem Maximalwert drei verwaltet werden
	Stehen z.B. drei gleiche Drucker zur Verfügung
	Zunächst erhält jeder Drucker einen Auftrag. Überschreitet die Zahl der aktuellen Aufträge die Zahl drei
	werden die überzähligen in die Warteschlange des Semaphors eingereiht. [Bearbeiten]
Implementation
	auf die nur über folgende Funktionen zugegriffen werden kann: P(s) Semaphor s; { while (s == 0) ; /* warte bis s>0
	Spinlock */ s = s-1; } V(s) Semaphor s; { s = s+1; } Init(s
	passieren und "verlaten"(vriegeven)
	Ein Semaphor ist eine geschützte Variable (oder ein abstrakter Datentyp)
	v) Semaphor s; Int v; { s = v; } P und V stehen für Niederländisch "passeren"
	verlassen (freigeben)
	wird ein "binärer Semaphor" mit dem Wert 0 oder 1 verwendet)
	Der Wert eines Semaphor ist die Anzahl an freien Einheiten der Ressource (wenn es nur eine Ressource gibt
	Die Funktion P() wartet
	worauf sie unmittelbar darauf eine beansprucht
	bis eine Ressource verfügbar ist
	nachdem sie vom Prozess nicht mehr verwendet wird
	die die Ressource wieder verfügbar macht
	V() ist die umgekehrte Funktion
	d.h. kein anderer Prozess kann auf die Semaphore während deren Ausführung zugreifen
	Die Funktionen P() und V() müssen atomar sein
	die Funktion P() als "down" bezeichnet. [Bearbeiten]
	Die Funktion V() wird auch als "up"
Vermeidung von Warteschleifen
	Warteschleifen verschwenden unnötig Prozessorzeit
	Um eine Warteschleife zu vermeiden
	kann einem Semaphor eine Liste von Prozessen zugeordnet werden
	die Warteschlange genannt wird
	hinzugefügt
	Wenn ein Prozess die P()-Funktion ausführt und damit den Semaphor auf Null setzt
	dann wird der Prozess dieser Liste
	Wenn ein Prozess den Semaphor mit der V()-Funktion erhöht
	dass bei Prozessoren
	wieder kritische Bereiche bei der Implementation der Warteschlangen auftreten
	Einreihung in Warteschlange */ s = s-1; } V(s) Semaphor s; { s = s+1; weckeauf(queue); /* Aufwecken eines Prozesses bei nichtleerer Warteschlange */ } Init(s
	die keine speziellen Befehle zur Verwaltung von Listen besitzen
	und andere Prozesse in der Warteliste sind
	dann wird einer davon von der Liste genommen und fortgesetzt. Queue queue; /* Warteschlange */ P(s) Semaphor s; { if (s==0) haltean(queue); /* Anhalten des Prozesses
	v) Semaphor s; Int v; { s = v; } Dabei ist jedoch zu beachten
	Diese müssen dann mit anderen Methoden (Spinlock
	Verhindern einer Unterbrechung) geschützt werden
	Siehe auch: Interprozesskommunikation en:Semaphore (programming) nl:Semafoor pl:Semafor (informatyka)

Dieser Artikel basiert auf dem Artikel Semaphor (Informatik) aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.