何為面試必問的CAS算法？

CSA算法

- CAS(Compare-And-Swap) 算法是硬體對于并發的支援,針對多處理器操作而設計的處理器中的一種特殊指令,用于管理對共享資料的并發通路;
- CAS 是一種無鎖的非阻塞算法（屬于樂觀鎖）的實作;
- CAS 包含了三個操作數:
  - 進行比較的舊預估值: A
  - 需要讀寫的記憶體值: V
  - 将寫入的更新值: B
  - 當且僅當 A == V 時, V = B, 否則,将不做任何操作,并且這個比較交換過程屬于原子操作;
           

CAS算法簡介

CAS是樂觀鎖技術，當多個線程嘗試使用CAS同時更新同一個變量時，隻有其中一個線程能更新變量的值，而其它線程都失敗，失敗的線程并不會被挂起，而是被告知這次競争中失敗，并可以再次嘗試。　　　 
           

代碼了解：

run(){
	System.out.println(num++);  // 1.把num讀到寄存器存儲在a  2.定義一個變量b使它等于a+1                    3.num=b
}

非原子性會造成的問題：
如果A線程執行到把num讀到寄存器，此時b線程搶到資源，num還未加一，b執行後列印的為+1後的值，然後線程A繼續執行，把寄存器中的a加一後，賦給num輸出，列印的也為+1後的值。是以會造成輸出兩次相同數值的情況
解決辦法：1.加同步鎖，但是執行效率慢
		2.CAS算法：
		　假如：AtomicInteger(原子變量)裡面的value原始值為3，即主記憶體中AtomicInteger的value為3，根據Java記憶體模型，線程A和線程B各自持有一份value的副本，值為3。 
線程A通過getIntVolatile(var1, var2)拿到value值3，這時線程A被挂起。 
線程B也通過getIntVolatile(var1, var2)方法擷取到value值3，運氣好，線程B沒有被挂起，并執行compareAndSwapInt方法比較記憶體值也為3，成功修改記憶體值為2。 
這時線程A恢複，執行compareAndSwapInt方法比較，發現自己手裡的值(3)和記憶體的值(2)不一緻，說明該值已經被其它線程提前修改過了，那隻能重新來一遍了。 （繼續拿現在存的value的值）
重新擷取value值，因為變量value被volatile修飾，是以其它線程對它的修改，線程A總是能夠看到，線程A繼續執行compareAndSwapInt進行比較替換，直到成功。
           

實作代碼：(看)

public class CompareAndSwapDemo {
	public static void main(String[] args) {
		CompareAndSwap compareAndSwap = new CompareAndSwap();
		for (int i = 0; i < 10; i++) {
			new Thread(new Runnable() {
				@Override
				public void run() {

					int expect = compareAndSwap.get();
					boolean b = compareAndSwap.compareAndSwap(expect, new Random().nextInt(101));
					System.out.println(b);
				}
			}).start();
		}
	}
}

class CompareAndSwap {
	private int value;

	/**
	 * 擷取值
	 * 
	 * @return
	 */
	public synchronized int get() {
		return value;
	}

	public synchronized boolean compareAndSwap(int expect, int newValue) {
        
		if (this.value == expect) {       //if内的代碼經過底層加工(CPU指令代碼完成)，為原子性的
			this.value = newValue;
			return true;
		}
		return false;
	}
}
           

ABA問題:

• 在CAS算法中，需要取出記憶體中某時刻的資料（由使用者完成），在下一時刻比較并替換（由CPU完成，該操作是原子的）。這個時間差中，會導緻資料的變化。

  假設如下事件序列：

  線程 1 從記憶體位置V中取出A。

  線程 2 從位置V中取出A。

  線程 2 進行了一些操作，将B寫入位置V。

  線程 2 将A再次寫入位置V。

  線程 1 進行CAS操作，發現位置V中仍然是A，操作成功。

盡管線程 1 的CAS操作成功，但不代表這個過程沒有問題——對于線程 1 ，線程 2 的修改已經丢失。

典型的ABA問題，也是很明顯的

如果變量V初次讀取的時候是A，并且在準備指派的時候檢查到它仍然是A，那能說明它的值沒有被其他線程修改過了嗎？

如果在這段期間曾經被改成B，然後又改回A，那CAS操作就會誤認為它從來沒有被修改過。針對這種情況，java并發包中提供了一個帶有标記的原子引用類AtomicStampedReference，它可以通過控制變量值的版本來保證CAS的正确性。AtomicStampedReference通過包裝[E,Integer]的元組來對對象标記版本戳stamp，進而避免ABA問題。

public class AbaDemo {
	private static AtomicStampedReference<Integer> integer=new AtomicStampedReference<Integer>(0, 0);
	public static void main(String[] args) throws Exception{
		for(int i=0;i<100;i++) {		
			//Thread.sleep(10);
			new Thread(new Runnable() {
				@Override
				public void run() {
					while(true) {
						int stamp = integer.getStamp();
						Integer reference = integer.getReference();
						if(integer.compareAndSet(reference, reference+1, stamp, stamp+1)) {
							System.out.println(reference+1);
							break;
						}
					}
				}
			}).start();
		}
	}
}