xylz,imxylz

关注后端架构、中间件、分布式和并发编程

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  111 随笔 :: 10 文章 :: 2680 评论 :: 0 Trackbacks

本小节是《并发容器》的最后一部分,这一个小节描述的是针对List/Set接口的一个线程版本。

在《并发队列与Queue简介》中介绍了并发容器的一个概括,主要描述的是Queue的实现。其中特别提到一点LinkedList是List/Queue的实现,但是LinkedList确实非线程安全的。不管BlockingQueue还是ConcurrentMap的实现,我们发现都是针对链表的实现,当然尽可能的使用CAS或者Lock的特性,同时都有通过锁部分容器来提供并发的特性。而对于List或者Set而言,增、删操作其实都是针对整个容器,因此每次操作都不可避免的需要锁定整个容器空间,性能肯定会大打折扣。要实现一个线程安全的List/Set,只需要在修改操作的时候进行同步即可,比如使用java.util.Collections.synchronizedList(List<T>)或者java.util.Collections.synchronizedSet(Set<T>)。当然也可以使用Lock来实现线程安全的List/Set。

通常情况下我们的高并发都发生在“多读少写”的情况,因此如果能够实现一种更优秀的算法这对生产环境还是很有好处的。ReadWriteLock当然是一种实现。CopyOnWriteArrayList/CopyOnWriteArraySet确实另外一种思路。

CopyOnWriteArrayList/CopyOnWriteArraySet的基本思想是一旦对容器有修改,那么就“复制”一份新的集合,在新的集合上修改,然后将新集合复制给旧的引用。当然了这部分少不了要加锁。显然对于CopyOnWriteArrayList/CopyOnWriteArraySet来说最大的好处就是“读”操作不需要锁了。

我们来看看源码。

/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;
public E get(int index) {
   
return (E)(getArray()[index]);
}
private static int indexOf(Object o, Object[] elements,
                          
int index, int fence) {
   
if (o == null) {
       
for (int i = index; i < fence; i++)
           
if (elements[i] == null)
               
return i;
    }
else {
       
for (int i = index; i < fence; i++)
           
if (o.equals(elements[i]))
               
return i;
    }
   
return -1;
}
public Iterator<E> iterator() {
   
return new COWIterator<E>(getArray(), 0);
}
   
public void clear() {
   
final ReentrantLock lock = this.lock;
    lock.lock();
   
try {
        setArray(
new Object[0]);
    }
finally {
        lock.unlock();
    }
    }

对于上述代码,有几点说明:

  1. List仍然是基于数组的实现,因为只有数组是最快的。
  2. 为了保证无锁的读操作能够看到写操作的变化,因此数组array是volatile类型的。
  3. get/indexOf/iterator等操作都是无锁的,同时也可以看到所操作的都是某一时刻array的镜像(这得益于数组是不可变化的)
  4. add/set/remove/clear等元素变化的都是需要加锁的,这里使用的是ReentrantLock。

这里有一段有意思的代码片段。

    public E set(int index, E element) {
   
final ReentrantLock lock = this.lock;
    lock.lock();
   
try {
        Object[] elements
= getArray();
        Object oldValue
= elements[index];
       
if (oldValue != element) {
       
int len = elements.length;
        Object[] newElements
= Arrays.copyOf(elements, len);
        newElements[index]
= element;
        setArray(newElements);
        }
else {
       
// Not quite a no-op; ensures volatile write semantics
        setArray(elements);
        }
       
return (E)oldValue;
    }
finally {
        lock.unlock();
    }
    }

final void setArray(Object[] a) {
    array
= a;
}

对于set操作,如果元素有变化,修改后setArray(newElements);将新数组赋值还好理解。那么如果一个元素没有变化,也就是上述代码的else部分,为什么还需要进行一个无谓的setArray操作?毕竟setArray操作没有改变任何数据。

对于这个问题也是很有意思,有一封邮件讨论了此问题(123)。
大致的意思是,尽管没有改变任何数据,但是为了保持“volatile”的语义,任何一个读操作都应该是一个写操作的结果,也就是读操作看到的数据一定是某个写操作的结果(尽管写操作没有改变数据本身)。所以这里即使不设置也没有问题,仅仅是为了一个语义上的补充(个人理解)。

这里还有一个有意思的讨论,说什么addIfAbsent在元素没有变化的时候为什么没有setArray操作?这个要看怎么理解addIfAbsent的语义了。如果说addIfAbsent语义是”写“或者”不写“操作,而把”不写“操作当作一次”读“操作的话,那么”读“操作就不需要保持volatile语义了。

 

对于CopyOnWriteArraySet而言就简单多了,只是持有一个CopyOnWriteArrayList,仅仅在add/addAll的时候检测元素是否存在,如果存在就不加入集合中。

private final CopyOnWriteArrayList<E> al;
/**
* Creates an empty set.
*/
public CopyOnWriteArraySet() {
    al
= new CopyOnWriteArrayList<E>();
}

public boolean add(E e) {
   
return al.addIfAbsent(e);
}

 

在使用上CopyOnWriteArrayList/CopyOnWriteArraySet就简单多了,和List/Set基本相同,这里就不再介绍了。

 

整个并发容器结束了,接下来好好规划下线程池部分,然后进入最后一部分的梳理。

 



©2009-2014 IMXYLZ |求贤若渴
posted on 2010-11-23 22:22 imxylz 阅读(14667) 评论(1)  编辑  收藏 所属分类: Java Concurrency

评论

# re: 深入浅出 Java Concurrency (27): 并发容器 part 12 线程安全的List/Set 2013-07-31 13:59 是的方式的
是地方是的  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航:
 

©2009-2014 IMXYLZ