TUD Logo

TUD Home » ... » Teaching » Operating Systems and Security » Deadlocks

Operating Systems

Exercise: Deadlocks

Verklemmungen

Geplante Bearbeitungszeit: eine Woche

1. Aufgabe:

Gegeben sei das folgende System paralleler Threads; s1 bis s4 bezeichnen dabei binäre Semaphore:\begin_inset Separator latexpar\end_inset
Thread A
while (1) {
        s1.down();
        s2.down();
        work();
        s2.up();
        s1.up();
}
Thread B
while (1) {
        s1.down();
        s3.down();
        work();
        s3.up();
        s1.up();
}
Thread C
while (1) {
        s4.down();
        s1.down();
        work();
        s1.up();
        s4.up();
}
Thread D
while (1) {
        s3.down();
        s4.down();
        work();
        s4.up();
        s3.up();
}
  1. Wie viele der Threads können sich maximal gleichzeitig im Zustand work() befinden?\begin_inset Separator latexpar\end_inset
  2. Was versteht man unter einer Verklemmung (deadlock)? Erläutern Sie mit Bezug auf obiges Beispiel die Bedingungen, die im Zusammenhang mit dem Auftreten von Verklemmungen stehen. Erklären Sie dabei auch den Begriff Betriebsmittel-Zuteilungsgraph (Prozess-Betriebsmittel-Graph).\begin_inset Separator latexpar\end_inset
  3. Ist das System verklemmungsfrei? Verwenden Sie zur Untersuchung der Zyklus-Bedingung einen Betriebsmittel-Zuteilungsgraphen.\begin_inset Separator latexpar\end_inset
  4. Welche Konsequenzen hat jeweils das Vertauschen\begin_inset Separator latexpar\end_inset
    • der beiden down-Operationen in Thread A,
    • der beiden down-Operationen in Thread B,
    • der beiden up-Operationen in Thread B?
  5. Geben Sie einen kurzen Überblick darüber, wie man dem Problem „Verklemmungen“ begegnen kann.

2. Aufgabe:

  1. Beschreiben Sie den Bank-Algorithmus für Betriebsmittel eines Typs. Welche Bedeutung hat in diesem Zusammenhang der Begriff „sicherer Zustand“?
  2. 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.
  3. Erläutern Sie Vor- und Nachteile dieser Vorgehensweise.

3. Aufgabe:

Betrachtet werde ein 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.
  1. Zeigen Sie, dass dieses System verklemmen kann.
  2. Schlagen Sie eine Lösung zur Vermeidung von Verklemmungen vor unter Beibehaltung der gleitenden Grenze zwischen den beiden Puffern.

4. Aufgabe:

Diskutieren Sie den folgenden Algorithmus unter dem Gesichtspunkt „Maßnahmen gegen Verklemmungen“:
  1. Die Menge der Betriebsmittel (BM) wird in m Klassen unterteilt. Jede Klasse besteht aus mindestens soviel BM, dass jeder Prozess einzeln fortschreiten kann.
  2. Die von einem Prozess benötigten BM aus einer Klasse müssen auf einmal zugeteilt werden.
  3. Wenn ein Prozess BM der Klasse i zugeteilt bekommen hat, kann er nur noch BM aus einer höheren Klasse j (j > i) anfordern.
  4. Die BM der höheren Klassen müssen von jedem Prozess vor den BM der niedrigeren Klasse freigegeben werden.
  5. 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.
Last modified: 3rd Dec 2017, 3.46 PM
Author: Dipl.-Inf. Jan Bierbaum

Contact
Sorry — there was an error in gathering the desired information

Regulations
  • ModuleModules: INF-B-380, INF-LE-EUI
  • 4/2/0 = 6 SWS
Time and Place
  • Lecture, weekly
    TimeTue, 9.20 AM PlaceHSZ 0004
  • Lecture, weekly
    TimeFri, 9.20 AM PlaceHSZ 0003
Mailing List