ご存じのように、誰かがデータを処理しているとき、特にリストを繰り返し処理しているときは、完全に安全な変更を行うことができませCopyOnWriteArrayList
ん。理由: データを操作しているときはいつでも、他の誰かがリスト データを変更する前に、リストにアクセスするステートメントの完全なブロックが実行されることを確認するコンテキストがありません。
したがって、ブロックにアクセスするデータ全体を実行するすべてのアクセス操作 (読み取りも!) には、コンテキスト (同期など) が必要です。例えば:
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);
}
またはイテレータの場合:
synchronized (list) {
for (String s : list) {
System.out.println(s);
}
}
しかし、このタイプの同期には大きな問題があります。速度が遅く、複数の読み取りアクセスが許可されていません。
したがって、データ アクセス用の独自のコンテキストを構築すると便利です。ReentrantReadWriteLock を使用して、複数の読み取りアクセスを許可し、パフォーマンスを向上させます。
私はこのトピックに非常に興味があり、ArrayList のコンテキストを作成し、終了後にここに添付します。
2012.10.20 | 18:30 - 編集: 安全な ArrayList に ReentrantReadWriteLock を使用して独自のアクセス コンテキストを作成しました。
まず、SecureArrayList クラス全体を挿入し (最初の操作のほとんどはオーバーライドと保護だけです)、次に Tester クラスを使用方法の説明と共に挿入します。
同時に多くのスレッドではなく、1 つのスレッドでアクセスをテストしましたが、動作することは間違いありません。そうでない場合は、教えてください。
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;
}
}
編集: スレッドの機能を実証するために、いくつかのテスト ケースを追加しました。上記のクラスは完全に機能し、メイン プロジェクト (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();
}