ACE中的Double Checked Locking 模式
(作者:Douglas C. Schmidt ,
by huihoo.org CORBA課題 Thzhang 譯 , Allen整理,制作)
意圖
無論什么時候當臨界區中的代碼僅僅需要加鎖一次，同時當其獲取鎖的時候必須是線程安全的，可以用Double Checked Locking 模式來減少競爭和加鎖載荷。
動機
1、標準的單例。開發正確的有效的并發應用是困難的。程序員必須學習新的技術（并發控制和防止死鎖的算法）和機制（如多線程和同步API）。此外，許多熟悉的設計模式（如單例和迭代子）在包含不使用任何并發上下文假設的順序程序中可以工作的很好。為了說明這點，考慮一個標準的單例模式在多線程環境下的實現。單例模式保證一個類僅有一個實例同時提供了全局唯一的訪問這個實例的入口點。在c++程序中動態分配單例對象是通用的方式，這是因為c++程序沒有很好的定義靜態全局對象的初始化次序，因此是不可移植的。而且，動態分配避免了單例對象在永遠沒有被使用情況下的初始化開銷。
class Singleton
{
public:
static Singleton *instance (void)
{
if (instance_ == 0)
// Critical section.
instance_ = new Singleton;
return instance_;
}
void method (void);
// Other methods and members omitted.
private:
static Singleton *instance_;
};
應用代碼在使用單例對象提供的操作前，通過調用靜態的instance方法來獲取單例對象的引用，如下所示：
Singleton::instance ()->method ();
2、問題：競爭條件。不幸的是，上面展示的標準單例模式的實現在搶先多任務和真正并行環境下無法正常工作。例如，如果在并行主機上運行的多個線程在單例對象初始化之前同時調用Singleton::instance方法，Singleton的構造函數將被調用多次，這是因為多個線程將在上面展示的臨界區中執行new singleton操作。臨界區是一個必須遵守下列定式的指令序列：當一個線程/進程在臨界區中運行時，沒有其他任何線程/進程會同時在臨界區中運行。在這個例子中，單例的初始化過程是一個臨界區，違反臨界區的原則，在最好的情況下將導致內存泄漏，最壞的情況下，如果初始化過程不是冪等的（idempotent.），將導致嚴重的后果。
3、 通常的陷阱和弊端。實現臨界區的通常方法是在類中增加一個靜態的Mutex對象。這個Mutex保證單例的分配和初始化是原子操作，如下：
class Singleton
{
public:
static Singleton *instance (void)
{
// Constructor of guard acquires lock_ automatically.
Guard guard (lock_);
// Only one thread in the critical section at a time.
if (instance_ == 0)
instance_ = new Singleton;
return instance_;
// Destructor of guard releases lock_ automatically.
}
private:
static Mutex lock_;
static Singleton *instance_;
};
guard類使用了一個c++的習慣用法，當這個類的對象實例被創建時，它使用構造函數來自動獲取一個資源，當類對象離開一個區域時，使用析構器來自動釋放這個資源。通過使用guard，每一個對Singleton::instance方法的訪問將自動的獲取和釋放lock_。
即使這個臨界區只是被使用了一次，但是每個對instance方法的調用都必須獲取和釋放lock_。雖然現在這個實現是線程安全的，但過多的加鎖負載是不能被接受的。一個明顯（雖然不正確）的優化方法是將guard放在針對instance進行條件檢測的內部：
static Singleton *instance (void)
{
if (instance_ == 0) {
Guard guard (lock_);
// Only come here if instance_ hasn't been initialized yet.
instance_ = new Singleton;
}
return instance_;
}
這將減少加鎖負載，但是不能提供線程安全的初始化。在多線程的應用中，仍然存在競爭條件，將導致多次初始化instance_。例如，考慮兩個線程同時檢測 instance_ == 0，都將會成功，一個將通過guard獲取lock_另一個將被阻塞。當第一線程初始化Singleton后釋放lock_，被阻塞的線程將獲取lock_，錯誤的再次初始化Singleton。
4、解決之道，Double Checked Locking優化。解決這個問題更好的方法是使用Double Checked Locking。它是一種用于清除不必要加鎖過程的優化模式。具有諷刺意味的是，它的實現幾乎和前面的方法一樣。通過在另一個條件檢測中包裝對new的調用來避免不必要的加鎖：
class Singleton
{
public:
static Singleton *instance (void)
{
// First check
if (instance_ == 0)
{
// Ensure serialization (guard constructor acquires lock_).
Guard guard (lock_);
// Double check.
if (instance_ == 0)
instance_ = new Singleton;
}
return instance_;
// guard destructor releases lock_.
}
private:
static Mutex lock_;
static Singleton *instance_;
};
第一個獲取lock_的線程將構建Singleton，并將指針分配給instance_，后續調用instance方法的線程將發現instance_ != 0，于是將跳過初始化過程。如果多個線程試圖并發初始化Singleton，第二個檢測件阻止競爭條件的發生。在上面的代碼中，這些線程將在lock_上排隊，當排隊的線程最終獲取lock_時，他們將發現instance_ != 0于是將跳過初始化過程。
上面Singleton::instance的實現僅僅在Singleton首次被初始化時，如果有多個線程同時進入instance方法將導致加鎖負載。在后續對Singleton::instance的調用因為instance_ != 0而不會有加鎖和解鎖的負載。 通過增加一個mutex和一個二次條件檢測，標準的單例實現可以是線程安全的，同時不會產生過多的初始化加鎖負載。
適應性
> 當一個應用具有下列特征時，可以使用Double Checked Locking優化模式：
1、應用包含一個或多個需要順序執行的臨界區代碼。
2、多個線程可能潛在的試圖并發執行臨界區。
3、臨界區僅僅需要被執行一次。
4、在每一個對臨界區的訪問進行加鎖操作將導致過多加鎖負載。
5、在一個鎖的范圍內增加一個輕量的，可靠的條件檢測是可行的。
結構和參與者
通過使用偽代碼能夠最好地展示Double Checked Locking模式的結構和參與者，圖1展示了在Double Checked Locking模式有下列參與者：
1、僅有一次臨界區（Just Once Critical Section,）。臨界區所包含的代碼僅僅被執行一次。例如，單例對象僅僅被初始化一次。這樣，執行對new Singleton的調用（只有一次）相對于Singleton::instance方法的訪問將非常稀少。
2、mutex。鎖被用來序列化對臨界區中代碼的訪問。
3、標記。標記被用來指示臨界區的代碼是否已經被執行過。在上面的例子中單例指針instance_被用來作為標記。
4、 應用線程。試圖執行臨界區代碼的線程。
協作
圖2展示了Double Checked Locking模式的參與者之間的互動。作為一種普通的優化用例，應用線程首先檢測flag是否已經被設置。如果沒有被設置，mutex將被獲取。在持有這個鎖之后，應用線程將再次檢測flag是否被設置，實現Just Once Critical Section，設定flag為真。最后應用線程釋放鎖。
結論
使用Double Checked Locking模式帶來的幾點好處：
1、最小化加鎖。通過實現兩個flag檢測，Double Checked Locking模式實現通常用例的優化。一旦flag被設置，第一個檢測將保證后續的訪問不要加鎖操作。
2、防止競爭條件。對flag的第二個檢測將保證臨界區中的事件僅實現一次。
使用Double Checked Locking模式也將帶來一個缺點：產生微妙的移植bug的潛能。這個微妙的移植問題能夠導致致命的bug，如果使用Double Checked Locking模式的軟件被移植到沒有原子性的指針和正數賦值語義的硬件平臺上。例如，如果一個instance_指針被用來作為Singleton實現的flag，instance_指針中的所有位（bit）必須在一次操作中完成讀和寫。如果將new的結果寫入內存不是一個原子操作，其他的線程可能會試圖讀取一個不健全的指針，這將導致非法的內存訪問。
在一些允許內存地址跨越對齊邊界的系統上這種現象是可能的，因此每次訪問需要從內存中取兩次。在這種情況下，系統可能使用分離的字對齊合成flag，來表示instance_指針。
如果一個過于激進（aggressive）編譯器通過某種緩沖手段來優化flag，或是移除了第二個flag==0檢測，將帶來另外的相關問題。后面會介紹如何使用volatile關鍵字來解決這個問題。
實現和例子代碼
ACE在多個庫組件中使用Double Checked Locking模式。例如，為了減少代碼的重復，ACE使用了一個可重用的適配器ACE Singleton來將普通的類轉換成具有單例行為的類。下面的代碼展示了如何用Double Checked Locking模式來實現ACE Singleton。
// A Singleton Adapter: uses the Adapter
// pattern to turn ordinary classes into
// Singletons optimized with the
// Double-Checked Locking pattern.
template
class ACE_Singleton
{
public:
static TYPE *instance (void);
protected:
static TYPE *instance_;
static LOCK lock_;
};
template TYPE *
ACE_Singleton::instance ()
{
// Perform the Double-Checked Locking to
// ensure proper initialization.
if (instance_ == 0) {
ACE_Guard lock (lock_);
if (instance_ == 0)
instance_ = new TYPE;
}
return instance_;
}
ACE Singleton類被TYPE和LOCK來參數化。因此一個給定TYEP的類將被轉換成使用LOCK類型的互斥量的具有單例行為的類。
ACE中的Token Manager.是使用ACE Singleton的一個例子。Token Manager實現在多線程應用中對本地和遠端的token（一種遞歸鎖）死鎖檢測。為了減少資源的使用，Token Manager被按需創建。為了創建一個單例的Token Manager對象，只是需要實現下面的typedef：
typedef ACE_Singleton
Token_Mgr;
Token Manager單例將被用于本地和遠端的token死鎖檢測。在一個線程阻塞等待互斥量之前，它首先查詢Token Manager單例，來測試阻塞是否會導致死鎖狀態。對于系統中的每一個token，Token Manager單例維護一個持有token線程和所有阻塞等待在該token的線程記錄鏈表。這些數據將提供充足的檢測死鎖狀態的依據。使用Token Manager單例的過程如下：
// Acquire the mutex.
int Mutex_Token::acquire (void)
{
// If the token is already held, we must block.
if (mutex_in_use ()) {
// Use the Token_Mgr Singleton to check
// for a deadlock situation *before* blocking.
if (Token_Mgr::instance ()->testdeadlock ()) {
errno = EDEADLK;
return -1;
}
else
// Sleep waiting for the lock...
// Acquire lock...
}
變化
一種變化的Double Checked Locking模式實現可能是需要的，如果一個編譯器通過某種緩沖方式優化了flag。在這種情況下，緩沖的粘著性（coherency）將變成問題，如果拷貝flag到多個線程的寄存器中，會產生不一致現象。如果一個線程更改flag的值將不能反映在其他線程的對應拷貝中。
另一個相關的問題是編譯器移除了第二個flag==0檢測，因為它對于持有高度優化特性的編譯器來說是多余的。例如，下面的代碼在激進的編譯器下將被跳過對flag的讀取，而是假定instance_還是為0，因為它沒有被聲明為volatile的。
Singleton *Singleton::instance (void)
{
if (Singleton::instance_ == 0)
{
// Only lock if instance_ isn't 0.
Guard guard (lock_);
// Dead code elimination may remove the next line.
// Perform the Double-Check.
if (Singleton::instance_ == 0)
// ...
解決這兩個問題的一個方法是生命flag為Singleton的volatile成員變量，如下：
private:
static volatile long Flag_; // Flag is volatile.
使用volatile將保證編譯器不會將flag緩沖到編譯器，同時也不會優化掉第二次讀操作。使用volatile關鍵字的言下之意是所有對flag的訪問是通過內存，而不是通過寄存器。
相關模式
Double Checked Locking模式是First-Time-In習慣用法的一個變化。First-Time-In習慣用法經常使用在類似c這種缺少構造器的程序語言中，下面的代碼展示了這個模式：
static const int STACK_SIZE = 1000;
static T *stack_;
static int top_;
void push (T *item)
{
// First-time-in flag
if (stack_ == 0) {
stack_ = malloc (STACK_SIZE * sizeof *stack);
assert (stack_ != 0);
top_ = 0;
}
stack_[top_++] = item;
// ...
}
第一次push被調用時，stack_是0，這將導致觸發malloc來初始化它自己。