A race is when two (or more) threads try to work with shared data, and the final result depends on the order of access to the data (and this order is uncertain)
From Wikipedia:
A race condition or racial danger is a defect in an electronic system or process, as a result of which the result and / or result of the process unexpectedly and critically depends on the sequence or time of other events. This term is associated with the idea of two signals that drive each other to influence the output in the first place.
For instance:
public class Test { private static List<String> list = new CopyOnWriteArrayList<String>(); public static void main(String[] args) throws Exception { ExecutorService e = Executors.newFixedThreadPool(5); e.execute(new WriterTask()); e.execute(new WriterTask()); e.execute(new WriterTask()); e.execute(new WriterTask()); e.execute(new WriterTask()); e.awaitTermination(20, TimeUnit.SECONDS); } static class WriterTask implements Runnable { @Override public void run() { for (int i = 0; i < 25000; i ++) { list.add("a"); } } } }
This, however, fails when using ArrayList , with ArrayIndexOutOfbounds . This is because ensureCapacity(..) should be called before insertion to ensure that the internal array can store new data. And here is what happens:
- the first thread calls
add(..) , which in turn calls ensureCapacity(currentSize + 1) - before the first thread actually
ensureCapacity(currentSize + 1) in size, the second thread also calls ensureCapacity(currentSize + 1) . - since both reads the initial value of
currentSize , the new size of the internal array is currentSize + 1 - two threads do an expensive operation by copying the old array to the expanded one, with a new size (which cannot contain both additions)
- Then each of them tries to assign a new element to
array[size++] . The first of them was completed successfully, the second failed because the internal array was not expanded properly due to the reception condition.
This happens because two threads tried to add elements at the same time to the same structure, and adding one of them overridden adding the other (i.e. the first was lost)
Another advantage of CopyOnWriteArrayList
- multiple threads are written to an
ArrayList - the thread iterates through an
ArrayList . It will definitely get a ConcurrentModificationException
Here's how to demonstrate it:
public class Test { private static List<String> list = new ArrayList<String>(); public static void main(String[] args) throws Exception { ExecutorService e = Executors.newFixedThreadPool(2); e.execute(new WriterTask()); e.execute(new ReaderTask()); } static class ReaderTask implements Runnable { @Override public void run() { while (true) { for (String s : list) { System.out.println(s); } } } } static class WriterTask implements Runnable { @Override public void run() { while(true) { list.add("a"); } } } }
If you run this program several times, you often get a ConcurrentModificationException before you get an OutOfMemoryError .
If you replace it with CopyOnWriteArrayList , you will not get an exception (but the program is very slow)
Please note that this is just a demonstration. The advantage of CopyOnWriteArrayList is that the number of files read far exceeds the number of records.