concurrency-sync.html 46.9 KB
Newer Older
Blanke, Daniela's avatar
Blanke, Daniela committed
1
<p>Der Zugriff auf gemeinsame Ressourcen, z.B. auf Objekte in Java, aus mehreren nebenläufigen Threads heraus, kann ohne Synchronisation zu inkonsistenten, ungewollten Zuständen führen. Dies tritt insbesondere dann auf, wenn mehrere Anweisungen im Kontrollfluss als eine atomare Aktion ausgeführt werden sollen, deren Effekt unbeeinflusst von Anweisungen sein muss, die in nebenläufigen Threads ausgeführt werden. Ähnliche Probleme treten im Umfeld von Datenbanken auf, wenn Transaktionen nicht ausreichend isoliert voneinander sind (s. <a href="https://de.wikipedia.org/wiki/ACID">ACID-Prinzip</a>).</p>
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

<h4>Race Conditions</h4>

<p>Ein typisches Beispiel für ein Nebenläufigkeitsproblem sind sogenannte <i>Race Conditions</i>. Diese beschreiben in der Programmierung eine Konstellation, in der der abschließend erreichte Zustand mehrerer nebenläufig ausgeführter Anweisungen von der zeitlichen Verschränkung (engl. <i>Interleaving</i>) der Threads durch den Scheduler ist. Race Conditions, die während der Entwicklungszeit nicht erkannt worden sind, können später Fehler verursachen, die im Betrieb nur sehr selten auftreten und deren Ursache im Nachhinein schwer zu lokalisieren ist. Derartige Fehler scheinen nicht reproduzierbar zu sein, da sie nur bei ungünstiger Verschränkung der nebenläufigen Threads auftreten. Das Debugging von Race Conditions ist demzufolge äußerst aufwändig.</p>

<p>Das folgende Beispiel stellt 2 nebenläufige Threads dar, die dieselben einfachen Anweisungen ausführen. Es wird zunächst die serielle Ausführung der Threads nacheinander und anschließend eine verschränkte Ausführung abgebildet. Die am Ende erreichten Zustände unterscheiden sich, da eine potentielle Race Condition vorliegt. Im Fall der verschränkten Ausführung ist eine der beiden Zustandsänderungen an der gemeinsamen Ressource verloren gegangen. Wir sprechen von einem <a href="https://de.wikipedia.org/wiki/Verlorenes_Update"><i>Lost Update</i></a>.</p>

<table class="table-bordered table-sm">
<tr><th>Thread 1</th><th>Thread 2</th><th></th><th>Zustand der gemeinsamen Ressource</th></tr>
<tr><td>Lesen des Zustands (0)</td><td></td><td>&larr;</td><td>0</td></tr>
<tr><td>Verändern des Zustands (+1)</td><td></td><td></td><td>0</td></tr>
<tr><td>Schreiben des Zustands (1)</td><td></td><td>&rarr;</td><td>1</td></tr>
<tr><td></td><td>Lesen des Zustands (1)</td><td>&larr;</td><td>1</td></tr>
<tr><td></td><td>Verändern des Zustands (+1)</td><td></td><td>1</td></tr>
<tr><td></td><td>Schreiben des Zustands (2)</td><td>&rarr;</td><td>2</td></tr>
</table>
<label>Serielle Ausführung der Anweisungen</label>

<table class="table-bordered table-sm">
<tr><th>Thread 1</th><th>Thread 2</th><th></th><th>Zustand der gemeinsamen Ressource</th></tr>
<tr><td>Lesen des Zustands (0)</td><td></td><td>&larr;</td><td>0</td></tr>
<tr><td></td><td>Lesen des Zustands (0)</td><td>&larr;</td><td>0</td></tr>
<tr><td>Verändern des Zustands (+1)</td><td></td><td></td><td>0</td></tr>
<tr><td></td><td>Verändern des Zustands (+1)</td><td></td><td>0</td></tr>
<tr><td>Schreiben des Zustands (1)</td><td></td><td>&rarr;</td><td>1</td></tr>
<tr><td></td><td>Schreiben des Zustands (1)</td><td>&rarr;</td><td>1</td></tr>
</table>
<label>Verschränkte Ausführung der Anweisungen</label>

<p>Im folgenden Code-Beispiel werden 100 Threads gestartet (Zeilen 29-31), von denen jeder auf eine gemeinsame Ressource vom Typ <code>int</code> zugreift (Zeile 5) und diese 100x inkrementiert (Zeilen 22-24). Da die Ressource mit 0 initialisiert ist, sollte in der letzten Zeile demzufolge ein abschließend erreichter Zustand der Ressource von 100 x 100 = 10.000 ausgegeben werden. Da in dieser Implementierung aber eine Race Condition vorliegt, wird dieser Zustand praktisch i.d.R. nicht erreicht. Einige Updates der Ressource gehen verloren.</p>

<pre><code class="language-java line-numbers">import java.util.concurrent.CountDownLatch;

class LostUpdate {

    int resource = 0; // shared resource

    // this method is the critical section
    void incrementResourceValue() {
        int t = resource;             // read resource value
        t++;                          // increment resource value
        resource = t;                 // write resource value
    }

    public static void main(String[] args) throws InterruptedException {
        new LostUpdate().runThreads(100);
    }

    void runThreads(int n) throws InterruptedException {
        CountDownLatch doneSignal = new CountDownLatch(n);

        Runnable runnable = () -> {
            for (int i = 0; i &lt; 100; i++) { // each thread increments the resource value 100 times
                incrementResourceValue();
            }
            doneSignal.countDown(); // send a signal that this thread is completed
        };

        // start all threads
        for (int i = 0; i &lt; n; i++) {
            new Thread(runnable).start();
        }

        // wait for all threads to complete
        doneSignal.await();

        System.out.println("Resource value = " + resource);
    }
}</code></pre> 
  
Blanke, Daniela's avatar
Blanke, Daniela committed
72
<p>Es existiert ein sogenannter kritischer Abschnitt (engl. <i>Critical Section</i>), indem sich nur ein Thread zurzeit befinden darf, damit keine Lost Updates auftreten. In dem obigen Code-Beispiel ist die Methode <code>incrementResourceValue</code> der kritische Abschnitt (Zeilen 8-12). Das Lesen, Inkrementieren und Schreiben des Zustands der Ressource muss als eine atomare Aktion ausgeführt werden und darf nicht durch eine Verschränkung der Threads unterbrochen werden. Eine naheliegende Idee ist es, den kritischen Abschnitt auf eine einzelne Anweisung zu reduzieren, z.B. indem die Methode <code>incrementResourceValue</code> wie folgt umgestaltet wird:</p>
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

