處理機的三級排程以及其排程算法自我總結（補充了實時排程算法）

在多道程式系統中，一個作業送出之後需經過處理機排程才能獲得處理機執行。

三級排程

• 進階排程

  • 别稱：作業排程，長程排程
  • 作用：根據一定算法把外存上處于後備隊列中的作業調入記憶體，并為之建立程序，配置設定資源，插入就緒隊列。（決定能否加入到執行的程序池中）
  • 對象：作業

• 低級排程

  • 别稱：程序排程，短程排程
  • 作用：（按照後面的某種算法）決定就緒隊列中的哪個程序獲得處理機。 （決定哪個可用程序占用處理機執行）
  • 對象：程序（或核心級線程）
  • 排程方式：1.非搶占式 （直到程序執行完或者發生某事件被阻塞） 2.搶占式（原則：1.優先權原則，2.短作業(程序)優先原則，3.時間片原則）

• 中級排程

  • 别稱：中程排程，平衡負載排程
  • 作用：把那些暫時不執行的程序調到外存上（決定哪些程序進入挂起狀态），可以提高記憶體使用率和系統吞吐量
  • 對象：程序（或核心級線程）

或者

排程算法

也叫資源配置設定算法

先來先服務排程算法 FCFS

作業排程：每次排程從後備隊列中**選擇最先進入隊列的**一個或多個作業，調入記憶體，配置設定資源，建立程序，加入就緒隊列
 程序排程：每次排程從就緒隊列中選擇最先進入隊列的一個或多個程序，配置設定處理機，使運作
           

特點：

• 最簡單
• 可用于作業排程，程序排程
• 該算法利于長作業（程序），不利于短作業（程序）

短作業（程序）優先排程算法 SJ(P)F

作業排程：每次排程從後備隊列中**選擇運作時間最短的**一個或多個作業，調入記憶體，配置設定資源，建立程序，加入就緒隊列
 程序排程：每次排程從就緒隊列中選擇運作時間最短一個或多個程序，配置設定處理機，使運作
           

特點：

• 可用于作業排程，程序排程
• 該算法利于短作業（程序），不利于長作業（程序），甚至長作業可能長期不被執行
• 該算法未考慮作業的緊迫程度，so緊迫的作業不一定被及時處理

兩個算法比較

• 完成時間 = 服務時間 + 開始時間
• 周轉時間 = 完成時間 - 到達時間
• 帶權周轉時間 = 周轉時間 / 服務時間

  

最高優先權排程算法 FPF

可用于作業排程，程序排程

調用時，系統從後備隊列中選取優先級最高的一個或多個作業（程序），操作。

程序排程中，該算法可分為兩種

• 非搶占式優先權算法：處理機配置設定到優先權最高的程序之後，一直到執行完成才停，或是發生事件導緻阻塞。（實時性不高）
• 搶占式優先權排程算法：處理器配置設定之後，執行到當出現優先級更高的程序就立即停止目前執行的程序，重新配置設定給最高（程序切換）。用作要求比較嚴格的實時系統/對性能要求高的批處理和分時系統

優先權分類

• 靜态優先權：優先權在程序建立時候确定并且在運作過程中不會改變
  • 确定優先權依據 1.程序類型 2.程序對資源的需求 3.使用者要求
• 動态優先權：在建立程序時賦予優先權，會随着程序推進或等待時間的增加而改變，以擷取更好的排程性能。

優先權 = （等待時間 + 要求服務時間） / 要求服務時間（）

(作業)響應時間 = 等待時間 + 要求服務時間

響應比： Rp = 響應時間 / 要求服務時間

特點

• 該算法利于短作業（要求服務時間越短優先權越高）
• 優先權相當于響應比
• 每次排程都要做響應比計算，增加系統開銷

時間片輪轉排程算法

早期，分時系統采用時間片輪轉法，後來采用多級回報隊列排程算法。

時間片輪轉法

每個程序被配置設定一個時間段，稱作它的時間片，即該程序允許運作的時間。如果在時間片結束時程序還在運作，則CPU将被剝奪并配置設定給另一個程序。如果程序在時間片結束前阻塞或結束，則CPU當即進行切換。排程程式所要做的就是維護一張就緒程序清單，當程序用完它的時間片後，它被移到隊列的末尾
           

