java - 遍历被另一个线程修改的列表

Question

我是多线程编程的新手，有一个问题。如何让每个线程遍历列表中由不同线程添加的所有元素？

这里有一个简单的程序来演示。我有一个整数列表和 10 个线程，编号为 1 到 10，正在处理它。每个线程都是将列表中的所有值写入一个StringBuilder。在一个线程写入列表中的所有值后，它将其编号添加到列表中，然后终止。

我试图让每个线程继续检查列表中的元素，直到列表不再被任何其他线程修改，但在锁定它时遇到问题。如果成功，该程序的输出可能如下所示:

3: 1,
8: 1,3,2,4,5,7,
6: 1,3,2,4,5,7,8,
9: 1,3,2,4,5,7,8,6,
7: 1,3,2,4,5,
10: 1,3,2,4,5,7,8,6,9,
5: 1,3,2,4,
4: 1,3,2,
2: 1,3,
1: 

这种情况有时会发生，但通常有两个或更多线程在设置锁之前完成，因此迭代过早结束:

1: 
2: 1,5,4,8,7,3,10,
10: 1,5,4,8,7,3,
9: 1,5,4,8,7,3,10,2,
3: 1,5,4,8,7,
7: 1,5,4,8,
5: 1,    <<one of these threads didn't wait to stop iterating. 
4: 1,    <<
8: 1,5,4,
6: 1,5,4,8,7,3,10,2,

有没有人有什么想法？

===========

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.ReentrantLock;

public class ListChecker implements Runnable{

static List<Integer> list = new ArrayList<Integer>();
static ReentrantLock lock = new ReentrantLock();

int id;
StringBuilder result = new StringBuilder(); 

public ListChecker(int id){
    this.id = id;
}

@Override
public void run() {
    int i=0;

    do{
        while (i < list.size()){            
            result.append(list.get(i++)).append(',');
        }   
        if (!lock.isLocked()){
            break;
        }
    }while (true);                  
    addElement(id);
    System.out.println(id + ": " + result.toString());
}

public void addElement(int element){
    try{
        lock.lock();
        list.add(element);  
    }finally{
        lock.unlock();
    }
}


public static void main(String[] args){
    for(int i=1; i<=10; i++){
        ListChecker checker = new ListChecker(i);
        new Thread(checker).start();
    }   
}   
}

---

编辑:感谢到目前为止的帮助。我应该澄清一下，我希望每个线程同时遍历列表。在我的例子中，每个线程需要对列表的每个元素执行大量处理(而不是附加到 StringBuffer，我正在对候选项目与 final 列表进行大量比较)。因此，多线程需要让每个线程能够同时处理同一个列表，以提高我的性能。所以，我不认为锁定整个迭代，或者将整个迭代放在一个同步(列表) block 中，会起作用。

---

编辑 2:我想我明白了。诀窍不仅在于在向列表添加元素时在列表上进行同步，而且在确定是否还有更多元素时也如此。这可以防止线程 2 在线程 1 完成添加到列表之前停止其迭代。它看起来有点笨拙，但这保留了我需要在同步块(synchronized block)之外的多个线程中运行的代码，因此我的真实案例应该获得我需要的性能提升。

感谢所有帮助过的人!

import java.util.ArrayList;
import java.util.List;

public class ListChecker2 implements Runnable{

    static List<Integer> list = new ArrayList<Integer>();

    int id;
    StringBuilder result = new StringBuilder(); 

    public ListChecker2(int id){
        this.id = id;
    }

    @Override
    public void run() {
        int i = 0;
        do{
            synchronized (list) {           
                if (i >= list.size()){
                    list.add(id);
                    System.out.println(id + ": " + result.toString());
                    return;
                }
            }
            result.append(list.get(i++)).append(',');
            System.out.println("running " + id);

        }while(true);
    }


    public static void main(String[] args){
        for(int i=1; i<=30; i++){
            ListChecker2 checker = new ListChecker2(i);
            new Thread(checker).start();
        }   
    }   
}

