概述
java.util.concurrent包中的许多类,比如Semaphore和ConcurrentLinkedQueue,都提供了比使用Synchronized更好的性能和可伸缩性.这是因为它们的内部实现使用了原子变量和非阻塞的同步机制.
近年来很多关于并发算法的研究都聚焦在非阻塞算法(nonblocking algorithms),这种算法使用低层原子化的机器指令取代锁,比如比较并交换(compare-and-swap),从而保证数据在并发访问下的一致性.非阻塞算法广泛应用于操作系统和JVM中的线程和进程调度、垃圾回收以及实现锁和其他的并发数据结构.
与基于锁的方案相比,非阻塞算法的设计和实现都要复杂得多,但是他们在可伸缩性和活跃度上占有很大的优势.
因为非阻塞算法可以让多个线程在竞争相同资源时不会发生阻塞,所以它能在更精化的层面上调整粒度,并能大大减少调度的开销.
进一步而言,它们对死锁和其它活跃度问题具有免疫性.在基于锁的算法中,如果一个线程在持有锁的时候休眠,或者停滞不前,那么其他线程就都不可能前进了,而非阻塞算法不会受到单个线程失败的影响.
在Java 5.0中,使用原子变量(atomic variable classes),比如AtomicInteger和AtomicReference,能够高效地构建非阻塞算法.
即使你不使用原子变量开发阻塞算法,它也可以当做更优的volatile变量来使用.原子变量提供了与volatile类型变量相同的内存语义,同时还支持原子更新--使它们能更加理想地用于计数器、序列发生器和统计数据收集等,另外也比基于锁的方案具有更加出色的可伸缩性.
1. 锁的劣势
使用一致的加锁协议来协调对共享状态的访问,确保无论哪个线程持有守护变量的锁,他们都能独占地访问这些变量,并且对变量的任何修改对其他随后获得同一锁的线程都是可见的.
现代JVM能够对非竞争锁的获取和释放进行优化,让它们非常高效,但是如果有多个线程同时请求锁JVM就需要向操作系统寻求帮助.
倘若出现了这种情况,一些"不幸的"线程将会挂起,稍后恢复运行.从线程开始恢复起,到它真正被调用前,可能必须等待其它线程完成它们的调度限额规定的时间.挂起和恢复线程会带来很大的开销,并通常伴有冗长的中断.
对于基于锁,并且其操作过度细分的类(比如同步容器类,大多数方法只包含很少的操作),当频繁地发生锁的竞争时,调度与真正用于工作的开销间的比值会很可观.
volatile变量与锁相比是更轻量的同步机制,因为它们不会引起上下文的切换和线程调度.
然而,volatile变量与锁相比有一些局限性:尽管他们提供了相似的可见性保证,但是它们不能用于构建原子化的复合操作.
这意味着当一个变量依赖其他变量时,或者当变量的新值依赖于旧值时,是不能用volatile变量的.这些都限制了volatile变量的使用,因此它们不能用于实现可靠的通用工具,比如计数器.
尽管自增操作(++i)看起来像是原子操作,事实上有3个独立操作--获取变量当前值,加1,然后写会更新值.为了不丢失更新,整个读-改-写操作必须是原子的.可以使用加锁保证它的线程安全.
在几乎没有竞争的条件下会运行良好.但是在竞争下,性能会由于上下文切换的开销和调度延迟而受到损失.倘若临时占有锁的线程进入休眠,将成为又一个问题,因为会有线程在这个错误的时间里请求锁.
加锁还有其他的缺点.当一个线程正在等待锁时,它不能做任何其他事情.如果一个线程在持有锁的情况下发生了延迟(原因包括页错误、调度延迟、或者类似情况),那么其他所有需要该锁的线程都不能前进了.
如果阻塞的线程是优先级很高的线程,持有锁的线程优先级较低,那么会造成严重问题--性能风险,被称为优先级倒置(priority inversion).
即使更高的优先级占先,它仍然需要等待锁被释放,这导致它的优先级会降至与优先级较低的线程相同的水平.
如果持有锁的线程发生了永久性的阻塞(因为无限循环、死锁、活锁和其它活跃度失败),所有等待该锁的线程都不会前进了.
即使忽略这样的风险,加锁对于细分的操作而言,仍是重量级(heavyweight)的机制,比如递增计数器.本应该有更好的技术用来管理线程之间的竞争--某些类似于volatile变量的机制,但是还要支持原子化更新.幸运的是,现代处理器为我们提供了这样的机制.
2. 硬件对并发的支持
独占锁是一项悲观的技术--它假设最坏的情况(总会有其他线程去修改变量),并且会通过获得正确的锁来避免其他线程的打扰,直到做出保证才能继续进行.
对于细粒度的操作,有另外一种选择通常更加有效--乐观的解决方法.凭借新的方法,我们可以指望不受打扰地完成更新.这个方法依赖于冲突检测,从而能判定更新过程中是否存在来自其他成员的干涉,在冲突发生的情况下,操作失败,并会重试(也可能不重试).这种方式更有效率.
如今,几乎所有现代的处理器都具有一些形式的原子化的读-改-写指令,比如比较并交换(compare-and-swap)和加载链接/存储条件(load-linked/store-conditional).操作系统和JVM使用这些指令来实现锁和并发的数据结构.
2.1 比较并交换
大多数处理器使用的架构方案都实现了比较并交换(CAS)指令(其他处理器,使用一对指令实现了相同的功能:链接加载/存储条件).
CAS有3个操作数---内存位置V、旧的预期值A和新值B.当且仅当V符合旧预期值A时,CAS用新值B原子化的更新V的值;否则它什么都不会做.在任何一种情况下,都会返回V的真实值.(这个变量称为compare-and-set,无论操作是否成功都会返回).
CAS的意思是:"我认为V的值是A,如果是,那么将B的值赋给V,若不是,则不修改,无论如何都返回V的值"
CAS是一项乐观技术--它抱着成功的希望进行更新,并且如果另一个线程在上次检查后更新了该变量,它能够发现错误.
阐释CAS的语意(并非真正的实现或执行方式):
public class SimulatedCAS { private int value; //原子的操作
public synchronized int getValue(){ return value;
} //原子的操作
public synchronized int compareAndSwap(int expectedValue,int newValue){ //到达缓存中的值
int oldValue = value; //如果缓存中的值等于传入来的期望的旧值
if(oldValue == expectedValue){ //把新值赋给内存中的值
value = newValue;
} //返回的是第一次得到的内存中的值
return oldValue;
} //原子的操作
public synchronized boolean compareAndSet(int expectedValue,int newValue){ //如果两个值相等,返回true并设置新的value值,否则返回false
return (expectedValue == compareAndSwap(expectedValue,newValue));
}
}使用CAS的时候,必须传入和内存中的值相同的旧值,才能将内存中的值更新为新值.
当多个线程试图使用CAS同时更新相同的变量时,其中一个会胜出,并更新变量的值,而其他的都会失败.失败的线程不会被挂起(但是在使用锁的情况下,没有获取锁的线程就会被挂起);它们会被告知这一次赛跑失利,但允许再尝试.
因为一个线程在竞争CAS时失败不会被阻塞,它可以决定是否重试,进行一些补救行动,或者什么都不做(最好的处理方式,可能其他线程已经完成了你要做的事情).这样的灵活性大大减少了与锁相关的活跃度风险(可能在极端的情况下引入活锁风险).
2.2 非阻塞计数器
public class CasCounter { private SimulatedCAS value = new SimulatedCAS(); public int getValue(){ return value.get();
} public int increment(){ int v ;
do{
v = value.get();
} while (v != value.compareAndSwap(v,v+1)); return v+ 1;
}
public static void main(String [] args){
CasCounter casCounter = new CasCounter(); for (int i = 0; i < 10; i++) {
System.out.println("casCounter.increment() = " + casCounter.increment());
}
}
}自增操作遵循了经典形式--取得旧值,根据它计算出新值(加1),并使用CAS设定新值.
如果CAS失败,立即重试操作.尽管在竞争十分激烈的情况下,更希望等待或者回退,以避免重试造成的活锁,但是,通常反复重试都是合理的策略.
CasCounter不会发生阻塞,如果其他线程同时更新计数器,他会进行数次重试.实践中,如果你仅仅需要一个计数器,获取序列生成器,直接使用AtomicInteger或者AtomicLong就可以了,它们提供原子化的自增方法和其他算数方法.
初看起来,基于CAS的计数器看起来比基于锁的计数器性能差一些:它具有更多的操作和更复杂的控制流,表面看来还依赖于复杂的CAS的操作.但是,实际上基于CAS的计数器,性能上远远胜过了基于锁的计数器,哪怕只有很小的竞争,或者不存在竞争.
获取非竞争锁的快速路径,通常至少需要一个CAS加上一个锁相关的细节琐事,所以,基于锁的计数器的最好情况也要比基于CAS的一般情况做更多的事情.
因为CAS在大多数情况下都能成功(假设竞争程度中等偏下),硬件将能够正确地预知隐藏在while循环中的分支,使本该更复杂的控制逻辑的开销最小化.
加锁的语法可能比较简洁,但是JVM和OS管理锁的工作却并不简单.加锁需要遍历JVM中整个复杂的代码路径,并可能引起系统级的加锁、线程挂起以及上下文切换.在最优的情况下,加锁需要至少一个CAS,所以使用锁时把CAS抛在一边几乎不能节省任何真正的开销.
另一方面,程序内部执行CAS不会调用到JVM的代码、系统调用或者调度活动.在应用级看起来越长的代码路径,在考虑到JVM和OS的时候,事实上会变成更短的代码.
CAS最大的缺点:它强迫调用者处理竞争(通过重试、回退,或者放弃);然而在锁被获得之前,却可以通过阻塞自动处理竞争(CAS最大的缺陷在于难以正确地构建外围算法).
即使是在"快速路径"上,获取和释放无竞争锁的开销大约也是CAS的两倍.
3. 原子变量类
原子变量比锁更精巧、更轻量,并且在多处理器系统中,对实现高性能的并发代码非常关键.
实现原子变量的快速(非竞争)路径,并不会比获取锁的快速路径差,并且通常会更快;而慢速路径绝对比锁的慢速路径快,因为它不会引起线程的挂起和重新调度.
在使用原子变量取代锁的算法中,线程更不易出现延迟,如果它们遇到竞争,也更容易恢复.
原子变量类,提供了广义的volatile变量,以支持原子的、条件的读-写-该操作.
AtomicInteger代表了一个int值,并提供了get和set方法,它们与读取和写入可变的int有着相同的内存语义.
它同样提供了一个compareAndSet方法(如果该方法成功成功,其内存效果和同时读取写入一个volatile变量是一样的),以及原子化的插入、递增、递减等方法,这样是为了使用方便.
AtomicInteger与扩展的Counter表面上看有共同之处,但是在竞争条件下AtomicInteger提供了更好的可伸缩性,因为它直接利用硬件对并发的支持.
原子变量类有12个,分成4组:计数器、域更新器(field updater)、数组以及复合变量.
最常用的原子变量是计数器:AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference.它们都支持CAS:AtomicInteger和AtomicLong还支持算术运算.
原子化的数组类(只有 Integer、Long和Reference版本的可用),它的元素是可以被原子化地更新的.
原子数组类为数组的元素提供了volatile的访问语义,这是普通数组所没有的特性---volatile类型的数组只针对数组的引用具有volatile语义,而不是它的元素.
基本类型的包装类(Integer/Long)是不可变的,而原子变量类是可变的.
3.1 性能比较: 锁与原子变量
在激烈竞争下,锁胜过原子变量,但是在没那么激烈的条件下,原子变量会胜过锁.这是因为锁通过挂起线程来响应竞争,减少了CPU的利用和共享内存总线上的同步通信量.(这与在生产者-消费者线程中,以阻塞生产者来减小消费者负荷,使消费者能够赶上进度的设计是类似的.)
使用原子变量把竞争推回给调用类.通过不断反复尝试来响应竞争,通常是正确的,但是在激烈竞争环境下,会带来更多竞争.
在实践中,原子化的伸缩性比锁更好,因为在典型的竞争级别中,原子性会带来更好的效率.
锁与原子化随竞争度的不同,性能发生的改变阐明了各自的优势和劣势.在中低程度的竞争下,原子化提供更好的伸缩性;在高强度的竞争下,锁能够更好地帮助我们避免竞争.
4. 非阻塞算法
基于锁的算法会带来一些活跃度的风险. 如果线程在持有锁的时候因为阻塞I/O,页面错误,或其他原因发生延迟,很可能所有线程都不能前进了.
一个线程的失败或挂起不应该影响其他线程的失败或挂起,这样的算法被称为非阻塞(nonblocking)算法.
如果算法的每一步骤中都有一些线程能够继续执行,那么这样的算法称为锁自由(lock-free)算法.
在线程间使用CAS进行协调,这样的算法如果能构建正确的话,它既是非阻塞的,又是锁自由的.
非竞争的CAS总是能够成功,如果多个线程以一个CAS竞争,总会有一个胜出并前进.
非阻塞算法对死锁和优先级倒置有"免疫性"(但它们可能会出现饥饿和活锁,因为他们允许重进入).有关死锁、活锁和饥饿的相关知识,请移驾并发编程学习笔记之死锁(八).
4.1 非阻塞栈
栈是最简单的链式数据结构:每个元素仅仅引用唯一的元素,并且每个元素只被一个元素引用.(看下面代码,这里面只保存一个最新的Node,但是这个Node中有一个相连的Node引用,可以通过Node.next.next.next如此反复得到所有的Node)
public class ConcurrentStack<E> { private static class Node<E>{ public final E item; public Node<E> next; public Node(E item){ this.item = item;
}
} //这里面存放的是一个Node,但是通过Node.next.next.next可以拿到所有Node
AtomicReference<Node<E>> top = new AtomicReference<Node<E>>(); public void push(E item){
Node<E> newHead = new Node<E>(item);
Node<E> oldHead; do{
oldHead = top.get(); /*
* 这是一个链表, 当有新值加入,会把旧值挂在新值的next方法上,
* 如此反复,可以通过递归next拿到所有Node
* */
newHead.next = oldHead;
} /*如果oldHead和内存中的旧值相同,更新为newHead,返回设置的结果
* 如果设置成功设置新值返回true,跳出循环
* */
while (!top.compareAndSet(oldHead,newHead));
} /*移除一个最新值*/
public E pop(){
Node<E> oldHead;
Node<E> newHead; do{ //得到当前最新值
oldHead = top.get(); if(oldHead == null){ return null;
} //得到第二新的值
newHead = oldHead.next;
} /*使第二新的值替换旧的值,如果成功退出循环*/
while (!top.compareAndSet(oldHead,newHead)); //返回移出的新的值
return oldHead.item;
}
}在并发访问的环境下,push和pop方法通过top.compareAndSet方法可以保证栈的原子性和可见性,从而安全高效的更新非阻塞栈.
CasCounter和ConcurrentStack阐释了非阻塞算法的所有特性:一些任务的完成具有不确定性,并可能重做.在ConcurrentStack中,当我们构建表示新节点的Node时,我们希望next的引用值(通过top.get获得的)在该节点装入栈的时候仍然有效,但是同时仍然为重试做好了准备.
在ConcurrentStack等中用到的非阻塞算法,其线程安全性源于:compareAndSet既能提供原子性,又能提供可见性保证,加锁也可以保证.
当一个线程改变栈的状态时,它使用具有与写入volatile变量相同的内存效应的compareAndSet.当线程检查栈的时候,通过调用同一个AtomicReference的get方法来实现,它具有与读取volatile变量相同的内存效应.所以任何线程修改都能够安全地发布给其他正在检查列表状态的线程.并且这个列表通过compareAndSet进行修改,更新top的引用或者因发现其它线程的干扰而失败,这些都是原子化地进行的.
4.2 非阻塞链表
到目前为止我们已经见到了两个非阻塞算法,即计数器和栈,他们阐释了使用CAS"投机地"更新值这以最基本的模式,如果更新失败就重试.
构建非阻塞算法的窍门是:缩小原子化的范围到唯一的变量.
使用非阻塞算法实现一个链接队列比栈更复杂.因为它需要支持首尾的快速访问.需要维护两个独立的队首指针和队尾指针,初始时都指向队列的末尾节点.在成功加入新元素时两个指针都需要原子化的更新.
使用链接队列构建非阻塞算法需要考虑两种情况:
第一个指针位置更新成功,第二个失败,队列将处于不一致的境地.
两个都成功了,另一个操作也可能在两个更新操作之间来访问队列.
要完成这个任务需要几个窍门:
即使在多步更新中,也要确保数据结构总能处于一致状态.这样线程B在到达时发现线程A正在更新,B可以分辨操作已部分完成,并且知道不能立即开始自己的更新.这样B就开始等待(通过反复检查队列状态)直到A完成更新,这样两个线程就不会相互影响了.
确保如果B到达时发现数据结构正在被A修改,在数据结构中应该有足够多的信息,说明需要B来替代A完成更新.如果B"帮助"A完成其操作,那么B可以进行自己的操作,而不用等待A的操作完成,当A恢复后试图完成其操作,会发现B已经替它完成了.
Michael-Scott的非阻塞链接队列算法的插入部分,已经用到了ConcurrentLinkedQueue中:
public class LinkedQueue<E> { private static class Node<E>{ final E item; //atomicReference 是非阻塞算法,可以保证放入元素的原子性和可见性.
final AtomicReference<Node<E>> next; /*
* 通过构造方法给item和next赋值
* */
public Node(E item, Node<E> next) { this.item = item; this.next = new AtomicReference<Node<E>>(next);
} @Override
public String toString() { return "Node{" + "item=" + item + ", next=" + next + '}';
}
} //初始化一个dummy,赋值两个null
private final Node<E> dummy = new Node<E>(null,null); /*
* 声明一个AtomicReference类型的head,把dummy放进去,
* 可以保证dummy的原子性和可见性
* */
private final AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(dummy); //同上
private final AtomicReference<Node<E>> tail = new AtomicReference<Node<E>>(dummy); /*
* 添加元素,返回一个Boolean类型的值.
* */
public boolean put(E item){ //声明一个新的节点,将item放进去
Node<E> newNode = new Node<E>(item,null); //创建一个死循环
while (true){ //得到当前尾部的值
Node<E> curTail = tail.get(); //得到当前尾部的值的下一个值
Node<E> tailNext = curTail.next.get(); /*
* 如果当前尾部的值 == 最新一次取到的尾部值,
* 往下走, 否则进入下一次循环.
* 这里保证不会有过期值.
* */
if(curTail == tail.get()){ /*
*步骤A, 如果当前尾部值的下一个值不为null,
* 也就是不是第一次往里放值的情况
* */
if(tailNext != null){ // 步骤B,队列处于静止状态,推进尾节点,进入下次循环
tail.compareAndSet(curTail,tailNext);
}else{ //步骤C,处于静止状态,尝试插入新节点
if(curTail.next.compareAndSet(null,newNode)){ //步骤D
tail.compareAndSet(curTail,newNode); return true;
}
}
}
}
} @Override
public String toString() { return "LinkedQueue{" + "dummy=" + dummy + ", head=" + head + ", tail=" + tail + '}';
} public static void main(String [] args){
LinkedQueue<String> linkedQueue = new LinkedQueue<>();
linkedQueue.put("a");
linkedQueue.put("b");
linkedQueue.put("c"); //linkedQueue.put("b");
System.out.println("linkedQueue = " + linkedQueue);
}
}
打印输出:
linkedQueue = LinkedQueue{dummy=Node{item=null, next=Node{item=a, next=Node{item=b, next=Node{item=c, next=null}}}}, head=Node{item=null, next=Node{item=a, next=Node{item=b, next=Node{item=c, next=null}}}}, tail=Node{item=c, next=null}}一个空队列有一个"哨兵(sentinel)节点"或者"虚(dummy)节点",并且队首指针和队尾指针的初始化都指向哨兵节点.队尾指针永远指向哨兵节点,也就是队列的最后一个元素(看打印输出的tail就可以看出,永远输出的是最后一个添加的元素的节点),或者(当操作正在更新队列时)指向倒数第二个元素.
要想同时实现两个窍门的方法是:假设队列处于稳定状态,则tail节点的next域的值为null,如果队列处于中间状态tail.next为非空.所以任何线程都能够通过检查tail.next即时地了解队列状态.进一步而言,如果队列处于中间状态,它能够通过推进tail指针向前移动一个节点把状态恢复为稳定(tail.compareAndSet(curTail,tailNext)这一行),结束任意线程正在插入元素的操作.
LinkedQueue.put在尝试插入前首先检查是否处于中间状态(步骤A).如果是,那么其他线程正在插入元素(在步骤C和D之间).除了等待线程完成,当前线程还能够帮助结束操作,推进队尾指针(步骤B).在这之后,如果另一个线程已经开始插入新元素了,它会进行重复检查,继续推进队尾指针直到它发现队列处于稳定状态,可以开始自己的插入了.
步骤C的CAS,在队尾链接了新的节点,如果两个线程视图同时插入元素,会造成失败.在这样的情况下不会造成危害:没有发生改变,当前的线程只需要重载队尾指针并重试.C一旦成功,插入就生效了.
第二个CAS(步骤D)被用作"清除",因为它可以由插入的线程执行,也可以由其他任何线程.如果D失败,插入线程无论如何都会返回,而不是重新尝试CAS,因为不再需要重试了---另一个线程已经在步骤B就完成了这个工作!这样做不会有问题,因为在所有线程尝试向队列链接新节点之前,首先通过检查tail.next是否为空来判定队列是否需要清理,如果是,它首先会推进队尾指针(可能多次),直到队列处于稳定状态(tail.next为空).
4.3 原子化的域更新器
之前的代码说的只是一个实现的大概意思,ConcurrentLinkedQueue的真实实现与它略有区别.
ConcurrentLinkedQueue并未使用原子化的引用,而是使用普通的volatile引用来代表每一个节点,并通过基于反射的AtomicReferenceFieldUpdater来进行更新.
private static class Node<E>{
final E item; volatile Node<E> next; public Node(E item) { this.item = item;
}
} private static AtomicReferenceFieldUpdater<Node,Node> nextUpdater =
AtomicReferenceFieldUpdater.newUpdater(Node.class,Node.class,"next");原子化的域更新器类,代表着已存在的volatile域基于反射的"视图",使得CAS能够用于已有的volatile域.
域更新器类并不依赖特定的实例;它可以用于更新目标类任何实例的目标域.
更新器类提供的原子性保护比普通的原子类差一些,因为你不能保证底层的域不被直接修改.--compareAndSet和算数方法只在其它线程使用原子化的域更新器方法时保证其原子性.
在ConcurrentLinkedQueue中,更新Node的next域是通过使用nextUpdater的compareAndSet方法实现的.这是出于性能的考虑.对于频繁分配的、生命周期短暂的对象,比如队列的链接节点,减少每个Node的AtommicReference创建,对于减少插入操作的开销是非常有效的.
原子变量其实已经够好了,尽在很少的情况下才需要原子化的域更新器(当你想要保存现有类的串行化形式时,原子化的域更新器会非常有用).
4.4 ABA问题
在CAS,内存中的值V如果和A相同就把V更新为B,但是 如果V的值先改为了C,又改回了A,也是可以更新的,但是中间有一个值改变又改变回来的过程. 这就是ABA问题
如果需要知道值改变过,有一种简单的解决方案:更新一对值,包括引用和版本号,而不是仅更新值的引用.
即使值由A改为B,又改回A,版本号也是不同的.
AtomicStampedReference以及它的同系AtomicMarkableReference提供了一堆变量原子化的更新条件.更新对象引用的证书对,允许"版本化"引用是能够避免ABA问题的.
总结
非阻塞算法通过使用低层级并发原语,比如比较并交换,取代了锁.原子变量类向用户提供了这些低层级原语,也能够当做"更佳的volatile变量"使用,同时提供了整数类和对象引用的原子化更新操作.
非阻塞算法在设计和实现中很困难,但是在典型条件下能够提供更好的可伸缩性,并能更好地预防活跃度失败.从JVM的一个版本到下一个版本间并发性的提升很大程度上来源于非阻塞算法的使用,包括在JVM内部以及平台类库.