迭代通過正在被另一個線程修改的列表

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，我正在對候選項目與入圍名單進行大量比較）。因此，讓多線程同時處理同一列表中的每個線程都可以提高我的性能。所以，我不認爲鎖定整個迭代，或者說整個迭代是一個同步（列表）塊，將會起作用。

---

編輯2：我想我明白了。訣竅不僅僅是在添加元素的同時添加元素，還要確定是否還有其他元素。這可以防止線程2在線程1完成添加到列表之前停止其迭代。它看起來有點笨拙，但是這使我需要在同步塊外的多個線程中運行的代碼，所以我的真實情況應該會得到我需要的性能提升。

感謝大家幫助！

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, 

Answer 2

您選擇了一個艱難的案例讓你的腳溼。閱讀和寫作的同時對象是複雜的，從不建議和經常專門防止（即不會與一個Iterator和工作列表中）

但

如果你必須這樣做，你應該同步上在添加元素之前添加元素，並在添加元素之後調用list.notifyAll，這會喚醒正在等待更多結果的線程。同時，你的其他線程應該讀到最後，然後在列表中同步（你需要在對象上同步以調用wait，notify或notifyAll）並且調用等待它。

順便說一句更簡單的方法是使用偵聽器/觀察者/可觀察模式，儘管偵聽器模式可以（通常）單線程操作。你可能想要谷歌的教程。

Answer 3

您可以像使用Collections.synchronizedList（名單列表）

的方法，這是你如何使用它：

List list = Collections.synchronizedList(new ArrayList()); 
    ... 
    synchronized (list) { 
    Iterator i = list.iterator(); // Must be in synchronized block 
    while (i.hasNext()) 
     foo(i.next()); 
    } 

Answer 4

請更新您的run方法。並讓我知道它是否按照您的預期工作？

public void run() { 
int i=0; 
    lock.lock(); 
    while (i < list.size()){    
     result.append(list.get(i++)).append(','); 
} 
addElement(id); 
lock.unlock();`` 
System.out.println(id + ": " + result.toString()); 
}