juc并发集合类_并发集合类

发布于:2021-09-17 03:12:03

出现在Java类库中的第一个关联集合类是Hashtable ,它是JDK 1.0的一部分。 Hashtable提供了易于使用,线程安全的关联映射功能,并且肯定很方便。 但是,线程安全是要付出代价的Hashtable所有方法都是同步的。 当时,无竞争的同步具有可衡量的性能成本。 Hashtable的后继者HashMap出现在JDK 1.2中的Collections框架中,它通过提供未同步的基类和同步的包装器Collections.synchronizedMap解决线程安全问题。 将基本功能与线程安全性Collections.synchronizedMap分开,可以使需要同步的用户进行同步,而不需要同步的用户则不必为此付费。


简单的方法,以通过两取同步HashtablesynchronizedMap -同步于每个方法Hashtable或同步Map包装对象-有两个主要缺陷。 这是可伸缩性的一个*蛭淮沃荒苡幸桓鱿叱谭梦使1怼 同时,这不足以提供真正的线程安全性,因为许多常见的复合操作仍然需要额外的同步。 尽管诸如get()put()类的简单操作可以安全地完成而无需额外的同步,但是有一些常见的操作序列,例如迭代或不存在put,它们仍需要外部同步以避免数据竞争。


条件线程安全

同步的集*捌鳎 synchronizedMapsynchronizedList有时被称为条件线程安全的 -所有单个操作都是线程安全的,但是控制流取决于先前操作的结果的操作序列可能会受到数据竞争的影响。 清单1中的第一个代码片段显示了常见的“如果不存在”的*惯用法-如果Map尚不存在某个条目,则添加它。 不幸的是,正如所写的那样,另一个线程可能在containsKey()方法返回到调用put()方法之间插入具有相同键的值。 如果要确保一次插入,则需要用在Map m上同步的同步块包装这对语句。


清单1中的其他示例涉及迭代。 在第一个示例中, List.size()的结果在循环执行期间可能变得无效,因为另一个线程可以从列表中删除项目。 如果计时不List.get() ,并且进入循环的最后一次迭代后某个项目被另一个线程删除,则List.get()将返回null ,而doSomething()可能会抛出NullPointerException 。 您可以如何避免这种情况? 如果在迭代过程中另一个线程可能正在访问List则必须在迭代时锁定整个List ,方法是使用synchronized块包装它,并在List l上进行同步。 这可以解决数据争用问题,但会增加并发成本,因为在迭代时锁定整个List可能会阻止其他线程长时间访问该列表。


Collections框架引入了用于遍历列表或其他集合的迭代器,该迭代器优化了对集合中的元素进行迭代的过程。 但是,在java.util Collections类中实现的迭代器是快速失败的,这意味着,如果一个线程更改了一个集合,而另一个线程通过Iterator遍历该集合,则下一个Iterator.hasNext()Iterator.next()调用将抛出ConcurrentModificationException 。 与前面的示例一样,如果要防止ConcurrentModificationException ,则必须在迭代时锁定整个List ,方法是使用在List lsynchronized块将其包装。 (或者,您可以调用List.toArray()并在不进行同步的情况下在数组上进行迭代,但是如果列表很大,这可能会很昂贵。)


清单1.同步地图中的常见竞争条件

Map m = Collections.synchronizedMap(new HashMap());
List l = Collections.synchronizedList(new ArrayList());

// put-if-absent idiom -- contains a race condition
// may require external synchronization
if (!map.containsKey(key))
map.put(key, value);

// ad-hoc iteration -- contains race conditions
// may require external synchronization
for (int i=0; i doSomething(list.get(i));
}

// normal iteration -- can throw ConcurrentModificationException
// may require external synchronization
for (Iterator i=list.iterator(); i.hasNext(); ) {
doSomething(i.next());
}

错误的信心

synchronizedListsynchronizedMap提供的条件线程安全性存在隐患-开发人员认为,由于这些集合是同步的,因此它们是完全线程安全的,并且他们忽略了正确同步复合操作。 结果是,尽管这些程序看起来在轻负载下工作,但在重负载下,它们可能会开始抛出NullPointerExceptionConcurrentModificationException


可伸缩性问题

可伸缩性描述了应用程序的吞吐量如何随其工作负载和可用计算资源的增加而变化。 可伸缩程序可以使用更多处理器,内存或I / O带宽来按比例处理更大的工作量。 锁定共享资源以进行独占访问是可伸缩性的瓶颈-即使其他空闲处理器可用于调度那些线程,它也会阻止其他线程访问该资源。 为了实现可伸缩性,我们必须消除或减少对专有资源锁的依赖。


同步的Collections包装器以及较早的HashtableVector类的更大问题是它们在单个锁上进行同步。 这意味着只有一个线程可以一次访问该集合,并且如果一个线程正在从Map读取数据,则所有其他想要从其读取或写入的线程都必须等待。 最常见的Map操作get()put()可能涉及比明显更多的计算-在遍历哈希存储桶以查找特定键时, get()可能必须大量调用Object.equals()的候选人。 如果键类使用的hashCode()函数未在哈希范围内*均分配值或发生大量哈希冲突,则某些存储桶链可能比其他存储桶链长得多,并且遍历较长的哈希链并调用equals()在一定比例的元素上可能会很慢。 在这种情况下, get()put()昂贵的问题不仅在于访问速度很慢,而且在遍历该哈希链时,所有其他线程也被禁止访问Map


由于上面讨论的条件线程安全性问题,在某些情况下执行get()可能需要花费大量时间,这一事实变得更加糟糕。 清单1所示的竞争条件通常使得必须将单个集合锁的持有时间比执行单个操作所需的时间长得多。 如果要在整个迭代过程中保持对集合的锁定,则其他线程可能会停滞,等待较长时间的集合锁定。


示例:一个简单的缓存

服务器应用程序中最常见的Map应用程序之一是实现缓存。 服务器应用程序可以缓存文件内容,生成的页面,数据库查询的结果,与已解析的XML文件关联的DOM树以及许多其他类型的数据。 缓存的主要目的是通过重用以前的计算结果来减少服务时间并增加吞吐量。 缓存工作负载的典型特征是检索比更新要普遍得多,因此(理想情况下)缓存将提供非常好的get()性能。 阻碍应用程序性能的缓存要比根本没有缓存差。


如果使用synchronizedMap来实现高速缓存,则将在应用程序中引入潜在的可伸缩性瓶颈。 只有一个线程可以一次访问Map ,这包括可能正在从Map检索值的所有线程,以及想要在Map中安装新(key, value)对的线程。


减少锁定粒度

在提供线程安全性的同时提高HashMap并发性的一种方法是放弃整个表的单个锁,并为每个哈希存储桶使用一个锁(或更常见的是,每个存储池都保护多个存储桶的锁池)。 这意味着多个线程可以同时访问Map不同部分,而不必争用单个集合范围的锁。 这种方法立即提高了插入,检索和删除操作的可伸缩性。 不幸的是,这种并发性有代价-实现整个集合上运行的方法size()例如size()isEmpty()变得更加困难,因为这可能需要一次获取多个锁,否则可能会返回错误的结果。 但是,对于实现高速缓存之类的情况,这是一个非常明智的折衷方案-检索和插入操作非常频繁,而size()isEmpty()操作的频率则大大降低。


并发哈希图

util.concurrentConcurrentHashMap类(还将出现在JDK 1.5中的java.util.concurrent包中)是Map的线程安全实现,它提供的synchronizedMap远好于synchronizedMap 。 多次读取几乎总是可以同时执行,同时读取和写入通常可以同时执行,并且多个同时写入通常可以同时执行。 (相关的ConcurrentReaderHashMap类提供了类似的多读取器并发性,但是只允许一个活动的写入器。) ConcurrentHashMap被设计为优化检索操作;因此,可以使用以下代码: 实际上,成功的get()操作通常不会锁定就成功。 在不锁定的情况下实现线程安全是很棘手的,并且需要对Java内存模型的细节有深入的了解。 并发专家对ConcurrentHashMap实现以及util.concurrent的其余部分进行了广泛的同行评审,以确保其正确性和线程安全性。 我们将在下个月的文章中查看ConcurrentHashMap的实现细节。


ConcurrentHashMap通过稍微放松对调用者的承诺来实现更高的并发性。 检索操作将返回由最*完成的插入操作插入的值,并且还可能返回由并发进行中的插入操作添加的值(但决不会返回无意义的结果)。 由ConcurrentHashMap.iterator()返回的Iterators将最多返回每个元素一次,并且永远不会抛出ConcurrentModificationException ,但是可能反映出自构造迭代器以来发生的插入或删除。 在迭代集合时,不需要(甚至可能没有)表范围的锁定来提供线程安全性。 ConcurrentHashMap ,可以用作替代synchronizedMapHashtable在不依靠锁定整个表,以防止更新能力的任何应用程序。


这些折衷方案使ConcurrentHashMap能够提供比Hashtable更好的可伸缩性,而不会在诸如共享缓存之类的多种常见情况下损害其有效性。


好多了?

表1给出了HashtableConcurrentHashMap之间的可伸缩性差异的粗略概念。 在每次运行中, n个线程同时执行一个紧密循环,其中他们从HashtableConcurrentHashMap检索随机键值,其中80%的失败检索执行put()操作,而1%的成功检索执行remove() 。 测试是在运行Linux的双处理器Xeon系统上进行的。 数据显示10,000,000次迭代的运行时间(以毫秒为单位),已标准化为ConcurrentHashMap的1线程情况。 您可以看到ConcurrentHashMap的性能可扩展到许多线程,而Hashtable的性能几乎在存在锁争用时立即下降。


与典型的服务器应用程序相比,此测试中的线程数可能看起来很小。 但是,由于每个线程除了重复敲击表外什么都不做,因此在执行大量实际工作的情况下,使用表模拟了更多线程的争用。


表1. Hashtable与ConcurrentHashMap的可伸缩性
线程数 并发哈希图 哈希表
1个 1.00 1.03
2 2.59 32.40
4 5.58 78.23
8 13.21 163.48
16 27.58 341.21
32 57.27 778.41

CopyOnWriteArrayList

CopyOnWriteArrayList类用于在并发应用程序中遍历大大超过插入或删除操作的并发应用程序中替换ArrayList 。 当使用ArrayList来存储侦听器列表时(例如在AWT或Swing应用程序中,或通常在JavaBean类中),这种情况非常普遍。 (相关的CopyOnWriteArraySet使用CopyOnWriteArrayList来实现Set接口。)


如果您使用普通的ArrayList来存储侦听器列表,只要该列表保持可变并可以被多个线程访问,则必须在迭代过程中锁定整个列表,或者在迭代之前将其克隆,这两个都有重要意义。成本。 相反,无论何时执行变异操作, CopyOnWriteArrayList都会创建列表的新副本,并且保证它的迭代器在构造迭代器时返回列表的状态,并且不会引发ConcurrentModificationException 。 无需在迭代之前克隆列表或在迭代期间锁定列表,因为迭代器看到的列表副本不会更改。 换句话说, CopyOnWriteArrayList包含一个对不可CopyOnWriteArrayList的可变引用,因此只要将该引用保持固定状态,就可以获得不可变性的所有线程安全好处,而无需锁定。


摘要

同步的集合类HashtableVector以及同步的包装器类Collections.synchronizedMapCollections.synchronizedList提供了MapList的基本的有条件线程安全的实现。 但是,有几个因素使它们不适合在高度并发的应用程序中使用-它们的单个集合范围的锁阻碍了可伸缩性,并且经常有必要在迭代过程中将集合锁定相当长的时间,以防止ConcurrentModificationExceptionConcurrentHashMapCopyOnWriteArrayList实现在保留线程安全性的同时提供了更高的并发性,在对调用者的承诺方面有一些小的妥协。 ConcurrentHashMapCopyOnWriteArrayList不一定在您可能使用HashMapArrayList任何地方都有用,但旨在优化特定的常见情况。 许多并发应用程序将从其使用中受益。











翻译自: https://www.ibm.com/developerworks/java/library/j-jtp07233/index.html


相关推荐