FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Technische Informatik

Frage zu GProt Aufgabe 3

Frage zu GProt Aufgabe 3 2010-07-17 16:23
Anonymer User
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe.
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen.
b) Kann in ihrem Beispiel eine Verklemmung auftreten?
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok?
d) Was sind kritische Abschnitte?
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

Stimmt die überlegung soweit?

a) Schal etc. bedeutet "Schal aus Schrank nehmen"
s = new Semaphore(); Kind 1                Kind 2                Kind 3 s.P()                 s.P()                 s.P() Schal                 Handschuhe            Schal             Handschuhe            Mütze                 Mütze s.V()                 s.V()                 s.V()
b) In jedem Fall sind nachdem 1 Kind dran war, die beiden anderen verklemmt.
c) Es tritt immernoch eine Verklemmung auf.
d) Das herausnehmen der jeweils Fehlenden Utensilien aus dem Schrank.

Oder war die Frage so gemeint, dass die Semaphore auf das Rausgehen und wieder hereinkommen angewandt werden soll?

RE: Frage zu GProt Aufgabe 3 2010-07-17 17:21
Anonymer User
Intuitiv hätte ich die drei Prozesse genauso modeliert, aber die übrigen Frage finde ich merkwürdig.

Unter einer Verklemmung verstehe ich einen Deadlock, soetwas tritt auf, wenn nach einer Handlung keine weiteren mehr möglich sind. Das sehe ich hier nicht gegeben. Es kann immer nur ein Kind die volle Montur haben und draußen spielen, sobald es aber wieder reinkommt kann eines der anderen Kinder drankommen und kann nach hause gehen, die übrigen schlafen.

In dieser Implementierung kann es mMn keine Verklemmungen geben. Die Frage ist vllcht, ob man in einem Zug mehrere Betriebsmittel erlangen darf. Eine Verklemmung kann nur vorkommen, wenn alle drei Kinder auf etwas warten, was ein jeweils anderes besetzt hat und nicht wieder hergibt.

RE: Frage zu GProt Aufgabe 3 2010-07-17 17:22
Anonymer User
und kann nach hause gehen

kann nach draußen gehen meinte ich natürlich.

Ist es sicher, dass der Aufgabentext korrekt ist?

RE: Frage zu GProt Aufgabe 3 2010-07-18 01:02
Anonymer User
Also ich sehe da eine Verklemmung.  Kind 1 nehme sich Mütze und Schal,  Kind 2 Schal und Handschuhe, Kind 3 Handschuhe und Mütze.   So sind alle Ressourcen vergeben, Kind 1 bräuchte Handschuhe von Kind 2 oder Kind 3, Kind 2 bräuchte Mütze von Kind1 oder Kind 3, und Kind 3 bräuchte Schal von Kind1 oder Kind 2.

Weil Kinder aber zu egoistisch sind hat jeder nur 2 teile und keiner kann raus. Weil zum rausgehen brauch man alle 3

In der nächsten Aufgabe: Stirbt also Kind 1 aus Egoismus, bleiben ne Mütze und nen Schal über, genau das was Kind 2 und Kind 3 brauchen.

RE: Frage zu GProt Aufgabe 3 2010-07-18 10:59
Anonymer User
Also ich sehe da eine Verklemmung.  Kind 1 nehme sich Mütze und Schal,  Kind 2 Schal und Handschuhe, Kind 3 Handschuhe und Mütze.   So sind alle Ressourcen vergeben, Kind 1 bräuchte Handschuhe von Kind 2 oder Kind 3, Kind 2 bräuchte Mütze von Kind1 oder Kind 3, und Kind 3 bräuchte Schal von Kind1 oder Kind 2.

Weil Kinder aber zu egoistisch sind hat jeder nur 2 teile und keiner kann raus. Weil zum rausgehen brauch man alle 3

In der nächsten Aufgabe: Stirbt also Kind 1 aus Egoismus, bleiben ne Mütze und nen Schal über, genau das was Kind 2 und Kind 3 brauchen.

Das macht doch keinen Sinn? Warum soll der Prozess Kind1 sich Sachen nehmen, die er nicht braucht? Ist doch auch nicht so implementiert, deswegen wird er das auch nicht tun. Das ist kein Argument für ein Deadlock. (Außerdem kann das Szenario garnicht erst eintreten, da es nur drei Ressourcen gibt, sodass jedes Kind keine zwei (falschen) haben kann)

Die einzige Verklemmung, die ich mir Vorstellen könnte wäre:

Ein Prozess, sagen wir Kind1, nimmt sich seine Sachen und geht raus. D.h. es war im kritischen Bereich, hat das getan, was es wollte und hat den kritischen Bereich wieder verlassen. Das ist nun ein Signal für die übrigen Prozesse, dass sie auch wieder in den kritischen Bereich dürfen.

