How can I achieve the safe read/write concurrency on an ArrayList?

Question

My application is designed the following way:

1. Data is continuously appended to an ArrayList (by multiple writes)
2. Data is read from the beginning of the list (guaranteed to be before the indexes affected by the current writes) by reader threads.

Is there a thread safe way to implement it so that:

• Writer threads are blocking each other when writing (to avoid write concurrency issues)

• Reader threads aren't blocked when either other readers read

• Reader threads aren't blocked when writer threads append to the end

  I am making an assumption here that merely writing to the end of ArrayList is thread safe for the reader of the array's start

• However, read threads are blocked when writing cases some operation that would make reading thread unsafe - such reallocating full array data if the array runs out of allocated memory during an append.

  I am making an assumption here that reallocating the memory of ArrayList is NOT thread safe for the reader of the array's start - if the array growth is actually implemented by adding more linked arrays to the end without changing the original array that may be a false assumption.

---

UPDATE: Rather than deal with this headache, in the end, I simply re-designed the whole system to be an array of arrays. This way I can lock the parent array ONLY when creating - or rather, adding - the new sub-array; and any other locks are on individual sub-arrays that are treated atomically by all operations in the program anyway and thus won't suffer from locking issues.

Answer 1

How can I achieve the safe read/write concurrency on an ArrayList?

It's hard to figure out what is actually happening to the list. Items are being added to the end of the while readers are consuming from the front but I can't tell if multiple readers read a single item or does every reader consume every element?

But regardless, I would consider switching to using a BlockingQueue like an ArrayBlockingQueue. ArrayList is not at all built for your use case. I would have a BlockingQueue for the work and then another BlockingQueue for the results. Again, this assumes that entries in your list are not consumed by multiple threads.

One of the main issues here is that synchronization performances two functions: mutex protection and memory synchronization. The writers have to lock so they don't collide but the readers need to lock to be able to see the writers' updates to the list.

In terms of the blocking specifics, some of your requirements are not possible because of the race conditions involved with dynamically extending the list.

I am making an assumption here that merely writing to the end of ArrayList is thread safe for the reader of the array's start

This is true unless the write to the end of the list causes the list to be reallocated. However, again, you need to synchronize on the list to see any of the updates made to the list by the writers. Even if your ArrayList is volatile the fields inside of the list are not.

I am making an assumption here that reallocating the memory of ArrayList is NOT thread safe for the reader of the array's start...

No it is not. No part of the ArrayList is thread safe when it comes to the array of data. I'd recommend looking at the source if there is any question. The following method is called from add(...) and any other method that changes the size of the list.

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Answer 2

I'm unsure why you are using an ArrayList at all. What you are describing is a queue, a First-In-First-Out data structure. Java offers several Queue implementations that are thread-safe, notably ConcurrentLinkedQueue and LinkedBlockingQueue.

An ArrayList is fundamentally not thread-safe, and the only way to make it so is by wrapping it in a call to Collections.synchronizedList() which will make read and write access to the array essentially single-threaded.

Answer 3

Consider scenario:

Reader R1 takes the list and works with it

Writer W1 appends an element to the list, without array reallocation

Reader R2 takes the list and works with it.

The question is: should the list objects seen by R1 and R2 be different, or can be the same? In the first case, each write operation has to create new object, though underlying array can be the same (which is much more efficient than using CopyOnWriteArrayList). In the second case, R1 can see that the length of the list can grow unpredictably, which may cause programming errors.

In both cases, AtomicReference can be used to store current version of the list. Readers simply get the current list from it, and writers use additional object with monitor to synchronize update operations.