並行程式的潛在問題(三)

# 並行程式的潛在問題(三) :::info - 🚀 更多文章都已經整合到 [AwesomeCS Wiki](https://github.com/ianchen0119/AwesomeCS/wiki) 了，歡迎送上 Star ! - 🚀 [AwesomeCS 臉書專業](https://www.facebook.com/AwesomeComputerScience/) ::: 在介紹 Mutex lock 與 spinlock 後，本篇文章同樣針對並行程式的 Synchronization 作探討，學習如何保證並行程式的執行順序並介紹什麼是 Deadlock 與 Livelock 。 ## Semaphore **Semaphore** 中文稱為號誌，是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值。當執行緒完成一次對該 semaphore 物件的等待（wait）時，該計數值減一；當執行緒完成一次對 semaphore 物件的釋放（release）時，計數值加一。當計數值為 0 ，則執行緒等待該 semaphore 物件不再能成功直至該 semaphore 物件變成 signaled 狀態。 semaphore 物件的計數值大於 0 ，為 signaled 狀態；計數值等於 0 ，為 nonsignaled 狀態. -- 維基百科 ### Semaphore APIs 使用 Semaphore 前須詳閱公開說明書: ```c= sem_t semaphore; int sem_init(sem_t *sem, int pshared, unsigned int value); int sem_wait(sem_t *sem); int sem_post(sem_t *sem); ``` 在使用 semaphore 前，我們需要使用 `sem_init()` 將其初始化: ```c= static sem_t semaphore; sem_init(&semaphore, 0, 1); ``` 透過 [Linux manual page](https://man7.org/linux/man-pages/man3/sem_init.3.html) 查看 `sem_init()` 的定義，可以知道它的三個參數從左至右分別為: - `sem_t` 型別變數的位址。 - 決定 semaphore 共享於同一個 Process 的 Thread ，或是多個 Process 。 - semaphore 的初始值。初始化後，通常我們會在 Critical section 間放置 `sem_wait()` 與 `sem_post()` 去避免 Race condition 。 #### sem_wait() `sem_wait()` 會檢查傳入的 semaphore 變數值，如果大於零，則會將它減一。相反的，如果變數值為零，該執行緒就會被 Block 。 #### sem_post() 當執行緒處理完 Critical section 便可以使用 `sem_post()` 釋放 Semaphore 物件。這時，傳入的 Semaphore 物件值會被加一。 ### 透過範例程式學習 Semaphore! 比起 Mutex ，雖然 Semaphore 同樣可以用來保護 Critical section ，不過它更常被用來確保並行程式的執行順序。不像是 Mutex lock **解鈴還需繫鈴人**的特性，在 Semaphore 中，每個任務都會消耗與製造不同的號誌，考慮以下程式碼: ```c= static sem_t A_B; static sem_t B_C; static sem_t C_A; void *printA(void *arg) { int i = 0; for(i = 1;i<11;i++){ sem_wait(&C_A); printf("第%02d次:A",i); sem_post(&A_B); } return NULL; } void *printB(void *arg) { int i = 0; for(i = 1;i<11;i++){ sem_wait(&A_B); printf("B"); sem_post(&B_C); } return NULL; } void *printC(void *arg) { int i = 0; for(i = 1;i<11;i++){ sem_wait(&B_C); printf("C"); sem_post(&C_A); } return NULL; } ``` 在 `main()` 賦予初始值: ```c= pthread_t thread_A; pthread_t thread_B; pthread_t thread_C; sem_init(&A_B,0,0); sem_init(&B_C,0,0); sem_init(&C_A,0,1); pthread_create(&thread_A,NULL,printA,NULL); pthread_create(&thread_B,NULL,printB,NULL); pthread_create(&thread_C,NULL,printC,NULL); //... ``` 透過 Semaphore ，我們不止可以避免 Race condition ，更可以保證三個 Task 的執行順序。 > 原始碼連結: [Github](https://github.com/ianchen0119/Multi-thread/blob/master/semaphore/semaphore.c) 。 ### 與 Mutex lock 的異曲同工之妙文章前面有提到， Semaphore 用於保持在 0 至指定最大值之間的一個計數值。如果開發者將 Semaphore 設計成只會出現 0 和 1 兩種狀態，便稱為 **Binary semaphore**。仔細想想， Binary semaphore 同樣確保一次只能有一個執行緒獲得共用資源的存取權，比較不同的是 Binary semaphore 不像 Mutex lock 有 Owner ship 的概念。因此在應用上， Binary semaphore 會更具彈性。 > 這裡的彈性是指，當一個 Thread 更改 Semaphore 的狀態，程式能夠允許另一個 Thread 對同一個 Semaphore 修改狀態。換句話說， Binary semaphore 可以讓我們造出一個能有它人解鎖的 Mutex lock 。 > 關於這個問題，網路上也有人設計相關實驗作探討，有興趣的讀者請參考該[連結](https://hackmd.io/@nKngvyhpQdGagg1V6GKLwA/Skh9Z2DpX?type=view)。 ## Deadlock 與 Livelock 使用鎖或是 Semaphore 確實可以避免 Race condition 的發生，不過，當開發者在設計機制時沒有考慮周全，就有可能讓程式邏輯**打結**。 ### Deadlock 簡單來說，當有兩個 Process 或是 Thread 需要彼此目前佔有的資源，而兩者卻又不願意釋放資源時，便會讓彼此的進度卡住，形成死結。又好比兩個人做交易，買家堅持賣家先出貨，賣家則堅持買家先付款，導致交易僵持，如果在電腦中出現類似的情況，就稱為 Deadlock 。 ### Deadlock 範例考慮以下程式碼: ```c= // Source: https://stackoverflow.com/questions/27480125/simple-deadlock-example-using-pthread/50111909 pthread_mutex_t lock1, lock2; void *resource1(){ pthread_mutex_lock(&lock1); printf("Job started in resource1..\n"); sleep(2); printf("Trying to get resourc2\n"); pthread_mutex_lock(&lock2); printf("Aquired resourc2\n"); pthread_mutex_unlock(&lock2); printf("Job finished in resource1..\n"); pthread_mutex_unlock(&lock1); pthread_exit(NULL); } void *resource2(){ pthread_mutex_lock(&lock2); printf("Job started in resource2..\n"); sleep(2); printf("Trying to get resourc1\n"); pthread_mutex_lock(&lock1); printf("Aquired resourc1\n"); pthread_mutex_unlock(&lock1); printf("Job finished in resource2..\n"); pthread_mutex_unlock(&lock2); pthread_exit(NULL); } int main() { pthread_mutex_init(&lock1,NULL); pthread_mutex_init(&lock2,NULL); pthread_t t1,t2; pthread_create(&t1,NULL,resource1,NULL); pthread_create(&t2,NULL,resource2,NULL); pthread_join(t1,NULL); pthread_join(t2,NULL); return 0; } ``` 在上面的範例中，兩個 Task 都會嘗試 Lock 兩個互斥鎖，一個 Task 先上鎖 lock1 再上鎖 lock2 ，另一個則相反。當這兩個 Task 嘗試上獲得第二道鎖時，就會因為對方遲遲不交出資源而陷入 Deadlock 的狀況。 ### Deadlock 發動條件要讓程式進入死結，必須天時地利人和: - No preemption：占用系統資源的一個任務無法被強制停止。 - Hold and wait：一個行程可以在等待時持有系統資源。 - Mutual exclusion：系統資源只能同時分配給一個行程，無法在多個行程共享。 - Circular waiting：多個行程互相持有其他行程所需要的資源。要達成以上條件，程式才有可能進入 Deadlock ，作業系統在做排程設計時也會將其考慮進去，做出應對機制，像是: 讓任務是可以被作業系統強制結束的。 ### Starvation 當一個 Process 遲遲無法獲得所需資源，進入長期等待，這種情況就可以稱為 Starvation (飢餓)。作業系統為了避免飢餓/死結發生，除了上面提到的可搶斷式排程，也添加了老化的機制，也就是: 當一個 Process 久久沒有執行完成，作業系統便會逐步調高它的優先權，增加該 Process 完成的速度。 > 對排程演算法感興趣的話，可以參考[作業系統概念學習筆記 10 CPU 排程](https://www.itread01.com/content/1550575293.html)。 ### Livelock Livelock 不同於 Deadlock ， Livelock 發生在彼此競爭但都願意讓步的情況，用生活上的例子就像是: 當我們走在行人道遇到對向的行人，兩個人都想讓路給對方卻又很剛好的站到同一邊，在電腦中，這樣看似有在執行卻毫無進展的情況就是 Livelock 。 ## Reference - [semaphore, mutex, spin lock](https://descent-incoming.blogspot.com/2015/11/semaphore-mutex-spin-lock.html) - Linux manual page - [Mutex, Semaphore, the difference, and Linux kernel](https://blog.louie.lu/2016/10/22/mutex-semaphore-the-difference-and-linux-kernel/) - [三、Queue 的應用(3) - Semaphore、Mutex的同步](https://ithelp.ithome.com.tw/articles/10219642) - [deadlock跟starvation教會我的人生哲學](https://antrash.pixnet.net/blog/post/91984155)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.