千頭萬緒:平行計算和吃飯中的哲學家

Posted By Mr. Thursday

每天早上醒來,我們通常會洗臉刷牙,吃早餐,搭車上班或是上學。有時候我們為了節省時間,會開始「平行處理」,譬如說:我們一邊擠牙膏的時候,可能一邊開水龍頭把水裝滿,同時完成兩件事情,減少等待閒置的時間。這就是平行處理的一個例子。我們如果把工作分成兩部分,同時給兩台機器跑,那麼原來需要一小時的工作,現在就可以在半小時內完成了。以此類推,如果有n台機器,那麼就能以 n 倍的速度完成原來的工作。平行計算如此好,然而卻會遇到一些問題,同時也有新的問題會產生。

第一個問題是工作完整性 (atomic) 和同步性 (synchronization) 的問題。譬如說餐廳的訂位系統,訂位的步驟有兩步:(1) 查詢現在剩下的位子 (2) 如果有位子的話,就把位子訂下來,否則回覆沒有位子。這個演算法非常簡單,只有兩個步驟。如果今天我們想把這個系統用平行計算來處理,達到節省時間的效果,會發生甚麼事情呢?

首先,因為電腦的作業系統 (OS: Operating System) 要達到平行計算的效果,會把每一個獨立的運轉單位當成是一個執行緒 (thread),然而作業系統在一般情況下並不會限制執行緒的優先順序 (priority),因此這一堆執行緒可能依次執行,也可能第一個 thread 執行到一半,換到第二個 thread,之後再跳回第一個 thread 繼續跑完。

所以就上面這個例子,如果今天作業系統裡面有兩個執行緒,分別處理兩個同時要訂位的要求。第一個執行緒甲 (thread) 先執行步驟 (1),他發現餐廳剛好剩下最後一個位子,所以他準備要執行步驟 (2) 訂這個位子。接下來作業系統跳到第二個執行緒乙 (thread),執行步驟 (1),也發現有一個位子,所以準備執行步驟 (2) 訂位子。結果作業系統再分別把執行緒甲執行緒乙跑完,發現一個位子被兩個人訂走了。到時候客人來的時候,就發現怎麼有兩位客人訂到同一個位子了!

同樣的情形也可能發生在提款和存款的系統。如果今天提款的步驟是:(1) 查詢餘額=X (2) 將餘額扣除領出來的錢數M (3) 把扣完的餘額存回原來帳戶的紀錄裡面,成為新的餘額,也就是 X-M。假如這個系統也用平行計算,現在又有兩個人在不同提款機提同一個帳戶的錢。thread A 首先查詢餘額 100 元,然後扣掉提出來的 20 元,剩下 80 元,還沒更新紀錄之前,thread B 被作業系統選進來,查詢餘額又是 100 元,然後扣掉提出來的錢,假設這次他要提 30 元,剩下餘額應該是 70 元,接著把餘額寫回系統,變成餘額 70 元。作業系統再回到 thread A,把剛才算出來的餘額寫回去,變成餘額 80 元。所以,兩個人總共提領了 20+30 = 50 元,帳戶餘額應該是 50 元,但是成是因為平行計算的原因,餘額變成 80 元,讓銀行白白被提領了 30 元!同樣的情形也可能讓帳戶少 30 元,讓銀行白白多了 30 元。無論是銀行少錢,或是存款人少錢,相信兩方都不會高興的!只有正確的餘額紀錄下來,才會讓銀行和存款者都滿意!

因此,如果一個程式要變成平行計算來增進效率,首先要確定某些步驟是完整的 (atomic),有如原子不可分割一般。像是訂餐系統裡面的兩個步驟,必須確定要一次執行完,不能中途被作業系統打斷,改執行另外一個thread。提款系統中的步驟 (1)(2)(3) 也是要一次執行完,才不會發生餘額多錢或少錢的情形。然而完整的步驟,或是同步後的步驟,雖然可以避免錯誤的結果,卻減少了平行計算的效率,譬如說剛才假如有 100 個人訂位,那麼第一個人訂位的時候,剩下 99 個人就要等待,因為步驟 (1)(2) 要一次執行完,即使電腦有雙核心或 100 核心也沒辦法平行處理。這是一種 tradeoff,有的問題就是無法平行化;有的可以,但是要同步 (synchronize) 某些步驟,犧牲部分效率上的延遲,以保證答案的正確

第二個問題是死結 (deadlock) 的問題。這個問題發生的最經典的例子,就是用餐中的哲學家 (Dining Philosopher) 的問題。Dining Philosopher 的問題是這樣子的:有 n 位哲學家,假設有 8 位好了,他們每個人會有三個狀態:想問題 (think)、飢餓 (hungry)、以及吃飯 (eat)。這8個哲學家坐在一個圓桌上,環繞成一個圓圈,如下圖:

Dining_Philosopher

