并发中的遍历

     在开发多线程并发的程序时，对列表进行遍历是一个很常见的操作。比如说在观察者模式中，当某个事件发生时，就需要通知到对应的观察者进行事件的处理，这里就需要对观察者列表进行遍历，逐一触发观察者进行事件的处理。那么，如何保证并发中的遍历操作的原子性呢？大概有下面几种方式：

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回收掉。

评论

1 楼 狂放不羁 2010-04-08  

写的不错。多谢分享。