一、處理機調度概念

進程切換（上下文切換）：切換CPU的當前任務，從一個進程/線程到另一個，保存當前在PCB/TCB中的執行上下文，讀取下一個的上下文

CPU調度：從就緒隊列中挑選一個進程/線程作為CPU將要運行的下一個線程/進程

調度程序：挑選進程/線程的內核函數（通過一切調度策略）使得效率最高，滿足用戶需求

在進程/線程的生命周期中的什么時候進行調度？

1. 從一個狀態變為另一個狀態，特別是和運行（running）相關的狀態。
2. 內核運行調度程序的條件：進程從運行狀態切換到等待狀態or終結了（done）
3. 不可搶占調度，調度必須等待事件/進程結束，早期OS。
4. 現在多為可以搶占的進程，OS決定在何時打斷進程，調度程序在中斷被響應后執行，當前進程從運行切換到就緒，或者一個進程從等待切換到就緒，可以被換出。

針對的是用戶態的進程。

進程在內核中通過系統調用執行，因為系統調用返回時是到發起這個調用的進程繼續執行，所以內核中不會切換，搶占。只要進程在系統調用時不存在從運行態到阻塞態的變化，OS可以確保返回正常。

二、調度準則

1、處理機資源的使用模式

CPU的占用率是波狀，CPU大量運算是高峰，而讀寫I/O時是平穩的低值。每個調度決定都是關于下一個CPU突發時將哪個工作交給CPU，在時間分片下，線程可能在結束當前CPU突發前被迫放棄CPU。?

程序在CPU突發和I/O中交替，CPU占用率高說明是在充分地使用CPU。

2、比較調度算法的準則

1. CPU使用率：CPU處于忙狀態的時間百分比
2. 吞吐量：單位時間內完成的進程數量
3. 周轉時間：一個進程從初始化到結束包括（所有等待時間）所花費的總時間，周轉時間=等待時間+服務時間
4. 等待時間：進程在就緒隊列中的總時間，進程從就緒態到運行態的時間。
5. 響應時間：一個請求被提交到第一次響應所花費的總時間

2、吞吐量與延遲

要求：希望更快的服務。什么是更快？

• 高帶寬：吞吐量高 （傳輸文件）
• 低延遲：響應時間快（玩游戲）

3、調度算法的響應時間目標

• 減少響應時間：及時處理用戶的輸入請求，盡快發饋給用戶
• 減少平均響應時間的波動：交互系統中，可預測性比高差異低平均更重要
• 低延遲調度改善用戶的交互體驗?
• 響應時間是操作系統的計算延遲

4、調度策略的吞吐量目標

• 增加吞吐量：減少開銷（操作系統開銷，上下文切換）?、系統資源的高效利用（CPU,I/O設備）
• 減少等待時間
• 操作系統需要保證吞吐量不受用戶交互的影響

5、處理機調度的公平性目標

• 公平的定義：保證每個進程占用相同的CPU時間；保證每個進程的等待時間相同
• 公平通常會增加平均響應時間

三、先來先服務、短進程優先和最高響應比優先調度算法

1、FCFS first come first served先來先服務算法

依據進程進入就緒狀態的先后順序排列

如果前面的進程運行的時間長，后面的進程就只能等著，導致周轉時間慢。如果進程阻塞了，隊列中的下一個會得到CPU

優點：簡單?

缺點：平均等待時間波動大，花費時間少的可能反而排在后面，可能導致CPU和I/O之間的重疊處理，沒考慮搶占，CPU密集的進程導致I/O閑置時，I/O密集型進程也在等。

2、短進程優先算法

選擇就緒隊列中執行時間最短進程占用CPU進入運行狀態，就緒隊列按預期的執行時間來排序；

短進程優先算法具有最優平均周轉時間

• 不可搶占：SJF、SPN
• 可搶占：ready queue中的第一個進程正在運行時，來了一個比它的預測完成時間還短的進程，SPT

優點：最小的平均等待時間和周轉時間

缺點：可能導致長任務饑餓，不能保證公平；需要預知未來下一個進程的時間，比如詢問用戶，如果用戶欺騙就殺死進程。

短進程優先算法的執行時間預估：根據執行歷史看將來CPU突發的持續時間，遞歸展開

3、最高響應比優先算法（HRRN）

選擇就緒隊列中響應比R值最高的進程

• R=（w+s）/s
• w:等待時間（waiting time）
• s:執行時間（service time)

在短進程優先算法的基礎上改進；不可搶占；關注進程的等待時間；防止無限期推遲。

四、時間輪轉、多級反饋隊列、公平共享調度算法和ucore調度框架

1、時間片輪換算法（RR）

時間片：分配處理機資源的基本時間單元

算法思路：用時間切片和搶占來輪流執行，強調了公平。在量子切片/時間切片的離散單元中分配處理器，時間片結束時切換到下一個準備好的進程?

