当前访客身份：游客 [
“ 及尽繁华 不过一掬细沙 只望淡泊名利 自在一生 奈何凡尘俗世之杂碎琐事 竟有我舍之不去的牵挂 故 始终俗人！ ”
：package com.wy.controller. import com....
：仍然取不到啊. org.springframework.beans.facto...
：不需要在IDEA中配置吗？
：引用来自“蓝天之云”的评论 你的org.apache.co...
：你的mons.httpclient的jar包可以发...
今日访问：6
昨日访问：5
本周访问：6
本月访问：155
所有访问：8288
CAS原理 Java SE1.6中的Synchronized
发表于2年前( 16:25)&&
阅读（1613）&|&评论（）
0人收藏此文章,
在多线程并发编程中Synchronized一直是元老级角色，很多人都会称呼它为重量级锁，但是随着Java SE1.6对Synchronized进行了各种优化之后，有些情况下它并不那么重了，本文详细介绍了Java SE1.6中为了减少获得锁和释放锁带来的性能消耗而引入的偏向锁和轻量级锁，以及锁的存储结构和升级过程。
在JDK 5之前Java语言是靠synchronized关键字保证同步的，这会导致有锁（后面的章节还会谈到锁）。
锁机制存在以下问题：
（1）在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题。
（2）一个线程持有锁会导致其它所有需要此锁的线程挂起。
（3）如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。
volatile是不错的机制，但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。
独占锁是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。
上面的乐观锁用到的机制就是CAS，Compare and Swap。
CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
非阻塞算法 （nonblocking algorithms）
一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。
现代的CPU提供了特殊的指令，可以自动更新共享数据，而且能够检测到其他线程的干扰，而 compareAndSet() 就用这些代替了锁定。
拿出AtomicInteger来研究在没有锁的情况下是如何做到数据正确性的。
首先毫无以为，在没有锁的机制下可能需要借助volatile原语，保证线程间的数据是可见的（共享的）。这样才获取变量的值的时候才能直接读取。
public final int get() { &&&&&&& &&& }
然后来看看++i是怎么做到的。
public final int incrementAndGet() { &&& for (;;) { &&&&&&& int current = get(); &&&&&&& int next = current + 1; &&&&&&& if (compareAndSet(current, next)) &&&&&&&&&&& &&& } }
在这里采用了CAS操作，每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作，如果成功就返回结果，否则重试直到成功为止。
而compareAndSet利用JNI来完成CPU指令的操作。
public final boolean compareAndSet(int expect, int update) {&&& &&& pareAndSwapInt(this, valueOffset, expect, update); &&& }
整体的过程就是这样子的，利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。
而整个J.U.C都是建立在CAS之上的，因此对于synchronized阻塞算法，J.U.C在性能上有了很大的提升。
CAS看起来很爽，但是会导致“ABA问题”。
CAS算法实现一个重要前提需要取出内存中某时刻的数据，而在下时刻比较并替换，那么在这个时间差类会导致数据的变化。
比如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且two进行了一些操作变成了B，然后two又将V位置的数据变成A，这时候线程one进行CAS操作发现内存中仍然是A，然后one操作成功。尽管线程one的CAS操作成功，但是不代表这个过程就是没有问题的。如果链表的头在变化了两次后恢复了原值，但是不代表链表就没有变化。因此前面提到的原子操作AtomicStampedReference/AtomicMarkableReference就很有用了。这允许一对变化的元素进行原子操作。
可扩展阅读：/java-synchronized/
本文属作者原创，原文发表于InfoQ：
在多线程并发编程中Synchronized一直是元老级角色，很多人都会称呼它为重量级锁，但是随着Java SE1.6对Synchronized进行了各种优化之后，有些情况下它并不那么重了，本文详细介绍了Java SE1.6中为了减少获得锁和释放锁带来的性能消耗而引入的偏向锁和轻量级锁，以及锁的存储结构和升级过程。
2 术语定义
Compare and Swap
比较并设置。用于在硬件层面上提供原子性操作。在&Intel&处理器中，比较并交换通过指令cmpxchg实现。比较是否和给定的数值一致，如果一致则修改，不一致则不修改。
3 同步的基础
Java中的每一个对象都可以作为锁。
对于同步方法，锁是当前实例对象。
对于静态同步方法，锁是当前对象的Class对象。
对于同步方法块，锁是Synchonized括号里配置的对象。
当一个线程试图访问同步代码块时，它首先必须得到锁，退出或抛出异常时必须释放锁。那么锁存在哪里呢？锁里面会存储什么信息呢？
4 同步的原理
JVM规范规定JVM基于进入和退出Monitor对象来实现方法同步和代码块同步，但两者的实现细节不一样。代码块同步是使用monitorenter和monitorexit指令实现，而方法同步是使用另外一种方式实现的，细节在JVM规范里并没有详细说明，但是方法的同步同样可以使用这两个指令来实现。monitorenter指令是在编译后插入到同步代码块的开始位置，而monitorexit是插入到方法结束处和异常处， JVM要保证每个monitorenter必须有对应的monitorexit与之配对。任何对象都有一个 monitor 与之关联，当且一个monitor 被持有后，它将处于锁定状态。线程执行到 monitorenter 指令时，将会尝试获取对象所对应的 monitor 的所有权，即尝试获得对象的锁。
4.1 Java对象头
锁存在Java对象头里。如果对象是数组类型，则虚拟机用3个Word（字宽）存储对象头，如果对象是非数组类型，则用2字宽存储对象头。在32位虚拟机中，一字宽等于四字节，即32bit。
存储对象的hashCode或锁信息等。
Class Metadata Address
存储到对象类型数据的指针
Array length
数组的长度（如果当前对象是数组）
Java对象头里的Mark Word里默认存储对象的HashCode，分代年龄和锁标记位。32位JVM的Mark Word的默认存储结构如下：
1bit是否是偏向锁
2bit锁标志位
对象的hashCode
对象分代年龄
在运行期间Mark Word里存储的数据会随着锁标志位的变化而变化。Mark Word可能变化为存储以下4种数据：
是否是偏向锁
指向栈中锁记录的指针
指向互斥量（重量级锁）的指针
对象分代年龄
在64位虚拟机下，Mark Word是64bit大小的，其存储结构如下：
ThreadID(54bit) Epoch(2bit)
4.2 锁的升级
Java SE1.6为了减少获得锁和释放锁所带来的性能消耗，引入了“偏向锁”和“轻量级锁”，所以在Java SE1.6里锁一共有四种状态，无锁状态，偏向锁状态，轻量级锁状态和重量级锁状态，它会随着竞争情况逐渐升级。锁可以升级但不能降级，意味着偏向锁升级成轻量级锁后不能降级成偏向锁。这种锁升级却不能降级的策略，目的是为了提高获得锁和释放锁的效率，下文会详细分析。
4.3 偏向锁
Hotspot的作者经过以往的研究发现大多数情况下锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。当一个线程访问同步块并获取锁时，会在对象头和栈帧中的锁记录里存储锁偏向的线程ID，以后该线程在进入和退出同步块时不需要花费CAS操作来加锁和解锁，而只需简单的测试一下对象头的Mark Word里是否存储着指向当前线程的偏向锁，如果测试成功，表示线程已经获得了锁，如果测试失败，则需要再测试下Mark Word中偏向锁的标识是否设置成1（表示当前是偏向锁），如果没有设置，则使用CAS竞争锁，如果设置了，则尝试使用CAS将对象头的偏向锁指向当前线程。
偏向锁的撤销：偏向锁使用了一种等到竞争出现才释放锁的机制，所以当其他线程尝试竞争偏向锁时，持有偏向锁的线程才会释放锁。偏向锁的撤销，需要等待全局安全点（在这个时间点上没有字节码正在执行），它会首先暂停拥有偏向锁的线程，然后检查持有偏向锁的线程是否活着，如果线程不处于活动状态，则将对象头设置成无锁状态，如果线程仍然活着，拥有偏向锁的栈会被执行，遍历偏向对象的锁记录，栈中的锁记录和对象头的Mark Word要么重新偏向于其他线程，要么恢复到无锁或者标记对象不适合作为偏向锁，最后唤醒暂停的线程。下图中的线程1演示了偏向锁初始化的流程，线程2演示了偏向锁撤销的流程。
关闭偏向锁：偏向锁在Java 6和Java 7里是默认启用的，但是它在应用程序启动几秒钟之后才激活，如有必要可以使用JVM参数来关闭延迟-XX：BiasedLockingStartupDelay = 0。如果你确定自己应用程序里所有的锁通常情况下处于竞争状态，可以通过JVM参数关闭偏向锁-XX:-UseBiasedLocking=false，那么默认会进入轻量级锁状态。
4.4 轻量级锁
轻量级锁加锁：线程在执行同步块之前，JVM会先在当前线程的栈桢中创建用于存储锁记录的空间，并将对象头中的Mark Word复制到锁记录中，官方称为Displaced Mark Word。然后线程尝试使用CAS将对象头中的Mark Word替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，表示其他线程竞争锁，当前线程便尝试使用自旋来获取锁。
轻量级锁解锁：轻量级解锁时，会使用原子的CAS操作来将Displaced Mark Word替换回到对象头，如果成功，则表示没有竞争发生。如果失败，表示当前锁存在竞争，锁就会膨胀成重量级锁。下图是两个线程同时争夺锁，导致锁膨胀的流程图。
因为自旋会消耗CPU，为了避免无用的自旋（比如获得锁的线程被阻塞住了），一旦锁升级成重量级锁，就不会再恢复到轻量级锁状态。当锁处于这个状态下，其他线程试图获取锁时，都会被阻塞住，当持有锁的线程释放锁之后会唤醒这些线程，被唤醒的线程就会进行新一轮的夺锁之争。
5 锁的优缺点对比
加锁和解锁不需要额外的消耗，和执行非同步方法比仅存在纳秒级的差距。
如果线程间存在锁竞争，会带来额外的锁撤销的消耗。
适用于只有一个线程访问同步块场景。
竞争的线程不会阻塞，提高了程序的响应速度。
如果始终得不到锁竞争的线程使用自旋会消耗CPU。
追求响应时间。
同步块执行速度非常快。
线程竞争不使用自旋，不会消耗CPU。
线程阻塞，响应时间缓慢。
追求吞吐量。
同步块执行速度较长。
6 参考源码
本文一些内容参考了源码 。对象头源码markOop.hpp。偏向锁源码biasedLocking.cpp。以及其他源码ObjectMonitor.cpp和BasicLock.cpp。
7 参考资料
&Synchronization Optimization章节
Dave Dice&
（全文完）如果您喜欢此文请点赞，分享，评论。
更多开发者职位上
1)">1)">1" ng-class="{current:{{currentPage==page}}}" ng-repeat="page in pages"><li class='page' ng-if="(endIndex<li class='page next' ng-if="(currentPage
相关文章阅读聚合国内IT技术精华文章，分享IT技术精华，帮助IT从业人士成长
>> 技术文章 >> 正文
[原]【原创】无锁编程技术及实现
浏览: 3164 次
无锁编程技术及实现作者：jx （360电商技术组）&1.基于锁的编程的缺点&多线程编程是多CPU系统在中应用最广泛的一种编程方式，在传统的多线程编程中，多线程之间一般用各种锁的机制来保证正确的对共享资源（share&resources）进行访问和操作。在多线程编程中只要需要共享某些数据，就应当将对它的访问串行化。比如像++count(count是整型变量)这样的简单操作也得加锁，因为即便是增量操作这样的操作，，实际上也是分三步进行的：读、改、写（回）。movl&x,&%eaxaddl&$1,&%eaxmovl&%eax,&x更进一步，甚至内存变量的赋值操作都不能保证是原子的，比如在32位环境下运行这样的函数void&setValue()&{&&&&&&value&=&0x6;&}执行的过程中，这两条指令之间也是可以被打断的，而不是一条原子操作。（也就是所谓的写撕裂）所以修改共享数据的操作必须以原子操作的形式出现，这样才能保证没有其它线程能在中途插一脚来破坏相应数据。而在使用锁机制的过程中，即便在锁的粒度（granularity），负载（overhead），竞争（contention），死锁（deadlock）等需要重点控制的方面解决的很好，也无法彻底避免这种机制的如下一些缺点：1，&锁机制会引起线程的阻塞（block），对于没有能占用到锁的线程或者进程，将一直等待到锁的占有者释放锁资源后才能继续执行，而等待时间理论上是不可设置和预估的。2，&申请和释放锁的操作，增加了很多访问共享资源的消耗，尤其是在锁竞争(lock-contention)很严重的时候，比如这篇文章所说：3，&现有实现的各种锁机制，都不能很好的避免编程开发者设计实现的程序出现死锁或者活锁的可能4，&优先级反转（prorithy&inversion）和锁护送(Convoying)的现象5，&难以调试无锁编程（Lock-Free）就是在某些应用场景和领域下解决以上基于锁机制的并发编程的一种方案。&2.无锁编程(LOCK-FREE)的定义& & 提到无锁编程（lock-free），按字面最直观的理解是不使用锁的情况下实现多线程之间对变量同步和访问的一种程序设计实现方案。严格的说这个理解是不对的，Lock-Free的程序肯定是不包括锁机制的，而不包括锁机制的程序不一定是lock-free的。&更准确的说，在并发编程上按照同步的维护划分，可以分为阻塞的编程方式（Block）和非阻塞的编程方式（Non-blocking&Synchronization）。阻塞的编程方式基本是基于锁的（lock-based）。&其中无锁编程（Lock-free）属于非阻塞同步（Non-blocking&Synchronization）中的一种情况，实现非阻塞同步的算法方案按照效果要求不同可以粗略的分为：Wait-free:&满足等待无关的程序，任何线程可以在有限步之内结束，不管其它线程的执行速度和进度如何Lock-free：锁无关的程序，一个锁无关的程序能够确保它所有线程中至少有一个能够继续往下执行，而有些线程可能会被的延迟。然而在整体上，在某个时刻至少有一个线程能够执行下去。作为整体进程总是在前进的，尽管有些线程的进度可能没有其它线程进行的快。Obstruction-free：在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行。一旦共享数据被修改，Obstruction-free&要求中止已经完成的部分操作进行回滚。&更细致的还可以把并发编程按效果划分为:Blocking&&&&1.&Blocking&&&&&2.&Starvation-FreeObstruction-Free&&&&3.&Obstruction-FreeLock-Free&&&&4.&Lock-Free&(LF)Wait-Free&&&&5.&Wait-Free&(WF)&&&&&&6.&Wait-Free&Bounded&(WFB)&&&&7.&Wait-Free&Population&Oblivious&(WFPO)具体细节可以参考这篇文章，有对阻塞非阻塞的等定义的详细描述，这里不详细论述。&&3.无锁编程中涉及的一些技术原理&无锁编程具体使用和考虑到的技术方法包括：原子操作（atomic&operations）,&内存栅栏（memory&barriers）,&内存顺序冲突（memory&order），&指令序列一致性（sequential&consistency）和顺ABA现象等等，这方面借用一篇资料的总结的图概况：&&&在这其中最基础最重要的是操作的原子性或说原子操作。原子操作可以理解为在执行完毕之前不会被任何其它任务或事件中断的一系列操作。原子操作是非阻塞编程最核心基本的部分，没有原子操作的话，操作会因为中断异常等各种原因引起数据状态的不一致从而影响到程序的正确。对于原子操作的实现机制，在硬件层面上CPU处理器会默认保证基本的内存操作的原子性，CPU保证从系统内存当中读取或者写入一个字节的行为肯定是原子的，当一个处理器读取一个字节时，其他CPU处理器不能访问这个字节的。但是对于复杂的内存操作CPU处理器不能自动保证其原子性，比如跨总线宽度或者跨多个缓存行（Cache&Line），跨页表的访问等。这个时候就需要用到CPU指令集中设计的原子操作指令，现在大部分CPU指令集都会支持一系列的原子操作。而在无锁编程中经常用到的原子操作是Read-Modify-Write&&（RMW）这种类型的，这其中最常用的原子操作又是&COMPARE&AND&SWAP（CAS），几乎所有的CPU指令集都支持CAS的原子操作，比如X86平台下中的是&CMPXCHG。继续说一下CAS，CAS操作行为是比较某个内存地址处的内容是否和期望值一致，如果一致则将该地址处的数值替换为一个新值。CAS能够操作的位数越多，使用它来实现锁无关的数据结构就越容易（细节可以在intel手册中查看）。CAS操作具体的实现原理主要是两种方式：总线锁定和缓存锁定。所谓总线锁定，就是CPU执行某条指令的时候先锁住数据总线的，&使用同一条数据总线的CPU就无法访问内存了，在指令执行完成后再释放锁住的数据总线。锁住数据总线的方式系统开销很大，限制了访问内存的效率，所以又有了基于CPU缓存一致性来保持操作原子性作的方法作为补充，简单来说就是用CPU的缓存一致性的机制来防止内存区域的数据被两个以上的处理器修改（可详见CPU缓存的MESI协议）。在操作系统的层面，Linux系统提供了软件级的原子操作，包括两大类系统调用，一类是基于对整数进行操作的atomic_set/and/inc，一类是针对单独的位进行操作的set/clear/change_bit，它们大部分都是基于硬件层面的CAS的指令实现的。在各种开发语言中（c,c++,java）基于操作系统提供的接口也都封装实现了对应的原子操作api，所以开发者完全可以直接调用各个开发语言提供的接口实现无锁程序。除了使用原子操作保证操作的原子性，还要考虑在不用的语言和内存模型下，如何保证，操作的顺序性，&编译时和运行时的指令重排序，还有由假共享引起内存顺序冲突（Memory&order&violation）等等细节。原子性确保指令执行期间不被打断，要么全部执行，要么根本不执行，而顺序性确保即使两条或多条指令出现在独立的执行线程中或者独立的处理器上时，保持它们本该执行的顺序。假共享是指多个CPU同时修改同一个缓存行的不同部分而引起其中一个CPU的操作无效，当出现这个内存顺序冲突时，CPU必须清空流水线。这些其实在多核编程的环境下的locked-base的实现中也有类似的问题所以这里就不多展开。&&4.几个例子&John&D.&Valois&《》中提到的一个基于链表的无锁队列链表的实现，可以作为了解lock-free一个例子&EnQueue(x)&{&//入队列方法&&&&q&=&new&record();&&&&q-&value&=&x;&//队列节点的值&&&&q-&next&=&NULL;//下一个节点&&&&p&=&&//保存尾节点指针&&&&oldp&=&p;&&&&do&{&//开始&loop&&cas&&&&&&&&&while&(p-&next&!=&NULL)&//用来防止进行cas（tail,oldp,q）操作的线程挂掉引起死循环&&&&&&&&&&&&p&=&p-&&&&&}&while(&CAS(p.next,&NULL,&q)&!=&TRUE);&CAS(tail,&oldp,&q);&}&DeQueue()&//出队列方法{&&&&do{&&&&&&&&p&=&&&&&&&&&if&(p-&next&==&NULL){&&&&&&&&&&&&return&ERR_EMPTY_QUEUE;&&&&&&&&}&&&&while(&CAS(head,&p,&p-&next)&!=&TRUE&);&&&&return&p-&next-&}&具体实现中，在linux&平台上gcc编译器（内置了支持cas操作的函数，或者直接调用汇编命令（比如CMPXCHG&和&CMPXCHG8B）也可以在c程序里实现cas操作。GCC&(GNU&Compiler&Collection，4.1&和更高版本）提供几个内置函数，可以使用它们在&x86&和&x86-64&平台上实现&CAS&操作，这些内置函数包括：&type&__sync_fetch_and_add&(type&*ptr,&type&value)&&&&&&&&&type&__sync_fetch_and_sub&(type&*ptr,&type&value)&&&&&&&&&&&&type&__sync_fetch_and_or&(type&*ptr,&type&value)&&&&&&&&type&__sync_fetch_and_and&(type&*ptr,&type&value)type&__sync_fetch_and_xor&(type&*ptr,&type&value)type&__sync_fetch_and_nand&(type&*ptr,&type&value)type&__sync_add_and_fetch&(type&*ptr,&type&value)type&__sync_sub_and_fetch&(type&*ptr,&type&value)type&__sync_or_and_fetch&(type&*ptr,&type&value)type&__sync_and_and_fetch&(type&*ptr,&type&value)type&__sync_xor_and_fetch&(type&*ptr,&type&value)type&__sync_nand_and_fetch&(type&*ptr,&type&value)bool&__sync_bool_compare_and_swap&(type&*ptr,&type&oldval&type&newval,&...)type&__sync_val_compare_and_swap&(type&*ptr,&type&oldval&type&newval,&...)type&__sync_lock_test_and_set&(type&*ptr,&type&value,&...)更多细节分析可参看John&D.&Valois的&《》&同样，在java语言中Lock-Free的数据结构和算法其实更加常见，在java.util.concurrent包中大量实现都是建立在基于CAS实现Lock-Free算法上，没有CAS就不会有此包。Java.util.concurrent.atomic提供了基于CAS实现的若干原语：&AtomicBoolean&--&原子布尔AtomicInteger&--&原子整型AtomicIntegerArray&--&原子整型数组AtomicLong&--&原子长整型AtomicLongArray&--&原子长整型数组AtomicReference&--&原子引用AtomicReferenceArray&--&原子引用数组AtomicMarkableReference&--&原子标记引用AtomicStampedReference&--&原子戳记引用AtomicIntegerFieldUpdater&--&用来包裹对整形&volatile&域的原子操作AtomicLongFieldUpdater&--&用来包裹对长整型&volatile&域的原子操作AtomicReferenceFieldUpdater&--&用来包裹对对象&volatile&域的原子操作&引入这些类的主要目的就是为了实现Lock-Free算法和相关数据结构，以incrementAndGet这个方法为例：&public&final&int&incrementAndGet()&{&&&&for&(;;)&{&&&&&&&&int&current&=&get();&&&&&&&&int&next&=&current&+&1;&&&&&&&&if&(compareAndSet(current,&next))&&&&&&&&&&&&return&&&&&}}&在这里使用CAS原子操作，每次读取数据数值后将此数值和+1后的结果进行CAS操作，如果成功就返回结果，否则重试到成功为止。其中compareAndSet是java中实现的CAS函数，在java语言中的实现，是借助JNI机制来调用汇编实现的：public&final&boolean&compareAndSet(int&expect,&int&update)&{&&&&&&&return&pareAndSwapInt(this,&valueOffset,&expect,&update);}&pareAndSwapInt是个本地方法调用，对应的x86处理器的jni源码&#define&LOCK_IF_MP(mp)&__asm&cmp&mp,&0&&&&&&&&&__asm&je&L0&&&&&&&&&&&&&__asm&_emit&0xF0&&&&&&&&__asm&L0:inline&jint&&&Atomic::cmpxchg&&&&(jint&&exchange_value,&volatile&jint*&&&&&dest,&jint&&compare_value)&{//&alternative&for&InterlockedCompareExchange&int&mp&=&os::is_MP();__asm&{mov&edx,&dest&mov&ecx,&exchange_value&mov&eax,&compare_valueLOCK_IF_MP(mp)//判断是否是多核，是则添加LOCK指令维护顺序一致性cmpxchg&dword&ptr&[edx],&ecx}}&&再看看在java里无锁队列的实现作为对比参照：&import&java.util.concurrent.atomic.AtomicRpublic&class&LockFreeQueue&T&&{&private&AtomicReference&Node&&&//可以规避ABA现象private&AtomicReference&Node&&&/**&&*&Create&a&new&object&of&this&class.&&*/&public&LockFreeQueue()&{&&Node&sentinel&=&new&Node(null);&　&head&=&new&AtomicReference&Node&(sentinel);&　&tail&=&new&AtomicReference&Node&(sentinel);&}&/**&&*&Enqueue&an&item.&&*&@param&value&Item&to&enqueue.&&*/&public&void&enq(T&value)&{&　&//&try&to&allocate&new&node&from&local&pool&　&Node&node&=&new&Node(value);&　&while&(true)&{　　　　　　　&　　&Node&last&=&tail.get();　&　　&Node&next&=&last.next.get();　　&//&are&they&consistent&　　&if&(last&==&tail.get())&{&　　　&if&(next&==&null)&{　　&　　　　&//&try&to&link&node&to&end&of&list&　　　　&if&(laspareAndSet(next,&node)&{&　　　　　&//&enq&done,&try&to&advance&tail&　　　　　&pareAndSet(last,&node);&　　　　　&&　　　　&}&　　　&}&else&{　　　　　　　&　　　　&//&try&to&swing&tail&to&next&node&　　　　&pareAndSet(last,&next);&　　　&}&　　&}&　&}&}&&/**&&*&Dequeue&an&item.&&*&@throws&queue.EmptyException&The&queue&is&empty.&&*&@return&Item&at&the&head&of&the&queue.&&*/&public&T&deq()&throws&EmptyException&{&　&while&(true)&{&　　&Node&first&=&head.get();&　　&Node&last&=&tail.get();&　　&Node&next&=&first.next.get();&　　&//&are&they&consistent&　　&if&(first&==&head.get())&{&　　　&if&(first&==&last)&{　&　　　　&if&(next&==&null)&{　&　　　　　&throw&new&EmptyException();&　　　　&}&　　　　&//&tail&is&behind,&try&to&advance&　　　　&pareAndSet(last,&next);&　　　&}&else&{&　　　　&T&value&=&next.&　　　　&if&(pareAndSet(first,&next))&{&　　　　　&return&&　　　　&}&　　　&}&　　&}&　&}&}&/**&&*&Items&are&kept&in&a&list&of&nodes.&&*/&public&class&Node&{&　&/**&　　&*&Item&kept&by&this&node.&　　&*/&　&public&T&&　&/**&　　&*&Next&node&in&the&queue.&　　&*/&　&public&AtomicReference&Node&&　　/**&　　&*&Create&a&new&node.&　　&*/&　&public&Node(T&value)&{&　　&this.next&=&new&AtomicReference&Node&(null);&　　&this.value&=&&　&}&}&&最后这里随便说一下CAS操作的ABA的问题，所谓的ABA的问题简要的说就是，线程a先读取了要对比的值v后，被线程b抢占了，线程b对v进行了修改后又改会v原来的值，线程1继续运行执行CAS操作的时候，无法判断出v的值被改过又改回来。ABA对基于指针实现的算法影响很大。上面的C语言里实现的程序是有可能被ABA问题影响的，因为它的CAS操作判断的是指针的地址，这个地址被重用的可能性很大（地址被重用是很经常发生的，一个内存分配后释放了，再分配，很有可能还是原来的地址，内存管理中重用内存基本上是一种很常见的行为）。解决ABA的问题的一种方法是，一次用CAS检查双倍长度的值，前半部是指针，后半部分是一个计数器；或者对CAS的数值加上版本号。&《》也有提到相关的解决方案。&5.结论和建议&无锁编程方式相对基于锁的编程方式，具备一定的优点，比如不会发生死锁，不会有优先级倒置，进行CAS操作的消耗比加锁操作轻很多等等。单从这个角度上讲在对应用程序不太复杂，而对操作实时性要求较高时，采用无锁多线程能发挥一定优势。在性能上基于CAS实现的硬件级的互斥，其单次操作性能比相同条件下的应用层的较为高效，但当多个线程并发时，硬件级的互斥引入的消耗一样很高(类似spin_lock)。&无锁算法及相关数据结构并不意味在所有的环境下都能带来整体性能的极大提升。循环CAS操作对时会大量占用cpu，对系统时间的开销也是很大。这也是基于循环CAS实现的各种自旋锁不适合做操作和等待时间太长的并发操作的原因。而通过对有锁程序进行合理的设计和优化，在很多的场景下更容易使程序实现高度的并发性。在开发维护的成本和复杂度上，无锁编程难度非常高，类似ABA的问题也比较难直观的探测和解决，并且实现细节和硬件平台相关性很强。目前理论和实践上只有少数数据结构可以支持实现无锁编程，比如队列、栈、链表、词典等，目前要在产品业务开发环境中进行大规模的无锁编程较为困难，更多的是用在部分特殊场景解决锁竞争等问题比较合适，比如操作系统中实现metux，semaphare,&一些语言的库的实现（比如&java&current&lib，&lmax&disprute）。若想在应用开发中尝试的Lock-Free的方案，建议可以选择合适的第三方lib实现。&附一. 些常见的相关lib库工具/mthssdrbrg/LockFreeStack&& &&http://www.cse.chalmers.se/research/group/noble/& &&& &&&&&& &&&&附二. 参考资料和进阶阅读;Writing&Lock-Free&Code:&A&Corrected&QueueThe&Trouble&With&LocksIntel&64&and&IA-32&Architectures&Software&Developer’s&ManualThe&Art&of&Multiprocessor&ProgrammingLock-Free&Techniques&for&Concurrent&Access&to&Shared&ObjectsLock-Free&Linked&Lists&Using&Compare-and-SwapCAS-Based&Lock-Free&Algorithm&for&Shared&Deques&&&&&&&&-------------------------------------------------------------------------------------黑夜路人，一个关注开源技术、乐于学习、喜欢分享的程序员博客：http://blog.csdn.net/heiyeshuwu微博：微信：heiyeluren2012 &想获取更多IT开源技术相关信息，欢迎关注微信！微信二维码扫描快速关注本号码：
本页关键字}