« »

GRABS Übungsaufgaben Ressourcen und Nebenläufigkeit Deadlocks

Deadlocks

Betrachten Sie folgende parallele Threads t1 und t2:

int t1() {
	z = z + 2;
	sem1.wait();
	x = x + 2;
	sem2.wait();
	sem1.signal();
	y = y + 2;
	sem2.signal();
}
int t2() {
	sem2.wait();
	y = y + 1;
	sem1.wait();
	x = x + 1;
	sem1.signal();
	sem2.signal();
	z = z + 1;
}

Sie verwenden diese geteilten Variablen:

int x = 0, y = 0, z = 0;
sem_t sem1 = 1, sem2 = 1;

a)

Level 1: Wissen

Beide Threads parallel auszuführen kann zu einem Deadlock führen. Warum?

Hinweis

Bedenken Sie, dass eine Zuweisung z = z + 1; aus mehreren atomaren Operationen besteht.

Lösung
  • t1 läuft bis Zeile 4 (sem1=0, sem2=1)
  • t2 läuft bis Zeile 3 (sem1=0, sem2=0)
  • t1 wartet auf sem2 in Zeile 5
  • t2 wartet auf sem1 in Zeile 4

Alternative:

  • t2 läuft bis Zeile 2 (sem1=1, sem2=0)
  • t1 läuft bis Zeile 3 (sem1=0, sem2=0)
  • t2 wartet auf sem1 in Zeile 4
  • t1 wartet auf sem2 in Zeile 5

b)

Level 1: Wissen

Was sind die möglichen Werte von x, y und z im Fall eines Deadlocks?

Lösung

x = 2, y = 1, z = 2

c)

Level 1: Wissen

Was sind die möglichen Werte von x, y und z, wenn das Programm erfolgreich terminiert, also kein Deadlock auftritt?

Lösung
  • t1 oder t2 läuft zuerst bis zum Ende, dann der jeweils andere Thread
    • somit möglich: x = 3, y = 3, z = 3
  • ebenfalls möglich:
    • Kontextumschaltung inmitten der Zeile 8 von t2
    • somit möglich: x = 3, y = 3, z = 1
  • ebenfalls möglich:
    • t2 läuft bis zu Teil 1 von Zeile 8 (Auslesen des alten Werts von z)
    • t1 läuft bis zu Teil 1 von Zeile 2 (Auslesen des alten Werts von z)
    • t2 schreibt z=0+1 und läuft bis zum Ende
    • t1 schreibt z=0+2 und läuft bis zum Ende
    • somit möglich: x = 3, y = 3, z = 2

d)

Level 3: Anwenden

Gegeben sind die folgenden drei Threads.

Thread 1:

wait(a);
wait(b);
// kritischer Abschnitt
signal(a);
signal(b);

Thread 2:

wait(a);
wait(c);
// kritischer Abschnitt
signal(c);
signal(a);

Thread 3:

wait(b);
wait(c);
// kritischer Abschnitt
signal(b);
signal(c);

Können sich die Threads verklemmen? Falls eine Verklemmung auftreten kann, welche Reihenfolge der Instruktionen führt zu der Verklemmung? Wenn keine auftritt, begründen Sie, warum.

Diese Aufgabe war Teil der Klausur im Sommersemester 2025 (Zweittermin).

Lösung

Es kann keine Verklemmung auftreten, da die Ressourcen gemäß einer linearen Ordnung angefragt werden. Ordnet man die Ressourcen gedanklich nach dem Alphabet (a < b < c), fragt ein Thread immer von der “kleineren” zur “größeren” Ressource an (z. B. erst a, dann b). Um eine zirkuläre Wartebeziehung zwischen zwei Threads herzustellen, müsste mindestens ein Thread seine Anfragen entgegen der linearen Ordnung stellen (z. B. erst b, dann a).

Lernziele

In dieser Aufgabe …

  • nutzen die Studierenden ihr Wissen über Synchronisationsmechanismen, um mögliche Ausführungspfade eines Programms zu analysieren.
  • untersuchen die Studierenden ein gegebenes Programm auf das Vorhandensein von Deadlocks.
  • finden die Studierenden formale Argumente, um ihre Beobachtungen zum Auftreten eines Deadlocks zu stützen.