Atomicity is one of the key concepts in multi-threaded programs. We say a set of actions is atomic if they all execute as a single operation, in an indivisible manner. Taking for granted that a set of actions in a multi-threaded program will be executed serially may lead to incorrect results. The reason is due to thread interference, which means that if two threads execute several steps on the same data, they may overlap.
The following Interleaving example shows two threads executing several actions (prints in a loop) and how they are overlapped:
When executed, it will produce unpredictable results. As an example:
Thread 2 - Number: 0
Thread 2 - Number: 1
Thread 2 - Number: 2
Thread 1 - Number: 0
Thread 1 - Number: 1
Thread 1 - Number: 2
Thread 1 - Number: 3
Thread 1 - Number: 4
Thread 2 - Number: 3
Thread 2 - Number: 4
In this case, nothing wrong happens since they are just printing numbers. However, when you need to share the state of an object (its data) without synchronization, this leads to the presence of race conditions.
Race condition
Your code will have a race condition if there’s a possibility to produce incorrect results due to thread interleaving. This section describes two types of race conditions:
- Check-then-act
- Read-modify-write
To remove race conditions and enforce thread safety, we must make these actions atomic by using synchronization. Examples in the following sections will show what the effects of these race conditions are.
Check-then-act race condition
This race condition appears when you have a shared field and expect to serially execute the following steps:
- Get a value from a field.
- Do something based on the result of the previous check.
The problem here is that when the first thread is going to act after the previous check, another thread may have interleaved and changed the value of the field. Now, the first thread will act based on a value that is no longer valid. This is easier seen with an example.
UnsafeCheckThenAct is expected to change the field number once. Following calls to changeNumber method, should result in the execution of the else condition:
But since this code is not synchronized, it may (there's no guarantee) result in several modifications of the field:
T13 | Changed
T17 | Changed
T35 | Not changed
T10 | Changed
T48 | Not changed
T14 | Changed
T60 | Not changed
T6 | Changed
T5 | Changed
T63 | Not changed
T18 | Not changed
Another example of this race condition is lazy initialization.
A simple way to correct this is to use synchronization.
SafeCheckThenAct is thread-safe because it has removed the race condition by synchronizing all accesses to the shared field.
Now, executing this code will always produce the same expected result; only a single thread will change the field:
T0 | Changed
T54 | Not changed
T53 | Not changed
T62 | Not changed
T52 | Not changed
T51 | Not changed
...
In some cases, there will be other mechanisms which perform better than synchronizing the whole method but I won’t discuss them in this post.
Read-modify-write race condition
Here we have another type of race condition which appears when executing the following set of actions:
- Fetch a value from a field.
- Modify the value.
- Store the new value to the field.
In this case, there’s another dangerous possibility which consists in the loss of some updates to the field. One possible outcome is:
Field’s value is 1.
Thread 1 gets the value from the field (1).
Thread 1 modifies the value (5).
Thread 2 reads the value from the field (1).
Thread 2 modifies the value (7).
Thread 1 stores the value to the field (5).
Thread 2 stores the value to the field (7).
As you can see, update with the value 5 has been lost.
Let’s see a code sample. UnsafeReadModifyWrite shares a numeric field which is incremented each time:
Can you spot the compound action
which causes the race condition?
I’m sure you did, but for completeness, I will explain it anyway. The problem is in the increment (number++). This may appear to be a single action but in fact, it is a sequence of three actions (get-increment-write).
When executing this code, we may see that we have lost some updates:
2014-08-08 09:59:18,859|UnsafeReadModifyWrite|Final number (should be 10_000): 9996
Depending on your computer it will be very difficult to reproduce this update loss, since there’s no guarantee on how threads will interleave. If you can’t reproduce the above example, try UnsafeReadModifyWriteWithLatch, which uses a CountDownLatch to synchronize thread’s start, and repeats the test a hundred times. You should probably see some invalid values among all the results:
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
Final number (should be 1_000): 997
Final number (should be 1_000): 999
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
Final number (should be 1_000): 1000
This example can be solved by making all three actions atomic.
SafeReadModifyWriteSynchronized uses synchronization in all accesses to the shared field:
Let’s see another example to remove this race condition. In this specific case, and since the field number is independent to other variables, we can make use of atomic variables. SafeReadModifyWriteAtomic uses atomic variables to store the value of the field:
Following posts will further explain mechanisms like locking or atomic variables.
Conclusion
This post explained some of the risks implied when executing compound actions in non-synchronized multi-threaded programs. To enforce atomicity and prevent thread interleaving, one must use some type of synchronization.
This post is part of the Java Concurrency Tutorial series. Check here to read the rest of the tutorial.
You can take a look at the source code at github.
I'm publishing my new posts on Google plus and Twitter. Follow me if you want to be updated with new content.
Labels: Concurrency, Core, Java