15.1處理機調(diào)度概念

CPU資源的時分復(fù)用

■進程切換：CPU資源的當前占用者切換

保存當前進程在PCB中的執(zhí)行上下文(CPU狀態(tài))

恢復(fù)下一個進程的執(zhí)行上下文

■處理機調(diào)度

從就緒隊列中挑選下一個占用CPU運行的進程

從多個可用CPU中挑選就緒進程可使用的CPU資源

■調(diào)度程序：挑選就緒進程的內(nèi)核函數(shù)

調(diào)度策略

依據(jù)什么原則挑選進程/線程曙咽？

調(diào)度時機

什么時候進行調(diào)度蛔趴？

調(diào)度時機

■內(nèi)核運行調(diào)度程序的條件

進程從運行狀態(tài)切換到等待狀態(tài)

進程被終結(jié)了

■非搶占系統(tǒng)

當前進程主動放棄CPU時

■可搶占系統(tǒng)

中斷請求被服務(wù)例程響應(yīng)完成時

當前進程被搶占

進程時間片用完

進程從等待切換到就緒

精髓：

操作系統(tǒng)根據(jù)進程的執(zhí)行對三種類型的調(diào)度方案做出選擇。長程調(diào)度確定何時允許一個新進程進入系統(tǒng)例朱。中程調(diào)度是交換功能的一部分孝情，它確定何時把一個程序的部分或全部取進內(nèi)存鱼蝉，使得該程序能夠被執(zhí)行。短程調(diào)度確定哪一個就緒進程下一次被處理器執(zhí)行箫荡。

15.2調(diào)度準則

處理機資源的使用模式

■進程在CPU計算和I/O操作間交替

每次調(diào)度決定在下一個CPU計算時將哪個工作交給CPU

在時間片機制下魁亦，進程可能在結(jié)束當前CPU計算前被迫放棄CPU（對進程執(zhí)行不利）

比較調(diào)度算法的準則

■CPU使用率

CPU處于忙狀態(tài)的時間百分比（需要是CPU盡可能的忙）

■吞吐量

單位時間內(nèi)完成的進程數(shù)量

■周轉(zhuǎn)時間

進程從初始化到結(jié)束的總時間(包括進入內(nèi)存、在就緒隊列中等待羔挡、在CPU上執(zhí)行和I/O執(zhí)行洁奈。通常受輸出設(shè)備速度的限制）

■等待時間

進程在就緒隊列中的總時間

■響應(yīng)時間

從提交請求到產(chǎn)生響應(yīng)所花費的總時間

吞吐量與延遲

■調(diào)度算法的要求

希望“更快”的服務(wù)

■什么是更快？

傳輸文件時的高帶寬绞灼，調(diào)度算法的高吞吐量

玩游戲時的低延遲利术，調(diào)度算法的低響應(yīng)延遲

這兩個因素是獨立的

■與水管的類比

低延遲：喝水的時候想要一打開水龍頭水就流出來

高帶寬：給游泳池充水時希望從水龍頭里同時流出大量的水，并且不介意是否存在延遲

概念：需要使CPU使用率和吞吐量最大化低矮，而使周轉(zhuǎn)時間印叁、等待時間和相應(yīng)時間最小化。

處理機調(diào)度策略的響應(yīng)時間目標

■減少響應(yīng)時間

及時處理用戶的輸入請求军掂，盡快將輸出反饋給用戶

■減少平均響應(yīng)時間的波動

在交互系統(tǒng)中轮蜕，可預(yù)測性比高差異低平均更重要

■低延遲調(diào)度改善了用戶的交互體驗

如果移動鼠標時，屏幕中的光標沒動蝗锥，用戶可能會重啟電腦

■響應(yīng)時間是操作系統(tǒng)的計算延遲

處理機調(diào)度策略的吞吐量目標

■增加吞吐量

減少開銷（操作系統(tǒng)開銷跃洛，上下文切換）

系統(tǒng)資源的高效利用（CPU，I/O設(shè)備）

■減少等待時間

減少每個進程的等待時間（可以提高它的響應(yīng)性能也可以提高它的吞吐量的性能）

■操作系統(tǒng)需要保證吞吐量不受用戶交互的影響

操作系統(tǒng)必須不時進行調(diào)度玛追，即使存在許多交互任務(wù)

■吞吐量是操作系統(tǒng)的計算帶寬

處理機調(diào)度的公平性目標

■公平的定義

保證每個進程占用相同的CPU時間

保證每個進程的等待時間相同

■公平通常會增加平均響應(yīng)時間

15.3調(diào)度算法

先來先服務(wù)算法(First Come First Served, FCFS)

■依據(jù)進程進入就緒狀態(tài)的先后順序排列

進程進入等待或結(jié)束狀態(tài)時（進程主動讓出cpu）税课，就緒隊列中的下一個進程占用CPU

■優(yōu)點

簡單

■缺點

·平均等待時間波動較大

短進程可能排在長進程后面

·I/O資源和CPU資源的利用率較低

CPU密集型進程會導(dǎo)致I/O設(shè)備閑置時，I/O密集型進程也等待

短進程優(yōu)先算法(SPN)

■選擇就緒隊列中執(zhí)行時間最短進程占用CPU進入運行狀態(tài)

就緒隊列按預(yù)期的執(zhí)行時間來排序

■短剩余時間優(yōu)先算法(SRT)

SPN算法的可搶占改進

■優(yōu)點

短進程優(yōu)先算法具有最優(yōu)平均周轉(zhuǎn)時間

■缺點

·可能導(dǎo)致饑餓

連續(xù)的短進程流會使長進程無法獲得CPU資源

·需要預(yù)知未來

如何預(yù)估下一個CPU計算的持續(xù)時間痊剖？

簡單的解決辦法：詢問用戶

用戶欺騙就殺死相應(yīng)進程

用戶不知道怎么辦韩玩？

■短進程優(yōu)先算法的執(zhí)行時間預(yù)估

用歷史的執(zhí)行時間來預(yù)估未來的執(zhí)行時間

最高響應(yīng)比優(yōu)先算法(HRRN)

■選擇就緒隊列中響應(yīng)比R值最高的進程

Ｒ＝（ｗ+s)/s

