# Pseudocode Kinokarten Verkauf



## Sonnenblume123 (28. Jul 2018)

Guten Tag,
auf dem Bild seht ihr ein Programm, das folgendes realisiert:
Eröffnung eines weiteren Kartenschalters wegen zu langer Wartezeiten 
• Beide Schalter zur gleichen Zeit geöffnet. 
• Für jeden Schalter stehen ein eigener Prozessor und Drucker zur Verfügung. •
 Prozessoren können miteinander kommunizieren (gemeinsamer Speicher oder Austausch von Nachrichten).




Nun soll ja beantwortet werden, ob es klappt oder nicht.
Meine Antwort: nein.
Meine Begründung durch Angabe einer Ausführungssequenz:
p0->p1->p2->p3->p4->q0->q1->q2->q3->q4->p5->q5
Platz wird doppelt belegt!

Würdet ihr mir da zustimmen?


----------



## Xyz1 (28. Jul 2018)

Sonnenblume123 hat gesagt.:


> Würdet ihr mir da zustimmen


jo

Du musst das natürlich ausführlich Begründen viel Spaß


----------



## Sonnenblume123 (29. Jul 2018)

Reicht nicht nur die Ausführungssequenz?


----------



## Xyz1 (29. Jul 2018)

Es gibt mindestens 479001600 mögliche Ausführungssequenzen von denen einige der Platz doppelt belegt wird....

Die willst du doch nicht alle auflisten?


----------



## httpdigest (29. Jul 2018)

Sonnenblume123 hat gesagt.:


> Nun soll ja beantwortet werden, ob es klappt oder nicht.
> Meine Antwort: nein.


Ich würde sagen, deine eine Ausführungssequenz ist vollkommen ausreichend, um zu beweisen, dass es nicht klappt, bzw. eher um die Behauptung zu widerlegen, dass es klappt.
Es soll ja nicht gezeigt werden, dass es _niemals_ funktioniert. Wenn nur eine einzige mögliche Ausführungssequenz existiert, bei der es nicht funktioniert, dann ist damit bewiesen, dass eine solche nebenläufige Ausführung zu Fehlern führen _kann_ und somit nicht fehlerfrei verwendbar ist.


----------



## Xyz1 (29. Jul 2018)

Man könnte auch sagen in 33,3 % der Fälle funktioniert das nicht. Agree @httpdigest ?


----------



## Xyz1 (29. Jul 2018)

Ah schnell eine Berichtigung , in 31 % der Fälle.


----------



## httpdigest (29. Jul 2018)

Das noch zusätzlich zu beweisen wäre definitiv den einen oder anderen Bonuspunkt wert.


----------



## Xyz1 (29. Jul 2018)

ja ich habe mich gefragt, was wie hier dabei zu beweisen wäre....
Jetzt habe ich den Probabilistischen Ansatz gewählt.


----------



## httpdigest (29. Jul 2018)

Naja, zuerst einmal müsste man zeigen, ob und falls ja, warum oder falls nein, warum nicht die Wahrscheinlichkeit unabhängig von 'n' ist, was nicht ganz offensichtlich so ist oder nicht so ist.
Also z.B. bei n > 2 und wenn die ersten zwei Plätze bereits belegt sind, wäre ja auch die folgende fehlerhafte Sequenz möglich:
p0,p1,p0,p1,p0,p1,p2,p3,p4,q0,q1,q0,q1,q0,q1,q2,q3,q4,p5,q5


----------



## Xyz1 (29. Jul 2018)

httpdigest hat gesagt.:


> unabhängig von 'n' ist, was nicht ganz offensichtlich so ist


ja das stimmt
Man müsste noch eine Gewichtung hernehmen.... Das kommt unter Anderem auf die Hardware an


----------



## Xyz1 (29. Jul 2018)

Ich bin einfach mal mit Monte-Carlo darauf losgegangen, unter der Annahme dass die Wahrscheinlichkeiten unabhängig von `n` sind, hier mit n = 2.