Geht z.b. Kind 2 jetzt da rein, schnappt sich was da ist (die Mütze) und stellt fest, dass keine Hanschuhe da sind. Wenn das Kind jetzt die Mütze nimmt und ewig im Kritischen Bereich sitzt um auf Handschuhe zu warten (und nicht etwa die Mützen Ressource wieder freigibt und sich aus dem kritischen Bereich begibt) gibt es einen Deadlock.

Die übrigen Aufgaben machen also erst Sinn, wenn man die erste so betrachtet und diese Annahme gleich dazustellt.

Verhindert ist der Deadlock, wenn das entsprerren des Semaphors erst stattfindet, wenn das Kind wieder drin ist und die Sachen zurückgelegt hat. Oder wenn die Prozesse nicht im kritischen Bereich auf Ressourcen warten, da es ganz klar ist, dass sie dort keine kriegen werden.

Also imo schwammige Aufgabe.

RE: Frage zu GProt Aufgabe 3 2010-07-18 11:10
Anonymer User
Also meiner Meinung nach gibt es 6 Ressourcen.

Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. Das sind die ersten drei


In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. und das die nächsten 3

RE: Frage zu GProt Aufgabe 3 2010-07-18 11:12
Anonymer User
Achja und Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten.  Also rausgehen ist nur mit allen 3 Ressourcen sonst nicht.

RE: Frage zu GProt Aufgabe 3 2010-07-18 11:30
Anonymer User
Also meiner Meinung nach gibt es 6 Ressourcen.

Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. Das sind die ersten drei


In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe.  und das die nächsten 3

Ja ok, aber drei der Ressourcen besitzen die Prozesse bereits, sodass sie nicht in den Pool für freie BM geworfen werden. Ich dachte du meinst, dass sie sich neben ihrer eigenen noch zwei holen.

Nach der Implementierung oben ist das Szenario immer noch nicht möglich. Ein Kind nimmt sich gleich zwei der Ressourcen, nicht nur eine. Es können also nicht alle Kinder zwei Ressourcen haben und immer eines hat drei.

Wie oben geschrieben wurde - wenn ein Prozess immer nur eine Ressource nehmen darf - man bei der Implementierung also nicht einfach sagen kann, Kind x nimmt sich gleich seine zwei fehlenden Sachen - würde das Szenario greifen.

RE: Frage zu GProt Aufgabe 3 2010-07-18 11:33
Wulf
Kind1 geht an Schrank, holt sich Schal und Handschuhe und geht raus.
Kind2 geht auch zum Schrank, holt sich die Mütze, klaut Kind3 die Handschuhe und geht auch raus.
Kind3 geht an Rechner und zockt ne Runde WoW.
Keine Verklemmung.

Sind aber alle Kinder sowohl egoistisch als auch fair, bekommt jeder ein Teil aus dem Schrank, alle gehen raus und spielen lieb miteinander. Es kriegt dann je einer kalte Hände, einen kalten Kopf oder einen kalten Hals, alle erkälten sich und sind unglücklich. Auch hier ist keine Verklemmung.

Und die Moral von der Geschicht': kauft euren Kindern genug Kleidung!

RE: Frage zu GProt Aufgabe 3 2010-07-18 12:00
tein
Soll diese Aufgabe nicht einfach das Philosophenproblem mit n=3 darstellen?

RE: Frage zu GProt Aufgabe 3 2010-07-18 12:24
Anonymer User
Soll diese Aufgabe nicht einfach das Philosophenproblem mit n=3 darstellen?

Ja aber das löst nicht das Problem der schwammigen Aufgabe. Es gibt ja Implementationen, die das Problem erfolgreich lösen. Z.b. wenn der Philosoph seine linke Gabel genommen hat, die rechte aber nicht frei ist, wartet er eine zufällige Zeit und legt seine Gabel wieder hin.

D.h. ich kann für a) eine korrekte Implementation angeben. Dann sag ich bei b) nö und bei c) funktioniert immernoch supertoll?

Eine weitere Frage ist - streicht man ein Kind, gelangt seine Ressource in den Pool für freie Ressourcen oder ist sie weg?

RE: Frage zu GProt Aufgabe 3 2010-07-18 12:35
tein
Soll diese Aufgabe nicht einfach das Philosophenproblem mit n=3 darstellen?

Ja aber das löst nicht das Problem der schwammigen Aufgabe.
Das ist sicher richtig, es fehlen Informationen. Abgesehen davon, dass Kinder in der Regel zusammen, also gleichzeitig im Schnee spielen wollen und nicht nacheinander.

RE: Frage zu GProt Aufgabe 3 2010-07-18 13:59
RaG
Wieso modelliert ihr das mit einer einzigen Semaphore? Für was soll die stehen?

