This article is part of our Academy Course titled Java Concurrency Essentials.
In this course, you will dive into the magic of concurrency. You will be introduced to the fundamentals of concurrency and concurrent code and you will learn about concepts like atomicity, synchronization and thread safety. Check it out here!
Table Of Contents
1. Liveness
When developing an application that uses concurrency to accomplish its aims, you may come across situations where different threads may block each other. As the whole application then performs slower than expected, we would say that the application does not finish in matter of time as expected. In this section we will take a closer look at the problems that may endanger the liveness of a multi-threaded application.
1.1. A Deadlock
The term deadlock is well known to software developers and even most normal computer users use this term from time to time, although it is not always used in the correct sense. Strictly spoken it means that two (or more) threads are each waiting on the other thread to free a resource that it has locked, while the thread itself has locked a resource the other thread is waiting on:
Thread 1: locks resource A, waits for resource B Thread 2: locks resource B, waits for resource A
To gain an even better understanding of the problem, let’s have a look at the following source code:
public class Deadlock implements Runnable {
private static final Object resource1 = new Object();
private static final Object resource2 = new Object();
private final Random random = new Random(System.currentTimeMillis());
public static void main(String[] args) {
Thread myThread1 = new Thread(new Deadlock(), "thread-1");
Thread myThread2 = new Thread(new Deadlock(), "thread-2");
myThread1.start();
myThread2.start();
}
public void run() {
for (int i = 0; i < 10000; i++) {
boolean b = random.nextBoolean();
if (b) {
System.out.println("[" + Thread.currentThread().getName() + "] Trying to lock resource 1.");
synchronized (resource1) {
System.out.println("[" + Thread.currentThread().getName() + "] Locked resource 1.");
System.out.println("[" + Thread.currentThread().getName() + "] Trying to lock resource 2.");
synchronized (resource2) {
System.out.println("[" + Thread.currentThread().getName() + "] Locked resource 2.");
}
}
} else {
System.out.println("[" + Thread.currentThread().getName() + "] Trying to lock resource 2.");
synchronized (resource2) {
System.out.println("[" + Thread.currentThread().getName() + "] Locked resource 2.");
System.out.println("[" + Thread.currentThread().getName() + "] Trying to lock resource 1.");
synchronized (resource1) {
System.out.println("[" + Thread.currentThread().getName() + "] Locked resource 1.");
}
}
}
}
}
}As can be seen from the code above, two threads are started and try to lock the two static resources. But for a deadlock we need a different sequence for both threads, hence we utilize the Random instance to choose what resource the thread wants to lock first. If the boolean variable b is true, the resource1 is locked first and the threads then tries to get the lock for resource 2. If b is false, the thread locks resource2 first and then tries to lock resource1. This program does not have to run long until we reach the first deadlock, i.e. the program hangs forever if we would not terminate it:
[thread-1] Trying to lock resource 1. [thread-1] Locked resource 1. [thread-1] Trying to lock resource 2. [thread-1] Locked resource 2. [thread-2] Trying to lock resource 1. [thread-2] Locked resource 1. [thread-1] Trying to lock resource 2. [thread-1] Locked resource 2. [thread-2] Trying to lock resource 2. [thread-1] Trying to lock resource 1.
In this execution thread-1 holds the lock for resource2 and waits for the lock on resource1, whereas thread-2 holds the lock for resource1 and waits for resource2.
If we would set the boolean variable b in the example code above to true, we would not experience any deadlock because the sequence in which thread-1 and thread-2 are requesting the locks is always the same. Hence one of both threads gets the lock first and then requests the second lock, which is still available because the other threads wait for the first lock.
In general the following requirements for a deadlock can be identified:
- Mutual exclusion: There is a resource which can be accessed only by one thread at any point in time.
- Resource holding: While having locked one resource, the thread tries to acquire another lock on some other exclusive resource.
- No preemption: There is no mechanism, which frees the resource if one threads holds the lock for a specific period of time.
- Circular wait: During runtime a constellation occurs in which two (or more) threads are each waiting on the other thread to free a resource that it has locked.
Although the list of requirements looks long, it is not uncommon that more advanced multi-threaded applications have deadlock problems. But you can try to avoid deadlocks if you are able to relax one of the requirements listed above:
- Mutual exclusion: This is a requirement that often cannot be relaxed, as the resource has to be used exclusively. But this must no always be the case. When using DBMS systems, a possible solution instead of using a pessimistic lock on some table row that has to be updated, one can use a technique called Optimistic Locking.
- A possible solution to circumvent resource holding while waiting for another exclusive resource is to lock all necessary resources at the beginning of the algorithm and free all resources if it is not possible to obtain all locks. This is of course not always possible, maybe the resources to lock are not known ahead or it is just as waste of resources.
- If the lock cannot be obtained immediately, a possible solution to circumvent a possible deadlock is the introduction of a timeout. The SDK class ReentrantLock for example provides the possibility to specify a timeout for locking.
- As we have seen from the example code above, a deadlock does not appear if the sequence of lock requests does not differ between the different threads. This can be easily controlled if you are able to put all the locking code into one method where all threads have to pass through.
In more advanced applications you may even consider the implementation of a deadlock detection system. Here you would have to implement some kind of thread monitoring, where each thread reports the successful acquisition of a lock and his attempt to obtain a lock. If threads and locks are modelled as a directed graph, you are able to detect when two different threads are holding resources while simultaneously requesting another blocked resource. If you would then able to force the blocking threads to release an obtained resource you are able to resolve deadlock situations automatically.
1.2. Starvation
The scheduler decides which of the threads in state RUNNABLE it should execute next. The decision is based on the thread’s priority; hence threads with lower priority gain less CPU time than threads with a higher priority. What sounds like a reasonable feature can also cause problems when abused. If most of the time threads with a high priority are executed, the threads with lower priority seem to “starve” as they get not enough time to execute their work properly. Therefore it is recommended to set the priority of a thread only if there are strong reasons for it.
A sophisticated example for thread starvation is for example the finalize() method. This feature of the Java language can be used to execute code before an object gets garbage collected. But when you take a look at the priority of the finalizer thread, you may see that it runs not with highest priority. Hence there is the possibility for thread starvation if the finalize() methods of your object spend too much time in comparison to the rest of the code.
Another problem with execution time is the problem, that it is not defined in which order threads pass a synchronized block. When many parallel threads have to pass some code that is encapsulated with a synchronized block, it may happen that certain threads have to wait longer than other threads until they can enter the block. In theory they may never enter the block.
A solution to the latter problem is the so called “fair” lock. Fair locks take the waiting time of the threads into account, when choosing the next thread to pass. An example implementation of a fair lock is provided by the Java SDK: java.util.concurrent.locks.ReentrantLock. If the constructor with the boolean flag set to true is used, the ReentrantLock grants access to the longest-waiting thread. This guarantees a lack of starvation but introduces at the same time the problem that the thread priority is not taken into account and therefore threads with lower priority that often wait at this barrier may be executed more often. Last but not least the ReentrantLock class can of course only consider threads that are waiting for the lock, i.e. threads that have been executed often enough to reach the lock. If thread priority is too low this may not often happen and therefore threads with higher priority still pass the lock more often.
2. Object monitors with wait() and notify()
A common task in multi-threaded computing is to have some worker threads that are waiting for their producer to create some work for them. But as we have learned, busy waiting within a loop and checking some value is not a good option in terms of CPU time. In this use case the Thread.sleep() method is also not of much value, as we want to start our work immediately after it has been submitted.
The Java Programming Language therefore has another construct, that can be used in this scenario: wait() and notify(). The wait() method that every object inherits from the java.lang.Object class can be used to pause the current thread execution and wait until another threads wakes us up using the notify() method. In order to work correctly, the thread that calls the wait() method has to hold a lock that it has acquired before using the synchronized keyword. When calling wait() the lock is released and the threads waits until another thread that now owns the lock calls notify() on the same object instance.
In a multi-threaded application there may of course be more than one thread waiting on some object to be notified. Hence there are two different methods to wake up threads: notify() and notifyAll(). Whereas the first method only wakes up one of the waiting threads, the notifyAll() methods wakes them all up. But be aware that similar to the synchronized keyword there is no rule that specifies which thread to wake up next when calling notify(). In a simple producer and consumer example this does not matter, as we are not interested in the fact which thread exactly wakes up.
The following code demonstrates how the wait() and notify() mechanism can be used to let the consumer threads wait for new work that is pushed into a queue from some producer thread:
package a2;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class ConsumerProducer {
private static final Queue queue = new ConcurrentLinkedQueue();
private static final long startMillis = System.currentTimeMillis();
public static class Consumer implements Runnable {
public void run() {
while (System.currentTimeMillis() < (startMillis + 10000)) {
synchronized (queue) {
try {
queue.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if (!queue.isEmpty()) {
Integer integer = queue.poll();
System.out.println("[" + Thread.currentThread().getName() + "]: " + integer);
}
}
}
}
public static class Producer implements Runnable {
public void run() {
int i = 0;
while (System.currentTimeMillis() < (startMillis + 10000)) {
queue.add(i++);
synchronized (queue) {
queue.notify();
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
synchronized (queue) {
queue.notifyAll();
}
}
}
public static void main(String[] args) throws InterruptedException {
Thread[] consumerThreads = new Thread[5];
for (int i = 0; i < consumerThreads.length; i++) {
consumerThreads[i] = new Thread(new Consumer(), "consumer-" + i);
consumerThreads[i].start();
}
Thread producerThread = new Thread(new Producer(), "producer");
producerThread.start();
for (int i = 0; i < consumerThreads.length; i++) {
consumerThreads[i].join();
}
producerThread.join();
}
}The main() method starts five consumer and one producer thread and then waits for them to finish. The producer thread then inserts a new value into the queue and afterwards notifies all waiting threads that something has happened. The consumer threads acquire the queue lock and then fall asleep in order to be woken up later on when the queue is filled again. When the producer thread has finished its work, it notifies all consumer threads to wake up. If we won’t do the last step, the consumer threads would wait forever for the next notification, as we haven’t specified any timeout for the waiting. Instead we could have used the method wait(long timeout) to be woken up at least after some amount of time has passed by.
2.1. Nested synchronized blocks with wait() and notify()
As mentioned in the last section, calling wait() on an object monitor only frees the lock on this object monitor. Other locks which are being hold by the same thread are not freed. As this is easy to understand, it may happen in day-to-day work that the thread that calls wait() holds further locks. And if other threads are also waiting for these locks a deadlock situation can happen. Let’s have a look at the following example code:
public class SynchronizedAndWait {
private static final Queue queue = new ConcurrentLinkedQueue();
public synchronized Integer getNextInt() {
Integer retVal = null;
while (retVal == null) {
synchronized (queue) {
try {
queue.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
retVal = queue.poll();
}
}
return retVal;
}
public synchronized void putInt(Integer value) {
synchronized (queue) {
queue.add(value);
queue.notify();
}
}
public static void main(String[] args) throws InterruptedException {
final SynchronizedAndWait queue = new SynchronizedAndWait();
Thread thread1 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i < 10; i++) {
queue.putInt(i);
}
}
});
Thread thread2 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i < 10; i++) {
Integer nextInt = queue.getNextInt();
System.out.println("Next int: " + nextInt);
}
}
});
thread1.start();
thread2.start();
thread1.join();
thread2.join();
}
}As we have learned before, adding synchronized to the method signature is equal to creating a synchronized(this){} block. In the example above we have accidentally added the synchronized keyword to the method and afterwards synchronized on the object monitor queue in order to put the current thread into sleep while waiting for the next value from the queue. The current thread then releases the lock hold on queue but not the lock hold on this. The putInt() method notifies the sleeping thread that a new value has been added. But accidentally we have also added the keyword synchronized to this method. When now the second thread has fallen asleep, it still holds the lock. The first thread can then not enter the method putInt() as the this lock is hold by the first thread. Hence we have a deadlock situation and the program hangs. If you execute the code above, this happens right after the beginning of the program.
In everyday life the situation may not be as clear as above. The locks a thread holds may depend on runtime parameter and conditions and the synchronized block causing the problem may not be that near to the place in the code, where we put the wait() call. This makes it difficult to find such problems and if may be that these problems only appear after some time or under heavy load.
2.2. Conditions in synchronized blocks
Often you will have to check that some condition is fulfilled, before you execute some action on a synchronized object. When you have for example a queue you want to wait until this queue is filled. Hence you can write a method that checks if the queue is filled. If not you put the current thread asleep until it is woken up:
public Integer getNextInt() {
Integer retVal = null;
synchronized (queue) {
try {
while (queue.isEmpty()) {
queue.wait();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
synchronized (queue) {
retVal = queue.poll();
if (retVal == null) {
System.err.println("retVal is null");
throw new IllegalStateException();
}
}
return retVal;
}The code above synchronizes on the queue before calling wait() and then waits within the while loop until the queue has at least one entry. The second synchronized block again uses the queue as object monitor. It polls() the queue for the value inside. For demonstration purposes an IllegalStateException is thrown when poll() returns null. This is the case when there are no values inside the queue to poll.
When you run this example, you will see that the IllegalStateException is thrown very soon. Although we have correctly synchronized on the queue monitor, the exception is thrown. The reason here is that we have two separate synchronized blocks. Imagine we have two threads that have arrived at the first synchronized block. The first thread enters the block and falls asleep because the queue is empty. The same is true for the second thread. Now when both threads wake up (by another thread calling notifyAll() on the monitor), they both see a value in the queue (the one added by the producer. Then both threads arrive at the second barrier. Here the first thread enters and polls the value from the queue. When the second thread enters, the queue is already empty. Hence it gets null as return value from the poll() call and throws the exception.
To avoid situations like the one above, you will have to execute all operations that depend on the monitor’s state in the same synchronized block:
public Integer getNextInt() {
Integer retVal = null;
synchronized (queue) {
try {
while (queue.isEmpty()) {
queue.wait();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
retVal = queue.poll();
}
return retVal;
}Here we execute the method poll() in the same synchronized block as the isEmpty() method. Through the synchronized block we are sure that only one thread is executing methods on this monitor at a given point in time. Hence no other thread can remove elements from the queue between the isEmpty() and the poll() call.
3. Designing for multi-threading
As we have seen in the last sections, implementing a multi-threading application is sometimes more complex than it might look at first glance. Therefore it is important to have a clear design in mind when starting the project.
3.1. Immutable object
One design rule that is considered to be very important in this context is Immutability. If you share object instances between different threads you have to pay attention that two threads do not modify the same object simultaneously. But objects that are not modifiable are easy to handle in such situations as you cannot change them. You always have to construct a new instance when you want to modify the data. The basic class java.lang.String is an example of an immutable class. Every time you want to change a string, you get a new instance:
String str = "abc"; String substr = str.substring(1);
Although object creation is an operation that does not come without costs, these costs are often overestimated. But you always have to weight out if a simple design with immutable objects outweighs to not use immutable objects with the risk of concurrency errors that are observed maybe very late in the project.
In the following you will find a set of rules to apply when you want to make a class immutable:
- All fields should be final and private.
- There should be not setter methods.
- The class itself should be declared final in order to prevent subclasses to violate the principle of immutability.
- If fields are not of a primitive type but a reference to another object:
- There should not be a getter method that exposes the reference directly to the caller.
- Don’t change the referenced objects (or at least changing these references is not visible to clients of the object).
Instances of the following class represent a message with subject, message body and a few key/value pairs:
public final class ImmutableMessage {
private final String subject;
private final String message;
private final Map<String,String> header;
public ImmutableMessage(Map<String,String> header, String subject, String message) {
this.header = new HashMap<String,String>(header);
this.subject = subject;
this.message = message;
}
public String getSubject() {
return subject;
}
public String getMessage() {
return message;
}
public String getHeader(String key) {
return this.header.get(key);
}
public Map<String,String> getHeaders() {
return Collections.unmodifiableMap(this.header);
}
}The class is immutable as all of its fields are final and private. There are no methods that would be able to modify the state of an instance after its construction. Returning the references to subject and message is safe, as String itself is an immutable class. The caller who obtains a reference for example to the message cannot modify it directly. With the Map of headers we have to pay more attention. Just returning the reference to the Map would allow the caller to change its content. Hence we have to return an unmodifiable Map acquired through a call of Collections.unmodifiableMap(). This returns a view on the Map that allows callers to read the values (which are strings again), but which does not allow modifications. An UnsupportedOperationException will be thrown when trying to modify the Map instance. In this example it is also safe to return the value for a specific key, like it is done within getHeader(String key), as the returned String is immutable again. If the Map would contain objects that are not immutable themselves, this operation would not be thread-safe.
3.2. API design
When designing the public methods of a class, i.e. the API of this class, you can also try to design it for multi-threaded usage. You might have methods that should not be executed when the object is within a certain state. One simple solution to overcome this situation would be to have a private flag, which indicate in which state we are and throws for example an IllegalStateException when a specific method should not be called:
public class Job {
private boolean running = false;
private final String filename;
public Job(String filename) {
this.filename = filename;
}
public synchronized void start() {
if(running) {
throw new IllegalStateException("...");
}
...
}
public synchronized List getResults() {
if(!running) {
throw new IllegalStateException("...");
}
...
}
}The above pattern is also often referred to as “balking pattern”, as the method balks once it gets executed in the wrong state. But you could have designed the same functionality using a static factory method without checking in each method the state of the object:
public class Job {
private final String filename;
private Job(String filename) {
this.filename = filename;
}
public static Job createAndStart(String filename) {
Job job = new Job(filename);
job.start();
return job;
}
private void start() {
...
}
public synchronized List getResults() {
...
}
}The static factory method creates a new instance of Job using the private constructor and already calls start() on the instance. The returned reference of Job is already in the correct state to work with, hence the getResults() method only needs to be synchronized but does not have to check for the state of the object.
3.3. Thread local storage
We have seen so far that threads share the same memory. In terms of performance this is a good way to share data between the threads. If we would have used separate processes in order to execute code in parallel, we would have more heavy data exchange methods, like remote procedure calls or synchronization on file system or network level. But sharing memory between different threads is also difficult to handle if not synchronized properly.
Dedicated memory that is only used by our own thread and not by other threads is provided in Java through the java.lang.ThreadLocal class:
private static final ThreadLocal myThreadLocalInteger = new ThreadLocal();
The type of data that should be stored within the ThreadLocal is given by the generic template parameter T. In the example above we used just Integer, but we could have used any other data type here as well. The following code demonstrates the usage of ThreadLocal:
public class ThreadLocalExample implements Runnable {
private static final ThreadLocal threadLocal = new ThreadLocal();
private final int value;
public ThreadLocalExample(int value) {
this.value = value;
}
@Override
public void run() {
threadLocal.set(value);
Integer integer = threadLocal.get();
System.out.println("[" + Thread.currentThread().getName() + "]: " + integer);
}
public static void main(String[] args) throws InterruptedException {
Thread threads[] = new Thread[5];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(new ThreadLocalExample(i), "thread-" + i);
threads[i].start();
}
for (int i = 0; i < threads.length; i++) {
threads[i].join();
}
}
}You may wonder that each thread outputs exactly the value that it gets through the constructor although the variable threadLocal is declared static. ThreadLocal’s internal implementation makes sure that every time you call set() the given value is stored within a memory region that only the current thread has access to. Hence when you call afterwards get() you retrieve the value you have set before, despite the fact that in the meantime other threads may have called set().
Application servers in the Java EE world make heavy usage of the ThreadLocal feature as you have many parallel threads but each thread has for example its own transaction or security context. As you don’t want to pass these objects within each method invocation, you simply store it in the thread’s own memory and access it later when you need it.
Hello! Thank you for this tutorial.
I’ve got a question under subsection 2.1.
Should the sentence
‘The first thread can then not enter the method putInt() as the this lock is hold by the (first) thread’
be read as follows
‘The first thread can then not enter the method putInt() as the this lock is hold by the (second) thread’?
Hello Sergey,
you are right. It should be “hold by the second thread”.
ThreadLocal is very tempting, but wondering what “clean code” folks have to say about it. The example I’m looking at is related to logging. I’d like to stash some logging context information in a thread local. This would significantly clean up our code base where almost every class has some boiler plate to deal with the logging context. My concern is that ThreadLocal breaks some dependency injection rules and in a way acts like a global variable.
Would be interested to hear what others have to say…