在并行程序中，鎖的使用會主要會引發(fā)兩類難題：一類是諸如死鎖、活鎖等引起的多線程Bug；另一類是由鎖競爭引起的性能瓶頸。本文將介紹并行編程中因為鎖引發(fā)的這兩類難題及其解決方案。

1. 用鎖來防止數(shù)據(jù)競跑

在進行并行編程時，我們常常需要使用鎖來保護共享變量，以防止多個線程同時對該變量進行更新時產(chǎn)生數(shù)據(jù)競跑（Data Race）。所謂數(shù)據(jù)競跑，是指當(dāng)兩個（或多個）線程同時對某個共享變量進行操作，且這些操作中至少有一個是寫操作時所造成的程序錯誤。例1中的兩個線程可能同時執(zhí)行“counter++”從而產(chǎn)生數(shù)據(jù)競跑，造成counter最終值為1（而不是正確值2）。
例1：

01 02 03 04 05 06 07 08 09 10 11 12 13 14

#include <pthread.h> int?counter = 0; void?*func(void?*params) { ????counter++;?//數(shù)據(jù)競跑 } void?main() { ????pthread_t thread1, thread2; ????pthread_create(&thread1, 0, func, 0); ????pthread_create(&thread2, 0, func, 0); ????pthread_join(thread1, 0 ); ????pthread_join(thread2, 0 ); }

這是因為counter++本身是由三條匯編指令構(gòu)成的（從主存中將counter的值讀到寄存器中；對寄存器進行加1操作；將寄存器中的新值寫回主存），所以例1中的兩個線程可能按如下交錯順序執(zhí)行，導(dǎo)致counter的最終值為1：
例2：

01 02 03 04 05 06

load [%counter], rax;?// 線程1從counter讀取0到寄存器rax add rax, 1;?// 線程1對寄存器rax進行加1 load [%counter], rbx;?// 線程2從counter讀取0到寄存器rbx store rax [%counter];?// 線程1把1寫入counter的主存地址 add rbx, 1;?// 線程2對寄存器rbx進行加1 store rbx, [%counter];?// 線程2把1寫入counter的主存地址

為了防止例1中的數(shù)據(jù)競跑現(xiàn)象，我們可以使用鎖來保證每個線程對counter++操作的獨占訪問（即保證該操作是原子的）。在例3的程序中，我們使用mutex鎖將counter++操作放入臨界區(qū)中，這樣同一時刻只有獲取鎖的線程能訪問該臨界區(qū)，保證了counter++的原子性：即只有在線程1執(zhí)行完counter++的三條指令之后線程2才能執(zhí)行counter++操作，保證了counter的最終值必定為2。
例3：

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19

#include <pthread.h> int?counter = 0; pthread_mutex_t mutex; void?*func(void?*params) { ????pthread_mutex_lock(&mutex); ????counter++;?//處于臨界區(qū)，不會產(chǎn)生數(shù)據(jù)競跑 ????pthread_mutex_unlock(&mutex); } void?main() { ????pthread_t thread1, thread2; ????pthread_mutex_init(&mutex); ????pthread_create(&thread1, 0, func, 0); ????pthread_create(&thread2, 0, func, 0); ????pthread_join(thread1, 0 ); ????pthread_join(thread2, 0 ); ????pthread_mutex_destroy(&mutex); }

2. 死鎖和活鎖

然而，鎖的使用非常容易導(dǎo)致多線程Bug，最常見的莫過于死鎖和活鎖。從原理上講，死鎖的產(chǎn)生是由于兩個（或多個）線程在試圖獲取正被其他線程占有的資源時造成的線程停滯。在下例中，假設(shè)線程1在獲取mutex_a鎖之后正在嘗試獲取mutex_b鎖，而線程2此時已經(jīng)獲取了mutex_b鎖并正在嘗試獲取mutex_a鎖，兩個線程就會因為獲取不到自己想要的資源、且自己正占有著對方想要的資源而停滯，從而產(chǎn)生死鎖。
例4：

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19

// 線程 1 void?func1() { ????LOCK(&mutex_a); ????LOCK(&mutex_b);//線程1停滯在此 ????counter++; ????UNLOCK(&mutex_b); ????UNLOCK(&mutex_a); }?????????????????????? // 線程 2 void?func2() { ????LOCK(&mutex_b); ????LOCK(&mutex_a);//線程2停滯在此 ????counter++; ????UNLOCK(&mutex_a); ????UNLOCK(&mutex_b); }

