java - 需要在多线程环境中实现 ArrayList 的傻瓜式同步

Question

我已经研究了一个星期，现在正在研究如何正确同步 ArrayList。

简而言之，我的主要问题是我有一个对象的“主”ArrayList。不同的线程可能会进入并从该列表中添加/设置/删除。我需要确保当一个线程遍历 ArrayList 时，另一个线程不会更改它。

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

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

在每次迭代中使用同步块(synchronized block)，添加/设置/删除 block 似乎是我想要的，但人们说有很多开销。

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

我是否将每个最终不得不在同步块(synchronized block)中添加/设置/删除元素的迭代器包装起来？

这必须是多线程的常见问题。我本以为有人会创建一个可以毫无顾虑地处理所有这些的类......

提前感谢您查看此内容!

Answer 1

正如您自己发现的那样，CopyOnWriteArrayList 无法在有人处理数据时进行完全安全的更改，尤其是在迭代时在名单之上。因为:无论何时处理数据，都没有上下文来确保在其他人更改列表数据之前执行访问列表的完整语句 block 。

因此，对于执行整个数据访问 block 的所有访问操作(也包括读取!)，您必须具有任何上下文(如同步)。例如:

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 月 | 2012 年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_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();
}