```
if (p1 < q1) {
    if (p5 < q1) {
        notLocks++;
    } else {
        locks++;
    }
} else {
    if (q5 < p1) {
        notLocks++;
    } else {
        locks++;
    }
}
```


----------



## Xyz1 (29. Jul 2018)

Hier steht es https://de.wikipedia.org/wiki/Monte-Carlo-Simulation#Mathematik .
Weiß nicht ob ich mit n = 2 ergodisch bin, ist mir aber auch egal.


----------



## AndiE (29. Jul 2018)

Welchen Sinn machen p3 und q3?


----------



## httpdigest (29. Jul 2018)

AndiE hat gesagt.:


> Welchen Sinn machen p3 und q3?


Sie sorgen dafür, dass die Schleife nicht erneut betreten wird, dadurch, dass die Schleifenbedingung i <= n (die implizit durch die Formulierung der Schleife als "for i from 1 to n" angegeben ist) nicht mehr erfüllt wird.
Es ist also effektiv ein Java "break;"


----------



## Xyz1 (29. Jul 2018)

Ja ist ne neumodische Schreibweise für break; bzw die übliche im Pseudocode.


----------



## Xyz1 (30. Jul 2018)

DerWissende hat gesagt.:


> Es gibt mindestens 479001600 mögliche Ausführungssequenzen ....


Oh man ey, ich könnte echt heulen...
Alles falsch was ich geschrieben hatte...
Für n = 2 ergeben sich "nur" 3432 *gültige* Ausführungssequenzen, bei denen es bei einigen zu "Platz doppelt belegt" kommt: Hier sind einmal die ersten 15 und letzten 15 aufgelistet 

```
n = 2
     size() = 3432
alis.get(0) = [p0, p1, p2, p3, p4, p5, p6, q0, q1, q2, q3, q4, q5, q6]
alis.get(1) = [p0, p1, p2, p3, p4, p5, q0, p6, q1, q2, q3, q4, q5, q6]
alis.get(2) = [p0, p1, p2, p3, p4, p5, q0, q1, p6, q2, q3, q4, q5, q6]
alis.get(3) = [p0, p1, p2, p3, p4, p5, q0, q1, q2, p6, q3, q4, q5, q6]
alis.get(4) = [p0, p1, p2, p3, p4, p5, q0, q1, q2, q3, p6, q4, q5, q6]
alis.get(5) = [p0, p1, p2, p3, p4, p5, q0, q1, q2, q3, q4, p6, q5, q6]
alis.get(6) = [p0, p1, p2, p3, p4, p5, q0, q1, q2, q3, q4, q5, p6, q6]
alis.get(7) = [p0, p1, p2, p3, p4, p5, q0, q1, q2, q3, q4, q5, q6, p6]
alis.get(8) = [p0, p1, p2, p3, p4, q0, p5, p6, q1, q2, q3, q4, q5, q6]
alis.get(9) = [p0, p1, p2, p3, p4, q0, p5, q1, p6, q2, q3, q4, q5, q6]
alis.get(10) = [p0, p1, p2, p3, p4, q0, p5, q1, q2, p6, q3, q4, q5, q6]
alis.get(11) = [p0, p1, p2, p3, p4, q0, p5, q1, q2, q3, p6, q4, q5, q6]
alis.get(12) = [p0, p1, p2, p3, p4, q0, p5, q1, q2, q3, q4, p6, q5, q6]
alis.get(13) = [p0, p1, p2, p3, p4, q0, p5, q1, q2, q3, q4, q5, p6, q6]
alis.get(14) = [p0, p1, p2, p3, p4, q0, p5, q1, q2, q3, q4, q5, q6, p6]
...
alis.get(3417) = [q0, q1, q2, q3, q4, p0, q5, p1, p2, p3, p4, p5, p6, q6]
alis.get(3418) = [q0, q1, q2, q3, q4, p0, q5, p1, p2, p3, p4, p5, q6, p6]
alis.get(3419) = [q0, q1, q2, q3, q4, p0, q5, p1, p2, p3, p4, q6, p5, p6]
alis.get(3420) = [q0, q1, q2, q3, q4, p0, q5, p1, p2, p3, q6, p4, p5, p6]
alis.get(3421) = [q0, q1, q2, q3, q4, p0, q5, p1, p2, q6, p3, p4, p5, p6]
alis.get(3422) = [q0, q1, q2, q3, q4, p0, q5, p1, q6, p2, p3, p4, p5, p6]
alis.get(3423) = [q0, q1, q2, q3, q4, p0, q5, q6, p1, p2, p3, p4, p5, p6]
alis.get(3424) = [q0, q1, q2, q3, q4, q5, p0, p1, p2, p3, p4, p5, p6, q6]
alis.get(3425) = [q0, q1, q2, q3, q4, q5, p0, p1, p2, p3, p4, p5, q6, p6]
alis.get(3426) = [q0, q1, q2, q3, q4, q5, p0, p1, p2, p3, p4, q6, p5, p6]
alis.get(3427) = [q0, q1, q2, q3, q4, q5, p0, p1, p2, p3, q6, p4, p5, p6]
alis.get(3428) = [q0, q1, q2, q3, q4, q5, p0, p1, p2, q6, p3, p4, p5, p6]
alis.get(3429) = [q0, q1, q2, q3, q4, q5, p0, p1, q6, p2, p3, p4, p5, p6]
alis.get(3430) = [q0, q1, q2, q3, q4, q5, p0, q6, p1, p2, p3, p4, p5, p6]
alis.get(3431) = [q0, q1, q2, q3, q4, q5, q6, p0, p1, p2, p3, p4, p5, p6]
         locks = 2346
      notLocks = 1086
                 68.35664335664336
```
Ok? 

