CODEWITHSUNDEEP
javaarraylistconcurrencythread-safety
DVK
DVK

Reputation: 129403

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

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:

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.

Upvotes: 1

Views: 1992

Answers (3)

Gray
Gray

Reputation: 116878

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);
    }
}

Upvotes: 3

Alexei Kaigorodov
Alexei Kaigorodov

Reputation: 13525

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.

Upvotes: 0

dimo414
dimo414

Reputation: 48824

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.

Upvotes: 1

Related Questions