在並行程式中，鎖的使用會主要會引發兩類難題：一類是諸如死鎖、活鎖等引起的多執行緒Bug；另一類是由鎖競爭引起的效能瓶頸。本文將介紹並行程式設計中因為鎖引發的這兩類難題及其解決方案。

1、用鎖來防止資料競跑

在進行並行程式設計時，我們常常需要使用鎖來保護共享變數，以防止多個執行緒同時對該變數進行更新時產生資料競跑（Data Race）。所謂資料競跑，是指當兩個（或多個）執行緒同時對某個共享變數進行操作，且這些操作中至少有一個是寫操作時所造成的程式錯誤。例1中的兩個執行緒可能同時執行“counter++”從而產生資料競跑，造成counter最終值為1（而不是正確值2）。

例1：

#include <pthread.h>int counter = 0;void *func(void *params){    counter++; //資料競跑}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++本身是由三條彙編指令構成的（從主存中將counter的值讀到暫存器中；對暫存器進行加1操作；將暫存器中的新值寫回主存），所以例1中的兩個執行緒可能按如下交錯順序執行，導致counter的最終值為1：

例2：

load [%counter], rax; // 執行緒1從counter讀取0到暫存器raxadd rax, 1; // 執行緒1對暫存器rax進行加1load [%counter], rbx; // 執行緒2從counter讀取0到暫存器rbxstore rax [%counter]; // 執行緒1把1寫入counter的主存地址add rbx, 1; // 執行緒2對暫存器rbx進行加1store rbx, [%counter]; // 執行緒2把1寫入counter的主存地址

為了防止例1中的資料競跑現象，我們可以使用鎖來保證每個執行緒對counter++操作的獨佔訪問（即保證該操作是原子的）。在例3的程式中，我們使用mutex鎖將counter++操作放入臨界區中，這樣同一時刻只有獲取鎖的執行緒能訪問該臨界區，保證了counter++的原子性：即只有在執行緒1執行完counter++的三條指令之後執行緒2才能執行counter++操作，保證了counter的最終值必定為2。

例3：

#include <pthread.h>int counter = 0;pthread_mutex_t mutex;void *func(void *params){    pthread_mutex_lock(&mutex);    counter++; //處於臨界區，不會產生資料競跑    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. 死鎖和活鎖

然而，鎖的使用非常容易導致多執行緒Bug，最常見的莫過於死鎖和活鎖。從原理上講，死鎖的產生是由於兩個（或多個）執行緒在試圖獲取正被其他執行緒佔有的資源時造成的執行緒停滯。在下例中，假設執行緒1在獲取mutex_a鎖之後正在嘗試獲取mutex_b鎖，而執行緒2此時已經獲取了mutex_b鎖並正在嘗試獲取mutex_a鎖，兩個執行緒就會因為獲取不到自己想要的資源、且自己正佔有著對方想要的資源而停滯，從而產生死鎖。

例4：

// 執行緒 1                     void func1()                    {                           LOCK(&mutex_a);                          LOCK(&mutex_b);//執行緒1停滯在此             counter++;                           UNLOCK(&mutex_b);                         UNLOCK(&mutex_a);                    }                        // 執行緒 2void func2(){    LOCK(&mutex_b);    LOCK(&mutex_a);//執行緒2停滯在此    counter++;    UNLOCK(&mutex_a);    UNLOCK(&mutex_b);}

例4中的死鎖其實是最簡單的情形，在實際的程式中，死鎖往往發生在複雜的函式呼叫過程中。在下面這個例子中，執行緒1在func1()中獲取了mutex_a鎖，之後呼叫func_call1()並在其函式體中嘗試獲取mutex_b鎖；與此同時執行緒2在func2()中獲取了mutex_b鎖之後再在func_call2()中嘗試獲取mutex_a鎖從而造成死鎖。可以想象，隨著程式複雜度的增加，想要正確的檢測出死鎖會變得越來越困難。

例5：

