在多线程环境中需要ArrayList的傻瓜证明同步

Question

我已经在这一周了,正在研究如何正确同步ArrayList.

简而言之,我的主要问题是我有一个"主"对象ArrayList.可能会有不同的线程进入并添加/设置/删除此列表.我需要确保当一个线程迭代通过ArrayList时,另一个线程不会更改它.

现在我已经阅读了很多关于"最佳"处理方式的文章:

• 使用collections.synchronizedlist
• 使用CopyOnWriteArrayList
• 将synchronized()块与collections.synchronizedlist结合使用
• 使用Vector(很多人反对这个)

在每次迭代中使用synchronized块,添加/设置/删除块似乎是我想要的,但人们说有很多开销.

然后我开始玩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的观点？

我是否包装每个迭代器,最终必须在同步块中添加/设置/删除元素？

这个HAS是多线程的常见问题.我原本以为有人会做一个能够毫无顾虑地处理这一切的课程......

提前谢谢你看看这个!

Answer 1

正如您自己发现的那样，当有人处理数据时，尤其是在迭代列表时，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 - 编辑：我使用 ReentrantReadWriteLock 为安全 ArrayList 创建了自己的访问上下文。
首先，我将插入整个 SecureArrayList 类（大多数第一个操作只是覆盖和保护），然后插入我的 Tester 类以及用法说明。
我只是用一个线程测试了访问，而不是同时用多个线程测试了访问，但我很确定它可以工作！如果没有，请告诉我。

安全数组列表：

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_测试：

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<Str