Semaphore: Fehler in Wikipedia

freakC++

was glaubst Du, was ich gemacht habe?

"Bei einem Aufruf der P-Operation wird der Zähler dekrementiert. Ist der Zähler danach größer gleich 0, so setzt der Prozess seine Aktionen fort. Ist der Zähler jedoch kleiner als 0, kehrt der Kontrollfluss nicht aus der Operation zurück. Der aufrufende Prozess wird blockiert und in die Warteschlange des Semaphors eingereiht. Bei einem Aufruf der V-Operation wird der Zähler inkrementiert."

Am Anfang steht zwar, dass der Zähler nicht unter 0 fallen kann, aber in diesem Beispiel ist das ja anders!

LG, freakC++

volkard

Jo, vielleicht kennen sich die da mehr aus.
http://ko.wikipedia.org/wiki/세마포어

hustbaer

freakC++ schrieb:

Muss in der mit "Fehler" markierten Zeile das >= nicht zu <= werden?

Ja, es muss.
Guck mal auf die Diskussionsseite, das wurde schon vor Jahren diskutiert, immer wieder mal gefixt, aber anscheinend finden sich immer wieder genug Idioten die es wieder falschbiegen.
Tjoah...

BTW: was soll die Scheisse mit "nicht markiert"? Wer kann Änderungen auf Wikipedia freigeben - braucht man da jetzt neuerdings einen Account dazu?

hustbaer schrieb:

freakC++ schrieb:

Muss in der mit "Fehler" markierten Zeile das >= nicht zu <= werden?

Ja, es muss.
Guck mal auf die Diskussionsseite, das wurde schon vor Jahren diskutiert, immer wieder mal gefixt, aber anscheinend finden sich immer wieder genug Idioten die es wieder falschbiegen.
Tjoah...

Nein, muss es nicht. Was soll das für einen Sinn machen, zu blockieren und entblocken die gleiche Bedingung zu verwenden?

Ok, ich erklärs mir selber.
s.zaehler ist nicht die Anzahl der Elemente in der Queue.
Aber warum schreiben die dann nicht einfach.

/* up() */
 void V (Semaphor s) {
   s.zaehler = s.zaehler + 1;
   if (s.queue.size> 0) 
      einen_entblocken(s.queue); /* Entblockieren eines Prozesses aus der Warteschlange */
 }

hustbaer

Weil es so funktioniert, und anders rum halt nicht.

Ich weiss, es ist kontraintuitiv, und scheint erstmal keinen Sinn zu machen, was vermutlich auch der Grund sein wird warum es immer wieder kaputt-editiert wurde.

Machen wir ein Beispiel:

Sagen wir du hast ein Auto, ein Sportwagen, da passen zwei Leute rein.
Das Auto ist erstmal leer.
Also haben wir plätzeFrei = 2

Jetzt steigt einer ein: plätzeFrei = 1
Und noch einer steigt ein: plätzeFrei = 0

Das Auto ist jetzt voll.

Jetzt kommt noch einer, der muss aber warten. Man könnte jetzt plätzeFrei auf Null lassen, und irgendwo extra vermerken wer und wie viele warten.
Tun wir aber nicht, wir setzen stattdessen plätzeFrei = -1 .
plätzeFrei < 0 bedeutet also "Auto ist voll und es warten noch Leute die einsteigen möchten" (Leute = mindestens einer).

Der Code fürs einsteigen ist also

einsteigen()
{
    plätzeFrei = plätzeFrei - 1   -- wir versuchen erstmal ob wir direkt noch reinkommen
    if (plätzeFrei < 0)           -- und prüfen dann ob es funktioniert hat
    {
       -- nö, war kein platz mehr, wir müssen warten
       warten()  -- blockiert bis jemand der ausgestiegen ist uns benachrichtigt hat
    }
    -- wir können jetzt einsteigen
}

Jetzt müssen wir noch den Code fürs aussteigen definieren. Klar ist, wenn einer aussteigt, dann ist unmittelbar danach immer Platz im Auto. Es kann also einer wieder einsteigen. Jetzt müssen wir nur wissen ob jmd. wartet, weil wenn jemand wartet, dann müssen wir den benachrichtigen.

