Übungsblatt 11 Aufgabe 2b)

Re: Übungsblatt 11 Aufgabe 2b)

Reitanna — Wed, 01 Feb 2006 20:07:29 +0100

vielen dank :) alles klar

Re: Übungsblatt 11 Aufgabe 3

Stefan Disch — Wed, 01 Feb 2006 19:25:55 +0100

Wir machen eine Annahme:
Shortest Job First ist immer optimal, auch wenn nicht alle Prozesse gleichzeitig
verfügbar sind.

Jetzt ein Gegenbeispiel:
Es wird nach einer konkreten Menge von Prozessen mit konkreten Lauf- und
Ankunftszeiten gefragt.

Für dieses Beispiel muss folgendes gelten:

* Es gibt einen Schedule, so dass die mittlere Durchlaufzeit geringer ist, wie
bei dem Schedule durch Shortest Job First. Da muss man beide angeben und die
mittlere Durchlaufzeit ausrechnen.

* Die Prozesse sind nicht alle gleichzeitig verfügbar.

Wenn man so ein Beispiel gefunden hat, widerlegt dieses obige Annahme.
Dann hat man gezeigt, dass Shortest Job First _nicht_ optimal ist, wenn
nicht alle Prozesse gleichzeitig verfügbar sind.

Jetzt müsste man noch zeigen, dass Shortest Job First optimal ist, _wenn_ alle
Prozesse gleichzeitig verfügbar sind. Dies wurde aber schon in der Vorlesung gezeigt.

Wenn man also eine Behauptung mit einem Beispiel widerlegen kann, ist dies ein
Gegenbeispiel und gleichzeitig ein mathematischer Beweis, weil völlig klar ist,
dass die Behauptung falsch sein muss.

Hoffe geholfen zu haben

Stefan

Re: Übungsblatt 11 Aufgabe 3

Reitanna — Wed, 01 Feb 2006 19:02:05 +0100

>>>Ein Gegenbeispiel ist ein mathematischer Beweis!<<<

Also, es muss mit Hilfe von formalen Bezeichnungen wie t oder d gemacht werden?
aber, ich kann ja nicht wissen, ob der nächste Prozess nach der Ausführung von z.B. P0 kommt oder später ---> das kann man doch nicht in einer Formel definieren...

MfG,

Reitanna

Re: Übungsblatt 11 Aufgabe 2b)

Stefan Disch — Wed, 01 Feb 2006 17:10:55 +0100

JB Wrote:
-------------------------------------------------------
> Ich verstehs nicht so ganz, danke aber
> aufjedenfall für die Antwort...
>
> Ja ich meinte mit Zustand 1 = Zeile 1 etc.
>
> Wenn P1 Zeile 1 Ausgeführt hat, dann kann P1
> aufjedenfall gleich terminiert werden.

ARGH, Du hast natürlich recht. Da ist uns ein Fehler bei der
Aufgabenstellung passiert. *kopfaufdentischhämmer*
Ich werde hierzu gleich nochmal ein Posting ins Forum stellen.

> Damit ergibt sich kein Problem für P0 und dessen
> Maximalanforderungen, denn es gilt auf jedenfall
> (nach den Folien) M_0 <= V;
>
> Naja vielleicht fällt es mir noch auf...
>
> Achja, müssen wir bei Aufgabe 3 einen
> mathematischen Beweis bringen oder nur ein
> Gegenbeispiel mit konkreten Zahlen etc.?

Ein Gegenbeispiel ist ein mathematischer Beweis!

Grüße und Danke
Stefan

Re: Übungsblatt 11 Aufgabe 2b)

JB — Wed, 01 Feb 2006 15:11:13 +0100

Ich verstehs nicht so ganz, danke aber aufjedenfall für die Antwort...

Ja ich meinte mit Zustand 1 = Zeile 1 etc.

Wenn P1 Zeile 1 Ausgeführt hat, dann kann P1 aufjedenfall gleich terminiert werden.
Damit ergibt sich kein Problem für P0 und dessen Maximalanforderungen, denn es gilt auf jedenfall (nach den Folien) M_0 <= V;

Naja vielleicht fällt es mir noch auf...

Achja, müssen wir bei Aufgabe 3 einen mathematischen Beweis bringen oder nur ein Gegenbeispiel mit konkreten Zahlen etc.?

MfG Asgaroth

Re: Übungsblatt 11 Aufgabe 2b)

Stefan Disch — Wed, 01 Feb 2006 14:56:16 +0100

Hallo,

JB Wrote:
-------------------------------------------------------
> Hab mal ne Frage zu Aufgabe 2b,
>
> Nehmen wir an P0 wurde bis zum Zustand 2
> ausgeführt und P1 bis Zustand 2, dann ist der
> Zustand doch nicht unsicher weil auf jedenfall
> alles freigegeben wird oder?!?

Ich nehme an Du meinst mit Zustand 2 die Zeile 2.

Nein, wenn P0 zuerst Zeile 2 ausführt und dann P1 Zeile 2, wird
nicht alles freigegeben.

>
> Ansonsten, kann es sein, dass sich P0 auch schon
> bei einem Zustand >= 3 befindet und dann erst
> P1 bis Zustand 2 ausgeführt wird? (Oder impliziert
> die Formulierung aus der Aufgabe das sich einfach
> beide Prozesse bei Zustand 2 befinden? Hab das
> irgendwie nicht so ganz verstanden bzw macht
> irgendwie gerade keinen Sinn...)
>
> MfG J.B.

Wir betrachten folgenden Zustand:
P0 hat Zeile 1 ausgeführt und P1 hat Zeile 2 ausgeführt. (reale Ausführung)
Es ist offensichtlich, dass P0 nun seine Ressource erst wieder freigibt,
bevor er wieder eine anfordert.

Warum betrachtet aber der Bankieralgorithmus diesen Zustand als unsicher?
Hinweise: * Welche Werte wurden bei a) ermittelt?
* Wie wird berechnet, ob ein Zustand unsicher ist?

Hoffe geholfen zu haben

Stefan

Übungsblatt 11 Aufgabe 2b)

JB — Wed, 01 Feb 2006 14:34:39 +0100

Hab mal ne Frage zu Aufgabe 2b,

Nehmen wir an P0 wurde bis zum Zustand 2 ausgeführt und P1 bis Zustand 2, dann ist der Zustand doch nicht unsicher weil auf jedenfall alles freigegeben wird oder?!?

Ansonsten, kann es sein, dass sich P0 auch schon bei einem Zustand >= 3 befindet und dann erst P1 bis Zustand 2 ausgeführt wird? (Oder impliziert die Formulierung aus der Aufgabe das sich einfach beide Prozesse bei Zustand 2 befinden? Hab das irgendwie nicht so ganz verstanden bzw macht irgendwie gerade keinen Sinn...)

MfG J.B.