OS同步機制
背景
Cooperating process(合作行程)指的是這個porcess會受到其他人影響，這一類的process因為互相合作，所以常常會碰(共享)同一個記憶體的資料，這個記憶體區端稱作critical section，其他不會共享的記憶體區段稱作remainder section。
這時候就會有同步的問題，例如一個process正在改寫資料，另外一個process也開始改寫資料，這時候就會出問題，我們稱作 race condition problem，所以OS提供了多個機制解決這類的問題。
平行化的程式很容易遇到這樣的問題，這邊的平行是指不同的process 同時 run在不同core上，並且我們對於平行化程式的正確性定義為，他的結果因該要跟只用一個process run出來的結果一樣，我們稱作正確。
critical section problem
以此延伸的同步問題稱作critical section problem，其中大概對於解法的想像為，設定權限，一次只能讓一個人進去，因此在進去的時候都要請求權限，這邊會有code實現，叫做enrty section，而對應的離開critical section，需要exit section來實作放開權限，整體架構圖如下。
並且，critical section problem要求解法必須有三個特性
- mutual exclusion ， critical section一次只能有一個人進入
- progress，如果cs沒process ， 其他process不能阻擋任意process進入critical section
- bounded waiting，一個人想進入cs，他總有一天能進去，絕對不可能不進去(因為process數量是固定的)，因此不允許插隊的行為發生，並且不可能永遠有人佔用cs
實際可能在os發生race condition的地方包括，當有多個kernel process對file存取，或者多個process同時fork，或者在memory allocation and interrupt handling的情況(詳細請看恐龍書)。
單一核心可以在修改cs時禁止interrupt來避免race condition，但在多核心禁止interrupt是代價很大的，因此衍生兩種kernel類型。preemptive kernel and nonpreemptive kernel。Preemptive and Non-Preemptive Scheduling
Software-based solution-Peterson’s solution(Spinlock實作此演算法)
需要load跟store動作都是atomic，也就是一次性的動作，這需要仰賴cpu硬體的實作，如下
- memory barriers，確保load/store operation執行之前，所有的operation都已經完成了。
- atomically instruction，在不同solution有用到不同的動作，像是load/store/test_and_set…等動作，都要是一次性(atomically)的。
- atomic variable
Linux的Futex就是peterson's solution的實作。
Mutex/Semaphore
其他同步解法，這兩個解法與spinlock為，spinlock使用for迴圈一直等待鎖，而mutex/semaphore則是使用讓等待的process睡著(需要context switch的成本)，所以當等待時間較長，比較適合使用mutex/semaphore。
兩者的差別如下Mutex 與 Semaphore 最大的差異是，基本上恐龍書說01semaphore = mutex。
Linux的adaptive mutex 會自動幫你選擇要哪個鎖。
參考資料: Shiwu Lo: 以Linux為基礎的作業系統概論，第二版、恐龍書(OS concept)
