[[389259]]

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

一、前言

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

首先明確一下：如果利用操作系統提供的互斥鎖可以實現我需要的功能，我肯定使用互斥鎖，之所以介紹 Peterson 這個算法，主要是因為它比較有意思，很小巧，可以為我們帶來一些“規范的”編程之外的一些想法。

后臺也有一些小伙伴對這個算法發表了一些留言，只要有想法都非常好，就怕不去想。

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

晚上下班后，我就花了點時間找到下面的這個算法，分享一下!

二、Micha Hofri 算法

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

算法截圖：

從算法的主體代碼看，Hofri 算法主要是擴展了 Peterson 算法，都是使用 2 個全局變量數組來控制哪個線程可以進入臨界區。

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

三、測試代碼

// 線程操作的資源 
static int num = 0; 
 
// 創建 10 個線程 
#define THREAD_NUM      10 
 
// 這 2 個全局變量控制算法 
int flag[THREAD_NUM] = {0 }; 
int turn[THREAD_NUM - 1] = {0}; 
 
// 這是線程函數 
void *thread_routine(void *arg) 
{ 
    int index = *(int *)arg; 
 
    for (int i = 0; i < 10000; ++i) // 線程循環次數 
    { 
        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; 
         
        // 關鍵代碼段 
        num++; 
         
        flag[index] = 0; 
    } 
    return NULL; 
} 
 
void test() 
{ 
    // 用來傳遞線程的索引 
    int index[THREAD_NUM] = {0}; 
     
    創建多個線程，執行同一個函數 
    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]); 
    } 
} 

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

四、總結

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

本文轉載自微信公眾號「IOT物聯網小鎮」，可以通過以下二維碼關注。轉載本文請聯系IOT物聯網小鎮公眾號。