Semaphor

[NotYourfan]

Hallo,

ich habe eine Frage bzgl. Semaphor - in der Literatur steht :

"Ein Semaphor ist ein Zähler der mehreren Prozessen gleichzeitig den Zugriff auf ein gemeinsames Datenobjekt ermöglicht."

Das verstehe ich aber nicht - wir möchten doch mit Semaphor verhindern, dass mehrere Prozesse gleichzeitig Zugriff auf ein gemeinsames Datenobjekt haben. Das binäre Semaphor verstehe ich - nur der Zähler verwirrt etwas. Angenommen ich habe einen Zähler n = 5. Bedeutet das, dass 5 Prozesse/Threads gleichzeitig auf eine gemeinsame Ressource zugreifen dürfen?
Außerdem gibt es ja noch die Regel - "Es darf sich zur selben Zeit nur ein Prozess im kritischen Abschnitt befinden"

 

[dermoritz]

Ein Semaphor kannst du dir als eine Kugel in einer Schüssel vorstellen. Auf der Kugel steht zum Beispiel "Drucker". Prozessor 1 will den Drucker benutzen, schaut in die Schüssel und falls die Kugel drin liegt nimmt er sich die Kugel und benutzt den Drucker. Sobald Prozessor 1 fertig ist legt er die Kugel zurück - das ist sehr wichtig.

Drucken ist nur erlaubt/möglich wenn man die Kugel - das Semaphor besitzt.

Falls die Kugel nicht da ist muss der Prozesor warten und immer mal wieder reinschauen. Die Schüssel kann aber auch Bescheid sagen falls jemand die Kugel nimmt oder zurücklegt.

Für "Datenobjekt" wie in deiner Beschreibung ist eigentlich nicht "Zugriff" allgemein das Problem. Auf ein Datenobjekt können mehrere Prozesse gleichzeitig "LESEND" zugreifen. Das ändern/ schreiben ist das Problem und dafür kann man ein Semaphor benutzen. Man kann sich es als Kugel mit der Bschriftung "schreibe auf Datenobjekt x" vorstellen.
----
Das ganze wird unpraktisch wenn man mehrere solcher Resourcen hat. Z.b. Drucker und Scanner die auch gleichzeitig benötigt werden: Prozessor 1 nimmt sich den Drucker und Prozessor 2 nimmt sich den Scanner. Nun warten beide auf die andere Resource (Prozessor 1 auf Scanner und Prozessor 2 auf Drucker) - das sie ewig warten werden spricht man hier von einem Dead-Lock. Diese Situation ist dringend zu vermeiden.

 

[RalphS]

Stell es Dir als thread allocator vor.

Du hast 16 CPU-Threads und 28 Tasks. Also kannst Du 16 gleichzeitig zuordnen, der Rest muß irgendwie warten.

Was tust Du also? Du baust eine semaphore und sagst, 1 Task zugewiesen, semaphore um 1 geändert (der zugewiesene Task). Ein Task fertig, semaphore um 1 wieder zurückgesetzt.
16 Tasks zugewiesen, semaphore enthält nun 16 == CPU-Threadanzahl oder 0 = nix mehr frei.
Also muß der nächste Task solange warten (und die Semaphore angucken) bis diese einen freien Thread signalisiert. Dann kann der Task diesem Thread zugeordnet werden.

 

[NotYourfan]

Hey das verstehe ich vollkommen - das wäre ja ein binärer Semaphor. Die Idee dahinter verstehe ich ebenfalls. Ich hab folgendes Beispiel gefunden:

Ein Beispiel aus dem Leben ist z.B. die Benutzung eines Aufzuges, in dem maximal 5 Personen Platz haben. Ein Semaphor wäre hier ein Zähler, der auf 5 initialisiert wird und jedes Mal, wenn eine Person den Aufzug betritt, wird er um 1 herabgezählt (dekrementiert). Verlässt eine Person den Aufzug, dann wird der Zähler um 1 erhöht (inkrementiert). Ist der Zähler auf 0, so darf keine weitere Person den Aufzug betreten.

Ich verstehe nur nicht wie dieser Zähler funktionieren soll. Zum einen gibt es ja wie gesagt die Regel, dass sich zur selben Zeit nur ein Prozess im kritischen Abschnitt befinden darf und zum anderen haben wir den Zähler mit n = 5 der aussagt, dass 5 Prozesse in den kritischen Abschnitt dürfen. Diese 5 Prozesse könnten doch die gemeinsam genutzt Ressource öfters überschreiben / löschen etc.

 

[Tsu]

Dass das so eine Art größeres “Lock” ist, nur eben mit Zähler, hast du ja schon richtig. Der Zähler wird „atomar“ verkleinert und vergrößert, zum Beispiel damit:
https://de.m.wikipedia.org/wiki/Compare-and-swap

Bei den oben genannten Beispielen würde man aber einfach 5 oder 16 Worker-Threads mit Warteschlange starten.

