Pseudocode Kinokarten Verkauf

S

Sonnenblume123

Aktives Mitglied
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?
 
X

Xyz1

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

Die willst du doch nicht alle auflisten? :rolleyes:
 
H

httpdigest

Top Contributor
Sonnenblume123 hat gesagt.:
Nun soll ja beantwortet werden, ob es klappt oder nicht.
Meine Antwort: nein.
Zum Vergrößern anklicken....
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.
 
X

Xyz1

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

httpdigest

Top Contributor
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
 
X

Xyz1

Gast
Ich bin einfach mal mit Monte-Carlo darauf losgegangen, unter der Annahme dass die Wahrscheinlichkeiten unabhängig von n sind, hier mit n = 2.
Java: 
if (p1 < q1) {
    if (p5 < q1) {
        notLocks++;
    } else {
        locks++;
    }
} else {
    if (q5 < p1) {
        notLocks++;
    } else {
        locks++;
    }
}
 
X

Xyz1

Gast
DerWissende hat gesagt.:
Es gibt mindestens 479001600 mögliche Ausführungssequenzen ....
Zum Vergrößern anklicken....
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
Code: 
          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
 
A

AndiE

Top Contributor
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.
 
H

httpdigest

Top Contributor
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.
 
A

AndiE

Top Contributor
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?
 
H

httpdigest

Top Contributor
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.
 
A

AndiE

Top Contributor
@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?
 
H

httpdigest

Top Contributor
zufällig von 2 bis 10 s dauern
Zum Vergrößern anklicken....
gleichzeitig beginnen
Zum Vergrößern anklicken....
wobei natürlich die beiden Startwerte unterschiedlich sind
Zum Vergrößern anklicken....
also bei P beginnt der erste Prozess bei t=0 und bei Q beim Zeitpunkt 2<t<10
Zum Vergrößern anklicken....
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.
Zum Vergrößern anklicken....
Hier gibt es mehrere Ansätze. In diesem Beispiel würde es ein einfaches Compare-And-Swap (CAS) bzw. Compare-And-Exchange tun.
 
X

Xyz1

Gast
AndiE hat gesagt.:
Da ist eben die Frage für mich, wie wahrscheinlich es ist, dass
Zum Vergrößern anklicken....
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?
Zum Vergrößern anklicken....
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!!
 
M

Meniskusschaden

Top Contributor
AndiE hat gesagt.:
Wo ist dann der Vorteil des 2. Schalters?
Zum Vergrößern anklicken....
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.
Zum Vergrößern anklicken....
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.
 
X

Xyz1

Gast
Meniskusschaden hat gesagt.:
die Vorsitzende des Landfrauenvereins 25 Karten für den Häkelclub
Zum Vergrößern anklicken....
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,
Zum Vergrößern anklicken....
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
Zum Vergrößern anklicken....
Erkennen - und vermeiden/umgehen....
Meniskusschaden hat gesagt.:
In anderen Szenarien
Zum Vergrößern anklicken....
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....
 

Aktuelle Jobs

Neue Themen


Oben