Answer 1

您可以通过同步列表来更简单地做到这一点。

public class ListChecker implements Runnable {
  // Number of threads.
  static final int THREADS = 10;
  // The list.
  static final List<Integer> list = new ArrayList<Integer>(THREADS);

  // My ID
  int id;

  public ListChecker(int id) {
    // Remember my ID.
    this.id = id;
  }

  @Override
  public void run() {
    // My string.
    StringBuilder result = new StringBuilder ();
    // Wait for exclusive access to the list.
    synchronized (list) {
      // Build my string.
      for ( Integer i : list ) {
        result.append(i).append(",");
      }
      // Add me to the list.
      list.add(id);
    }
    System.out.println(id + ": " + result.toString());
  }

  public static void main(String[] args) {
    for (int i = 1; i <= THREADS; i++) {
      ListChecker checker = new ListChecker(i);
      new Thread(checker).start();
    }
  }
}

这是我的输出。恐怕有点无聊，但它证明它有效。

1: 
2: 1,
3: 1,2,
4: 1,2,3,
5: 1,2,3,4,
6: 1,2,3,4,5,
7: 1,2,3,4,5,6,
8: 1,2,3,4,5,6,7,
9: 1,2,3,4,5,6,7,8,
10: 1,2,3,4,5,6,7,8,9,

已添加

如果您需要避免锁定整个列表(正如您的编辑所建议的那样)，您可以尝试一个特殊的列表，该列表在提供最后一个条目时会自行锁定。当然，您需要专门解锁它。

遗憾的是，这种技术不能很好地处理空列表的情况。或许您可以想出一个合适的解决方案。

public class ListChecker implements Runnable {
  // Number of threads.
  static final int THREADS = 20;
  // The list.
  static final EndLockedList<Integer> list = new EndLockedList<Integer>();
  // My ID
  int id;

  public ListChecker(int id) {
    // Remember my ID.
    this.id = id;
  }

  @Override
  public void run() {
    // My string.
    StringBuilder result = new StringBuilder();
    // Build my string.
    for (int i = 0; i < list.size(); i++) {
      result.append(i).append(",");
    }
    // Add me to the list.
    list.add(id);
    // Unlock the end lock.
    list.unlock();
    System.out.println(id + ": " + result.toString());
  }

  public static void main(String[] args) {
    for (int i = 0; i < THREADS; i++) {
      ListChecker checker = new ListChecker(i + 1);
      new Thread(checker).start();
    }
  }

  private static class EndLockedList<T> extends ArrayList<T> {
    // My lock.
    private final Lock lock = new ReentrantLock();
    // Were we locked?
    private volatile boolean locked = false;

    @Override
    public boolean add(T it) {
      lock.lock();
      try {
        return super.add(it);
      } finally {
        lock.unlock();
      }
    }

    // Special get that locks the list when the last entry is got.
    @Override
    public T get(int i) {
      // Get it.
      T it = super.get(i);
      // If we are at the end.
      if (i == size() - 1) {
        // Speculative lock.
        lock.lock();
        // Still at the end?
        if (i < size() - 1) {
          // Release the lock!
          lock.unlock();
        } else {
          // Remember we were locked.
          locked = true;
          // It is now locked for putting until specifically unlocked.
        }
      }
      // That's the one.
      return it;
    }

    // Unlock.
    void unlock() {
      if (locked) {
        locked = false;
        lock.unlock();
      }
    }
  }
}

输出(注意空列表的错误处理):

2: 
8: 
5: 
1: 
4: 
7: 
6: 
9: 
3: 
10: 0,1,2,3,4,5,6,7,8,
11: 0,1,2,3,4,5,6,7,8,9,
12: 0,1,2,3,4,5,6,7,8,9,10,
13: 0,1,2,3,4,5,6,7,8,9,10,11,
14: 0,1,2,3,4,5,6,7,8,9,10,11,12,
15: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,
16: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,
17: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
18: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,
19: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,
20: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,