[作業系統] 排程

排程

• 排程
  • 何時使用排程
  • 排程的分類
  • 排程要實作的目标
  • 批處理系統中的排程
  • 互動式系統中的排程
  • 實時系統中的排程
  • 政策和機制
  • 線程排程

1. 何時使用排程？

1. 在建立一個新程序後，需要決定是運作父程序還是運作子程序。
2. 在一個程序退出時必須做出排程決策，以選擇另外某個程序。
3. 當一個程序阻塞在I/O和信号量上或由于其他原因阻塞時，必須選擇另一個程序運作。
4. 在一個I/O中斷發生時，必須做出排程決策。如果中斷來自I/O裝置，而該裝置現在完成了工作，某些被阻塞的等待該I/O的程序就成為可運作的就緒程序了，是否讓新就緒的程序運作，這取決于排程程式的決定，或者讓中斷發生時運作的程序繼續運作，或者應該讓某個其他程序運作。

2. 排程的分類

1. 批處理：适用于使用者不會在終端旁等待一個短請求的快捷響應（如商業領域，計算薪水，存貨等）
2. 互動式：避免一個程序霸占CPU拒絕為其他程序服務（如伺服器），對于這類排程，搶占是必要的
3. 實時：搶占有時是不需要的，因為程序了解它們可能會長時間得不到運作，是以通常很快地完成各自的工作并阻塞。與互動系統的差别是，實時系統隻運作那些用來推進現有應用的程式，而互動式系統是通用的，它可以運作任意的非協作甚至是有惡意的程式

3. 排程要實作的目标

1. 所有系統
   • 公平：相似的程序應得到相似的服務。不應該給予一個程序較其他等價程序更多的CPU時間。
   • 政策強制執行：看到所宣布的政策執行。例如，如果政策為隻要需要就必須運作安全控制程序，那麼即便這意味着要将其他程序推遲30秒，也要保證能夠強制執行該政策
   • 忙碌：保持CPU和I/O裝置始終能夠運作。例如對程序進行組合，CPU密集型和I/O密集型，交替運作。
   • CPU密集型(計算密集型)：程序花費了絕大多數時間在計算上
   • I/O密集型：程序在等待I/O上花費了大量時間。
2. 批處理系統
   • 吞吐量：每小時最大作業數。
   • 周轉時間：從送出作業到作業終止的平均時間(即期望得到輸出與實際得到輸出的平均等待時間)。
   • CPU使用率：保持CPU始終忙碌。
3. 互動式系統
   • 響應時間：希望快速響應請求，即有最小的發出指令到得到響應的時間。例如，請求打開檔案應該優于背景處理電子郵件的程序。
   • 均衡性：滿足使用者的期望。
4. 實時系統
   • 滿足截止時間：避免丢失資料。
   • 可預測性：在多媒體系統中避免品質降低。

4. 批處理系統中的排程

1. 先來先服務(First Come First Service)

   用隊列來維護所有程序，當一個程序請求CPU時就被放在隊列尾部，CPU處理完目前任務就取出隊列頭的任務處理。該方式為非搶占式的，即目前任務處理完或者阻塞時，才會輪到下一個任務。如果一個任務被阻塞，它會被重新放到隊尾，就像一個新作業一樣。如果兩個任務同時請求CPU，那哪個任務先被放到隊尾是不确定的。

   優點：

   • 易于了解，實作簡單
   缺點：

   • 假設有一個一次運作1秒鐘的計算密集型程序和很少使用CPU但是每個都要進行1000次磁盤讀操作的I/O密集型程序。計算密集程序運作1秒鐘，然後讀一個磁盤塊。所有的I/O程序開始運作并讀磁盤。當該計算密集程序獲得其磁盤塊時，它運作下一個1秒鐘，緊跟随着的是所有I/O程序。

     這樣做的結果是，每個I/O程序在每秒鐘内讀到一個磁盤塊，要花費1000秒鐘。

2. 最短作業優先(Shortest Job First)

   在同等重要的作業中，選擇需要運作時間最短的作業。該方法隻适用于運作時間可以預知的情況。在所有作業重要程度相等且可以同時運作的情況下，最短作業優先算法有最小的平均周轉時間。

