寫出正確程序的第一步是掌握這些并發(fā)編程缺陷

多年來(lái)，研究人員花了大量的時(shí)間和精力研究并發(fā)編程的缺陷。很多早期的工作是關(guān)于死鎖的，之前的章節(jié)也有提及，本章會(huì)深入學(xué)習(xí)[C+71]。最近的研究集中在一些其他類型的常見(jiàn)并發(fā)缺陷（即非死鎖缺陷）。在本章中，我們會(huì)簡(jiǎn)要了解一些并發(fā)問(wèn)題的例子，以便更好地理解要注意什么問(wèn)題。因此，本章的關(guān)鍵問(wèn)題就是：

關(guān)鍵問(wèn)題：如何處理常見(jiàn)的并發(fā)缺陷

并發(fā)缺陷會(huì)有很多常見(jiàn)的模式。了解這些模式是寫出健壯、正確程序的第一步。

32.1　有哪些類型的缺陷

第一個(gè)最明顯的問(wèn)題就是：在復(fù)雜并發(fā)程序中，有哪些類型的缺陷呢？一般來(lái)說(shuō)，這個(gè)問(wèn)題很難回答，好在其他人已經(jīng)做過(guò)相關(guān)的工作。具體來(lái)說(shuō)，Lu等人[L+08]詳細(xì)分析了一些流行的并發(fā)應(yīng)用，以理解實(shí)踐中有哪些類型的缺陷。

研究集中在4個(gè)重要的開(kāi)源應(yīng)用：MySQL（流行的數(shù)據(jù)庫(kù)管理系統(tǒng)）、Apache（著名的Web服務(wù)器）、Mozilla（著名的Web瀏覽器）和OpenOffice（微軟辦公套件的開(kāi)源版本）。研究人員通過(guò)檢查這幾個(gè)代碼庫(kù)已修復(fù)的并發(fā)缺陷，將開(kāi)發(fā)者的工作變成量化的缺陷分析。理解這些結(jié)果，有助于我們了解在成熟的代碼庫(kù)中，實(shí)際出現(xiàn)過(guò)哪些類型的并發(fā)問(wèn)題。

表32.1是Lu及其同事的研究結(jié)論。可以看出，共有105個(gè)缺陷，其中大多數(shù)是非死鎖相關(guān)的（74個(gè)），剩余31個(gè)是死鎖缺陷。另外，可以看出每個(gè)應(yīng)用的缺陷數(shù)目，OpenOffice只有8個(gè)，而Mozilla有接近60個(gè)。

表32.1　現(xiàn)代應(yīng)用程序的缺陷統(tǒng)計(jì)

我們現(xiàn)在來(lái)深入分析這兩種類型的缺陷。對(duì)于第一類非死鎖的缺陷，我們通過(guò)該研究的例子來(lái)討論。對(duì)于第二類死鎖缺陷，我們討論人們?cè)谧柚埂⒈苊夂吞幚硭梨i上完成的大量工作。

32.2　非死鎖缺陷

Lu的研究表明，非死鎖問(wèn)題占了并發(fā)問(wèn)題的大多數(shù)。它們是怎么發(fā)生的？我們?nèi)绾涡迯?fù)？我們現(xiàn)在主要討論其中兩種：違反原子性（atomicity violation）缺陷和錯(cuò)誤順序（order violation）缺陷。

違反原子性缺陷

第一種類型的問(wèn)題叫作違反原子性。這是一個(gè)MySQL中出現(xiàn)的例子。讀者可以先自行找出其中問(wèn)題所在。

1????Thread?1::2????if?(thd->proc_info)?{3??????...4??????fputs(thd->proc_info,?...);5??????...6????}78????Thread?2::9????thd->proc_info?=?NULL;

這個(gè)例子中，兩個(gè)線程都要訪問(wèn)thd結(jié)構(gòu)中的成員proc_info。第一個(gè)線程檢查proc_info非空，然后打印出值；第二個(gè)線程設(shè)置其為空。顯然，當(dāng)?shù)谝粋€(gè)線程檢查之后，在fputs()調(diào)用之前被中斷，第二個(gè)線程把指針置為空；當(dāng)?shù)谝粋€(gè)線程恢復(fù)執(zhí)行時(shí)，由于引用空指針，導(dǎo)致程序奔潰。

