第09章-單處理器調(diào)度

第九章單處理器調(diào)度廈門大學(xué)軟件學(xué)院

吳清強(qiáng)操作系統(tǒng)調(diào)度類型多道程序設(shè)計(jì)的關(guān)鍵是調(diào)度調(diào)度的類型調(diào)度類型說明長程調(diào)度決定加入到待執(zhí)行的進(jìn)程池中中程調(diào)度決定加入到部分或全部在內(nèi)存中的進(jìn)程集合中短程調(diào)度決定哪一個(gè)可用進(jìn)程將被處理器執(zhí)行I/O調(diào)度決定哪一個(gè)進(jìn)程掛起的I/O請(qǐng)求將被可用的I/O設(shè)備處理39.1處理器調(diào)度的類型調(diào)度的目標(biāo)：把進(jìn)程指定到一個(gè)處理器或多個(gè)處理器中執(zhí)行響應(yīng)時(shí)間吞吐率處理器效率49.1處理器調(diào)度的類型圖9.1調(diào)度和進(jìn)程狀態(tài)轉(zhuǎn)換59.1處理器調(diào)度的類型圖9.2調(diào)度的層次9.1處理器調(diào)度的類型圖9.3用于調(diào)度的隊(duì)列圖79.1.1長程調(diào)度決定哪一個(gè)程序可以進(jìn)入到系統(tǒng)中被處理控制了多道程序設(shè)計(jì)的程度進(jìn)程越多，每個(gè)進(jìn)程用于執(zhí)行的時(shí)間片就越少89.1.2中程調(diào)度屬于交換功能的一部分換入（Swapped-In）換出（Swapped-Out)99.1.3短程調(diào)度也稱為分派器（Dispatcher）執(zhí)行頻率最大在一個(gè)事件發(fā)生時(shí)被激活時(shí)鐘中斷I/O中斷系統(tǒng)調(diào)用信號(hào)109.2（短程）調(diào)度算法按照優(yōu)化系統(tǒng)行為的一個(gè)或多個(gè)方面的方式來分配處理器時(shí)間（需要評(píng)價(jià)準(zhǔn)則）面向用戶，與性能相關(guān)周轉(zhuǎn)時(shí)間響應(yīng)時(shí)間最后期限面向用戶，其它可預(yù)測性9.2.1短程調(diào)度準(zhǔn)則119.2.1短程調(diào)度準(zhǔn)則

面向系統(tǒng)，與性能相關(guān)吞吐量處理器使用率面向系統(tǒng)，其它公平強(qiáng)制優(yōu)先級(jí)平衡資源129.2.2優(yōu)先級(jí)每個(gè)進(jìn)程被指定一個(gè)優(yōu)先級(jí)，調(diào)度器總是選擇具有最高優(yōu)先級(jí)的進(jìn)程多個(gè)優(yōu)先級(jí)，多個(gè)就緒進(jìn)程隊(duì)列低優(yōu)先級(jí)的進(jìn)程可能饑餓允許一個(gè)進(jìn)程動(dòng)態(tài)改變優(yōu)先級(jí)執(zhí)行歷史等待時(shí)間139.2.3選擇調(diào)度策略選擇函數(shù)：確定在就緒進(jìn)程中選擇哪個(gè)進(jìn)程在下一次執(zhí)行基于優(yōu)先級(jí)基于資源需求基于進(jìn)程執(zhí)行特性w：花費(fèi)的等待時(shí)間e：到現(xiàn)在為止，花費(fèi)的執(zhí)行時(shí)間s：進(jìn)程所需要的總服務(wù)時(shí)間，包括e決策模式（DecisionMode）非搶占搶占新進(jìn)程到達(dá)中斷發(fā)生后，把一個(gè)被阻塞的進(jìn)程置為就緒狀態(tài)周期性的時(shí)間片中斷（*）149.2.3選擇調(diào)度策略定義：進(jìn)程周轉(zhuǎn)時(shí)間（Tr）=結(jié)束時(shí)間-到達(dá)時(shí)間=駐留時(shí)間=等待時(shí)間+服務(wù)時(shí)間（Ts）歸一化周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間（運(yùn)行時(shí)間）=Tr/