特點

• 時間片選的小，利于短作業，頻繁發生中斷，程序切換，增加系統開銷
• 時間片選的長，退化為FCFS

  

  某個時間點，順序是先下一個程序進入隊列，然後才切換程序

多級回報隊列排程算法

特點：

• 設有N個隊列，其中各個隊列對于處理機的優先級是不一樣的（一般優先級 1隊列>2>3…）
• 每個隊列遵循自己的時間片，并且越前的隊列時間片越小，後面的隊列優先級小而時間片長。
• 前面的隊列執行停止的程序會配置設定到下一個隊列尾，等待此隊列被排程。
• 當第n隊列空閑，排程程式才排程第(n+1)隊列中程序，其他依此進行。
• 如果處理繼被配置設定到n隊列執行其中一個程序，而有個優先級高的程序此時進入（配置設定到1~(n-1)隊列中），其會搶占處理機，則排程程式把正在執行的程序放到n隊列末尾，然後排程處理機給此優先級高的程序。

實時排程算法

實時系統中存在着多個實時程序（任務）用來反應或控制某些外部事件（緊迫性），用上面的排程算法不滿足。

實時排程的基本條件

• 就緒時間：該任務成為就緒狀态的起始時間，若是周期任務，則時間就是一串時間序列。（可預知）
• 開始截至時間和完成截止時間： 知道其中一個即可。
• 處理時間：一個任務從開始執行到完成的時間。（可以由系統提供此時間）
• 資源要求：任務所需資源
• 優先級：
• 系統處理能力強
• 采用搶占式排程機制
• 有快速切換機制（對外部中斷快速反應，快速任務分派）

實時排程算法的分類

• 根據任務性質： 硬實時排程算法， 軟實時排程算法
• 根據排程方式：非搶占式排程算法，搶占式排程算法
  • 非搶占式可分為
    • 非搶占式輪轉排程算法：按順序輪流執行，用于要求不嚴格的實時控制系統（幾秒到幾十秒響應時間）
    • 非搶占式優先排程算法：有一定要求的實時控制系統（幾秒到幾百毫秒響應時間）
  • 搶占式可分為
    • 基于時鐘中斷的搶占式優先權排程算法：當任務的優先級高于目前任務的優先級，要等到時鐘中斷到來才能搶占。大多數實時系統使用（幾十毫秒響應時間）
    • 立即搶占式優先權排程算法：一旦出現外部中斷，隻要目前任務未處于臨界區，就剝奪目前任務的執行，配置設定給更緊迫的程序（幾毫秒到幾百微秒響應時間）

      

• 根據程式排程時間：靜态排程算法，動态排程算法

最早截止時間優先算法 EDF

• 根據任務的開始截止時間确定任務優先級，截止時間越早，優先級越高。
• 可用于搶占式和非搶占式
  • 非搶占式排程方式用于非周期實時任務 （這裡2比3先到，但是3的截止時間比2早，是以先執行3）

    

  • 搶占式排程方式用于周期實時任務（這裡第二行和第三行是普通的優先級排程，分别是A或B優先，都會有程序未能執行完畢，第四個是本算法）

    兩個任務：A，B；A任務周期時間20ms，處理時間10ms；B任務周期時間50ms，處理時間25ms

    

    上B1執行期間A3進入，但是由于B1最後期限在前，是以A3不能搶占；而B2執行期間A5進入，二者最後期限相同，是以搶不搶都可以

最低松弛度優先算法 LLF

• 根據任務緊急（或松弛）的程度，确定任務優先級。越緊急（松弛度越低），優先級越高。越先執行。
• 松弛度 = 必須完成時間 - 本身運作時間 - 目前時間；

當t1,A1松弛讀是20-10-0=10ms，而B1松弛度是50-25-0=25ms，是以A1先；當A1完畢，t2處，B1松弛度是50-25-10=15，而A2還沒到的；當t3，B1松弛度是50-30-20=10，而A2松弛度是40-30-10=0，是以先運作A2,….；當t7時，A4松弛度為0，必須執行。（個人感覺B程序能執行就一直執行，除非到了A程序不得不搶的地步，即松弛度為0的時候）

END