<pre><code class="language-java line-numbers">void incrementResourceValue() {
	resource++;   // read, increment, and write resource value
}</code></pre> 

<p>Aber auch diese äußerst einfache Anweisung ist nicht <i>thread-safe</i>, d.h. sie ist keine unteilbare Aktion, da sie im kompilierten Bytecode in mehrere Instruktionen zerlegt wird, die wiederum durch eine unglückliche Verschränkung nebenläufiger Threads nicht direkt nacheinander ausgeführt werden könnten. Der Bytecode der obigen Methode ist folgend dargestellt, wobei die Instruktionen der Anweisung <code>resource++;</code> sich von <code>getfield</code> bis <code>putfield</code> erstrecken. Der Bytecode einer kompilierten Java-Klasse, z.B. <code>MyClass.class</code>, lässt sich mittels <code>javap -c MyClass.class</code> anzeigen.</p>

<pre><code class="language-clike line-numbers">void incrementResourceValue();
    Code:
       0: aload_0
       1: dup
       2: getfield      #2                  // Field resource:I
       5: iconst_1
       6: iadd
       7: putfield      #2                  // Field resource:I
      10: return</code></pre> 

<h4>Wechselseitiger Ausschluss für kritische Abschnitte</h4>

<span>Das Blockieren von Threads am Anfang von kritischen Abschnitten bezeichnen wir allgemein als wechselseitigen Ausschluss (engl. <i>Mutual Exclusion</i>, kurz <i>Mutex</i>). Das Verfahren des wechselseitigen Ausschlusses lässt sich in folgende drei Phasen unterteilen:</span>
<ol>
<li>Ein Thread erlangt eine Sperre (engl. <i>Lock</i>) für einen kritischen Abschnitt, in dem der Zustand einer gemeinsamen Ressource verändert wird.</li>
<li>Ein Thread durchläuft den kritischen Abschnitt und blockiert währenddessen andere Threads, die den kritischen Abschnitt in dieser Zeit ebenfalls betreten möchten.</li>
<li>Ein Thread gibt die erlangte Sperre wieder frei und informiert die blockierten Threads darüber.</li>
</ol>

Blanke, Daniela's avatar
Blanke, Daniela committed
99
<p>In Java muss das Schlüsselwort <code>synchronized</code> verwendet werden, um eine Methode oder einen beliebigen Anweisungsblock als kritischen Abschnitt zu kennzeichnen. Es gewährleistet, dass nur ein Thread gleichzeitig den kritischen Abschnitt betreten und durchlaufen darf. Erst durch die Verwendung des Schlüsselworts <code>synchronized</code> ist die folgende Methode tatsächlich <i>thread-safe</i></p>.
100
101
102
103
104

<pre><code class="language-java line-numbers">synchronized void incrementResourceValue() {
	resource++;
}</code></pre> 

Blanke, Daniela's avatar
Blanke, Daniela committed
105
<p>Während sich ein Thread im kritischen Abschnitt befindet, sichert die JVM durch eine Sperre zu, dass weitere Threads am Anfang des kritischen Abschnitts blockiert werden. Dadurch wechseln die Threads ggf. aus dem Zustand <b>Runnable</b> in den Zustand <b>Blocked</b>. Eine Sperre wird in Java je Objekt gesetzt, d.h. mehrere <code>synchronized</code>-Methoden und -Blöcke, die sich auf dasselbe Objekt beziehen, sind nicht unabhängig voneinander, sondern teilen sich eine gemeinsame Sperre. Das folgende Code-Beispiel zeigt beispielhaft eine Klasse mit zwei <code>synchronized</code>-Methoden und einem <code>synchronized</code>-Block. Wenn ein Objekt X dieser Klasse instantiiert wird und ein Thread auf diesem Objekt X die Methode <code>a</code> aufruft, so kann kein anderer Thread die Methoden <code>a</code>, <code>b</code> und den <code>synchronized</code>-Block in Methode <code>c</code> betreten. Auf einem weiteren Objekt Y dieser Klasse hingegen wären dadurch keine Sperren gesetzt und die <code>synchronized</code>-Methoden und -Blöcke könnten weiterhin aufgerufen werden, ohne zu blockieren.</p>
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

<pre><code class="language-java line-numbers">class SharedResource {

    // synchronized method
    synchronized void a() {
        // ...
    }

    // another synchronized method
    synchronized void b() {
        // ...
    }

    // method containing a synchronized block
    void c() {
        // ...
        synchronized (this) {
            // ...
        }
        // ...
    }
}</code></pre> 

<h4>Thread-Zustände in der JVM</h4>

Blanke, Daniela's avatar
Blanke, Daniela committed
131
<p>Das folgende UML-Zustandsdiagramm visualisiert die möglichen Zustände eines Threads innerhalb der JVM sowie die möglichen Transitionen zwischen diesen Zuständen. Sperren mittels <code>synchronized</code> gewährleisten den wechselseitigen Ausschluss für kritische Abschnitte und können damit Race Conditions verhindern. Die JVM versetzt die Threads ggf. automatisch in den Zustand <b>Blocked</b>, falls auf eine Sperre, bedingt durch <code>synchronized</code>, zu warten ist: <i>"Thread is blocked for synchronization"</i>.</p>
132
133
134
135
136
137

<img src="media/concurrency_thread_states.png" style="width:750px">
<label>Zustände und Transitionen von Threads in der JVM</label>
<span class="source"><a href="https://www.uml-diagrams.org/java-thread-uml-state-machine-diagram-example.html">Java Thread States and Life Cycle</a></span>