Ich habe mich gefragt was bei n = 3 (also es gibt 3 Karten....) passiert


----------



## AndiE (30. Jul 2018)

Was ist mit der 3. Nebenbedingung? Wenn ich das als Modell übertrage, dann dauert es zwischen zwei Buchungsvorgängen eine Zeit t, deren zwischen zwei Werten (tmin und tmax) schwankt. So gesehen ist es recht unwahrscheinlich, dass p1 und q1 zum gleichen Zeitpunkt ausgeführt werden. Somit kann der Algorithmus so wie angegeben funktionieren.


----------



## httpdigest (30. Jul 2018)

Was für eine 3. Nebenbedingung? Du meinst "Prozessoren können miteinander kommunizieren (gemeinsamer Speicher oder Austausch von Nachrichten)."?
Gemeinsam genutzter Speicher ist genau der Grund für solche Fehler.
Ansonsten macht deine Ausführung nicht viel Sinn.
Hier ist von mehreren Prozessoren die Rede, die die Instruktionen beliebig parallel/verschränkt ausführen können. Somit ist es sehr wohl wahrscheinlich.


----------



## Xyz1 (30. Jul 2018)

@AndiE Ich glaube du hast eine Ausführungssequenz noch nicht verstanden.


----------



## AndiE (30. Jul 2018)

Das mag sein. Ich stelle mir das so vor, dass in einem Kinosaal 100 Plätze zu vergeben sind. Diese n=100 Karten für die Plätze 1...100 werden von 2 Schaltern verkauft, in denen zwei Personen P und Q sitzen. Zwischen den beiden Schaltern ist eine, Wand die eine Platte enthält, wo beide die verkauften Plätze abstreichen können( entspricht S[n]). Selbst wenn beide Schalter zeitgleich aufmachen, wird der Käufer bei P einen Augenblick vor dem Käufer bei Q seine Anfrage machen. Da der Käufer bei P aber erst sein Geld suchen muss, kann Q den nächsten Kunden bereits vor P bedienen. Das ergäbe dann: P,Q,Q,P wenn man aufschreibt, wer die Plätze 1 bis 4 verkauft hat. 

Wo liegt nun mein Fehler?


----------



## httpdigest (30. Jul 2018)

