Nutzung eines binären Semaphores für simples Erzeuger-Verbraucher-Problems

[Cinematic]

Die Lösung mit 2 Semaphoren verstehe ich, aber wie soll das mit nur 1 binären Semaphor gehen? Könnte das jemand so darstellen wie in den letzten beiden blauen Zeilen auf dem Screenshot gezeigt?

p() steht hier übrigens für wait() und v() für signal()

 

[ayngush]

Such mal nach "mutex"

 

[Cinematic]

Ich weiß was ein mutex ist.

Nennen wir die binäre Semaphor einfach mal sem, und laut Musterlösung soll diese ja mit 1 initialisiert sein.

P1: p(sem) schreiben(); v(sem)
P2: p(sem) lesen(); v(sem)

Wäre das einzige halbwegs sinnvolle was mir einfallen würde. Das ist nur halbwegs sinnvoll, weil hierdurch nicht sichergestellt wird, dass P1 erst dann wieder schreiben kann, wenn das Bild gelesen wurde; und analog P2 erst dann wieder liest, wenn ein neues Bild im Speicher ist.

 

[ayngush]

Das wäre aber die Lösung.

Wichtig ist nur, dass nach der Initialisirung init(sem, 1) im Ablauf der Prozess P1 vor dem Prozess P2 gestartet wird, sonst wird "einmal Grütze" gelesen. Die Warteschlange verwaltet das OS und da hüpfen P1 und P2 ja wechselseitig immer wieder an der Ende der Warteschlange. Wechselseitiger Ausschluss halt. Oder eben Mutual Exclusion. Kurz MutEx aber du weißt ja, was ein mutex ist

 

[Cinematic]

Danke für deinen Vorschlag. Jedoch nach meinem Verständnis von Semaphoren macht das keinen Sinn. Vielleicht habe ich da aber auch ein Verständnisfehler. Andernfalls:

Semaphoren haben genauer gesagt einen Wert, keinen Zustand.
Man kann die p(sem) Funktion nicht von einem Wert abhängig machen.
p(sem) funktioniert so, dass wenn sem == 0, blockiert der Prozess, ansonsten wenn sem > 0, wird der sem um 1 niedriger gemacht und der Prozess blockiert nicht.
v(sem) erhöht einen sem einfach um +1

Mit der Lösung

P1: p(sem) schreiben(); v(sem)
P2: p(sem) lesen(); v(sem)

wäre zwar sichergestellt, dass nicht gleichzeitig gelesen und geschrieben werden kann. Aber es könnte z.B. 100 mal hintereinander geschrieben werden, ohne dass ein einziges mal gelesen wird.

Mit einem einzigen Semaphor kann man meiner Meinung nach nicht die sich abwechselnde Reihenfolge schreiben, lesen, schreiben, lesen, schreiben,... gewährleisten.
Genau das sagt die Musterlösung aber, und ich verstehe nicht wie das gehen soll.

 

[ayngush]

Okay, das erklärt es. p() und v() ist dir noch nicht in Bezug auf die Funktionsweise mit den OS Process Queue geläufig.

Die P()-Operation eines Semaphors ist als atomare Operation wie folgt definiert:

• Hat die Zählervariable einen positiven Wert (>0), dann verringere den Wert der Zählvariablen um 1.
• Wenn die Zählvariable den Wert 0 hat, dann blockiert die P()-Operation den aufrufenden Prozess und fügt ihn an das Ende ihrer Warteschlange hinzu.

Die V()-Operation eines Semaphors ist als atomare Operation wie folgt definiert:

• Wenn die Warteschlange nicht leer ist, dann entblockiere den ersten Prozess der Warteschlange.
• Ist die Warteschlange leer, dann erhöhe den Wert der Zählervariable um 1.

Source: http://vfhcab.oncampus.de/loop/Semaphore

 

[Cinematic]

Das hatte ich aber eigentlich schon so verstanden. Die Process Queue spielt bei dieser Aufgabe meiner Meinung nach auch keine Rolle.

