# OS synchronization
###### tags: `Linux 探討`
同步問題陳述:
critical section (以下簡稱 CS): 提供對共享變數之存取的互斥控制，從而確保資料正確。


所謂Critical sections意指一小塊『用來處理一份被共享之資源』的程式碼,廣義地指一塊記憶體、一個資料結構、一個檔案，或是任何其他具有『使用之排他性』的東西。也就是說，『資源』每一次（同一時間）只能夠被一個執行緒處理。

CS 解法:

1. Mutual exclusion (互斥)：任一時間點，只允許一個 process/thread 進入規範的 CS 內活動。
1. Progress (有進展): 需要同時滿足下面要件：
* 不想進入 CS 的 process/thread 不得阻礙其它 process/thread 進入 CS，也就是說，不得參與進入 CS 的決策過程;
* 必須在有限的時間從想進入 CS 的 process/thread 中，挑選其中一個 process/thread 進入 critical section，一有有空位就讓想進 CS 者即刻進入;
1. Bound waiting (有限的等待): 自 process/thread 提出進入 CS 的申請到獲准進入 CS 的等待時間是有限的。即若有 n 個 processes/thread 想進入，則任一 process/thread 至多等待 n - 1 次即可進入。

因此發展需多同步的機制像是:
atomic operations, semaphore, mutex ,rw_semaphore, spinlock, rwlock, RCU，以及seqlock

## Semaphore
提供兩個"Atomic" Operation : wait(S) 與 signal(s)定義如下:
* wait(s) : while(s<=0) do no-op; s=s-1
* signal(s) : s=s+1


1. Recursive Deadlock 可能在 Recursive 又 callback到自己產生Deadlock

1. 假設有幾個Task 互等對方資源，一個Task在上鎖之後進入CS之後，不知啥原因造成segmentation fault，其他在等資源的人可能就拿不到資源，形成Deadlock

## MUTEX
1. MUTEX 可以當成 0-1 semaphore
1. MUTEX 有下列特色
* The principle of ownership-只有上鎖的人可以解鎖
* 當MUTEX沒有所有者即失效
* 可以支援優先權繼承
* 可以資源或者不支援巢狀鎖定
* 可以資源自適應索
當最High Task 想執行cs時，發現cs已被low Task佔住，在這個時間點low task 的優先權就會繼承高的優先權，直到做完cs才回歸原本的優先權。

在科技公司的面試過程中，答覆 [Mutex, Semaphore, the difference, and Linux kernel](https://blog.louie.lu/2016/10/22/mutex-semaphore-the-difference-and-linux-kernel/)

1. 比較 Linux 和 stm32 FreeRTOS 的code 有甚麼差別?
1. 為什麼 FreeRTOS 沒有實作 heap?
1. MUTEX 用在驅動上什麼地方?
1. 工作都沒Semaphore 都用MUTEX?
1. Semaphore 和 MUTEX 差別?
1. MUTEX 和 spinlock 差別?