3. 最短剩餘時間優先(Shortest Remaining Time First)

   最短作業優先方法的搶占式版本。同樣該方法也隻适用于運作時間已知的情況。這種方法可以使新的端作業獲得良好的服務。

5. 互動式系統中的排程

1. 輪轉排程(Round Robin)

   每個程序被配置設定一個時間段，稱為時間片，即允許該程序在該時間段中運作。如果在時間片結束時該程序還在運作，則将剝奪CPU并配置設定給另一個程序。如果該程序在時間片結束前阻塞或結束，則CPU立即進行切換。是以，輪轉排程是搶占式的。例如，時間片時間為2ms，程序A需要3ms才能完成，程序B隻需要1ms完成。A先請求CPU，CPU先運作程序A，運作2ms，盡管A并為完成，但是時間片已經到達了，CPU轉而運作程序B。隻運作1ms，雖然時間片未到達但是B已經運作完畢，CPU就繼續切換到A運作。

   在該方法中時間片的選擇很重要，因為程序的上下文切換需要時間如果時間片太小，則會有很多上下文切換浪費性能。如果太大，那麼在時間片完成前就會産生很多阻塞，也會延長短的互動請求的響應時間。

2. 優先級排程

   對輪轉排程的改進，可以為每個程序設定優先級。允許優先級高的程序先運作，而為了防止高優先級程序無休止地運作下去，排程程式可以再每個時鐘中斷降低目前程序的優先級。可以按照優先級将程序分組（如按優先級1,2,3,4分為四組）每組有一個隊列，當高優先級有可運作程序時，不會運作低優先級隊列中的程序。如果不對優先級進行調整，低優先級隊列有可能産生饑餓。

   

3. 多級隊列

   對優先級排程進行改進，當一個程序運作完指定時間且未結束時，被自動下調一個優先級，并放入下一層優先級程序隊列的結尾。同時，優先級最高的隊列中的程式每次運作1個時間片，次高的每次運作兩個時間片，然後是4，8，16…以此類推。這樣，可以防止CPU密集型程序的頻繁切換，以及長時間片程序影響響應時間。

   

   如圖所示，假如程序A需要運作5ms，程序B需要運作2ms，C程序要運作1ms。如果A先開始運作，當它運作時，一開始A的優先級為0(即最高優先級)，此時A的時間片為2^0 為1ms。并且在此期間程序B也請求CPU，B的優先級期初也為0，被放置在優先級為0的隊尾。

   當A運作1ms時，A被打斷并下調優先級為1，被放入優先級為1的隊列中。此時運作B，時間片也為1ms。并且C也請求CPU，并被放入優先級為0的隊尾。當B運作1ms時和A一樣，也被打斷并放入優先級為1的隊尾。此時優先級為0的隊列中有C，而優先級為1的隊列中有A，B。C的優先級比A，B都高。是以此時運作C，因為C 在1ms内可以運作完畢。并且沒有更多新任務到達。是以當C運作完畢後優先級為0的隊列就被清空。沒有任務的優先級高于A。

   此時轉而運作A，A這時的時間片應為2^1為2ms，A運作2ms，并未結束，被打斷并放入優先級為2的隊列。此時B的優先級為1，A的優先級為2，該運作B。B的時間片也為2ms，但是運作1ms時B就可以結束了。是以這時，檢查隊列0和1中沒有任務，就可以運作隊列2中的隊頭A，時間片為 2^2為4ms，A隻運作2ms，完成任務。此時所有任務都可以完成了。

   缺點：

   • 該方法存在的問題為，如果一個任務需要長時間才能完成，會被放到比較低的優先級，而如果此時一直有新任務到來，那麼這個長任務會饑餓，直到那些短任務都執行完，它才會執行。

4. 保證排程

   向使用者作出明确的性能保證，然後實作。若使用者工作時有n個使用者登入，則使用者将獲得CPU處理能力的1/n。類似地，在一個有n個程序運作的單使用者系統中，若所有程序都等價，則每個程序獲得1/n的CPU時間。系統必須跟蹤各個程序自建立以來已使用了多少CPU時間。然後它計算各個程序應獲得的CPU時間，即自建立以來時間除以n，然後求出真正獲得的CPU時間和應獲得的CPU時間。然後運作比率最低的程序，直到它超過其他程序。

