CAS (Compare and Swap)
CAS字面意思為比較并交換.CAS 有 3 個運算元，分別是：記憶體值 M，期望值 E，更新值 U，當且僅當記憶體值 M 和期望值 E 相等時，將記憶體值 M 修改為 U，否則什么都不做，
1.CAS的應用場景
CAS 只適用于執行緒沖突較少的情況，
CAS 的典型應用場景是：
- 原子類
- 自旋鎖
1.1 原子類
原子類是 CAS 在 Java 中最典型的應用，
我們先來看一個常見的代碼片段，
if(a==b) {
a++;
}
如果 a++ 執行前， a 的值被修改了怎么辦？還能得到預期值嗎？出現該問題的原因是在并發環境下，以上代碼片段不是原子操作，隨時可能被其他執行緒所篡改，
解決這種問題的最經典方式是應用原子類的 incrementAndGet 方法，
public class AtomicIntegerDemo {
public static void main(String[] args) throws InterruptedException {
ExecutorService executorService = Executors.newFixedThreadPool(3);
final AtomicInteger count = new AtomicInteger(0);
for (int i = 0; i < 10; i++) {
executorService.execute(new Runnable() {
@Override
public void run() {
count.incrementAndGet();
}
});
}
executorService.shutdown();
executorService.awaitTermination(3, TimeUnit.SECONDS);
System.out.println("Final Count is : " + count.get());
}
}
J.U.C 包中提供了 AtomicBoolean、AtomicInteger、AtomicLong 分別針對 Boolean、Integer、Long 執行原子操作，操作和上面的示例大體相似，不做贅述，
1.2 自旋鎖
利用原子類（本質上是 CAS），可以實作自旋鎖，
所謂自旋鎖，是指執行緒反復檢查鎖變數是否可用，直到成功為止，由于執行緒在這一程序中保持執行，因此是一種忙等待，一旦獲取了自旋鎖，執行緒會一直保持該鎖，直至顯式釋放自旋鎖，
示例：非執行緒安全示例
public class AtomicReferenceDemo {
private static int ticket = 10;
public static void main(String[] args) {
ExecutorService executorService = Executors.newFixedThreadPool(3);
for (int i = 0; i < 5; i++) {
executorService.execute(new MyThread());
}
executorService.shutdown();
}
static class MyThread implements Runnable {
@Override
public void run() {
while (ticket > 0) {
System.out.println(Thread.currentThread().getName() + " 賣出了第 " + ticket + " 張票");
ticket--;
}
}
}
}
輸出結果：
pool-1-thread-2 賣出了第 10 張票
pool-1-thread-1 賣出了第 10 張票
pool-1-thread-3 賣出了第 10 張票
pool-1-thread-1 賣出了第 8 張票
pool-1-thread-2 賣出了第 9 張票
pool-1-thread-1 賣出了第 6 張票
pool-1-thread-3 賣出了第 7 張票
pool-1-thread-1 賣出了第 4 張票
pool-1-thread-2 賣出了第 5 張票
pool-1-thread-1 賣出了第 2 張票
pool-1-thread-3 賣出了第 3 張票
pool-1-thread-2 賣出了第 1 張票
很明顯，出現了重復售票的情況，
【示例】使用自旋鎖來保證執行緒安全
可以通過自旋鎖這種非阻塞同步來保證執行緒安全，下面使用 AtomicReference 來實作一個自旋鎖，
public class AtomicReferenceDemo2 {
private static int ticket = 10;
public static void main(String[] args) {
threadSafeDemo();
}
private static void threadSafeDemo() {
SpinLock lock = new SpinLock();
ExecutorService executorService = Executors.newFixedThreadPool(3);
for (int i = 0; i < 5; i++) {
executorService.execute(new MyThread(lock));
}
executorService.shutdown();
}
static class SpinLock {
private AtomicReference<Thread> atomicReference = new AtomicReference<>();
public void lock() {
Thread current = Thread.currentThread();
while (!atomicReference.compareAndSet(null, current)) {}
}
public void unlock() {
Thread current = Thread.currentThread();
atomicReference.compareAndSet(current, null);
}
}
static class MyThread implements Runnable {
private SpinLock lock;
public MyThread(SpinLock lock) {
this.lock = lock;
}
@Override
public void run() {
while (ticket > 0) {
lock.lock();
if (ticket > 0) {
System.out.println(Thread.currentThread().getName() + " 賣出了第 " + ticket + " 張票");
ticket--;
}
lock.unlock();
}
}
}
}
輸出結果：
pool-1-thread-2 賣出了第 10 張票
pool-1-thread-1 賣出了第 9 張票
pool-1-thread-3 賣出了第 8 張票
pool-1-thread-2 賣出了第 7 張票
pool-1-thread-3 賣出了第 6 張票
pool-1-thread-1 賣出了第 5 張票
pool-1-thread-2 賣出了第 4 張票
pool-1-thread-1 賣出了第 3 張票
pool-1-thread-3 賣出了第 2 張票
pool-1-thread-1 賣出了第 1 張票
2.CAS 的原理
Java 主要利用 Unsafe 這個類提供的 CAS 操作，Unsafe 的 CAS 依賴的是 JVM 針對不同的作業系統實作的硬體指令 Atomic::cmpxchg，Atomic::cmpxchg 的實作使用了匯編的 CAS 操作，并使用 CPU 提供的 lock 信號保證其原子性，
3.CAS 帶來的問題
一般情況下，CAS 比鎖性能更高，因為 CAS 是一種非阻塞演算法，所以其避免了執行緒阻塞和喚醒的等待時間，
但是，事物總會有利有弊，CAS 也存在三大問題：
ABA 問題回圈時間長開銷大只能保證一個共享變數的原子性
如何解決這三個問題:
3.1 ABA 問題
如果一個變數初次讀取的時候是 A 值，它的值被改成了 B，后來又被改回為 A，那 CAS 操作就會誤認為它從來沒有被改變過，
J.U.C 包提供了一個帶有標記的原子參考類 如:AtomicStampedReference 來解決這個問題，它可以通過控制變數值的版本來保證 CAS 的正確性，大部分情況下 ABA 問題不會影響程式并發的正確性，如果需要解決 ABA 問題，改用傳統的互斥同步可能會比原子類更高效，
解決方案：增加標志位，例如：AtomicMarkableReference、AtomicStampedReference
3.2 回圈時間長開銷大
自旋 CAS （不斷嘗試，直到成功為止）如果長時間不成功，會給 CPU 帶來非常大的執行開銷，
如果 JVM 能支持處理器提供的 pause 指令那么效率會有一定的提升，pause 指令有兩個作用：
- 它可以延遲流水線執行指令（de-pipeline）,使 CPU 不會消耗過多的執行資源，延遲的時間取決于具體實作的版本，在一些處理器上延遲時間是零，
- 它可以避免在退出回圈的時候因記憶體順序沖突（memory order violation）而引起 CPU 流水線被清空（CPU pipeline flush），從而提高 CPU 的執行效率，
解決方案：因為是while回圈，消耗必然大，設定嘗試次數上限
3.3只能保證一個共享變數的原子性
當對一個共享變數執行操作時，我們可以使用回圈 CAS 的方式來保證原子操作，但是對多個共享變數操作時，回圈 CAS 就無法保證操作的原子性，這個時候就可以用鎖，
或者有一個取巧的辦法，就是把多個共享變數合并成一個共享變數來操作，比如有兩個共享變數 i ＝ 2, j = a，合并一下 ij=2a，然后用 CAS 來操作 ij，從 Java 1.5 開始 JDK 提供了 AtomicReference 類來保證參考物件之間的原子性
解決方案：用AtomicReference把多個變數封裝成一個物件來進行CAS操作.
關注公眾號:java寶典
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/200878.html
標籤：其他
上一篇：040_陣列
下一篇：「MCOI-03」村國題解