w:等待時間(waiting time)

s:執(zhí)行時間(service time)

在短進程優(yōu)先算法的基礎(chǔ)上改進

不可搶占

關(guān)注進程的等待時間

防止無限期推遲

時間片輪轉(zhuǎn)算法(RR, Round-Robin)

■時間片

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

■算法思路

時間片結(jié)束時，按FCFS算法切換到下一個就緒進程

每隔(n–1)個時間片進程執(zhí)行一個時間片q

注：分配了一個基本時間單元q陆馁，每個進程每次在時間片q的時間內(nèi)執(zhí)行找颓，沒完成則繼續(xù)排隊尾，完成了結(jié)束叮贩。

時間片為20的RR算法示例

時間片輪轉(zhuǎn)算法中的時間片長度

■RR算法開銷

額外的上下文切換

■時間片太大（退化成FCFS）

等待時間過長

極限情況退化成FCFS

■時間片太小

反應(yīng)迅速击狮，但產(chǎn)生大量上下文切換

大量上下文切換開銷影響到系統(tǒng)吞吐量

■時間片長度選擇目標

選擇一個合適的時間片長度

經(jīng)驗規(guī)則：維持上下文切換開銷處于1%以內(nèi)

比較FCFS和RR

多級隊列調(diào)度算法(MQ)

■就緒隊列被劃分成多個獨立的子隊列

如：前臺(交互)、后臺(批處理)

■每個隊列擁有自己的調(diào)度策略

如：前臺–RR益老、后臺–FCFS

■隊列間的調(diào)度

·固定優(yōu)先級

先處理前臺彪蓬，然后處理后臺

可能導(dǎo)致饑餓

·時間片輪轉(zhuǎn)

每個隊列都得到一個確定的能夠調(diào)度其進程的CPU總時間

如：80%CPU時間用于前臺，20%CPU時間用于后臺

多級反饋隊列算法(MLFQ)

注：例：分三個執(zhí)行隊列捺萌，0隊列的時間片是8档冬，1隊列的時間片是24，2隊列采用FCFS。不超過8的進程有最高優(yōu)先級酷誓，接下來依次披坏。在隊列0中未執(zhí)行完的進程將會排至隊列1末尾，隊列1中未執(zhí)行完的排隊列2尾盐数。

■進程可在不同隊列間移動的多級隊列算法

時間片大小隨優(yōu)先級級別增加而增加（優(yōu)先級高時間片邪舴鳌）

