Data race in Java ArrayList class

Question

I was reading about CopyOnWriteArrayList and was wondering how can I demonstrate data race in ArrayList class. Basically I'm trying to simulate a situation where ArrayList fails so that it becomes necessary to use CopyOnWriteArrayList. Any suggestions on how to simulate this.

Answer 1

A race is when two (or more) threads try to operate on shared data, and the final output depends on the order the data is accessed (and that order is indeterministic)

From Wikipedia:

A race condition or race hazard is a flaw in an electronic system or process whereby the output and/or result of the process is unexpectedly and critically dependent on the sequence or timing of other events. The term originates with the idea of two signals racing each other to influence the output first.

For example:

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. That's because before insertion the ensureCapacity(..) should be called to make sure the internal array can hold the new data. And here's what happens:

• the first thread calls add(..), which in turn calls ensureCapacity(currentSize + 1)
• before the first thread has actually incremented the size, the 2nd thread also calls ensureCapacity(currentSize + 1).
• because both have read the initial value of currentSize, the new size of the internal array is currentSize + 1
• the two threads make the expensive operation to copy the old array into the extended one, with the new size (which cannot hold both additions)
• Then each of them tries to assign the new element to array[size++]. The first one succeeds, the second one fails, because the internal array has not been expanded properly, due to the rece condition.

This happens, because two threads have tried to add items at the same time on the same structure, and the addition of one of them has overridden the addition of the other (i.e. the first one was lost)

Another benefit of CopyOnWriteArrayList

• multiple threads write to the ArrayList
• a thread iterates the ArrayList. It will surely get 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 multiple times, you will often be getting ConcurrentModificationException before you get OutOfMemoryError.

If you replace it with CopyOnWriteArrayList, you don't get the exception (but the program is very slow)

Note that this is just a demonstration - the benefit of CopyOnWriteArrayList is when the number of reads vastly outnumbers the number of writes.