<p>Mittels <code>synchronized</code> können aber keine anwendungsspezifischen Bedingungen formuliert werden. Häufig ergibt sich in der Praxis die Situation, dass ein Thread auf ein bestimmtes Ereignis warten muss, bevor er sinnvoll weiterarbeiten kann. Er soll von einem anderen Thread benachrichtigt werden können, wenn dieser das Ereignis herbeigeführt hat, das aus dem Wartezustand befreit. Der grundlegende Mechanismus für das Warten auf Benachrichtigungen von anderen Threads kann in Java über die Methoden <code>wait</code> und <code>notify</code> abgebildet werden, die in der allgemeinen Oberklasse <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Object.html"><code>java.lang.Object</code></a> implementiert sind und damit jedem Objekt zur Verfügung stehen. Wenn ein Thread die Methode <code>wait</code> auf einem Objekt aufruft, wird er in den Zustand <b>Waiting</b> versetzt: <i>"Thread is waiting for notification"</i>. Erst wenn ein anderer Thread die Methode <code>notify</code> oder die Methode <code>notifyAll</code> auf demselben Objekt aufruft, wird der wartende Thread wieder aus dem Wartezustand befreit und in den Zustand <b>Runnable</b> versetzt. Die Methode <code>wait</code> kann auch mit einem Timeout-Argument versehen werden. In diesem Fall wird der Thread, wie bei einem Aufruf der Methode <code>Thread.sleep</code>, in den Zustand <b>Timed Waiting</b> versetzt. Über <code>java.lang.management.ThreadInfo</code> kann grundsätzlich ausgewertet werden, wie viel Zeit ein Thread in welchem der Zustände verbracht hat.</p>
Blanke, Daniela's avatar
Blanke, Daniela committed
138

139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

<p>Der Zustand <b>Runnable</b> ist in die Zustände <b>Ready</b> und <b>Running</b> untergliedert. Wenn es mehr nebenläufige Threads als Prozessoren gibt, steuert der Scheduler den Wechsel der Threads zwischen diesen Zuständen. Im Zustand <b>Running</b> ist einem Thread tatsächlich ein Prozessor zugewiesen, so dass der Kontrollfluss des Threads abgearbeitet werden kann. Ein Thread im Zustand <b>Ready</b> wartet darauf, dass der Scheduler ihm im Zuge des Interleaving einen Prozessor zuweist.</p>

<h4>Erzeuger-Verbraucher-Problem</h4>

<span>Die Verwendung der Methoden <code>wait</code> und <code>notify</code> lässt sich über das sogenannte <a href="https://de.wikipedia.org/wiki/Erzeuger-Verbraucher-Problem">Erzeuger-Verbraucher-Problem</a> motivieren. Wir stellen uns dazu folgendes Szenario vor:</span>
<ul>
<li>Es sind mehrere Erzeuger-Threads (unten implementiert in der Klasse <code>Producer</code>) aktiv, die generische Waren – oder in der folgenden Implementierung vereinfacht Textnachrichten – produzieren und diese für interessierte Verbraucher bereitstellen.</li>
<li>Weiterhin sind mehrere Verbraucher-Threads (unten implementiert in der Klasse <code>Consumer</code>) aktiv, die ihrerseits die bereitgestellten Waren bzw. Nachrichten konsumieren.</li>
<li>Die Erzeuger und Verbraucher tauschen die Nachrichten über einen Speicher aus, der in seiner Kapazität begrenzt ist und die gemeinsam genutzte Ressource darstellt. Beim Zugriff auf den Speicher ist also wechselseitiger Ausschluss zu gewährleisten. Nach welchem Prinzip (FIFO, LIFO, etc.) die Nachrichten im Speicher eingelagert und ausgeliefert werden, ist nicht wichtig. Entscheidend ist, dass der Speicher begrenzt ist, weil dadurch anwendungsspezifische Wartebedingungen für die Erzeuger- und Verbraucher-Threads entstehen. Ein Erzeuger kann nur Nachrichten bereitstellen, wenn der Speicher nicht voll ist. Ein Verbraucher kann nur Nachrichten konsumieren, wenn der Speicher nicht leer ist. Falls der Speicher also voll ist, wird ein Erzeuger, der eine neue Nachricht erzeugt hat, die Methode <code>wait</code> auf dem Speicher-Objekt aufrufen. Aus diesem Wartezustand kann ein Erzeuger befreit werden, wenn ein Verbraucher irgendwann eine vorhandene Nachricht aus dem Speicher entnimmt und damit einen freien Platz für die neue Nachricht des Erzeugers schafft. Die Verbraucher müssen dazu bei der Entnahme von Nachrichten aus dem Speicher, die Methode <code>notify</code> auf dem Speicher-Objekt aufrufen, um wartende Erzeuger zu befreien.
Falls der Speicher leer ist, wird ein Verbraucher die Methode <code>wait</code> auf dem Speicher-Objekt aufrufen, da er aktuell keine Nachricht entnehmen kann. Der Verbraucher wird später entsprechend von einem Erzeuger aus diesem Wartezustand befreit, der die Methode <code>notify</code> auf dem Speicher-Objekt aufruft, wenn er eine neue Nachricht bereitgestellt hat.
Eine derartige gemeinsam genutzte Ressource, die wechselseitigen Ausschluss in ihren Zugriffsmethoden zusichert und ggf. blockiert bis eine bestimmte Bedingung erfüllt ist, wird in der Informatik auch als <a href="https://en.wikipedia.org/wiki/Monitor_(synchronization)">Monitor</a> bezeichnet.
</ul>

<p>Es folgt eine beispielhafte Implementierung des Erzeuger-Verbraucher-Problems. Der Speicher ist in der Klasse <code>BoundedBufferSync</code> implementiert und hat hier eine Kapazität von lediglich 3 Nachrichten. Es werden in der Klasse <code>ProducerConsumerStarter</code> jeweils 2 Erzeuger- und Verbraucher-Threads gestartet.</p>

<ul class="nav nav-tabs" id="sync-pcp-tabs" role="tablist">
  <li class="nav-item"><a href="#sync-pcp-tabs-producer" class="nav-link active" data-toggle="tab" role="tab">Producer</a></li>
  <li class="nav-item"><a href="#sync-pcp-tabs-consumer" class="nav-link" data-toggle="tab" role="tab">Consumer</a></li> 
  <li class="nav-item"><a href="#sync-pcp-tabs-bb" class="nav-link" data-toggle="tab" role="tab">BoundedBuffer</a></li>  
  <li class="nav-item"><a href="#sync-pcp-tabs-bbimpl" class="nav-link" data-toggle="tab" role="tab">BoundedBufferSync</a></li>  
  <li class="nav-item"><a href="#sync-pcp-tabs-starter" class="nav-link" data-toggle="tab" role="tab">ProducerConsumerStarter</a></li>