如進程在當前的時間片沒有完成，則降到下一個優(yōu)先級（執(zhí)行時間越長玫氢，優(yōu)先級調(diào)的越低）

■MLFQ算法的特征

CPU密集型進程的優(yōu)先級下降很快帚屉，優(yōu)先級會逐步降低，并且時間片會分的很大

I/O密集型進程停留在高優(yōu)先級

公平共享調(diào)度(FSS, Fair Share Scheduling)

■FSS控制用戶對系統(tǒng)資源的訪問

一些用戶組比其他用戶組更重要（用戶分組琐旁，根據(jù)重要程度）

保證不重要的組無法壟斷資源

未使用的資源按比例分配

沒有達到資源使用率目標的組獲得更高的優(yōu)先級

傳統(tǒng)調(diào)度算法總結(jié)

■先來先服務(wù)算法

不公平涮阔，平均等待時間較差

■短進程優(yōu)先算法

不公平，平均周轉(zhuǎn)時間最小

需要精確預(yù)測計算時間

可能導(dǎo)致饑餓

■最高響應(yīng)比優(yōu)先算法（主要考慮等待時間）

基于SPN調(diào)度

不可搶占

■時間片輪轉(zhuǎn)算法

公平灰殴，但是平均等待時間較差敬特，交互性很好

■多級反饋隊列

多種算法的集成

■公平共享調(diào)度

公平是第一要素

概念：先到先服務(wù)〔FCFS)調(diào)度是最簡單的調(diào)度算法，但是它會讓短進程等待非常長的進程牺陶。最短作業(yè)優(yōu)先(SJF)調(diào)度可證明是最佳的伟阔，它提供了最短平均等待時間。實現(xiàn)SJF調(diào)度比較困難掰伸，因為預(yù)測下一個CPU區(qū)間的長度有難度皱炉。SJF算法是通用優(yōu)先級調(diào)度算法（將CPU簡單地分配給具有最高優(yōu)先級的進程)的特例。優(yōu)先級和SJF調(diào)度會產(chǎn)生饑餓狮鸭。老化技術(shù)（隨等待時間增加逐漸提高優(yōu)先級）可阻止饑餓合搅。

輪轉(zhuǎn)法(RR)調(diào)度對于分時(交互)系統(tǒng)更為合適。RR調(diào)度讓就緒隊列的第一個進程使用CPU的q個時間單元歧蕉，這里q是時間片灾部。在q時間單元之后，如果該進程還沒有釋放CPU惯退，那么它被搶占并放到就緒隊列的尾部赌髓。該算法是主要問題是選擇時間片。如果時間片太大催跪，那么RR調(diào)度就成了FCFS調(diào)度:

如果時間片太小锁蠕，那么因上下文切換而引起的調(diào)度開銷就過大。

FCFS算法是非搶占的懊蒸，而RR算法是搶占的荣倾。SJF和優(yōu)先級算法可以是搶占的，也可以是非搶占的骑丸。

多級隊列調(diào)度算法允許多個不同算法用于各種類型的進程舌仍。最為常用的模型包括使用RR調(diào)度的前臺交互隊列鳖孤，以及使用FCFS調(diào)度的后合批處理隊列。多級反饋隊列調(diào)度算法允許進程在隊列之間遷移抡笼。

15.5實時調(diào)度

實時操作系統(tǒng)

■實時操作系統(tǒng)

正確性依賴于其時間和功能兩方面的操作系統(tǒng)

■實時操作系統(tǒng)的性能指標

時間約束的及時性（deadlines）

速度和平均性能相對不重要

■實時操作系統(tǒng)的特性

時間約束的可預(yù)測性

實時操作系統(tǒng)分類

■強實時操作系統(tǒng)

要求在指定的時間內(nèi)必須完成重要的任務(wù)

■弱實時操作系統(tǒng)

重要進程有高優(yōu)先級，要求盡量但非必須完成

實時任務(wù)

■任務(wù)（工作單元）

一次計算黄鳍，一次文件讀取推姻，一次信息傳遞等等

■任務(wù)屬性

完成任務(wù)所需要的資源

定時參數(shù)

周期實時任務(wù)

■周期實時任務(wù)：一系列相似的任務(wù)

任務(wù)有規(guī)律地重復(fù)

