在开发多线程并发的程序时,对列表进行遍历是一个很常见的操作。比如说在观察者模式中,当某个事件发生时,就需要通知到对应的观察者进行事件的处理,这里就需要对观察者列表进行遍历,逐一触发观察者进行事件的处理。那么,如何保证并发中的遍历操作的原子性呢?大概有下面几种方式:
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回收掉。
- 大小: 4.8 KB
- 大小: 8 KB
分享到:
相关推荐
List集合遍历和删除操作
《Java 7并发编程实战手册》是Java 7并发编程的实战指南,介绍了Java 7并发API中大部分重要而有用的机制。全书分为9章,涵盖了线程管理、线程同步、线程执行器、Fork/Join框架、并发集合、定制并发类、测试并发应用...
前言说起线程池大家肯定不会陌生,在面试中属于必问的问题之一,特别是对于高并发有较高要求的企业,基本是核…阅读数 1万+反转!BAT编程吸金榜来了,AI程序员刷爆
java中List对象集合的遍历方法 第一种: for(Iterator<A> it = list.iterator(); it.hasNext(); ) { .... } 这种方式在循环执行过程中会进行数据锁定, 性能稍差, 同时,如果你想在寻欢过程中去掉某个元素,只能...
多线程磁盘文件扫描
框架通过在框架线程中调用应用程序代码将并发性引入应用程序,因此对线程安全的需求在整个应用程序中都需要考虑 基础知识 线程安全性 定义 当多个线程访问某个类时,这个类始终能表现出正确的行为,...
2.新增sliced scroll类型:并发遍历 新增切片类型,进行并发的遍历 3.新增profile api:查询优化 4、新增reindex:对数据进行重建 进行异步重建提高索引的性能 5.新增ingest节点 直接在es中进行简单的过滤 不需要在...
Java处理高并发量访问的处理.txt Map集合的四种遍历方式.txt Mybatis查询某- -日、周、月数据.txt MySQL安装教程.txt MySQL查询最近-周、月每月、周统计数据.txt MySQL入Ar ]很简单学习笔记李国华.dox Oracle查看表...
不过光全局唯⼀还不够,很多时候我们会只根据订单ID直接查询订单信息,这时 由于没有uid,我们不知道去哪个分库的分表中查询,遍历所有的库的所有表?这显然不⾏。所以我们需要将分库分表的信息添加到订单ID 上,下...
ConcurrentSkipListSet 是Java中的一个线程安全的有序集合类,它基于跳表(Skip List)数据结构实现。...可通过迭代器进行并发遍历:ConcurrentSkipListSet 的迭代器是弱一致性的,并且不会抛出 ConcurrentModifica
这是并发目录遍历库。 它通过呼叫者必须服务的渠道返回结果。 调用者可以指定有趣的条目: 档案 目录 特殊文件(符号链接,设备节点等) 上述所有的 它可以选择跟随符号链接并检测安装点交叉。 如何使用? 这是一...
Java SE 8 Lambda Quick Start 中文版 -> :: ... Lambda表达式还可以改进收集库(Collection libraries),从而更容易地从集合中遍历,过滤和提取数据。 此外,新的并发功能可提高多核环境中的性能。
其次,内核中实现 select是用轮询方法,即每次检测都会遍历所有FD_SET中的句柄,显然,select函数执行时间与FD_SET中的句柄个数有一个比例关系,即 select要检测的句柄数越多就会越费时。当然,在前文中我并没有提及...
2. 获取所有车厢中有两个座位余票的车厢,并对这些车厢进行遍历,按照下述流程执行; 3. 首先检查所有车厢中是否存在一等座车票的相邻座位。如果所有车厢中都没有相邻座位,进入下一步逻辑; 4. 接着检查是否有车厢...
例如,如果程序循环遍历数组中的所有元素,JVM 就可以优化数组的边界检查,使循环更快,展开循环能提供额外的加速。但如果循环是为了找到特定元素,那目前还没有什么优化的办法,使得遍历数组和采用HashMap 的版本...
co_dict 字典(哈希表),内部有一个链表用于遍历,使用它可以实现lrucache co_set 集合,内部由红黑树实现。 co_list 双向链表 co_queue 循环队列 co_pqueue 优先队列 co_buffer 可读写bufer,环形buffer co_utf8 utf...
数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。...
测试遍历10个记录(休眠1秒)单线程和多线程(5个进程)执行效率比较:单线程10秒\多线程2秒。 整理操作模板,供参考(ps:线程数实际应用过程中,需要控制数量)
在main方法中,创建了一个BankAccountManager对象和ExecutorService线程池,并初始化了1000个账户和10个线程。然后循环遍历每个账户,将每个账户提交给线程池执行转账操作。在transfer方法中,获取两个账户对象和...
Java 中集合框架的主要接口是什么? ArrayList 和 LinkedList 有什么区别? HashSet 和 TreeSet 有什么区别? HashMap 和 TreeMap 有什么区别? 什么是迭代器?如何使用它来遍历集合? 什么是 fail-fast 机制? 如何...