« »

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.

b)

Level 1: Wissen

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

c)

Level 1: Wissen

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

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).

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.