根據(jù)Lu等人，更正式的違反原子性的定義是：“違反了多次內(nèi)存訪問(wèn)中預(yù)期的可串行性（即代碼段本意是原子的，但在執(zhí)行中并沒(méi)有強(qiáng)制實(shí)現(xiàn)原子性）”。在我們的例子中，proc_info的非空檢查和fputs()調(diào)用打印proc_info是假設(shè)原子的，當(dāng)假設(shè)不成立時(shí)，代碼就出問(wèn)題了。

這種問(wèn)題的修復(fù)通常（但不總是）很簡(jiǎn)單。你能想到如何修復(fù)嗎？

在這個(gè)方案中，我們只要給共享變量的訪問(wèn)加鎖，確保每個(gè)線程訪問(wèn)proc_info字段時(shí)，都持有鎖（proc_info_lock）。當(dāng)然，訪問(wèn)這個(gè)結(jié)構(gòu)的所有其他代碼，也應(yīng)該先獲取鎖。

1????pthread_mutex_t?proc_info_lock?=?PTHREAD_MUTEX_INITIALIZER;23????Thread?1::4????pthread_mutex_lock(&proc_info_lock);5????if?(thd->proc_info)?{6??????...7??????fputs(thd->proc_info,?...);8??????...9????}10????pthread_mutex_unlock(&proc_info_lock);1112???Thread?2::13???pthread_mutex_lock(&proc_info_lock);14???thd->proc_info?=?NULL;15???pthread_mutex_unlock(&proc_info_lock);

違反順序缺陷

Lu等人提出的另一種常見(jiàn)的非死鎖問(wèn)題叫作違反順序（order violation）。下面是一個(gè)簡(jiǎn)單的例子。同樣，看看你是否能找出為什么下面的代碼有缺陷。

1????Thread?1::2????void?init()?{3????????...4????????mThread?=?PR_CreateThread(mMain,?...);5????????...6????}78????Thread?2::9????void?mMain(...)?{10???????...11???????mState?=?mThread->State;12???????...13???}

你可能已經(jīng)發(fā)現(xiàn)，線程2的代碼中似乎假定變量mThread已經(jīng)被初始化了（不為空）。然而，如果線程1并沒(méi)有首先執(zhí)行，線程2就可能因?yàn)橐每罩羔槺紳ⅲ僭O(shè)mThread初始值為空；否則，可能會(huì)產(chǎn)生更加奇怪的問(wèn)題，因?yàn)榫€程2中會(huì)讀到任意的內(nèi)存位置并引用）。

違反順序更正式的定義是：“兩個(gè)內(nèi)存訪問(wèn)的預(yù)期順序被打破了（即A應(yīng)該在B之前執(zhí)行，但是實(shí)際運(yùn)行中卻不是這個(gè)順序）”[L+08]。

我們通過(guò)強(qiáng)制順序來(lái)修復(fù)這種缺陷。正如之前詳細(xì)討論的，條件變量（condition variables）就是一種簡(jiǎn)單可靠的方式，在現(xiàn)代代碼集中加入這種同步。在上面的例子中，我們可以把代碼修改成這樣：