// 執行緒 1                     void func1()                    {                       LOCK(&mutex_a);                      ...                     func_call1();                UNLOCK(&mutex_a);                }                        func_call1()                    {                          LOCK(&mutex_b);                  ...                          UNLOCK(&mutex_b);                    ...                       }                        // 執行緒 2void func2(){    LOCK(&mutex_b);    ...    func_call2()    UNLOCK(&mutex_b);} func_call2(){    LOCK(&mutex_a);    ...    UNLOCK(&mutex_b);    ...}

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

除死鎖外，多個執行緒的加鎖、解鎖操作還可能造成活鎖。在下例中，程式設計師為了防止死鎖的產生而做了如下處理：當執行緒1在獲取了mutex_a鎖之後再嘗試獲取mutex_b時，執行緒1透過呼叫一個非阻塞的加鎖操作（類似pthread_mutex_trylock）來嘗試進行獲得mutex_b：如果執行緒1成功獲得mutex_b，則trylock()加鎖成功並返回true，如果失敗則返回false。執行緒2也使用了類似的方法來保證不會出現死鎖。不幸的是，這種方法雖然防止了死鎖的產生，卻可能造成活鎖。

例如，線上程1獲得mutex_a鎖之後嘗試獲取mutex_b失敗，則執行緒1會釋放mutex_a並進入下一次while迴圈；如果此時執行緒2線上程1進行TRYLOCK(&mutex_b)的同時執行TRYLOCK(&mutex_a)，那麼執行緒2也會獲取mutex_a失敗，並接著釋放mutex_b及進入下一次while迴圈；如此反覆，兩個執行緒都可能在較長時間內不停的進行“獲得一把鎖、嘗試獲取另一把鎖失敗、再解鎖之前已獲得的鎖“的迴圈，從而產生活鎖現象。當然，在實際情況中，因為多個執行緒之間排程的不確定性，最終必定會有一個執行緒能同時獲得兩個鎖，從而結束活鎖。儘管如此，活鎖現象確實會產生不必要的效能延遲，所以需要大家格外注意。

例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);                           }                              }                        }                        // 執行緒 2void 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);        }    }}

【文章福利】需要C/C++ Linux伺服器架構師學習資料加群812855908（資料包括C/C++，Linux，golang技術，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg等）

3. 鎖競爭效能瓶頸

在多執行緒程式中鎖競爭是最主要的效能瓶頸之一。在前面我們也提到過，透過使用鎖來保護共享變數能防止資料競跑，保證同一時刻只能有一個執行緒訪問該臨界區。但是我們也注意到，正是因為鎖造成的對臨界區的序列執行導致了並行程式的效能瓶頸。

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

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

總體執行時間 T = S + P/N

根據這個公式，我們可以得到一些非常有意思的結論。例如，如果一個程式全部程式碼都可以被並行執行，那麼它的加速比會非常好，即隨著執行緒數（CPU核數）的增多該程式的加速比會線性遞增。換句話說，如果單執行緒執行該程式需要16秒鐘，用16個執行緒執行該程式就只需要1秒鐘。

然而，如果這個程式只有80%的程式碼可以被並行執行，它的加速比卻會急劇下降。根據阿姆達爾法則，如果用16個執行緒並行執行此程式可並行的部分，該程式的總體執行時間T = S + P/N = (160.2) + (160.8)/16 = 4秒，這比完全並行化的情況（只需1秒）足足慢了4倍！實際上，如果該程式只有50%的程式碼可以被並行執行，在使用16個執行緒時該程式的執行時間仍然需要8.5秒！

從阿姆達爾法則我們可以看到，並行程式的效能很大程度上被只能序列執行的部分給限制住了，而由鎖競爭引起的序列執行正是造成序列效能瓶頸的主要原因之一。

3.2鎖競爭的常用解決辦法

3.2.1 避免使用鎖

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

3.2.2 使用讀寫鎖

