一、前言

二、Peterson 算法簡(jiǎn)介

三、測(cè)試代碼

四、Mutex 互斥鎖對(duì)代碼執(zhí)行效率的影響

五、總結(jié)

一、前言

在 Linux 系統(tǒng)中,當(dāng)多個(gè)線程并行執(zhí)行時(shí),如果需要訪問同一個(gè)資源,那么在訪問資源的地方,需要使用操作系統(tǒng)為我們提供的同步原語來進(jìn)行保護(hù)。同步原語包括:互斥鎖、條件變量、信號(hào)量等,被保護(hù)的代碼稱作“臨界區(qū)”。

這是非常正規(guī)的流程,我們基本上也都是這么做的。

那有沒有想過,這些同步原語對(duì)代碼的執(zhí)行效率會(huì)產(chǎn)生多大的影響?是否可以不使用操作系統(tǒng)提供的這些機(jī)制,而是用其它純軟件的方法也能達(dá)到保護(hù)臨界區(qū)的目的呢?

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

二、Peterson 算法簡(jiǎn)介

這個(gè)算法主要用來解決臨界區(qū)的保護(hù)問題。我們知道,一個(gè)臨界區(qū)必須保證 3 個(gè)條件:

互斥訪問: 在任意一個(gè)時(shí)刻,最多只能有一個(gè)線程可以進(jìn)入臨界區(qū);空閑讓進(jìn):當(dāng)沒有線程正在執(zhí)行臨界區(qū)的代碼時(shí),必須在所有申請(qǐng)進(jìn)入臨界區(qū)的線程中,選擇其中的一個(gè),讓它進(jìn)入臨界區(qū);有限等待:當(dāng)一個(gè)線程申請(qǐng)進(jìn)去臨界區(qū)時(shí),不能無限的等待,必須在有限的時(shí)間內(nèi)獲得許可進(jìn)入臨界區(qū)。也就是說,不論其優(yōu)先級(jí)多低,不應(yīng)該餓死在該臨界區(qū)入口處。

Peterson算法是一個(gè)實(shí)現(xiàn)互斥鎖的并發(fā)程序設(shè)計(jì)算法,可以控制兩個(gè)線程訪問一個(gè)共享的用戶資源而不發(fā)生訪問沖突。

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

LockOne 算法使用一個(gè) flag 布爾數(shù)組來實(shí)現(xiàn)互斥;  LockTwo 使用一個(gè) turn 的整型量來實(shí)現(xiàn)互斥;  

這 2 個(gè)算法都實(shí)現(xiàn)了互斥,但是都存在死鎖的可能。Peterson 算法把這兩種算法結(jié)合起來,完美地用軟件實(shí)現(xiàn)了雙線程互斥問題。

算法說明如下

兩個(gè)重要的全局變量:

1． flag 數(shù)組:有 2 個(gè)布爾元素,分別代表一個(gè)線程是否申請(qǐng)進(jìn)入臨界區(qū);

2． turn:如果 2 個(gè)線程都申請(qǐng)進(jìn)入臨界區(qū),這個(gè)變量將會(huì)決定讓哪一個(gè)線程進(jìn)入臨界區(qū);

三、測(cè)試代碼 // 被 2 個(gè)線程同時(shí)訪問的全局資源
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);
       // 臨階區(qū)代碼
       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);
       // 臨階區(qū)代碼
       num++;
       flag[1] = FALSE;
   }
   return NULL;
}

全局資源 num 的初始值為 0 ,兩個(gè)編程分別遞增 100 萬次,因此最終結(jié)果應(yīng)該是 200 萬,實(shí)際測(cè)試結(jié)果也確實(shí)如此。

四、Mutex 互斥鎖對(duì)代碼執(zhí)行效率的影響 

1． 單線程中:Mutex 互斥鎖對(duì)代碼執(zhí)行效率的影響for (int i = 0; i < 1000000; ++i)
{
   num++;
}

以上代碼,耗時(shí)約:1．8ms -- 3．5ms。

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

以上代碼,耗時(shí)約:23．9ms -- 38．9ms�？梢钥闯�,上鎖和解鎖對(duì)代碼執(zhí)行效率的影響還是很明顯的。

2． 多線程中:Mutex 互斥鎖對(duì)代碼執(zhí)行效率的影響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;
}

耗時(shí):

thread0: diff = 125．8ms
thread1: diff = 129．1ms

3． 在兩個(gè)線程中,使用 Peterson 算法來保護(hù)臨界區(qū)

耗時(shí):

thread1: diff = 1．89ms
thread0: diff = 1．94ms

五、總結(jié)

Peterson 算法使用純軟件來保護(hù)臨界區(qū),比使用操作系統(tǒng)提供的互斥鎖表現(xiàn)出了更好的性能。

但是它也有一個(gè)缺點(diǎn):只能使用在 2 個(gè)線程中,但是由于它與平臺(tái)無關(guān),在某些特殊的場(chǎng)合,也許能夠拿來為我們所用!