讀書筆記-現代作業系統-2程序與線程-2.4排程

2.4排程

計算密集型/IO密集型

何時排程：

• 在建立一個新程序後
• 再一個程序退出時
• 在一個程序IO和信号量或其他原因阻塞時
• 中斷發生時

排程算法分類：

• 批處理
• 互動式
• 實時

排程算法的目标：

• 所有系統：
  • 公平-給每個程序公平的CPU份額
  • 政策強制執行-看到所宣布的政策執行
  • 平衡-儲存系統的所有部分忙碌
• 批處理：
  • 吞吐量-每小時最大作業數
  • 周轉時間-從送出到終止間的最小時間
  • CPU使用率-儲存CPU始終忙碌
  • 互動式系統
  • 響應時間-快速響應請求
  • 平衡性-滿足使用者的期望
  • 實時系統
  • 滿足截止時間-避免丢失資料
  • 可預測性-在多媒體系統中避免品質降低

2.4.1 批處理系統

1. 先來線服務

2. 最短作業優先

   運作時間可預知的批處理排程算法

3. 最短剩餘時間優先

   相當于最短作業優先的搶占式版本，必須掌握有關程式的運作時間

2.4.2 互動式系統中的調用

1. 輪轉排程

   每個程序配置設定一個時間片。唯一需要考慮的是時間片的長度。

2. 優先級排程

   每個程序被賦予一個優先級，允許優先級最高的可運作程序先運作。通常在不同優先級内實作優先級排程，而在同一個優先級内實作輪轉排程，不過需要适時調整優先級否則低優先級的程式會饑餓。

3. 多級隊列

   為CPU密集型設定更長的時間片，并對優先級分類。比如有四個優先級類，中斷，IO，段時間片和長時間篇，每個優先級的cpu時間片不同長。

4. 最短程序優先

   如果可以估計目前作業的時間的話。

5. 保證排程

   一種完全不同的排程算法是想使用者作出明确的性能保證，然後實作它，比如說必須跟蹤程序子建立以來已使用了多少CPU時間，然後計算目前程序需要多少CPU，優先運作比例較低的程式，保證所有比較都互相接近

6. 彩票制度

   對不同的優先級分發不同的彩票數，彩票數和得到的cpu時間片比例相同。

   這樣做的好處是可以很快速的響應。

   如果程序阻塞可以交換彩票，待阻塞結束後

7. 公平分享排程

   根據使用者配置設定。

2.4.3 實時系統中的排程

硬實時/軟實時

可排程的

2.4.4 政策和機制

機制位于核心，政策交給使用者。由使用者設定優先級

2.4.5 線程排程

使用者級線程切換速度快，但是核心并不知道線程存在，程序内的一個線程可能占用該程序内的所有時間片，但是對其他程序的線程沒有影響。

核心級使用者切換速度慢，但是可以可以實作對線程更加精細的操作，同一個程序的各個線程都有時間片。