8

ArrayList を適切に同期する方法について調査を行ってから 1 週間が経過しました。

一言で言えば、私の主な問題は、オブジェクトの「マスター」ArrayList があることです。さまざまなスレッドが入ってきて、このリストに追加/設定/削除する場合があります。あるスレッドが ArrayList を反復処理しているときに、別のスレッドがそれを変更していないことを確認する必要があります。

今、これを処理する「最良の」方法に関する多くの記事を読みました。

  • collections.synchronizedlist を使用する
  • CopyOnWriteArrayList を使用する
  • synchronized() ブロックを collection.synchronizedlist と組み合わせて使用​​する
  • ベクターを使用する(多くの人がこれに反対しています)

すべての反復で同期ブロックを使用して、ブロックの追加/設定/削除は私が望んでいるように思えますが、多くのオーバーヘッドがあると人々は言っています。

それで、私は CopyOnWriteArrayList をいじり始めました (マスター ArrayList の書き込みよりも読み取りの方がはるかに多いです)。これは読むには問題ありませんが、イテレータ自体から要素を追加、設定、または削除できないことを多くのフォーラム スレッドが言及することを怠っています。例(基本的なバージョンですが、マルチスレッド環境で想像してください):

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

行 "litr.set(new TestObject("TEST"));" を投げます

java.lang.UnsupportedOperationException

Java ドキュメントを見ると、この動作を説明する特定の行があります。

「反復子自体の要素変更操作 (削除、設定、および追加) はサポートされていません。これらのメソッドは UnsupportedOperationException をスローします。」

そのため、使用してそのリストを変更する必要があります

list.set(litr.previousIndex(), new TestObject("TEST"));

技術的には、これは同期の問題を引き起こすべきではありませんか? 別のスレッドが同時に入ってきて、たとえば「リスト」からすべての要素を削除すると、反復子はそれを認識せず、指定されたインデックスで「リスト」を設定し、例外をスローします。その時点でもう存在しません。イテレータ自体を介して要素を追加できない場合、 CopyOnWriteArrayList のポイントがわかりません。

CopyOnWriteArrayList を使用してポイントを逃していますか?

要素を追加/設定/削除する必要があるすべてのイテレータを同期ブロックでラップする必要がありますか?

これは、マルチスレッドでよくある問題です。誰かがこれをすべて心配することなく処理できるクラスを作ったと思っていたでしょう...

これをご覧いただきありがとうございます。

4

4 に答える 4

3

ご存じのように、誰かがデータを処理しているとき、特にリストを繰り返し処理しているときは、完全に安全な変更を行うことができませ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();
}
于 2012-10-19T22:26:57.673 に答える
1

別のアプローチは、リストへのすべてのアクセスを保護することですが、同期ブロックの代わりに ReadWriteLock を使用します。

これにより、安全な方法で同時読み取りが可能になり、読み取りが多く書き込みが少ないシナリオでパフォーマンスが大幅に向上する可能性があります。

于 2012-10-19T19:45:28.907 に答える
1

CopyOnWriteArrayList を使用し、書き込み操作のみで同期する

CopyOnWriteArrayList<TestObject> list = ...

final Object writeLock = new Object();

void writeOpA()
{
    synchronized(writeLock)
    {
        read/write list
    }
}
void writeOpB()
{
    synchronized(writeLock)
    {
        read/write list
    }
}

したがって、2 つの書き込みセッションが互いに重複することはありません。

読み取りにはロックは必要ありません。ただし、読み取りセッションでは、変化するリストが表示される場合があります。読み取りセッションでリストのスナップショットを表示する場合は、 を使用するかiterator()、 でスナップショットを取得しtoArray()ます。


自分でコピーオンライトを行うと、おそらくさらに良いでしょう

volatile Foo data = new Foo(); // ArrayList in your case

final 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
}
于 2012-10-19T20:14:50.033 に答える
0

反復中に変更している場合は、オプション 3 を使用する必要があります。他の方法では、実際に必要なことは行われません。

より具体的には、何をしたいのかを考えると、途中でリストを変更する可能性があるため、リスト全体をロックする必要あります。これにより、リストで同時に作業している他のイテレーターが破損する可能性があります。これはオプション 3 を意味します。Java 言語は「同期された反復子」だけを持つことができないためです。反復子自体は、hasNext()またはへの個々の呼び出しのみを同期できnext()ますが、反復全体にわたって同期することはできません。

于 2012-10-19T19:37:38.287 に答える