Mehr Sinn macht eine Semaphore bei Operationen ungleicher Größe (Last, Bandbreite, …). Beispiel: Dein Download-Manager is gedeckelt auf 10 Mbps, aber ein Download will genau 6, der andere 4 Mbps; der Rest (5, 5, 7, 3…) soll warten. Entsprechend wird die Sempahore zu 10 initialisiert, „6“ bekommt den Zuschlag, „4“ passt auch noch, der Rest ist blockiert bis passend viel Bandbreite „entlassen“ wird.
(Im nächsten Schritt könnten die weniger probieren, also verhandeln. Ist aber nicht mehr der Punkt hier.)

 

[benneq]

Ich verstehe nur nicht wie dieser Zähler funktionieren soll. Zum einen gibt es ja wie gesagt die Regel, dass sich zur selben Zeit nur ein Prozess im kritischen Abschnitt befinden darf und zum anderen haben wir den Zähler mit n = 5 der aussagt, dass 5 Prozesse in den kritischen Abschnitt dürfen. Diese 5 Prozesse könnten doch die gemeinsam genutzt Ressource öfters überschreiben / löschen etc.

Es kommt halt maßgeblich darauf an, WAS man absichern will.
Wenn es um eine simple read/write Sperre geht, dann ist hier natürlich eine binäre Semaphore das richtige.
Aber es gibt quasi unendlich viele Möglichkeiten und Anwendungsfälle.

Deine 5 Prozesse müssen ja nicht identisch dumm sein, sondern die können evtl. auch untereinander kommunizieren und sich den Speicherbereich so aufteilen, dass sie sich nicht in die Quere kommen.

Oder eine ganz simple multi threaded Queue. Hier will man gleichzeitig höchstens so viele Threads wie CPU Cores laufen haben, aber die Queue kann ja trotzdem aus tausenden Tasks bestehen. Also lässt man die Tasks an der Semaphore warten bis wieder ein CPU Core frei, und dann darf der nächste rein zur Bearbeitung.

 

[Raijin]

Zum einen gibt es ja wie gesagt die Regel, dass sich zur selben Zeit nur ein Prozess im kritischen Abschnitt befinden darf und zum anderen haben wir den Zähler mit n = 5 der aussagt, dass 5 Prozesse in den kritischen Abschnitt dürfen.

Deine Schlussfolgerung ist falsch. Ja, im kritischen Abschnitt darf immer nur ein Prozess zur Zeit sein, aber das hat erstmal nichts mit n zu tun. n kann beliebig groß sein, ändert aber nichts daran, dass nur ein Prozess zur Zeit die Semaphore beackern darf. Der kritische Bereich dient dazu, dass prozessübergreifend sauber gezählt wird. Würden mehrere Prozesse gleichzeitig den Zähler neu setzen, knallt es, weil nicht mehr gewährleistet ist, dass tatsächlich nur 5 Plätze verteilt wurden. Deswegen wird der Zähler der Semaphore ausschließlich im kritischen Bereich hoch- bzw. runtergezählt und wie du ja schon selbst geschrieben hast, kann das nur ein Prozess zur Zeit. Der nächste Prozess, der den kritischen Bereich betritt, bekommt also das n zu Gesicht, das der Vorgängerprozess hinterlassen hat. Hat der Vorgänger n auf 0 gesetzt, weil er den letzten Platz genommen hat, muss der Folgeprozess entsprechend darauf reagieren und entweder warten bis n wieder >0 ist oder es gibt einen Fehler, eine Nachricht oder sonstwas vom Prozess.


Das heißt im Klartext: Die ersten 5 Prozesse holen sich von der Semaphore nacheinander einen Platz im Fahrstuhl, aber der 6. Prozess muss warten bis einer der anderen 5 den Fahrstuhl wieder verlassen hat und ein Platz frei geworden ist oder er nimmt die Treppe....

So wird ein Schuh draus

 

[NotYourfan]

Danke für die Antwort @Raijin - kannst du mir noch kurz erklären was passiert wenn der Zähler bei bspw. bei 3 ist?
1. Prozess A kommt geht in den kritischen Bereich und dekrementiert den Zähler auf 2
2. Wenn jetzt Prozess B kommt - darf dieser dann auch in den kritischen Bereich und den Zähler auf 1 dekrementieren? Oder was passiert dann?

und bezüglich "Die ersten 5 Prozessen holen sich von der Semaphore nacheinander einen Platz" - das bedeutet für mich aber trotzdem, dass das Betriebsmittel "Fahrstuhl" parallel (auch wenn sie nacheinander einsteigen) das Betriebsmittel "Fahrstuhl" benutzen.

Oder bin ich komplett auf der falschen Spur?

 

[Raijin]

1. Ja
2. Wenn A den kritischen Bereich verlassen hat, ja, denn nur dann ist sichergestellt, dass nicht zwei Prozesse gleichzeitig am Zähler schrauben. Ist A aus dem kritischen Bereich, hat der Zähler einen eindeutig definierten Wert, in dem Falle dann 2. B Betritt den Bereich und C müsste abermals warten bis B damit fertig ist, denn erst dann ist sicher welchen Wert der Zähler nach B hat, sei es 1 oder wieder 3, weil B ja auch aussteigen könnte.

