5 操作系統調度

• 1. 調度機制
• • 1.1 長期、中期、短期調度
• 2. 單核調度策略
• • 2.1 經典調度
  • 2.2 優先級調度
  • 2.3 公平共享調度
  • 2.4 實時調度
• 3. 多核調度策略
• • 3.1 負載分擔
  • 3.2 協同調度
  • 3.3 兩級調度
  • 3.4 負載追蹤與負載均衡

---

1. 調度機制

1.1 長期、中期、短期調度

進程調度機制負責進程在這些狀態間的轉換。進程調度根據職責的不同，具體分為長期、中期、短期調度。

• 長期調度的觸發間隔較長，它粗粒度地決定是否應該將一個新的進程納人調度管理，負責增加系統中可被調度的進程的數量。
• 中期調度的觸發相對頻繁，它輔助換頁機制，負責限制系統中可被調度的進程的數量。
• 短期調度的觸發最為頻繁，它負責細粒度地調度進程的執行，做出相應的調度決策。

2. 單核調度策略

2.1 經典調度

• 先到先得(FIFO / FCFS)：
  選取運行隊列中的第一個任務，將其移出運行隊列并執行;當一個任務執行完后，它會被再次放入運行隊列的隊尾。
  • 缺點：
  • 在長短任務混合的場景下對短任務不友好。
• 最短任務優先(SJF)：
  調度時會選擇運行時間最短的任務執行。
  • 缺點：
  • 必須預知任務的運行時間。
  • 其表現嚴重依賴于任務到達時間點
• 最短完成時間任務優先(STCF)：
  • 缺點：
  • 長任務饑餓。
  • 需要預知任務的運行時間。

非搶占式調度：調度器必須等一個任務執行完或者主動退出執行才能升始下—個調度。
搶占式調度：任務到達系統時會進行調度，有可能會中斷當前正在執行的任務，轉而執行其他任務。

• 時間片輪轉(RR)：
  需要為任務設置時間片，限定任務每次執行的時間。當前任務執行完時間片后，就切換到運行隊列中的下一個任務。
  • 缺點
  • 在任務運行時間相似的場景下平均周轉時間高。

響應時間：指的是從用戶發起請求到任務響應用戶所需的時間。
時間片：每個請求一次可以占用多長時間的資源。

2.2 優先級調度

優先級：會根據重要程度給每個請求分配優先級，優先級高的請求可以優先使用資源。

• 多級隊列(MLQ)：
  • 每個任務會被分配預先設置好的優先級，每個優先級對應一個隊列，任務會被存儲在對應的優先級隊列中。如果優先級不同的任務同時處于預備狀態，那么調度器應該傾向于調度優先級較高的任務，因此一個任務必須等到所有優先級比它高的任務調度完才可以被調度。處于相同優先級隊列的任務。它們內部的調度方式沒有統一標準，可以針對性地為不同隊列采用不同調度策略，例如FCPS策略或RR策略。
    [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-w69jd02I-1661672910708)(https：//img-blog.csdnimg.cn/6375960d780b4c1cb786b051f79a5fbd.png)]
  • 缺點：

  • 低優先級任務饑餓 [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-CYLJOcEC-1661672910709)(https：//img-blog.csdnimg.cn/2fe2d6fca3bf48be968a6d1e42e39286.png)]

  • 優先級反轉：

優先級反轉：
?假設現在有3個任務A、B、C，它們的優先級為A＞B＞C。任務C在運行時持有一把鎖，然后它被高優先級的任務A搶占了(任務C的鎖沒有被釋放)。此時任務A恰巧也想申請任務C持有的鎖，但是申請失敗，因此進人阻塞狀態等待任務C放鎖。此時，任務B、C都處于可以運行的狀態，由于任務B的優先級高于C，因此B優先運行。綜合觀察該情況，就會發現任務B好像優先級高于任務A，先于任務A執行。這一問題稱為優先級反轉。
優先級繼承：
?任務A通過將自己的優先級轉移給占有鎖的任務C，讓任務C優先執行并放鎖。之后，任務A可在任務C放鎖后以搶占的方式立即執行，從而避免了優先級反轉的問題。

• 多級反饋隊列(MLFQ)：
  • 短任務擁有更高的優先級
  • 低優先級的任務采用更長的時間片
  • 定時地將所有任務的優先級提升至最高

2.3 公平共享調度

這類調度器會量化任務對系統資源的占有比例，從而實現對資源的公平調度。我們將以份額(share)來量化每個任務對CPU時間的使用。

• 彩票調度
• 步幅調度

2.4 實時調度

根據任務超過截至時間所造成的后果來分類：

• 硬實時任務：
  該類任務必須在截止時間前完成，否則系統無法承擔任務處理超過截止時間的后果。
• 軟實時任務：
  該類任務可以偶爾超過截止時間完成，其結果是可接受的。

根據被觸發的時間來分類：

• 周期任務：
  指到達系統時間遵循一定周期的任務。
• 偶發任務：
  指不會周期性地到達系統的任務，且還要滿足連續兩個相同偶發任務到達系統的時間間隔有最小值，即系統不會在同—時刻處理兩個相同的偶發任務。
• 非周期任務：
  指到達系統時間隨機的任務。

實時操作系統的特點是確定性，即實時任務的完成時間應該是有明確上界的。
實時調度策略：

• 速度單調(RM)：
  該調度策略需要預知任務的周期T，并且根據周期靜態地為每個任務分配一個優先級，任務的周期越短，意味著其截止時間要求越迫切，則其優先級越高。RM策略還支持搶占調度，高優先級的任務可以搶占低優先級的任務執行。
• 最早截至時間優先(EDF)：
  任務的截止時間越近則優先級越高。

3. 多核調度策略

3.1 負載分擔

?多核共享—個全局運行隊列。當一個CPU核心需要調度任務時，根據給定的調度策略，決定全局運行隊列中下一個由它執行的任務。給定的調度策略可以是單核調度中的任一策略。

3.2 協同調度

?盡可能讓一組任務并行執行，避免調度器同時調度有依賴關系的兩組任務，同時避免關聯任務(傾向于同時執行的—系列任務，比如需要相互通信的任務)執行效率降低的問題。

• 群組調度：
  將關聯任務設置為一組(gang)，并以組為單位調度任務在多個CPU核心上執行，使它們的開始時間和結束時間接近相同。

3.3 兩級調度

?全局調度器會使得任務在不同CPU核心上切換執行，造成切換開銷。為了減少開銷，每個任務應盡可能只在一個CPU核心上進行調度。因此，新的調度策略改為每個CPU核心都引人一個本地調度器，并用它管理對應核心上執行的任務。這種調度策略使用全局調度器和本地調度器，構成了層級化結構，—般稱之為兩級調度(two level scheduling)。

3.4 負載追蹤與負載均衡

?通過追蹤每個CPU核心當前的負載情況，將處于高負載的CPU核心管理的任務遷移到低負載的CPU核心上，盡可能地保證每個核心的負載大致相同。

• 調度實體粒度負載追蹤
• 負載均衡

總結

以上是生活随笔為你收集整理的【5 操作系统调度】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。