lock-free編程實在讓人又愛又恨。博主以前曾經寫過幾篇關於 lock-free 編程的文章。比如關於無鎖編程、並發數據結構:迷人的原子。如果想更加深入的了解和實踐 lock-free 編程，可以參考CLR 2.0 Memory Model、並發數據結構:Stack。這篇文章並不打算繼續闡述如何使用 lock-free 技術，而是談一下它的負面影響。從而讓大家對 lock-free 有個更加全面的認識。
說到 lock-free 編程，現實中經常使用 CAS 原語。CAS 是英文 Compare and Swap 的簡寫。在 Windows 和 .NET 平台，由於歷史原因，它被寫做 Interlocked API。原子操作在 x86 架構 CPU 對應的匯編指令有 XCHG、CMPXCHG、INC 等，當然還得加上 LOCK 作為前綴(更多信息請看 並發數據結構:迷人的原子)。
CAS 原語在輕度和中度爭用情況下確實可以大幅度提高程序性能。但凡事有利必有弊，CAS 原語極度扼殺了程序的可伸縮性(其他缺點請看關於無鎖編程)。各位看官可能覺得這種觀點有點偏激，但事實如此。請容博主細細道來：
CAS 的原子性完全取決於硬件實現。大多數 Intel 和 AMD 的 CPU 采用了一種叫做 MOSEI 緩存一致性協議來管理緩存。這種架構下，處理器緩存內 CAS 操作相對成本低廉。但一旦資源爭用，就會引起緩存失效和總線占用。緩存越失效，總線越被占用，完成 CAS 操作也越被延遲。緩存爭用是程序可伸縮性殺手。當然對於非 CAS 內存操作來說也是如此，但 CAS 情況更加槽糕。
CAS 操作要比普通內存操作花費更多 CPU 周期。這歸功於緩存分級的額外負擔、刷新寫緩沖區與穿越內存柵欄限制和需求以及編譯器對 CAS 操作優化的能力。
CAS 經常被用在優化並行操作上。這意味著 CAS 操作失敗將導致重新嘗試某些指令(典型的回滾操作)。即便沒有任何爭用，它也會做一些無用功。不論成功或失敗都會增加爭用的風險。
大多數 CAS 操作發生在鎖進入和退出時。盡管鎖可由單一 CAS 操作構建，但 .NET CLR Monitor 類卻使用了兩個(一個在 Enter 方法，另一個在 Exit 方法)。lock-free 算法也經常使用 CAS 原語來代替使用鎖機制。但是由於內存重組，這樣的算法也常常需要顯式的柵欄，即便使用了 CAS 指令。鎖機制非常邪惡，但大多數合格的開發人員都知道讓鎖持有盡量少的時間。因此，雖然鎖機制讓人非常討厭，且影響性能。但相對於大量，頻繁的 CAS 操作而言，它卻並不影響程序的可伸縮性。
舉個很簡單的例子，增加計數 100,000,000 次。要做到這樣，有幾種方式。如果僅運行在單核單處理器上，我們可以使用普通的內存操作：
static volatile int counter = 0;
static void BaselineCounter()
{
for (int i = 0; i < Count; i++)
{
counter++;
}
}
很明顯，上述代碼示例不是線程安全的，但給計數器提供了一個很好的時間基准。下面我們使用 LOCK INC 來作為線程安全的第一種方式：
static volatile int counter = 0;
static void LockIncCounter()
{
for (int i = 0; i < Count; i++)
{
Interlocked.Increment(ref counter);
}
}
現在代碼示例線程安全了。我們還可以采取另外一種方式來保證線程安全。如果需要執行一些驗證(比如內存溢出保護)，我們通常會使用這種方式。就是使用 CMPXCHG(即 CAS)：
static volatile int counter = 0;
static void CASCounter()
{
for (int i = 0; i < Count; i++)
{
int oldValue;
do
{
oldValue = counter;
}
while (Interlocked.CompareExchange(ref counter, oldValue + 1, oldValue) != oldValue);
}
}
現在問一個有意思的問題：當緩存爭用時，哪一個方法更慢？結果可能會讓你大吃一驚哦。
在 Intel 4 核處理器下測試結果如下：
圖中，當 CPU 使用 2 個核時，BaselineCounter 方法是單核單路情況的 2.11 倍。其他情況類似。通過結果比對，我們可以得知：更多的並發性導致結果更加槽糕。這很大部分原因由內存爭用所致。
當 CAS 操作失敗，通過旋轉等待可以改善 CASCounter 方法的在多核處理器上的性能(具體技巧可以參考夏天是個好季節兄的自己動手實現一個輕量級的信號量（一）、（二）)。這可以大大減少活鎖和關聯內聯阻礙鎖耗費的時間。
當然，這個示例非常極端。它頻繁反復修改同一個內存地址。通過期間插入特定的函數調用，延遲訪問共享內存可以極大緩解壓力。
比如插入 2 個函數調用，我們得到了如下數據：
插入 64 個函數調用之後，數據又變成了如下所示：
這個時候，我們看到多核所花費的時間少於單核了。這就是我們使用並行所帶來的加速。看到這裡，我們可能會想，既然從 2 到 64 個函數調用使得結果越來越好，那麼超過 64 個函數調用豈不是會變得更好？實際上，在插入 128 個函數調用之後，加速已經達到極限。結果如下所示：
如何計算加速比，請參考並行思維 [II]。
天下沒有免費的午餐，CAS 也不例外。我們應當慎之又慎的將 lock-free CAS 代碼放到我們的代碼中，且必須清楚的知道線程執行它們的頻繁程度。我們可以用下面這句話來作為總結：共享是魔鬼。它從根本上限制應用程序可伸縮性，最好盡量避免。共享內存需要並發控制，而並發控制需要 CAS。CAS 又非常昂貴，因此共享內存也非常昂貴。有很多人提出 lock-free 技術，事務內存，讀寫鎖等可以改善程序可伸縮性。但很遺憾，這種情況很少出現。CAS 往往比正確實現鎖機制的解決方案更加糟糕。很大原因要歸結於共享內存、樂觀失敗嘗試、緩存失效等。
Update 於 2009 年 4 月 8 日 21 : 10
overred 兄在 review 這篇文章的時候，提了一個很好的問題：在使用 Interlocked API 的時候，共享變量不用 volatile 修飾。
為了更方便說明這個問題，俺寫個簡單點的代碼示例，如下所示：
using System;
namespace Lucifer.CSharp.Sample
{
class Program
{
static volatile int x;
static void Main(string[] args)
{
Foo(ref x);
}
static void Foo(ref int y)
{
while (y == 0) ;
}
}
}
當我們在 Visual Studio 中編譯這段代碼時，IDE 會給出編譯警告，如下所示：
通常來說，我們對於這樣的編譯警告應該給予足夠重視。比如在上面的例子中，JIT 編譯器會認為 y 一直未變，從而引起死循環。在 IA64 平台上，這會被認為普通內存訪問代替了特殊的 load-acquire 訪問，這就可能導致 CPU 指令重組方面的一些 Bug。但是有一種情況例外，就是使用 Interlocked API 和 Thread.VolatileXXX 方法以及鎖。因為這些 API 內部都會顯式要求內存柵欄和硬件原子指令，而不管外部共享變量是否采用 volatile 修飾。因此，文中采用的測試方法還是很安全嘀。
如果你覺得這個編譯警告很煩人，可以使用 #pragma 指令禁掉這種警告，如下所示：
static volatile int x;
static void Foo()
{
#pragma warning disable 0420
Interlocked.Exchange(ref x, 1);
#pragma warning restore 0420
}
當然，也可以完全不用 volatile 修飾符。CLR 內存模型保證了這一點。
如何正確使用 volatile ，請參考並發數據結構:談談volatile變量。