Der Fehler liegt darin, zu glauben, dass die einzelnen Operationen:
1. die Abfrage, ob ein Platz bereits besetzt ist; und
2. das Belegen des Platzes
eine atomare Operation sowohl für P als auch für Q darstellt.
Das ist NICHT der Fall. Die einzelnen Operationen können P und Q beliebig verschränkt ausführen.
Das heißt: Kunde Müller kommt zu P und Kunde Meier kommt zu Q. P und Q schauen, ob Platz 1 belegt ist. Sowohl P und Q kommen zu dem Schluss: Nein, ist noch nicht belegt. Also setzen sowohl P als auch Q bei Platz 1 eine Reservierung. Aus Sicht von P und Q ist die ganze Transaktion jetzt abgeschlossen, obwohl ja jetzt Meier und Müller denselben Platz haben.


----------



## Xyz1 (30. Jul 2018)

AndiE hat gesagt.:


> Wo liegt nun mein Fehler?


Das Du Nebenläufigkeit noch nicht verstanden hast....
Zwei echte Menschen welche etwas durchstreichen blockieren sich gegenseitig dabei!!
( @httpdigest hat es gerade erklärt )


----------



## AndiE (30. Jul 2018)

@httpdigest: Wann tritt dieser Zustand ein? Wenn beide Prozesse gleichzeitig auf die Ressource S zugreifen. Da ist eben die Frage für mich, wie wahrscheinlich es ist, dass auf die Ressource S beide Prozesse gleichzeitig lesend zugreifen. Wenn man mal genau ist, sind es 3 Prozessor-Schritte: In S an Stelle n den Wert lesen, Wert mit Null vergleichen und an s[n] eine 1 schreiben. Wie groß ist die Wahrscheinlichkeit, dass zwei Zeiträume, die gleichverteilt zufällig von 2 bis 10 s dauern, gleichzeitig beginnen, wobei natürlich die beiden Startwerte unterschiedlich sind, also bei P beginnt der erste Prozess bei t=0 und bei Q beim Zeitpunkt 2<t<10? Wobei man auch die Dauer bedenken muss, die zum Durchsuchen des Arrays gebraucht wird.

Ansonsten ist natürlich die Frage, wie man das so lösen kann, dass es dennoch funktioniert. Da würde ich nicht erst die Sequenzen p1 bis p5 und dann die Sequenzen q1 bis q5 durchgehen lassen, da ja alleine der Druck meist länger dauert. Das würde ja übertragen bedeuten: Erst verkauft P ein Ticket, dann Q. Wo ist dann der Vorteil des 2. Schalters?


----------



## httpdigest (30. Jul 2018)

> zufällig von 2 bis 10 s dauern





> gleichzeitig beginnen





> wobei natürlich die beiden Startwerte unterschiedlich sind





> also bei P beginnt der erste Prozess bei t=0 und bei Q beim Zeitpunkt 2<t<10


Vorher nimmst du eigentlich immer diese wilden Analogien und Annahmen her?
Herrgott, es geht um diesen Programmausschnitt und um nichts anderes. Dass ein möglicher menschlicher Kinobesucher hier erstmal sein Portemonnaie durchsuchen muss oder sonst noch irgendwie mit der Kassiererin ein Pläuderchen abhält ist doch absolut und vollkommen irrelevant... Das ist EIN BEISPIEL!
Außerdem steht doch nirgends geschrieben, welche Prozessschritte nach welcher Interaktion mit dem Benutzer passieren... vielleicht schreibt sich P und Q ja auch erstmal alles auf und kassiert und DANN lassen sie den beschriebenen Algorithmus laufen. Aber das ist alles komplett irrelevant. Es geht um den Algorithmus und um nichts anderes.



> Ansonsten ist natürlich die Frage, wie man das so lösen kann, dass es dennoch funktioniert.


Hier gibt es mehrere Ansätze. In diesem Beispiel würde es ein einfaches Compare-And-Swap (CAS) bzw. Compare-And-Exchange tun.


