C語言中如何用純軟件來代替Mutex互斥鎖
一、前言
二、Peterson 算法簡介
三、測試代碼
四、Mutex 互斥鎖對代碼執(zhí)行效率的影響
五、總結(jié)
一、前言
在 Linux 系統(tǒng)中,當(dāng)多個線程并行執(zhí)行時,如果需要訪問同一個資源,那么在訪問資源的地方,需要使用操作系統(tǒng)為我們提供的同步原語來進行保護。同步原語包括:互斥鎖、條件變量、信號量等,被保護的代碼稱作“臨界區(qū)”。
這是非常正規(guī)的流程,我們基本上也都是這么做的。
那有沒有想過,這些同步原語對代碼的執(zhí)行效率會產(chǎn)生多大的影響?是否可以不使用操作系統(tǒng)提供的這些機制,而是用其它純軟件的方法也能達到保護臨界區(qū)的目的呢?
這篇文章我們介紹一下 Peterson(皮特森)算法,也許實用性不強,但是可以給我們帶來一些思考,提高我們的編程元技能。
二、Peterson 算法簡介
這個算法主要用來解決臨界區(qū)的保護問題。我們知道,一個臨界區(qū)必須保證 3 個條件:
互斥訪問: 在任意一個時刻,最多只能有一個線程可以進入臨界區(qū);空閑讓進:當(dāng)沒有線程正在執(zhí)行臨界區(qū)的代碼時,必須在所有申請進入臨界區(qū)的線程中,選擇其中的一個,讓它進入臨界區(qū);有限等待:當(dāng)一個線程申請進去臨界區(qū)時,不能無限的等待,必須在有限的時間內(nèi)獲得許可進入臨界區(qū)。也就是說,不論其優(yōu)先級多低,不應(yīng)該餓死在該臨界區(qū)入口處。
Peterson算法是一個實現(xiàn)互斥鎖的并發(fā)程序設(shè)計算法,可以控制兩個線程訪問一個共享的用戶資源而不發(fā)生訪問沖突。
Peterson 算法是基于雙線程互斥訪問的 LockOne 與 LockTwo 算法而來。
LockOne 算法使用一個 flag 布爾數(shù)組來實現(xiàn)互斥; LockTwo 使用一個 turn 的整型量來實現(xiàn)互斥;
這 2 個算法都實現(xiàn)了互斥,但是都存在死鎖的可能。Peterson 算法把這兩種算法結(jié)合起來,完美地用軟件實現(xiàn)了雙線程互斥問題。
算法說明如下
兩個重要的全局變量:
1. flag 數(shù)組:有 2 個布爾元素,分別代表一個線程是否申請進入臨界區(qū);
2. turn:如果 2 個線程都申請進入臨界區(qū),這個變量將會決定讓哪一個線程進入臨界區(qū);
三、測試代碼 // 被 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);
// 臨階區(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 ,兩個編程分別遞增 100 萬次,因此最終結(jié)果應(yīng)該是 200 萬,實際測試結(jié)果也確實如此。
四、Mutex 互斥鎖對代碼執(zhí)行效率的影響
1. 單線程中:Mutex 互斥鎖對代碼執(zhí)行效率的影響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。可以看出,上鎖和解鎖對代碼執(zhí)行效率的影響還是很明顯的。
2. 多線程中:Mutex 互斥鎖對代碼執(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;
}
耗時:
thread0: diff = 125.8ms
thread1: diff = 129.1ms
3. 在兩個線程中,使用 Peterson 算法來保護臨界區(qū)
耗時:
thread1: diff = 1.89ms
thread0: diff = 1.94ms
五、總結(jié)
Peterson 算法使用純軟件來保護臨界區(qū),比使用操作系統(tǒng)提供的互斥鎖表現(xiàn)出了更好的性能。
但是它也有一個缺點:只能使用在 2 個線程中,但是由于它與平臺無關(guān),在某些特殊的場合,也許能夠拿來為我們所用!
請輸入評論內(nèi)容...
請輸入評論/評論長度6~500個字
最新活動更多
-
即日-10.29立即報名>> 2024德州儀器嵌入式技術(shù)創(chuàng)新發(fā)展研討會
-
10月31日立即下載>> 【限時免費下載】TE暖通空調(diào)系統(tǒng)高效可靠的組件解決方案
-
即日-11.13立即報名>>> 【在線會議】多物理場仿真助跑新能源汽車
-
11月14日立即報名>> 2024工程師系列—工業(yè)電子技術(shù)在線會議
-
12月19日立即報名>> 【線下會議】OFweek 2024(第九屆)物聯(lián)網(wǎng)產(chǎn)業(yè)大會
-
即日-12.26火熱報名中>> OFweek2024中國智造CIO在線峰會
推薦專題
- 1 Intel宣布40年來最重大轉(zhuǎn)型:年底前裁員15000人、拋掉2/3房產(chǎn)
- 2 因美封殺TikTok,字節(jié)股價骨折!估值僅Meta1/5
- 3 宏山激光重磅發(fā)布行業(yè)解決方案,助力智能制造產(chǎn)業(yè)新飛躍
- 4 國產(chǎn)AI芯片公司破產(chǎn)!白菜價拍賣
- 5 具身智能火了,但規(guī)模落地還需時間
- 6 國產(chǎn)英偉達們,抓緊沖刺A股
- 7 三次錯失風(fēng)口!OpenAI前員工殺回AI編程賽道,老東家捧金相助
- 8 英特爾賦能智慧醫(yī)療,共創(chuàng)數(shù)字化未來
- 9 英偉達的麻煩在后頭?
- 10 將“網(wǎng)紅”變成“商品”,AI“爆改”實力拉滿
- 高級軟件工程師 廣東省/深圳市
- 自動化高級工程師 廣東省/深圳市
- 光器件研發(fā)工程師 福建省/福州市
- 銷售總監(jiān)(光器件) 北京市/海淀區(qū)
- 激光器高級銷售經(jīng)理 上海市/虹口區(qū)
- 光器件物理工程師 北京市/海淀區(qū)
- 激光研發(fā)工程師 北京市/昌平區(qū)
- 技術(shù)專家 廣東省/江門市
- 封裝工程師 北京市/海淀區(qū)
- 結(jié)構(gòu)工程師 廣東省/深圳市