What does thread safety mean in Java?

November 27, 2019

Category: The package java.util.concurrent.atomic

Thread safety in java means that the methods of a class are either atomic or quiescent. So what does atomic and what does quiescent mean? And why are there no other types of thread-safe methods in java?

Meaning of Atomic

A method is atomic when the method call appears to take effect instantaneously. So other threads either see the state before or after the method call but no intermediate state. Let us look at a non-atomic method to see how an atomic method makes a class thread-safe. You can download the source code of all examples from GitHub here.

public class UniqueIdNotAtomic {
	private volatile long counter = 0;
	public  long nextId() {	
		return counter++;	
	}	
}

The class UniqueIdNotAtomic creates unique ids by using the volatile variable counter. I use a volatile field, line 2, to make sure that the threads always see the current values, as explained in greater detail here. To see if this class is thread-safe we use the following test:

public class TestUniqueIdNotAtomic {
	private final UniqueIdNotAtomic uniqueId = new UniqueIdNotAtomic();
	private long firstId;
	private long secondId;
	private void updateFirstId() {
		firstId  = uniqueId.nextId();
	}
	private void updateSecondId() {
		secondId = uniqueId.nextId();
	}
	@Test
	public void testUniqueId() throws InterruptedException {	
		try (AllInterleavings allInterleavings = 
			    new AllInterleavings("TestUniqueIdNotAtomic");) {
		while(allInterleavings.hasNext()) {	
		Thread first = new Thread( () ->   { updateFirstId();  } ) ;
		Thread second = new Thread( () ->  { updateSecondId();  } ) ;
		first.start();
		second.start();
		first.join();
		second.join();	
		assertTrue(  firstId != secondId );
		}
		}
	}

}

To test if the counter is thread-safe we need two threads, created in lines 16 and 17. We start those two threads, lines 18 and 19. And then wait till both are ended using thread join, lines 20 and 21. After both threads are stopped we check if the two ids are unique line 22. To test all thread interleavings we put the complete test in a while loop iterating over all thread interleavings using the class AllInterleavings from vmlens, line 15.

Running the test we see the following error:

java.lang.AssertionError: 
	at org.junit.Assert.fail(Assert.java:91)
	at org.junit.Assert.assertTrue(Assert.java:43)

The reason for the error is that since the operation ++ is not atomic the two threads can override the result of the other thread. We can see this in the report from vmlens:

In the case of the error, both threads first read the variable counter in parallel. And then both create the same id. To solve this problem we make the method atomic by using a synchronized block:

private final Object LOCK = new Object();
public  long nextId() {
  synchronized(LOCK) {
    return counter++;	
  }	
}

Now the method is atomic. The synchronized block makes sure that other threads can not see the intermediate state of the method.

Methods which do not access shared state are automatically atomic. The same is true for classes with read-only state. Therefore stateless and immutable classes are an easy way to implement thread-safe classes. All their methods are automatically atomic.

Not all usages of atomic methods are automatically thread safe. Combining multiple atomic methods for the same values typical leads to race conditions. Let us look at the atomic method get and put from ConcurrentHashMap to see why. Let us use those methods to insert a value in the map when no previous mapping exists:

public class TestUpdateTwoAtomicMethods {
	public void update(ConcurrentHashMap<Integer,Integer>  map)  {
			Integer result = map.get(1);		
			if( result == null )  {
				map.put(1, 1);
			}
			else	{
				map.put(1, result + 1 );
			}	
	}
	@Test
	public void testUpdate() throws InterruptedException	{
		try (AllInterleavings allInterleavings = 
		   new AllInterleavings("TestUpdateTwoAtomicMethods");) {
		while(allInterleavings.hasNext()) {	
		final ConcurrentHashMap<Integer,Integer>  map = 
		   new  ConcurrentHashMap<Integer,Integer>();	
		Thread first = new Thread( () ->   { update(map);  } ) ;
		Thread second = new Thread( () ->  { update(map);  } ) ;
		first.start();
		second.start();
		first.join();
		second.join();	
		assertEquals( 2 , map.get(1).intValue() );
		}
		}
	}	
}

The test is similar to the previous test. Again we use two threads, to test if our method is thread-safe, lines 18 and 19. An again we test after both threads finished if the result is correct, line 24. Running the test we see the following error:

java.lang.AssertionError: expected:<2> but was:<1>
	at org.junit.Assert.fail(Assert.java:91)
	at org.junit.Assert.failNotEquals(Assert.java:645)

The reason for the error is that the combination of the two atomic methods, get and put is not atomic. So the two threads can override the result of the other thread. We can see this in the report from vmlens:

In the case of the error, both threads first get the value in parallel. And then both create the same value and put it into the map. To solve this race condition we need to use one method instead of two. In our case we can use the single method compute instead of the two methods get and put:

public void update() {
  map.compute(1, (key, value) -> {
	if (value == null) {
		return 1;
	} 
	return value + 1;
  });
}

This solves the race condition since the method compute is atomic. While all operations which operate on the same element of ConcurrentHashMap are atomic, operations that operate on the complete map like size are quiescent. So let us see what quiescent means.

Meaning of Quiescent

Quiescent means that we need to make sure that no other methods are currently running when we call the quiescent method. The following example shows how to use the quiescent method size of the ConcurrentHashMap:

ConcurrentHashMap<Integer,Integer>  map = 
	new  ConcurrentHashMap<Integer,Integer>();
Thread first  = new Thread(() -> { map.put(1,1);});
Thread second = new Thread(() -> { map.put(2,2);});
first.start();
second.start();
first.join();
second.join();	
assertEquals( 2 ,  map.size());

By waiting till all threads are finished using thread join, we make sure that no other threads are accessing the ConcurrentHashMap when we call the method size.

The method size uses a mechanism also used in the class java.util.concurrent.atomic.LongAdder, LongAccumulator, DoubleAdder, and DoubleAccumulator to avoid contention. Instead of using a single variable for storing the current size it uses an array. Different threads update different parts of the array thereby avoiding contention. The algorithm is explained in more detail in the java doc of Striped64

The quiescent classes and methods are useful for collecting statistics under high contention. After you collected the data you can use a single thread to evaluate the collected statistics.

Why no other types of thread safe methods in java?

In theoretical computer science, thread safety means that a data structure full fills a correctness criterion. The most common used correctness criterion is linearizable, which means that the methods of the data structure are atomic. For common data structures exists a provable linearizable concurrent data structures, see the book The Art of multiprocessor programming by Maurice Herlihy and Nir Shavit. But to make a data structure linearizable an expensive synchronization mechanism like compare and swap is needed, see the paper Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated.

Therefore other correctness criteria like quiescent are investigated. So I think the question is not, why are there no other types of thread-safe methods in java but rather when will there be other types of thread safety available in java.

Conclusion

Thread safety in java means that the methods of a class are either atomic or quiescent. A method is atomic when the method call appears to take effect instantaneously. Quiescent means that we need to make sure that no other methods are currently running when we call the quiescent method.

Currently, quiescent methods are only used to collect statistics like the size of the concurrentHashMap. For all other use cases atomic methods are used. Let us see if the future brings other types of thread-safe methods.

Make your application thread safe

LEARN MORE