Tuesday, February 12, 2013

The frightening and shocking history of concurrency

    Some time ago I was a participant of the Java conference. That time one of the speaker said that about 80-90% (I do not remember the exact value) of multi threaded code was synchronized wrongly and the rest of the code had not yet been proven to be synchronized wrongly.
It is a little shocking but I believe it could be true. As an object of the investigation I would like to present a small piece of code:
public class SequenceGenerator {
 private int counter = 0;

 public int getNext() {
  return counter++;
It looks potentially harmless. Yes, indeed, it is harmless in a single-thread environment. However, when it comes to threads - very little is guaranteed. I decided to test that piece of code against race condition. I used TestNG framework as it allows to execute tests concurrently. If you use Maven you can add the following dependency to your pom.xml:
I wrote the test:
import static org.testng.Assert.assertFalse;

import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;

import org.testng.annotations.Test;

public class SequenceGeneratorTest {
 private Collection generatedValues = Collections.synchronizedList(new LinkedList());
 private SequenceGenerator sequenceGenerator = new SequenceGenerator();
 @Test(threadPoolSize = 200, invocationCount = 2000)
 public void shouldTestThreadSafety() {
  int nextValue = sequenceGenerator.getNext();
  assertFalse(generatedValues.contains(nextValue), "Generated value is not unique!");
After executing  'mvn clean test' the method 'shouldTestThreadSafety' was invoked 2000 times by 200 threads concurrently. I triggered the tests three times and everything worked fine. During the fourth execution something went wrong:
 T E S T S
Running SequenceGeneratorTest
Configuring TestNG with: org.apache.maven.surefire.testng.conf.TestNG652Configurator@535bab52
Tests run: 2000, Failures: 1, Errors: 0, Skipped: 0, Time elapsed: 29.437 sec <<< FAILURE!
testThreadSafety(SequenceGeneratorTest)  Time elapsed: 0.001 sec  <<< FAILURE!
java.lang.AssertionError: Generated value is not unique! expected [false] but found [true]
 at org.testng.Assert.fail(Assert.java:94)
 at org.testng.Assert.failNotEquals(Assert.java:494)
 at org.testng.Assert.assertFalse(Assert.java:63)
 at SequenceGeneratorTest.testThreadSafety(SequenceGeneratorTest.java:21)

Results :

Failed tests:   testThreadSafety(SequenceGeneratorTest): Generated value is not unique!

Tests run: 2000, Failures: 1, Errors: 0, Skipped: 0

The reason for that is the fact that i++ operation is not atomic. It consists of three operations:
1). reading the original value,
2). incrementing the value,
3). assigning incremented value.

Between those operations Thread Scheduler can transfer the thread from running to runnable state. Let's imagine the scenario:

ThreadA is put into running state
ThreadA reads original value - 0
ThreadA is put into runnable state
ThreadB is put into running state
ThreadB reads original value - 0 !!!
ThreadB increments the value
ThreadB assigns the value - 1
ThreadA is put into running state
ThreadA increments the value
ThreadA assigns the value - 1 !!!

As you can see the scenario is quite real. The simplest solution is to use java.util.concurrent.AtomicInteger instead of int or synchronizing 'getNext' method.
It should give you some insight into concurrent problems. The application can work fine for a long time, but one day it can crash because of a race condition. Those kinds of bugs are extremely hard to find. Stay focused and keep your code well synchronized.

No comments :

Post a Comment