C++ 并行編程中的“鎖”難題
掃描二維碼
隨時(shí)隨地手機(jī)看文章
在并行程序中，鎖的使用會(huì)主要會(huì)引發(fā)兩類難題：一類是諸如死鎖、活鎖等引起的多線程Bug；另一類是由鎖競(jìng)爭(zhēng)引起的性能瓶頸。本文將介紹并行編程中因?yàn)殒i引發(fā)的這兩類難題及其解決方案。
1、用鎖來防止數(shù)據(jù)競(jìng)跑
在進(jìn)行并行編程時(shí)，我們常常需要使用鎖來保護(hù)共享變量，以防止多個(gè)線程同時(shí)對(duì)該變量進(jìn)行更新時(shí)產(chǎn)生數(shù)據(jù)競(jìng)跑（Data Race）。所謂數(shù)據(jù)競(jìng)跑，是指當(dāng)兩個(gè)（或多個(gè)）線程同時(shí)對(duì)某個(gè)共享變量進(jìn)行操作，且這些操作中至少有一個(gè)是寫操作時(shí)所造成的程序錯(cuò)誤。例1中的兩個(gè)線程可能同時(shí)執(zhí)行“counter++”從而產(chǎn)生數(shù)據(jù)競(jìng)跑，造成counter最終值為1（而不是正確值2）。
例1：
#includeint counter = 0; void *func(void *params) { counter++; //數(shù)據(jù)競(jìng)跑 } 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 ); }
這是因?yàn)閏ounter++本身是由三條匯編指令構(gòu)成的（從主存中將counter的值讀到寄存器中；對(duì)寄存器進(jìn)行加1操作；將寄存器中的新值寫回主存），所以例1中的兩個(gè)線程可能按如下交錯(cuò)順序執(zhí)行，導(dǎo)致counter的最終值為1：
例2：
load [%counter], rax; // 線程1從counter讀取0到寄存器rax add rax, 1; // 線程1對(duì)寄存器rax進(jìn)行加1 load [%counter], rbx; // 線程2從counter讀取0到寄存器rbx store rax [%counter]; // 線程1把1寫入counter的主存地址 add rbx, 1; // 線程2對(duì)寄存器rbx進(jìn)行加1 store rbx, [%counter]; // 線程2把1寫入counter的主存地址
為了防止例1中的數(shù)據(jù)競(jìng)跑現(xiàn)象，我們可以使用鎖來保證每個(gè)線程對(duì)counter++操作的獨(dú)占訪問（即保證該操作是原子的）。在例3的程序中，我們使用mutex鎖將counter++操作放入臨界區(qū)中，這樣同一時(shí)刻只有獲取鎖的線程能訪問該臨界區(qū)，保證了counter++的原子性：即只有在線程1執(zhí)行完counter++的三條指令之后線程2才能執(zhí)行counter++操作，保證了counter的最終值必定為2。
例3：
#includeint counter = 0; pthread_mutex_t mutex; void *func(void *params) { pthread_mutex_lock(&mutex); counter++; //處于臨界區(qū)，不會(huì)產(chǎn)生數(shù)據(jù)競(jìng)跑 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)生是由于兩個(gè)（或多個(gè)）線程在試圖獲取正被其他線程占有的資源時(shí)造成的線程停滯。在下例中，假設(shè)線程1在獲取mutex_a鎖之后正在嘗試獲取mutex_b鎖，而線程2此時(shí)已經(jīng)獲取了mutex_b鎖并正在嘗試獲取mutex_a鎖，兩個(gè)線程就會(huì)因?yàn)楂@取不到自己想要的資源、且自己正占有著對(duì)方想要的資源而停滯，從而產(chǎn)生死鎖。
例4：
// 線程 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中的死鎖其實(shí)是最簡(jiǎn)單的情形，在實(shí)際的程序中，死鎖往往發(fā)生在復(fù)雜的函數(shù)調(diào)用過程中。在下面這個(gè)例子中，線程1在func1()中獲取了mutex_a鎖，之后調(diào)用func_call1()并在其函數(shù)體中嘗試獲取mutex_b鎖；與此同時(shí)線程2在func2()中獲取了mutex_b鎖之后再在func_call2()中嘗試獲取mutex_a鎖從而造成死鎖?？梢韵胂螅S著程序復(fù)雜度的增加，想要正確的檢測(cè)出死鎖會(huì)變得越來越困難。
例5：
// 線程 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); ... }
其實(shí)避免死鎖的方法非常簡(jiǎn)單，其基本原則就是保證各個(gè)線程加鎖操作的執(zhí)行順序是全局一致的。例如，如果上例中的線程1和線程2都是先對(duì)mutex_a加鎖再對(duì)mutex_b進(jìn)行加鎖就不會(huì)產(chǎn)生死鎖了。在實(shí)際的軟件開發(fā)中，除了嚴(yán)格遵守相同加鎖順序的原則防止死鎖之外，我們還可以使用RAII（Resource Acquisition Is Initialization，即“資源獲取即初始化”）的手段來封裝加鎖解鎖操作，從而幫助減少死鎖的發(fā)生[1]。
除死鎖外，多個(gè)線程的加鎖、解鎖操作還可能造成活鎖。在下例中，程序員為了防止死鎖的產(chǎn)生而做了如下處理：當(dāng)線程1在獲取了mutex_a鎖之后再嘗試獲取mutex_b時(shí)，線程1通過調(diào)用一個(gè)非阻塞的加鎖操作（類似pthread_mutex_trylock）來嘗試進(jìn)行獲得mutex_b：如果線程1成功獲得mutex_b，則trylock()加鎖成功并返回true，如果失敗則返回false。線程2也使用了類似的方法來保證不會(huì)出現(xiàn)死鎖。不幸的是，這種方法雖然防止了死鎖的產(chǎn)生，卻可能造成活鎖。
例如，在線程1獲得mutex_a鎖之后嘗試獲取mutex_b失敗，則線程1會(huì)釋放mutex_a并進(jìn)入下一次while循環(huán)；如果此時(shí)線程2在線程1進(jìn)行TRYLOCK(&mutex_b)的同時(shí)執(zhí)行TRYLOCK(&mutex_a)，那么線程2也會(huì)獲取mutex_a失敗，并接著釋放mutex_b及進(jìn)入下一次while循環(huán)；如此反復(fù)，兩個(gè)線程都可能在較長(zhǎng)時(shí)間內(nèi)不停的進(jìn)行“獲得一把鎖、嘗試獲取另一把鎖失敗、再解鎖之前已獲得的鎖“的循環(huán)，從而產(chǎn)生活鎖現(xiàn)象。當(dāng)然，在實(shí)際情況中，因?yàn)槎鄠€(gè)線程之間調(diào)度的不確定性，最終必定會(huì)有一個(gè)線程能同時(shí)獲得兩個(gè)鎖，從而結(jié)束活鎖。盡管如此，活鎖現(xiàn)象確實(shí)會(huì)產(chǎn)生不必要的性能延遲，所以需要大家格外注意。
例6：
// 線程 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. 鎖競(jìng)爭(zhēng)性能瓶頸
在多線程程序中鎖競(jìng)爭(zhēng)是最主要的性能瓶頸之一。在前面我們也提到過，通過使用鎖來保護(hù)共享變量能防止數(shù)據(jù)競(jìng)跑，保證同一時(shí)刻只能有一個(gè)線程訪問該臨界區(qū)。但是我們也注意到，正是因?yàn)殒i造成的對(duì)臨界區(qū)的串行執(zhí)行導(dǎo)致了并行程序的性能瓶頸。
3.1阿姆達(dá)爾法則（Amdahl’s Law）
在介紹鎖競(jìng)爭(zhēng)引起的性能瓶頸之前，讓我們先來了解一下阿姆達(dá)爾法則。我們知道，一個(gè)并行程序是由兩部分組成的：串行執(zhí)行的部分和可以并行執(zhí)行的部分。假設(shè)串行部分的執(zhí)行時(shí)間為S，可并行執(zhí)行部分的執(zhí)行時(shí)間為P，則整個(gè)并行程序使用單線程（單核）串行執(zhí)行的時(shí)間為S+P。阿姆達(dá)爾法則規(guī)定，可并行執(zhí)行部分的執(zhí)行時(shí)間與線程數(shù)目成反比：即如果有N個(gè)線程（N核CPU）并行執(zhí)行這個(gè)可并行的部分，則該部分的執(zhí)行時(shí)間為P/N。由此我們可以得到并行程序總體執(zhí)行時(shí)間的公式：
總體執(zhí)行時(shí)間 T = S + P/N
根據(jù)這個(gè)公式，我們可以得到一些非常有意思的結(jié)論。例如，如果一個(gè)程序全部代碼都可以被并行執(zhí)行，那么它的加速比會(huì)非常好，即隨著線程數(shù)（CPU核數(shù)）的增多該程序的加速比會(huì)線性遞增。換句話說，如果單線程執(zhí)行該程序需要16秒鐘，用16個(gè)線程執(zhí)行該程序就只需要1秒鐘。
然而，如果這個(gè)程序只有80%的代碼可以被并行執(zhí)行，它的加速比卻會(huì)急劇下降。根據(jù)阿姆達(dá)爾法則，如果用16個(gè)線程并行執(zhí)行次程序可并行的部分，該程序的總體執(zhí)行時(shí)間T = S + P/N = (160.2) + (160.8)/16 = 4秒，這比完全并行化的情況（只需1秒）足足慢了4倍！實(shí)際上，如果該程序只有50%的代碼可以被并行執(zhí)行，在使用16個(gè)線程時(shí)該程序的執(zhí)行時(shí)間仍然需要8.5秒！
從阿姆達(dá)爾法則我們可以看到，并行程序的性能很大程度上被只能串行執(zhí)行的部分給限制住了，而由鎖競(jìng)爭(zhēng)引起的串行執(zhí)行正是造成串行性能瓶頸的主要原因之一。
3.2鎖競(jìng)爭(zhēng)的常用解決辦法
3.2.1 避免使用鎖
為了提高程序的并行性，最好的辦法自然是不使用鎖。從設(shè)計(jì)角度上來講，鎖的使用無非是為了保護(hù)共享資源。如果我們可以避免使用共享資源的話那自然就避免了鎖競(jìng)爭(zhēng)造成的性能損失。幸運(yùn)的是，在很多情況下我們都可以通過資源復(fù)制的方法讓每個(gè)線程都擁有一份該資源的副本，從而避免資源的共享。如果有需要的話，我們也可以讓每個(gè)線程先訪問自己的資源副本，只在程序的后講各個(gè)線程的資源副本合并成一個(gè)共享資源。例如，如果我們需要在多線程程序中使用計(jì)數(shù)器，那么我們可以讓每個(gè)線程先維護(hù)一個(gè)自己的計(jì)數(shù)器，只在程序的最后將各個(gè)計(jì)數(shù)器兩兩歸并（類比二叉樹），從而最大程度提高并行度，減少鎖競(jìng)爭(zhēng)。
3.2.2 使用讀寫鎖
如果對(duì)共享資源的訪問多數(shù)為讀操作，少數(shù)為寫操作，而且寫操作的時(shí)間非常短，我們就可以考慮使用讀寫鎖來減少鎖競(jìng)爭(zhēng)。讀寫鎖的基本原則是同一時(shí)刻多個(gè)讀線程可以同時(shí)擁有讀者鎖并進(jìn)行讀操作；另一方面，同一時(shí)刻只有一個(gè)寫進(jìn)程可以擁有寫者鎖并進(jìn)行寫操作。讀者鎖和寫者鎖各自維護(hù)一份等待隊(duì)列。當(dāng)擁有寫者鎖的寫進(jìn)程釋放寫者鎖時(shí)，所有正處于讀者鎖等待隊(duì)列里的讀線程全部被喚醒并被授予讀者鎖以進(jìn)行讀操作；當(dāng)這些讀線程完成讀操作并釋放讀者鎖時(shí)，寫者鎖中的第一個(gè)寫進(jìn)程被喚醒并被授予寫者鎖以進(jìn)行寫操作，如此反復(fù)。
換句話說，多個(gè)讀線程和一個(gè)寫線程將交替擁有讀寫鎖以完成相應(yīng)操作。這里需要額外補(bǔ)充的一點(diǎn)是鎖的公平調(diào)度問題。例如，如果在寫者鎖等待隊(duì)列中有一個(gè)或多個(gè)寫線程正在等待獲得寫者鎖時(shí)，新加入的讀線程會(huì)被放入讀者鎖的等待隊(duì)列。這是因?yàn)?，盡管這個(gè)新加入的讀線程能與正在進(jìn)行讀操作的那些讀線程并發(fā)讀取共享資源，但是也不能賦予他們讀權(quán)限，這樣就防止了寫線程被新到來的讀線程無休止的阻塞。
需要注意的是，并不是所有的場(chǎng)合讀寫鎖都具備更好的性能，大家應(yīng)該根據(jù)Profling的測(cè)試結(jié)果來判斷使用讀寫鎖是否能真的提高性能，特別是要注意寫操作雖然很少但很耗時(shí)的情況。
3.2.3 保護(hù)數(shù)據(jù)而不是操作
在實(shí)際程序中，有不少程序員在使用鎖時(shí)圖方便而把一些不必要的操作放在臨界區(qū)中。例如，如果需要對(duì)一個(gè)共享數(shù)據(jù)結(jié)構(gòu)進(jìn)行刪除和銷毀操作，我們只需要把刪除操作放在臨界區(qū)中即可，資源銷毀操作完全可以在臨界區(qū)之外單獨(dú)進(jìn)行，以此增加并行度。正是因?yàn)榕R界區(qū)的執(zhí)行時(shí)間大大影響了并行程序的整體性能，我們必須盡量少在臨界區(qū)中做耗時(shí)的操作，例如函數(shù)調(diào)用，數(shù)據(jù)查詢，I/O操作等。簡(jiǎn)而言之，我們需要保護(hù)的只是那些共享資源，而不是對(duì)這些共享資源的操作，盡可能的把對(duì)共享資源的操作放到臨界區(qū)之外執(zhí)行有助于減少鎖競(jìng)爭(zhēng)帶來的性能損失。
3.2.4 盡量使用輕量級(jí)的原子操作
在例3中，我們使用了mutex鎖來保護(hù)counter++操作。實(shí)際上，counter++操作完全可以使用更輕量級(jí)的原子操作來實(shí)現(xiàn)，根本不需要使用mutex鎖這樣相對(duì)較昂貴的機(jī)制來實(shí)現(xiàn)。在今年程序員第四期的《volatile與多線程的那些事兒》中我們就有對(duì)Java和C/C++中的原子操作做過相應(yīng)的介紹。
3.2.5 粗粒度鎖與細(xì)粒度鎖
為了減少串行部分的執(zhí)行時(shí)間，我們可以通過把單個(gè)鎖拆成多個(gè)鎖的辦法來較小臨界區(qū)的執(zhí)行時(shí)間，從而降低鎖競(jìng)爭(zhēng)的性能損耗，即把“粗粒度鎖”轉(zhuǎn)換成“細(xì)粒度鎖”。但是，細(xì)粒度鎖并不一定更好。這是因?yàn)榇至６孺i編程簡(jiǎn)單，不易出現(xiàn)死鎖等Bug，而細(xì)粒度鎖編程復(fù)雜，容易出錯(cuò)；而且鎖的使用是有開銷的（例如一個(gè)加鎖操作一般需要100個(gè)CPU時(shí)鐘周期），使用多個(gè)細(xì)粒度的鎖無疑會(huì)增加加鎖解鎖操作的開銷。在實(shí)際編程中，我們往往需要從編程復(fù)雜度、性能等多個(gè)方面來權(quán)衡自己的設(shè)計(jì)方案。
事實(shí)上，在計(jì)算機(jī)系統(tǒng)設(shè)計(jì)領(lǐng)域，沒有哪種設(shè)計(jì)是沒有缺點(diǎn)的，只有仔細(xì)權(quán)衡不同方案的利弊才能得到最適合自己當(dāng)前需求的解決辦法。例如，Linux內(nèi)核在初期使用了Big Kernel Lock（粗粒度鎖）來實(shí)現(xiàn)并行化。從性能上來講，使用一個(gè)大鎖把所有操作都保護(hù)起來無疑帶來了很大的性能損失，但是它卻極大的簡(jiǎn)化了并行整個(gè)內(nèi)核的難度。當(dāng)然，隨著Linux內(nèi)核的發(fā)展，Big Kernel Lock已經(jīng)逐漸消失并被細(xì)粒度鎖而取代，以取得更好的性能。
3.2.6 使用無鎖算法、數(shù)據(jù)結(jié)構(gòu)
首先要強(qiáng)調(diào)的是，筆者并不推薦大家自己去實(shí)現(xiàn)無鎖算法。為什么別去造無鎖算法的輪子呢？因?yàn)楦咝阅軣o鎖算法的正確實(shí)現(xiàn)實(shí)在是太難了。有多難呢? Doug Lea 提到j(luò)ava.util.concurrent庫中一個(gè)Non Blocking的算法的實(shí)現(xiàn)大概需要1個(gè)人年，總共約500行代碼。事實(shí)上，我推薦大家直接去使用一些并行庫中已經(jīng)實(shí)現(xiàn)好了的無鎖算法、無鎖數(shù)據(jù)結(jié)構(gòu)，以提高并行程序的性能。典型的無鎖算法的庫有java.util.concurrent，Intel TBB等，它們都提供了諸如Non-blocking concurrent queue之類的數(shù)據(jù)結(jié)構(gòu)以供使用。
下載文檔
