行程的調度

• 考慮因素

  1. 為了構建調度策略，需要做一些簡化假設，這些假設和系統中運行的行程相關，統稱為作業負載(workload)

     （1）每一個行程（作業）運行相同的時間

     （2）所有作業同時到達，有時候當多個作業到達的時間相差很小的時候，也近似認為是同時到達的

     （3）一旦開始作業，每個作業將保持運行直到完成

     （4）所有作業只是使用CPU，即：它們不執行I/O操作

     （5）每個作業的運行時間是已知的

  2. 為了能夠衡量不同調度策略的優缺點，提出一個指標——周轉時間（turnaround time)

     （1）定義：任務完成時間減去任務到達的時間，即：

 （2）當滿足假設同時到達時，到達時間為0，周轉時間等于完成時間

 （3）周轉時間是一個**性能**（performance）**指標**，而性能和公平在調度系統往往時矛盾的，調度系統可以優化性能，但代價時阻止一些任務運行，這就降低了公平

• 先進先出（FIFO）

  1. 先進先出（First In First Out)：先就緒的作業先執行

  2. 假設有A、B、C三個作業，A比B早一點點，B比C早一點點，此時根據我們的假設，可以將A、B、C近似看作時同時到達的，但是根據實際情況，是A先執行，其次是B，最后是C，假設每個作業運行10s，求作業的平均周轉時間（average turnaround time)？
     

     A的周轉時間為10s，B的周轉時間為20s，C的周轉時間為30s

     平均周轉時間為（10+20+30）/3=20

  3. 現在放寬假設1，讓A、B、C運行時間不同，考慮FIFO是否存在平均周轉時間較長的情況

  4. 假設A、B、C三個作業，A運行時間為100s，B和C運行時間為10s，如果依舊是A先早到一點，然后是B，最后是C（仍然近似認為是同時到達的），此時系統的平均周轉時間較長（100+110+120）/3=110

     

  5. FIFO出現4這種情況被稱為護航效應（convoy effect），即：一些耗時較少的潛在資源消耗者排在重量級的資源消費者后面，例如：在雜貨店只有一個排隊隊伍的時候，你看見前面的裝滿了3輛購物車的貨物時，這會讓你等很長時間

• 最短任務優先（SJF）

  1. 最短任務優先（Shortest Job First）：先運行最短的時間，然后是次短的時間，如此繼續

  2. 依舊在上述4的情況下，按照SJF的策略，平均周轉時間為（10+20+120）/3=50，和FIFO相比，顯著降低了平均周轉時間，但前提是滿足假設2——同時到達
     

  3. 現在放寬假設2，即：作業能夠隨時到達，考慮SJF平均周轉時間較長的情況

  4. 依舊是FIFO中4的情況，假設A在t=0時到達，并且需要運行100s，而B和C在t=10s到達，各自運行10s，則A的周轉時間為100s，B的周轉時間為110-10=100，C的周轉時間為120-10=110，平均周轉時間為（100+100+110）/3=103.33s

  5. 很明顯當作業能夠隨時到達的情況下，SJF可能會出現平均周轉時間較長的情況

• 最短完成時間優先（STCF）

  1. 最短完成時間優先（Shortest Time-to-Completion First）：放寬假設3，即：調度程式可以安排其它作業搶占正在運行的作業占用的CPU，

  2. 在SJF中添加了搶占，每當新作業進入就緒狀態時，它就會確定剩余作業和新作業中，誰的完成時間最少，然后調度這個作業

  3. 在上述4的情況下，STCF將搶占A并先運行完B和C后，才會繼續運行，則A的周轉時間為120s，B的周轉時間為10s，C的周轉時間為20s，平均周轉時間為(120+10+20)/3=50，顯著降低了SJF相同情況下的平均周轉時間

  

• 增加考慮因素

  1. 當符合假設4、5成立時，即：知道任務長度，并且任務只使用CPU，根據當前的唯一衡量指標為周轉時間時，STCF是一個很好的策略，但是，引入分時系統時，就出現了問題，因為此時需要任務和用戶進行互動，而周轉時間無法衡量任務的互動性

  2. 回應時間（response time）：能夠衡量任務的互動性，定義為從任務到達系統到首次運行的時間
     

