J++ = Java + ?

ACE中的Double Checked Locking 模式

(作者:Douglas C. Schmidt ,by huihoo.org CORBA課題 Thzhang 譯 , Allen整理,制作)

意圖

無(wú)論什么時(shí)候當(dāng)臨界區(qū)中的代碼僅僅需要加鎖一次，同時(shí)當(dāng)其獲取鎖的時(shí)候必須是線程安全的，可以用Double Checked Locking 模式來(lái)減少競(jìng)爭(zhēng)和加鎖載荷。

動(dòng)機(jī)

1、標(biāo)準(zhǔn)的單例。開(kāi)發(fā)正確的有效的并發(fā)應(yīng)用是困難的。程序員必須學(xué)習(xí)新的技術(shù)（并發(fā)控制和防止死鎖的算法）和機(jī)制（如多線程和同步API）。此外，許多熟悉的設(shè)計(jì)模式（如單例和迭代子）在包含不使用任何并發(fā)上下文假設(shè)的順序程序中可以工作的很好。為了說(shuō)明這點(diǎn)，考慮一個(gè)標(biāo)準(zhǔn)的單例模式在多線程環(huán)境下的實(shí)現(xiàn)。單例模式保證一個(gè)類僅有一個(gè)實(shí)例同時(shí)提供了全局唯一的訪問(wèn)這個(gè)實(shí)例的入口點(diǎn)。在c++程序中動(dòng)態(tài)分配單例對(duì)象是通用的方式，這是因?yàn)閏++程序沒(méi)有很好的定義靜態(tài)全局對(duì)象的初始化次序，因此是不可移植的。而且，動(dòng)態(tài)分配避免了單例對(duì)象在永遠(yuǎn)沒(méi)有被使用情況下的初始化開(kāi)銷。

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_;
};

應(yīng)用代碼在使用單例對(duì)象提供的操作前，通過(guò)調(diào)用靜態(tài)的instance方法來(lái)獲取單例對(duì)象的引用，如下所示：
Singleton::instance ()->method ();
2、問(wèn)題：競(jìng)爭(zhēng)條件。不幸的是，上面展示的標(biāo)準(zhǔn)單例模式的實(shí)現(xiàn)在搶先多任務(wù)和真正并行環(huán)境下無(wú)法正常工作。例如，如果在并行主機(jī)上運(yùn)行的多個(gè)線程在單例對(duì)象初始化之前同時(shí)調(diào)用Singleton::instance方法，Singleton的構(gòu)造函數(shù)將被調(diào)用多次，這是因?yàn)槎鄠€(gè)線程將在上面展示的臨界區(qū)中執(zhí)行new singleton操作。臨界區(qū)是一個(gè)必須遵守下列定式的指令序列：當(dāng)一個(gè)線程/進(jìn)程在臨界區(qū)中運(yùn)行時(shí)，沒(méi)有其他任何線程/進(jìn)程會(huì)同時(shí)在臨界區(qū)中運(yùn)行。在這個(gè)例子中，單例的初始化過(guò)程是一個(gè)臨界區(qū)，違反臨界區(qū)的原則，在最好的情況下將導(dǎo)致內(nèi)存泄漏，最壞的情況下，如果初始化過(guò)程不是冪等的（idempotent.），將導(dǎo)致嚴(yán)重的后果。

3、 通常的陷阱和弊端。實(shí)現(xiàn)臨界區(qū)的通常方法是在類中增加一個(gè)靜態(tài)的Mutex對(duì)象。這個(gè)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類使用了一個(gè)c++的習(xí)慣用法，當(dāng)這個(gè)類的對(duì)象實(shí)例被創(chuàng)建時(shí)，它使用構(gòu)造函數(shù)來(lái)自動(dòng)獲取一個(gè)資源，當(dāng)類對(duì)象離開(kāi)一個(gè)區(qū)域時(shí)，使用析構(gòu)器來(lái)自動(dòng)釋放這個(gè)資源。通過(guò)使用guard，每一個(gè)對(duì)Singleton::instance方法的訪問(wèn)將自動(dòng)的獲取和釋放lock_。
即使這個(gè)臨界區(qū)只是被使用了一次，但是每個(gè)對(duì)instance方法的調(diào)用都必須獲取和釋放lock_。雖然現(xiàn)在這個(gè)實(shí)現(xiàn)是線程安全的，但過(guò)多的加鎖負(fù)載是不能被接受的。一個(gè)明顯（雖然不正確）的優(yōu)化方法是將guard放在針對(duì)instance進(jìn)行條件檢測(cè)的內(nèi)部：

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_;
}

