TUD Logo

TUD Startseite » ... » Lehre » Betriebssysteme und Sicherheit » Verklemmungen

Betriebssysteme

Übung: Verklemmungen

Verklemmungen

Geplante Bearbeitungszeit: eine Woche

1. Aufgabe:

Gegeben sei das folgende System paralleler Threads; s1 bis s4 bezeichnen dabei binäre Semaphore:
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?
  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).
  3. Ist das System verklemmungsfrei? Verwenden Sie zur Untersuchung der Zyklus-Bedingung einen Betriebsmittel-Zuteilungsgraphen.
  4. Welche Konsequenzen hat jeweils das Vertauschen
    • 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.
Stand: 15.11.2018, 20:30 Uhr
Autor: Jan Bierbaum

Kontakt
Bitte entschuldigen Sie – beim Einbinden der Informationen ist ein Fehler aufgetreten

Regelungen
  • ModuleModule: INF-B-380, INF-LE-EUI
  • 4/2/0 = 6 SWS
Zeit und Ort
  • Vorlesung, wöchentlich
    TimeDi, 9:20 Uhr PlaceHSZ 0004
  • Vorlesung, wöchentlich
    TimeFr, 9:20 Uhr PlaceHSZ 0003
Mailingliste