• 輪轉（RR）

  1. 輪轉（Round-Robin）：在一個時間片內運行一個作業，然后切換到運行佇列的下一個任務，而不是運行一個任務直到結束，它反復執行，直到所有任務完成，

  2. 時間片長度必須時時鐘周期的倍數，如果不是，進行背景關系切換的時候需要等待一段時間，此時CPU沒作業，就浪費了CPU資源

  3. 假設3個任務，A、B、C在系統中同時到達，并且它們都希望運行5s，SJF調度程式必須運行完當前任務才能運行下一個任務，而1s時間片的RR能夠快速回圈作業，RR平均回應時間為：（0+1+2）/3=1（注：同時到達，到達時間為0），SJF演算法平均回應時間為（0+5+10）/3=5
     

  4. 時間片長度對RR至關重要，越短，RR在回應時間上的表現越好，但是時間片不能設定得太短：突然背景關系切換會影響整體性能，因為背景關系切換的成本不僅僅來自保存和恢復少量暫存器的作業系統操作，程式在運行時，還會在CPU高速快取、TLB、分支預測器和其他片上的硬體中建立了大量的狀態，所以時間片長度需要慎重權衡，讓它足夠長，以便攤銷背景關系切換成本，而又不會讓系統不及時回應

  5. 攤銷（amortize)：通過減少成本的頻度（即：執行較少的操作），系統的總成本就會降低，例如：如果時間片設定為10ms，并且背景關系切換時間為1ms，大約會浪費10%的時間用于背景關系切換，為了攤銷這個成本，可以把時間片長度增加到100ms，則只有不到1%的時間會用于背景關系切換，

  6. 在3中，我們只考慮了回應時間，沒考慮周轉時間，如果計算RR的周轉時間，A為13，B為14，C為15，平均14，而SJF的周轉時間為，A為5，B為10，C為15，平均10.此時RR雖然回應時間較好，但是周轉時間較差，

  7. 到目前為止，有兩類調度程式

     （1）SJF、STCF優化了周轉時間，但是回應時間——互動性不好

     （2）RR優化了回應時間，但是周轉時間不好

• 結合I/O

  1. 放寬假設4，即：作業會執行I/O，此時調度程式會面臨兩個問題

     （1）發起I/O請求做出決定，因為當前運行的任務在I/O期間不會使用CPU，它會被阻塞等待I/O完成，這時調度程式需要考慮是否等待該任務的執行還是安排另一項任務

     （2）I/O完成時做出決定，I/O完成時會產生中斷，作業系統運行并將發出I/O的行程從阻塞狀態移回到就緒狀態，此時調度程式將考慮是繼續執行該任務，還是執行其他任務

  2. 假設有兩項作業A、B，每項作業需要50ms的CPU時間，A每運行10ms，就會發出一次I/O請求，而B只是單純地使用CPU50ms.調度程式先運行A再運行B，假設構建STCF調度程式，可以將A的每個10ms的子作業看作是一項獨立的作業，所以任務運行時，先執行A10ms的子任務，完成后，會執行B，當I/O請求完成后，就會搶占B并運行10ms，這樣就會充分利用系統，

  

  3. 當互動式作業（即：I/O請求較多）正在執行I/O時，其他CPU密集型任務（即：I/O操作很少）將運行，從而更好的利用處理器

• 多級反饋佇列（MLFQ）

  1. 多級反饋佇列（Multi-level Feedback Queue，MLFQ）需要解決的問題

     （1）優化周轉時間

     （2）放寬假設5，即：不知道任務運行時間

     （3）降低回應時間，獲取更好的互動體驗

  2. 基本構成：有許多獨立的佇列，每個佇列有不同的優先級（priority level）

  3. 基本規則：

     （1）規則1：如果A的優先級>B的優先級，運行A（不運行B）

     （2）規則2：如果A的優先級=B的優先級，輪轉運行A和B

  4. 如何改變優先級（1）？

     （1）系統需要執行的任務可以分為下列兩類

     ? a. 運行時間很短、頻繁放棄CPU的互動性任務

     ? b. 需要很多CPU時間、回應時間不是很重要的長時間計算密集型任務

     （2）優先級調整演算法

     ? a. 規則3：任務進入系統時，放在最高優先級（最上層佇列）

     ? b. 規則4a：任務用完整個時間片后，降低優先級（移入下一個佇列）

     ? c. 規則4b：如果作業再其時間片內主動釋放CPU，則優先級不變

     （3）實體1：單個長作業

     下圖展示了一個有三個佇列的調度程式，該作業首先進入最高優先級（Q2），執行10ms的時間片后，優先級-1，最終進入Q1，并一直到執行完畢

     

     （4）實體2：來了一個短作業

     有兩個作業：A時一個長時間運行的CPU密集任務，B是一個運行時間很短的互動型任務，假設A執行一段時間后B到達，下圖中A（用黑色表示）在最低優先佇列中（由（3）可知：長時間任務很長時間都會在最低佇列中），B（用灰色表示）在時間T=100時到達，并加入最高優先級佇列中，由于它運行時間很短，經過兩個時間片，在被移入最低優先級佇列之前，B執行完畢，然后A繼續運行，

     

     （5）MLFQ演算法的目標：如果不知道任務時短任務還是長任務，那么就在考試的時候假設它時短任務，并賦予最高優先級，如果確實是短任務，則會很快執行完畢，否則就會被慢慢移入低優先級佇列，而這個時候該任務也被認為是長任務了，通過這種方式，MLFQ近似于SJF，

     （6）實體3：有I/O

     根據4b，互動型作業中有大量的I/O操作（比如等待用戶的鍵盤或滑鼠輸入），它會在時間片用完之前放棄CPU，在這種情況下，我們會保持它的優先級不變

     假設互動型作業B（用灰色表示）每執行1ms便需要進行I/O操作，它與長時間運行的作業A（用黑色表示）競爭CPU，MLFQ演算法保持B在最高優先級，因為B總是讓CPU，如果B是互動型作業，MLFQ就進一步實作了它的目標，讓互動型作業快速運行，

  5. 現在，MLFQ在長時間任務之間可以公平地分享CPU，又能給短作業或互動型作業很好地回應時間，這樣就完美呢？其實還有問題

     a. 饑餓問題（starvation）問題，即：系統有許多互動型作業，就會不停地搶占長時間任務地CPU，讓它們永遠無法得到CPU

     b. 愚弄調度程式（game the scheduler），即：行程在時間片用完之前，呼叫一個I/O操作（比如訪問一個無關的檔案），從而主動釋放CPU，如此便可以保持吃在高優先級，占用更多的CPU時間

     c. 一個程式可能在不同時間表現不同，即：一個計算密集型的行程可能在某段時間表現為一個互動型的行程

