一、無鎖算法
CAS（比較與交換，Compare and swap） 是一種有名的無鎖算法。無鎖編程，即不使用鎖的情況下實現(xiàn)多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實現(xiàn)變量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。實現(xiàn)非阻塞同步的方案稱為“無鎖編程算法”（ Non-blocking algorithm）。?
相對應(yīng)的，獨占鎖是一種悲觀鎖，synchronized就是一種獨占鎖，它假設(shè)最壞的情況，并且只有在確保其它線程不會造成干擾的情況下執(zhí)行，會導(dǎo)致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖。?
使用lock實現(xiàn)線程同步有很多缺點：?
* 產(chǎn)生競爭時，線程被阻塞等待，無法做到線程實時響應(yīng)。?
* dead lock，死鎖。?
* live lock。?
* 優(yōu)先級翻轉(zhuǎn)。?
* 使用不當，造成性能下降。?
當然在部分情況下，目前來看，無鎖編程并不能替代 lock。
非同步阻塞的實現(xiàn)可以分成三個級別：wait-free/lock-free/obstruction-free。?
wait-free?
是最理想的模式，整個操作保證每個線程在有限步驟下完成。?
保證系統(tǒng)級吞吐（system-wide throughput）以及無線程饑餓。?
截止2011年，沒有多少具體的實現(xiàn)。即使實現(xiàn)了，也需要依賴于具體CPU。?
lock-free?
允許個別線程饑餓，但保證系統(tǒng)級吞吐。確保至少有一個線程能夠繼續(xù)執(zhí)行。?
wait-free的算法必定也是lock-free的。?
obstruction-free?
在任何時間點，一個線程被隔離為一個事務(wù)進行執(zhí)行（其他線程suspended），并且在有限步驟內(nèi)完成。在執(zhí)行過程中，一旦發(fā)現(xiàn)數(shù)據(jù)被修改（采用時間戳、版本號），則回滾。也叫做樂觀鎖，即樂觀并發(fā)控制(OOC)。事務(wù)的過程是：1讀取，并寫時間戳；2準備寫入，版本校驗；3校驗通過則寫入，校驗不通過，則回滾。?
lock-free必定是obstruction-free的。
CAS（比較與交換，Compare and swap） 是一種有名的無鎖算法。CAS, CPU指令，在大多數(shù)處理器架構(gòu)，包括IA32、Space中采用的都是CAS指令，CAS的語義是“我認為V的值應(yīng)該為A，如果是，那么將V的值更新為B，否則不修改并告訴V的值實際為多少”，CAS是項 樂觀鎖 技術(shù)，當多個線程嘗試使用CAS同時更新同一個變量時，只有其中一個線程能更新變量的值，而其它線程都失敗，失敗的線程并不會被掛起，而是被告知這次競爭中失敗，并可以再次嘗試。CAS有3個操作數(shù)，內(nèi)存值V，舊的預(yù)期值A(chǔ)，要修改的新值B。當且僅當預(yù)期值A(chǔ)和內(nèi)存值V相同時，將內(nèi)存值V修改為B，否則什么都不做。?
java.util.concurrent.atomic中的AtomicXXX，都使用了這些底層的JVM支持為數(shù)字類型的引用類型提供一種高效的CAS操作，而在java.util.concurrent中的大多數(shù)類在實現(xiàn)時都直接或間接的使用了這些原子變量類，這些原子變量都調(diào)用了 sun.misc.Unsafe 類庫里面的 CAS算法，用CPU指令來實現(xiàn)無鎖自增，JDK源碼：
public final int getAndIncrement() {
? ? ? ? for (;;) {?
? ? ? ? ? ? int current = get();?
? ? ? ? ? ? int next = current + 1;?
? ? ? ? ? ? if (compareAndSet(current, next))?
? ? ? ? ? ? ? ? return current;?
? ? ? ? }?
}??
public final boolean compareAndSet(int expect, int update) {?
? ? return unsafe.compareAndSwapInt(this, valueOffset, expect, update);?
}
因而在大部分情況下，java中使用Atomic包中的incrementAndGet的性能比用synchronized高出幾倍。
thread1意圖對val=1進行操作變成2，cas(val,1,2)。?
thread1先讀取val=1；thread1被搶占（preempted），讓thread2運行。?
thread2 修改val=3，又修改回1。?
thread1繼續(xù)執(zhí)行，發(fā)現(xiàn)期望值與“原值”（其實被修改過了）相同，完成CAS操作。?
使用CAS會造成ABA問題，特別是在使用指針操作一些并發(fā)數(shù)據(jù)結(jié)構(gòu)時。?
解決方案?
ABA?：添加額外的標記用來指示是否被修改。?
從Java1.5開始JDK的atomic包里提供了一個類AtomicStampedReference來解決ABA問題。這個類的compareAndSet方法作用是首先檢查當前引用是否等于預(yù)期引用，并且當前標志是否等于預(yù)期標志，如果全部相等，則以原子方式將該引用和該標志的值設(shè)置為給定的更新值。
