WikiDer > Semaphor (Computer)

Semafoor (computer)

EIN Semaphor (ebenfalls: Semaphor) ist Teil eines Synchronisationsmechanismus für parallele oder verteilte Programme entworfen von Edsger Dijkstraße.

Beim Entwurf verteilter Programme ist es normal, dass die verschiedenen Unterprogramme innerhalb des Hauptprogramms sich irgendwie gegenseitig berücksichtigen müssen. Dieses "berücksichtigen" kann sich auf die gemeinsame Nutzung von Speicher oder den Zugriff auf andere Hardware beziehen oder einfach darauf, dass ein Programm darauf wartet, dass ein anderes Programm einen bestimmten Punkt in seinem Code erreicht.

Betrachten wir das Problem der gegenseitigen Ausgrenzung ("gegenseitiger AusschlussKurz gesagt, das Problem läuft darauf hinaus, dass in einem verteilten Programm eine Reihe von Programmen der folgenden Form enthalten sind:

Programm p:|[ CRITICAL_SECTION.p ; NON_CRITICAL_SECTION.p]|

Von all diesen Programmen darf höchstens eines zu jeder Zeit beschäftigt sein Kritischer Abschnitt. Wir möchten, dass diese Programme Folgendes tun:

Geteilt: Variable s : Ganzzahl; {s verfolgt, wie viele Programme an ihrem kritischen Abschnitt arbeiten}Programm p:|[ if s = 0 then s := s 1 ;CRITICAL_SECTION.ps := s - 1 else block_and_try_again ; NON_CRITICAL_SECTION.p]|

Natürlich müssen der Wert von s und die Zuweisungen zu s (die Zunahme und Abnahme von s) atomar sein Anleitung sein.

Wenn wir das Programm nun – aus historischen Gründen – ein wenig optimieren, erhalten wir Folgendes:

Geteilt: Variable s : Ganzzahl; {s verfolgt, wie viele Programme an ihrem kritischen Abschnitt arbeiten} r : integer; {r = 1 - s}Programm p:|[ if r > 0 {then s is 0} then r, s := r - 1, s 1 ;CRITICAL_SECTION.pr, s := r 1, s - 1 else block_and_try_again ; NON_CRITICAL_SECTION.p]|

Jetzt hat r die Funktion von s im obigen Programm übernommen: r überwacht nun den exklusiven Zugriff auf die kritischen Abschnitte der verschiedenen Programme. Wir können jetzt s aus dem Programm entfernen. Im folgenden Programm verwenden wir gebrochene Klammern, um Teile anzuzeigen, die atomar sein müssen:

Share: r : integer;program p:|[ < if r > 0 then r := r - 1 > ;CRITICAL_SECTION.p < r := r 1 > else block_and_try_again ; NON_CRITICAL_SECTION.p]|

Nun fassen wir einiges in zwei Funktionen zusammen:

  • Funktion P (Prolayer), mit Argument x: if x > 0 then x := x - 1 else block_and_try_again
  • Funktion V (Erhöhen), mit Argument x: x := x 1

"Prolow" ist ein Wort, das sich Dijkstra ausgedacht hat und es bedeutet "versuchen zu senken".

Kommen wir nun zur neusten Version des Programms:

Geteilt: r : Semaphor;Programm p:|[ P(r) ; CRITICAL_SECTION.p ; V(r) ; NON_CRITICAL_SECTION.p]|

Und so kommen wir zu den Semaphoren von Dijkstra: natürliche Zahlen mit atomaren Operationen, die die Werte eines Semaphors um eins erhöhen oder verringern, ihn jedoch blockieren, wenn versucht wird, dem Semaphor einen Wert kleiner als 0 zu geben.

Semaphoren werden nicht nur für den gegenseitigen Ausschluss kritischer Abschnitte verwendet, sondern auch für andere Synchronisationsprobleme wie das Producer-Consumer-Problem. In diesem Fall übergibt ein Programm Daten über einen gemeinsamen Puffer, der nicht unter- oder überlaufen darf, an ein anderes Programm. Bei solchen Anwendungen können die Semaphoren auch einen Wert höher als 1 haben.

Geschichte

Dijkstra entwickelte seine Semaphoren 1963, als parallele Programme zu einem "heißen Gegenstand" wurden. Damals war es ein großes Problem, den exklusiven Zugriff auf Teile von Programmen und Computern zu kontrollieren, aber mit der Einführung von Semaphoren verschwand das Problem wie Schnee in der Sonne.

Heutzutage sind Semaphoren in der verteilten Programmierung so alltäglich, dass praktisch jeder Prozessor Anweisungen zum Implementieren von Semaphoren enthält. Auch Signalmasten gehören zur Standardausstattung von Betriebssysteme und sind die Grundlage für praktisch jeden Synchronisationsmechanismus, der innerhalb von Computern (einschließlich Monitoren) verwendet wird.

Quellen

  • EWD74 - PDF-Datei, HTML-Datei, in dem Dijkstra Semaphoren einführte
  • Über eine Methode der Multiprogrammierung (aus der Serie "Monographien in Informatik") -- W.H.J. Feijen und A.J.M. van Gasteren, ISBN 038798870X , Herausgeber Springer-Verlag