非阻塞同步算法与CAS(比较和交换)无锁算法 - 美因茨

锁（锁）的代价

锁是用来做并发最简单的方式，当然其代价也是最高的。内核态的锁的时候需要操作系统进行一次上下文切换，加锁，释放锁会导致比较多的上下文切换和调度延时，等待锁的线程会被挂起直至锁释放。在上下文切换的时候，CPU之前缓存的指令和数据都将失效，对性能有很大的损失。用户态的锁虽然避免了这些问题，但是其实它们只是在没有真实的竞争时才有效。

Java的JDK1.5在之前都是靠同步关键字保证同步的，这种通过使用一致的锁定协议来协调对共享状态的访问，可以确保无论哪个线程持有守护变量的锁，都采用独占的方式来访问这些变量，如果出现多个线程同时访问锁，那第一些线线程将被挂起，当线程恢复执行时，必须等待其它线程执行完他们的时间片以后才能被调度执行，在挂起和恢复执行过程中存在着很大的开销。锁还存在着其它一些缺点，当一个线程正在等待锁时，它不能做任何事。如果一个线程在持有锁的情况下被延迟执行，那么所有需要这个锁的线程都无法执行下去。如果被阻塞的线程优先级高，而持有锁的线程优先级低，将会导致优先级反转（优先级倒置）。

乐观锁与悲观锁

独占锁是一种悲观锁，同步就是一种独占锁，它假设最坏的情况，并且只有在确保其它线程不会造成干扰的情况下执行，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。

挥发性的问题

与锁相比，易失性变量是一和更轻量级的同步机制，因为在使用这些变量时不会发生上下文切换和线程调度等操作，但是挥发性变量也存在一些局限：不能用于构建原子的复合操作，因此当一个变量依赖旧值时就不能使用挥发性变量（参考：谈谈volatiile）。

Java中的原子操作（原子操作）

原子操作指的是在一步之内就完成而且不能被中断原子操作在多线程环境中是线程安全的，无需考虑同步的问题在java的中，下列操作是原子操作。：

• 除long和double之外的所有原始类型的赋值
• 所有参考作业
• java.concurrent.Atomic * classes的所有操作
• 所有分配给不稳定的多头和双头

问题来了，为什么长型赋值不是原子操作呢例如？

long foo = 65465498L;

实时上的java会分两步写入这个长变量，先写32位，再写后32位这样就线程不安全了如果改成下面的就线程安全了。：

私人 挥发性 长 foo;

因为挥发性内部已经做了同步。

CAS无锁算法

要实现无锁（无锁）的非阻塞算法有多种实现方法，其中 CAS（比较与交换，比较和交换） 是一种有名的无锁算法.CAS，CPU指令，在大多数处理器架构，包括IA32，空间中采用的都是CAS指令，CAS的语义是“我认为V的值应该为A，如果是，那么将V的值更新为B，否则不修改并告诉V的值实际为多少“CAS项的英文 乐观锁 技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试.CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B.当且仅当预期值阿和内存值V相同时，将内存值V修改为B，否则什么都不做.CAS无锁算法的?实现如下：

int compare_and_swap（int * reg，int oldval，int newval）
{
 原子（）;
 int old_reg_val = * reg ;
 if（old_reg_val == oldval）
 * reg = newval;
 END_ATOMIC（）;
 return old_reg_val;
}

CAS（乐观锁算法）的基本假设前提

CAS比较与交换的伪代码可以表示为：

	do { 
 备份旧数据; 
 基于旧数据构造新数据; 
} while（！CAS（内存地址，备份的旧数据，新数据）） 

就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行;如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出CAS操作是基于共享数据不会被修改的假设，采用了类似于数据库的commit-retry的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

JVM对CAS的支持：AtomicInt，AtomicLong.incrementAndGet（）

在JDK1.5之前，如果不编写明确的代码就无法执行CAS操作，在JDK1.5中引入了底层的支持，在的int，long和对象的引用等类型上都公开了CAS的操作，并且JVM把它们编译为底层硬件提供的最有效的方法，在运行CAS的平台上，运行时把它们编译为相应的机器指令，如果处理器/ CPU不支持CAS指令，那么JVM将使用自旋锁。因此，值得注意的是， CAS解决方案与平台/编译器紧密相关（比如x86架构下其对应的汇编指令是lock cmpxchg，如果想要64Bit的交换，则应使用lock cmpxchg8b。在.NET中我们可以使用Interlocked .CompareExchange函数） 。

在原子类变量中，如java.util.concurrent.atomic中的中的AtomicXXX，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中中的大多数类在实现时都直接或间接的使用了这些原子变量类。

可以看到用AtomicLong.incrementAndGet的性能比用同步高出几倍。

CAS的例子：非阻塞堆栈

比非阻塞自增稍微复杂一点的CAS的例子：非阻塞堆栈/ ConcurrentStack 。 ConcurrentStack 中的 push() 和 pop() 操作在结构上与 NonblockingCounter 上相似，只是做的工作有些冒险，希望在“提交”工作的时候，底层假设没有失效。 push() 方法观察当前最顶的节点，构建一个新节点放在堆栈上，然后，如果最顶端的节点在初始观察之后没有变化，那么就安装新节点。如果CAS失败，意味着另一个线程已经修改了堆栈，那么过程就会重新开始。

在轻度到中度的争用情况下，非阻塞算法的性能会超越阻塞算法，因为CAS的多数时间都在第一次尝试时就成功，而发生争用时的开销也不涉及线程挂起和上下文切换，只多了几个循环迭代。没有争用的C??AS要比没有争用的锁便宜得多（这句话肯定是真的，因为没有争用的锁涉及CAS加上额外的处理），而争用的CAS比争用的锁获取涉及更短的延迟。

