友情提示：對 Lock-free 算法沒(méi)概念的朋友，請先看下面的參考。

算法描述

Lock-free 算法的基礎是 CAS (Compareand-Swap) 原子操作。當某個(gè)地址的原始值等于某個(gè)比較值時(shí)，把值改成新值，無(wú)論有否修改，返回這個(gè)地址的原始值。目前的cpu 支持最多64位的CAS。并且指針 p 必須對齊。

 注：原子操作指一個(gè)cpu時(shí)鐘周期內就可以完成的操作，不會(huì )被其他線(xiàn)程干擾。

一般的 CAS 使用方式是：

假設有指針 p, 它指向一個(gè) 32 位或者64位數，

1. 復制p 的內容（*p）到比較量 cmp （原子操作）

2. 基于這個(gè)比較量計算一個(gè)新值 xchg (非原子操作）

3. 調用 CAS 比較當前 *p 和 cmp, 如果相等把 *p 替換成 xchg （原子操作）

4. 如果成功退出，否則回到第一步重新進(jìn)行

第3步的 CAS 操作保證了寫(xiě)入的同時(shí) p 沒(méi)有被其他線(xiàn)程更改。如果*p已經(jīng)被其他線(xiàn)程更改，那么第2步計算新值所使用的值(cmp)已經(jīng)過(guò)期了，因此這個(gè)整個(gè)過(guò)程失敗，重新來(lái)過(guò)。多線(xiàn)程環(huán)境下，由于 3 是一個(gè)原子操作，那么起碼有一個(gè)線(xiàn)程（最快執行到3）的CAS 操作可以成功，這樣整體上看，就保證了所有的線(xiàn)程上在“前進(jìn)”，而不需要使用效率低下的鎖來(lái)協(xié)調線(xiàn)程，更不會(huì )導致死鎖之類(lèi)的麻煩。

ABA 問(wèn)題

當 A 線(xiàn)程執行2的時(shí)候，被B 線(xiàn)程更改了 *p為x, 而 C 線(xiàn)程又把它改回了原始值，這時(shí)回到A 線(xiàn)程，A線(xiàn)程無(wú)法監測到原始值已經(jīng)被更改過(guò)了，CAS 操作會(huì )成功（實(shí)際上應該失?。?。ABA 大部分情況下會(huì )造成一些問(wèn)題，因為 p 的內容一般不可能是獨立的，其他內容已經(jīng)更改，而A線(xiàn)程認為它沒(méi)有更改就會(huì )帶來(lái)不可預知的結果。

ABA 問(wèn)題的解決一般是擴展 *p 的位數（比如從32擴展到64），使用多余的位來(lái)保存一個(gè)版本號，每次更改都修改版本號，從而保證這個(gè)線(xiàn)程能正確的監測到值的更改。

擴展

一個(gè) 32 位數無(wú)法攜帶太多信息，但是32位的C++ 環(huán)境中，這樣的一個(gè)數已經(jīng)可以代表很多東西了，比如——指針。

我們剛才保證了我們的線(xiàn)程可以安全讀寫(xiě)一個(gè) 32 位的數，如果這個(gè)數是一個(gè)指針，指向了我們真實(shí)使用的對象。那么我們就可以創(chuàng )建了一個(gè)無(wú)鎖而線(xiàn)程安全的對象?；舅枷刖褪敲看涡薷膶ο笄?，復制整個(gè)對象，然后更改完成以后用上面的算法使用新對象來(lái)替換舊對象（更改p的指向），當然，這個(gè)對象不能太大，否則lock-free的速度優(yōu)勢，就被復制操作消耗殆盡。

這里有個(gè)很大的問(wèn)題，在于老的對象何時(shí)銷(xiāo)毀。P 指向新的對象了，以后的操作都將會(huì )訪(fǎng)問(wèn)新的對象，但是老的對象還可能正被其他線(xiàn)程訪(fǎng)問(wèn)中。遺憾的是，我們還沒(méi)有垃圾收集器，所以需要設計一個(gè)引用計數之類(lèi)的策略來(lái)保護這個(gè)對象。

待續……

 參考：

鎖無(wú)關(guān)的（Lock-Free）數據結構

多核編程中的任務(wù)隨機競爭模式的概率分析