這將減少加鎖負(fù)載，但是不能提供線程安全的初始化。在多線程的應(yīng)用中，仍然存在競(jìng)爭(zhēng)條件，將導(dǎo)致多次初始化instance_。例如，考慮兩個(gè)線程同時(shí)檢測(cè) instance_ == 0，都將會(huì)成功，一個(gè)將通過(guò)guard獲取lock_另一個(gè)將被阻塞。當(dāng)?shù)谝痪€程初始化Singleton后釋放lock_，被阻塞的線程將獲取lock_，錯(cuò)誤的再次初始化Singleton。
4、解決之道，Double Checked Locking優(yōu)化。解決這個(gè)問(wèn)題更好的方法是使用Double Checked Locking。它是一種用于清除不必要加鎖過(guò)程的優(yōu)化模式。具有諷刺意味的是，它的實(shí)現(xiàn)幾乎和前面的方法一樣。通過(guò)在另一個(gè)條件檢測(cè)中包裝對(duì)new的調(diào)用來(lái)避免不必要的加鎖：

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_;
};

第一個(gè)獲取lock_的線程將構(gòu)建Singleton，并將指針?lè)峙浣oinstance_，后續(xù)調(diào)用instance方法的線程將發(fā)現(xiàn)instance_ != 0，于是將跳過(guò)初始化過(guò)程。如果多個(gè)線程試圖并發(fā)初始化Singleton，第二個(gè)檢測(cè)件阻止競(jìng)爭(zhēng)條件的發(fā)生。在上面的代碼中，這些線程將在lock_上排隊(duì)，當(dāng)排隊(duì)的線程最終獲取lock_時(shí)，他們將發(fā)現(xiàn)instance_ != 0于是將跳過(guò)初始化過(guò)程。

上面Singleton::instance的實(shí)現(xiàn)僅僅在Singleton首次被初始化時(shí)，如果有多個(gè)線程同時(shí)進(jìn)入instance方法將導(dǎo)致加鎖負(fù)載。在后續(xù)對(duì)Singleton::instance的調(diào)用因?yàn)閕nstance_ != 0而不會(huì)有加鎖和解鎖的負(fù)載。 通過(guò)增加一個(gè)mutex和一個(gè)二次條件檢測(cè)，標(biāo)準(zhǔn)的單例實(shí)現(xiàn)可以是線程安全的，同時(shí)不會(huì)產(chǎn)生過(guò)多的初始化加鎖負(fù)載。

適應(yīng)性

> 當(dāng)一個(gè)應(yīng)用具有下列特征時(shí)，可以使用Double Checked Locking優(yōu)化模式：
1、應(yīng)用包含一個(gè)或多個(gè)需要順序執(zhí)行的臨界區(qū)代碼。
2、多個(gè)線程可能潛在的試圖并發(fā)執(zhí)行臨界區(qū)。
3、臨界區(qū)僅僅需要被執(zhí)行一次。
4、在每一個(gè)對(duì)臨界區(qū)的訪問(wèn)進(jìn)行加鎖操作將導(dǎo)致過(guò)多加鎖負(fù)載。
5、在一個(gè)鎖的范圍內(nèi)增加一個(gè)輕量的，可靠的條件檢測(cè)是可行的。

結(jié)構(gòu)和參與者

通過(guò)使用偽代碼能夠最好地展示Double Checked Locking模式的結(jié)構(gòu)和參與者，圖1展示了在Double Checked Locking模式有下列參與者：

1、僅有一次臨界區(qū)（Just Once Critical Section,）。臨界區(qū)所包含的代碼僅僅被執(zhí)行一次。例如，單例對(duì)象僅僅被初始化一次。這樣，執(zhí)行對(duì)new Singleton的調(diào)用（只有一次）相對(duì)于Singleton::instance方法的訪問(wèn)將非常稀少。
2、mutex。鎖被用來(lái)序列化對(duì)臨界區(qū)中代碼的訪問(wèn)。
3、標(biāo)記。標(biāo)記被用來(lái)指示臨界區(qū)的代碼是否已經(jīng)被執(zhí)行過(guò)。在上面的例子中單例指針instance_被用來(lái)作為標(biāo)記。
4、 應(yīng)用線程。試圖執(zhí)行臨界區(qū)代碼的線程。

協(xié)作

圖2展示了Double Checked Locking模式的參與者之間的互動(dòng)。作為一種普通的優(yōu)化用例，應(yīng)用線程首先檢測(cè)flag是否已經(jīng)被設(shè)置。如果沒(méi)有被設(shè)置，mutex將被獲取。在持有這個(gè)鎖之后，應(yīng)用線程將再次檢測(cè)flag是否被設(shè)置，實(shí)現(xiàn)Just Once Critical Section，設(shè)定flag為真。最后應(yīng)用線程釋放鎖。

結(jié)論

