Java進(jìn)階：線程并發(fā)之深入理解CAS機(jī)制詳解
前言
獨(dú)占鎖是一種悲觀鎖，synchronized就是一種獨(dú)占鎖，會導(dǎo)致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖;
而另一個更加有效的鎖就是樂觀鎖。所謂樂觀鎖就是，每次不加鎖而是假設(shè)沒有沖突而去完成某項操作，如果因?yàn)闆_突失敗就重試，直到成功為止。樂觀鎖用到的機(jī)制就是CAS;
今天我們就來介紹下cas機(jī)制;
一、CAS介紹
1、什么是CAS
- CAS,compare and swap的縮寫，中文翻譯成比較并交換。CAS指令在Intel CPU上稱為CMPXCHG指令，它的作用是將指定內(nèi)存地址的內(nèi)容與所給的某個值相比，如果相等，則將其內(nèi)容替換為指令中提供的新值，如果不相等，則更新失敗從內(nèi)存領(lǐng)域來說這是樂觀鎖，因?yàn)樗趯蚕碜兞扛轮皶缺容^當(dāng)前值是否與更新前的值一致，如果是，則更新，如果不是，則無限循環(huán)執(zhí)行(稱為自旋)，直到當(dāng)前值與更新前的值一致為止，才執(zhí)行更新;
- CAS 操作包含三個操作數(shù) —— 內(nèi)存位置(V)、預(yù)期原值(A)和新值(B)。如果內(nèi)存位置的值與預(yù)期原值相匹配，那么處理器會自動將該位置值更新為新值 。否則，處理器不做任何操作。無論哪種情況，它都會在 CAS 指令之前返回該 位置的值;
- 通常將 CAS 用于同步的方式是從地址 V 讀取值 A，執(zhí)行多步計算來獲得新 值 B，然后使用 CAS 將 V 的值從 A 改為 B。如果 V 處的值尚未同時更改，則 CAS 操作成功;
- 類似于 CAS 的指令允許算法執(zhí)行讀-修改-寫操作，而無需害怕其他線程同時 修改變量，因?yàn)槿绻渌€程修改變量，那么 CAS 會檢測它(并失敗)，算法 可以對該操作重新計算;
2、那些地方采用了 CAS 機(jī)制
- 在 java.util.concurrent.atomic 包下，一系列以 Atomic 開頭的包裝類。例如AtomicBoolean，AtomicInteger，AtomicLong 等，它們就是典型的利用 CAS 機(jī)制實(shí)現(xiàn)的原子操作類;
- Lock 系列類的底層實(shí)現(xiàn)以及 Java 1.6 在 synchronized 轉(zhuǎn)換為重量級鎖之前，也會采用到 CAS 機(jī)制;
3、synchronized 和 CAS 的區(qū)別
- synchronized 采用的是 CPU 悲觀鎖機(jī)制，即線程獲得的是獨(dú)占鎖。獨(dú)占鎖就意味著 其他線程只能依靠阻塞來等待線程釋放鎖。而在 CPU 轉(zhuǎn)換線程阻塞時會引起線程上下文切換，當(dāng)有很多線程競爭鎖的時候，會引起 CPU 頻繁的上下文切換導(dǎo)致效率很低。盡管 Java1.6 為 synchronized 做了優(yōu)化，增加了從偏向鎖到輕量級鎖再到重量級鎖的過度，但是在最終轉(zhuǎn)變?yōu)橹亓考夋i之后，性能仍然較低;
- Synchronized(未優(yōu)化前)最主要的問題是：在存在線程競爭的情況下會出現(xiàn)線程阻塞和喚醒鎖帶來的性能問題，因?yàn)檫@是一種互斥同步(阻塞同步)。而CAS并不是武斷的間線程掛起，當(dāng)CAS操作失敗后會進(jìn)行一定的嘗試，而非進(jìn)行耗時的掛起喚醒的操作，因此也叫做非阻塞同步。這是兩者主要的區(qū)別;
- 使用CAS時非阻塞同步，也就是說不會將線程掛起，會自旋(無非就是一個死循環(huán))進(jìn)行下一次嘗試，如果這里自旋時間過長對性能是很大的消耗。如果JVM能支持處理器提供的pause指令，那么在效率上會有一定的提升;
- CAS它當(dāng)中使用了3個基本操作數(shù)：內(nèi)存地址 V，舊的預(yù)期值 A，要修改的新值 B。采用的是一種樂觀鎖的機(jī)制，它不會阻塞任何線程，所以在效率上，它會比 synchronized 要高。所謂樂觀鎖就是：每次不加鎖而是假設(shè)沒有沖突而去完成某項操作，如果因?yàn)闆_突失敗就重試，直到成功為止;
4、為什么需要CAS機(jī)制
我們經(jīng)常使用volatile關(guān)鍵字修飾某一個變量，表明這個變量是全局共享的一個變量，同時具有了可見性和有序性。但是卻沒有原子性。比如說一個常見的操作a++。這個操作其實(shí)可以細(xì)分成三個步驟：
(1)從內(nèi)存中讀取a
(2)對a進(jìn)行加1操作
(3)將a的值重新寫入內(nèi)存中
在單線程狀態(tài)下這個操作沒有一點(diǎn)問題，但是在多線程中就會出現(xiàn)各種各樣的問題了。因?yàn)榭赡芤粋€線程對a進(jìn)行了加1操作，還沒來得及寫入內(nèi)存，其他的線程就讀取了舊值。造成了線程的不安全現(xiàn)象;
Volatile關(guān)鍵字可以保證線程間對于共享變量的可見性可有序性，可以防止CPU的指令重排序(DCL單例)，但是無法保證操作的原子性，所以jdk1.5之后引入CAS利用CPU原語保證線程操作的院子性;
CAS操作由處理器提供支持，是一種原語。原語是操作系統(tǒng)或計算機(jī)網(wǎng)絡(luò)用語范疇。是由若干條指令組成的，用于完成一定功能的一個過程，具有不可分割性，即原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷。如 Intel 處理器，比較并交換通過指令的 cmpxchg 系列實(shí)現(xiàn);
二、cas底層實(shí)現(xiàn)
1、底層依靠Unsafe的CAS操作來保證原子性;
CAS的實(shí)現(xiàn)主要在JUC中的atomic包，我們以AtomicInteger類為例：
- /**
- * Atomically adds the given value to the current value.
- *
- * @param delta the value to add
- * @return the previous value
- */
- public final int getAndAdd(int delta) {
- return unsafe.getAndAddInt(this, valueOffset, delta);
- }
- public final int incrementAndGet() {
- for (;;) {
- int current = get();
- int next = current + 1;
- if (compareAndSet(current, next))
- return next;
- }
- }
- private volatile int value;
- public final int get() {
- return value;
- }
代碼是一個無限循環(huán)，也就是CAS的自旋。循環(huán)體當(dāng)中做了三件事：
獲取當(dāng)前值;
當(dāng)前值+1，計算出目標(biāo)值;
進(jìn)行CAS操作，如果成功則跳出循環(huán)(當(dāng)前值和目標(biāo)值相等)，如果失敗則重復(fù)上述步驟;
2、Unsafe.class
- public final int getAndAddInt(Object var1, long var2, int var4) {
- int var5;
- do {
- var5 = this.getIntVolatile(var1, var2);
- } while (!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//native方法
- return var5;
- }
- ********
- public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);//底層c++實(shí)現(xiàn)
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);//底層c++實(shí)現(xiàn)
3、compareAndSwapInt為native方法，對應(yīng)底層hotspot虛擬機(jī)unsage.cpp
- UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
- UnsafeWrapper("Unsafe_CompareAndSwapInt");
- oop p = JNIHandles::resolve(obj);
- jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
- return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
- UNSAFE_END
- ***
這里可以看到最終使用了Atomic::cmpxchg來保證原子性，可繼續(xù)跟進(jìn)代碼
4、Atomic::cmpxchg針對不同平臺有不同的實(shí)現(xiàn)方式
- ***
- // Adding a lock prefix to an instruction on MP machine
- #define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
- ***
- inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
- int mp = os::is_MP();
- __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
- : "=a" (exchange_value)
- : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
- : "cc", "memory");
- return exchange_value;
- }
最重要的指令為 LOCK_IF_MP ， MP是指多CPU(multi processors)，最終意義為多CPU的情況下需要lock，通過lock的方式來保證原子;
lock解釋：
- 確保后續(xù)指令執(zhí)行的原子性;
- 在Pentium及之前的處理器中，帶有l(wèi)ock前綴的指令在執(zhí)行期間會鎖住總線，使得其它處理器暫時無法通過總線訪問內(nèi)存，很顯然，這個開銷很大。在新的處理器中，Intel使用緩存鎖定來保證指令執(zhí)行的原子性，緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷;
- 禁止該指令與前面和后面的讀寫指令重排序;
- 把寫緩沖區(qū)的所有數(shù)據(jù)刷新到內(nèi)存中;
總之：JAVA中我們使用到涉及到CAS操作的底層實(shí)現(xiàn)為對應(yīng)平臺虛擬機(jī)中的c++代碼(lock指令)實(shí)現(xiàn)來保證原子性;
三、CAS 的缺點(diǎn)及解決方式
CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題。ABA問題，循環(huán)時間長開銷大和只能保證一個共享變量的原子操作;
1、ABA問題：因?yàn)镃AS需要在操作值的時候檢查下值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新，但是如果一個值原來是A，變成了B，又變成了A， 那么使用CAS進(jìn)行檢查時會發(fā)現(xiàn)它的值沒有發(fā)生變化，但是實(shí)際上卻變化了;
ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加一，那么A-B-A 就會變成1A-2B-3A;
從Java1.5開始JDK的atomic包里提供了一個類 AtomicStampedReference 來解決ABA問題。這個類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值;
2、循環(huán)時間長開銷大：在并發(fā)量比較高的情況下，如果許多線程反復(fù)嘗試更新某一個變量，即自旋CAS如果長時間不成功，會給CPU帶來非常大的執(zhí)行開銷;
如果JVM能支持處理器提供的pause指令，那么效率會有一定的提升。pause指令有兩個作用，第一它可以延遲流水線執(zhí)行指令(de-pipeline),使CPU不會消耗過多的執(zhí)行資源，延遲的時間取決于具體實(shí)現(xiàn)的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環(huán)的時候因內(nèi)存順序沖突(memory order violation)而引起CPU流水線被清空(CPU pipeline flush)，從而提高CPU的執(zhí)行效率;
代碼層面，破壞掉for死循環(huán)，當(dāng)自旋超過一定時間或者一定次數(shù)時，return退出;
使用類似ConcurrentHashMap的方法。當(dāng)多個線程競爭時，將粒度變小，將一個變量拆分為多個變量，達(dá)到多個線程訪問多個資源的效果，最后再調(diào)用sum把它合起來，能降低CPU消耗，但是治標(biāo)不治本;
3、只能保證一個共享變量的原子操作：當(dāng)對一個共享變量執(zhí)行操作時，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對多個共享變量操作時，循環(huán)CAS就無法保證操作的原子性;
這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如有兩個共享變量i=2,j=a，合并一下ij=2a，然后用CAS來操作ij;
從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性，你可以把多個變量放在一個對象里來進(jìn)行CAS操作;
四、CAS使用的時機(jī)
線程數(shù)較少、等待時間短可以采用自旋鎖進(jìn)行CAS嘗試拿鎖，較于synchronized高效;
線程數(shù)較大、等待時間長，不建議使用自旋鎖，占用CPU較高;
總結(jié)
CAS可以保證多線程對數(shù)據(jù)寫操作時數(shù)據(jù)的一致性;
CAS的思想：三個參數(shù)，一個當(dāng)前內(nèi)存值V、舊的預(yù)期值A(chǔ)、即將更新的值B，當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時，將內(nèi)存值修改為B并返回true，否則什么都不做，并返回false;