在高度争用的情况下（即有多个线程不断争用一个内存位置的时候），基于锁的算法开始提供比非阻塞算法更好的吞吐率，因为当线程阻塞时，它就会停止争用，耐心地等候轮到自己，从而避免了进一步争用。但是，这么高的争用程度并不常见，因为多数时候，线程会把线程本地的计算与争用共享数据的操作分开，从而给其他线程使用共享数据的机会。

CAS的例子3：非阻塞链表

以上的示例（自增计数器和堆栈）都是非常简单的非阻塞算法，一旦掌握了在循环中使用CAS，就可以容易地模仿它们。对于更复杂的数据结构，非阻塞算法要比这些简单示例复杂得多，因为修改链表，树或哈希表可能涉及对多个指针的更新。所以，要构建一个非阻塞的链表，树或哈希表，需要找到一种方式，可以用CAS更新多个指针，同时不会让数据结构处于不一致的状态。

在链表的尾部插入元素，通常涉及对两个指针的更新：“下一个”指针从过去的最后一个元素指向新插入的元素。因为需要更新两个指针，所以需要两个CAS。在独立的CAS中更新两个指针带来了两个需要考虑的潜在问题：如果第一个CAS成功，而第二个CAS失败，会发生什么？如果其他线程在第一个和第二个CAS之间企图访问链表，会发生什么？

对于非复杂数据结构，构建非阻塞算法的“技巧”是确保数据结构总处于一致的状态（甚至包括在线程开始修改数据结构和它完成修改之间），还要确保其他线程不仅能够判断出第一个线程已经完成了更新还是处在更新的中途，还能够判断出如果第一个线程走向AWOL，完成更新还需要什么操作。如果线程发现了处在更新中途的数据结构，它就可以“帮助“正在执行更新的线程完成更新，然后再进行自己的操作。当第一个线程回来试图完成自己的更新时，会发现不再需要了，返回即可，因为CAS会检测到帮助线程的干预（在这种情况下，是建设性的干预）。

这种“帮助邻居”的要求，对于让数据结构免受单个线程失败的影响，是必需的。如果线程发现数据结构正处在被其他线程更新的中途，然后就等候其他线程完成更新，那么如果其他线程在操作中途失败，这个线程就可能永远等候下去。即使不出现故障，这种方式也会提供糟糕的性能，因为新到达的线程必须放弃处理器，导致上下文切换，或者等到自己的时间片过期（而这更糟）

Java的的的ConcurrentHashMap的实现原理

Java5中中的ConcurrentHashMap中，线程安全，设计巧妙，用桶粒度的锁，避免了把和GET中对整个地图的锁定，尤其在获取中，只对一个HashEntry做锁定操作，性能提升是显而易见的。

高并发环境下优化锁或无锁（无锁）的设计思路

高并发环境下要实现高吞吐量和线程安全，两个思路：。一个是用优化的锁实现，一个是无锁的无锁结构但非阻塞算法要比基于锁的算法复杂得多开发非阻塞算法是相当专业的训练，而且要证明算法的正确也极为困难，不仅和具体的目标机器平台和编译器相关，而且需要复杂的技巧和严格的测试。虽然无锁编程非常困难，但是它通常可以带来比基于锁编程更高的吞吐量。所以无锁编程是大有前途的技术。它在线程中止，优先级倒置以及信号安全等方面都有着良好的表现。

• 优化锁实现的例子 ：Java的中的ConcurrentHashMap中，设计巧妙，用桶粒度的锁和锁分离机制，避免了把和GET中对整个地图的锁定，尤其在获取中，只对一个HashEntry做锁定操作，性能提升是显而易见的。
• 无锁无锁的例子 ：CAS（CPU的比较并交换指令）的利用和LMAX的 破坏者 无锁消息队列数据结构等有兴趣了解LMAX的。 破坏者 无锁消息队列数据结构的可以 移步SlideShare上 。

破坏者 无锁消息队列数据结构的类图产品状语从句： 技术文档下载

另外，在设计思路上除了尽量减少资源争用以外，还可以借鉴 的nginx / node.js的 等单线程大循环的机制，用单线程或CPU数相同的线程开辟大的队列，并发的时候任务压入队列，线程轮询然后一个个顺序执行。由于每个都采用异步I / O，没有阻塞线程。这个大队列可以使用RabbitMQueue，或是JDK的同步队列（性能稍差），或是使用 能干扰无锁队列 （JAVA）。任务处理可以全部放在内存（多级缓存，读写分离，ConcurrentHashMap的，甚至分布式缓存Redis的）中进行增删改查。最后用石英硅维护定时把缓存数据同步到数据库中。当然，这只是中小型系统的思路，如果是大型分布式系统会非常复杂，需要分而治理，用SOA的思路，参考 这篇文章的图产品。

深入JVM的OS的无锁非阻塞算法

如果深入JVM和操作系统，会发现非阻塞算法无处不在。 垃圾收集器 使用非阻塞算法加快并发和平行的垃圾搜集; 调度器 使用非阻塞算法有效地调节线程和进程，实现内在锁。在野马（Java 6.0）中，基于锁的 SynchronousQueue 算法被新的非阻塞版本代替。很少有开发人员会直接使用SynchronousQueue ，但是通过 Executors.newCachedThreadPool() 工厂构建的线程池用它作为工作队列。比较缓存线程池性能的对比测试显示， 新的非阻塞同步队列 实现提供了几乎是当前实现3倍的速度。在Mustang的后续版本（代码名称为Dolphin）中，已经规划了进一步的改进。