並行程式設計之CAS
一，問題引入
1.需求
模擬網站存取量統計，假設現在有100個使用者，每個人存取10次。
/**
* @author yhd
* @createtime 2020/10/3 19:05
* @description 模擬網站存取量統計
* 假設現在有100個使用者，每個人存取10次。
*/
public class DemoA {
/**
* 模擬使用者存取
*/
public static int count = 0;
public static void request() {
try {
count++;
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public static void main(String[] args) throws InterruptedException {
//開始時間
long startTime = System.currentTimeMillis();
int size = 100;
CountDownLatch latch = new CountDownLatch(size);
//模擬100個使用者
for (int i = 0; i < size; i++) {
new Thread(() -> {
//模擬每個使用者存取10次
for (int j = 0; j < 10; j++) {
request();
}
latch.countDown();
}, "使用者" + String.valueOf(i)).start();
}
latch.await();
//結束時間
long endTime = System.currentTimeMillis();
System.out.println(Thread.currentThread().getName()+"統計完成：耗時" + (endTime - startTime) / 1000 + "s"+" 存取次數："+count);
}
//結果：main統計完成：耗時10s 存取次數：805
}
我們發現輸出結果始終是錯誤的。
1.分析問題出在哪裡？
count++ 操做實際上是由3步來完成的！（jvm執行引擎）
1.獲取count的值，記作A：A=count
2.將A的值+1，得到B ： B=A+1
3.將B的值賦給count
如果有A，B兩個執行緒同時執行count++，他們同時執行到上面步驟的第一步，得到的count是一樣的，3步操做結束後，count只加1，導致count結果不正確！
2.怎麼解決結果不正確的問題？
對count操做的時候，我們讓多個執行緒排隊處理，多個執行緒同時到達request()方法的時候，只能允許一個執行緒進去操做其他執行緒在外面等著，等裡面的處理完畢之後，外面等著的再進去一個，這樣操做的count++就是排隊進行的，結果一定是正確的。
3.怎麼實現排隊效果？
Java中的synchronized和ReentranLock都可以實現對資源枷鎖，保證並行正確性，多執行緒情況下可以保證被鎖住的資源被「序列」存取。
2.程式碼改進（執行緒安全）
/**
* @author yhd
* @createtime 2020/10/3 19:05
* @description 模擬網站存取量統計
* 假設現在有100個使用者，每個人存取10次。
*/
public class DemoA {
/**
* 模擬使用者存取
*/
public static int count = 0;
public synchronized static void request() {
try {
count++;
TimeUnit.MILLISECONDS.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public static void main(String[] args) throws InterruptedException {
//開始時間
long startTime = System.currentTimeMillis();
int size = 100;
CountDownLatch latch = new CountDownLatch(size);
//模擬100個使用者
for (int i = 0; i < size; i++) {
new Thread(() -> {
//模擬每個使用者存取10次
for (int j = 0; j < 10; j++) {
request();
}
latch.countDown();
}, "使用者" + String.valueOf(i)).start();
}
latch.await();
//結束時間
long endTime = System.currentTimeMillis();
System.out.println(Thread.currentThread().getName()+"統計完成：耗時" + (endTime - startTime) + "ms"+" 存取次數："+count);
}
//結果：main統計完成：耗時5665ms 存取次數：1000
}
結果正確了，可是耗時很長。
1.耗時太長的原因是什麼呢？
程式中的request()方法使用synchronized關鍵字修飾，保證了並行情況下，request方法同一時刻只允許同一個執行緒進入，request加鎖相當於序列執行了，count的結果和我們預期的一致，只是消耗的時間太長了。
2.如何解決耗時長的問題？
count++操做實際上是由三步來完成的！
1.獲取count的值，記作A：A=count
2.將A的值+1，得到B ： B=A+1
3.將B的值賦給count
升級第三步的實現：
1.獲取鎖
2.獲取一下count最新值，記作LV
3.判斷LV是否等於A，如果相等，則將B的值賦值給count，並返回true，否則返回false。
4.釋放鎖
3.再次優化（執行時間）
/**
* @author yhd
* @createtime 2020/10/3 19:05
* @description 模擬網站存取量統計
* 假設現在有100個使用者，每個人存取10次。
*/
public class DemoA {
/**
* 模擬使用者存取
*/
public volatile static int count = 0;
public static void request() {
try {
while (!compareAndSwap((getCount()), count + 1)) {
}
TimeUnit.MILLISECONDS.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
/**
* 比較count的預期值與當前值，如果相等將新值賦值給count，並返回true，否則返回false。
*
* @param expectCount 預期值
* @param newCount 新值
* @return count+1；
*/
public synchronized static boolean compareAndSwap(int expectCount, int newCount) {
if (getCount() == expectCount) {
count = newCount;
return true;
}
return false;
}
/**
* 獲取count的值
*
* @return
*/
public static int getCount() {
return count;
}
public static void main(String[] args) throws InterruptedException {
//開始時間
long startTime = System.currentTimeMillis();
int size = 100;
CountDownLatch latch = new CountDownLatch(size);
//模擬100個使用者
for (int i = 0; i < size; i++) {
new Thread(() -> {
//模擬每個使用者存取10次
for (int j = 0; j < 10; j++) {
request();
}
latch.countDown();
}, "使用者" + String.valueOf(i)).start();
}
latch.await();
//結束時間
long endTime = System.currentTimeMillis();
System.out.println(Thread.currentThread().getName() + "統計完成：耗時" + (endTime - startTime) + "ms" + " 存取次數：" + count);
}
//結果：main統計完成：耗時88ms 存取次數：1000
}
此時保證了資料正確的同時，效率也得到了極大的提升。
二，java中對CAS的支援
CAS 全稱「CompareAndSwap」，中文翻譯過來為「比較並替換」
1.定義
CAS操作包含三個運算元————記憶體位置（V）、期望值（A）和新值（B）。
如果記憶體位置的值與期望值匹配，那麼處理器會自動將該位置值更新為新值。否則，
處理器不作任何操作。無論哪種情況，它都會在CAS指令之前返回該位置的值。
（CAS在一些特殊情況下僅返回CAS是否成功，而不提取當前值）CAS有效的說明了
「我認為位置V應該包含值A；如果包含該值，則將B放到這個位置；否則，不要更改
該位置的值，只告訴我這個位置現在的值即可。」
2.如何使用jdk提供的對cas的支援？
java中提供了對CAS操作的支援，具體在sun.misc.unsafe類中，宣告如下：
public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
引數var1：表示要操作的物件
引數var2：表示要操作物件中屬性地址的偏移量
引數var4：表示需要修改資料的期望的值
引數var5：表示需要修改為的新值
3.cas的實現原理
CAS通過呼叫JNI的程式碼實現，JNI：java Native Interface，允許java呼叫其它語言。而compareAndSwapxxx系列的方法就是藉助「C語言」來呼叫cpu底層指令實現的。
以常用的Intel x86平臺來說，最終對映到的cpu的指令為「cmpxchg」，這是一個原子指令，cpu執行此命令時，實現比較並替換的操作！
4.cmpxchg怎麼保證多核心下的執行緒安全？
系統底層進行CAS操作的時候，會判斷當前系統是否為多核心繫統，如果是就給「匯流排」加鎖，只有一個執行緒會對匯流排加鎖成功，加鎖成功之後會執行CAS操作，也就是說CAS的原子性是平臺級別的！
5.cas存在的問題
1.ABA問題
執行緒1準備用CAS將變數的值由A替換為B，在此之前，執行緒2將變數的值由A替換為C，又由C替換為A，然後執行緒1執行CAS時發現變數的值仍然為A，所以CAS成功。但實際上這時的現場已經和最初不同了，儘管CAS成功，但可能存在潛藏的問題。
舉例：一個小偷，把別人家的錢偷了之後又還了回來，還是原來的錢嗎，你老婆出軌之後又回來，還是原來的老婆嗎？ABA問題也一樣，如果不好好解決就會帶來大量的問題。最常見的就是資金問題，也就是別人如果挪用了你的錢，在你發現之前又還了回來。但是別人卻已經觸犯了法律。
2.迴圈時間長開銷大
3.只能保證一個共用變數的原子操作
6.程式碼模擬ABA問題
/**
* @author yhd
* @createtime 2020/10/3 21:17
* 演示ABA問題
*/
public class CasAbaDemo {
//cas共用變數
public static AtomicInteger a = new AtomicInteger(1);
public static void main(String[] args) {
//主執行緒
new Thread(() -> {
System.out.println("操作執行緒" + Thread.currentThread().getName() + ", 初始值：" + a.get());
try {
//期望值
int expectNum = a.get();
//新值
int newNum = a.get() + 1;
//將cpu執行權讓給干擾執行緒
Thread.sleep(1000);
boolean flag = a.compareAndSet(expectNum, newNum);
System.out.println("操作執行緒" + Thread.currentThread().getName() + "，CAS操作：" + flag);
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "main"
).start();
//干擾執行緒
new Thread(() -> {
try {
//將cpu的執行權先交給主執行緒
Thread.sleep(20);
//+1
a.incrementAndGet();
System.out.println("操作執行緒" + Thread.currentThread().getName() + "，【increment】,值=" + a.get());
//-1
a.decrementAndGet();
System.out.println("操作執行緒" + Thread.currentThread().getName() + "，【decrement】,值=" + a.get());
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "other").start();
}
}
控制檯列印：
7.jdk對於cas問題的解決
1.如何解決ABA問題
解決ABA最簡單的方案就是給值加一個修改版本號，每次值變化，都會修改它的版本號，CAS操作時都去對比此版本號。
java中ABA解決方法（AtomicStampedReference）
AtomicStampedReference主要包含一個物件參照及一個可以自動更新的整數「stamp」的pair物件來解決ABA問題。
/**
* @author yhd
* @createtime 2020/10/3 21:17
* 解決ABA問題
*/
public class CasAbaDemo {
//cas共用變數
public static AtomicStampedReference<Integer> a = new AtomicStampedReference(1, 1);
public static void main(String[] args) {
//主執行緒
new Thread(() -> {
System.out.println("操作執行緒" + Thread.currentThread().getName() + ", 初始值：" + a.getReference());
try {
//期望值
int expectNum = a.getReference();
//新值
int newNum = a.getReference() + 1;
//期望版本
int expectVersion = a.getStamp();
//新的版本
int newVersion = a.getStamp() + 1;
//將cpu執行權讓給干擾執行緒
Thread.sleep(1000);
boolean flag = a.compareAndSet(expectNum, newNum, expectVersion, newVersion);
System.out.println("操作執行緒" + Thread.currentThread().getName() + "，CAS操作：" + flag);
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "main"
).start();
//干擾執行緒
new Thread(() -> {
try {
//將cpu的執行權先交給主執行緒
Thread.sleep(20);
//+1
a.compareAndSet(a.getReference(), a.getReference() + 1, a.getStamp(), a.getStamp() + 1);
System.out.println("操作執行緒" + Thread.currentThread().getName() + "，【increment】,值=" + a.getReference());
//-1
a.compareAndSet(a.getReference(), a.getReference() - 1, a.getStamp(), a.getStamp() + 1);
System.out.println("操作執行緒" + Thread.currentThread().getName() + "，【decrement】,值=" + a.getReference());
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "other").start();
}
}
2.AtomicStampedReference
1.內部類Pair
private static class Pair<T> {
final T reference; //資料參照
final int stamp; //版本號
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
//建立一個新的pair物件
static <T> Pair<T> of(T reference, int stamp) {
return new Pair<T>(reference, stamp);
}
}
將資料和版本號封裝成一個物件進行比較，懂的人自然懂。
2.compareAndSet（）
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
//期望參照和當前參照一致
expectedReference == current.reference &&
//期望版本與當前版本一致
expectedStamp == current.stamp &&
(
//表示版本號對應上的同時要修改的值與原來的值相等，
//就沒有必要建立一個新的Pair物件了
(newReference == current.reference &&
newStamp == current.stamp)
||
//否則的話，建立新的物件
casPair(current, Pair.of(newReference, newStamp)));
}
3.casPair（）
private boolean casPair(Pair<V> cmp, Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}
實際上呼叫的還是unsafe類裡面的compareAndSwapObject（）。