2+線程的自寫互斥

我寫了下面的代碼，到目前爲止在我所有的測試中，似乎我已經爲我的4個線程編寫了一個可用的互斥鎖，但我希望得到其他人的意見我的解決方案的有效性。2+線程的自寫互斥

typedef struct Mutex{ 
    int turn; 
    int * waiting; 
    int num_processes; 
} Mutex; 

void enterLock(Mutex * lock, int id){ 
    int i; 
    for(i = 0; i < lock->num_processes; i++){ 
     lock->waiting[id] = 1; 
     if (i != id && lock->waiting[i]) 
      i = -1; 
     lock->waiting[id] = 0; 
    } 
    printf("ID %d Entered\n",id); 
} 

void leaveLock(Mutex * lock, int id){ 
    printf("ID %d Left\n",id); 
    lock->waiting[id] = 0; 
} 

void foo(Muted * lock, int id){ 
    enterLock(lock,id); 
    // do stuff now that i have access 
    leaveLock(lock,id); 
}

來源

2015-09-06 AndrewGrant

這段代碼是不完整的，但（或可怕的錯誤）.. Mutex.waiting從不指着某處定義。除此之外，試圖將自己的原子基元寫在非原子的東西上C提供的絕對是一個壞主意，它只是很多工作（但總是可行的）來證明它可能出錯的地方。 [關鍵就是找到一個隨機的線程切換最容易出問題的點] –

添加到我的評論...可靠的代碼，請改用'pthread_mutex_t' ...實現可能會有所不同，但你永遠也找不到依據的實現在「純粹」C上，因爲它總是需要一些原子基元。 –

據我所見，在線程A已經進入之後，線程A離開它之前，什麼都不能阻止線程B進入相同的互斥體。無論是鎖定還是解鎖，互斥鎖的狀態都是相同的。 – regular

這個問題我在你代碼中看到：

一個mutex背後的想法是提供相互排斥，是指當thread_a處於臨界區，thread_b必須等待（如果他想也要輸入）爲thread_a。

這個等待部分應該在enterLock函數中實現。但是你所擁有的是一個for循環，它可能在臨界區完成thread_a之前結束，因此thread_b也可以進入，因此你不能互相排斥。

辦法解決它：

在Peterson's algorithm看一看例如或德克爾的（more complicated），他們做了什麼有什麼所謂busy waiting這基本上是一個while環路說： while(i can't enter) { do nothing and wait...}

來源

2015-09-06 07:36:27 ThunderWiring

我很困惑，爲什麼你認爲我的for循環可能會在thread_a完成之前結束？生病編輯自己的帖子顯示在'以獲取更多信息 – AndrewGrant

（i = 0;我< lock-> num_processes;我++）'，'i'運行'num_processes'次，那麼'爲loop'到此爲止，但是，同時'thread_a'它不會被完成，它可以執行一個沉重的任務或somtheng – ThunderWiring

它運行無數次，直到一個迭代顯示每個鎖 - >等待[我]是錯誤的。您可能會錯過閱讀for循環 – AndrewGrant

在enterLock()返回後，Mutex對象的狀態與調用該函數之前的狀態相同。因此，即使在第一個線程釋放它呼叫leaveLock()之前，它也不會阻止第二個線程輸入相同的Mutex對象。沒有互斥性。

來源

2015-09-06 07:49:37 regular

我覺得不得不在這裏寫一個答案，因爲這個問題很好，考慮到它可以幫助其他人理解互斥的一般問題。在你的情況下，你走了很長的路要隱藏這個問題，但你無法避免它。它歸結爲：

01 /* pseudo-code */ 
02 if (! mutex.isLocked()) 
03  mutex.lock();

你總是期待線路02和03之間的線程切換。因此，有兩種線程發現mutex可能解鎖並在此之後中斷......只有稍後才能恢復並單獨鎖定此互斥鎖。您將有兩個線程同時進入關鍵部分。

因此，您確實需要實現可靠的互斥，這是一種原子操作，它可以測試一個條件，同時設置一個值，同時不會有任何中斷的機會。

01 /* pseudo-code */ 
02 while (! test_and_lock(mutex));

只要這個test_and_lock功能不能被打斷，你的代碼是安全的。直到c11，C沒有提供類似的東西，所以需要使用例如pthreads的實現。組裝或特殊的編譯器內部函數。有了c11，終於有了一種「標準」的方式來編寫這樣的原子操作，但我不能在這裏舉一個例子，因爲我沒有這方面的經驗。對於一般用途，pthreads圖書館會給你你需要的東西。

編輯：當然，這仍然是簡化的 - 在多處理器場景中，您需要確保偶數內存訪問是互斥的。

來源

2015-09-06 08:17:08

你完全忽略了內存模式的話題。除非您的計算機使用順序一致的內存模式（目前沒有任何PC CPU），否則您的代碼不正確，因爲任何由一個線程執行的存儲不一定對其他CPU立即可見。但是，這似乎是你的代碼中的一個假設。

底線：使用由操作系統或運行時庫這樣的POSIX或者Win32 API中提供的現有的同步原語，不自作聰明和自己實現。除非你有多年的並行編程經驗以及對CPU架構的深入瞭解，否則很可能會導致錯誤的實現。和調試並行programms的可能是地獄......

來源

2015-09-06 23:09:44 GloomY

無論機器的內存如何模型是：*編譯器*可能會重新排序內存訪問。 – EOF

2+線程的自寫互斥

回答

相關問題