例4中的死鎖其實是最簡單的情形，在實際的程序中，死鎖往往發(fā)生在復(fù)雜的函數(shù)調(diào)用過程中。在下面這個例子中，線程1在func1()中獲取了mutex_a鎖，之后調(diào)用func_call1()并在其函數(shù)體中嘗試獲取mutex_b鎖；與此同時線程2在func2()中獲取了mutex_b鎖之后再在func_call2()中嘗試獲取mutex_a鎖從而造成死鎖。可以想象，隨著程序復(fù)雜度的增加，想要正確的檢測出死鎖會變得越來越困難。
例5：

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// 線程 1 void?func1() { LOCK(&mutex_a); ... func_call1(); UNLOCK(&mutex_a); }?????????????????????? func_call1() { ???LOCK(&mutex_b); ???... ???UNLOCK(&mutex_b); ???... }?????????????????????? // 線程 2 void?func2() { ????LOCK(&mutex_b); ????... ????func_call2() ????UNLOCK(&mutex_b); } func_call2() { ????LOCK(&mutex_a); ????... ????UNLOCK(&mutex_b); ????... }

其實避免死鎖的方法非常簡單，其基本原則就是保證各個線程加鎖操作的執(zhí)行順序是全局一致的。例如，如果上例中的線程1和線程2都是先對mutex_a加鎖再對mutex_b進行加鎖就不會產(chǎn)生死鎖了。在實際的軟件開發(fā)中，除了嚴(yán)格遵守相同加鎖順序的原則防止死鎖之外，我們還可以使用RAII（Resource Acquisition Is Initialization，即“資源獲取即初始化”）的手段來封裝加鎖解鎖操作，從而幫助減少死鎖的發(fā)生[1]。

除死鎖外，多個線程的加鎖、解鎖操作還可能造成活鎖。在下例中，程序員為了防止死鎖的產(chǎn)生而做了如下處理：當(dāng)線程1在獲取了mutex_a鎖之后再嘗試獲取mutex_b時，線程1通過調(diào)用一個非阻塞的加鎖操作（類似pthread_mutex_trylock）來嘗試進行獲得mutex_b：如果線程1成功獲得mutex_b，則trylock()加鎖成功并返回true，如果失敗則返回false。線程2也使用了類似的方法來保證不會出現(xiàn)死鎖。不幸的是，這種方法雖然防止了死鎖的產(chǎn)生，卻可能造成活鎖。例如，在線程1獲得mutex_a鎖之后嘗試獲取mutex_b失敗，則線程1會釋放mutex_a并進入下一次while循環(huán)；如果此時線程2在線程1進行TRYLOCK(&mutex_b)的同時執(zhí)行TRYLOCK(&mutex_a)，那么線程2也會獲取mutex_a失敗，并接著釋放mutex_b及進入下一次while循環(huán)；如此反復(fù)，兩個線程都可能在較長時間內(nèi)不停的進行“獲得一把鎖、嘗試獲取另一把鎖失敗、再解鎖之前已獲得的鎖“的循環(huán)，從而產(chǎn)生活鎖現(xiàn)象。當(dāng)然，在實際情況中，因為多個線程之間調(diào)度的不確定性，最終必定會有一個線程能同時獲得兩個鎖，從而結(jié)束活鎖。盡管如此，活鎖現(xiàn)象確實會產(chǎn)生不必要的性能延遲，所以需要大家格外注意。
例6：

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

// 線程 1 void?func1() { ????int?done = 0; ????while(!done) { ????????LOCK(&mutex_a); ????????if?(TRYLOCK(&mutex_b)) { ????????????counter++; ????????????UNLOCK(&mutex_b); ????????????UNLOCK(&mutex_a); ????????????done = 1; ????????} ????????else?{ ????????????UNLOCK(&mutex_a); ????????} ????} }?????????????????????? // 線程 2 void?func2() { ????int?done = 0; ????while(!done) { ????????LOCK(&mutex_b); ????????if?(TRYLOCK(&mutex_a)) { ????????????counter++; ????????????UNLOCK(&mutex_a); ????????????UNLOCK(&mutex_b); ????????????done = 1; ????????} ????????else?{ ????????????UNLOCK(&mutex_b); ????????} ????} }

3. 鎖競爭性能瓶頸

在多線程程序中鎖競爭是最主要的性能瓶頸之一。在前面我們也提到過，通過使用鎖來保護共享變量能防止數(shù)據(jù)競跑，保證同一時刻只能有一個線程訪問該臨界區(qū)。但是我們也注意到，正是因為鎖造成的對臨界區(qū)的串行執(zhí)行導(dǎo)致了并行程序的性能瓶頸。

