?? 出自[原子操作(CAS)](http://286.iteye.com/blog/2295165) 眾所周知鎖有兩種：樂觀鎖與悲觀鎖。獨占鎖是一種悲觀鎖，而 synchronized 就是一種獨占鎖，synchronized?會導致其它所有未持有鎖的線程阻塞，而等待持有鎖的線程釋放鎖。所謂樂觀鎖就是，每次不加鎖而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止。而樂觀鎖用到的機制就是CAS。 ? ? ? ??**1.CAS（Compare And Set）** ? ? ? ? Compare And Set（或Compare And Swap），CAS是解決多線程并行情況下使用鎖造成性能損耗的一種機制，CAS操作包含三個操作數——**內存位置**（V）、**預期原值**（A）、**新值**(B)。如果內存位置的值與預期原值相匹配，那么處理器會自動將該位置值更新為新值。否則，處理器不做任何操作。無論哪種情況，它都會在CAS指令之前返回該位置的值。CAS有效地說明了“我認為位置V應該包含值A；如果包含該值，則將B放到這個位置；否則，不要更改該位置，只告訴我這個位置現在的值即可。 ? ? ? ? 在java中可以通過鎖和循環CAS的方式來實現原子操作。Java中 java.util.concurrent.atomic包相關類就是 CAS的實現，atomic包里包括以下類：? | | | | --- | --- | | | | | **AtomicBoolean** | 可以用原子方式更新的?`boolean`?值。 | | **AtomicInteger** | 可以用原子方式更新的?`int`?值。 | | **AtomicIntegerArray** | 可以用原子方式更新其元素的?`int`?數組。 | | **AtomicIntegerFieldUpdater** | 基于反射的實用工具，可以對指定類的指定?`volatile int`?字段進行原子更新。 | | **AtomicLong** | 可以用原子方式更新的?`long`?值。 | | **AtomicLongArray** | 可以用原子方式更新其元素的?`long`?數組。 | | **AtomicLongFieldUpdater** | 基于反射的實用工具，可以對指定類的指定?`volatile long`?字段進行原子更新。 | | **AtomicMarkableReference** | `AtomicMarkableReference`?維護帶有標記位的對象引用，可以原子方式對其進行更新。 | | **AtomicReference** | 可以用原子方式更新的對象引用。 | | **AtomicReferenceArray** | 可以用原子方式更新其元素的對象引用數組。 | | **AtomicReferenceFieldUpdater** | 基于反射的實用工具，可以對指定類的指定?`volatile`?字段進行原子更新。 | | **AtomicStampedReference** | `AtomicStampedReference`?維護帶有整數“標志”的對象引用，可以用原子方式對其進行更新。 | ? ? ? ? atomic包中的類可將?volatile?值、字段和數組元素的概念擴展到那些也提供原子條件更新操作的類，其形式如下：?? Java代碼?? 1. boolean?compareAndSet(expectedValue,?updateValue);?? ? ? ? ? 如果此方法（在不同的類間參數類型也不同）當前保持 expectedValue，則以原子方式將變量設置為 updateValue，并在成功時報告 true。此包中的類還包含獲取并無條件設置值的方法，以及以下描述的較弱條件的原子更新操作 weakCompareAndSet。? ? ? ? ? 這些方法的規范使實現能夠使用當代處理器上提供的高效機器級別原子指令。但是在某些平臺上，該支持可能需要某種形式的內部鎖。因而，該方法不能嚴格保證不被阻塞 - 執行操作之前可能暫時阻塞線程。 **? ? ? ? 2.AtomicInteger** ? ? ? ? AtomicInteger可以用原子方式更新的 int 值。AtomicInteger 可用在應用程序中（如以原子方式增加的計數器），并且不能用于替換 Integer。但是，此類確實擴展了 Number，允許那些處理基于數字類的工具和實用工具進行統一訪問。?我們拿?AtomicInteger為例來學習下 CAS操作是如何實現的。 ? ? ? ??通常情況下，在 Java中，i++等類似操作并不是線程安全的，因為 i++可分為三個獨立的操作：獲取變量當前值，為該值+1，然后寫回新的值。在沒有額外資源可以利用的情況下，只能使用加鎖才能保證讀-改-寫這三個操作時“原子性”的。但是利用加鎖的方式來實現該功能的話，代碼將非常復雜及難以維護，如： Java代碼?? 1. synchronized?(lock)?{?? 2. ????i++;?? 3. }?? ? ? ? ? 相關類中還需要增加 Object lock等額外標志，這樣就帶來了很多麻煩，增加了很多業務無關代碼，給開發與維護帶來了不便。 ? ? ? ? 然而利用?atomic包中相關類型就可以很簡單實現此操作，以下是一個計數程序實例： Java代碼?? 1. import?java.util.ArrayList;?? 2. import?java.util.List;?? 3. import?java.util.concurrent.atomic.AtomicInteger;?? 4. ?? 5. public?class?Counter?{?? 6. ????private?AtomicInteger?ai?=?new?AtomicInteger();?? 7. ????private?int?i?=?0;?? 8. ?? 9. ????public?static?void?main(String[]?args)?{?? 10. ????????final?Counter?cas?=?new?Counter();?? 11. ????????List?ts?=?new?ArrayList();?? 12. ????????//?添加100個線程?? 13. ????????for?(int?j?=?0;?j?100;?j++)?{?? 14. ????????????ts.add(new?Thread(new?Runnable()?{?? 15. ????????????????public?void?run()?{?? 16. ????????????????????//?執行100次計算，預期結果應該是10000?? 17. ????????????????????for?(int?i?=?0;?i?100;?i++)?{?? 18. ????????????????????????cas.count();?? 19. ????????????????????????cas.safeCount();?? 20. ????????????????????}?? 21. ????????????????}?? 22. ????????????}));?? 23. ????????}?? 24. ????????//開始執行?? 25. ????????for?(Thread?t?:?ts)?{?? 26. ????????????t.start();?? 27. ????????}?? 28. ????????//?等待所有線程執行完成?? 29. ????????for?(Thread?t?:?ts)?{?? 30. ????????????try?{?? 31. ????????????????t.join();?? 32. ????????????}?catch?(InterruptedException?e)?{?? 33. ????????????????e.printStackTrace();?? 34. ????????????}?? 35. ????????}?? 36. ????????System.out.println("非線程安全計數結果："+cas.i);?? 37. ????????System.out.println("線程安全計數結果："+cas.ai.get());?? 38. ????}?? 39. ?? 40. ????/**?使用CAS實現線程安全計數器?*/?? 41. ????private?void?safeCount()?{?? 42. ????????for?(;;)?{?? 43. ????????????int?i?=?ai.get();?? 44. ????????????//?如果當前值?==?預期值，則以原子方式將該值設置為給定的更新值?? 45. ????????????boolean?suc?=?ai.compareAndSet(i,?++i);?? 46. ????????????if?(suc)?{?? 47. ????????????????break;?? 48. ????????????}?? 49. ????????}?? 50. ????}?? 51. ?? 52. ????/**?非線程安全計數器?*/?? 53. ????private?void?count()?{?? 54. ????????i++;?? 55. ????}?? 56. }?? 57. //結果：?? 58. 非線程安全計數結果：9867?? 59. 線程安全計數結果：10000?? ? ? ? ? 其中非線程安全計數器所計算的結果每次都不相同且不正確，而線程安全計數器計算的結果每次都是正確的。可以看到代碼中并不含有任何有關?synchronized 關鍵字的地方，所以 safeCount可以當做一個普通的方法來使用。 ? ? ? ? 示例中使用了?compareAndSet方法，那么我們就從此方法開始深入了解?AtomicInteger的用法。 ? ? ? ??**compareAndSet方法** ? ? ? ? 如果當前值 == 預期值，則以原子方式將該值設置為給定的更新值。 Java代碼?? 1. public?final?boolean?compareAndSet(int?expect,?int?update)?{?? 2. ????return?unsafe.compareAndSwapInt(this,?valueOffset,?expect,?update);?? 3. }?? ? ? ? ? compareAndSet 調用的是 unsafe.compareAndSwapInt方法。 ? ? ? ? Unsafe類是用于執行低級別、不安全操作的方法集合。盡管這個類和所有的方法都是公開的（public），但是這個類的使用仍然受限，你無法在自己的 java程序中直接使用該類，因為只有授信的代碼才能獲得該類的實例。該類是用來執行較低級別的操作的，比如獲取某個屬性在內存中的位置，不過一般人很少會有這樣的需求。個人不建議直接使用 Unsafe，它遠比原生的 Java開發所需要的測試要多。基于這個原因建議還是使用經過測試的庫。如果你只是想自己用 Unsafe，建議你最好在一個獨立的類庫中進行全面的測試。這限制了Unsafe在你的應用程序中的使用方式，但會給你一個更安全的Unsafe。 ? ? ? ? 其中絕大部分方法都調用的是?compareAndSet方法，比如 getAndIncrement： Java代碼?? 1. public?final?int?getAndIncrement()?{?? 2. ????for?(;;)?{?? 3. ????????int?current?=?get();?? 4. ????????int?next?=?current?+?1;?? 5. ????????if?(compareAndSet(current,?next))?? 6. ????????????return?current;?? 7. ????}?? 8. }?? ? ? ? ? 其他相關方法都類似，這里就不細說了。 ? ? ? ? CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題：ABA問題、循環時間長開銷大、只能保證一個共享變量的原子操作。 ? ? ? ??**ABA問題**：因為CAS需要在操作值的時候檢查下值有沒有發生變化，如果沒有發生變化則更新，但是如果一個值原來是A，變成了B，又變成了A，那么使用CAS進行檢查時會發現它的值沒有發生變化，但是實際上卻變化了。ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加一，那么A－B－A 就會變成1A-2B－3A。 從Java1.5開始JDK的 atomic包里提供了一個類AtomicStampedReference 來解決ABA問題。這個類的 compareAndSet方法作用是首先檢查當前引用是否等于預期引用，并且當前標志是否等于預期標志，如果全部相等，則以原子方式將該引用和該標志的值設置為給定的更新值。 Java代碼?? 1. compareAndSet(V?expectedReference,?V?newReference,?int?expectedStamp,?int?newStamp)??? ? ? ? ? 如果當前引用 == 預期引用，并且當前標志等于預期標志，則以原子方式將該引用和該標志的值設置為給定的更新值。其中參數代表：expectedReference - 該引用的預期值；newReference - 該引用的新值； expectedStamp - 該標志的預期值；newStamp - 該標志的新值。 ? ? ? ??**循環時間長開銷大**：自旋CAS如果長時間不成功，會給CPU帶來非常大的執行開銷。如果JVM能支持處理器提供的pause指令那么效率會有一定的提升，pause指令有兩個作用，第一它可以延遲流水線執行指令（de-pipeline）,使CPU不會消耗過多的執行資源，延遲的時間取決于具體實現的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因內存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執行效率。　 ? ? ? ??**只能保證一個共享變量的原子操作**：當對一個共享變量執行操作時，我們可以使用循環CAS的方式來保證原子操作，但是對多個共享變量操作時，循環CAS就無法保證操作的原子性，這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如有兩個共享變量i＝2,j=a，合并一下ij=2a，然后用CAS來操作ij。從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性，你可以把多個變量放在一個對象里來進行CAS操作。 ? ? ? ? 原子類不是 java.lang.Integer 和相關類的通用替換方法。它們不 定義諸如 hashCode 和 compareTo 之類的方法。（因為原子變量是可變的，所以對于哈希表鍵來說，它們不是好的選擇。）另外，僅為那些通常在預期應用程序中使用的類型提供類。例如，沒有表示 byte 的原子類。這種情況不常見，如果要這樣做，可以使用 AtomicInteger 來保持 byte 值，并進行適當的強制轉換。也可以使用 Float.floatToIntBits 和 Float.intBitstoFloat 轉換來保持 float 值，使用 Double.doubleToLongBits 和 Double.longBitsToDouble 轉換來保持 double 值。?? ? ? ? ? 類 AtomicBoolean、AtomicInteger、AtomicLong 和 AtomicReference 的實例各自提供對相應類型單個變量的訪問和更新。每個類也為該類型提供適當的實用工具方法。例如，類 AtomicLong 和 AtomicInteger 提供了原子增量方法。一個應用程序將按以下方式生成序列號：? Java代碼?? 1. class?Sequencer?{?? 2. ??private?final?AtomicLong?sequenceNumber?? 3. ????=?new?AtomicLong(0);?? 4. ??public?long?next()?{?? 5. ????return?sequenceNumber.getAndIncrement();?? 6. ??}?? 7. }?? ? ? ? ? 原子訪問和更新的內存效果一般遵循以下可變規則： * get 具有讀取 volatile 變量的內存效果。? * set 具有寫入（分配）volatile 變量的內存效果。? * 除了允許使用后續（但不是以前的）內存操作，其自身不施加帶有普通的非 volatile 寫入的重新排序約束，lazySet 具有寫入（分配）volatile 變量的內存效果。在其他使用上下文中，當為 null 時（為了垃圾回收），lazySet 可以應用不會再次訪問的引用。? * weakCompareAndSet 以原子方式讀取和有條件地寫入變量但不 創建任何 happen-before 排序，因此不提供與除 weakCompareAndSet 目標外任何變量以前或后續讀取或寫入操作有關的任何保證。? * compareAndSet 和所有其他的讀取和更新操作（如 getAndIncrement）都有讀取和寫入 volatile 變量的內存效果。? ? ? ? ? 除了包含表示單個值的類之外，atomic包還包含 Updater 類，Updater?類可用于獲取任意選定類的任意選定 volatile 字段上的 compareAndSet 操作。AtomicReferenceFieldUpdater、AtomicIntegerFieldUpdater 和 AtomicLongFieldUpdater 是基于反射的實用工具，可以提供對關聯字段類型的訪問。它們主要用于原子數據結構中，該結構中同一節點（例如，樹節點的鏈接）的幾個 volatile 字段都獨立受原子更新控制。這些類在如何以及何時使用原子更新方面具有更大的靈活性，但相應的弊端是基于映射的設置較為拙笨、使用不太方便，而且在保證方面也較差。? ? ? ? ? AtomicIntegerArray、AtomicLongArray 和 AtomicReferenceArray 類進一步擴展了原子操作，對這些類型的數組提供了支持。這些類在為其數組元素提供 volatile 訪問語義方面也引人注目，這對于普通數組來說是不受支持的。? ? ? ? ? 原子類也支持 weakCompareAndSet 方法，該方法具有受限制的適用性。在某些平臺上，弱版本在正常情況下可能比 compareAndSet 更有效，但不同的是 weakCompareAndSet 方法的任何給定調用可能意外 返回 false（即沒有明確的原因）。返回 false 僅意味著可以在需要時重新嘗試操作，具體取決于重復執行調用的保證，當該變量保持 expectedValue 并且沒有其他線程也在嘗試設置該變量時，最終將獲得成功。（例如，這樣的虛假失敗可能是由于內存爭用的結果，該爭用與期望值和當前值是否相等無關）。 此外，weakCompareAndSet 不提供通常需要同步控制的排序保證。但是，在這樣的更新與程序的其他 happen-before 排序不相關時，該方法可用于更新計數器和統計數據。當一個線程看到對 weakCompareAndSet 導致的原子變量的更新時，它不一定能看到在 weakCompareAndSet 之前發生的對任何其他 變量的更新。例如，在更新性能統計數據時，這也許可以接受，但其他情況幾乎不可以。? ? ? ? ? AtomicMarkableReference 類將單個布爾值與引用關聯起來。例如，可以在數據結構內部使用此位，這意味著引用的對象在邏輯上已被刪除。AtomicStampedReference 類將整數值與引用關聯起來。例如，這可用于表示與更新系列對應的版本號。? ? ? ? ? 設計原子類主要用作各種構造塊，用于實現非阻塞數據結構和相關的基礎結構類。compareAndSet 方法不是鎖的常規替換方法。僅當對象的重要更新限定于單個 變量時才應用它。