Verklemmungen
Geplante Bearbeitungszeit: eine Woche
1. Aufgabe:
Gegeben sei das folgende System paralleler Prozesse (bzw. von
Threads innerhalb eines Prozesses); s1 bis s4
bezeichnen dabei binäre Semaphore:
| Prozess
A |
Prozess
B |
Prozess
C |
Prozess
D |
while (1) {
s1.P();
s2.P();
work();
s2.V();
s1.V();
}
|
while (1) {
s1.P();
s3.P();
work();
s3.V();
s1.V();
}
|
while (1) {
s4.P();
s1.P();
work();
s1.V();
s4.V();
}
|
while (1) {
s3.P();
s4.P();
work();
s4.V();
s3.V();
}
|
- Welches ist die Maximalzahl von Prozessen, die sich
gleichzeitig im Zustand work()
befinden können?
- Was versteht man unter einem Deadlock? Erläutern Sie mit
Bezug auf obiges Beispiel die Bedingungen, die im Zusammenhang
mit dem Auftreten von Deadlocks
stehen. Erklären Sie dabei auch
den Begriff Prozess-Betriebsmittel-Graph
(BM-Zuteilungsgraph).
- Ist das System verklemmungsfrei? Verwenden Sie zur
Untersuchung der Zyklus-Bedingung einen
Prozess-Betriebsmittel-Graphen.
- Welche Konsequenzen hat das Vertauschen
- der beiden P-Operationen in Prozess A,
- der beiden P-Operationen in Prozess B,
- der beiden V-Operationen in Prozess B?
- Geben Sie einen kurzen Überblick darüber, wie man dem
Problem „Verklemmungen“ begegnen kann.
2. Aufgabe:
Für n Prozesse stehen
m gleichartige Exemplare
eines Betriebsmittels zur Verfügung, die jeweils nur einzeln
reserviert bzw. freigegeben werden können, dabei benötigt jeder
Prozess maximal k Exemplare
gleichzeitig. Wie viele Betriebsmittel-Exemplare müssen
mindestens vorhanden sein, damit keine Verklemmungen auftreten
können?
Hinweis: Untersuchen Sie zunächst die beiden Fälle n = 3, k = 2, m1 = 3, m2 = 4.
3. Aufgabe:
- Beschreiben Sie den Bank-Algorithmus für Betriebsmittel
eines Typs. Welche Bedeutung hat in diesem Zusammenhang der
Begriff „sicherer Zustand“?
- Betrachten Sie den Bank-Algorithmus in dem folgenden Fall:
Vier Prozesse A,…,D bewerben sich um acht Exemplare eines
Betriebsmittels. Der Vektor der maximal benötigten
Betriebsmittel sei (6 3 8 4) T, der aktuelle Zustand sei
(1 2 2 1) T. Untersuchen Sie, inwieweit –
jeweils von diesem Zustand ausgehend – die Forderung nach einem
Betriebsmittel-Exemplar durch den Prozess A bzw. durch den
Prozess C erfüllt werden kann. Diskutieren Sie die Gültigkeit
der Aussage: „Der Nachfolgezustand eines sicheren Zustands ist
sicher“ und ihrer Umkehrung.
- Erläutern Sie Vor- und Nachteile dieser
Vorgehensweise.
4. Aufgabe:
Betrachtet werde ein sogenanntes SPOOL-System mit einem
Eingabeprozess, einem Verarbeitungsprozess und einem
Ausgabeprozess, die durch zwei Puffer miteinander verbunden
sind. Die Prozesse transferieren Daten in Einheiten gleicher
Größe. Dabei entnimmt der Verarbeitungsprozess eine Seite aus
dem Puffer (gibt diesen Bereich danach frei), speichert den
Seiteninhalt in einem lokalen Puffer und füllt dann den
Ausgabepuffer. Die Grenze zwischen Eingabepuffer und
Ausgabepuffer ist gleitend in Abhängigkeit von der
Geschwindigkeit der Prozesse, einzige Beschränkung ist die
Gesamtkapazität des Speichers, in dem die Puffer angelegt sind.
Jeder der drei Prozesse arbeitet, solange Eingabedaten für ihn
vorhanden sind und Speicherplatz in dem Puffer, den er
benötigt, zur Verfügung steht; andernfalls wartet er.
- Zeigen Sie, dass dieses System verklemmen kann.
- Schlagen Sie eine Lösung zur Vermeidung von Verklemmungen
vor unter Beibehaltung der gleitenden Grenze zwischen den
beiden Puffern.
5. Aufgabe:
Diskutieren Sie den folgenden Algorithmus unter dem
Gesichtspunkt „Maßnahmen gegen Verklemmungen“:
- Die Menge der Betriebsmittel (BM) wird in m Klassen unterteilt. Jede Klasse
besteht aus mindestens soviel BM, dass jeder Prozess einzeln
fortschreiten kann.
- Die von einem Prozess benötigten BM aus einer Klasse müssen
auf einmal zugeteilt werden.
- Wenn ein Prozess BM der Klasse i zugeteilt bekommen hat, kann er nur
noch BM aus einer höheren Klasse j (j > i) anfordern.
- Die BM der höheren Klassen müssen von jedem Prozess vor den
BM der niedrigeren Klasse freigegeben werden.
- Erst wenn ein Prozess alle BM, die er aus einer gegebenen
Klasse erhalten hatte, wieder freigegeben hat, kann er neue BM
aus dieser Klasse anfordern.
e-mail contact form