Ts

159.2.3調(diào)度策略之調(diào)度算法先來先服務(wù)（FCFS）每個(gè)進(jìn)程就緒后，就加入就緒隊(duì)列當(dāng)前正在運(yùn)行的進(jìn)程停止執(zhí)行后，選擇在就緒隊(duì)列中存在時(shí)間最長的進(jìn)程運(yùn)行短進(jìn)程可能要等待很長時(shí)間偏向受處理器限制的進(jìn)程169.2.3調(diào)度策略之調(diào)度算法輪轉(zhuǎn)基于時(shí)鐘的搶占使用的時(shí)間片長度時(shí)鐘中斷、執(zhí)行調(diào)度和分派函數(shù)都是需要花費(fèi)代價(jià)避免時(shí)間片太短指導(dǎo)思想：時(shí)間片最好略大于一次典型的交互所需要的時(shí)間179.2.3調(diào)度策略之調(diào)度算法輪轉(zhuǎn)周期性發(fā)生時(shí)鐘中斷當(dāng)中斷發(fā)生時(shí)，正在運(yùn)行的進(jìn)程進(jìn)入就緒隊(duì)列下一個(gè)進(jìn)程被選擇運(yùn)行189.2.3調(diào)度策略之調(diào)度算法輪轉(zhuǎn)受I/O限制的進(jìn)程和受處理器限制的進(jìn)程不公平使用處理器受I/O限制的進(jìn)程使用少受處理器限制的進(jìn)程使用多

改進(jìn)：虛擬輪轉(zhuǎn)法（VRR）輔助隊(duì)列優(yōu)先級(jí)高當(dāng)一個(gè)進(jìn)程從輔助隊(duì)列中調(diào)度時(shí)，它的運(yùn)行時(shí)間不會(huì)長于基本時(shí)間段減去它上次從就緒隊(duì)列中被選擇運(yùn)行的總時(shí)間199.2.3調(diào)度策略之調(diào)度算法最短進(jìn)程優(yōu)先（SPN）非搶占式策略就緒隊(duì)列中預(yù)計(jì)服務(wù)時(shí)間最短的進(jìn)程被選擇運(yùn)行長進(jìn)程可能饑餓難點(diǎn)：需要知道或者至少估計(jì)每個(gè)進(jìn)程所需要的時(shí)間（估計(jì)不正確，OS可能中斷執(zhí)行）209.2.3調(diào)度策略之調(diào)度算法最短進(jìn)程優(yōu)先（SPN）進(jìn)程執(zhí)行時(shí)間簡單估計(jì)：指數(shù)平滑：指數(shù)平滑比簡單估計(jì)能夠更快地跟蹤進(jìn)程行為的變化的值越大，對(duì)觀測值變化的反應(yīng)就越快21229.2.3調(diào)度策略之調(diào)度算法最短剩余時(shí)間（SRT）SPN的搶占機(jī)制版需要估算進(jìn)程剩下的時(shí)間長進(jìn)程可能饑餓239.2.3調(diào)度策略之調(diào)度算法最高響應(yīng)比優(yōu)先（HRRN）響應(yīng)比：w：等待處理器的時(shí)間s：期待的服務(wù)時(shí)間（運(yùn)行時(shí)間）選擇響應(yīng)比最大的進(jìn)程執(zhí)行249.2.3調(diào)度策略之調(diào)度算法反饋懲罰運(yùn)行時(shí)間較長的進(jìn)程剩余時(shí)間不好估計(jì)已運(yùn)行時(shí)間可獲得

搶占（時(shí)間片）+動(dòng)態(tài)優(yōu)先級(jí)FCFSFCFSRR259.2.3調(diào)度策略之調(diào)度算法反饋長進(jìn)程周轉(zhuǎn)時(shí)間可能驚人增加有可能出現(xiàn)饑餓（新進(jìn)程不斷進(jìn)入系統(tǒng)）

改變搶占次數(shù)

RQ0:執(zhí)行一個(gè)時(shí)間單位RQ1：執(zhí)行兩個(gè)時(shí)間單位

RQi：執(zhí)行2i個(gè)時(shí)間單位