</ul>
<div class="tab-content" id="sync-pcp-tabs-content">
  <div class="tab-pane show active" id="sync-pcp-tabs-producer" role="tabpanel">
	<pre><code class="language-java line-numbers">class Producer extends Thread {

    BoundedBuffer buffer;

    Producer(int id, BoundedBuffer buffer) {
        super("Producer " + id);
        this.buffer = buffer;
    }

    @Override
    public void run() {
        while (true) {
            try {
                sleep(ThreadLocalRandom.current().nextInt(0, 100)); // sleep
                buffer.put(UUID.randomUUID().toString()); // put a message to the buffer
            } catch (InterruptedException e) { }
        }
    }
}</code></pre>  
  </div> 
  <div class="tab-pane" id="sync-pcp-tabs-consumer" role="tabpanel">
	<pre><code class="language-java line-numbers">class Consumer extends Thread {

    BoundedBuffer buffer;

    Consumer(int id, BoundedBuffer buffer) {
        super("Consumer " + id);
        this.buffer = buffer;
    }

    @Override
    public void run() {
        while (true) {
            try {
                sleep(ThreadLocalRandom.current().nextInt(0, 100)); // sleep
                buffer.take(); // take a message from the buffer
            } catch (InterruptedException e) { }
        }
    }
}</code></pre>  
  </div> 
  <div class="tab-pane" id="sync-pcp-tabs-bb" role="tabpanel">
	<pre><code class="language-java line-numbers">interface BoundedBuffer {

    // put a new message to the buffer, waiting if necessary for space to become available
    void put(String message) throws InterruptedException;

    // retrieve and remove a message from the buffer, waiting if necessary until a new message becomes available
    String take() throws InterruptedException;
}</code></pre>  
  </div>   
  <div class="tab-pane" id="sync-pcp-tabs-bbimpl" role="tabpanel">
	<pre><code class="language-java line-numbers">import java.util.Queue;
import java.util.LinkedList;	

class BoundedBufferSync implements BoundedBuffer {

    int capacity;
    Queue&lt;String> queue = new LinkedList<>();

