# Synchronization Tools ## Mutex lock * a software tool * prevent race conditions * 試圖取得使用中的 lock 會被 block，直到 lock 被釋出 ## Spin lock * a software tool * prevent race conditions * 不斷在迴圈重複等待進入crical section * 缺點 : busy waiting * 這種需要 busy waiting 的 lock 也被稱作 spinlock * 浪費 CPU time(多個 process 分享單一 CPU) * 優點 * 在 wait 的時候不需要 context switch * lock 使用時間短的時候非常有效 * 常用在 multiprocessor system * one thread spin on one processor while another thread performs its critical section on another processor ## Semaphore ### Usage * 整數變數 * 只能透過兩個atomic operation : `wait()` `signal()` 存取 * 當有process在修改semaphore的值，不能有其他process同時修改同一個semaphore的值 * critical section problem ```C wait(S) { while(S <= 0); /* busy wait */ S--; } ``` ```C signal(S) { S++; } ``` * binary semaphore * 類似mutex lock * counting semaphore * control acess to a given resource * initalized to the number of resources available ### Implementation * 為了避免busy waiting * 當process執行`wait()`時發現semaphore的值為負的時候 * use `block()` to block itself * places process into a waiting queue * magnitude 代表等待 semaphore 的 process 數量 * 當其他process執行`signal()` * process is restarted by a `wakeup()` * 把 process 從 waiting state 變成 ready state 並放到 ready queue * 根據以上方法重新定義semaphore ``` C typedef struct { int value; struct process *list; } semaphore ``` ``` C wait(semaphore *S) { S -> value --; if(S->value ＜ 0) { add this process to S->list; block() } } ``` ``` C signal(semaphore *S) { S -> value ++; if(S->value <= 0) { remove a process P from S->list; wakeup(P); } } ``` * `block()` 和 `wakeup()` 都是system call * 在single processor環境 * 抑制中斷 * 在multiprocessor環境 * 每個processor都必須抑制中斷 * 嚴重影響效能 * SMP system必須提供另外的方法來確保`wait()`和`signal()` * `compare_and_swap()` or spinlocks * 這個定義並沒有完全消除busy waiting * 只是把它從 entry section 移到 critical section ### Deadlock and Starvation * S、Q都初始化為1 ![](https://i.imgur.com/D6Caqne.png) * 當P~0~執行wait(Q) * 必須等到P~1~執行signal(Q) * 當P~1~執行wait(S) * 必須等到P~0~執行signal(S) * 如果我們用LIFO的方法從semaphore的list移除process * 會造成Indefinite blocking(or starvation) ## Priority Inversion * kernel資料通常有lock保護 * 高優先權process需要的資源被低優先權的process佔著 * 假設有三個process: 優先權 L < M < H * L正在用H需要的資源R * H必須等到L結束 * 然而現在有個可執行的M * 它會插在L前先執行 * 間接影響了H的等待時間 * 解決辦法 * 限定只有兩種優先權 * priority-inheritance * 在用高優先權需要的資源的process會有高優先權 * 使用完畢後恢復原本的優先權 ## Monitor * A programming language construct * 結構 * 共享變數 * 程序 * 初始區 * 任何時間只有一個process可以在monitor中執行 * 允許process在monitor做等待，需要一個condition * 兩種運算: `wait()` `signal()` * 避免同時有兩個process執行 * 假設 P 執行 `x.signal()` 喚醒 Q * signal and wait * 讓最近被喚醒的process(Q)執行，另一個\(P\)等待直到他(Q)離開 * signal and continue * 讓最近被喚醒的process(Q)等待，直到另一個\(P\)離開 * Resuming processes * FCFS ordering * conditional-wait * `x.wait(c)` ， c 是一個 priority number * 當執行 `x.signal()` ，c 最小的process會被喚醒 --- ##### last edit > [name=dot] [time=Wed, Dec 25, 2019 5:32 PM] [HOME PAGE](/bKDZoNkrT9SOBnTvY_aj2Q) :lock: {%hackmd theme-dark %} ###### tags: `OS` `CSIE`