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

【Java开源代码栏目提醒】：网学会员--在 Java开源代码编辑为广大网友搜集整理了：第4章 使用开源软件构建并发应用程序 - 大学课件绩等信息，祝愿广大网友取得需要的信息，参考学习。

    

第4章 使用Amino构建并发应用程序2008年度“教育部-IBM精品课程”建设项目IBM公司经费支持重庆大学计算机学院建设2009年3月 导言 在实际的并发线程应用程序中，常常会用到数组、树、图、集合等数据结构，而这些结构也涉及到并发线程所遇到的安全问题。

    采用Amino组件可以很方便地实现线程安全的数据结构。

    本章将介绍Amino组件在Java多线程中的使用。

     章节内容31 开源软件Amino介绍2 Lock-Free数据结构3 应用Amino提供的数据结构4 Amino使用的模式和调度算法5 Amino的简单使用 4.1 开源软件Amino介绍 Amino是Apache旗下的开源软件。

    读者可以访问 http://amino-cbbs.sourceforge.net/得到其最新 版本。

    面向并发编程，它有以下特点：① 可操作性和良好的伸缩性② 跨平台性③ 无论在Java、C或其他流行语言中，编程风格一 致④ 适用于多核的各种操作系统⑤ 可以进行并发编程正确性的测试 4.1 开源软件Amino介绍 Amino Java类库将涉及下面四个方面的内容 ：① 数据结构 该组件将提供一套免锁的集合类。

    ② 并行模式 主要讲解Master-Worker算法③ 并行计算中的一般功能 String、Sequence 和Array 的处理方面 以及处 理树和图的方法④ 原子和STM4.2锁无关（Lock-Free）数据结构 锁无关（Lock-Free）算法 优点：① 对死锁、优先级倒置等问题免疫 它属于非阻塞性同步，因为它不使用锁来协调各 个线程，所以对死锁、优先级倒置等由锁引起的问 题免疫② 保证程序的整体进度： 由于锁无关算法避免了死锁等情况出现，所以它 能确保线程是在运行当中，从而确保程序的整体进 度；③ 性能理想 使用锁无关算法可以得到理想的性能提升4.2锁无关（Lock-Free）数据结构 锁无关（Lock-Free）算法的原理 一个“锁无关”的程序能够确保执行它的所有线 程中至少有一个能够继续往下执行。

    这便意味着有 些线程可能会被任意地延迟，然而在每一步都至少 有一个线程能够往下执行。

    尽管有些线程的进度可 能不如其它线程来得快，但系统作为一个整体总是 在“前进”的。

    而基于锁的程序则无法提供上述的任 何保证。

     而在锁无关多线程编程的世界里，几乎任何操 作都是无法原子地完成的。

    只有很小一集操作可以 被原子地进行，这一限制使得锁无关编程的难度大 大地增加了。

    4.2锁无关（Lock-Free）数据结构 锁无关（Lock-Free）算法的实现 2003年，Maurice Herlihy因他在1991年发表 的开创性论文“Wait-Free Synchronization” （ http://www.podc.org/dijkstra/2003.html）而 获得了分布式编程的Edsger W. Dijkstra奖。

    在论 文中，Herlihy证明了哪些原语对于构造锁无关数 据结构来说是好的，哪些则是不好的。

    他证明了一 些简单的结构就足以实现出任何针对任意数目的线 程的锁无关算法。

     Herlihy 证明了原语Compare-and-swap （CAS） 是实现锁无关数据结构的通用原语 。

     4.2锁无关Lock-Free数据结构 什么是CAS CAS 可以原子地比较一个内存位置的内容及 一个期望值，如果两者相同，则用一个指定值取替 这个内存位罝里的内容，并且提供结果指示这个操 作是否成功。

    很多现代的处理器已经提供了 CAS 的硬件实现，例如在 x86 架构下的 CMPXCHG8 指令。

    而在 Java 下，位于 java.util.concurrent. atomic 内的 AtomicReference 类亦提供了 CAS 原语的实现，并且有很多其他的扩展功能。

     Amino可以提供基于锁无关的数据结构 4.3 应用Amino提供的数据结构 Amino提供的功能 Amino Java并发类库提供了应用程序常用的 一些数据结构，如集合、树和图等。

     由于Amino目前的版本为0.31作者写稿时， 还处于茁壮成长期，虽然已经实现了最基本的数据 结构，但还有很多的功能需要完善 下面举例说明Amino简单的应用 4.3 应用Amino提供的数据结构 Amino提供的功能 Amino Java并发类库提供了应用程序常用的 一些数据结构，如集合、树和图等。

     由于Amino目前的版本为0.31作者写稿时， 还处于茁壮成长期，虽然已经实现了最基本的数据 结构，但还有很多的功能需要完善 下面举例说明Amino简单的应用 Amino Java并发库 集合（ListQueque等 ）Amino Java 并发库 树tree 图Graph 4.3.1 简单集合 在Amino并发类库提供了 ListQuequeSetVectorDirctionaryStackDeque 等数据结构，采用Lock-Free数据结构，可以确保 线程安全。

    例4-1 关于LockFreeList 的简单例子 LockFreeList实现了并发线程安全的List数据结 构。

    在java.util.包中，List接口继承了Collection并 声明了类集的新特性。

    使用一个基于零的下标，元 素可以通过它们在列表中的位置被插入和访问。

    一 个列表可以包含重复元素。

     例4-1完整的LockFreeList程序 package org.amino.test import java.util.List import java.util.concurrent.ExecutorService import java.util.concurrent.Executors import java.util.concurrent.TimeUnit import java.util.concurrent.atomic.AtomicInteger import org.amino.ds.lockfree.LockFreeList // Amino提供的无锁数据结构public class ListTest private static final int ELEMENT_NUM 80 public static void mainString argvs 例4-1完整的LockFreeList程序ExecutorService exec Executors.newCachedThreadPool final List listStr new LockFreeList for int i 0 i ELEMENT_NUM i exec.submitnew ListInsTasklistStr exec.shutdown try exec.awaitTermination500 TimeUnit.SECONDS catch InterruptedException e e.printStackTrace 例4-1完整的LockFreeList程序 System.out.printlnSize of list is listStr.size for int i 1 i