Die Bedingung ob jmd. benachrichtigt werden soll hat also nichts damit zu tun ob noch Platz frei ist, denn das ist nach dem einer ausgestiegen ist immer der Fall. Sondern die Bedingung ist ob jemand wartet.

Der Code zum Aussteigen wird also:

aussteigen()
{
    -- erstmal gucken ob einer wartet
    wartetJemand = plätzeFrei < 0

    -- aussteigen
    plätzeFrei = plätzeFrei + 1

    -- ggf. einen wartenden benachrichtigen
    if (wartetJemand)
        einen_wartenden_benachrichtigen();
}

Das ganze können wir jetzt umschreiben, so dass die Hilfsvariable wartetJemand wegfällt. Dadurch dass der Test jetzt nach dem Inkrementieren von plätzeFrei erfolgt verschiebt sich natürlich die Schwelle gegen die wir prüfen müssen um eins nach oben. Aus < 0 wird also < 1 , was wir auch als <= 0 schreiben können:

aussteigen()
{
    -- aussteigen
    plätzeFrei = plätzeFrei + 1

    -- ggf. einen wartenden benachrichtigen
    if (plätzeFrei <= 0)
        einen_wartenden_benachrichtigen();
}

Tadaa.

Was soll das überhaupt für ein Code sein? Wie soll das mit Multithreading funktionieren?
Wenn man es so macht und zaehler ist anfangs 0.

/* down() */
 void P (Semaphor s) {
   s.zaehler = s.zaehler - 1;
   if (s.zaehler < 0)
      selbst_blockieren(s.queue); /* Blockieren des Prozesses, Einreihung in Warteschlange */
 }

/* up() */
 void V (Semaphor s) {
   s.zaehler = s.zaehler + 1;
   if (s.zaehler <= 0)
      einen_entblocken(s.queue); /* Entblockieren eines Prozesses aus der Warteschlange */
 }

Thread 1 ruft P auf und kommt bis Zeile 5 führt sie aber noch nicht aus. zaehler ist also -1.
Thread 2 ruft V auf und will dann in Zeile 12 einen Thread entblocken, der sich aber noch garnicht in die queue eingetragen hat.

hustbaer

dann erklär mal schrieb:

Aber warum schreiben die dann nicht einfach.

/* up() */
 void V (Semaphor s) {
   s.zaehler = s.zaehler + 1;
   if (s.queue.size> 0) 
      einen_entblocken(s.queue); /* Entblockieren eines Prozesses aus der Warteschlange */
 }

Wenn du es genau wissen willst, dann musst du Dijkstra fragen.

Ich kann nur raten... vielleicht weil man sich, wenn man nur nach s.zaehler geht, den Test auf die Queue sparen kann, so lange niemand wartet.

Wenn die Member-Variablen der Queue in der selben Cache-Line zu hause sind wie der Zähler sollte das allerdings relativ egal sein, von daher keine tolle Optimierung.

hustbaer

dann erklär mal schrieb:

Was soll das überhaupt für ein Code sein? Wie soll das mit Multithreading funktionieren? ...

Es steht direkt unter den Code-Beispielen

Wikipedia schrieb:

Beide Operationen müssen unteilbare, atomare Aktionen sein. Dadurch ist garantiert, dass nach dem Aufruf einer Operation eines Semaphors kein anderer Prozess auf den gleichen Semaphor durch einen Operationsaufruf modifizierend zugreifen kann, bevor die zuerst aufgerufene Semaphoroperation vollständig ausgeführt worden ist. Die Unteilbarkeit ist notwendig, um die Synchronisation zu organisieren und Wettlaufsituationen bei Ausführung der Semaphoroperationen durch parallele Prozesse zu vermeiden.

Könnte man besser formulieren, z.B. indem man "Beide Operationen müssen..." durch "Die beiden Operationen P und V müssen..." ersetzt.

Also braucht man ein Mutex, um ein Semaphor zu implementieren? Und warum machen die dann ein C++ Beispiel dazu, wenn es so garnicht funktioniert, weil das in C++ keine unteilbaren Aktionen sind?