長進(jìn)程仍然可能餓死

當(dāng)一個(gè)進(jìn)程在當(dāng)前隊(duì)列中等待服務(wù)的時(shí)間超過一定的時(shí)間量之后，把它提升到一個(gè)優(yōu)先級(jí)較高的隊(duì)列中269.2.4性能比較沒有絕對(duì)好的調(diào)度策略調(diào)度策略好壞因使用環(huán)境而異作業(yè)復(fù)習(xí)題：9.3、9.5習(xí)題：9.1、9.16補(bǔ)充：彩票調(diào)度算法基本思想：向進(jìn)程提供各種系統(tǒng)資源（如CPU時(shí)間）的彩票。一旦需要做出一項(xiàng)調(diào)度決策時(shí)，就隨機(jī)抽出一張彩票，擁有該彩票的進(jìn)程獲得該資源。實(shí)際使用：在應(yīng)用到CPU調(diào)度時(shí)，系統(tǒng)可以掌握每秒鐘50次的一種彩票，作為獎(jiǎng)勵(lì)每個(gè)獲獎(jiǎng)?wù)呖梢缘玫?0ms的CPU時(shí)間。補(bǔ)充：彩票調(diào)度算法不同重要性進(jìn)程的彩票：可以給更重要的進(jìn)程額外的彩票，以便增加它們獲勝的機(jī)會(huì)。如果出售了100張彩票，而有一個(gè)進(jìn)程持有其中的20張，那么在每一次抽獎(jiǎng)中該進(jìn)程就有20%的取勝機(jī)會(huì)。在較長的運(yùn)行中，該進(jìn)程會(huì)得到20%的CPU。相反，對(duì)于優(yōu)先級(jí)調(diào)度程序，很難說明擁有優(yōu)先級(jí)40究竟是什么意思，而這里的規(guī)則很清楚：擁有彩票f份額的進(jìn)程大約得到系統(tǒng)資源的f份額。補(bǔ)充：彩票調(diào)度算法進(jìn)程協(xié)作：如果希望協(xié)作進(jìn)程可以交換它們的彩票。例如，有一個(gè)客戶進(jìn)程向服務(wù)器進(jìn)程發(fā)送消息后就被阻塞，該客戶進(jìn)程可以把它所有的彩票交給服務(wù)器，以便增加該服務(wù)器下次運(yùn)行的機(jī)會(huì)。在服務(wù)器運(yùn)行完成之后，該服務(wù)器再把彩票還給客戶機(jī)，這樣客戶機(jī)又可以運(yùn)行了。事實(shí)上，如果沒有客戶機(jī)，服務(wù)器根本就不需要彩票。補(bǔ)充：公平分享調(diào)度用戶公平性：到現(xiàn)在為止，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身，并不關(guān)注其所有者是誰。這樣做的結(jié)果是，如果用戶1啟動(dòng)9個(gè)進(jìn)程而用戶2啟動(dòng)1個(gè)進(jìn)程，使用輪轉(zhuǎn)或相同優(yōu)先級(jí)調(diào)度算法，那么用戶1將得到90%的CPU時(shí)間，而用戶2只得到10%的CPU時(shí)間。補(bǔ)充：公平分享調(diào)度解決方案：為了避免這種情形，某些系統(tǒng)在調(diào)度處理之前考慮誰擁有進(jìn)程這一因素。在這種模式中，每個(gè)用戶分配到CPU時(shí)間的一部分，而調(diào)度程序以一種強(qiáng)制的方式選擇進(jìn)程。這樣，如果兩個(gè)用戶都得到獲得50%CPU時(shí)間的保證，那么無論一個(gè)用戶有多少進(jìn)程存在，每個(gè)用戶都會(huì)得到應(yīng)有的CPU份額。補(bǔ)充：公平分享調(diào)度例子：作為一個(gè)例子，考慮有兩個(gè)用戶的一個(gè)系統(tǒng)，每個(gè)用戶都保證獲得50%CPU時(shí)間。用戶1有4個(gè)進(jìn)程A、B、C和D，而用戶2只有1個(gè)進(jìn)程E。如果采用輪轉(zhuǎn)調(diào)度，一個(gè)