???? 在開發多線程并發的程序時，對列表進行遍歷是一個很常見的操作。比如說在觀察者模式中，當某個事件發生時，就需要通知到對應的觀察者進行事件的處理，這里就需要對觀察者列表進行遍歷，逐一觸發觀察者進行事件的處理。那么，如何保證并發中的遍歷操作的原子性呢？大概有下面幾種方式：

1. 首先，最容易想到的肯定是使用JAVA內置的同步機制-synchronized,把整個遍歷操作當作一個原子操作。

    synchronized(lock)
{
    for(Observer ob:observers)
    {
          //trigger event
          ob.update(event);
    }
}
  

?

這里使用的鎖對象-lock,應該是和對觀察者列表進行增加刪除操作時使用的鎖是同一個。采用這種方式，如果觀察者列表比較少而且觀察者進行事件的處理時間比較短的時候，是可接受的。如果觀察者列表變的很大或者其中某幾個觀察者進行事件的處理占時比較長的時候，那么就會引發并發的liveness問題，從而引起性能的下降。

?

2.索引訪問

??針對第一種遍歷出現的問題，我們可以通過減少synchronized的范圍來進行優化。每當我們看到synchronized塊的時候，我們要問問自己，synchronized塊保護的是什么？很明顯，上面保護的是observers列表，保證對該列表并發訪問時數據的正確性。也就是說，對于ob.update(event)，根本不需要進行保護。從而出現了Doug Lea所說的索引訪問：

    Observer ob=null;
for(int i=0;true;i++)
{
     synchronized(observers)
     {
         if(i<observers.size())
            ob=observers.get(i);
         else
            break;
     }

     //下面update調用不需要同步
   ob.update(event);
}
  

??? 雖然這種方式對性能有所提升，但是有可能會出現這樣的問題，如果在遍歷過程中，對observers列表進行刪除，則有可能出現被刪除的Observer沒有機會進行事件的觸發，或者對observers列表進行增加一個相同的元素，而observers本身就允許增加相同元素的時候，那么同一個Observer可能會對同一事件進行兩次處理。而對于第一種遍歷方式的另外一種改進，則是通過在持有鎖的情況下，復制一份observers列表，然后在不持有鎖的情況下，對observers列表中的每個observer進行事件的通知：

    Object[] tempObservers=null;
synchronized(observers)
{
    tempObservers=Arrays.copyOf(observers,observers.length);
}

for(Observer ob:tempObservers)
    ob.update(event);

  

?

?

3.Fail-fast

?? 如果不允許第2種遍歷方式出現的問題，那么可以通過使用Fail-fast模式來進行強制避免。Fail-fast模式經常出現在java的Iterator中。在Fail-fast模式中，每個列表維護一個int型的版本變量，每次對這個列表進行更新操作都會使這個版本變量加1。

    public class List
{
int version;

public synchronized void add(Object obj)
{
    //add object
    array[cursor++]=obj;    
    version++;
}

public synchronized  void remove(int index)
{
     //remove
     array[index]=null;
     version++;
}

//其余略

}

  

?? 而在創建一個Iterator時，會將當前的版本變量保存，在通過Iterator進行遍歷的時候，會每次都將Iterator內部保存的版本變量和List列表維護的版本變量進行比較，如果不相等，則表示有線程對當前的List列表進行了更新操作，那么Iterator的遍歷方式會拋出一個異常進行中止遍歷。

    public class List
{
   int version;
  
   ....

    public Iterator iterator()
    {
          return new ListIterator();
    }
 
    //inner class
    class ListIterator implements Iterator
    {
         int iteratorVersion;
         public ListIterator()
         {
             iteratorVersion=version;
         }

         public boolean hasNext()
         {
              synchronized(List.this){
                 if(iteratorVersion!=version)
                      throw new RuntimeException();
                  //check if the next element exists
              }
         }

