Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 15. September 2019 

Semaphor


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein Semaphor (griech.: "Zeichenträger") ist eine Datenstruktur zur Synchronisation des Zugriffs auf kritische oder Ressourcen bei nebenläufigen Prozessen . Ursprünglich bezeichnet das Wort Semaphor einen Signalmast mit beweglichen Flügeln wie zur Nachrichtenübertragung in früheren Jahrhunderten eingesetzt wurde auch eine Verkehrsampel. Auch bei der Eisenbahn wurden die Formsignale als Semaphore bezeichnet. Der Informatiker Edsger Dijkstra hat Semaphore erstmals im Jahre 1965 bei der Implementation seines T.H.E Betriebssystems

Inhaltsverzeichnis

Probleme bei mehreren Prozessen

In Mehrprozesssystemen treten die folgenden Probleme die mit Hilfe von Semaphoren gelöst werden

  • Ressourcen wie Drucker Speicher Prozessoren sind beschränkt. z. B. drei gleiche Drucker zur Verfügung muss der Zugriff auf diese Drucker geregelt Es können maximal drei Druckaufträge parallel ausgeführt Will ein vierter Prozess drucken so muss auf das Ende eines Auftrags warten.
  • Zugriffe innerhalb des Speichers können nicht immer eine Maschineninstruktion abgebildet werden insbesondere wenn die für eine Struktur mehr als ein Maschinenwort oder wenn ein Maschinenwort nur teilweise geändert soll. Überlappende Zugriffe mehrerer Prozesse müssen verhindert da sonst die Daten unter Umständen zerstört Speicherflächen die so geschützt werden müssen nennt kritische Bereiche.

Dijkstras Lösung

Die Datenstruktur verfügt über einen Zähler eventuell eine Prozess- Warteschlange sowie über die Methoden wait und signal . Zunächst verwendete Dijkstra die Bezeichnungen P und V .

Es wird festgelegt wieviele kritische Prozesse dürfen wobei jeder Prozess eine Ressource verbraucht. Zahl der noch freien Prozesse wird im festgehalten. Jeder wait -Aufruf verringert den Zähler. Wird der Zähler so reiht die Methode wait den letzten Prozess in eine Warteschlange ein. Manchmal wartet der Prozess auch einer Schleife. Die Methode signal erhöht den Zähler. Wenn der Zähler positiv wird wird der an der ersten befindliche Prozess aus der Warteschlange geholt. Eine Möglichkeit zur Synchronisation von kritischen Prozessen sind Monitore .

Im einfachsten Fall besteht ein Semaphor einem Bit das gesetzt sein kann oder was auch binärer Semaphor oder Mutex genannt wird. Ein Prozess der einen Bereich betritt löscht das Semaphor-Bit. Dies verhindert Betreten des Bereichs durch andere Prozesse. Der wird wieder gelöst wenn der Prozess den Bereich verlässt. Wartende Prozesse werden dann nacheinander

Stehen z.B. drei gleiche Laserdrucker zu können die Druckaufträge über ein Semaphor mit Maximalwert drei verwaltet werden. Zunächst erhält jeder einen Auftrag. Überschreitet die Zahl der aktuellen die Zahl drei werden die überzähligen in Warteschlange des Semaphors eingereiht.

Implementation

Ein Semaphor ist eine geschützte Variable ein abstrakter Datentyp) auf die nur über Funktionen zugegriffen werden kann:

 P(s) Semaphor s; { while (s 0) ; /* warte bis s>0 Spinlock s = s-1; }  

 V(s) Semaphor s; { s = }  

 Init(s v) Semaphor s; Int v; s = v; }  

P und V stehen für Holländisch probieren und "Verhogen" erhöhen. Der Wert eines ist die Anzahl an freien Einheiten der (wenn es nur eine Ressource gibt wird "binärer Semaphor" mit dem Wert 0 oder verwendet). Die Funktion P() wartet bis eine verfügbar ist worauf sie unmittelbar darauf eine V() ist die umgekehrte Funktion die die wieder verfügbar macht nachdem sie vom Prozess mehr verwendet wird. Die Funktionen P() und müssen atomar sein d.h. kein anderer Prozess kann die Semaphore während deren Ausführung zugreifen.

Vermeidung von Warteschleifen

Warteschleifen verschwenden unnötig Prozessorzeit. Um eine zu vermeiden kann einem Semaphor eine Liste Prozessen zugeordnet haben. Wenn ein Prozess die ausführt und damit der Semaphor auf Null dann wird der Prozess dieser Liste die genannt wird hinzugefügt. Wenn ein Prozess den mit der V()-Funktion erhöht und andere Prozesse der Warteliste sind dann wird einer davon der Liste genommen und fortgesetzt.

 Queue queue; /* Warteschlange */ P(s) s; { while (s == 0) haltean(queue); Anhalten des Prozesses Einreihung in Warteschlange */ = s-1; }  

 V(s) Semaphor s; { s = weckeauf(queue); /* Aufwecken eines Prozesses bei nichtleerer */ }  

 Init(s v) Semaphor s; Int v; s = v; }  

Dabei ist jedoch zu beachten dass Prozessoren die keine speziellen Befehle zur Verwaltung Listen besitzen wieder kritische Bereiche bei der der Warteschlangen auftreten. Diese müssen dann mit Methoden (Spinlock Verhindern einer Unterbrechung) geschützt werden.

Siehe auch: Interprozesskommunikation



Bücher zum Thema Semaphor

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Semaphor.html">Semaphor </a>