1????pthread_mutex_t?mtLock?=?PTHREAD_MUTEX_INITIALIZER;2????pthread_cond_t?mtCond?=?PTHREAD_COND_INITIALIZER;3????int?mtInit????????????=?0;45????Thread?1::6????void?init()?{7???????...8???????mThread?=?PR_CreateThread(mMain,?...);910??????//?signal?that?the?thread?has?been?created...11??????pthread_mutex_lock(&mtLock);12??????mtInit?=?1;13??????pthread_cond_signal(&mtCond);14??????pthread_mutex_unlock(&mtLock);15??????...16???}1718???Thread?2::19???void?mMain(...)?{20??????...21??????//?wait?for?the?thread?to?be?initialized...22??????pthread_mutex_lock(&mtLock);23??????while?(mtInit?==?0)24??????????pthread_cond_wait(&mtCond,??&mtLock);25??????pthread_mutex_unlock(&mtLock);2627??????mState?=?mThread->State;28??????...29???}

在這段修復(fù)的代碼中，我們?cè)黾恿艘粋€(gè)鎖（mtLock）、一個(gè)條件變量（mtCond）以及狀態(tài)的變量（mtInit）。初始化代碼運(yùn)行時(shí)，會(huì)將mtInit設(shè)置為1，并發(fā)出信號(hào)表明它已做了這件事。如果線程2先運(yùn)行，就會(huì)一直等待信號(hào)和對(duì)應(yīng)的狀態(tài)變化；如果后運(yùn)行，線程2會(huì)檢查是否初始化（即mtInit被設(shè)置為1），然后正常運(yùn)行。請(qǐng)注意，我們可以用mThread本身作為狀態(tài)變量，但為了簡(jiǎn)潔，我們沒(méi)有這樣做。當(dāng)線程之間的順序很重要時(shí)，條件變量（或信號(hào)量）能夠解決問(wèn)題。

非死鎖缺陷：小結(jié)

Lu等人的研究中，大部分（97%）的非死鎖問(wèn)題是違反原子性和違反順序這兩種。因此，程序員仔細(xì)研究這些錯(cuò)誤模式，應(yīng)該能夠更好地避免它們。此外，隨著更自動(dòng)化的代碼檢查工具的發(fā)展，它們也應(yīng)該關(guān)注這兩種錯(cuò)誤，因?yàn)殚_(kāi)發(fā)中發(fā)現(xiàn)的非死鎖問(wèn)題大部分都是這兩種。

然而，并不是所有的缺陷都像我們舉的例子一樣，這么容易修復(fù)。有些問(wèn)題需要對(duì)應(yīng)用程序的更深的了解，以及大量代碼及數(shù)據(jù)結(jié)構(gòu)的調(diào)整。閱讀Lu等人的優(yōu)秀（可讀性強(qiáng)）的論文，了解更多細(xì)節(jié)。

32.3　死鎖缺陷

除了上面提到的并發(fā)缺陷，死鎖（deadlock）是一種在許多復(fù)雜并發(fā)系統(tǒng)中出現(xiàn)的經(jīng)典問(wèn)題。例如，當(dāng)線程1持有鎖L1，正在等待另外一個(gè)鎖L2，而線程2持有鎖L2，卻在等待鎖L1釋放時(shí)，死鎖就產(chǎn)生了。以下的代碼片段就可能出現(xiàn)這種死鎖：

Thread?1:????Thread?2:lock(L1);????lock(L2);lock(L2);????lock(L1);

這段代碼運(yùn)行時(shí)，不是一定會(huì)出現(xiàn)死鎖的。當(dāng)線程1占有鎖L1，上下文切換到線程2。線程2鎖住L2，試圖鎖住L1。這時(shí)才產(chǎn)生了死鎖，兩個(gè)線程互相等待。如圖32.1所示，其中的圈（cycle）表明了死鎖。

圖32.1　死鎖依賴圖

該圖應(yīng)該有助于描述清楚問(wèn)題。程序員在編寫代碼中應(yīng)該如何處理死鎖呢？

關(guān)鍵問(wèn)題：如何對(duì)付死鎖

我們?cè)趯?shí)現(xiàn)系統(tǒng)時(shí)，如何避免或者能夠檢測(cè)、恢復(fù)死鎖呢？這是目前系統(tǒng)中的真實(shí)問(wèn)題嗎？

為什么發(fā)生死鎖

你可能在想，上文提到的這個(gè)死鎖的例子，很容易就可以避免。例如，只要線程1和線程2都用相同的搶鎖順序，死鎖就不會(huì)發(fā)生。那么，死鎖為什么還會(huì)發(fā)生？

其中一個(gè)原因是在大型的代碼庫(kù)里，組件之間會(huì)有復(fù)雜的依賴。以操作系統(tǒng)為例。虛擬內(nèi)存系統(tǒng)在需要訪問(wèn)文件系統(tǒng)才能從磁盤讀到內(nèi)存頁(yè)；文件系統(tǒng)隨后又要和虛擬內(nèi)存交互，去申請(qǐng)一頁(yè)內(nèi)存，以便存放讀到的塊。因此，在設(shè)計(jì)大型系統(tǒng)的鎖機(jī)制時(shí)，你必須要仔細(xì)地去避免循環(huán)依賴導(dǎo)致的死鎖。

