排程問題與CPU Scheduling

Posted By Mr. Thursday

如果今天有一台機器,N個人要用,每個人使用的時間分別是t1, t2, …, tn,那麼怎樣子才能讓等待的時間最少呢?如果是以每個人的角度來說的話,當然是先搶先贏啦!不過如果是以這N個人所屬機構的角度來看,要讓全部人的等待時間最少,要如何安排使用機器的順序呢?這個時候作業系統 (OS: Operating System) 裡面的CPU Scheduling方法,就可以參考了!

首先我們先看看N個人不同的先後順序有幾種組合呢?答案是N!(N階層)種組合,譬如說5個人先後順序的組合方法就有5! = 120種組合,裡面包括第一個人先、然後第二個人、第三個人、第四個人、第五個人執行,也包括第一個人先、然後第三個人、第四個人、第五個人、最後才是第二個人執行,以及更多種組合的方法。因此我們排程的解答,就是在這麼多種組合(N!種)裡面,找到一個執行的順序,大家等待的時間加總起來是最小的。然而要怎麼找到這個解答呢?

我們可以每一種組合都計算一次總共等待的時間,然後找出等待時間最少的那一次,作為解答。然而這個方法需要N!次的計算!如果今天有10個人,我們不知道要計算幾次(有興趣的人可以計算一下10!有多大)。因此如果有其他經驗改良的搜尋法(Heuristic Search),會讓我們比較快地找出正確答案,或是雖然不是正確答案,也不會差太多的答案,也是可以,只要找出解答的時間可以接受就好。

作業系統課本裡面CPU Scheduling主要提到了三大種方法:先到先執行 (FCFS: First-Come, First-Served Scheduling)、最短時間的工作先執行 (Shortest-Job-First Scheduling)、以及循環執行(Round-Robin Scheduling)。以下我簡單地用白話來解釋這三種排程的演算法是甚麼樣子。

先到先執行就是說,今天一台機器,先來到機器旁邊的人先用,以此類推。這個方法雖然容易,但是如果其中某一個人要使用機器很久的時間,後面又剛好等了很多人,那麼大家等待的時間總和就會變的很久。

最短時間的工作先執行,則是看看大家的執行時間,需要最少執行時間的人先用機器,以此類推。這個方法是最佳解(optimal),大家可以用矛盾證法來證明(prove by contradiction),如果今天我們按照這個演算法,讓執行最少時間的第一位執行、次少時間的第二位執行,以此類推。然後排出來的結果我們說並不是最好的解答,也就是存在一個解答,會和現在的執行順序不同,而且讓執行時間的總和變少。假設是這群人當中的i和j兩個人 (按照剛才的演算法 i 在 j 之前執行) 要交換順序得到最佳解答,變成 j 在 i 之前執行才是最佳解答(等待時間比剛才排程的解答更少),那麼就表示 j 的執行時間會比 i 的執行時間還短,才有辦法讓新的排程的等待時間總和變少,然而這和一開始的假設矛盾 (按照剛才的演算法,i 之所以排在 j前面,是因為 i 的執行時間比 j 的執行時間少),因此依照剛才演算法得到的排程,會得到最佳解答。

這個演算法雖然是最佳解,然而因為這個問題是用在不知道每個人究竟會執行多少時間的狀況,所以要找出最短執行時間的人可能有困難,需要用類似移動平均的方法來預測下次可能執行的時間長度。如果每個人使用機器的時間是固定的,而且每個人會執行幾次,以及一開始就知道每次執行的時間是多長,那麼就不需要這邊提到的三大演算法來找出排程順序了!如果使用機器的時間不一樣長,每個人會執行幾次並不一定,每次執行的時間要在執行之前才會知道,這篇文章提到的三種演算法就可以拿來參考看看!

第三種方法則是循環執行(Round Robin)。這個方法是說,把時間分成一個一個小間隔,譬如說一小時一小時,或是10分鐘為一個單位,大家循序漸進,執行完10分鐘以後就換下一個人,執行完10分鐘以後再換下一個人。如果做個比喻,就好像有10盤菜,每盤菜吃一口,這道菜吃一口就再吃另一道菜,每次都只吃一小口,但是10盤菜最後還是會吃完。這個演算法是分享式的演算法,也就是說如果系統中有50個人,每個人執行時間會變成約50倍,但是就不會有先到先執行演算法的問題,某一個人要執行很久,後面的人就要全部一起等。這個演算法等待時間的總和是多少呢?每個人的等待時間不會超過(n-1)*ti,因此等待時間的總和不會超過 (n-1)*全部工作時間的總和。有些情況這會比先到先執行的演算法好,不過如果工作不能切割,或是換下一個人使用機器的過程成本太高(overhead),就不適合用這個演算法了。

下圖顯示了不同演算法的排程,用在5個不同時間長短的工作(P1到P5)上面的情形,等待時間的總和必須要累加時間才是等待時間的總和,至於工作全部執行完畢的時間則是當然相同的了。FCFS是先到先執行演算法,SJF是最短工作先執行演算法,RR是循環執行演算法,Priotiy本篇文章沒提到,是一種優先順序演算法,可以自訂工作的優先順序來排程。

排程其實有更多種演算法,用在更多更複雜的情形,譬如從1顆CPU變成多顆CPU的問題,以及每個工作可能有先後順序的限制的問題 (譬如說P3不能排在P1後面等限制條件)。

Job-Shop Problem就是一個很難的問題,也被證明了是NP-complete的問題,就留給有興趣的讀者再進一步去研究吧!希望每個人在遇到有限資源的時候,都能夠找到最佳解的排程 (schedule)!

延伸閱讀

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