asf

AALBERT-LUDWIGS-
UNIVERSITÄT FREIBURG
INSTITUT FÜR INFORMATIK
Prof. Dr. Christoph Scholl
Freiburg, 22. Januar 2009
Dipl. Inf. Stefan Disch
Systeme I
Übungsblatt 11 - Theorie
Aufgabe 1 (2+1+1+1 Punkte)
Zwei Prozesse wollen auf vier Ressourcen A, B, C, D und zugreifen. Folgende Tabelle zeigt, in
welcher Reihenfolge die Prozesse Ressourcen anfragen bzw. freigeben; Befehle, die zwischen den
Anforderungen und Freigaben stehen, vernachlässigen wir hier.
/* Prozess 0 */
/* Prozess 1 */
1: Anforderung A
1: Anforderung C
2: Anforderung D
2: Anforderung B
3: Anforderung B
3: Anforderung A
4: Anforderung C
4: Freigabe A
5: Freigabe B
5: Freigabe B
6: Freigabe C
6: Anforderung B
7: Anforderung B
7: Anforderung D
8: Freigabe A
8: Freigabe D
9: Freigabe B
9: Freigabe C
10: Freigabe D
10: Freigabe B
a) Zeichnen Sie in untenstehende Grafik die Bereiche ein, in der beide Prozesse auf eine Res-
source zugreifen würden. Die horizontale Achse repräsentiert den Programmfortschritt von
Prozess 0 und die vertikale Achse repräsentiert den Programmfortschritt von Prozess 1. Die
mit einer Nummer versehenen horizontalen und vertikalen Linien sind die Zeitpunkte in
der Programmausführung, an der die entsprechend numerierte Zeile des Prozesses ausge-
führt wird.
b) Markieren Sie die Deadlocks und die Bereiche, in dem ein Deadlock unvermeindlich ist.
c) Geben Sie für einen der Deadlocks eine Abarbeitungsfolge der beiden Prozesse an, die in
diesen Deadlock führt.
d) Beweisen Sie Ihre Aussage, indem Sie den Belegungs-Anforderungs-Graphen nach Ausfüh-
ren Ihrer Abarbeitungsfolge aus c) angeben und den Teil des Graphen markieren, der zeigt,
daß ein Deadlock vorliegt.

---

Prozess 1
10
9
8
7
6
5
4
3
2
1
Prozess 0
1
2
3
4
5
6
7
8
9
10
Abbildung 1: Zeichnen Sie hier Ihre Lösung ein.
Aufgabe 2 (1+1+1 Punkte)
Bankieralgorithmus:
Zwei Prozesse P0 und P1 wollen auf eine Ressourcenklasse A zugreifen. Folgende Tabelle zeigt, in
welcher Reihenfolge die Prozesse Ressourcen anfragen bzw. freigeben. Die Anzahl der zur Verfü-
gung stehenden Ressourcen V sei 2. Die Variable x wird von den Prozessen gemeinsam genutzt.
/* P0 */
/* P1 */
1: x = -1;
1: Anforderung A;
2: Anforderung A;
2: x = 5;
3: if (x >= 0) { Freigabe A; }
3: Anforderung A;
4: Anforderung A;
4: Freigabe A;
5: Freigabe A;
5: Freigabe A;
6: if (x < 0) { Freigabe A; }
a) Bestimmen Sie für jeden Prozess die maximale Anzahl Mi von Ressourcen. Sind die Vorraus-
setzungen für den Bankieralgorithmus erfüllt? Begründen Sie kurz Ihre Aussage.
b) Sei die Ausführung jeder Zeile eine atomare Operation. Betrachten Sie folgenden Zustand:
P 0 führt zuerst Zeile 1 und 2 aus, danach führt P 1 die Zeilen 1 und 2 aus.
Warum ist dieser Zustand bezüglich des Bankieralgorithmus unsicher?
2

---

c) Gibt es ausgehend von dem in Teil b) angegebenen unsicheren Zustand eine Abarbeitungs-
reihenfolge der Prozesse, die zu einem Deadlock führt?
Aufgabe 3 (4 Punkte)
In der Vorlesung wurde erwähnt, daß die Scheduling-Strategie „Shortest job first“ nur dann opti-
mal (im Sinne von minimaler mittlerer Durchlaufzeit) ist, wenn alle Prozesse gleichzeitig verfüg-
bar sind.
Beweisen Sie diese Aussage, indem Sie eine Menge von Prozessen samt Lauf- und Ankunftszeiten
angeben, für die ein (nicht-präemptiver) Schedule existiert, dessen mittlere Durchlaufzeit gerin-
ger ist als die mittlere Durchlaufzeit des mittels „Shortest job first“ erzeugten Schedules. (Die
Ankunftzeit ist der Zeitpunkt, ab dem ein Prozeß verfügbar ist.)
Abgabe: bis Mittwoch 28.01.2009, 23:00 Uhr im Übungsportal
3

---