         public Object next()
         {
              synchronized(List.this){
                 if(iteratorVersion!=version)
                      throw new RuntimeException();
                  //return the next element
               }
          }
}
    

  

? ? 如果你看過JDK的Iterator實現，你就會發現JDK中提供的大多數Iterator都不是同步的，即使是使用Collections.synchronizedList()后的list,這也就導致了我們常常在使用JDK提供的Iterator時，要自己考慮遍歷時的同步,否則會出現這樣的問題，iterator的遍歷是在一個線程，而對集合進行更新操作的是在另一個線程，那么，由于iterator遍歷的過程沒有同步，而version變量也不是violate,這樣就沒法保證version變量在并發中的可見性從而引起問題。而上述的實現了一個有鎖的版本。

???? 其實，上面這個synchronized版本的iterator可以進一步優化，可以將version變量聲明為violate,從而將所有的的鎖給去掉。雖然Fail-fast模式的遍歷可以保證并發遍歷操作時數據的正確性，但是這種遍歷方式很不友好，特別是在大并發的情況下，Fail-fast遍歷拋出異常中止的機率很高，試想下，如果在觀察者中使用Fail-fast的遍歷方式來通知事件的發生，那么在大并發的情況下，一件事件的發生并不保證會通知到所有的觀察者，這樣有可能就造成了事件的丟失，這個問題導致了Fail-fast的遍歷方式的使用業務場景會比較窄。

??

4.copy on write

???而對于copy on write方式，其原理是，每次在對集合進行更新操作的時候，都會對底層的數組進行拷貝。比如說add,remove操作。

    public class CopyOnWriteList
{
     
     public synchronized void add(Object obj)
     {
         Object[] newArray=Arrays.copyOf(oldArray,oldArray.length+1);
         newArray[oldArray.length]=obj;
         oldArray=newArray;
     }

    .....
}
  

??? 那么就可以在進行遍歷操作的時候，不需要加鎖來保證同步。

??

    public class CopyOnWriteList
{
    Object[] oldArray;
    ....

    public Iterator iterator()
    {
         return new CopyOnWriteIterator(oldArray);
    }
    
    public CopyOnWriteIterator implements Iterator
    {
         private Object[] iteratorArray;
         private int cursor;
         public CopyOnWriteIterator(Object[] array)
         {
              iteratorArray=array;
         }

         //不需要加鎖
      public boolean hasNext()
         {
             return cursor++<iteratorArray.length;
         }

          //不需要加鎖
       public Object next()
          {
              return iteratorArray[cursor];
          }
}
  

???雖然說copy on write的方式避免了遍歷時加鎖的問題，但是這種方式只適用于對于集合更新操作比較少，但遍歷使用場景比較多的情況下，?否則頻繁的COPY操作也會使性能下降。這種方式現在廣泛的應用于觀察者模式中，因為觀察者模式更多的是進行一個事件的通知（即遍歷集合），而不是增加/刪除觀察者。

?

5.鏈表-通過對add，remove等更新操作分別進行特殊處理，使得遍歷不加鎖。

?? 這種實現方式沒有鎖，也沒有violate變量，而是通過維護一個單向鏈表，并分別對Add，Remove操作進行一些額外的限制。對于Add操作來說，新加入的節點必須加到原先鏈表頭結點之前,新加入的節點變成新的鏈表頭節點：

???

?

?????通過這樣的方式，在遍歷過程中進行節點的增加操作也不會有并發問題，而對應的remove操作則需要復制被刪除節點之前的所有節點，并與被刪除的節點后面的節點關聯起來，如果要刪除的節點是最后一個節點，則相當于復制了整個鏈表。
?????????

?
??????? 如果在遍歷過程中進行刪除，也不會有并發問題，原先的遍歷會一直執行，新的遍歷會從新復制的節點開始。因為這里的刪除操作是對原來的節點進行了復制，而原先的節點在遍歷結束后被GC回收掉。

并發中的遍歷