----------



## Xyz1 (30. Jul 2018)

AndiE hat gesagt.:


> Da ist eben die Frage für mich, wie wahrscheinlich es ist, dass


Diese Informationen haben wir nicht.... Das ist Hardware, System und Software abhängig....
Wir haben nur die Annahme dass jederzeit zwischen den zwei Programmausführungen gewechselt werden kann....



AndiE hat gesagt.:


> Wo ist dann der Vorteil des 2. Schalters?


Es geht nicht um Vor- oder Nachteile....
Es geht einfach um eine von einem gegebene Aufgabe welche bearbeitet werden soll
Es gibt 2 Verkaufsstellen die gleichzeitig auf derselben Ressource lesen und schreiben.... fertig
und das führt zu.... ich weiß nicht wie man es richtig nennt.... "zwei Personen auf einem Platz"

Wie sich diese Personen dann in echt einigen würden ist eine psychologische Fragestellung!!


----------



## Meniskusschaden (30. Jul 2018)

AndiE hat gesagt.:


> Wo ist dann der Vorteil des 2. Schalters?


Wenn der Algorithmus fehlerhaft wäre, bedeutet das ja nicht, dass deswegen die eigentliche Lösungsidee des zweiten Schalters unbrauchbar ist. Man könnte ja auf einen fehlerfreien Algorithmus umstellen.


AndiE hat gesagt.:


> Da ist eben die Frage für mich, wie wahrscheinlich es ist, dass auf die Ressource S beide Prozesse gleichzeitig lesend zugreifen.


Ich stimme dir schon zu, dass das in diesem Szenario eher unwahrscheinlich sein wird, weil das Zeitfenster für einen möglichen Konflikt nur wenige Prozessortakte lang sein dürfte, wogegen die Abwicklung eines Kunden im Verhältnis dazu Ewigkeiten dauert. Aber es könnte ja beispielsweise der Fall eintreten, dass an Schalter P ein Lehrer für seine Schulklasse auf Klassenfahrt 25 Karten auf einmal kauft und gleichzeitig an Schalter Q die Vorsitzende des Landfrauenvereins 25 Karten für den Häkelclub. Dann würden beide Programme die Reservierungsprozedur immerhin 25 Mal in kurzer Abfolge aufrufen. Da könnte die Konfliktwahrscheinlichkeit schon etwas höher sein, falls beide Kassierer gleichzeitig ENTER drücken.
Insgesamt geht es aber vermutlich ohnehin nur darum, solche Parallelisierungprobleme überhaupt zu erkennen. In anderen Szenarien ist das dann eben realistischer.


----------



## Xyz1 (30. Jul 2018)

Meniskusschaden hat gesagt.:


> die Vorsitzende des Landfrauenvereins 25 Karten für den Häkelclub


Wer kauft heute denn 25 Karten auf einmal, dann biste ja gleich 3 Hunnis los....
Dennoch ein schön gewähltes wenn auch antiquiertes Szenario das es tatsächlich so geben könnte...


Meniskusschaden hat gesagt.:


> Wenn der Algorithmus fehlerhaft wäre,


So nochmal um das klarzustellen.... Der Algorithmus funktioniert, er funktioniert aber eben nicht richtig.... (Das wäre auch die Antwort auf die flapsige Frage , Klappt das ? )


Meniskusschaden hat gesagt.:


> Parallelisierungprobleme


Erkennen - und vermeiden/umgehen....


Meniskusschaden hat gesagt.:


> In anderen Szenarien


In anderen Szenarien wird ganz dabei echtes Geld verbrannt....

Eine psychologische Fragestellung könnte erstmal sein, wie sich die Probanden die von der Richtigkeit der Reservierungsprozedur überzeugt sind und dabei von auch gar nichts wissen verhalten *können*. Dann wie sie sich wahrscheinlich verhalten *werden*. Und dann welche Folgen alle das *haben*.
Solche nichtkonfliktfreien Situationen sind nicht absolut weltfremd....


----------