Betrachten wir dazu folgendes Beispiel:

P1 versucht dauerhaft zu schreiben, und P2 nur alle 60sek.

Der Semaphor ist gemäß Musterlösung mit 1 initialisiert.

P1: p(sem) schreiben(); v(sem)
P2: p(sem) lesen(); v(sem)

P1 ruft p(sem) auf, dadurch wird der sem auf 0 gesetzt und P1 kann übergehen zu schreiben(), daraufhin wird mit v(sem) der Semaphor wieder auf 1 gesetzt. Das schreiben() dauert nur Bruchteile einer Sekunden.
Nun versucht P1 direkt wieder zu schreiben, was ihm auch gelingt, da der Semaphor ja wieder auf 1 ist.
Das darf aber nicht passieren.
Nach einem Schreibvorgang muss sichergestellt sein, dass erst ein Lesevorgang passieren muss, bevor P1 wieder schreiben kann.

 

[Revan1710]

Man kann die p(sem) Funktion nicht von einem Wert abhängig machen.

Das brauchst du auch nicht, wenn deine Programmlogik das abbildet. P2 ist ja erst am Zug nachdem P1 v(sem) aufuft. Wichtig ist dabei also, dass P1 die Semaphore auch wirklich nur dann fregibt - v(sem), wenn auch etwas geschrieben wurde. Ansonsten rennst du in die Problematik hinein, dass P2 ein leeres Bild liest.

Auf der anderen Seite geht es bei P2 unmittelbar weiter nach P1: v(sem) und P2 sperrt die Semaphore bis auch der Lesevorgang wieder abgeschlossen ist.

 

[ayngush]

Auf der anderen Seite geht es bei P2 unmittelbar weiter nach P1: v(sem) und P2 sperrt die Semaphore bis auch der Lesevorgang wieder abgeschlossen ist.

Und P1 stellt sich in der Zwischenzeit durch seinen Aufruf von p(sem) wieder "brav" hinten an. So kommt die "Wechselwirkung" zustande.

 

[Cinematic]

Du bzw. ihr beide setzt dabei voraus, dass P1 und P2 sich dauerhaft auf der Ready Queue befinden. Das geht aber aus der Aufgabenstellung nicht hervor. P1 oder P2 könnten auch Blocked sein, da sie irgendwelche E/A Operationen ausführen, oder was auch immer.

 

[ayngush]

Dann hättest du einen Deadlock.
Ich verstehe p() und v() und binäre Semaphore in dem Kontext schon so, dass sie mit der OS Warteschlange arbeiten. Eine Semaphore ist ja nicht eine einfache Eigenschaft / Variable.

Edit: Mir hat man mal gesagt, dass wenn etwas aus der Aufgabenstellung nicht hervorgeht, dass man Annahmen treffen soll, die man der Lösung vorausstellt

Edit2: Eine Synchronisation wirst du mit nur einer binären Semaphore nicht hinbekommen, das geht nach meinem Verständnis nur über die Process Quee... Kackwort! Über die Warteschlange.

 

[Cinematic]

Ich habe das noch etwas ungenau geschrieben.
Sagen wir mal das CPU Scheduling sieht vor, dass jeder Prozess eine Zeitscheibe von 10ms zugeteilt bekommt (Round Robin Scheduling), aber sowohl schreiben als auch lesen dauern nur 2ms.
Was würde P1 dann davon abhalten innerhalb seiner Zeitscheibe 5mal hintereinander zu schreiben?

EDIT (Zusatz): Wenn P1 von alleine nach einem Schreibvorgang die CPU abgibt, ist ja alles okay, aber dann bräuchten wir nichtmal einen Semaphor. Dann würde das OS Scheduling schon von ganz alleine dafür sorgen, dass alles synchronisiert abläuft.
Aber es steht nirgends, dass P1 nach einem Schreibvorgang von alleine die CPU abgibt.

 

[ayngush]

