Java 理论与实践: 非阻塞算法简介
看吧,没有锁定!
Java™ 5.0 第一次让使用 Java 语言开发非阻塞算法成为可能,java.util.concurrent 包充分地利用了这
个功能。非阻塞算法属于并发算法,它们可以安全地派生它们的线程,不通过锁定派生,而是通过低级的
原子性的硬件原生形式 —— 例如
比较和交换
。非阻塞算法的设计与实现极为困难,但是它们能够提供更
好的吞吐率,对生存问题(例如死锁和优先级反转)也能提供更好的防御。在这期的 Java
理论与实践
中,
并发性大师 Brian Goetz 演示了几种比较简单的非阻塞算法的工作方式。
在不只一个线程访问一个互斥的变量时,所有线程都必须使用同步,否则就可能会发生一些非常糟糕的事
情。Java 语言中主要的同步手段就是 synchronized 关键字(也称为
内在锁
),它强制实行互斥,确保
执行 synchronized 块的线程的动作,能够被后来执行受相同锁保护的 synchronized 块的其他线程看
到。在使用得当的时候,内在锁可以让程序做到线程安全,但是在使用锁定保护短的代码路径,而且线程
频繁地争用锁的时候,锁定可能成为相当繁重的操作。
在 “流行的原子” 一文中,我们研究了
原子变量
,原子变量提供了原子性的读-写-修改操作,可以在不使用
锁的情况下安全地更新共享变量。原子变量的内存语义与 volatile 变量类似,但是因为它们也可以被原
子性地修改,所以可以把它们用作不使用锁的并发算法的基础。
非阻塞的计数器
清单 1 中的 Counter 是线程安全的,但是使用锁的需求带来的性能成本困扰了一些开发人员。但是锁是
必需的,因为虽然增加看起来是单一操作,但实际是三个独立操作的简化:检索值,给值加 1,再写回值。
(在 getValue 方法上也需要同步,以保证调用 getValue 的线程看到的是最新的值。虽然许多开发人
员勉强地使自己相信忽略锁定需求是可以接受的,但忽略锁定需求并不是好策略。)
在多个线程同时请求同一个锁时,会有一个线程获胜并得到锁,而其他线程被阻塞。JVM 实现阻塞的方
式通常是挂起阻塞的线程,过一会儿再重新调度它。由此造成的上下文切换相对于锁保护的少数几条指令
来说,会造成相当大的延迟。
清单 1. 使用同步的线程安全的计数器
public "nal class Counter {
private long value = 0;
public synchronized long getValue() {
return value;
}
public synchronized long increment() {
return ++value;
}
}
清单 2 中的 NonblockingCounter 显示了一种最简单的非阻塞算法:使用 AtomicInteger 的
compareAndSet() (CAS)方法的计数器。compareAndSet() 方法规定 “将这个变量更新为新值,但
是如果从我上次看到这个变量之后其他线程修改了它的值,那么更新就失败”(请参阅 “流行的原子” 获得
关于原子变量以及 “比较和设置” 的更多解释。)