• 如何提高優先級（2)?

  1. 如何解決上述5中的問題？

     周期性地提升所有任務地優先級，最簡單的就是周期性的將所有任務放到最高優先級佇列中

     規則5：經過一段時間S，就將系統的任務重新加入到最高優先級佇列中，

  2. 新規則解決的問題

     （1）行程不會餓死——在最高優先級佇列中，它會以RR的方式，和其他高優先級作業分享CPU，從而最侄訓得執行

     （2）如果一個CPU密集型作業變成了互動型，當它的優先級提升，調度程式會正確對待它

  3. 下邊有兩張圖，左邊沒有優先級提升，長時間任務在兩個短任務到達后被餓死，右邊的每隔50ms就有一次優先級提升（50ms只是舉例），因此至少保證了長任務的作業會有一定的行程，每過50ms就被提升到最高優先級，從而定期獲得執行，

     

  4. 剩余問題

     （1）S的值如何設定？如果S設定得太高，長任務會被餓死，如果太低，互動型作業得不到合適的CPU時間比例

     （2）如何阻止調度程式被愚弄？作業在時間片以內釋放CPU就保留它的優先級是存在問題的

• 選擇好的計時方式

  1. 更完善的CPU計時方式：調度程式應該記錄一個行程在某一層消耗的總時間，只要行程用完了自己的配額，就將它降到低一級的優先級佇列中，

  2. 重寫規則4a和4b

     規則4：一旦作業用完了其在某一層的時間配額（無論中間主動放棄了多少次的CPU），就降低其優先級（移入低一級佇列）

  3. 下圖對比了在規則4a、4b的策略下（左圖），以及在新的規則4（右圖）的策略下，同樣試圖愚弄調度程式的行程的表現，滅有規則4的保護下，行程可以在每個時間片結束前發起一次I/O操作，從而壟斷CPU時間，有了這樣的保護，無論行程的I/O行為如何，都會慢慢降低優先級

     

• MLFQ調優以及其他問題

  問題：

  （1）配置多少佇列

  （2）每一層佇列的時間片配置多大

  這些問題沒有顯而易見的答案，只有利用對作業負載的經驗以及后續對調優程式的調優，才會取得令人滿意的平衡

  例如：高優先級佇列通常只有較短的時間片，使得互動型作業能夠更快的切換，而低優先級佇列中更多的是CPU密集性作業，配置更長的時間片會更好

• MLFQ規則小結

  （1）規則1：如果A的優先級>B的優先級，運行A（不運行B）

  （2）規則2：如果A的優先級=B的優先級，輪轉運行A和B

  （3） 規則3：任務進入系統時，放在最高優先級（最上層佇列）

  （4）規則4：一旦作業用完了其在某一層的時間配額（無論中間主動放棄了多少次的CPU），就降低其優先級（移入低一級佇列）

  （5）規則5：經過一段時間S，就將系統的任務重新加入到最高優先級佇列中，

標籤：其他

上一篇：作業系統導論（1）

下一篇：Java Object 類常用方法總結