}
4.2无锁(Lock-Free)数据结构
我们知道,在传统的多线程环境下,我们需要共享某些数据,但为了避免竞争条件引
致数据出现不一致的情况,某些代码段需要变成基于锁(Lockbased)的原子操作去执行。
加锁可以让某一线程可以独占共享数据,避免竞争条件,确保数据一致性。从好的一面来说,只要互斥体是在锁状态,就可以放心地进行任何操作,不用担心其它线程会闯进来搞坏你的共享数据。然而,正是这种在互斥体的锁状态下可以为所欲为的机制同样也带来了很大的问题。例如,可以在锁期间读键盘或进行某些耗时较长的I/O操作,这种阻塞意味着其它想要占用正占用着的互斥体的线程只能被搁在一旁等着。更糟的是有可能引起死锁。基于锁(Lockbased)的多线程
设计更可能引发死锁、优先级倒置、饥饿等情况,令到一些线程无法继续其进度。在Amino类库中,主要算法将使用锁无关的(Lock-Free)的数据结构。锁无关(Lock-Free)算法,顾名思义,即不牵涉锁的使用。这类算法可以在不使用锁的情况下同步各个线程。对比基于锁的多线程设计,锁无关算法有以下优势:d对死锁、优先级倒置等问题免疫:它属于非阻塞性同步,因为它不使用锁来协调各个线程,所以对死锁、优先级倒置等由锁引起的问题免疫;d保证程序的整体进度:由于锁无关算法避免了死锁等情况出现,所以它能确保线程是在运行当中,从而确保程序的整体进度;d性能理想:因为不涉及使用锁,所以在普遍的负载环境下,使用锁无关算法可以
得到理想的性能提升。自JDK5推出之后,包java.util.concurrent.atomic中的一组类为实现锁无关算法提供了
重要的基础。锁无关数据结构是线程安全的,在使用时无需再编写额外代码去确保竞争条件
不会出现。
而在锁无关多线程编程的世界里,几乎任何操作都是无法原子地完成的。只有很小一集操作可以被原子地进行,这一限制使得锁无关编程的难度大大地增加了。锁无关编程带来的好处是在线程进展和线程交互方面,借助于锁无关编程,你能够对线程的进展和交互提供
更好的保证。
经过十几年的发展,锁无关的数据结构已经非常成熟,性能并不逊色于传统的实现方式。虽然编写锁无关算法十分困难的,但因为数据结构是经常被重用的部分,开发者可以使
用现成的API(如Amino)轻易让程序进入锁无关的世界。首先,一个“等待无关”的程序可以在有限步之内结束,而不管其它线程的相对速度如何。一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。这便意味着有些线程可能会被任意地延迟,然而在每一步都至少有一个线程能够往下执行。尽管有些线程的进度可能不如其它线程来得快,但系统作为一个整体总是在“前进”的。而基于锁的程序则无法提供上述的任何保证。一旦任何线程持有了某个互斥体并处于等待状态,那么其它任何想要获取同一互斥体的线程就只好站着干瞪眼;一般来说,基于锁的算法无法摆脱“死锁”或“活锁”的阴影,前者如两个线程互相等待另一个所占有的互斥体,后者如两个线程都试图去避开另一个线程的锁行为,就像两个在狭窄桥面上撞了个照面的家伙,都试图去给对方让路,结果像跳舞似的摆来摆去最终还是面对面走不过去。2003年,MauriceHerlihy因他在1991年发表的开创性论文“Wait-FreeSynchronization”(http://www.podc.org/dijkstra/2003.html)而获得了分布式编程的EdsgerW.Dijkstra奖。在论文中,Herlihy证明了哪些原语对于构造锁无关数据结构来说是好的,哪些则是不好的。他证明了一些简单的结构就足以实现出任何针对任意数目的线程的锁无关算法。例如,Herlihy证明了原语Compare-and-swap(CAS)是实现锁无关数据结构的通用原语。CAS可以原子
地比较一个内存位置的内容及一个期望值,如果两者相同,则用一个指定值取替这个内存位罝里的内容,并且提供结果指示这个操作是否成功。很多现代的处理器已经提供了CAS硬件实现,例如在Javax86下,位于架构下的CMPXCHG8的
指令。而在
java.util.concurrent.atomic内的AtomicReference
类亦提供了CAS原语的实现,并且有很多其他的扩展功能。
下面我们来简单的了解一下硬件同步指令的工作方式:在进行多处理时,现代CPU都可以通过检测或者阻止其他处理器的并发访问来更新共
享内存,最通用的方法是实现CAS(比较并转换)指令,例如在Intel处理器中CAS是通过cmpxchg指令实现的。CAS操作过程是:当处理器要更新一个内存位置的值的时候,它首先将目前内存位置的值与它所知道的修改前的值进行对比(要知道在多处理的时候,你要更新的内存位置上的值有可能被其他处理更新过,而你全然不知),如果内存位置目前的值与期望的原值相同(说明没有被其他处理更新过),那么就将新的值写入内存位置;而如果不同(说明有其他处理在我不知情的情况下改过这的值咯),那么就什么也不做,不写入新的
值(现在最新的做法是定义内存值的版本号,根据版本号的改变来判断内存值是否被修改,一般情况下,比较内存值的做法已经满足要求了)。CAS的价值所在就在于它是在硬件级别实现的,速度那是相当的快。JDK5.0中的原子类就是利用了现代处理器中的这个特性,可
以在不进行锁定的情况下,进行共享属性访问的同步。下面我们将举例说明锁无关栈(Stack)的实现方法。栈能以数组或者链表作为底下的储存结构,虽然采取链表为基础的实现方式会占用多一点空间去储存代表元素的节点,但却可避免处理数组溢出的问题。故此我们将以链表作为栈的基础,本文不打算展开对栈数据结构的论述,仅给出相应的实现代码://锁无关的栈实现importjava.util.concurrent.atomic.*;classNode{Nodenext;Tvalue;publicNode(Tvalue,Nodenext){this.next=next;this.value=value;