時間片長度

• 開銷： 額外的上下文切換；
• 時間片太大則等待時間過長會退化成FCFS，
• 太小反應迅速但吞吐量由于大量的上下文切換開銷受影響?；
• 選擇一個合適的時間片，經驗是維持上下文切換開銷處于1%以內，現在LINUX是千分之一秒

2、多級隊列調度算法（MQ）

就緒隊列分為多個相對獨立的隊列，每個隊列擁有自己的調度策略。

隊列間的調度：

1. 固定優先級：先高優先級，再處理低優先級，可能導致饑餓
2. 時間切片輪轉：每個隊列都得到一個確定的，調度其進程的CPU總時間，如80%給前臺，20%給后臺

3、多級反饋隊列算法（MLFQ）

• 時間片大小隨優先級增加而增加
• 若當前時間量子中沒有完成就給當前任務則降到下一個優先級

進程調度先是I/O密集型，CPU密集型隨著不斷消耗時間片就下降到低的優先級，保證I/O密集型任務停留在高優先級?

等待時間越長，優先級越高，服務時間越長優先級越低?，能動態地根據進程的特征調整隊列和調度

4、公平共享調度（FSS）

在用戶級別實現公平共享?

FFS 一些用戶組比其他組更重要，保證不重要的組無法壟斷資源，未使用的資源按照每個組所分配的資源的比例來分配，沒有達到資源使用率目標的組獲得更高的優先級

5、評價調度方法

確定性建模，對確定的工作量計算每個算法的表現
隊列模型：用來處理隨機工作負載的數學方法
實現/模擬：建立一個允許算法運行實際數據的系統，最靈活，一般性

五、實時調度和多處理器調度

1、實時調度

• 定義：正確性依賴于其時間和功能兩方面的一種OS
• 性能指標：時間約束的及時性（deadlines），速度和平均性能相對不重要，
• 重點是時間約束的可預測性。
• 實時任務：任務/工作單元（一次計算，一次文件讀取，一次信息傳遞等等）?
• 任務屬性：取得進展所需要的資源和實時參數?
• 任務請求時間（release time）：進程處于就緒態的時間?
• 相對截止時間（relative deadline）: 任務是間隔時間段完成，每個任務有個特定的時間，要在特定的時間段內完成?
• 絕對截止時間（absolute deadline）：最終的結束時間

周期任務：一系列相似的任務，有規律的重復

• 周期p=任務請求時間間隔 (0 < p)?
• 執行時間e=最大執行時間，最大執行時間< p?
• 使用率/利用率：U=e/p

2、類別?

• 硬實時系統/強實時系統：如果某個任務沒完成有嚴重后果，比須驗證，在最壞情況下能夠滿足時限
• 軟實時系統/弱實時系統：重要的進程優先級更高，要盡量完成，如看視頻，幀數沒控制好會掉幀。

3、實時調度算法

• 速率單調調度算法（RM）：通過周期安排優先級，周期越短優先級越高，執行周期最短的任務；
• 最早截止時間優化算法（EDF）：截止時間越早優先級越高，執行截止時間最早的任務

對于實時系統來說，有兩種調度策略，一是靜態調度策略，一個是動態調度策略。靜態調度策略是指按照進程執行時間長短進行調度，執行時間短的先執行。動態調度策略是按照進程截止時間進行調度，截止時間越早的先執行。

4、多處理器調度?

• 要考慮：1，任務來了，放在哪個CPU上執行？2，怎么考慮公平性？load balance負載平衡?
• 多處理器的CPU調度更加復雜，多個相同的單處理器組成一個多處理器，優點是負載共享。對稱多處理器(SMP)，每個處理器運行自己的調度程序，需要在調度程序中同步

多處理機是指由多個處理機組成一個多處理機系統，處理機之間可以實現負載共享。其中每個處理器有自己的調度程序，調度程序對共享資源的訪問需要進行同步。多處理機調度策略中最重要的一點是一個進程應該分配給哪一個處理機。靜態進程分配是進程從開始到結束都分配到一個固定的處理機上執行，之后就是在每個處理機上的單處理機調度算法，但這會導致處理機利用率不均。動態進程分配則是一個進程可以分配到任意空閑處理機執行，所有處理機共享一個就緒隊列，調度開銷較大，但負載均衡。

六、優先級反置

優先級反置是指高優先級進程要請求的資源被低優先級進程占用而被阻塞，此時中優先級進程反而搶占了CPU導致高優先級進程始終無法運行。針對這一現象有兩種解決方案：一是優先級繼承，導致高優先級進程阻塞的低優先級進程會暫時繼承高優先級進程的優先級，避免被中間優先級進程搶占；二是優先級天花板協議，占有資源的進程和所有可能申請該資源的進程的優先級比較，設置成其中最高優先級對應的優先級，這樣就不會有進程阻止他使用這個資源，可能會出現優先級濫用的情況。

?