How many problems can you spot in this simple code?
Let’s try to create a program that runs ten threads and every thread adds a thousand numbers to the list. Here is our client code where we spawn threads:
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < 10 ; i++ ) {
Thread thread = new Thread(new AddNumbersJob(list));
thread.start();
}
System.out.println(list);
}
}
And our thread that adds numbers to the list:
public class AddNumbersJob implements Runnable {
private final List<Integer> numbers;
public AddNumbersJob(List<Integer> numbers) {
this.numbers = numbers;
}
@Override
public void run() {
for ( int i = 0 ; i < 1000 ; i++ ) {
numbers.add(i);
}
}
}
Pause and try to find as many code smells and bugs and think about how would you resolve them. Now, let’s resolve those problems. If you run this code you will end up with this exception:
Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.base/java.util.ArrayList$Itr.next(Unknown Source)
at java.base/java.util.AbstractCollection.toString(Unknown Source)
at java.base/java.lang.String.valueOf(Unknown Source)
at java.base/java.io.PrintStream.println(Unknown Source)
at com.Main.main(Main.java:39)
Java throws this exception when you try to modify the list while iterating through it.. You may think “But I am not iterating through my list, I am not using an iterator to fetch elements from the list”. The answer is that System.out.println called toString method of the list. The implementation of the toString method in the AbstractCollection class iterates.
Let’s give some time to those adding threads to finish their work so that we can print elements when the list contains all elements. You might be tempted to call Thread.sleep(2000) method but this is the wrong way. You cannot be sure that threads will finish their work in two seconds. This is also inefficient because threads will likely add a thousand elements in just a few milliseconds. The point is that hardcoding this number is a bad idea). A good way to solve this problem is by calling thread.join(). The main thread won’t proceed until the thread on which the join method is called is not done. It is important to remember that simple fact about the join method!
IMPORTANT: Don’t do this
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < 10 ; i++ ) {
Thread thread = new Thread(new AddNumbersJob(list));
thread.start();
thread.join();
}
System.out.println(list);
}
}
This way, you essentially create a single-threaded application. When you call the join method in the first iteration, you cannot proceed to the second iteration while your thread from the first iteration is not over. It is obvious that in that scenario only one of those ten threads is doing a job simultaneously. That is not what we intended in the first place. This is the way to go:
public class Main {
public static void main(String[] args) {
List<Thread> threads = new ArrayList<>();
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < 10 ; i++ ) {
Thread thread = new Thread(new AddNumbersJob(list), "Thread " + i);
thread.start();
threads.add(thread);
}
threads.forEach(thread -> {
try {
thread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
System.out.println(list.size());
}
}
You are not receiving ConcurrentModificationException but your list contains a different number of elements every time you run your program. Your problem is that your program contains race condition.
What is a race condition?
The problem is that multiple threads are trying to write to the same memory location at the same time. In our case, we share the list between two threads. One thread overrides changes of the other thread. Let me explain the race condition problem with the picture. Race condition is the most basic and most important problem in multithreading!
Firstly, it is important to say that Java keeps all objects in the heap memory(main memory/ RAM memory). Also important is that every single thread is spawned in the different cores of the CPU. For example, if you have a CPU that has 4 cores then you can run at most 4 threads in parallel! Every single core has a mini cache memory bound to that core. That means that thread one cannot read data from the cache memory of thread two. Let’s get back to the picture and explain the steps:
- Step 1: Thread one reads the list from the main memory and puts that list inside thread cache memory(let’s say that at the beginning the list contained 10 elements)
- Step 2: After thread one finished reading from the main memory, thread two read the list from the memory and put the list in its own cache memory. This read happens after the thread one read but before thread one finishes updating the list and writes that list back to the main memory.
- Step 3: Thread one internally(inside its cache memory) update the list and the list now has 11 elements.
- Step 4: Thread two internally(inside its cache memory) updates the list and the list now has 11 elements
- Step 5: Thread one flush list changes from the cache memory to the main memory. Now the list in the main memory has 11 elements.
- Step 6: Thread two flushes list changes from the cache memory to the main memory. Now the list in the main memory has 11 elements.
The result is that we started with 10 elements in the list and ended up with 11 elements. Our expectations were that both threads added one element so that at the end list contains 12 elements.
How to solve race condition?
There are two ways how to prevent this. Introduce a synchronized block or switch our list from ArrayList to some list implementation that is doing synchronization internally.
First solution(introduce synchronized block):
public class AddNumbersJob implements Runnable {
private final List<Integer> numbers;
public AddNumbersJob(List<Integer> numbers) {
this.numbers = numbers;
}
@Override
public void run() {
for ( int i = 0 ; i < 1000 ; i++ ) {
synchronized (numbers) {
numbers.add(i);
}
}
}
}
Entering a synchronized block means that the thread will acquire a lock before entering that block of code(it will acquire a lock on the object numbers). Thread will release a lock when it exits the synchronized block. In the meantime, no other threads can acquire the same lock meaning that the race condition problem won’t happen!
Second solution(change implementation of the list):
public class AddNumbersJob implements Runnable {
private final List<Integer> numbers;
public AddNumbersJob(List<Integer> numbers) {
this.numbers = numbers;
}
@Override
public void run() {
for ( int i = 0 ; i < 1000 ; i++ ) {
numbers.add(i);
}
}
}
Note: You don’t need a synchronized block in the second solution. The list that is returned with this static method Collections.synchronizedList(new ArrayList<>()); is doing synchronization inside it’s own implementation(if you open that list implementation you can find synchronized blocks, etc.)
public class Main {
public static void main(String[] args) {
List<Thread> threads = new ArrayList<>();
List<Integer> list = Collections.synchronizedList(new ArrayList<>());
for(int i = 0 ; i < 10 ; i++ ) {
Thread thread = new Thread(new AddNumbersJob(list), "Thread " + i);
thread.start();
threads.add(thread);
}
threads.forEach(thread -> {
try {
thread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
System.out.println(list.size());
}
}
You can also try to add the number to the list just if the number is not present. synchronizedList doesn’t work in that case, you have to use a synchronized block:
synchronized (numbers) {
if(!numbers.contains(i)) {
numbers.add(i);
}
}
Bonus: Since you learned about synchronized block take a look at this article to see how things can go wrong even when you use synchronization.
Further reading
If this article was interesting to you, here are some great resources on the multithreading topic: