第4章使用开源软件构建并发应用程序.pdfVIP

第 4 章 使用开源软件构建并发应用程序 第 4 章 使用开源软件构建并发应用程序 1 4.1 开源软件Amino介绍2 4.2 无锁（Lock-Free）数据结构3 4.3 应用Amino提供的数据结构6 4.3.1 简单集合6 4.3.2 树11 4.3.3 图13 4.4 Amino使用的模式和调度算法14 4.5 Amino的简单使用17 参考资料： 20 在实际的并发线程应用程序中，常常会用到数组、树、图、集合等数据结构，而这些结 构也涉及到并发线程所遇到的安全问题。采用 Amino 组件可以很方便地实现线程安全的数 据结构。本章将介绍 Amino 组件在 Java 多线程中的使用。 4.1 开源软件Amino 介绍 Amino是Apache旗下的开源软件。读者可以访问/得到其 必威体育精装版版本。面向并发编程，它有以下特点： 1）可操作性和良好的伸缩性 2 ）跨平台性 3 ）无论在 Java、C++或其他流行语言中，编程风格一致 4 ）适用于多核的各种操作系统 5 ）可以进行并发编程正确性的测试 本章将介绍 Amino 的Java 版。Amino Java 类库将提供优化后的并发线程组件，适用于 JDK6.0 及其以后的版本。 Amino Java 类库将涉及下面四个方面的内容： 1）数据结构 该组件将提供一套免锁的集合类。因为这些数据结构采用免锁的运算法则来生成，所 以，它们将拥有基本的免锁组件的特性，如可以避免不同类型的死锁，不同类型的线程初始 化顺序等。 2 ）并行模式 Amino 将为应用程序提供一个或几个大家熟知的并行计算模式。采用这些并行模式可 以使开发者起到事半功倍的效果，这些模式包括 Master-Worker 、Map-reduce 、Divide and conquer, Pipeline 等，线程调度程序可以与这些模式类协同工作，提供了开发效率。 3 ）并行计算中的一般功能 Amino 将为应用程序提供并行计算中常用的方法，例如： a. String、Sequence 和 Array 的处理方面。如 Sort、Search、Merge 、Rank 、Compare、 Reverse 、 Shuffle 、Rotate 和 Median 等 b. 处理树和图的方法：如组件连接，树生成，最短路径，图的着色等 4 ）原子和 STM （软件事务内存模型） 下面的程序可以简单地演示使用 Amino 的例子： // LogServerGood.java package org.amino.logserver; import org.amino.ds.lockfree.LockFreeQueue; public class LogServerGood { /*Standard Queue interface*/ private QueueString queue; public LogServerGood() throws IOException { /*Amino components are compatible with standard interface whenever possible*/ queue = new LockFreeQueueString(); } } 4.2 无锁（Lock-Free）数据结构 我们知道，在传统的多线程环境下，我们需要共享某些数据，但为了避免竞争条件引 致数据出现不一致的情况，某些代码段需要变成基于锁（Lock based ）的原子操作去执行。 加锁可以让某一线程可以独占共享数据，避免竞争条件，确保数据一致性。从好的一面来说， 只要互斥体是在锁状态，就可以放心地进行任何操作，不用担心其它线程会闯进来搞坏你的 共享数据。 然而，正是这种在互斥体的锁状态下可以为所欲为的机制同样也带来了很大的问题。 例如，可以在锁期间读键盘或进行某些耗时较长的 I/O 操作，这种阻塞意味着其它想要占用 正占用着的互斥体的线程只能被搁在一旁等着。更糟的是有可能引起死锁。基于锁（Lock based ）的