隨著多核CPU成為主流，並行程序設計亦成為研究領域的熱門。
要想利用多核/多路CPU帶來的強大功能，通常使用多線程來開發應用程序。但是要想擁有良好的硬件 利用率，僅僅簡單的在多個線程間分割工作是不夠的。還必須確保線程大部分時間在工作，而不是在等待 工作或等待鎖定共享數據結構。
在不止一個線程訪問共享數據時，所有線程都必須使用同步。如果線程間不進行協調，則沒有任務可 以真正並行，更糟糕的是這會給程序帶來毀滅性的錯誤。
現在讓我們來看一下在.NET和D語言中的標准同步手段-鎖定。.NET下我們使用lock關鍵字，而D語言則 使用synchronized關鍵字。它們在Windows下均使用臨界區(Critical Section)來實現，而在Linux下則使 用互斥鎖(Mutex)來實現。不論其如何實現，它們均強制實行互斥，來確保持有鎖的線程對共享數據的獨 占訪問權，以及當其他線程持有鎖時，可以看到其對共享數據的修改。
簡而言之，在基於鎖的多線程編程中，任何針對共享數據，且有可能導致競爭條件的操作，我們都得 將其改為原子操作(即連續的，不允許被打斷的步驟；上面的lock/synchronized關鍵字就是我們實現原子 操作的手段)。只要我們的線程持有鎖，就不必擔心其他線程會進來搗亂。
這聽起來似乎很不錯，我們只要加鎖/解鎖就可以為所欲為了。然而正是這種為所欲為的事實帶來了問 題。比如我們的線程持有鎖之後，進行了耗時很久的I/O操作。這也就意味著任何其他想持有該鎖的線程 只能被晾在一邊干等了，這時其他線程都處於饑餓狀態。假如有更高優先級的線程，此時也只能干巴巴等 待了。這就是所謂的優先級倒置。更糟糕的是，我們的線程現在試圖霸占另一個鎖，而該鎖卻被另外的線 程持有。這個線程這時反過來想要霸占我們線程持有的鎖。對於這種情況，我們人類只要互相打個哈哈， 咱倆互換鎖就OK了。但是CPU卻是死腦筋一個，你不給我，我也不給你。結果兩個線程都在干等對方，動 彈不得。這就是死鎖。
此外，如果成千上萬個線程在同時競爭鎖，我們的CPU就不堪忍受了。因為同步的競爭非常昂貴，所以 這會大大降低CPU的吞吐量。
當然，我們也可以使用volatile變量來以比同步更低的成本存儲共享數據，但是volatile變量相當有 局限性。詳情請參考談談volatile變量。
線程安全計數器經常被拿來做關於多線程並發的案例。我們接下來就來實現一個線程安全的計數器。 在談談volatile變量中，我們實現了一個這樣的計數器，但是其使用場景是在多線程讀而少線程寫的情況 下，下面實現的則是一個一般的線程安全技術器。
.NET代碼:
public class ThreadSafeCounter
{
private int value;
private object obj = new Object();
public int GetValue()
{
lock (obj)
{
return value;
}
}
public int Increment()
{
lock (obj)
{
return ++value;
}
}
public int Decrement()
{
lock (obj)
{
return --value;
}
}
}
D代碼：
public class ThreadSafeCounter
{
private int value;
public synchronized int GetValue()
{
return value;
}
public synchronized int Increment()
{
return ++value;
}
public synchronized int Decrement()
{
return --value;
}
}
為了安全實現計數器，我們在每個方法上都加上了lock/synchronized關鍵字來確保其他線程不能打斷 。否則，如果兩個線程試圖同時增加計數，交叉的操作將導致計數只增加了1，而不是2。
現在我們開始真正進入令人激動的Lock-Free世界。
在Lock-Free世界裡，最簡單也最普遍的一個通用原語是CAS(Compare and Swap)操作。支持並發的現 代的處理器都提供了這個原語的硬件實現。比如x86架構下其對應的匯編指令是lock cmpxchg，如果想要 64Bit的交換，則應使用lock cmpxchg8b。在.NET中我們可以使用Interlocked.CompareExchange函數，而 在D中則可以使用tango.core.Atomic(T).storeIf函數，或者system.threading.Atomic.compareAndSwap (T)模板函數。你可以在http://code.google.com/p/d- phoenix/source/browse/trunk/source/system/threading/Atomic.d浏覽代碼。該代碼基於Tango代碼， 我將其修改成.NET風格，並添加了atomicAdd模板函數。
CAS原語負責比較某個內存地址處的內容與一個期望值，如果比較成功則將該內存地址處的內容替換為 一個新值。這整個操作是原子的。下面的代碼模擬了CAS操作的行為(而不是性能特征)。CAS的價值在於它 可以在硬件中實現，且是極輕量級的。
.NET代碼:
public T CAS<T>(ref T value, T newValue, T equalTo) where T : class
{
lock (obj)
{
if (value == equalTo)
value = newValue;
return value;
}
}
public int CAS(ref int value, int newValue, int equalTo)
{
lock (obj)
{
if (value == equalTo)
value = newValue;
return value;
}
}
public long CAS(ref long value, long newValue, long equalTo)
{
lock (obj)
{
if (value == equalTo)
value = newValue;
return value;
}
}
D代碼:
public synchronized bool CAS(T)(ref T value, T newValue, T equalTo)
{
static assert( IsIntegerType!(T) || IsPointerType!(T) );
if (value == equalTo)
value = newValue;
return value;
}
Update: 2008-04-16 18:29
關於CAS原語有個相當出名的ABA問題：我們把CAS的value值設為A，在更改value時，CAS詢問value的 值是否仍為A，如果為A，我們就把newValue的值賦給value。但是假如我們把value的值從A改為B，緊接著 又從B改為A。CAS無法知道其中的變化，仍然認為比對成功。這時就可能帶來無法預知的結果。這類問題 就是ABA問題。注意，此處計數器的實現不受其困擾。通常，我們通過將標記或版本編號與要進行 CAS 操 作的每個值相關聯，並原子地更新值和標記，來處理這類問題。比如Java中的AtomicStampedReference類 就支持這種方法。我們應當知道能夠交換的位越長，ABA發生的幾率越低。
基於CAS的並發算法，我們稱為Lock-Free算法，因為線程不必再等待鎖定。當然，也有很多其他擴展 的硬件原語可用於並發算法，比如DCAS，但是目前只有CAS是被廣泛實現的。其他如FetchAndAdd，原子隊 列等則被證明不足以良好的同步兩個以上的線程。無論 CAS 操作成功還是失敗，在任何一種情況中，它 都在可預知的時間內完成。如果 CAS 失敗，調用者可以重試 CAS 操作或采取其他適合的操作。下面我們 使用CAS原語來實現線程安全的計數器。
public class CASCounter
{
private int value;
public int GetValue()
{
return value;
}
public int Increment()
{
int oldValue;
do
{
oldValue = value;
}
while (Interlocked.CompareExchange(ref value, oldValue+1, oldValue) != oldValue);
return oldValue + 1;
}
//
}
D代碼:
public class CASCounter
{
private int value;
public int getValue()
{
volatile return value;
}
public int increment()
{
int oldValue;
do
{
oldValue = value;
}
while (!Atomic.CompareAndSwap(value, oldValue+1, oldValue));
return oldValue + 1;
}
//
}
如果仔細比對兩段代碼，可以發現D的實現代碼使用volatile關鍵字，而.NET則沒有用。這是因為.NET 的內存模型已經明確提出原子操作會維持高速緩存一致性，而D的文檔規范裡則只字未提內存模型，所以 加上volatile來確保高速緩存一致性。當然我們也可以使用Interlocked.Increment函數來計數，此處只 為了說明CAS的思想。
在Lock-Free的世界裡，幾乎任何操作都無法原子的完成。只有極少的操作可以原子完成，這一限制使 得編程難度大大增加。但是Lock-Free的程序能夠確保執行它的所有線程中至少有一個能夠繼續往下執行 。這便意味著有些線程可能會被任意地延遲，然而在每一步都至少有一個線程能夠往下執行。因此這個系 統作為一個整體總是在“前進”的，盡管有些線程的進度可能不如其它線程來得快。而基於鎖的程序則無 法提供上述任何保證。
關於Lock-Free的優缺點可以參考關於無鎖編程。除了文章中所提到的內容外，Lock-Free編程還有三 大優點:
線程中止免疫:殺掉系統中的任何線程都不會導致其它線程被延遲。
優先級倒置免疫：所謂“優先級倒置”就是指一個低優先級線程持有了一個高優先級線程所需要的互 斥體。這種微妙的沖突必須由OS內核來解決。而等待無關和鎖無關算法則對此免疫。
死鎖免疫:因為沒有使用鎖，所以也就不存在死鎖的可能。但是樂觀的並發，可能會導致活鎖。
雖然Lock-Free編程非常困難，但是它通常可以帶來比基於鎖編程更高的吞吐量。所以Lock-Free編程 是大有前途的技術。它在線程中止、優先級倒置以及信號安全等方面都有著良好的表現。