3.1阿姆達爾法則（Amdahl’s Law）

在介紹鎖競爭引起的性能瓶頸之前，讓我們先來了解一下阿姆達爾法則。我們知道，一個并行程序是由兩部分組成的：串行執(zhí)行的部分和可以并行執(zhí)行的部分。假設(shè)串行部分的執(zhí)行時間為S，可并行執(zhí)行部分的執(zhí)行時間為P，則整個并行程序使用單線程（單核）串行執(zhí)行的時間為S+P。阿姆達爾法則規(guī)定，可并行執(zhí)行部分的執(zhí)行時間與線程數(shù)目成反比：即如果有N個線程（N核CPU）并行執(zhí)行這個可并行的部分，則該部分的執(zhí)行時間為P/N。由此我們可以得到并行程序總體執(zhí)行時間的公式：

01	總體執(zhí)行時間T = S + P/N

根據(jù)這個公式，我們可以得到一些非常有意思的結(jié)論。例如，如果一個程序全部代碼都可以被并行執(zhí)行，那么它的加速比會非常好，即隨著線程數(shù)（CPU核數(shù)）的增多該程序的加速比會線性遞增。換句話說，如果單線程執(zhí)行該程序需要16秒鐘，用16個線程執(zhí)行該程序就只需要1秒鐘。
然而，如果這個程序只有80%的代碼可以被并行執(zhí)行，它的加速比卻會急劇下降。根據(jù)阿姆達爾法則，如果用16個線程并行執(zhí)行次程序可并行的部分，該程序的總體執(zhí)行時間T = S + P/N = (16*0.2) + (16*0.8)/16 = 4秒，這比完全并行化的情況（只需1秒）足足慢了4倍！實際上，如果該程序只有50%的代碼可以被并行執(zhí)行，在使用16個線程時該程序的執(zhí)行時間仍然需要8.5秒！
從阿姆達爾法則我們可以看到，并行程序的性能很大程度上被只能串行執(zhí)行的部分給限制住了，而由鎖競爭引起的串行執(zhí)行正是造成串行性能瓶頸的主要原因之一。

3.2鎖競爭的常用解決辦法

3.2.1 避免使用鎖

為了提高程序的并行性，最好的辦法自然是不使用鎖。從設(shè)計角度上來講，鎖的使用無非是為了保護共享資源。如果我們可以避免使用共享資源的話那自然就避免了鎖競爭造成的性能損失。幸運的是，在很多情況下我們都可以通過資源復(fù)制的方法讓每個線程都擁有一份該資源的副本，從而避免資源的共享。如果有需要的話，我們也可以讓每個線程先訪問自己的資源副本，只在程序的后講各個線程的資源副本合并成一個共享資源。例如，如果我們需要在多線程程序中使用計數(shù)器，那么我們可以讓每個線程先維護一個自己的計數(shù)器，只在程序的最后將各個計數(shù)器兩兩歸并（類比二叉樹），從而最大程度提高并行度，減少鎖競爭。

3.2.2 使用讀寫鎖

如果對共享資源的訪問多數(shù)為讀操作，少數(shù)為寫操作，而且寫操作的時間非常短，我們就可以考慮使用讀寫鎖來減少鎖競爭。讀寫鎖的基本原則是同一時刻多個讀線程可以同時擁有讀者鎖并進行讀操作；另一方面，同一時刻只有一個寫進程可以擁有寫者鎖并進行寫操作。讀者鎖和寫者鎖各自維護一份等待隊列。當(dāng)擁有寫者鎖的寫進程釋放寫者鎖時，所有正處于讀者鎖等待隊列里的讀線程全部被喚醒并被授予讀者鎖以進行讀操作；當(dāng)這些讀線程完成讀操作并釋放讀者鎖時，寫者鎖中的第一個寫進程被喚醒并被授予寫者鎖以進行寫操作，如此反復(fù)。換句話說，多個讀線程和一個寫線程將交替擁有讀寫鎖以完成相應(yīng)操作。這里需要額外補充的一點是鎖的公平調(diào)度問題。例如，如果在寫者鎖等待隊列中有一個或多個寫線程正在等待獲得寫者鎖時，新加入的讀線程會被放入讀者鎖的等待隊列。這是因為，盡管這個新加入的讀線程能與正在進行讀操作的那些讀線程并發(fā)讀取共享資源，但是也不能賦予他們讀權(quán)限，這樣就防止了寫線程被新到來的讀線程無休止的阻塞。
需要注意的是，并不是所有的場合讀寫鎖都具備更好的性能，大家應(yīng)該根據(jù)Profling的測試結(jié)果來判斷使用讀寫鎖是否能真的提高性能，特別是要注意寫操作雖然很少但很耗時的情況。