另一個(gè)原因是封裝（encapsulation）。軟件開(kāi)發(fā)者一直傾向于隱藏實(shí)現(xiàn)細(xì)節(jié)，以模塊化的方式讓軟件開(kāi)發(fā)更容易。然而，模塊化和鎖不是很契合。Jula等人指出[J+08]，某些看起來(lái)沒(méi)有關(guān)系的接口可能會(huì)導(dǎo)致死鎖。以Java的Vector類和AddAll()方法為例，我們這樣調(diào)用這個(gè)方法：

Vector?v1,?v2;?v1.AddAll(v2);

在內(nèi)部，這個(gè)方法需要多線程安全，因此針對(duì)被添加向量（v1）和參數(shù)（v2）的鎖都需要獲取。假設(shè)這個(gè)方法，先給v1加鎖，然后再給v2加鎖。如果另外某個(gè)線程幾乎同時(shí)在調(diào)用v2.AddAll(v1)，就可能遇到死鎖。

產(chǎn)生死鎖的條件

死鎖的產(chǎn)生需要如下4個(gè)條件[C+71]。

互斥：線程對(duì)于需要的資源進(jìn)行互斥的訪問(wèn)（例如一個(gè)線程搶到鎖）。

持有并等待：線程持有了資源（例如已將持有的鎖），同時(shí)又在等待其他資源（例如，需要獲得的鎖）。

非搶占：線程獲得的資源（例如鎖），不能被搶占。

循環(huán)等待：線程之間存在一個(gè)環(huán)路，環(huán)路上每個(gè)線程都額外持有一個(gè)資源，而這個(gè)資源又是下一個(gè)線程要申請(qǐng)的。

如果這4個(gè)條件的任何一個(gè)沒(méi)有滿足，死鎖就不會(huì)產(chǎn)生。因此，我們首先研究一下預(yù)防死鎖的方法；每個(gè)策略都設(shè)法阻止某一個(gè)條件，從而解決死鎖的問(wèn)題。

預(yù)防

也許最實(shí)用的預(yù)防技術(shù)（當(dāng)然也是經(jīng)常采用的），就是讓代碼不會(huì)產(chǎn)生循環(huán)等待。最直接的方法就是獲取鎖時(shí)提供一個(gè)全序（total ordering）。假如系統(tǒng)共有兩個(gè)鎖（L1和L2），那么我們每次都先申請(qǐng)L1然后申請(qǐng)L2，就可以避免死鎖。這樣嚴(yán)格的順序避免了循環(huán)等待，也就不會(huì)產(chǎn)生死鎖。

當(dāng)然，更復(fù)雜的系統(tǒng)中不會(huì)只有兩個(gè)鎖，鎖的全序可能很難做到。因此，偏序（partial ordering）可能是一種有用的方法，安排鎖的獲取并避免死鎖。Linux中的內(nèi)存映射代碼就是一個(gè)偏序鎖的好例子[T+94]。代碼開(kāi)頭的注釋表明了10組不同的加鎖順序，包括簡(jiǎn)單的關(guān)系，比如i_mutex早于i_mmap_mutex，也包括復(fù)雜的關(guān)系，比如i_mmap_mutex早于private_lock，早于swap_lock，早于mapping->tree_lock。

你可以想到，全序和偏序都需要細(xì)致的鎖策略的設(shè)計(jì)和實(shí)現(xiàn)。另外，順序只是一種約定，粗心的程序員很容易忽略，導(dǎo)致死鎖。最后，有序加鎖需要深入理解代碼庫(kù)，了解各種函數(shù)的調(diào)用關(guān)系，即使一個(gè)錯(cuò)誤，也會(huì)導(dǎo)致“D”字[1]

。

提示：通過(guò)鎖的地址來(lái)強(qiáng)制鎖的順序