"Die ersten 5 Prozessen holen sich von der Semaphore nacheinander einen Platz" - das bedeutet für mich aber trotzdem, dass das Betriebsmittel "Fahrstuhl" parallel (auch wenn sie nacheinander einsteigen) das Betriebsmittel "Fahrstuhl" benutzen.

Tun sie ja auch. Der Fahrtstuhl bietet nun mal 5 Plätze, die parallel genutzt werden können. Das ist im Prinzip nichts anderes als wenn es bei einem Skiverleih 100 Paar Ski gibt. Die werden ebenso parallel genutzt wie die Plätze im Fahrstuhl, nur dass der Fahrstuhl in dem Fall die Dimension eines Skigebiets hat. Kommt der 101. Skifahrer zum Verleih, geht er leer aus bzw. muss warten bis ein Paar Ski wieder zurückgegeben wurde.

Es gibt verschiedene Typen von Ressourcen. Solche, die nur exklulsiv nutzbar sind wie zB ein Telefon (mal von Freisprechen abgesehen), und solche, die parallel nutzbar sind wie zB ein Fahrstuhl oder ein Bus, aber auch ein Museum oder ein Skiverleih.
Effektiv ist eine exklusive/binäre Semaphore nichts anderes als eine Zähler-Semaphore mit n=1, sie darf also nur 1x parallel genutzt werden und nicht 5x parallel wie der Fahrstuhl.

Du musst allerdings klar unterscheiden zwischen der eigentlichen Ressource, dem Fahrtstuhl, und der Semaphore, die den Zugriff auf die Ressource regelt. Die Semaphore muss zwingend exklusiv bedient werden, es gibt nur diese eine und die muss alle 5, 50, 5000 zugreifenden Prozesse einzeln und nacheinander abfrühstücken. Was die Prozesse hinterher mit ihrem Ticket aus dem Zähler der Semaphore anfangen, hat damit nichts zu tun.

Wenn ein Museum beispielsweise 50 gleichzeitige Besucher zulässt, ist das Drehkreuz am Eingang die Semaphore. Sind 50 Besucher drin, bleibt das Drehkreuz zu bis ein Besucher rauskommt. Ob die Besucher drinnen nun die Skulpturen anschauen, die Gemälde bewundern oder einfach nur auf die Toilette müssen, ist dem Drehkreuz aka Semaphore vollkommen egal, Hauptsache hinter der Semaphore sind nur 50 Besucher gleichzeitig aktiv, was auch immer sie dann tun - inkl. sofort Kehrt machen und wieder rausgehen (und den Platz wieder freimachen).

 

[Skysnake]

Wenn A den kritischen Bereich verlassen hat, ja, denn nur dann ist sichergestellt, dass nicht zwei Prozesse gleichzeitig am Zähler schrauben.

Ich glaube die Verwirrung kommt daher, dass du völlig korrekt den allgemeinen Fall beschreibst, in dem die Semaphore selbst über eine critical section nachbilden musst.

Bei x86 sollte das aber einfach über eine atomare addition nachgebildet werden können.

Das ist dann halt wo die nützlichen Eigenschaften mancher Hardware benutzt werden können. Apriori klar ist das aber nicht, das man auch mehr als nen atomaren inkrement/dekrement hat.

 

[AW4]

Seh die Semaphore mit n > 1 mal eher wie einen "exklusiven Bereich", zu dem der Zugang/Zugriff moderiert werden muss/soll.
Der "exklusive Bereich" selber regelt dabei aber nicht den Zugriff auf eine einzelne Ressource.
Die einzelne(n) Ressource(n) innerhalb des "exklusiven Bereichs" muss/müssen im Zweifel immer noch einzeln mit einer Critical Section abgesichert werden.
Der "exklusive Bereich" dient dabei als Garant dafür, dass ein Prozess mit Zugang zum "exklusiven Bereich" auch irgendwann einmal fertig werden wird.

Ein aus der Luft gegriffenes, eventuell nicht ganz praktikables aber hoffentlich anschauliches Beispiel:
Hast du z.B. eine Liste, in die Ergebnisse von parallelisierten Berechnungen, mit relativ kurzen Intervallen, hinterlegt werden sollen und lässt 1000 Prozesse/Threads darauf los, ist die CPU mehr damit beschäftigt, den exklusiven Zugriff auf die Liste zu regeln, als damit, neuen Inhalt der Liste anzuhängen oder gar die parallelisierten Berechnungen auszuführen.
Beschränkst du den Zugriff, z.B. mit einer Semaphore, auf weniger Prozesse/Threads verringert sich auch der Overhead und es bleibt mehr Prozessorzeit für alles andere und im Schnitt sind alle notwendigen Berechnungen und deren Protokollierung in der Liste in weniger Zeit abgeschlossen.