[計(jì)算機(jī)軟件及應(yīng)用]os-03中斷與處理機(jī)調(diào)度-文庫吧
2025-03-30 00:42 本頁面
【正文】 非剝奪的策略 ，其原則是下一次選擇所需處理時(shí)間最短的進(jìn)程，因此，短進(jìn)程將會越過長進(jìn)程，得到優(yōu)先運(yùn)行 ? SPN策略的難點(diǎn)在于需要知道或至少需要估計(jì)每個(gè)進(jìn)程所需要的處理時(shí)間 ? 長進(jìn)程可能被 “ 餓死 ” 調(diào)度算法 ?最短剩余時(shí)間優(yōu)先調(diào)度算法 (SRTN) ? 對 SPN增加剝奪機(jī)制。當(dāng)一個(gè)時(shí)鐘中斷周期到后，調(diào)度程序總是 選擇預(yù)期剩余時(shí)間最短 的進(jìn)程 ? 當(dāng)一個(gè)新進(jìn)程加入就緒隊(duì)列時(shí)，它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時(shí)間，因此，調(diào)度程序?qū)儕Z當(dāng)前程序，將處理器分配給新進(jìn)程。 ? 和 SPN一樣，調(diào)度程序必須有關(guān)于處理時(shí)間的估計(jì)，并且存在長進(jìn)程被餓死的危險(xiǎn) 調(diào)度算法 ?最高響應(yīng)比優(yōu)先調(diào)度算法（ HRRN） ? 響應(yīng)比： R=(w+s)/s=1+w/s w表示等待時(shí)間； s表示執(zhí)行所需時(shí)間 ? 最高響應(yīng)比也是對最短進(jìn)程法的一種改進(jìn)，當(dāng)當(dāng)前進(jìn)程完成或被阻塞時(shí)， 選擇響應(yīng)比最大的進(jìn)程先執(zhí)行 ，是一種 非剝奪 的策略。 ? 響應(yīng)比 R，代表了進(jìn)程的年齡，算法在保證短進(jìn)程優(yōu)先的同時(shí)又兼顧了長進(jìn)程 —— 折中 調(diào)度算法 ?最高響應(yīng)比優(yōu)先調(diào)度算法（ HRRN） ? R=(w+s)/s=1+w/s ? 當(dāng)一系列進(jìn)程同時(shí)進(jìn)入系統(tǒng)時(shí)，由于短作業(yè) s值小， R值就大，因此短作業(yè)得到了優(yōu)先執(zhí)行。 ? 但隨著長作業(yè)等待的時(shí)間 (w)增長， R值不斷增大，到達(dá)一定的等待時(shí)間，長進(jìn)程最終將憑借年齡的增長戰(zhàn)勝短進(jìn)程，從而獲得處理器。 ? 可見，在 HRRN算法中，長作業(yè)不會被餓死 調(diào)度算法 ?優(yōu)先級調(diào)度算法：按進(jìn)程的優(yōu)先級調(diào)度，選擇就緒隊(duì)列中優(yōu)先級最高的進(jìn)程到處理機(jī)上運(yùn)行。 ?優(yōu)先數(shù)確定方式： ? 靜態(tài)優(yōu)先級：每個(gè)進(jìn)程創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該優(yōu)先數(shù)在進(jìn)程整個(gè)生命周期都是固定不變的。 ? 動態(tài)優(yōu)先級：每個(gè)進(jìn)程被創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該優(yōu)先數(shù)在進(jìn)程的生命周期內(nèi)是可以動態(tài)變化的 調(diào)度算法 ? 大多數(shù)動態(tài)優(yōu)先級設(shè)計(jì)方案 ? 把交互式和 I/O頻繁的進(jìn)程移到優(yōu)先級隊(duì)列的頂端，而讓計(jì)算量大的進(jìn)程移到較低的優(yōu)先級上 ? 對與優(yōu)先級相同的進(jìn)程，按先來先服務(wù)或輪轉(zhuǎn)法則分配處理機(jī) ? 對于一給定時(shí)間周期，一個(gè)正在運(yùn)行的進(jìn)程，每請求一次 I/O操作后其優(yōu)先級就自動加 1，直接反映出 I/O請求的頻率，從而使 I/O設(shè)備具有很高的利用率 調(diào)度算法 ?優(yōu)先級調(diào)度算法分類： ? 非搶占的優(yōu)先級調(diào)度法 ：一旦一個(gè)高優(yōu)先級的進(jìn)程占有了處理器，就一直運(yùn)行下去，直到因等待某事被阻塞或執(zhí)行結(jié)束，才選擇就緒隊(duì)列中優(yōu)先級最高的進(jìn)程來執(zhí)行。 ? 可搶占的優(yōu)先級調(diào)度法 ：任何時(shí)刻都按照高優(yōu)先級進(jìn)程在處理器上運(yùn)行的原則進(jìn)行進(jìn)程調(diào)度。當(dāng)一高優(yōu)先級進(jìn)程運(yùn)行時(shí)，若有一更高優(yōu)先級進(jìn)程到達(dá)就緒隊(duì)列，則當(dāng)前運(yùn)行進(jìn)程立刻將處理器讓給更高優(yōu)先級的進(jìn)程（即使未處理完，也無遇到阻塞情況） 調(diào)度算法 最高優(yōu)先數(shù)算 法 ? 可搶占 CPU – Process Arrival time Priority Burst time ? P1 0 0 8 ? P2 2 1 5 ? P3 4 3 7 ? P4 0 2 3 ? P5 5 7 2 ? Gantt Chart 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 最 高優(yōu)先數(shù)算 法 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 ?輪轉(zhuǎn)調(diào)度 (簡單輪轉(zhuǎn)法 RR) ? 系統(tǒng)把所有就緒進(jìn)程按先后次序排隊(duì)，處理機(jī)總是優(yōu)先分配給就緒隊(duì)列中的第一個(gè)就緒進(jìn)程，并分配它一個(gè)固定的時(shí)間片 (如 50毫秒 ) ? 當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時(shí)間片時(shí)，被迫釋放處理機(jī)給下一個(gè)處于就緒隊(duì)列中的第一個(gè)進(jìn)程 ,自己回到就緒隊(duì)列的尾部，并等待下次調(diào)度 ? 當(dāng)某個(gè)正在運(yùn)行的進(jìn)程的時(shí)間片尚未用完，但進(jìn)程需要 I/O時(shí)，該進(jìn)程被送到相應(yīng)阻塞隊(duì)列，等 I/O完成重新返回到就緒隊(duì)列尾部，等待調(diào)度。 調(diào)度算法 簡單輪轉(zhuǎn)法 RR 處理器 就緒隊(duì)列 阻塞隊(duì)列 分派 釋放 超時(shí) 等待事件 事件發(fā)生 ?輪轉(zhuǎn)調(diào)度 ? 簡單輪轉(zhuǎn)法是以就緒隊(duì)列中的所有進(jìn)程均以相同的速度往前推進(jìn)為其特征。其時(shí)間片的長短，影響著進(jìn)程的進(jìn)展速度 ? 當(dāng)就緒進(jìn)程很多時(shí)，如果時(shí)間片很長，就會影響一些需要“緊急”運(yùn)行的作業(yè)。同樣這對短作業(yè)和要求 I/O 操作多的作業(yè)顯然是不利的 ? 因而，在簡單輪轉(zhuǎn)法的基礎(chǔ)上又提出了分級輪轉(zhuǎn)法 調(diào)度算法 ?分級輪轉(zhuǎn)法 – 將一個(gè)就緒隊(duì)列根據(jù)進(jìn)程的優(yōu)先級不同，劃分二個(gè)或二個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先級，甚至可以分配不同的時(shí)間片 – 一般情況下，調(diào)度算法把相同的時(shí)間片分配給優(yōu)先級高的就緒隊(duì)列中的隊(duì)首進(jìn)程 – 只有當(dāng)優(yōu)先級高的就緒隊(duì)列中的所有進(jìn)程全部運(yùn)行完畢或等待 I/O操作而沒有進(jìn)程運(yùn)行時(shí)，才把處理機(jī)分配給低優(yōu)先級就緒隊(duì)列中的進(jìn)程 調(diào)度算法 高優(yōu)先級就緒隊(duì)列 低優(yōu)先級就緒隊(duì)列 處理器 分級輪轉(zhuǎn)調(diào)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1