當(dāng)一個(gè)函數(shù)要搶多個(gè)鎖時(shí)，我們需要注意死鎖。比如有一個(gè)函數(shù)：do_something(mutex t *m1, mutex t *m2)，如果函數(shù)總是先搶m1，然后m2，那么當(dāng)一個(gè)線程調(diào)用do_something(L1, L2)，而另一個(gè)線程調(diào)用do_something(L2, L1)時(shí)，就可能會(huì)產(chǎn)生死鎖。

為了避免這種特殊問(wèn)題，聰明的程序員根據(jù)鎖的地址作為獲取鎖的順序。按照地址從高到低，或者從低到高的順序加鎖，do_something()函數(shù)就可以保證不論傳入?yún)?shù)是什么順序，函數(shù)都會(huì)用固定的順序加鎖。具體的代碼如下：

if?(m1?>?m2)?{?//?grab?locks?in?high-to-low?address?order? ??pthread_mutex_lock(m1); ??pthread_mutex_lock(m2); }?else?{? ??pthread_mutex_lock(m2);? ??pthread_mutex_lock(m1); 　 } //?Code?assumes?that?m1?!=?m2?(it?is?not?the?same?lock)

>在獲取多個(gè)鎖時(shí)，通過(guò)簡(jiǎn)單的技巧，就可以確保簡(jiǎn)單有效的無(wú)死鎖實(shí)現(xiàn)。 ####?持有并等待 死鎖的持有并等待條件，可以通過(guò)原子地?fù)屾i來(lái)避免。實(shí)踐中，可以通過(guò)如下代碼來(lái)實(shí)現(xiàn)：

1????lock(prevention); 2????lock(L1); 3????lock(L2); 4????... 5????unlock(prevention);

先搶到prevention這個(gè)鎖之后，代碼保證了在搶鎖的過(guò)程中，不會(huì)有不合時(shí)宜的線程切換，從而避免了死鎖。當(dāng)然，這需要任何線程在任何時(shí)候搶占鎖時(shí)，先搶到全局的prevention鎖。例如，如果另一個(gè)線程用不同的順序搶鎖L1和L2，也不會(huì)有問(wèn)題，因?yàn)榇藭r(shí)，線程已經(jīng)搶到了prevention鎖。 注意，出于某些原因，這個(gè)方案也有問(wèn)題。和之前一樣，它不適用于封裝：因?yàn)檫@個(gè)方案需要我們準(zhǔn)確地知道要搶哪些鎖，并且提前搶到這些鎖。因?yàn)橐崆皳尩剿墟i（同時(shí)），而不是在真正需要的時(shí)候，所以可能降低了并發(fā)。 ####?非搶占 在調(diào)用unlock之前，都認(rèn)為鎖是被占有的，多個(gè)搶鎖操作通常會(huì)帶來(lái)麻煩，因?yàn)槲覀兊却粋€(gè)鎖時(shí)，同時(shí)持有另一個(gè)鎖。很多線程庫(kù)提供更為靈活的接口來(lái)避免這種情況。具體來(lái)說(shuō)，trylock()函數(shù)會(huì)嘗試獲得鎖，或者返回?1，表示鎖已經(jīng)被占有。你可以稍后重試一下。 可以用這一接口來(lái)實(shí)現(xiàn)無(wú)死鎖的加鎖方法：

1????top: 2??????lock(L1); 3??????if?(trylock(L2)?==?-1)?{ 4????????unlock(L1); 5????????goto?top; 6????}

