3.2.11.3.1.1 Wechselseitiger Ausschluss
Der folgende Quellcode ist bereits aus dem Kapitel Kritischer Abschnitt bekannt:
1 public class Beispiel_Kritischer_Abschnitt {
2
3 static int counter = 0;
4
5 public static class Thread_A extends Thread {
6 public void run() {
7 do_something(); // unkritisch
8 count_from_10(); // kritisch !!!
9 do_something_else(); // unkritisch
10 }
11 private void do_something() {
12 // unkritischer Abschnitt
13 System.out.println("Thread_A: unkritisch");
14 }
15 private void count_from_10() {
16 // Vorsicht: kritischer Abschnitt!
17 counter = 10;
18 counter++;
19 counter++;
20 System.out.println("A-Counter: " + counter);
21 }
22 private void do_something_else() {
23 // unkritischer Abschnitt
24 System.out.println("Thread_A: wieder unkritisch");
25 }
26 }
27
28 public static class Thread_B extends Thread {
29 public void run() {
30 System.out.println("Thread_B ist gestartet.");
31 counter = 20;
32 counter++;
33 counter++;
34 counter++;
35 counter++;
36 counter++;
37 counter++;
38 System.out.println("B-Counter: " + counter);
39 }
40 }
41
42 public static void main(String[] args) {
43 Thread a = new Thread_A();
44 Thread b = new Thread_B();
45 a.start();
46 b.start();
47 }
48
49 }
Erläuterungen zu Listing 1
Zwei Threads A und B greifen jeweils auf die counter-Variable zu. Die counter-Variable stellt damit ein gemeinsam genutztes Betriebsmittel dar.
In beiden Threads lassen sich kritische Abschnitte identifizieren. Es muss dafür gesorgt werden, dass sich immer nur ein Thread zur Zeit in seinem kritischen Abschnitt befindet.
Dies nennt man den wechselseitigen Ausschluss: Wenn sich ein Thread in seinem kritischen Abschnitt befindet, dann muss ausgeschlossen sein, dass auch der andere Thread in seinen kritischen Abschnitt eintritt.
Du kennst bereits das aktive Warten (mit TSL), durch das ein wechselseitiger Ausschluss realisiert werden kann. Jedoch verschwendet das aktive Warten CPU-Zeit.
Ein Mutex kommt nun anstatt des aktiven Wartens zum Einsatz. Somit verschwindet auch der Nachteil der CPU-Zeitverschwendung.
Mutex in Listing 1 einbauen
Um einen Mutex in Listing 1 einzubauen, muss diese Datenstruktur zunächst erzeugt werden, um anschließend die P()- und V()-Operationen an den geeigneten Stellen aufzurufen.
Listing 2 zeigt dieses Vorgehen, direkt darunter gibt es einige Erläuterungen.
1 public class Wechselseitiger_Ausschluss_mit_Mutex {
2
3 static int counter = 0;
4 static Semaphore mutex = new Semaphore(1);
5
6 public static class Thread_A extends Thread {
7 public void run() {
8 do_something(); // unkritisch
9 count_from_10(); // kritisch !!!
10 do_something_else(); // unkritisch
11 }
12 private void do_something() {
13 // unkritischer Abschnitt
14 System.out.println("Thread_A: unkritisch");
15 }
16 private void count_from_10() {
17 // Vorsicht: kritischer Abschnitt!
18
19 P(mutex);
20
21 counter = 10;
22 counter++;
23 counter++;
24 System.out.println("A-Counter: " + counter);
25
26 V(mutex);
27 }
28 private void do_something_else() {
29 // unkritischer Abschnitt
30 System.out.println("Thread_A: wieder unkritisch");
31 }
32 }
33
34 public static class Thread_B extends Thread {
35 public void run() {
36 System.out.println("Thread_B ist gestartet.");
37
38 P(mutex);
39
40 counter = 20;
41 counter++;
42 counter++;
43 counter++;
44 counter++;
45 counter++;
46 counter++;
47 System.out.println("B-Counter: " + counter);
48
49 V(mutex);
50 }
51 }
52
53 public static void main(String[] args) {
54 Thread a = new Thread_A();
55 Thread b = new Thread_B();
56 a.start();
57 b.start();
58 }
59
60 }
Erläuterungen zu Listing 2 mit Mutex
Entscheidend sind hier die Zeilen 4, 19, 26, 38 und 49.
In Zeile 4 wird zunächst eine Variable mit dem Namen mutex vom Datentyp Semaphore deklariert und initialisiert. Hier wird also ein binärer Semaphor (Mutex) erzeugt.
Der kritische Abschnitt von Thread_A liegt in den Zeilen 21 bis 24.
Direkt davor (in Zeile 19) wird die Methode P(mutex); aufgerufen, direkt danach (in Zeile 26) wird die Methode V(mutex); aufgerufen.
Der kritische Abschnitt von Thread_B liegt in den Zeilen 40 bis 47.
Direkt davor (in Zeile 38) wird die Methode P(mutex); aufgerufen, direkt danach (in Zeile 49) wird die Methode V(mutex); aufgerufen.
Mutex-Beispiel mit Threads
Der hier abgedruckte Quellcode zu Listing 2 ist in dieser Form nicht ausführbar. Er soll lediglich beispielhaft verdeutlichen, an welchen Stellen zusätzliche Operationen im Bezug auf den Mutex zur Realisierung des wechselseitigen Ausschlusses eingefügt werden müssen.
Zwar gibt es in Java eine Klasse Semaphore, siehe
http://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Semaphore.html
jedoch sind hier die P() und V()-Operationen anders benannt:
acquire() bzw. release()
Unter dem hier verlinkten Dokument findet sich bei Bedarf ein anderes sehr einfaches Java-Beispiel, welches den praktischen Einsatz der Semaphore-Klasse zeigt.
Aufgabe 1
Spiele einmal gedanklich den Ablauf der beiden Threads aus Listing 2 durch.
Was passiert, wenn Thread_A bereits seinen kritischen Abschnitt betreten hat, und beispielsweise in Zeile 23 ein Kontextwechsel zu Thread_B erfolgt?
- Thread_B möchte auch seinen kritischen Abschnitt betreten und ruft in Zeile 38 die P()-Operation auf... Und dann?
- Was passiert mit Thread-B?
- Und wie kommt Thread-B da wieder raus?
Aufgabe 2
Vergleiche den obigen Quellcode aus Listing 2 (Mutex) einmal mit dem bereits bekannten Quellcode mit dem Beispiel des Aktiven Wartens (mit while).
1 public class Beispiel_Aktives_Warten_mit_while {
2
3 static int counter = 0; // gemeinsam genutztes Betriebsmittel
4 static int lock = 0; // Sperrvariable
5
6 public static class Thread_A extends Thread {
7 public void run() {
8 do_something(); // unkritisch
9 count_from_10(); // kritisch !!!
10 do_something_else(); // unkritisch
11 }
12 private void do_something() {
13 // unkritischer Abschnitt
14 System.out.println("Thread_A: unkritisch");
15 }
16 private void count_from_10() {
17 // Vorsicht: kritischer Abschnitt!
18 while (lock == 1); // Semikolon beachten!
19 lock = 1;
20
21 counter = 10;
22 counter++;
23 counter++;
24 System.out.println("A-Counter: " + counter);
25
26 lock = 0;
27 }
28 private void do_something_else() {
29 // unkritischer Abschnitt
30 System.out.println("Thread_A: wieder unkritisch");
31 }
32 }
33
34 public static class Thread_B extends Thread {
35 public void run() {
36 System.out.println("Thread_B ist gestartet.");
37 while (lock == 1); // Semikolon beachten!
38 lock = 1;
39
40 counter = 20;
41 counter++;
42 counter++;
43 counter++;
44 counter++;
45 counter++;
46 counter++;
47 System.out.println("B-Counter: " + counter);
48
49 lock = 0;
50 }
51 }
52
53 public static void main(String[] args) {
54 Thread a = new Thread_A();
55 Thread b = new Thread_B();
56 a.start();
57 b.start();
58 }
59
60 }
Hier ist ein Bild mit beiden Quelltexten nebeneinander:
Mutex mit Prozessen
Die in Listing 2 beispielhaft gezeigte Verwendung eines Mutex bezieht sich im Quellcode auf zwei Threads. Ein Mutex wird in Betriebssystemen aber üblicherweise eingesetzt, um die kritischen Abschnitte zweier Prozesse (mit einem gemeinsam genutzten Betriebsmittel) gegeneinander abzuschotten.
Aufgabe 3
Wikipedia zeigt auf der Seite
http://de.wikipedia.org/wiki/Semaphor_%28Informatik%29#Anwendungsbeispiele
im Abschnitt "Einsatz in Konkurrenzsituationen I" ein sehr einfach gehaltenes Beispiel mit zwei Prozessen und einem Mutex.
Schau' es dir dort an!
Das Erzeugen eines Mutex sowie die P()- und V()-Operation kann man sich bei Betriebssystemen als Systemaufrufe vorstellen. Somit verwaltet das Betriebssystem die Warteschlange eines Semaphors und kann problemlos dafür sorgen, dass die P()- und V()-Operation atomar abläuft. Das Betriebssystem kann dann mit dem Scheduler die wartenden Prozesse in den Status "wartend" versetzen - was nicht möglich wäre, wenn die Programmiersprache selbst die Mutex-Verwaltung durchführen würde.
Aufgabe 4
An der FH Köln wird ein Semaphor Workshop mit Java-Applets bereitgestellt, anhand derer der wechselseitige Ausschluss mit Hilfe eines binären Semaphors (Mutex) nachvollzogen werden kann. Probiere es aus!
http://www.nt.fh-koeln.de/fachgebiete/inf/diplom/semwork/beispiele/waus/waus.html
Falls das Java-Applet in deinem Browser nicht startet, musst du eventuell die Java-Sicherheitseinstellungen anpassen. Trage dort ein: http://www.nt.fh-koeln.de
Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png