3.2.3 保護數(shù)據(jù)而不是操作

在實際程序中，有不少程序員在使用鎖時圖方便而把一些不必要的操作放在臨界區(qū)中。例如，如果需要對一個共享數(shù)據(jù)結(jié)構(gòu)進行刪除和銷毀操作，我們只需要把刪除操作放在臨界區(qū)中即可，資源銷毀操作完全可以在臨界區(qū)之外單獨進行，以此增加并行度。
正是因為臨界區(qū)的執(zhí)行時間大大影響了并行程序的整體性能，我們必須盡量少在臨界區(qū)中做耗時的操作，例如函數(shù)調(diào)用，數(shù)據(jù)查詢，I/O操作等。簡而言之，我們需要保護的只是那些共享資源，而不是對這些共享資源的操作，盡可能的把對共享資源的操作放到臨界區(qū)之外執(zhí)行有助于減少鎖競爭帶來的性能損失。

3.2.4 盡量使用輕量級的原子操作

在例3中，我們使用了mutex鎖來保護counter++操作。實際上，counter++操作完全可以使用更輕量級的原子操作來實現(xiàn)，根本不需要使用mutex鎖這樣相對較昂貴的機制來實現(xiàn)。在今年程序員第四期的《volatile與多線程的那些事兒》中我們就有對Java和C/C++中的原子操作做過相應(yīng)的介紹。

3.2.5 粗粒度鎖與細粒度鎖

為了減少串行部分的執(zhí)行時間，我們可以通過把單個鎖拆成多個鎖的辦法來較小臨界區(qū)的執(zhí)行時間，從而降低鎖競爭的性能損耗，即把“粗粒度鎖”轉(zhuǎn)換成“細粒度鎖”。但是，細粒度鎖并不一定更好。這是因為粗粒度鎖編程簡單，不易出現(xiàn)死鎖等Bug，而細粒度鎖編程復(fù)雜，容易出錯；而且鎖的使用是有開銷的（例如一個加鎖操作一般需要100個CPU時鐘周期），使用多個細粒度的鎖無疑會增加加鎖解鎖操作的開銷。在實際編程中，我們往往需要從編程復(fù)雜度、性能等多個方面來權(quán)衡自己的設(shè)計方案。事實上，在計算機系統(tǒng)設(shè)計領(lǐng)域，沒有哪種設(shè)計是沒有缺點的，只有仔細權(quán)衡不同方案的利弊才能得到最適合自己當(dāng)前需求的解決辦法。例如，Linux內(nèi)核在初期使用了Big Kernel Lock（粗粒度鎖）來實現(xiàn)并行化。從性能上來講，使用一個大鎖把所有操作都保護起來無疑帶來了很大的性能損失，但是它卻極大的簡化了并行整個內(nèi)核的難度。當(dāng)然，隨著Linux內(nèi)核的發(fā)展，Big Kernel Lock已經(jīng)逐漸消失并被細粒度鎖而取代，以取得更好的性能。

3.2.6 使用無鎖算法、數(shù)據(jù)結(jié)構(gòu)

首先要強調(diào)的是，筆者并不推薦大家自己去實現(xiàn)無鎖算法。為什么別去造無鎖算法的輪子呢？因為高性能無鎖算法的正確實現(xiàn)實在是太難了。有多難呢？Doug Lea提到j(luò)ava.util.concurrent庫中一個Non Blocking的算法的實現(xiàn)大概需要1個人年，總共約500行代碼。事實上，我推薦大家直接去使用一些并行庫中已經(jīng)實現(xiàn)好了的無鎖算法、無鎖數(shù)據(jù)結(jié)構(gòu)，以提高并行程序的性能。典型的無鎖算法的庫有java.util.concurrent，Intel TBB等，它們都提供了諸如Non-blocking concurrent queue之類的數(shù)據(jù)結(jié)構(gòu)以供使用。

參考

[1] 陳碩.多線程服務(wù)器的常用編程模型.?
[2] Darryl Gove.?Multicore Application Programming
[3] 并行實驗室.?多線程隊列的算法優(yōu)化.

?

參看?http://www.parallellabs.com/2011/10/02/lock-in-parallel-programming/

from:?http://blog.csdn.net/cyh_24/article/details/7924822

總結(jié)

以上是生活随笔為你收集整理的并行编程中的“锁”难题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。