注意，另一個(gè)線程可以使用相同的加鎖方式，但是不同的加鎖順序（L2然后L1），程序仍然不會(huì)產(chǎn)生死鎖。但是會(huì)引來(lái)一個(gè)新的問(wèn)題：活鎖（livelock）。兩個(gè)線程有可能一直重復(fù)這一序列，又同時(shí)都搶鎖失敗。這種情況下，系統(tǒng)一直在運(yùn)行這段代碼（因此不是死鎖），但是又不會(huì)有進(jìn)展，因此名為活鎖。也有活鎖的解決方法：例如，可以在循環(huán)結(jié)束的時(shí)候，先隨機(jī)等待一個(gè)時(shí)間，然后再重復(fù)整個(gè)動(dòng)作，這樣可以降低線程之間的重復(fù)互相干擾。 關(guān)于這個(gè)方案的最后一點(diǎn)：使用trylock方法可能會(huì)有一些困難。第一個(gè)問(wèn)題仍然是封裝：如果其中的某一個(gè)鎖，是封裝在函數(shù)內(nèi)部的，那么這個(gè)跳回開(kāi)始處就很難實(shí)現(xiàn)。如果代碼在中途獲取了某些資源，必須要確保也能釋放這些資源。例如，在搶到L1后，我們的代碼分配了一些內(nèi)存，當(dāng)搶L2失敗時(shí)，并且在返回開(kāi)頭之前，需要釋放這些內(nèi)存。當(dāng)然，在某些場(chǎng)景下（例如，之前提到的Java的vector方法），這種方法很有效。####?互斥最后的預(yù)防方法是完全避免互斥。通常來(lái)說(shuō)，代碼都會(huì)存在臨界區(qū)，因此很難避免互斥。那么我們應(yīng)該怎么做呢？ Herlihy提出了設(shè)計(jì)各種無(wú)等待（wait-free）數(shù)據(jù)結(jié)構(gòu)的思想[H91]。想法很簡(jiǎn)單：通過(guò)強(qiáng)大的硬件指令，我們可以構(gòu)造出不需要鎖的數(shù)據(jù)結(jié)構(gòu)。舉個(gè)簡(jiǎn)單的例子，假設(shè)我們有比較并交換（compare-and-swap）指令，是一種由硬件提供的原子指令，做下面的事：

1????int?CompareAndSwap(int?*address,?int?expected,?int?new)?{ 2??????if?(*address?==?expected)?{ 3????????*address?=?new; 4????????return?1;?//?success 5??????} 6??????return?0;???//?failure 7????}

假定我們想原子地給某個(gè)值增加特定的數(shù)量。我們可以這樣實(shí)現(xiàn)：

1????void?AtomicIncrement(int?*value,?int?amount)?{ 2??????do?{ 3????????int?old?=?*value; 4??????}?while?(CompareAndSwap(value,?old,?old?+?amount)?==?0); 5????}

無(wú)須獲取鎖，更新值，然后釋放鎖這些操作，我們使用比較并交換指令，反復(fù)嘗試將值更新到新的值。這種方式?jīng)]有使用鎖，因此不會(huì)有死鎖（有可能產(chǎn)生活鎖）。 我們來(lái)考慮一個(gè)更復(fù)雜的例子：鏈表插入。這是在鏈表頭部插入元素的代碼：

1????void?insert(int?value)?{ 2??????node_t?*n?=?malloc(sizeof(node_t)); 3??????assert(n?!=?NULL); 4??????n->value?=?value; 5??????n->next?=?head; 6??????head?????=?n; 7????}

這段代碼在多線程同時(shí)調(diào)用的時(shí)候，會(huì)有臨界區(qū)（看看你是否能弄清楚原因）。當(dāng)然，我們可以通過(guò)給相關(guān)代碼加鎖，來(lái)解決這個(gè)問(wèn)題：

1????void?insert(int?value)?{ 2??????node_t?*n?=?malloc(sizeof(node_t)); 3??????assert(n?!=?NULL); 4??????n->value?=?value; 5??????lock(listlock);????//?begin?critical?section 6??????n->next?=?head; 7??????head????=?n; 8??????unlock(listlock);?//?end?of?critical?section 9????}

上面的方案中，我們使用了傳統(tǒng)的鎖^[2]。這里我們嘗試用比較并交換指令（compare-and-swap)來(lái)實(shí)現(xiàn)插入操作。一種可能的實(shí)現(xiàn)是：

1????void?insert(int?value)?{ 2??????node_t?*n?=?malloc(sizeof(node_t)); 3??????assert(n?!=?NULL); 4??????n->value?=?value; 5??????do?{ 6????????n->next?=?head; 7??????}?while?(CompareAndSwap(&head,?n->next,?n)?==?0); 8????}

文章轉(zhuǎn)自異步社區(qū)

任務(wù)調(diào)度 開(kāi)發(fā)者

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。