[[389259]]

• 一、前言
• 二、Micha Hofri 算法
• 三、測試代碼
• 四、總結(jié)

一、前言

在上一篇文章中，介紹了一種純軟件算法，用來實(shí)現(xiàn)臨界區(qū)的保護(hù)功能，文章鏈接: C語言邊角料2：用純軟件來代替Mutex互斥鎖。

首先明確一下：如果利用操作系統(tǒng)提供的互斥鎖可以實(shí)現(xiàn)我需要的功能，我肯定使用互斥鎖，之所以介紹 Peterson 這個(gè)算法，主要是因?yàn)樗容^有意思，很小巧，可以為我們帶來一些“規(guī)范的”編程之外的一些想法。

后臺(tái)也有一些小伙伴對這個(gè)算法發(fā)表了一些留言，只要有想法都非常好，就怕不去想。

其中有位朋友提到，這個(gè)算法只能用在 2 個(gè)線程中，是否有其他的類似算法，可以用在多線程中?

晚上下班后，我就花了點(diǎn)時(shí)間找到下面的這個(gè)算法，分享一下!

二、Micha Hofri 算法

這個(gè)算法我沒有找到名字，暫且以作者的名字來稱呼這個(gè)算法吧!

算法截圖：

從算法的主體代碼看，Hofri 算法主要是擴(kuò)展了 Peterson 算法，都是使用 2 個(gè)全局變量數(shù)組來控制哪個(gè)線程可以進(jìn)入臨界區(qū)。

這個(gè)算法的論證比較復(fù)雜，都是一些數(shù)學(xué)方面的證明，文章在這里：Proof of a Mutual Exclusion Algorithm-- A `Class'ic Example， 1989 年發(fā)表，感興趣的小伙伴可以自行去燒腦研究。

三、測試代碼

// 線程操作的資源 
static int num = 0; 
 
// 創(chuàng)建 10 個(gè)線程 
#define THREAD_NUM      10 
 
// 這 2 個(gè)全局變量控制算法 
int flag[THREAD_NUM] = {0 }; 
int turn[THREAD_NUM - 1] = {0}; 
 
// 這是線程函數(shù) 
void *thread_routine(void *arg) 
{ 
    int index = *(int *)arg; 
 
    for (int i = 0; i < 10000; ++i) // 線程循環(huán)次數(shù) 
    { 
        for (int j = 1; j < THREAD_NUM - 1; j++)  
        { 
            flag[index] = j; 
            turn[j] = index; 
    L: 
            for (int k = 1; k < THREAD_NUM; ++k) 
            { 
                if (k == index) continue; 
                if ((flag[k] >= j) && turn[j] == index) 
                    goto L; 
            } 
 
        } 
 
        flag[index] = THREAD_NUM; 
         
        // 關(guān)鍵代碼段 
        num++; 
         
        flag[index] = 0; 
    } 
    return NULL; 
} 
 
void test() 
{ 
    // 用來傳遞線程的索引 
    int index[THREAD_NUM] = {0}; 
     
    創(chuàng)建多個(gè)線程，執(zhí)行同一個(gè)函數(shù) 
    pthread_t t[THREAD_NUM]; 
    for (int i = 0; i < THREAD_NUM; ++i) 
    { 
        index[i] = i; 
        pthread_create(&t[i], NULL, thread_routine, &index[i]); 
    } 
} 

編譯、執(zhí)行，所有線程執(zhí)行結(jié)束后，共享資源 num 變量可以得到正確的結(jié)果。

四、總結(jié)

還是重復(fù)一下文章開頭說的話，這里的算法僅僅是說明它可以完成保護(hù)臨界區(qū)的功能，但是在實(shí)際項(xiàng)目中，真心不建議這么來用，畢竟代碼的可維護(hù)性是非常重要的!

本文轉(zhuǎn)載自微信公眾號(hào)「IOT物聯(lián)網(wǎng)小鎮(zhèn)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系IOT物聯(lián)網(wǎng)小鎮(zhèn)公眾號(hào)。