互斥算法基礎

互斥是個現代編程經常需要解決的問題，但實際上，不少人是基于編程API中的鎖API來理解互斥的，也有不少人是僅僅學習了操作系統教程中的形式邏輯的內容，對互斥實際要面對的問題沒有體會，本文嘗試把這個邏輯梳理出來。

互斥解決的問題是讓一組操作串行化。解決串行化的基礎方法是線程，線程是一個串行化執行系列的抽象。

這里的線程和串行化都是抽象的概念。所謂線程，可以是OS中創建的線程，進程，中斷處理向量，也可以是另一個CPU，IMU，MCU中的線程，啟動程序等等。

而所謂線程的串行化，也是從目的上來的，比如你寫：

a=3;

b=4;

編譯器，CPU，都可能認為這兩者的先后順序不影響你的結果，所以，執行上， 它們的執行不一定是有先后關系的。就算編譯器按正確的順序發出這兩條指令，這還要看總線（包括Cache）系統的認知，這兩個操作，作用到Cache和內存中的順序也是沒有保證的。

編譯器，CPU，總線系統間，有很多額外的協議來保證你所需的串行化可以得到保證。比如memory barrior指令，編譯器優化禁止等等。

所以，如果你僅僅寫一般算法，認為線程是完全串行化是沒有問題的。但如果你對串行化有非常specific的要求，你就必須理解CPU的這些行為，保證它是真正串行的。

當串行化的要求出現在多個線程上，這個問題就變得更復雜了。我們通常用mutex鎖來實現兩個線程內部操作的互斥。但我們必須清楚，mutex鎖的行為是基于線程的實現的。pthread_mutex_t能提供的互斥是基于pthread_t的，不是pthread_t的線程使用pthread_mutex_t并不能正常工作。

同理，spin_lock_t是基于SMP系統的，不能用于CPU和MCU的互斥。RCU是基于Linux Kernel的調度模型的，并不能用于AMP不同異構系統之間互斥。這種問題是顯而易見的，所有的串行化，不過是基于內存訪問的部分原子操作，重試，中斷這樣的行為實現的，這些設計都是一種對線程實現的依賴，如果鎖算法不依賴線程的實現，CPU調度，總線系統優化都無法做了。

這樣就意味著，如果你要實現一個CPU和MCU之間的互斥算法，你就必須從CPU語義開始設計，而不能基于高級語言開始設計。

我們設想CPU和MCU共享內存和總線系統，它們要互斥訪問一組全局變量。然后我們使用spinlock類似的算法，如果spinlock=1，CPU可以訪問，如果spinlock=0，MCU可以訪問。

CPU的代碼這樣寫：

if(spinlock)  {
  a=read_global_data("a");
  b=read_global_data("b");
  spinlock=0;
}

MCU的代碼這樣寫：

if(!spinlock) {
  write_global_data("a", 1);
  write_global_data("b", 2);
  spinlock=1;
}

好了，這個算法的要求就來了，首先，你要保證得了read/write_global_data()和spinlock的先后順序。這里需要增加memory barrior。mb如何加法，這需要根據流程進行設計。

第二個要求是CPU一側的代碼必須是單線程的，否則如果兩個CPU線程同時更新spinlock，你就需要加兩個CPU間互斥的算法

其他，根據你增加的其他行為，都要進行更新的。

說到底，你要做一個獨立的互斥算法，沒有庫支持，你要做設計，而不是直接用一個變量就說設計zuo'wan

來自：https://zhuanlan.zhihu.com/p/25534698