Wir haben drei verschiedene unzugeordnete Betriebsmittel: Schal, Mütze und Handschuhe, von denen jeweils eins. Um zu gewährleisten, dass ein Betriebsmittel jeweils von nur einem Prozess/Kind zur Zeit genutzt wird, müssen wir jedem einen eigenen Semaphor zuordnen (wenns gleichartige BM wären, könnte man auch einen zählenden Semaphor einsetzen):

schal = new Semaphore(); muetze = new Semaphore(); handschuhe = new Semaphore(); Kind 1                     Kind 2                           Kind 3 schal.P();                 handschuhe.P();                  schal.P(); handschuhe.P();            muetze.P();                      muetze.P();             spielen();                 spielen();                       spielen(); schal.V();                 handschuhe.V();                  schal.V(); handschuhe.V();            muetze.V();                      muetze.V();
Allerdings kann diese Implementation soweit ich das sehe auch nicht zu Verklemmungen führen… Anders die hier (bei Kind 3 die Reihenfolge vertauscht):


schal = new Semaphore(); muetze = new Semaphore(); handschuhe = new Semaphore(); Kind 1                     Kind 2                           Kind 3 schal.P();                 handschuhe.P();                  muetze.P(); handschuhe.P();            muetze.P();                      schal.P();             spielen();                 spielen();                       spielen(); schal.V();                 handschuhe.V();                  schal.V(); handschuhe.V();            muetze.V();                      muetze.V();
Wenn hier alle drei Kinder jeweils die erste Aktion ausführen, blockieren danach alle durch das nächste P() und können auch nie aufgeweckt werden, da kein Prozess je V() ausführen kann, um seine Betriebsmittel wieder frei zu geben.

RE: Frage zu GProt Aufgabe 3 2010-07-18 14:23
Anonymer User
Wieso modelliert ihr das mit einer einzigen Semaphore? Für was soll die stehen?

Wieso soll das nicht gehen? Sie steht dafür, dass ein Prozess in seinem kritischen Bereich ist. Wenn ein Prozess in seinem kritischen Bereich ist, darf kein  anderer seinen kritischen Bereich betreten.

Wenn alle das Semaphor prüfen bevor sie in ihren k. Bereich gehen, ist die Aufgabe doch gelöst.

Ich meine so wurde das auch im Tanenbaum behandelt. Von einem kritischen Bereich pro Betriebsmittel habe ich noch nichts gehört. Wozu auch?

RE: Frage zu GProt Aufgabe 3 2010-07-18 14:30
Wulf
Es ist egal, ob man ein, zwei, drei oder hundert Semaphore benutzt! Solange nicht ein Kind sein Kleidungsstück verleiht (oder es von einem anderen Kind geraubt wird) müssen immer zwei Kinder drinnen warten. Wie gesagt: Kauft euren Kindern genug Kleidung! Dann kann man sich solche Aufgaben sparen.

RE: Frage zu GProt Aufgabe 3 2010-07-18 14:31
RaG
Bei der Modellierung ist also der kritische Bereich alles? Dann kann aber immer nur ein Kind zur Zeit nach draußen gehen, obwohl es für zwei möglich wäre. D.h. man hat überhaupt keine Nebenläufigkeit mehr und kann sich die drei Prozesse/Threads auch sparen und nur einen nutzen.

Edit: Oops, hast recht, Wulf. Es kann eh immer nur ein Kind nach draußen gehen. Komische Aufgabenstellung…

RE: Frage zu GProt Aufgabe 3 2010-07-18 14:33
Anonymer User
Das liegt glaube ich im Ermessen des Programmierers/Modellierers.
Deine Implementierung finde ich auch nicht optimal, da sind ja immer kritische Abschnitte innerhalb anderer kritischer Abschnitte. Das hat doch keinen Sinn?!

RE: Frage zu GProt Aufgabe 3 2010-07-18 14:33
Anonymer User
Es ist egal, ob man ein, zwei, drei oder hundert Semaphore benutzt! Solange nicht ein Kind sein Kleidungsstück verleiht (oder es von einem anderen Kind geraubt wird) müssen immer zwei Kinder drinnen warten. Wie gesagt: Kauft euren Kindern genug Kleidung! Dann kann man sich solche Aufgaben sparen.

Es ist nicht gesagt, wieviele Kinder draußen spielen können müssen, um ein zufriedenstellendes Resultat zu erhalten/die Aufgabe korrekt gelöst zu haben. D.h. es ist egal, dass zwei Kinder warten müssen - solange nicht irgendwann alle drei ewig warten müssen kann von keiner Verklemmung die Rede sein.

Hinzuschreiben, dass die Eltern mehr Kleidung kaufen sollen wird wahrscheinlich nicht die volle Punktezahl bringen.