---
# System prepended metadata

title: Semaphore
tags: [OS]

---

<style>
H2{color:#BF0060 !important;}
H3{color:#009393 !important;}
p{color:Black !important;}
li strong {color:#4682b4 !important;}
</style>

# Semaphore
## **How to use** 
### **Binary Semaphore**
* **用法**
    * `sem_t s;`
    `sem_init(&s, 0, 1);`
    `sem_wait(&s);`
    `// criticle section`
    `sem_post(&s);`
* **trace**
    * T1 
        * 初始 s=1，wait 使s=0，繼續執行critical
    * T2
        * wait 使s=-1 ( -x , x 為等候者數)，進入 sleep
    * T1
        * critical 做完 post 使 s=0，wake T2
    * T2
        * wait return 後執行 critical，完成後 call post 使 s=1
* **Producer/Consumer**
    * <img src="https://i.imgur.com/5OUI7rV.png" width = "600"/></img>
* **Reader/Writer**
    * `Allow 1 writer and multiple reader`
        * <img src="https://i.imgur.com/HFpYobv.png" width = "250"/></img>

        * <img src="https://i.imgur.com/d60RJAb.png" width = "400"/></img>

* **Dining-Philosophers**
    * `Represent chopsticks by semaphore[idx]`
    * `所有人拿左等右 --> hold and wait --> deadlock`
        `wait(chopstick[i]);`
        `wait(chopstick[i＋1]);`
    * `解法`
        * 最多 n-1 人吃
        * pick only if both sides are available
        * asymmetric solution : 奇選左 偶選右 
* **Thread Throttling**
    * `限制 concurrent thread 數`
    * `初始 s = the max_num of threads`
    * `5->4->3->2->1->0，第六個進來時卡住`
        * sem_wait(&s)
        ...
        sem_post(&s)
## **How to implement** 
* <img src="https://i.imgur.com/ISilFUU.png" width = "550"/></img>

###### tags: `OS`