Menu
I've been at this for a week now doing my research on how to properly synchronize an ArrayList.
My main issue in a nutshell is I have a "master" ArrayList of objects. Different threads may come in and add/set/remove from this list. I need to be sure that when one thread is iterating through the ArrayList, another is not changing it.
Now I've read many articles on the "best" way of handling this:
Using synchronized blocks around every iteration, add/set/remove block seems to be kind of what I want, but people have said there is a lot of overhead.
So then I started playing with CopyOnWriteArrayList (I do way more reads than writes for my master ArrayList). This is fine for reading, but what a lot of forum threads neglect to mention is that elements cannote be added, set, or removed from the iterator itself. For example (a basic version, but imagine it in a multi-threaded environment):
public static void main(String[] args) {
class TestObject{
private String s = "";
public TestObject(String s){
this.s = s;
}
public void setTheString(String s){
this.s = s;
}
public String getTheString(){
return s;
}
}
CopyOnWriteArrayList<TestObject> list = new CopyOnWriteArrayList<TestObject>();
list.add(new TestObject("A"));
list.add(new TestObject("B"));
list.add(new TestObject("C"));
list.add(new TestObject("D"));
list.add(new TestObject("E"));
ListIterator<TestObject> litr = list.listIterator();
while(litr.hasNext()){
TestObject test = litr.next();
if(test.getTheString().equals("B")){
litr.set(new TestObject("TEST"));
}
}
}
the line "litr.set(new TestObject("TEST"));" would throw a
java.lang.UnsupportedOperationException
And looking at the Java Documentation there is a specific line describing this behavior:
"Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException."
So then you are forced to modify that list by using
list.set(litr.previousIndex(), new TestObject("TEST"));
Now technically shouldn't this present a synchronization issue? If another thread were to come in at the same time, and say, remove all elements from "list" the iterator would not see that, it would go to set the "list" at a given index and would throw an exception because the element at that point no longer exists. I just don't understand the point of CopyOnWriteArrayList if you cant add an element through the iterator itself.
Am I missing the point with using CopyOnWriteArrayList?
Do I wrap every iterator that ends up having to add/set/remove an element in a synchronized block?
This HAS to be a common issue with multi-threading. I would have thought someone would have made a class that could handle all this without worry...
Thanks in advance for having a look at this!
689
As you found out yourself, CopyOnWriteArrayList is NOT ABLE to make completely secure changes when someone is processing the data, especially not while iterating over the list.
Because: Whenever you are working on the data, there is no context to make sure your complete block of statements accessing the list is executed before someone else changed the list data.
Therefore you MUST have any context (like synchronization) for all your access operations (also for reading!) that execute your whole data accessing block. For example:
ArrayList<String> list = getList();
synchronized (list) {
int index = list.indexOf("test");
// if the whole block would not be synchronized,
// the index could be invalid after an external change
list.remove(index);
}
Or for iterators:
synchronized (list) {
for (String s : list) {
System.out.println(s);
}
}
But now comes the big problem with this type of synchronization: It is slow and doesn't allow multiple reading access.
Therefore it would be useful to build your own context for data access. I am going to use the ReentrantReadWriteLock to allow multiple reading access and improve the performance.
I'm very interested in this topic and will make such a context for the ArrayList and attach it here after I finished it.
20.10.2012 | 18:30 - EDIT:
I created an own access context using the ReentrantReadWriteLock for a secure ArrayList.
Firstly I will insert the whole SecureArrayList class (the most of the first operations is just overriding and protecting), then I insert my Tester class with the explanation of the usage.
I just tested the access with one thread, not with many at the same time, but I'm pretty sure it works! If not, please tell me.
SecureArrayList:
package mydatastore.collections.concurrent;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;
/**
* @date 19.10.2012
* @author Thomas Jahoda
*
* uses ReentrantReadWriteLock
*/
public class SecureArrayList<E> extends ArrayList<E> {
protected final ReentrantReadWriteLock rwLock;
protected final ReadLock readLock;
protected final WriteLock writeLock;
public SecureArrayList() {
super();
this.rwLock = new ReentrantReadWriteLock();
readLock = rwLock.readLock();
writeLock = rwLock.writeLock();
}
// write operations
@Override
public boolean add(E e) {
try {
writeLock.lock();
return super.add(e);
} finally {
writeLock.unlock();
}
}
@Override
public void add(int index, E element) {
try {
writeLock.lock();
super.add(index, element);
} finally {
writeLock.unlock();
}
}
@Override
public boolean addAll(Collection<? extends E> c) {
try {
writeLock.lock();
return super.addAll(c);
} finally {
writeLock.unlock();
}
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
try {
writeLock.lock();
return super.addAll(index, c);
} finally {
writeLock.unlock();
}
}
@Override
public boolean remove(Object o) {
try {
writeLock.lock();
return super.remove(o);
} finally {
writeLock.unlock();
}
}
@Override
public E remove(int index) {
try {
writeLock.lock();
return super.remove(index);
} finally {
writeLock.unlock();
}
}
@Override
public boolean removeAll(Collection<?> c) {
try {
writeLock.lock();
return super.removeAll(c);
} finally {
writeLock.unlock();
}
}
@Override
protected void removeRange(int fromIndex, int toIndex) {
try {
writeLock.lock();
super.removeRange(fromIndex, toIndex);
} finally {
writeLock.unlock();
}
}
@Override
public E set(int index, E element) {
try {
writeLock.lock();
return super.set(index, element);
} finally {
writeLock.unlock();
}
}
@Override
public void clear() {
try {
writeLock.lock();
super.clear();
} finally {
writeLock.unlock();
}
}
@Override
public boolean retainAll(Collection<?> c) {
try {
writeLock.lock();
return super.retainAll(c);
} finally {
writeLock.unlock();
}
}
@Override
public void ensureCapacity(int minCapacity) {
try {
writeLock.lock();
super.ensureCapacity(minCapacity);
} finally {
writeLock.unlock();
}
}
@Override
public void trimToSize() {
try {
writeLock.lock();
super.trimToSize();
} finally {
writeLock.unlock();
}
}
//// now the read operations
@Override
public E get(int index) {
try {
readLock.lock();
return super.get(index);
} finally {
readLock.unlock();
}
}
@Override
public boolean contains(Object o) {
try {
readLock.lock();
return super.contains(o);
} finally {
readLock.unlock();
}
}
@Override
public boolean containsAll(Collection<?> c) {
try {
readLock.lock();
return super.containsAll(c);
} finally {
readLock.unlock();
}
}
@Override
public Object clone() {
try {
readLock.lock();
return super.clone();
} finally {
readLock.unlock();
}
}
@Override
public boolean equals(Object o) {
try {
readLock.lock();
return super.equals(o);
} finally {
readLock.unlock();
}
}
@Override
public int hashCode() {
try {
readLock.lock();
return super.hashCode();
} finally {
readLock.unlock();
}
}
@Override
public int indexOf(Object o) {
try {
readLock.lock();
return super.indexOf(o);
} finally {
readLock.unlock();
}
}
@Override
public Object[] toArray() {
try {
readLock.lock();
return super.toArray();
} finally {
readLock.unlock();
}
}
@Override
public boolean isEmpty() { // not sure if have to override because the size is temporarly stored in every case...
// it could happen that the size is accessed when it just gets assigned a new value,
// and the thread is switched after assigning 16 bits or smth... i dunno
try {
readLock.lock();
return super.isEmpty();
} finally {
readLock.unlock();
}
}
@Override
public int size() {
try {
readLock.lock();
return super.size();
} finally {
readLock.unlock();
}
}
@Override
public int lastIndexOf(Object o) {
try {
readLock.lock();
return super.lastIndexOf(o);
} finally {
readLock.unlock();
}
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
try {
readLock.lock();
return super.subList(fromIndex, toIndex);
} finally {
readLock.unlock();
}
}
@Override
public <T> T[] toArray(T[] a) {
try {
readLock.lock();
return super.toArray(a);
} finally {
readLock.unlock();
}
}
@Override
public String toString() {
try {
readLock.lock();
return super.toString();
} finally {
readLock.unlock();
}
}
////// iterators
@Override
public Iterator<E> iterator() {
return new SecureArrayListIterator();
}
@Override
public ListIterator<E> listIterator() {
return new SecureArrayListListIterator(0);
}
@Override
public ListIterator<E> listIterator(int index) {
return new SecureArrayListListIterator(index);
}
// deligated lock mechanisms
public void lockRead() {
readLock.lock();
}
public void unlockRead() {
readLock.unlock();
}
public void lockWrite() {
writeLock.lock();
}
public void unlockWrite() {
writeLock.unlock();
}
// getters
public ReadLock getReadLock() {
return readLock;
}
/**
* The writeLock also has access to reading, so when holding write, the
* thread can also obtain the readLock. But while holding the readLock and
* attempting to lock write, it will result in a deadlock.
*
* @return
*/
public WriteLock getWriteLock() {
return writeLock;
}
protected class SecureArrayListIterator implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
@Override
public boolean hasNext() {
return cursor != size();
}
@Override
public E next() {
// checkForComodification();
int i = cursor;
if (i >= SecureArrayList.super.size()) {
throw new NoSuchElementException();
}
cursor = i + 1;
lastRet = i;
return SecureArrayList.super.get(lastRet);
}
@Override
public void remove() {
if (!writeLock.isHeldByCurrentThread()) {
throw new IllegalMonitorStateException("when the iteration uses write operations,"
+ "the complete iteration loop must hold a monitor for the writeLock");
}
if (lastRet < 0) {
throw new IllegalStateException("No element iterated over");
}
try {
SecureArrayList.super.remove(lastRet);
cursor = lastRet;
lastRet = -1;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException(); // impossibru, except for bugged child classes
}
}
// protected final void checkForComodification() {
// if (modCount != expectedModCount) {
// throw new IllegalMonitorStateException("The complete iteration must hold the read or write lock!");
// }
// }
}
/**
* An optimized version of AbstractList.ListItr
*/
protected class SecureArrayListListIterator extends SecureArrayListIterator implements ListIterator<E> {
protected SecureArrayListListIterator(int index) {
super();
cursor = index;
}
@Override
public boolean hasPrevious() {
return cursor != 0;
}
@Override
public int nextIndex() {
return cursor;
}
@Override
public int previousIndex() {
return cursor - 1;
}
@Override
public E previous() {
// checkForComodification();
int i = cursor - 1;
if (i < 0) {
throw new NoSuchElementException("No element iterated over");
}
cursor = i;
lastRet = i;
return SecureArrayList.super.get(lastRet);
}
@Override
public void set(E e) {
if (!writeLock.isHeldByCurrentThread()) {
throw new IllegalMonitorStateException("when the iteration uses write operations,"
+ "the complete iteration loop must hold a monitor for the writeLock");
}
if (lastRet < 0) {
throw new IllegalStateException("No element iterated over");
}
// try {
SecureArrayList.super.set(lastRet, e);
// } catch (IndexOutOfBoundsException ex) {
// throw new ConcurrentModificationException(); // impossibru, except for bugged child classes
// EDIT: or any failed direct editing while iterating over the list
// }
}
@Override
public void add(E e) {
if (!writeLock.isHeldByCurrentThread()) {
throw new IllegalMonitorStateException("when the iteration uses write operations,"
+ "the complete iteration loop must hold a monitor for the writeLock");
}
// try {
int i = cursor;
SecureArrayList.super.add(i, e);
cursor = i + 1;
lastRet = -1;
// } catch (IndexOutOfBoundsException ex) {
// throw new ConcurrentModificationException(); // impossibru, except for bugged child classes
// // EDIT: or any failed direct editing while iterating over the list
// }
}
}
}
SecureArrayList_Test:
package mydatastore.collections.concurrent;
import java.util.Iterator;
import java.util.ListIterator;
/**
* @date 19.10.2012
* @author Thomas Jahoda
*/
public class SecureArrayList_Test {
private static SecureArrayList<String> statList = new SecureArrayList<>();
public static void main(String[] args) {
accessExamples();
// mechanismTest_1();
// mechanismTest_2();
}
private static void accessExamples() {
final SecureArrayList<String> list = getList();
//
try {
list.lockWrite();
//
list.add("banana");
list.add("test");
} finally {
list.unlockWrite();
}
////// independent single statement reading or writing access
String val = list.get(0);
//// ---
////// reading only block (just some senseless unoptimized 'whatever' example)
int lastIndex = -1;
try {
list.lockRead();
//
String search = "test";
if (list.contains(search)) {
lastIndex = list.lastIndexOf(search);
}
// !!! MIND !!!
// inserting writing operations here results in a DEADLOCK!!!
// ... which is just really, really awkward...
} finally {
list.unlockRead();
}
//// ---
////// writing block (can also contain reading operations!!)
try {
list.lockWrite();
//
int index = list.indexOf("test");
if (index != -1) {
String newVal = "banana";
list.add(index + 1, newVal);
}
} finally {
list.unlockWrite();
}
//// ---
////// iteration for reading only
System.out.println("First output: ");
try {
list.lockRead();
//
for (Iterator<String> it = list.iterator(); it.hasNext();) {
String string = it.next();
System.out.println(string);
// !!! MIND !!!
// inserting writing operations called directly on the list will result in a deadlock!
// inserting writing operations called on the iterator will result in an IllegalMonitorStateException!
}
} finally {
list.unlockRead();
}
System.out.println("------");
//// ---
////// iteration for writing and reading
try {
list.lockWrite();
//
boolean firstAdd = true;
for (ListIterator<String> it = list.listIterator(); it.hasNext();) {
int index = it.nextIndex();
String string = it.next();
switch (string) {
case "banana":
it.remove();
break;
case "test":
if (firstAdd) {
it.add("whatever");
firstAdd = false;
}
break;
}
if (index == 2) {
list.set(index - 1, "pretty senseless data and operations but just to show "
+ "what's possible");
}
// !!! MIND !!!
// Only I implemented the iterators to enable direct list editing,
// other implementations normally throw a ConcurrentModificationException
}
} finally {
list.unlockWrite();
}
//// ---
System.out.println("Complete last output: ");
try {
list.lockRead();
//
for (String string : list) {
System.out.println(string);
}
} finally {
list.unlockRead();
}
System.out.println("------");
////// getting the last element
String lastElement = null;
try {
list.lockRead();
int size = list.size();
lastElement = list.get(size - 1);
} finally {
list.unlockRead();
}
System.out.println("Last element: " + lastElement);
//// ---
}
private static void mechanismTest_1() { // fus, roh
SecureArrayList<String> list = getList();
try {
System.out.print("fus, ");
list.lockRead();
System.out.print("roh, ");
list.lockWrite();
System.out.println("dah!"); // never happens cos of deadlock
} finally {
// also never happens
System.out.println("dah?");
list.unlockRead();
list.unlockWrite();
}
}
private static void mechanismTest_2() { // fus, roh, dah!
SecureArrayList<String> list = getList();
try {
System.out.print("fus, ");
list.lockWrite();
System.out.print("roh, ");
list.lockRead();
System.out.println("dah!");
} finally {
list.unlockRead();
list.unlockWrite();
}
// successful execution
}
private static SecureArrayList<String> getList() {
return statList;
}
}
Edit: I've added a couple test cases to demonstrate the functionality in threads. The above class works perfectly and I'm now using it in my main project (Liam):
private static void threadedWriteLock(){
final ThreadSafeArrayList<String> list = getList();
Thread threadOne;
Thread threadTwo;
final long lStartMS = System.currentTimeMillis();
list.add("String 1");
list.add("String 2");
System.out.println("******* basic write lock test *******");
threadOne = new Thread(new Runnable(){
public void run(){
try {
list.lockWrite();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
} finally {
list.unlockWrite();
}
}
});
threadTwo = new Thread(new Runnable(){
public void run(){
//give threadOne time to lock (just in case)
try {
Thread.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Expect a wait....");
//if this "add" line is commented out, even the iterator read will be locked.
//So its not only locking on the add, but also the read which is correct.
list.add("String 3");
for (ListIterator<String> it = list.listIterator(); it.hasNext();) {
System.out.println("String at index " + it.nextIndex() + ": " + it.next());
}
System.out.println("ThreadTwo completed in " + (System.currentTimeMillis() - lStartMS) + "ms");
}
});
threadOne.start();
threadTwo.start();
}
private static void threadedReadLock(){
final ThreadSafeArrayList<String> list = getList();
Thread threadOne;
Thread threadTwo;
final long lStartMS = System.currentTimeMillis();
list.add("String 1");
list.add("String 2");
System.out.println("******* basic read lock test *******");
threadOne = new Thread(new Runnable(){
public void run(){
try {
list.lockRead();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
} finally {
list.unlockRead();
}
}
});
threadTwo = new Thread(new Runnable(){
public void run(){
//give threadOne time to lock (just in case)
try {
Thread.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Expect a wait if adding, but not reading....");
//if this "add" line is commented out, the read will continue without holding up the thread
list.add("String 3");
for (ListIterator<String> it = list.listIterator(); it.hasNext();) {
System.out.println("String at index " + it.nextIndex() + ": " + it.next());
}
System.out.println("ThreadTwo completed in " + (System.currentTimeMillis() - lStartMS) + "ms");
}
});
threadOne.start();
threadTwo.start();
}
Another approach is to protect all access to the list, but with a ReadWriteLock instead of synchronized blocks.
This allows simultaneous reads in a safe manner, and could improve performance a lot in a scenario with many reads and few writes.
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