使用Double Checked Locking模式帶來(lái)的幾點(diǎn)好處：
1、最小化加鎖。通過(guò)實(shí)現(xiàn)兩個(gè)flag檢測(cè)，Double Checked Locking模式實(shí)現(xiàn)通常用例的優(yōu)化。一旦flag被設(shè)置，第一個(gè)檢測(cè)將保證后續(xù)的訪問(wèn)不要加鎖操作。
2、防止競(jìng)爭(zhēng)條件。對(duì)flag的第二個(gè)檢測(cè)將保證臨界區(qū)中的事件僅實(shí)現(xiàn)一次。
使用Double Checked Locking模式也將帶來(lái)一個(gè)缺點(diǎn)：產(chǎn)生微妙的移植bug的潛能。這個(gè)微妙的移植問(wèn)題能夠?qū)е轮旅腷ug，如果使用Double Checked Locking模式的軟件被移植到?jīng)]有原子性的指針和正數(shù)賦值語(yǔ)義的硬件平臺(tái)上。例如，如果一個(gè)instance_指針被用來(lái)作為Singleton實(shí)現(xiàn)的flag，instance_指針中的所有位（bit）必須在一次操作中完成讀和寫(xiě)。如果將new的結(jié)果寫(xiě)入內(nèi)存不是一個(gè)原子操作，其他的線程可能會(huì)試圖讀取一個(gè)不健全的指針，這將導(dǎo)致非法的內(nèi)存訪問(wèn)。
在一些允許內(nèi)存地址跨越對(duì)齊邊界的系統(tǒng)上這種現(xiàn)象是可能的，因此每次訪問(wèn)需要從內(nèi)存中取兩次。在這種情況下，系統(tǒng)可能使用分離的字對(duì)齊合成flag，來(lái)表示instance_指針。
如果一個(gè)過(guò)于激進(jìn)（aggressive）編譯器通過(guò)某種緩沖手段來(lái)優(yōu)化flag，或是移除了第二個(gè)flag==0檢測(cè)，將帶來(lái)另外的相關(guān)問(wèn)題。后面會(huì)介紹如何使用volatile關(guān)鍵字來(lái)解決這個(gè)問(wèn)題。

實(shí)現(xiàn)和例子代碼

ACE在多個(gè)庫(kù)組件中使用Double Checked Locking模式。例如，為了減少代碼的重復(fù)，ACE使用了一個(gè)可重用的適配器ACE Singleton來(lái)將普通的類轉(zhuǎn)換成具有單例行為的類。下面的代碼展示了如何用Double Checked Locking模式來(lái)實(shí)現(xiàn)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來(lái)參數(shù)化。因此一個(gè)給定TYEP的類將被轉(zhuǎn)換成使用LOCK類型的互斥量的具有單例行為的類。
ACE中的Token Manager.是使用ACE Singleton的一個(gè)例子。Token Manager實(shí)現(xiàn)在多線程應(yīng)用中對(duì)本地和遠(yuǎn)端的token（一種遞歸鎖）死鎖檢測(cè)。為了減少資源的使用，Token Manager被按需創(chuàng)建。為了創(chuàng)建一個(gè)單例的Token Manager對(duì)象，只是需要實(shí)現(xiàn)下面的typedef：

typedef ACE_Singleton Token_Mgr;
Token Manager單例將被用于本地和遠(yuǎn)端的token死鎖檢測(cè)。在一個(gè)線程阻塞等待互斥量之前，它首先查詢Token Manager單例，來(lái)測(cè)試阻塞是否會(huì)導(dǎo)致死鎖狀態(tài)。對(duì)于系統(tǒng)中的每一個(gè)token，Token Manager單例維護(hù)一個(gè)持有token線程和所有阻塞等待在該token的線程記錄鏈表。這些數(shù)據(jù)將提供充足的檢測(cè)死鎖狀態(tài)的依據(jù)。使用Token Manager單例的過(guò)程如下：

// 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模式實(shí)現(xiàn)可能是需要的，如果一個(gè)編譯器通過(guò)某種緩沖方式優(yōu)化了flag。在這種情況下，緩沖的粘著性（coherency）將變成問(wèn)題，如果拷貝flag到多個(gè)線程的寄存器中，會(huì)產(chǎn)生不一致現(xiàn)象。如果一個(gè)線程更改flag的值將不能反映在其他線程的對(duì)應(yīng)拷貝中。

另一個(gè)相關(guān)的問(wèn)題是編譯器移除了第二個(gè)flag==0檢測(cè)，因?yàn)樗鼘?duì)于持有高度優(yōu)化特性的編譯器來(lái)說(shuō)是多余的。例如，下面的代碼在激進(jìn)的編譯器下將被跳過(guò)對(duì)flag的讀取，而是假定instance_還是為0，因?yàn)樗鼪](méi)有被聲明為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)
// ...

解決這兩個(gè)問(wèn)題的一個(gè)方法是生命flag為Singleton的volatile成員變量，如下：
private:
static volatile long Flag_; // Flag is volatile.
使用volatile將保證編譯器不會(huì)將flag緩沖到編譯器，同時(shí)也不會(huì)優(yōu)化掉第二次讀操作。使用volatile關(guān)鍵字的言下之意是所有對(duì)flag的訪問(wèn)是通過(guò)內(nèi)存，而不是通過(guò)寄存器。

相關(guān)模式

Double Checked Locking模式是First-Time-In習(xí)慣用法的一個(gè)變化。First-Time-In習(xí)慣用法經(jīng)常使用在類似c這種缺少構(gòu)造器的程序語(yǔ)言中，下面的代碼展示了這個(gè)模式：

	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被調(diào)用時(shí)，stack_是0，這將導(dǎo)致觸發(fā)malloc來(lái)初始化它自己。