像宝石一样的Java原子类

像宝石一样的Java原子类

目录
问题:线程之间的协作
标准的处理方法:上锁
用锁实现计数器和互斥体
锁的问题
硬件同步原语
Compare and swap (CAS)
使用CAS实现计数器
Lock-freeK | E $ p / J k和 wait-free 算法
原子变量类
细粒度意味着更轻量
java.util.^ ( ` % C W B uconcurrent包中的原子变量
使用原子变量实现更高的吞吐量
总结
译者注
参考:
7 d N f 3 ! k五年前,多处理器系统是高度专业化的系统,通常耗资数十万美元(其中大多数具有两到四个处理器)。
如今,多处理器系统既便宜又丰富,几乎主流的微处理器都v l k q 1 4 M 2内置了对多处理器的支持,很多能够支持数十或数百个处理器。
为了充分利用多处理器系统的性能,通常使用多个线程来构建应用程序。
但是,任何一个写并发应用的人都会) o K 8 S 1 3 b告诉你,仅仅把工作分散在多个线程中处理不足以充分利用硬件的性能,你必须保证你的线程大部分时A C v间都在工作,而不是在等待工作,或者在等待共享数据上的锁。

问题:线程之间的协作
很少有应用可以不依赖线程协作而实现真正的并行化。
例如一个线程 . g *) D 1 N W n,其中的任务通常是彼此独立的被执行,互不干扰。一般会使用一个工作队列来维护这些任务,那么从工作队列中删除任务或向其中添Q V R : { L t加任务的过程必须是线程安全的,这意味着需要协调队列头部、尾部、以及节点之间的链接指针。这种协调工作是麻烦的根源。

标准的处理方法:上锁
在Java中,协调多线程访J s & ; G r问共享变量的传统方式是同步
通过同步(synchronized关键字)可以保证只有持有锁的线程才可以访问& Q ; e共享变量,此外可以确保持有锁的线程对这些变量的访问具有独占访问权,且线程对共享变量的改变对于其他后来的线程是可见的。
同步的缺点是,当锁的竞争激烈时- I(多个线程频繁的尝试获取锁),吞吐量会受到影响,同步的代价会非常高。
基于锁的算法另一个问题是如果一个持有锁的线程被延迟(由于page fault、调度延迟、或其他异常),那么其他正在等待该锁的线程都将无法执行。
volatile变量也可以用于存储共享变量,其成本比synchronized要低。( ~ b但是它有局限性C Z z c,虽然volatile变量的修改对其他线程是立即可见的,但是它无法呈现原子操作的read-modify-write操作序列,这意味着,volatile变量无法实现可靠的互斥锁或计数器。

用锁实现计数器和互斥体
考虑开发一个线程安全的计数器类,该类公开get()、increment()和decrement()操作。清单1展示了使用同步锁实现此类l ] B Q
请注意,所有方法,甚至get(),都是同步的,以保证不会丢失任何更新b ; A Y s,并且所有线程都可以看到计数器的最新值。

Listing 1. A synchroni+ ! { r 6zed co` 4 tunter class
public class SynchronizedCounter {

private int va| % k ! ^ W e ;lue;
public synchronized int getValue() { return value; }
public synchL @ d % c X qronized int increment() { return ++value; }
public synchronizei ^ d ; _ Z 4d int decrement() { return --value; }

}u Q ? 5 ~
increment(T 6 4 ( R) 和 decre= G 2 @ ) ; ;ment()都是原子的read-modify-w[ drite操作,为了安全的递增计数器,你必须取出当前值,然后对它加1,最后再把新值写回。所有这些操作都将作为一个单独的操作完成,中途不能被其他线程打断。否则,如果两个线程同时进行increment操作,意外的操作交错会导致计数器只被递增了一次,而不是两次。(请注意,通过把变量设置为volatile,不能可x 5 * P靠的实现以上操作)
原子的read-modify-write组合操作出现在很多并发算法中。下面清单2中的代码实现了一个简单的互斥体(Mutex,Mutual exclusion的简写)。acquire()方法就是原子的read-modL S H { { I T xify-write操作。
要获取这个互斥体,你必须确保没有其他线程占用它(curOwner==null),成功获取后标识你已经持有该锁(curOwner = Thread.currentThread()),这样其他线程就不可能再进入并修改curOwner变量。

Listing 2. A synchrS C = c c , Donized mutex class
puZ { G O N - 1blic class SynchronizedMutex {

private Thread curOwner = null;
public synchronized void acquire() throws Interrx c X X , muptedException {
if (Thread.interrupted% R 0()) throw; s b new Intem d q y # ; G / rruptedException();
w# w 3 Ahile (curOwner != null)
wait();
curOwner = Thread.c6 B { O j = n t )urrentThread();
}
public synchronized void release() {
if (curOwner == Thre4 ! z kad.currentThread()) {
curOwner = null;
notify();
} else
throw new IllegalStateException("not owner of mutex");
}

}
清单1中的计数器类在没有竞争^ i = + -或竞争很少的情况下可以可靠的工作。
g T Y B而,在竞争激烈时性能将大幅下降,因为JVM将花费更多的时间处理线程调度以及管理竞争,而花费较少的! 9 l 2 V N z时间7 * V v ] u 6进行实际工作,如增加计数器。

锁的问题
如果一个线程尝试获取一个正在被其他线程占用的锁,4 _ t z该线程会一直阻塞直到锁被其他线程释放。
这种方式有明显的缺点,当线程被阻塞时它不能做Z q k m y U X L任何事情。如果被阻塞的线| 1 - # o .程是较高优先级的任务,那么后果是灾难性的(这种危险被称为优先级倒置,priority inversion)。使用锁还有其他一些风险,例如死W T ]锁(当以不一致的顺序获取多个锁时可能会发生死锁)。
即使没有这样的危险,锁也只是相对粗粒度的协调机制。因此,对于管理简单的操作(例如计数器或互斥体)来说,锁是相当 / o P o Q“重”的。
如果有一个e N ~更细粒度的机制能够可靠地管理对变量的并发更新,那将是极好的。
幸运的是,大多数现代处x $ Q理器都有这种轻量级的机制。

硬件同步原语
如前所述,大多数现代处理都支持多处理器,这种% T 2 D支持除了基本的Z 7 5多个处理器共享外设和主存储器的能力p 4 c E b I,它通常还包括对指令集s 5 c U ?的增强,以支持多处理的特殊要求。特别是,几7 Q 4 d A T |乎每个现代处理器都具有用于更新共享变量的指令,该指令可以检测或阻止来自其他处理器的并发访问。

Cou @ d v s : , { )mpare and swap (M ] W *CAS)
第一批支持并发的处理器提供了原子的test-and-set操作,这些操作通常在一个bit上进行。但是当前主流的处理器(包括Intel和Sparc处理器)最常用的方法是实现一个被称D 2 8 U为compare-and-swap(CAS)的原语。(在Intel处理器上,CAS是由cmpxchg指令系列实现的。PowerPC处理器有一对"] ~ = q ,load and reserve" 和 "store conditional"的指令达到同样的效果)
CAS包括三个操作对象-内存位置(V),预期的旧值8 G ! x 3 B I ? U(A)和新的值(B)。
如果该位置的值V与预期的旧值A匹配,则处理器将原子地将该位置更新为新值B,否则它v Z A = _将不执行任何操作。
无论哪种情况,它都会返回CAS指令之前该位置的值V。 (CAS的某些版本会简单地` l p F J S ! s x返回CAS是否成功,而不获取当前值。)
CAS表示:“我认为位置V应该有值A;如果有,则将B放入其中,否则,不要改变它,但要告诉我现在有什么值。”
Cm / f n , wAS通常的使用方法是,从地址V读取值Aq 8 H H . 7 C,然后对A执行多次计算得到新值B,最后使用CAS指令将位置V的值从A变为B。
如果O h P V (该位置V同时没有被其他处8 v { _ i理器更新,那么CAS就会成功。
像CAS这样的指令T ^ h允许程序执行 rea$ _ * % Kd-modify-write序列,而不必担心同时有另一个线程修改变量,因为如果另一个线程确实修改了变量,则CAS会检测到该变量(并失败),并且程序可以重试该操作。
清单3,通过synchronized模拟了CAS的内部逻辑。(不包括性能模拟,也没办法模拟,因为CAS的价值就在于它是在硬件中实现的,非常轻量级。w T 0 G D p }

Listing 3. the behavior, n D X j I (but not performance) o_ b Q zf compare-and-swap
public class SimulatedCAS {

 private int value;
public synchronized int getValue() { return value; }
public synchronized int comparee l Q f h @ C 0AndSwap(int expectedValue, int newValue) {
int oldValue = v# * C )  | } Halue;
if (value == expecR 6 h , | 1 n B vtedValuM o s ^ {e)
value = newValue;
return oldValue;
}

}
使用CAS实现计数器
基于CAS的并发算法称为lock-fre& d # T N @e,因为线程不必等待锁(有时称为互斥体或临界区,术语因实现平台而异)。
无论CAS操作成功还是失败,它都可以在预期的时间内完成。如果CAS失败,则调用者可以重试CAS操作或采取其他合适措施。
清单4中使用CAS重写了计数器类:

Listing 4.D . k Implementing, H f ` | a counter with compare-and-swap
public class R P CasCounter {

pl  f o { Brivate Si= & - a M J QmulatedCAS valf G K cu` ] [ $e;
public int getValue() {
return value.getValue();D d % = 3 ) D
}
publicN r o p h 4 I ) int increment() {
int oldI f * T j &Value = value.getValue();
while (v2 y dalue.compareAndSwap(oldValue, oldValue + 1)  !=  oldVaZ ~ g J } 9 C - `lue){ //不断重试
oldValue = value.getValue();
}
return oldValue + 1;
}

}
Lock-free和 wait-free 算法
wn ^ J T F @ g (ait-free算法保证每个线程都在执行(make progress)。相反的,lock-free算法要求至少有L l ( ( N h一个线程能取得进展(make progress)。
可见,wait-free比lock-free的要求更苛刻。
在过去的15* P 2 ^ B f y年中,人们对wait-free和lock-free算法(也称为非阻塞算法)进行了大量研究,并且发现了许多常见数据D 9 1 i . I ?结构的非阻塞算法实现。
非阻塞算法在操作系统和JVM级别广泛用于诸如线程和进程调度之类的任务。
尽管实现起来较为复杂,但与基于锁的替代方法相比,它们具有许多优点,
避免了诸如优先级反转和死锁之类的危险,竞争成本更低,并且协调发生在更细粒度级别,从而实现了更高程度的并行性。

原子变量类
在JDK5之前,要实现wait-free、l7 } ) + 8ock-fr9 N a g ? x d a 8ee的算法必须通过native方法。但是,在JDK5中增加了java.uti# i ] = $ _ ul.concurrent.atomic原子包后,情况发生了变化。
atomic包提供了多种原子变量类(AtomicInteger; AtomicLong; Atom; u zicReference; AtomicBoolean等)。
原子变量类都暴露了一个compare-and-set原语(类似compare-and-swap),它使用了平台上可用的最I v ) g快的原生结构,具体实现方= * I c案因平台而异(可能是compare-and-swap, load linked/store conditional, 或者最坏的情况使用 spin locks)。
可以将原子变量类视为vN T _ m a : y aolatile变量的泛化,它扩展了volatile变量的概念以支持原子的compare-anA d 9d-set更新。
原子变量的读写与volatile变量的读写具有相同的内存语义。
尽管原子变量类或许看起来像清单1中的示例,但是他们的相似只是表面上的。在幕后,对原子变量的操作变成了平台提供的硬件原语,例如compare-and-swap。

3 ? 7 s r d $ 4 .粒度意味着更轻量
优化并发应j t 9 T用的一个常用技术是减少锁对象的粒度,~ r U可以让更多的q P Z c 9 ~ 7 ~ k锁获取从竞争的变b ` [成非竞争的。
把锁变成原子变量也达到了同样的效果,通过切换到更小粒度的协调机制,减少有竞争的操作,以提升系统吞吐量。

java.util.concurrent包中的原子变量
juc包中几乎所有的类都直接或间接的使用了. k j原子变量,3 c (而不是synchronized。例如ConcurrentLinkedQueue类C , & # _直接使用原子变量类实现了wait-free算法,
再比如ConcurrentHashMap类在需要的地方使用ReentrantLock上锁,而ReentrantLock使用原e k子变量类维护等待锁的线程队列。
如果没有JDK5的改进,这些类就无法实现,JDK5暴露了一个接口让类库可以使用硬件级的同步原语。而原子变量类以及juc中的其他类又把这些x U 2 g U v P 特性暴露给了用户类。

使用原子变量实现更高的吞吐量
清单5中分别使用同步和CAS实现了伪随机数生成器(PR` ] s 7 D * = 3 KNG)。要注意的是CAS必须在循环中执行,因为它在成功之前可能会失败一次或多次,这几乎是CAS的使用范式g @ B - , r . e

Listing 5H r g p } q C q $. Implementing a thread-safe PRK C ! 6 RNG with synchronization and atomic variables
public class PseudoRandomUsingSyn5 7 x uch implements PseudoY { / Y 4 2Random {

pri] U . * $ w svate int9 J * 3 P o ^ ( @ seed;
public PseudoRandomUsingSynch(int s)E o P R x { seed = s; }
public synchronized int nextq  [ @ I ~Int(int n) {
int s = seeA = r xd;
seed = Util.c_ H  lalculateNext(seed);
return s % n;
}

}
public class PseudoRandomUsingAtomic implements PseudoRandom {

private final/ X n AtomicInteger seed;
public PseudoRando_ 7 X umUsingAtomic(int s) {
seed = new AtomicInteger(s);
}
public int nextInt(int n) {: i & @ z 6 k
for (/ } b d;;) {
int s = seed.get();
int nexts = UtilR G y U | j.calculateNext(s);
if (seed.compareA/ ~ TndSet(s, nexts))
return s % n;
}
}

}
下面的两张图分别显示了在8路Ultrasparc3和单核的Pentium 4上的线程数0 # c R g : B与随机数生成器的吞? D V O & 4 - * }吐量关系k 0 I 3 R E e ` H
你会看到,原子变量(ATOMIH [ N + 5 t A #C曲线)相对于ReentrantLock(LOCK曲线)有了进一步改进,后者相比同步(SYNC曲线)已经取得了很大改进。
由于每个工作单元的工作量很少,因此下面的图形可能低估了原子变量与ReentrantLock相比在伸缩性方便的优势。

大多数用户不大 , c可能使用原子变量自己实现非阻塞算法,他们更应该使用java.utiU A e K u b 4 P 4l.concurrent中提供的版本,例如CoF S A O * p b q :ncurrentLinkedQu3 L & p Geue。
如果你想知道与之前的JDK中的类相比juc中的类的性o k 9 7 + 9 ] n能提升来自何处?那就是使用了原子变量类开放的更细粒度、硬件级| 5 ^ ^ x F Q并发原语。
另外,开发人员可以直接将原子变量用作共享计数器、序列号生成器以及其他独立共享变量的高性能替代= - q [ X o z | ~品,否则必须通过同步来保护它们。

总结
JDK 5.0在高性能并发的开发上迈出了一大. S , s步。它在内部暴露新的低层协调原语,并提供了一组公共的原子变量类。现在,你可以使用Java语言开发第一个wait-free,lock-free的算法了。
不过,java.util.concurrent中的类都是基于这些原子变量工具构建的,与之前类似功能的类相比,在性能上有了质的飞跃,你可以直接使用他们。
尽管你可能永远O I * c d V @ M不会直接使用原子变量,但是他们仍然值得我们为其欢呼。

译者注
这篇文; p E y章是Brian Goetz发表于2004年,即J7 + 9 WDK5刚刚发布之后,作为Java布道者第一时间对JDK5的新特性做了很透彻的说明。
Brian Goetz是Java语言的架构师,是Lambda项目S K T O & _ & @的主导者,也是《Java Concurrency in Practice》作者。

参考:
原文:https://www.ibm.com/developerworks/library/j-jtp11234/i2 G vndex.html
More flexible, scalable l^ - # 2 V 5 x 2ocking in JDK 5.0
https://www.ibm.com/developerworks/java/libE ) - n B h L 1 5rary/j-jtp10264/index.html~ q n #
NoN + # z )-Blocking algorythm 维基百科:https://en.m.wikipedia.org/wiki/Non-blocking_algorithm
wait-free和lock-free:https://www.zhihu.com/question/295904223
原文地址hD ` E + s Y = %ttps:E v u (//www.cnblog% K d [ m v { ` ns.com/upn. s O Cot= I @e/p/12972751& 3 ( w q & 5.html