• 一、前言

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

• 三、測(cè)試代碼

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

• 五、總結(jié)

一、前言

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

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

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

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

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

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

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

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

Peterson 算法是基于雙線程互斥訪問(wèn)的 LockOne 與 LockTwo 算法而來(lái)。

1. LockOne 算法使用一個(gè) flag 布爾數(shù)組來(lái)實(shí)現(xiàn)互斥；??
2. LockTwo 使用一個(gè) turn 的整型量來(lái)實(shí)現(xiàn)互斥；??

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

算法說(shuō)明如下

兩個(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í)訪問(wèn)的全局資源
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]