如果對共享資源的訪問多數為讀操作，少數為寫操作，而且寫操作的時間非常短，我們就可以考慮使用讀寫鎖來減少鎖競爭。讀寫鎖的基本原則是同一時刻多個讀執行緒可以同時擁有讀者鎖並進行讀操作；另一方面，同一時刻只有一個寫程序可以擁有寫者鎖並進行寫操作。讀者鎖和寫者鎖各自維護一份等待佇列。當擁有寫者鎖的寫程序釋放寫者鎖時，所有正處於讀者鎖等待佇列裡的讀執行緒全部被喚醒並被授予讀者鎖以進行讀操作；當這些讀執行緒完成讀操作並釋放讀者鎖時，寫者鎖中的第一個寫程序被喚醒並被授予寫者鎖以進行寫操作，如此反覆。

換句話說，多個讀執行緒和一個寫執行緒將交替擁有讀寫鎖以完成相應操作。這裡需要額外補充的一點是鎖的公平排程問題。例如，如果在寫者鎖等待佇列中有一個或多個寫執行緒正在等待獲得寫者鎖時，新加入的讀執行緒會被放入讀者鎖的等待佇列。這是因為，儘管這個新加入的讀執行緒能與正在進行讀操作的那些讀執行緒併發讀取共享資源，但是也不能賦予他們讀許可權，這樣就防止了寫執行緒被新到來的讀執行緒無休止的阻塞。

需要注意的是，並不是所有的場合讀寫鎖都具備更好的效能，大家應該根據Profling的測試結果來判斷使用讀寫鎖是否能真的提高效能，特別是要注意寫操作雖然很少但很耗時的情況。

3.2.3 保護資料而不是操作

在實際程式中，有不少程式設計師在使用鎖時圖方便而把一些不必要的操作放在臨界區中。例如，如果需要對一個共享資料結構進行刪除和銷燬操作，我們只需要把刪除操作放在臨界區中即可，資源銷燬操作完全可以在臨界區之外單獨進行，以此增加並行度。正是因為臨界區的執行時間大大影響了並行程式的整體效能，我們必須儘量少在臨界區中做耗時的操作，例如函式呼叫，資料查詢，I/O操作等。簡而言之，我們需要保護的只是那些共享資源，而不是對這些共享資源的操作，儘可能的把對共享資源的操作放到臨界區之外執行有助於減少鎖競爭帶來的效能損失。

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

在例3中，我們使用了mutex鎖來保護counter++操作。實際上，counter++操作完全可以使用更輕量級的原子操作來實現，根本不需要使用mutex鎖這樣相對較昂貴的機制來實現。

3.2.5 粗粒度鎖與細粒度鎖

為了減少序列部分的執行時間，我們可以透過把單個鎖拆成多個鎖的辦法來較小臨界區的執行時間，從而降低鎖競爭的效能損耗，即把“粗粒度鎖”轉換成“細粒度鎖”。但是，細粒度鎖並不一定更好。這是因為粗粒度鎖程式設計簡單，不易出現死鎖等Bug，而細粒度鎖程式設計複雜，容易出錯；而且鎖的使用是有開銷的（例如一個加鎖操作一般需要100個CPU時鐘週期），使用多個細粒度的鎖無疑會增加加鎖解鎖操作的開銷。在實際程式設計中，我們往往需要從程式設計複雜度、效能等多個方面來權衡自己的設計方案。

事實上，在計算機系統設計領域，沒有哪種設計是沒有缺點的，只有仔細權衡不同方案的利弊才能得到最適合自己當前需求的解決辦法。例如，Linux核心在初期使用了Big Kernel Lock（粗粒度鎖）來實現並行化。從效能上來講，使用一個大鎖把所有操作都保護起來無疑帶來了很大的效能損失，但是它卻極大地簡化了並行整個核心的難度。當然，隨著Linux核心的發展，Big Kernel Lock已經逐漸消失並被細粒度鎖而取代，以取得更好的效能。

3.2.6 使用無鎖演算法、資料結構

首先要強調的是，筆者並不推薦大家自己去實現無鎖演算法。為什麼別去造無鎖演算法的輪子呢？因為高效能無鎖演算法的正確實現實在是太難了。事實上，我推薦大家直接去使用一些並行庫中已經實現好了的無鎖演算法、無鎖資料結構，以提高並行程式的效能。