一腊尚、無鎖算法
CAS（比較與交換喜每，Compare and swap） 是一種有名的無鎖算法间护。無鎖編程企蹭，即不使用鎖的情況下實(shí)現(xiàn)多線程之間的變量同步白筹，也就是在沒有線程被阻塞的情況下實(shí)現(xiàn)變量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）练对。實(shí)現(xiàn)非阻塞同步的方案稱為“無鎖編程算法”（ Non-blocking algorithm）遍蟋。?
相對應(yīng)的，獨(dú)占鎖是一種悲觀鎖螟凭，synchronized就是一種獨(dú)占鎖虚青，它假設(shè)最壞的情況，并且只有在確保其它線程不會造成干擾的情況下執(zhí)行螺男，會導(dǎo)致其它所有需要鎖的線程掛起棒厘，等待持有鎖的線程釋放鎖。?
使用lock實(shí)現(xiàn)線程同步有很多缺點(diǎn)：?
* 產(chǎn)生競爭時(shí)下隧，線程被阻塞等待奢人，無法做到線程實(shí)時(shí)響應(yīng)。?
* dead lock淆院，死鎖何乎。?
* live lock。?
* 優(yōu)先級翻轉(zhuǎn)土辩。?
* 使用不當(dāng)支救，造成性能下降。?
當(dāng)然在部分情況下拷淘，目前來看各墨，無鎖編程并不能替代 lock。
非同步阻塞的實(shí)現(xiàn)可以分成三個(gè)級別：wait-free/lock-free/obstruction-free贬堵。?
wait-free?
是最理想的模式，整個(gè)操作保證每個(gè)線程在有限步驟下完成结洼。?
保證系統(tǒng)級吞吐（system-wide throughput）以及無線程饑餓黎做。?
截止2011年，沒有多少具體的實(shí)現(xiàn)松忍。即使實(shí)現(xiàn)了引几，也需要依賴于具體CPU。?
lock-free?
允許個(gè)別線程饑餓挽铁，但保證系統(tǒng)級吞吐伟桅。確保至少有一個(gè)線程能夠繼續(xù)執(zhí)行。?
wait-free的算法必定也是lock-free的情臭。?
obstruction-free?
在任何時(shí)間點(diǎn)芒炼，一個(gè)線程被隔離為一個(gè)事務(wù)進(jìn)行執(zhí)行（其他線程suspended）癌瘾，并且在有限步驟內(nèi)完成。在執(zhí)行過程中盖腕，一旦發(fā)現(xiàn)數(shù)據(jù)被修改（采用時(shí)間戳、版本號）浓镜，則回滾溃列。也叫做樂觀鎖，即樂觀并發(fā)控制(OOC)膛薛。事務(wù)的過程是：1讀取听隐，并寫時(shí)間戳；2準(zhǔn)備寫入哄啄，版本校驗(yàn)雅任；3校驗(yàn)通過則寫入，校驗(yàn)不通過咨跌，則回滾沪么。?
lock-free必定是obstruction-free的。
CAS（比較與交換禽车，Compare and swap） 是一種有名的無鎖算法。CAS, CPU指令刊殉，在大多數(shù)處理器架構(gòu)殉摔，包括IA32、Space中采用的都是CAS指令冗澈，CAS的語義是“我認(rèn)為V的值應(yīng)該為A钦勘，如果是，那么將V的值更新為B亚亲，否則不修改并告訴V的值實(shí)際為多少”彻采，CAS是項(xiàng) 樂觀鎖 技術(shù)，當(dāng)多個(gè)線程嘗試使用CAS同時(shí)更新同一個(gè)變量時(shí)捌归，只有其中一個(gè)線程能更新變量的值肛响，而其它線程都失敗，失敗的線程并不會被掛起惜索，而是被告知這次競爭中失敗特笋，并可以再次嘗試。CAS有3個(gè)操作數(shù)巾兆，內(nèi)存值V猎物，舊的預(yù)期值A(chǔ)虎囚，要修改的新值B。當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時(shí)蔫磨，將內(nèi)存值V修改為B淘讥，否則什么都不做。?
java.util.concurrent.atomic中的AtomicXXX堤如，都使用了這些底層的JVM支持為數(shù)字類型的引用類型提供一種高效的CAS操作蒲列，而在java.util.concurrent中的大多數(shù)類在實(shí)現(xiàn)時(shí)都直接或間接的使用了這些原子變量類，這些原子變量都調(diào)用了 sun.misc.Unsafe 類庫里面的 CAS算法搀罢，用CPU指令來實(shí)現(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進(jìn)行操作變成2，cas(val,1,2)洛退。?
thread1先讀取val=1瓣俯；thread1被搶占（preempted），讓thread2運(yùn)行兵怯。?
thread2 修改val=3彩匕，又修改回1。?
thread1繼續(xù)執(zhí)行媒区，發(fā)現(xiàn)期望值與“原值”（其實(shí)被修改過了）相同驼仪，完成CAS操作。?
使用CAS會造成ABA問題袜漩，特別是在使用指針操作一些并發(fā)數(shù)據(jù)結(jié)構(gòu)時(shí)绪爸。?
解決方案?
ABA?：添加額外的標(biāo)記用來指示是否被修改。?
從Java1.5開始JDK的atomic包里提供了一個(gè)類AtomicStampedReference來解決ABA問題宙攻。這個(gè)類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用奠货，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等座掘，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值递惋。
