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

第4章使用开源软件构建并发应用程序第4章使用开源软件构建并发应用程序................................14.1开源软件Amino介绍...........................................24.2无锁（Lock-Free）数据结构...................................34.3应用Amino提供的数据结构.....................................64.3.1简单集合...............................................64.3.2树....................................................114.3.3图....................................................134.4Amino使用的模式和调度算法..................................144.5Amino的简单使用............................................17参考资料：........................................................20在实际的并发线程应用程序中，常常会用到数组、树、图、集合等数据结构，而这些结构也涉及到并发线程所遇到的安全问题。采用Amino组件可以很方便地实现线程安全的数据结构。本章将介绍Amino组件在Java多线程中的使用。4.1开源软件Amino介绍Amino是Apache旗下的开源软件。读者可以访问得到其昀新版本。面向并发编程，它有以下特点：1）可操作性和良好的伸缩性2）跨平台性3）无论在Java、C++或其他流行语言中，编程风格一致4）适用于多核的各种操作系统5）可以进行并发编程正确性的测试本章将介绍Amino的Java版。AminoJava类库将提供优化后的并发线程组件，适用于JDK6.0及其以后的版本。AminoJava类库将涉及下面四个方面的内容：1）数据结构该组件将提供一套免锁的集合类。因为这些数据结构采用免锁的运算法则来生成，所以，它们将拥有基本的免锁组件的特性，如可以避免不同类型的死锁，不同类型的线程初始化顺序等。2）并行模式Amino将为应用程序提供一个或几个大家熟知的并行计算模式。采用这些并行模式可以使开发者起到事半功倍的效果，这些模式包括Master-Worker、Map-reduce、Divideandconquer,Pipeline等，线程调度程序可以与这些模式类协同工作，提供了开发效率。3）并行计算中的一般功能Amino将为应用程序提供并行计算中常用的方法，例如：a.String、Sequence和Array的处理方面。如Sort、Search、Merge、Rank、Compare、Reverse、Shuffle、Rotate和Median等b.处理树和图的方法：如组件连接，树生成，昀短路径，图的着色等4）原子和STM（软件事务内存模型）下面的程序可以简单地演示使用Amino的例子：//LogServerGood.javapackageorg.amino.logserver;importorg.amino.ds.lockfree.LockFreeQueue;publicclassLogServerGood{/*StandardQueueinterface*/privateQueueStringqueue;publicLogServerGood()throwsIOException{/*Aminocomponentsarecompatiblewithstandardinterfacewheneverpossible*/queue=newLockFreeQueueString();}}4.2无锁（Lock-Free）数据结构我们知道，在传统的多线程环境下，我们需要共享某些数据，但为了避免竞争条件引致数据出现不一致的情况，某些代码段需要变成基于锁（Lockbased）的原子操作去执行。加锁可以让某一线程可以独占共享数据，避免竞争条件，确保数据一致性。从好的一面来说，只要互斥体是在锁状态，就可以放心地进行任何操作，不用担心其它线程会闯进来搞坏你的共享数据。然而，正是这种在互斥体的锁状态下可以为所欲为的机制同样也带来了很大的问题。例如，可以在锁期间读键盘或进行某些耗时较长的I/O操作，这种阻塞意味着其它想要占用正占用着的互斥体的线程只能被搁在一旁等着。更糟的是有可能引起死锁。基于锁（Lockbased）的多线程设计更可能引发死锁、优先级倒置、饥饿等情况，令到一些线程无法继续其进度。在Amino类库中，主要算法将使用锁无关的（Lock-Free）的数据结构。锁无关（Lock-Free）算法，顾名思义，即不牵涉锁的使用。这类算法可以在不使用锁的情况下同步各个线程。对比基于锁的多线程设计，锁无关算法有以下优势：z对死锁、优先级倒置等问题免疫：它属于非阻塞性同步，因为它不使用锁来协调各个线程，所以对死锁、优先级倒置等由锁引起的问题免疫；z保证程序的整体进度：由于锁无关算法避免了死锁等情况出现，所以它能确保线程是在运行当中，从而确保程序的整体进度；z性能理想：因为不涉及使用锁，所以在普遍的负载环境下，使用锁无关算法可以得到理想的性能提升。自JDK5推出之后，包java.util.concurrent.atomic中的一组类为实现锁无关算法提供了重要的基础。锁无关数据结构是线程安全的，在使用时无需再编写额外代码去确保竞争条件不会出现。而在锁无关多线程编程的世界里，几乎任何操作都是无法原子地完成的。只有很小一集操作可以被原子地进行，这一限制使得锁无关编程的难度大大地增加了。锁无关编程带来的好处是在线程进展和线程交互方面，借助于锁无关编程，你能够对线程的进展和交互提供更好的保证。经过十几年的发展，锁无关的数据结构已经非常成熟，性能并不逊色于传统的实现方式。虽然编写锁无关算法十分困难的，但因为数据结构是经常被重用的部分，开发者可以使用现成的API（如Amino）轻易让程序进入锁无关的世界。首先，一个“等待无关”的程序可以在有限步之内结束，而不管其它线程的相对速度如何。一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。这便意味着有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行。尽管有些线程的进度可能不如其它线程来得快，但系统作为一个整体总是在“前进”的。而基于锁的程序则无法提供上述的任何保证。一旦任何线程持有了某个互斥体并处于等待状态，那么其它任何想要获取同一互斥体的线程就只好站着干瞪眼；一般来说，基于锁的算法无法摆脱“死锁”或“活锁”的阴影，前者如两个线程互相等待另一个所占有的互斥体，后者如两个线程都试图去避开另一个线程的锁行为，就像两个在狭窄桥面上撞了个照面的家伙，都试图去给对方让路，结果像跳舞似的摆来摆去昀终还是面对面走不过去。2003年，MauriceHerlihy因他在1991年发表的开创性论文“Wait-FreeSynchronization”（）而获得了分布式编程的EdsgerW.Dijkstra奖。在论文中，Herlihy证明了哪些原语对于构造锁无关数据结构来说是好的，哪些则是不好的。他证明了一些简单的结构就足以实现出任何针对任意数目的线程的锁无关算法。例如，Herlihy证明了原语Compare-and-swap（CAS）是实现锁无关数据结构的通用原语。CAS可以原子地比较一个内存位置的内容及一个期望值，如果两者相同，则用一个指定值取替这个内存位罝里的内容，并且提供结果指示这个操作是否成功。很多现代的处理器已经提供了CAS的硬件实现，例如在x86架构下的CMPXCHG8指令。而在Java下，位于java.util.concurrent.atomic内的AtomicReferenceV类亦提供了CAS原语的实现，并且有很多其他的扩展功能。下面我们来简单的了解一下硬件同步指令的工作方式：在进行多处理时，现代CPU都可以通过检测或者阻止其他处理器的并发访问来更新共享内存，昀通用的方法是实现CAS（比较并转换）指令，例如在Intel处理器中CAS是通过cmpxchg指令实现的。CAS操作过程是：当处理器要更新一个内存位置的值的时候，它首先将目前内存位置的值与它所知道的修改前的值进行对比（要知道在多处理的时候，你要更新的内存位置上的值有可能被其他处理更新过，而你全然不知），如果内存位置目前的值与期望的原值相同（说明没有被其他处理更新过），那么就将新的值写入内存位置；而如果不同（说明有其他处理在我不知情的情况下改过这的值咯），那么就什么也不做，不写入新的值（现在昀新的做法是定义内存值的版本号，根据版本号的改变来判断内存值是否被修改，一般情况下，比较内存值的做法已经满足要求了）。CAS的价值所在就在于它是在硬件级别实现的，速度那是相当的快。JDK5.0中的原子类就是利用了现代处理器中的这个特性，可以在不进行锁定的情况下，进行共享属性访问的同步。下面我们将举例说明锁无关栈（Stack）的实现方法。栈能以数组或者链表作为底下的储存结构，虽然采取链表为基础的实现方式会占用多一点空间去储存代表元素的节点，但却可避免处理数组溢出的问题。故此我们将以链表作为栈的基础，本文不打算展开对栈数据结构的论述，仅给出相应的实现代码：//锁无关的栈实现importjava.util.concurrent.atomic.*;classNodeT{NodeTnext;Tvalue;publicNode(Tvalue,NodeTnext){this.next=next;this.value=value;}}publicclassStackT{AtomicReferenceNodeTtop=newAtomicReferenceNodeT();publicvoidpush(Tvalue){booleansucessful=false;while(!sucessful){NodeToldTop=top.get();NodeTnewTop=newNodeT(value,oldTop);sucessful=top.compareAndSet(oldTop,newTop);};}publicTpeek(){returntop.get().value;}publicTpop(){booleansucessful=false;NodeTnewTop=null;NodeToldTop=null;while(!sucessful){oldTop=top.get();newTop=oldTop.next;sucessful=top.compareAndSet(oldTop,newTop);}returnoldTop.value;}}成员数据top的类型为AtomicReferenceNodeT，AtomicReferenceV这个类可以对top数据成员施加CAS操作，亦即是可以允许top原子地和一个期望值比较，两者相同的话便用一个指定值取代。4.3应用Amino提供的数据结构AminoJava并发类库提供了应用程序常用的一些数据结构，如集合、树和图等，下面将分别举例说明。4.3.1简单集合在Amino并发类库提供了List,Queque,Set,Vector,Dirctionary,Stack,Deque等数据结构，采用Lock-Free数据结构，可以确保线程安全。1、List在java.util.*包中，List接口继承了Collection并声明