    BoundedBufferSync(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void put(String message) throws InterruptedException {
        while (queue.size() == capacity) {
            wait();
        }
        queue.add(message);
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
    }

    public synchronized String take() throws InterruptedException {
        while (queue.isEmpty()) {
            wait();
        }
        String message = queue.poll(); // retrieves and removes head of queue
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
        return message;
    }
}</code></pre>  
  </div>
  <div class="tab-pane" id="sync-pcp-tabs-starter" role="tabpanel">
	<pre><code class="language-java line-numbers">class ProducerConsumerStarter {

    public static void main(String[] args) {

        BoundedBuffer buffer = new BoundedBufferSync(3); // select bounded buffer implementation here

        for (int i = 1; i &lt;= 2; i++) {
            new Producer(i, buffer).start();
            new Consumer(i, buffer).start();
        }
    }
}</code></pre>  
  </div>    
</div>

Blanke, Daniela's avatar
Blanke, Daniela committed
264
<span>Es ist anzumerken, dass die Methode <code>notify</code> nur einen zufälligen Thread aus der Menge, der aktuell auf die betroffene Sperre wartenden Threads, aus dem Wartezustand befreit. Dadurch ist keine Fairness unter den wartenden Erzeugern und Verbrauchern gewährleistet. Das folgende Beispiel widmet sich der Herausforderung faires Warten, gemäß des Prinzips einer FIFO-Warteschlange, zu realisieren. Wir stellen uns dazu eine Parkgarage mit einer beschränkten Kapazität an Stellplätzen vor. In diese Parkgarage fahren Autos ein und aus. Wenn alle Stellplätze belegt sind, müssen neu ankommende Autos an einer Schranke vor der Parkgarage in einer FIFO-Warteschlange warten. Die Parkgarage ist die gemeinsam genutzte Ressource für mehrere nebenläufige Threads. Die Autos werden als Threads implementiert, die in einer Endlosschleife folgende Aktivitäten ausführen (Zeilen 22-27 in Klasse <code>Car</code>):</span>
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
<ul>
<li>herumfahren (Methode <code>cruise</code> in Klasse <code>Car</code>),</li>
<li>einfahren in die Parkgarage (Methode <code>enter</code> in Interface <code>ParkingGarage</code>),</li>
<li>parken (Methode <code>park</code> in Klasse <code>Car</code>),</li>
<li>ausfahren aus der Parkgarage (Methode <code>leave</code> in Interface <code>ParkingGarage</code>).</li>
</ul>

<ul class="nav nav-tabs" id="sync-fairness-tabs" role="tablist">
  <li class="nav-item"><a href="#sync-fairness-tabs-car" class="nav-link active" data-toggle="tab" role="tab">Car</a></li>
  <li class="nav-item"><a href="#sync-fairness-tabs-garage" class="nav-link" data-toggle="tab" role="tab">ParkingGarage</a></li> 
</ul>
<div class="tab-content" id="sync-fairness-tabs-content">
  <div class="tab-pane show active" id="sync-fairness-tabs-car" role="tabpanel">
	<pre><code class="language-java line-numbers">class Car extends Thread {

    ParkingGarage garage; // shared resource

    public static void main(String[] args) {
        int places = 3;  // number of slots in parking garage
        int cars = 7;    // number of cars

        ParkingGarage garage = new UnfairParkingGarageImpl(places); // select implementation of parking garage here
        for (int i = 1; i &lt;= cars; i++) {
            new Car("Car " + i, garage).start();
        }
    }

    public Car(String name, ParkingGarage garage) {
        super(name);
        this.garage = garage;
    }

    @Override
    public void run() {
        while (true) {
            cruise();
            garage.enter(this);
            park();
            garage.leave(this);
        }
    }

    void cruise() { idle(30); } // cruise 0 to 30 ms

    void park() { idle(100); } // cruise 0 to 100 ms

    void idle(int maxSleepTime) {
        try {
            TimeUnit.MILLISECONDS.sleep(ThreadLocalRandom.current().nextInt(0, maxSleepTime));
        }
        catch (InterruptedException e) { }
    }
}
</code></pre>  
  </div>
  <div class="tab-pane" id="sync-fairness-tabs-garage" role="tabpanel">
	<pre><code class="language-java line-numbers">interface ParkingGarage {

    // car which enters the parking garage
    void enter(Car car);

    // car which leaves the parking garage
    void leave(Car car);
}
</code></pre>  
  </div>  
</div>

<p>Der wechselseitige Ausschluss der Threads beim Einfahren und Ausfahren der Parkgarage ist sicherzustellen, d.h. die Methoden <code>enter</code> und <code>leave</code> der gemeinsamen Ressource <code>ParkingGarage</code> müssen in der jeweiligen Implementierung des Interface mittels <code>synchronized</code> als kritische Abschnitte gekennzeichnet werden (siehe unten Zeilen 11+25 in der Klasse <code>UnfairParkingGarage</code>). Im folgenden Code-Beispiel werden 2 alternative Implementierungen des Interface <code>ParkingGarage</code> dargestellt. In der Implementierung <code>UnfairParkingGarage</code> benachrichtigt ein Auto, das die Parkgarage verlässt, zufällig eines der wartenden Autos vor der Schranke und ermöglicht ihm das Einfahren in die Parkgarage. Dies geschieht durch den Aufruf der Methode <code>notify</code> in Zeile 28. Wenn die nummerierte Ankunft an der Schranke vor der Parkgarage nicht der ebenfalls nummerierten Einfahrt in die Parkgarage entspricht – also das FIFO-Prinzip verletzt ist, wird dies durch eine Ausgabe über <code>System.err</code> in Zeile 20 kenntlich gemacht. Dieser Fall wird bei der Ausführung des Programms relativ selten auftreten, kann aber beobachtet werden.</p>

335
<span>Die Implementierung <code>FairParkingGarage</code> unterscheidet sich leicht, um die Fairness beim Warten abzubilden – insbesondere in den Zeilen 16 und 32.</span>
336
<ul>
337
<li>In Zeile 32 werden mittels der Methode <code>notifyAll</code> alle der wartenden Autos statt nur ein zufälliges benachrichtigt.</li>
Blanke, Daniela's avatar
Blanke, Daniela committed
338
<li>In Zeile 16 wird die Bedingung für das Warten erweitert. Es muss nicht nur gewartet werden, wenn keine Stellplätze frei sind (<code>places == 0</code>), sondern auch, wenn das Auto noch nicht an vorderster Position der Warteschlange angelangt ist. Es wird dazu gezählt, wie viele Autos bereits an der Schranke vor der Parkgarage angekommen sind (<code>arrivalCount</code>, Zeile 12) und wie viele Autos bereits in die Parkgarage eingefahren sind (<code>entranceCount</code>, Zeile 22). Die Wertzuweisung in die Variable <code>arrival</code> (Zeile 12) entspricht daher der Vergabe einer laufend inkrementierten Wartenummer – ähnlich des Wartebereichs in vielen Ämtern in Deutschland. Ein vor der Schranke wartendes Auto wird zwar jedes Mal erweckt, wenn ein anderes Auto die Parkgarage verlässt, kann aber nur vorrücken und nicht einfahren (<code>arrival - 1 != entranceCount</code>, Zeile 16), bis alle übrigen wartenden Autos mit niedrigerer Wartenummer eingefahren sind. Auf diese Weise wird die Fairness beim Zugriff auf die gemeinsame Ressource eingehalten.</li>
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
</ul>

<ul class="nav nav-tabs" id="sync-fairness2-tabs" role="tablist">
  <li class="nav-item"><a href="#sync-fairness2-tabs-unfairgarage" class="nav-link active" data-toggle="tab" role="tab">UnfairParkingGarage</a></li>
  <li class="nav-item"><a href="#sync-fairness2-tabs-fairgarage" class="nav-link" data-toggle="tab" role="tab">FairParkingGarage</a></li> 
</ul>
<div class="tab-content" id="sync-fairness2-tabs-content">
  <div class="tab-pane show active" id="sync-fairness2-tabs-unfairgarage" role="tabpanel">
	<pre><code class="language-java line-numbers">class UnfairParkingGarageImpl implements ParkingGarage {
    int places;
    int arrivalCount = 0;
    int entranceCount = 0;

    UnfairParkingGarageImpl(int places) {
        this.places = places;
    }

    @Override
    public synchronized void enter(Car car) {
        int arrival = ++arrivalCount;
        while (places == 0) {
            log(car.getName() + " stops at barrier [waiting cars = " + (arrivalCount - entranceCount) + "].");
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        int entrance = ++entranceCount;
366
367
        log(car.getName() + " enters parking garage [arrival = " + arrival + ", entrance = " + entrance + "].", 
            arrival == entrance ? System.out : System.err);
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
        places--;
    }

    @Override
    public synchronized void leave(Car car) {
        log(car.getName() + " leaves parking garage.");
        places++;
        notify();
    }

    void log(String msg, PrintStream printStream) { printStream.println(msg); }

    void log(String msg) { log(msg, System.out); }
}</code></pre>  
  </div>
  <div class="tab-pane" id="sync-fairness2-tabs-fairgarage" role="tabpanel">
	<pre><code class="language-java line-numbers">class FairParkingGarageImpl implements ParkingGarage {
    int places;
    int arrivalCount = 0;
    int entranceCount = 0;

    FairParkingGarageImpl(int places) {
        this.places = places;
    }

    @Override
    public synchronized void enter(Car car) {
        int arrival = ++arrivalCount;
        if (places == 0) {
            log(car.getName() + " stops at barrier [waiting cars = " + (arrivalCount - entranceCount) + "].");
        }
        while (arrival - 1 != entranceCount || places == 0) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        int entrance = ++entranceCount;
405
406
        log(car.getName() + " enters parking garage [arrival = " + arrival + ", entrance = " + entrance + "].", 
            arrival == entrance ? System.out : System.err);
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
        places--;
        notifyAll();
    }

    @Override
    public synchronized void leave(Car car) {
        log(car.getName() + " leaves parking garage.");
        places++;
        notifyAll();
    }

    void log(String msg, PrintStream printStream) { printStream.println(msg); }

    void log(String msg) { log(msg, System.out); }
}</code></pre>  
  </div>  
</div>

Blanke, Daniela's avatar
Blanke, Daniela committed
425
<p>Es stellt sich beim genauen Hinsehen die Frage, warum auch am Ende der Methode <code>enter</code> die Methode <code>notifyAll</code> aufgerufen wird (Zeile 25). Dazu müssen wir uns vorstellen, dass die Parkgarage voll belegt ist, während mehrere Autos vor der Schranke warten. Nun verlassen direkt hintereinander mehrere Autos die Parkgarage, sodass wieder einige Stellplätze frei werden. Der gemeinsame kritische Abschnitt der Methoden <code>enter</code> und <code>leave</code> sichert zu, dass während des Ausfahrens eines Autos nicht gleichzeitig ein anderes Auto einfahren kann. Anschließend gelingt es dem vordersten Auto in der Warteschlange in die Parkgarage einzufahren. Nach dem Einfahren muss es die anderen wartenden Autos mittels <code>notifyAll</code> benachrichtigen (Zeile 25), da noch weitere Plätze frei sind und ansonsten nicht wieder belegt werden würden.</p>
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549

<p>Im Package <code>java.util.concurrent</code> finden wir heute lange etablierte Interfaces und Klassen, die eine entwicklerfreundlichere API für die grundlegenden Muster zur Synchronisation von Threads bieten. Dazu zählen z.B. die Interfaces <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/locks/Lock.html"><code>Lock</code></a> als Alternative zu <code>synchronized</code> und <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/locks/Condition.html"><code>Condition</code></a> als Alternative zu den Methoden <code>wait</code>, <code>notify</code> und <code>notifyAll</code>. Blockierende FIFO-Warteschlangen bieten sämtliche Implementierungen des Interface <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/BlockingQueue.html"><code>BlockingQueue</code></a>. Das folgende Code-Beispiel demonstriert wie der oben dargestellte, begrenzte und blockierende Speicher in der Klasse <code>BoundedBufferSync</code> alternativ über <code>Lock</code>- und <code>Condition</code>-Objekte (siehe <code>BoundedBufferLock</code>) bzw. über eine <code>ArrayBlockingQueue</code> (siehe <code>BoundedBufferBlockingQueue</code>) realisiert werden kann.</p>

<ul class="nav nav-tabs" id="sync-bb-tabs" role="tablist">
  <li class="nav-item"><a href="#sync-bb-tabs-sync" class="nav-link" data-toggle="tab" role="tab">BoundedBufferSync</a></li>
  <li class="nav-item"><a href="#sync-bb-tabs-lock" class="nav-link active" data-toggle="tab" role="tab">BoundedBufferLock</a></li> 
  <li class="nav-item"><a href="#sync-bb-tabs-blockqueue" class="nav-link" data-toggle="tab" role="tab">BoundedBufferBlockingQueue</a></li>  
</ul>
<div class="tab-content" id="sync-bb-tabs-content">
  <div class="tab-pane" id="sync-bb-tabs-sync" role="tabpanel">
	<pre><code class="language-java line-numbers">import java.util.Queue;
import java.util.LinkedList;	

class BoundedBufferSync implements BoundedBuffer {

    int capacity;
    Queue&lt;String> queue = new LinkedList<>();

    BoundedBufferSync(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void put(String message) throws InterruptedException {
        while (queue.size() == capacity) {
            wait();
        }
        queue.add(message);
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
    }

    public synchronized String take() throws InterruptedException {
        while (queue.isEmpty()) {
            wait();
        }
        String message = queue.poll(); // retrieves and removes head of queue
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
        return message;
    }
}</code></pre>  
  </div>
  <div class="tab-pane show active" id="sync-bb-tabs-lock" role="tabpanel">
	<pre><code class="language-java line-numbers">import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;
// ...

class BoundedBufferLock implements BoundedBuffer {

    int capacity;
    Queue&lt;String> queue = new LinkedList<>();

    Lock lock = new ReentrantLock();
    Condition notFull = lock.newCondition();
    Condition notEmpty = lock.newCondition();

    BoundedBufferLock(int capacity) {
        this.capacity = capacity;
    }

    public void put(String message) throws InterruptedException {
        lock.lock(); // enter critical section
        try {
            while (queue.size() == capacity) {
                notFull.await();
            }
            queue.add(message);
            System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
            notEmpty.signal();
        } finally {
            lock.unlock();  // leave critical section
        }
    }

    public String take() throws InterruptedException {
        lock.lock(); // enter critical section
        try {
            while (queue.isEmpty()) {
                notEmpty.await();
            }
            String message = queue.poll(); // retrieves and removes head of queue
            System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
            notFull.signal();
            return message;
        } finally {
            lock.unlock();  // leave critical section
        }
    }
}</code></pre>  
  </div> 
  <div class="tab-pane" id="sync-bb-tabs-blockqueue" role="tabpanel">
	<pre><code class="language-java line-numbers">import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ArrayBlockingQueue;

class BoundedBufferBlockingQueue implements BoundedBuffer {

    int capacity;
    BlockingQueue&lt;String> queue;

    public BoundedBufferBlockingQueue(int capacity) {
        queue = new ArrayBlockingQueue<>(capacity);
    }

    @Override
    public void put(String message) throws InterruptedException {
        queue.put(message);
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
    }

    @Override
    public String take() throws InterruptedException {
        String message = queue.take();
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        return message;
    }
}</code></pre>  
  </div>    
</div>

<p>Die gezeigten Code-Beispiele zur Synchronisation von Threads in Java finden sich im Verzeichnis <a href="/concurrency" class="repo-link">/concurrency</a> des Modul-Repository.</p>

<h4>Deadlock und Starvation</h4>

Blanke, Daniela's avatar
Blanke, Daniela committed
550
<p>Wenn ein Thread nicht nur eine, sondern mehrere Sperren auf exklusiv nutzbare Ressourcen anfordert, kann es zu einer Verklemmung (engl. <i>Deadlock</i>) zwischen den nebenläufigen Threads kommen, die um den Zugriff auf die Ressourcen konkurrieren. Ein Deadlock bezeichnet den Zustand, bei dem eine zyklische Wartekette zwischen mehreren Threads eingetreten ist, wobei jeder beteiligte Thread auf die Freigabe von Sperren auf Ressourcen wartet, die ein anderer beteiligter Thread bereits exklusiv erlangt hat. Im einfachsten Fall sind, wie in der folgenden Abbildung visualisiert, nur 2 Threads und 2 Ressourcen beteiligt.</p>
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624

<img src="media/concurrency_deadlock.png" style="width:800px">
<label>Verklemmung von Threads beim Zugriff auf exklusiv nutzbare Ressourcen</label>

<span>Für einen Deadlock müssen folgende Bedingungen erfüllt sein. Wenn nur eine Bedingung aufgehoben werden kann, wird auch der Deadlock aufgelöst.</span>
<ol>
<li>Ressourcen sind nur exklusiv unter wechselseitigem Ausschluss nutzbar.</li>
<li>Belegte Ressourcen können einem Thread nicht entzogen werden.</li>
<li>Threads, die bereits eine Ressource belegt haben, fordern weitere an.</li>
<li>Es entsteht eine zyklische Wartekette zwischen den Threads. Jeder Thread belegt eine Ressource, die ein anderer Thread in der Wartekette anfordert.</li>
</ol>

<p>Zur Vermeidung von Deadlocks kann ein optimistischer oder ein pessimistischer Ansatz des Sperrens von Ressourcen verfolgt werden. Beim <i>Optimistic Locking</i> ist die grundlegende Annahme, dass Deadlocks aufgrund geringer Konkurrenz beim exklusiven Zugriff auf Ressourcen selten auftreten. Es wird periodisch geprüft, ob ein Deadlock eingetreten ist. Falls ein Deadlock, also eine zyklische Wartekette, erkannt wird, wird einem der beteiligten Threads eine Sperre und damit der Zugriff auf eine Ressource entzogen. Damit wird die zweite der obigen Bedingungen gelöst. Die Transaktion, die aktuell im betroffenen Thread ausgeführt wird, muss zurückgerollt und neugestartet werden (= <i>Rollback</i> einer Transaktion).</p>

<p>Beim <i>Pessimistic Locking</i> hingegen sollen Deadlocks grundsätzlich vermieden werden. Dazu muss ein Thread alle benötigten Sperren auf exklusiv nutzbare Ressourcen gleich zu Beginn der auszuführenden Transaktion anfordern. Entweder wird das Anfordern aller Sperren als atomare Aktion in einem kritischen Abschnitt zusammengefasst, wodurch die dritte der obigen Bedingungen hinfällig wird – oder die einzeln angeforderten Sperren werden in einer definierten Reihenfolge erlangt, wodurch keine Zyklen mehr entstehen können und die vierte der obigen Bedingungen gelöst wird.</p>

<p>Wer in Lehrbüchern oder im Internet zum Thema <i>Deadlock</i> recherchiert, wird relativ schnell auf das berühmte Beispielproblem der <a href="https://en.wikipedia.org/wiki/Dining_philosophers_problem">Dining Philosophers</a> stoßen. Die Problemstellung wurde bereits <a href="http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1000.PDF">1965 von Edsger Dijkstra</a> für seine Studierenden formuliert und ist bis heute in der Informatik-Lehre etabliert. Wir stellen uns folgende Situation vor, die in der Abbildung unten veranschaulicht ist: 5 Philosophen sitzen an einem Tisch und denken. Vor jedem Philosophen liegt ein Teller, um gelegentlich davon zu essen. Zum Essen benötigt ein Philosoph zwei Gabeln, die links und rechts des Tellers liegen. Zu einem zufälligen Zeitpunkt nimmt jeder Philosoph zwei Gabeln und isst zufällig lange, bis er sich wieder dem Denken zuwendet. Es stehen auf dem Tisch aber insgesamt nur 5 Gabeln zur Verfügung, und jeder Philosoph benötigt die beiden Gabeln links und rechts seines Tellers zum Essen.</p>

<img src="media/concurrency_dining_philosophers.png" style="width:240px">
<label>Veranschaulichung des Problems der Dining Philosophers</label>

<p>Die Philosophen sind in diesem Beispiel die Threads, die um den exklusiven Zugriff auf die Gabeln als Ressourcen konkurrieren. Wenn alle Philosophen zeitgleich zuerst die rechte und dann die linke Gabel nehmen, entsteht ein Deadlock, bei dem jeder Philosoph auf seinen linken Nachbarn warten muss, bis dieser die benötigte Gabel wieder freigibt. In diesem Zustand würden alle Philosophen verhungern. Ein Deadlock kann vermieden werden, wenn das Erlangen beider Gabeln als atomare Aktion in einem kritischen Abschnitt realisiert wird.</p>

<span>Ein Blick auf die obige Abbildung zeigt, dass immer 2 Philosophen parallel essen können, z.B. Philosoph 1 und Philosoph 3 und anschließend Philosoph 2 und Philosoph 4. Wenn diese 4 Philosophen sich jeweils paarweise abwechseln, wird der fünfte Philosoph verhungern. Dieses Verhungern (engl. <i>Starvation</i>) eines Threads auf Kosten der anderen, weil es keine faire Warteschlange gibt, ist ebenfalls zu vermeiden. Für das Philosophen-Problem gibt es unterschiedliche Ansätze um Starvation zu vermeiden:</span>
<ul>
<li>FIFO-Warteschlange – ineffizient, da Wartezeiten nicht zu optimaler Auslastung führen</li> 
<li>Timeouts beim Warten, d.h. Vorrang bei der Belegung von Ressourcen für Threads, die bereits lange warten</li>
<li>Asymmetrische Lösung durch einen zusätzlichen Butler-Thread, der die Belegung der Ressourcen möglichst fair steuert</li>
</ul>

<p>Es wird an dieser Stelle kein Java-Code als Lösung für das Philosophen-Problem dargestellt. Stattdessen soll die Lösung mit Hilfe der folgenden Klassen eigenständig entwickelt werden!</p>

<ul class="nav nav-tabs" id="sync-dining-tabs" role="tablist">
  <li class="nav-item"><a href="#sync-dining-tabs-philosopher" class="nav-link active" data-toggle="tab" role="tab">Philosopher</a></li>
  <li class="nav-item"><a href="#sync-dining-tabs-fork" class="nav-link" data-toggle="tab" role="tab">Table</a></li> 
</ul>
<div class="tab-content" id="sync-dining-tabs-content">
  <div class="tab-pane show active" id="sync-dining-tabs-philosopher" role="tabpanel">
	<pre><code class="language-java line-numbers">class Philosopher extends Thread  {
    int number;

    @Override
    public void run() {
        while (true) {
            // TODO: think, takeFork, eat, putFork
        }
    }
}</code></pre>  
  </div>
  <div class="tab-pane" id="sync-dining-tabs-fork" role="tabpanel">
	<pre><code class="language-java line-numbers">class Table {
    boolean[] forkUsed;

    synchronized void takeFork(int number) {
        // TODO ...
    }

    synchronized void putFork(int number) {
        // TODO ...
    }
}</code></pre>  
  </div>    
</div>

<h4>Java Concurrency API</h4>

<p>Die <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/package-summary.html">Java Concurrency API</a> im Package <code>java.util.concurrent</code> stellt seit Java 5 diverse Interfaces und Klassen bereit, um nebenläufige Threads zu steuern und zu koordinieren. Dazu zählen:</p>

<ul>
<li><b>Executors:</b> Die Klassen <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ThreadPoolExecutor.html"><code>ThreadPoolExecutor</code></a> und <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ScheduledThreadPoolExecutor.html"><code>ScheduledThreadPoolExecutor</code></a> stellen anpassbare, flexible Thread-Pools bereit.</li>
<li><b>Queues:</b> Die Klasse <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ConcurrentLinkedQueue.html"><code>ConcurrentLinkedQueue</code></a> stellt eine effiziente, skalierbare, Thread-sichere und nicht blockierende FIFO-Warteschlange bereit. Fünf weitere Klassen implementieren das Interface <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/BlockingQueue.html"><code>BlockingQueue</code></a>, das die blockierenden Methoden <code>put</code> and <code>take</code> definiert: <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/LinkedBlockingQueue.html"><code>LinkedBlockingQueue</code></a>, <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ArrayBlockingQueue.html"><code>ArrayBlockingQueue</code></a>, <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/SynchronousQueue.html"><code>SynchronousQueue</code></a>, <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/PriorityBlockingQueue.html"><code>PriorityBlockingQueue</code></a> und <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/DelayQueue.html"><code>DelayQueue</code></a>. Diese Klassen decken die häufigsten Verwendungen für Erzeuger-Verbraucher-Probleme, Nachrichtenaustausch (engl. <i>Messaging</i>) und die Verarbeitung nebenläufiger Aufgaben ab.</li>
<li><b>Concurrent Collections:</b> Neben Warteschlangen werden <code>Collection</code>-Implementierungen angeboten, die für die Verwendung im Multithreading-Kontext konzipiert sind, z.B. <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html"><code>ConcurrentHashMap</code></a> und <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/CopyOnWriteArrayList.html"><code>CopyOnWriteArrayList</code></a>. Wenn zu erwarten ist, dass viele Threads auf eine bestimmte Collection zugreifen, ist eine <code>ConcurrentHashMap</code> i.d.R. einer synchronisierten <code>HashMap</code> vorzuziehen. Eine <code>CopyOnWriteArrayList</code> ist einer synchronisierten <code>ArrayList</code> vorzuziehen, wenn die erwartete Anzahl an Lesezugriffen und Iterationen die Anzahl an Schreibzugriffen auf einer Liste übersteigt.</li>
<li><b>Locks:</b> Die Implementierungen der Interfaces <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/locks/Lock.html"><code>Lock</code></a> und <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/locks/Condition.html"><code>Condition</code></a> ermöglichen eine größere Flexibilität bei der Verwendung von Sperren und Bedingungen, jedoch auf Kosten einer unhandlicheren Syntax im Vergleich zum Schlüsselwort <code>synchronized</code>.</li>
<li><b>Timing:</b> Die Klasse <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/TimeUnit.html"><code>TimeUnit</code></a> bietet unterschiedliche Granularitäten (inkl. Nanosekunden) zum Steuern von Timeout-basierten Vorgängen.</li>
Blanke, Daniela's avatar
Blanke, Daniela committed
625
<li><b>Atomics:</b> Eine Sammlung von Klassen, die eine Thread-sichere Programmierung ohne Sperren für einzelne Variablen unterstützen, findet sich im	 Package <code>java.util.concurrent.atomic</code> – insbesondere für Variablen, die von einem Basisdatentyp sind. Instanzen der Klasse <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/atomic/AtomicLong.html"><code>AtomicLong</code></a> o.ä. bieten jeweils Zugriff und Aktualisierungen für eine einzelne Variable des entsprechenden Typs. Mittels <code>AtomicLong</code> kann im Multithreading-Kontext z.B. die Vergabe einer eindeutigen Sequenznummer realisiert werden, wie das folgende Code-Beispiel demonstriert.</li>
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640

<pre><code class="language-java line-numbers">class Sequencer {
	private final AtomicLong sequenceNumber = new AtomicLong(0);
	public long next() {
		return sequenceNumber.getAndIncrement(); // atomic and thread-safe variant of sequenceNumber++
	}
}</code></pre> 
<li><b>Synchronizers:</b> Es werden weitere Klassen für spezielle Synchronisationsidiome angeboten, wie z.B.:
	<ul>
	<li>Ein <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/CountDownLatch.html"><code>CountDownLatch</code></a> ist eine sehr einfache, verbreitete Klasse zum Blockieren eines Threads, bis eine bestimmte Anzahl von Signalen, Ereignissen oder Bedingungen erreicht wird.</li>
	<li>Ein <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/CyclicBarrier.html"><code>CyclicBarrier</code></a> ist eine Klasse zur Synchronisation, mit der eine Gruppe von Threads aufeinander warten kann, bis jeder von ihnen eine gemeinsame Barriere als Synchronisationspunkt erreicht hat. Die Barriere ist zyklisch, da sie nach dem Freigeben der wartenden Threads bei Bedarf erneut verwendet werden kann.</li>
	<li>Ein <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/Exchanger.html"><code>Exchanger</code></a> ermöglicht, dass zwei Threads Objekte an einem Rendezvous-Punkt austauschen. Dies ist häufig bei Pipelines zur Datenverarbeitung nützlich.</li>
	</ul>
</li>
</ul>