Erzeuger-Verbraucher-Problem

[syrvn]

Hi,

ich hab folgende zwei Lösungen für das E-V-P gegeben und soll nun

begründen, ob diese korrekt sind oder nicht. Leider blick ich nicht ganz durch...

1 Es gilt: dran = 0; sowie anzahl = 0; Beide Variablen sind vom Typ Integer.


// Erzeuger

while (true)

{

     Element.erzeuge();

     While (dran != 0) do {}

     Element.putonStack();

     Anzahl++;

     Dran = 0;

}



// Verbraucher

while (true)

{

     Element.erzeuge();

     While (dran <= 0) do {}

     Element.getfromStack();

     Anzahl--;

     Dran = 1;

     Verarbeite(element);

}

Was mir hier gleich aufgefallen ist ist, dass der Verbraucher am Anfang ein Element erzeugt. Das kann ja schon einmal nicht stimmen. Ich denke der Rest ist korrekt bis auf die Whiles mit dem dran. Keine Ahnung wie dran gesetzt werden muss, dass das ganze funktioniert. Das versteh ich einfach nicht.

2 Es gilt.. anzahl = 0; lock = false; TestAndSet ist wie in der Vorlesung definiert.


// Erzeuger

While (true)

{

     Element.erzeuge();

     While(anzahl >= N) do{}

     While(TestAndSet(lock)) do {}

     Element.getFromStack();

     Anzahl++;

     lock = false;

}



// Verbraucher

While (true)

{

     While (anzahl <= 0) do{}

     While(TestAndSet(lock)) do {}

     Element.getFromStack();

     Anzahl--;

     lock = false;

     Verarbeite(element);

}

Beim Erzeuger wird Element.getFromStack() aufgerufen das muss wohl Element.putonStack() heissen.

Ansonsten finde ich sieht das auch ganz gut aus, wobei ich wieder Probleme habe zu sagen ob die

jeweiligen ersten While schleifen mit anzahl stimmen.

Kann mir jemand von euch hier weiterhelfen?

Grüße

syrvn

[flashpixx]

Hi,

ich hab folgende zwei Lösungen für das E-V-P gegeben und soll nun

begründen, ob diese korrekt sind oder nicht. Leider blick ich nicht ganz durch...

Tut mir leid, ich aber auch nicht. Du hast zwei Schleifen die beide nicht terminieren, somit befinde ich mich in der ersten, die ich nie verlassen kann, d.h. die zweite wird gar nicht ausgeführt.

Selbst wenn ich hier von Multithreading ausgehe, so dass die Schleifen in zwei unterschiedlichen Threads ausgeführt werden und ich das bei allem guten Willen als Mutex Struktur betrachte, würde das zwar im Ansatz Sinn machen, da der eine Daten erzeugt und der andere Thread sie abarbeitet, hier fehlt dann aber eine entsprechende Synchronisation des Stacks und eine Aussage darüber welche Objekte / Variablen global über die Threads Gültigkeit besitzen. Außerdem ist die Terminierung innerhalb des Threads nicht sichergestellt, d.h. der Thread kann nur "hart" beendet werden

Phil

[syrvn]

Hi flashpixx,

du hast das schon ganz richtig erkannt. Das ganze sollen zwei unterschiedliche Threads sein, die einfach parallel nebeneinander laufen. Das ganze ist darüberhinaus auch nur in einer Art pseudo-sprache (aehnlich java) geschrieben. Auch ist nur das Kernproblem dargestellt: Also der gegenseitige ausschluss. Es geht darum, dass der Erzeuger nur dann ein erzeugtes element auf den Stack legen kann, wenn dieser noch nicht voll ist. Der Verbraucher darf nur dann ein Element verbrauchen, wenn mind. 1 auf dem Stack vorhanden ist. Der Gegenseitige Ausschluss hier ist, dass niemals beide gleichzeitig auf den Stack zugreifen dürfen sondern immer nur einer der beiden. Bei einer Fehlerhaften Implementierung kann es auch passieren, dass beide in der While do {}*schleife hängen bleiben und keiner mehr was macht. Das wäre dann eine sog. Verklemmung, die natuerlich nicht auftreten darf.

Also das Grundprinzip / Problem - wie du aus meiner erläuterung hoffentlich entnehmen konntest - verstehe ich schon aber ich weiss eben nicht ob das ganze verklemmungsfrei abläuft oder ob sonst ein Fehler auftritt...

Add Terminierung: Es ist schon richtig, dass die Threads nie terminieren, aber das ist für das eigentliche Problem nicht wichtig. Die Threads sollen einfach unendlich lange laufen und ihre Arbeit verrichten.

Gruß

Syrvn

Bearbeitet 11. Juli 2009 von syrvn

[flashpixx]

Also das Grundprinzip / Problem - wie du aus meiner erläuterung hoffentlich entnehmen konntest - verstehe ich schon aber ich weiss eben nicht ob das ganze verklemmungsfrei abläuft oder ob sonst ein Fehler auftritt...

schau Dir diese beiden Artikel an

Mutex ? Wikipedia

Deadlock ? Wikipedia

Da diese Codeauszug keine Rückschlüsse über die entsprechenden Strukturen hergibt, welche Variable lokal oder global über die Threads benutzt wird, kann man gar nichts sagen. Meiner Ansicht nach können Probleme auftreten, müssen es aber nicht zwingend. Kläre den Scope Deiner Variablen und der darunterliegenden Stack-Struktur und ob diese synchronisiert ist oder nicht, dann kann man weiter reden, aber so ist das meiner Ansicht nach überhaupt nicht zu gebrauchen

Phil

[syrvn]

Ok, werd mir das morgen mal bei Wikipedia durchlesen.

Muss jetzt leider los!

Das Problem ist halt, dass das mal eine Prüfungsaufgabe war und mehr

als ich oben geschrieben habe steht in der Prüfung auch nicht. Also

sollte es irgendwie vll doch zu lösen sein.

Gut, werd mich Morgen wieder melden.

Schoenen Abend!

Grüße

Syrvn