[[388911]]

一、前言

在 Linux 系統中，當多個線程并行執行時，如果需要訪問同一個資源，那么在訪問資源的地方，需要使用操作系統為我們提供的同步原語來進行保護。同步原語包括：互斥鎖、條件變量、信號量等，被保護的代碼稱作“臨界區”。

這是非常正規的流程，我們基本上也都是這么做的。

那有沒有想過，這些同步原語對代碼的執行效率會產生多大的影響?是否可以不使用操作系統提供的這些機制，而是用其它純軟件的方法也能達到保護臨界區的目的呢?

這篇文章我們介紹一下 Peterson(皮特森)算法，也許實用性不強，但是可以給我們帶來一些思考，提高我們的編程元技能。

二、Peterson 算法簡介

這個算法主要用來解決臨界區的保護問題。我們知道，一個臨界區必須保證 3 個條件：

1. 互斥訪問: 在任意一個時刻，最多只能有一個線程可以進入臨界區;
2. 空閑讓進：當沒有線程正在執行臨界區的代碼時，必須在所有申請進入臨界區的線程中，選擇其中的一個，讓它進入臨界區;
3. 有限等待：當一個線程申請進去臨界區時，不能無限的等待，必須在有限的時間內獲得許可進入臨界區。也就是說，不論其優先級多低，不應該餓死在該臨界區入口處。

Peterson算法是一個實現互斥鎖的并發程序設計算法，可以控制兩個線程訪問一個共享的用戶資源而不發生訪問沖突。

Peterson 算法是基于雙線程互斥訪問的 LockOne 與 LockTwo 算法而來。

1. LockOne 算法使用一個 flag 布爾數組來實現互斥;
2. LockTwo 使用一個 turn 的整型量來實現互斥;

這 2 個算法都實現了互斥，但是都存在死鎖的可能。Peterson 算法把這兩種算法結合起來，完美地用軟件實現了雙線程互斥問題。

算法說明如下

兩個重要的全局變量：

1. flag 數組：有 2 個布爾元素，分別代表一個線程是否申請進入臨界區;

2. turn：如果 2 個線程都申請進入臨界區，這個變量將會決定讓哪一個線程進入臨界區;

三、測試代碼

// 被 2 個線程同時訪問的全局資源 
static int num = 0;  
 
BOOL flag[2] = { 0 }; 
int turn = 0; 
 
void *thread0_routine(void *arg) 
{ 
    for (int i = 0; i < 1000000; ++i) 
    { 
        flag[0] = TRUE; 
        turn = 1; 
        while (TRUE == flag[1] && 1 == turn); 
 
        // 臨階區代碼 
        num++;  
         
        flag[0] = FALSE; 
    } 
     
    return NULL; 
} 
 
void *thread1_routine(void *arg) 
{ 
    for (int i = 0; i < 1000000; ++i) 
    { 
        flag[1] = TRUE; 
        turn = 0; 
        while (TRUE == flag[0] && 0 == turn); 
 
        // 臨階區代碼 
        num++; 
         
        flag[1] = FALSE; 
    } 
 
    return NULL; 
} 

全局資源 num 的初始值為 0 ，兩個編程分別遞增 100 萬次，因此最終結果應該是 200 萬，實際測試結果也確實如此。

四、Mutex 互斥鎖對代碼執行效率的影響

1. 單線程中：Mutex 互斥鎖對代碼執行效率的影響

for (int i = 0; i < 1000000; ++i) 
{ 
    num++; 
} 

以上代碼，耗時約：1.8ms -- 3.5ms。

for (int i = 0; i < 1000000; ++i) 
{ 
    pthread_mutex_lock(&mutex); 
    num++; 
    pthread_mutex_unlock(&mutex); 
} 

以上代碼，耗時約：23.9ms -- 38.9ms。可以看出，上鎖和解鎖對代碼執行效率的影響還是很明顯的。

2. 多線程中：Mutex 互斥鎖對代碼執行效率的影響

void *thread0_routine(void *arg) 
{ 
    for (int i = 0; i < 1000000; ++i) 
    { 
        pthread_mutex_lock(&mutex); 
        num++; 
        pthread_mutex_unlock(&mutex); 
    } 
     
    return NULL; 
} 
 
void *thread1_routine(void *arg) 
{ 
    for (int i = 0; i < 1000000; ++i) 
    { 
        pthread_mutex_lock(&mutex); 
        num++; 
        pthread_mutex_unlock(&mutex); 
    } 
 
    return NULL; 
} 

耗時：

• thread0: diff = 125.8ms
• thread1: diff = 129.1ms

3. 在兩個線程中，使用 Peterson 算法來保護臨界區

耗時：

• thread1: diff = 1.89ms
• thread0: diff = 1.94ms

五、總結

Peterson 算法使用純軟件來保護臨界區，比使用操作系統提供的互斥鎖表現出了更好的性能。

但是它也有一個缺點：只能使用在 2 個線程中，但是由于它與平臺無關，在某些特殊的場合，也許能夠拿來為我們所用!