每個哲學家的左手和右手各有一根筷子,當哲學家飢餓的時候,就會試著拿起兩邊的筷子,兩邊的筷子都拿到了,才能開始吃 (eat),否則就維持在飢餓狀態。這 8 位哲學家就是 8 個執行緒 (thread),各自被作業系統安排執行,沒有固定的先後順序,也不知道會吃多久。那麼我們要怎樣子為每一位哲學家設計演算法步驟,才能讓所有哲學家都能夠吃到飯,沒有人會餓死,也沒有人每次都拿不到筷子呢?

第一個方法可能是:我們讓每一位哲學家先拿起右手邊的筷子,拿不到就。拿到右手邊筷子之後,再等左手邊拿到筷子。兩邊筷子都拿到了就開始吃飯,吃完再放下筷子。但是這個演算法有一個問題,就是死結 (deadlock)。假設作業系統先跑第一位哲學家,第一位拿起右手邊的筷子,接著執行第二位哲學家,第二位哲學家拿起右邊的筷子,再跑第三位哲學家,以此類推,最後 8 位哲學家都拿到右手邊的筷子,然後都在等左手邊的筷子,這個時候就變成 deadlock 了,因為每個人左手邊的筷子,都被另一個哲學家當成右邊的筷子拿起來了,而另一位哲學家還要等其他哲學家放下筷子,才可能把他手中的筷子放下,第一位哲學家才有機會拿到他左手邊的筷子。因此這8位哲學家就會等在那邊,永遠沒辦法用餐了!

另外一個 deadlock 的例子是這樣子的:某一個地方規定在十字路口上,如果兩條路上面剛好有兩部車到這個路口,那麼「兩部車都要先停下來,等對方通過以後,再開過去」。這個規定聽起來似乎不錯,還有禮讓的味道。然而這個演算法會造成deadlock,因為兩部車都停下來,然後都等對方通過,但是兩部車都不會開動,彼此等來等去,最後一直等都沒辦法開動了!

剛才的 8 位哲學家也是這個問題,每一位哲學家都要等待另一位哲學家,而另一位哲學家要繼續等待另一位哲學家,最後等到我自己,形成一個等待的迴路,就永遠等不完了。

為了解決這個問題,我們可能想出第二個演算法:先拿右邊的筷子,如果左邊筷子等不到,那麼就把右邊筷子放下,這樣子至少右邊的哲學家有機會拿到他左手邊的筷子,他吃完我就有機會再拿到筷子了!這樣子似乎不錯,然而會造成 livelock (活結),也就是說,這8位哲學家不會無限地等下去,但是卻有可能不斷地拿起筷子又放下筷子,最後都沒有吃到飯。為甚麼呢?假設今天作業系統讓第一位哲學家先拿右邊的筷子、第二位拿右邊的筷子、以此類推、到第 8 位拿起右手邊的筷子。因為等不到左手邊的筷子,所以從第 8 位開始,放下右手邊的筷子、第七位放下右手邊的筷子、到最後第一位哲學家也放下右手邊的筷子。如此一來,大家都先拿起右手邊的筷子,然後又放下右手邊的筷子,但是都沒有吃到飯。這就是 livelock 了!(上面那張圖就是 livelock 的例子)

也許會說,如果剛才第8位拿到右邊的筷子後,第一位哲學家先放下右手邊的筷子,因為圓桌的關係,第一位右手邊的筷子就是第 8 位左手邊的筷子,那麼第 8 位哲學家就能順利吃到飯了!接下來第 7 位也可以順利吃到飯了,以此類推。然而平行計算有個特點,就是作業系統的排程是不確定的,每一個執行緒thread並沒有優先順序之分 (除非例外情形或是作業系統本身的工作),因此我們各種執行順序的可能性都要考慮到。這也就是說,我們如果要設計一個可以平行處理的演算法,必須要考慮所有可能執行的順序和情況,確定這些情況下我們的演算法都,才是對的演算法。這邊的「對」包括了結果正確,以及不會造成 deadlock (死結)、livelock (活結)、或是有時候還會有飢饉 (starving) 的情況。

最後提供一下名詞的區辨。多執行緒是指同一個電腦為了達成多工 (multi-tasking),讓 CPU 可以跑多個執行緒 (thread),執行的順序和時間長短由作業系統來做排程 (scheduling)。平行計算可以發生在單一 CPU 或多個 CPU 的機器上面,只要演算法是可以平行處理完某件工作就是平行演算法。分散式處理則是指「多個電腦」一起處理事情,和「多個 CPU」不同的地方在於記憶體沒有共享,電腦之間的溝通必須透過網路來傳遞訊息和資料。P2P (peer-to-peer) 也是一種分散式處理,只不過他強調的是電腦之間的關係,是平等的架構,而不是主從式 (server-client) 架構,有提供資料的主機 (server) 和享受資料的客戶端 (client),每台電腦同時是提供資料的主機 (server) 和享受資料的客戶端 (client),沒有主人和僕人的區別,因此稱為同儕 (peer),整個網路就稱為同儕網路了 (peer-to-peer)。

參考資料

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!