Linux多線程與同步
時間：2018-09-29 來源：未知
典型的UNIX系統都支持一個進程創建多個線程(thread)。在Linux進程基礎中提到，Linux以進程為單位組織操作，Linux中的線程也都基于進程。盡管實現方式有異于其它的UNIX系統，但Linux的多線程在邏輯和使用上與真正的多線程并沒有差別。
在Linux從程序到進程中提到的stack的功能和用途。由于stack中只有下方的stack frame可以被讀取，所以我們只能有該frame對應的單一函數處于激活狀態。為了實現多線程，我們必須繞開stack帶給我們的限制。為此，當我們創建一個新的線程的時候，我們為這個線程創建一個新的stack。當該stack執行到全部彈出的時候，該線程完成任務并結束。所以，多線程的進程在內存中會有多個stack，相互之間以一定的空白區域隔開，以備stack的增長。每個線程隨時可以使用自己stack中下方的stack frame中的參數和變量，并與其它線程共享內存中的Text，heap和global data區域。在上面的例子中，我們將在進程空間中有三個stack。
(要注意的是，對于多線程來說，由于同一個進程空間中存在多個stack，任何一個空白區域被填滿都會導致stack overflow的問題。)
多線程相當于一個并發(concunrrency)系統。并發系統一般同時執行多個任務。如果多個任務可以共享資源，特別是同時寫入某個變量的時候，就需要解決同步的問題。比如說，我們有一個多線程火車售票系統，用全局變量i存儲剩余的票數。多個線程不斷地賣票(i = i - 1)，直到剩余票數為0。所以每個都需要執行如下操作:
/*mu is a global mutex*/
while (1) { /*infinite loop*/
if (i != 0) i = i -1
else {
printf("no more tickets");
exit();
}
}
如果只有一個線程執行上面的程序的時候(相當于一個窗口售票)，則沒有問題。但如果多個線程都執行上面的程序(相當于多個窗口售票), 我們就會出現問題。我們會看到，其根本原因在于同時發生的各個線程都可以對i讀取和寫入。
我們這里的if結構會給CPU兩個指令, 一個是判斷是否有剩余的票(i != 0), 一個是賣票 (i = i -1)。某個線程會先判斷是否有票(比如說此時i為1)，但兩個指令之間存在一個時間窗口，其它線程可能在此時間窗口內執行賣票操作(i = i -1)，導致該線程賣票的條件不再成立。但該線程由于已經執行過了判斷指令，所以無從知道i發生了變化，所以繼續執行賣票指令，以至于賣出不存在的票 (i成為負數)。對于一個真實的售票系統來說，這將成為一個嚴重的錯誤 (售出了過多的票，火車爆滿)。
在并發情況下，指令執行的先后順序由內核決定。同一個線程內部，指令按照先后順序執行，但不同線程之間的指令很難說清除哪一個會先執行。如果運行的結果依賴于不同線程執行的先后的話，那么就會造成競爭條件(race condition)，在這樣的狀況下，計算機的結果很難預知。我們應該盡量避免競爭條件的形成。常見的解決競爭條件的方法是將原先分離的兩個指令構成不可分隔的一個原子操作(atomic operation)，而其它任務不能插入到原子操作中。
3. 多進程同步(synchronization)
對于多線程程序來說，同步是指在一定的時間內只允許某一個線程訪問某個資源 。而在此時間內，不允許其它的線程訪問該資源。我們可以通過互斥鎖(mutex)，條件變量(condition variable)和讀寫鎖(reader-writer lock)來同步資源。
1) mutex
mutex是一個特殊的變量，它有鎖上(lock)和打開(unlock)兩個狀態。mutex一般被設置成全局變量。打開的mutex可以由某個線程獲得。一旦獲得，這個mutex會鎖上，此后只有該線程有權打開。其它想要獲得mutex的線程，會等待直到mutex再次打開的時候。我們可以將mutex想像成為一個只能容納一個人的洗手間，當某個人進入洗手間的時候，可以從里面將洗手間鎖上。其它人只能在mutex外面等待那個人出來，才能進去。在外面等候的人并沒有排隊，誰先看到洗手間空了，就可以首先沖進去。
上面的問題很容易使用mutex的問題解決，每個進程的程序可以改為:
/*mu is a global mutex*/
while (1) { /*infinite loop*/
mutex_lock(mu); /*aquire mutex and lock it, if cannot, wait until mutex is unblocked*/
if (i != 0) i = i - 1;
else {
printf("no more tickets");
exit();
}
mutex_unlock(mu); /*release mutex, make it unblocked*/
}
第一個執行mutex_lock()的線程會先獲得mu。其它想要獲得mu的線程必須等待，直到第一個線程執行到mutex_unlock()釋放mu，才可以獲得mu，并繼續執行線程。所以線程在mutex_lock()和mutex_unlock()之間的操作時，不會被其它線程影響，就構成了一個原子操作。
需要注意的時候，如果存在某個進程依然使用原先的程序 (即不嘗試獲得mu，而直接修改i)，mutex不能阻止該程序修改i，mutex就失去了保護資源的意義。所以，mutex機制需要程序員自己來寫出完善的程序來實現mutex的功能。我們下面講的其它機制也是如此。
2) condition variable
condition variable是另一種常用的變量。它也常常被保存為全局變量，并和mutex合作。
假設我們有這樣一個狀況: 我們有100個工人，每人負責裝修一個房間。當有10個房間裝修完成的時候，我們就通知相應的十個工人一起去喝啤酒。我們如何實現呢?我們可以讓工人在裝修好房間之后，去檢查已經裝修好的房間數。但多線程條件下，會有競爭條件的危險(其他工人會在該工人裝修好房子和檢查之間完成工作)。
/*mu: global mutex, cond: global codition variable, num: global int*/
mutex_lock(mu)
num = num + 1; /*worker build the room*/
if (num <= 10) { /*worker is within the first 10 to finish*/
cond_wait(mu, cond); /*wait*/
printf("drink beer");
}
else if (num = 11) { /*workder is the 11th to finish*/
cond_broadcast(mu, cond); /*inform the other 9 to wake up*/
}
mutex_unlock(mu);
通常, condition variable除了要和mutex配合之外，還需要和另一個全局變量配合(這里的num, 也就是裝修好的房間數)。這個全局變量用來構成各個條件。
我們讓工人在裝修好房間(num = num + 1)之后，去檢查已經裝修好的房間數( num < 10 )。由于mu被鎖上，所以不會有其他工人在此期間裝修房間(改變num的值)。如果該工人是前十個完成的人，那么我們就調用cond_wait()函數。
cond_wait()做兩件事情，一個是釋放mu，從而讓別的工人可以建房。另一個是等待，直到cond的通知。這樣的話，符合條件的線程就開始等待。當有通知(第十個房間已經修建好)到達的時候，condwait()會再次鎖上mu，并恢復線程的運行，我們會執行下一句prinft("drink beer") (我們以此來代表喝啤酒)。此后直到mutex_unlock()就構成了另一個mutex結構。
那么如何讓前面十個調用cond_wait()的線程得到通知呢？我們注意到if還有另一種可能，也就是修建好第11個房間的人負責調用cond_broadcast()。它會給所有調用cond_wait()的進程放送通知，以便讓那些進程恢復運行。
Condition variable特別適用于多個線程等待某個條件的發生。如果不使用Condition variable，那么每個進程就需要不斷嘗試獲得mutex并檢查條件是否發生，這樣大大浪費了系統的資源。
3) reader-writer lock
Reader-writer lock與mutex非常相似。r、RW lock有三種狀態: 共享讀取鎖(shared-read), 互斥寫入鎖(exclusive-write lock), 打開(unlock)。后兩種狀態與之前的mutex兩種狀態完全相同。
一個unlock的RW lock可以被某個進程獲取R鎖或者W鎖。
如果被一個進程獲得R鎖，RW lock可以被其它進程繼續獲得R鎖，而不必等待該進程釋放R鎖。但是，如果此時有其它進程想要獲得W鎖，它必須等到所有持有共享讀取鎖的進程釋放掉各自的R鎖。
如果一個鎖被一個進程獲得W鎖，那么其它進程，無論是想要獲取R鎖還是W鎖，都必須等待該進程釋放W鎖。
這樣，多個進程就可以同時讀取共享資源。而具有危險性的寫入操作則得到了互斥鎖的保護。
我們需要同步并發系統，這為程序員編程帶來了難度。但是多線程系統可以很好的解決許多IO瓶頸的問題。比如我們監聽網絡端口。如果我們只有一個線程，那么我們必須監聽，接收請求，處理，回復，再監聽。如果我們使用多線程系統，則可以讓多個線程監聽。當我們的某個線程進行處理的時候，我們還可以有其他的線程繼續監聽，這樣，就大大提高了系統的利用率。在數據越來越大，服務器讀寫操作越來越多的今天，這具有相當的意義。多線程還可以更有效地利用多CPU的環境。
(就像做飯一樣，不斷切換去處理不同的菜。)
總結:
multiple threads, multiple stacks
race condition
mutex, condition variable, RW lock
