Need Fool Proof Synchronization of ArrayList in A Multi-threaded Environment
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.
Use CopyOnWriteArrayList, and synchronize on write operations only
CopyOnWriteArrayList<TestObject> list = ...final Object writeLock = new Object();void writeOpA(){ synchronized(writeLock) { read/write list }}void writeOpB(){ synchronized(writeLock) { read/write list }}Therefore no two write sessions will overlap with each other.
Reads require no lock. But a read session may see a changing list. If we want a read session to see a snapshot of the list, either use iterator(), or take a snapshot by toArray().
It's probably even better if you do the copy-on-write yourselves
volatile Foo data = new Foo(); // ArrayList in your casefinal Object writeLock = new Object();void writeOpA(){ synchronized(writeLock) { Foo clone = data.clone(); // read/write clone data = clone; }}void writeOpB(){ // similar...}void readSession(){ Foo snapshot = data; // read snapshot}