5. 彩票排程

   每個程序在一定時間内可以得到一張“彩票”（CPU時間），重要程序一次可以得到多個彩票。

   規則是：擁有彩票F份額的程序大約得到系統資源的F份額。還可以讓程序交換他們的彩票。例如，客戶機和服務機，客戶機得到彩票，并且請求服務機，因為客戶機需要的CPU時間很短，是以可以将彩票中剩下的時間交換給服務機。

6. 公平分享排程

   關注程序所有者，而不是程序本身。每個使用者配置設定到CPU時間的一部分。缺點是每個使用者想要執行的程序多少不一樣，可能浪費性能。

7. 最高響應比優先

   通過W+CC這個公式求得每個任務最高響應比，結果最大的優先執行

   • W代表該任務已經等待的時間
   • C代表該任務想要完成需要的時間

6. 實時系統中的排程

實時系統是一種時間起着主導作用的系統。首先要了解截止時間，即必須在此時間之前作出應答。在實時系統中，遲到的應答可能比沒有應答更為糟糕。

實時系統可以分為硬實時和軟實時，前者的含義是必須滿足絕對的截止時間，後者的含義是雖然不希望偶爾錯失截止時間，但是可以容忍。

實時系統中的事件可以分類為周期性(以規則的時間間隔發生)事件或非周期性(發生時間不可預知)事件。一個系統可能要響應多個周期性事件流。根據每個時間需要處理時間長短，系統可能無法處理完每個事件。例如如果有m個周期事件，事件i以周期Pi發生，并需要Ci秒CPU處理一個時間，那麼可以處理負載的條件是：

∑i=1mCiPi≤1

滿足這個條件的實時系統稱為可排程的。

7. 政策和機制

以上排程方法是基于所有程序分屬不同使用者，并且程序間互相競争CPU的假設。但是如果一個程序有許多子程序，并在其控制下運作。例如，一個資料庫管理系統可能有許多子程序，每一個子程序可能處理不同的請求，或每一個子程序實作不同的功能。主程序可以掌握哪一個子程序最重要，哪一個不重要。

為了做出最優選擇，解決辦法是将排程機制與排程政策分離，即将排程算法以某種形式參數化，而參數可以由使用者程序填寫。假設核心使用優先級排程算法，但提供一條可供程序設定優先級的系統調用。這樣盡管父程序不參與排程，但可以控制子程序的排程。在這裡排程機制位于核心，而排程政策由使用者決定。

8. 線程排程

現成的排程取決于使用的是使用者級線程還是核心級線程

1. 使用者級線程：選取一個程序A，給予時間片。A中的線程排程決定哪個線程運作，假如為A1,。由于這裡線程間不存在時鐘中斷，是以該線程可以一直運作。如果該線程用完了程序的全部時間片，核心選擇另一個程序運作。當再一次運作程序A時，A1也會接着運作，直到其完成工作。（程序内部問題不會影響其他程序）

   

2. 核心級線程：核心選擇一個特定的線程運作，不用考慮線程屬于哪個程序。

   

使用者級線程切換需要少量機器指令，而核心級需要完整的上下文切換，修改記憶體映像，使高速緩存失效。另一方面，核心級線程，一旦線程阻塞在I/O上不需要像在使用者級線程中那樣将整個程序挂起。從程序A的一個線程切換到程序B的一個線程，代價要遠高于切換到切成A的另一個線程。是以核心在切換時，會傾向于後者。

使用者級線程可以使用定制的線程排程程式。假如一個分派線程給兩個工作線程分派任務，其中一個工作線程剛剛被阻塞，是以這時分派線程應該接着運作，并啟動另一個未堵塞的工作線程。但在核心級線程中，核心不了解每個線程的作用。

當工作者線程從磁盤讀取 Web 頁時，它就會被阻塞。如果使用使用者級線程，該動作将阻塞整個程序，而

破壞多線程的價值。這就是使用核心線程的原因：某些線程的阻塞不會影響到其他線程

參考書目：現代作業系統第三版，分布式系統原理與範型第二版