周期p =任務(wù)請求時間間隔(0

執(zhí)行時間e =最大執(zhí)行時間(0 < e < p)

使用率U = e/p

軟時限和硬時限

■硬時限（Hard deadline）

錯過任務(wù)時限會導(dǎo)致災(zāi)難性或非常嚴重的后果

必須驗證，在最壞情況下能夠滿足時限

■軟時限(Soft deadline)

通常能滿足任務(wù)時限

如有時不能滿足框沟，則降低要求

盡力保證滿足任務(wù)時限

可調(diào)度性

■可調(diào)度表示一個實時操作系統(tǒng)能夠滿足任務(wù)時限要求

需要確定實時任務(wù)的執(zhí)行順序

靜態(tài)優(yōu)先級調(diào)度（事先把執(zhí)行順序排出來藏古，按這個順序調(diào)度，理論上保證能夠滿足要求）

動態(tài)優(yōu)先級調(diào)度（執(zhí)行過程中給出執(zhí)行順序）

實時調(diào)度

■速率單調(diào)調(diào)度算法(RM, Rate Monotonic)（靜態(tài)）

通過周期安排優(yōu)先級

周期越短優(yōu)先級越高

執(zhí)行周期最短的任務(wù)

■最早截止時間優(yōu)先算法(EDF, Earliest Deadline First)動態(tài)

截止時間越早優(yōu)先級越高

執(zhí)行截止時間最早的任務(wù)

15.5（2）多處理器調(diào)度

■多處理機調(diào)度的特征

多個處理機組成一個多處理機系統(tǒng)

處理機間可負載共享

■對稱多處理器(SMP, Symmetric multiprocessing)調(diào)度

每個處理器運行自己的調(diào)度程序

調(diào)度程序?qū)蚕碣Y源的訪問需要進行同步

對稱多處理器（SMR）的進程分配

■靜態(tài)進程分配

進程從開始到結(jié)束都被分配到一個固定的處理機上執(zhí)行

每個處理機有自己的就緒隊列

調(diào)度開銷小

各處理機可能忙閑不均

■動態(tài)進程分配

進程在執(zhí)行中可分配到任意空閑處理機執(zhí)行

所有處理機共享一個公共的就緒隊列

調(diào)度開銷大

各處理機的負載是均衡的

概念：

處理器親和性：絕大多數(shù)SMP系統(tǒng)試圖避免將進程從一個處理器移至另一個處理器忍燥，而是努力使一個進程在同一個處理器上運行

負載平衡（load balancing）：Push migration,pull mifration拧晕。

對稱多線程（SMT）：通過提供多個物理處理器，SMP系統(tǒng)允許同時運行幾個線程梅垄。另一種方法是提供多個邏輯（而不是物理邏輯）處理器來實現(xiàn)厂捞。SMT是硬件而不是軟件提供的。

15.6優(yōu)先級反置(Priority Inversion)

■操作系統(tǒng)中出現(xiàn)高優(yōu)先級進程長時間等待低優(yōu)先級進程所占用資源的現(xiàn)象

■基于優(yōu)先級的可搶占的調(diào)度算法存在優(yōu)先級反置

注：已經(jīng)排好的執(zhí)行隊列中有T1队丝。T2兩個進程靡馁，T1的優(yōu)先級比T2低，這是一個處于中間的進程T3搶占T1机久，三個都要用的資源L1現(xiàn)在被T3占用臭墨，這就是優(yōu)先級反置。

解決方法：優(yōu)先級繼承（Priority Inheritance）膘盖，優(yōu)先級天花板協(xié)議（priority ceiling protocol）

優(yōu)先級繼承（Priority Inheritance）

■占用資源的低優(yōu)先級進程繼承申請資源的高優(yōu)先級進程的優(yōu)先級

只在占有資源的低優(yōu)先級進程被阻塞時,才提高占有資源進程的優(yōu)先級

優(yōu)先級天花板協(xié)議（priority ceiling protocol）

■占用資源進程的優(yōu)先級和所有可能申請該資源的進程的最高優(yōu)先級相同

不管是否發(fā)生等待,都提升占用資源進程的優(yōu)先級

優(yōu)先級高于系統(tǒng)中所有被鎖定的資源的優(yōu)先級上限胧弛，任務(wù)執(zhí)行臨界區(qū)時就不會被阻塞