Die Prozesswarteschlange und die Tatsache, dass P1 einmal v(sem) aufgerufen, sich damit hinter P2 anstellt und P2 freigegeben hat aber P2 v(sem) dabei noch nicht aufgerufen und damit P1 wieder freigegeben hat. Round Robin wird in so einen Fall auch nicht zur Anwendung kommen. Aber spannend, dass du das einbeziehst.

 

[Cinematic]

P1 ruft doch selbst nach seinem Schreibvorgang v(sem) auf und erhöht somit den sem wieder auf 1, was dazu führt, dass P1 auch direkt wieder an p(sem) vorbeigehen kann.

 

[ayngush]

Nein, weil "Wenn die Warteschlange nicht leer ist, dann entblockiere den ersten Prozess der Warteschlange." Und das würde ja P2 und nicht P1 sein. P1 ist solange in der Warteschalange, weil es ja Versucht während P2 noch läuft (sem also den Wert 0 hat) p(sem) aufzurufen und dann gilt "Wenn die Zählvariable den Wert 0 hat, dann blockiert die P()-Operation den aufrufenden Prozess und fügt ihn an das Ende ihrer Warteschlange hinzu."

 

[Cinematic]

Achso, jetzt verstehe ich was ihr meint. Während P1 am schreiben ist, hat der sem den Wert 0, und daher befindet sich P2 bereits in der Warteschlange für seinen p(sem), d.h. P2 wartet darauf, dass von irgendwoher ein v(sem) ausgeführt wird, so dass er fortfahren kann. Richtig?

 

[ayngush]

Richtig! Jetzt hast du es. Nur, dass P2 nicht "auf seinen p(sem) wartet" sondern, "durch seinen P2 p(sem) Aufruf während sem den Wert 0 hat, weil P1 schreibt und sich "zwischen" P1 p(sem) und P1 v(sem) befindet, hinten eingereiht wird und auf den Aufruf von P1 v(sem) wartet".

 

[Revan1710]

Ich verstehe schon deine Bedenken, ich könnte die Threads ja auch so gestalten, dass P1 nach v(sem) fröhlich für längere Zeit ein Bild in seinen lokalen Speicher malt, während P2 auch schon wieder fertig mit Lesen ist und v(sem) aufgerufen hat.
Dann wäre die Semaphore frei und der nächste Thread der wieder bei p(sem) landet bekommt Vorfahrt, also evtl. auch wieder P2 als nächstes, wenn P1 immer noch am "malen" ist.

Ich glaube daher also nicht, dass diese Methode für jedes Szenario wasserdicht ist, aber darauf will die Frage ja vmtl. auch garnicht hinaus. Es geht ja auch nur um ein simples Beispiel mit Abwechselnd lesen/schreiben und nichts was die Threads nach v(sem) vlt. noch alles treiben.

 

[ayngush]

Sie wollen wohl darauf abzielen, dass durch die Aufgabe mutex verstanden wird, ohne es explizit zu erwähnen bzw. akzeptieren es als einen Lösungsweg.

Ich verstehe schon deine Bedenken, ich könnte die Threads ja auch so gestalten, dass P1 nach v(sem) fröhlich für längere Zeit ein Bild in seinen lokalen Speicher malt, während P2 auch schon wieder fertig mit Lesen ist und v(sem) aufgerufen hat.

Dieses Szenario kann mit einen binären Semaphor aber nicht eintreten. P1 kann nicht einfach "fröhlich weiter loopen", da sein eigener p() Aufruf während Prozess 2 noch am lesen ist P1 unterbrechen und an das der Ende der Warteschlange (der Semaphore, verwaltet vom OS) befördert.

Ihr macht euch dabei zu viele Gedanken um Laufzeiten. Das ist kein zeitliches Problem, sondern ein binäres Problem.

 

[Cinematic]

Genau solche Bedenken hatte ich bei dem Verfahren @Revan1710

Aber ja, das Szenario soll wohl simpel gehalten sein, und dann klappt es tatsächlich auch mit einen binären Semaphor. Danke euch beiden.