操作系統(tǒng)第6講課件

操作系統(tǒng)概念

第六講 CPU調(diào)度(1)OperatingSystemConceptionDavidfu上章回顧1、產(chǎn)生死鎖的四個(gè)必要條件？如何預(yù)防？OperatingSystemConceptionDavidfu本課總體綱要基本概念調(diào)度術(shù)語(yǔ)作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度OperatingSystemConceptionDavidfu基本概念CPU區(qū)間時(shí)間直方圖OperatingSystemConceptionDavidfuCPU調(diào)度當(dāng)CPU變?yōu)榭臻e時(shí)，操作系統(tǒng)就必須從就緒的隊(duì)列中選擇一個(gè)進(jìn)程來(lái)執(zhí)行。系統(tǒng)調(diào)度分為4級(jí)：作業(yè)調(diào)度交換調(diào)度進(jìn)程調(diào)度線程調(diào)度OperatingSystemConceptionDavidfu本課總體綱要基本概念調(diào)度術(shù)語(yǔ)作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度OperatingSystemConceptionDavidfuCPU作業(yè)調(diào)度作業(yè)調(diào)度功能：記錄系統(tǒng)中作業(yè)的狀況從后備作業(yè)隊(duì)列中挑選一批作業(yè)進(jìn)入執(zhí)行狀態(tài)被選中的作業(yè)分配資源建立進(jìn)程作業(yè)執(zhí)行結(jié)束后釋放所占用的資源作業(yè)調(diào)度目標(biāo)：對(duì)所有作業(yè)應(yīng)該公平合理較高的利用率每天執(zhí)行盡可能多的作業(yè)響應(yīng)時(shí)間快OperatingSystemConceptionDavidfu本課總體綱要基本概念調(diào)度術(shù)語(yǔ)作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度OperatingSystemConceptionDavidfu進(jìn)程調(diào)度功能功能包括：記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況選擇占有處理機(jī)的進(jìn)程進(jìn)行進(jìn)程上下文切換OperatingSystemConceptionDavidfu進(jìn)程上下文切換進(jìn)程上下文切換包括四個(gè)步驟：決定是否做上下文切換保存當(dāng)前執(zhí)行的進(jìn)程上下文采用合理的調(diào)度算法，選擇一個(gè)處于就緒狀態(tài)進(jìn)程恢復(fù)所選進(jìn)程的上下文，將控制權(quán)交給所選進(jìn)程OperatingSystemConceptionDavidfu進(jìn)程調(diào)度性能評(píng)價(jià)進(jìn)程調(diào)度性能的衡量是操作系統(tǒng)設(shè)計(jì)的一個(gè)重要指標(biāo)定性：調(diào)度的可靠性、簡(jiǎn)潔性定量：CPU利用率，進(jìn)程的等待/執(zhí)行率方法：對(duì)進(jìn)程調(diào)度的解析是十分困難的，一般采用模擬或測(cè)試系統(tǒng)響應(yīng)時(shí)間的方法OperatingSystemConceptionDavidfu本課總體綱要基本概念調(diào)度術(shù)語(yǔ)作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度功能進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程上下文切換進(jìn)程調(diào)度的性能評(píng)價(jià)調(diào)度算法先到先服務(wù)調(diào)度最短作業(yè)優(yōu)先調(diào)度優(yōu)先權(quán)調(diào)度輪轉(zhuǎn)法調(diào)度OperatingSystemConceptionDavidfu最短作業(yè)優(yōu)先調(diào)度最短作業(yè)優(yōu)先調(diào)度（SJF）將每個(gè)進(jìn)程與其下一個(gè)CUP區(qū)間段相關(guān)聯(lián)，當(dāng)CPU可用時(shí)，它會(huì)賦給具有最短后續(xù)CPU區(qū)間的進(jìn)程兩種方法非搶占性－一旦一個(gè)進(jìn)程開始執(zhí)行就需完成該次任務(wù)搶占性－如果新來(lái)的進(jìn)程CPU區(qū)間段比當(dāng)前進(jìn)程的時(shí)間段小，則優(yōu)先選擇新進(jìn)程。稱為SRTF(ShorestRemainingTimeFirst)SJF算法是最優(yōu)的。OperatingSystemConceptionDavidfu最短作業(yè)優(yōu)先調(diào)度進(jìn)程到達(dá)時(shí)間

區(qū)間時(shí)間

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(非搶占性)SJF平均等待時(shí)間=(0+(7-4)+(8-2)+(12-5))/4=4msFCFS平均等待時(shí)間＝（0＋(7-2)＋(11-4)＋(12-5))/4=4.75msP1P3P273160P4812OperatingSystemConceptionDavidfu最短作業(yè)優(yōu)先調(diào)度

Process ArrivalTime

BurstTime

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(搶占性)P1P3P242110P457P2P116平均等待時(shí)間=(9+1+0+2)/4=3OperatingSystemConceptionDavidfu最短作業(yè)優(yōu)先調(diào)度=0n+1=nRecenthistorydoesnotcount=1n+1=tn實(shí)際最后一個(gè)CPU區(qū)間記數(shù)。n+1=tn+(1-)tn

-1

+…

+(1-)j

tn

-j

+…

+(1-)n+10

因?yàn)閍nd(1-)小于或等于1,所以后面項(xiàng)的權(quán)比前面項(xiàng)權(quán)要小。OperatingSystemConceptionDavidfu最短作業(yè)優(yōu)先調(diào)度OperatingSystemConceptionDavidfu優(yōu)先權(quán)調(diào)度每個(gè)進(jìn)程都有優(yōu)先權(quán)具有最高優(yōu)先權(quán)的進(jìn)程分配給CPUSJF算法作為優(yōu)先權(quán)算法的特例。優(yōu)先權(quán)為下一個(gè)CPU區(qū)間的倒數(shù)。CPU區(qū)間越大，優(yōu)先權(quán)越小導(dǎo)致的問(wèn)題：饑餓（starvation)－低優(yōu)先權(quán)的進(jìn)程可能永遠(yuǎn)也不會(huì)運(yùn)行。（無(wú)窮阻塞）解決方案：老化(aging)－逐漸增加在系統(tǒng)中等待很長(zhǎng)時(shí)間的進(jìn)程的優(yōu)先權(quán)。OperatingSystemConceptionDavidfu輪轉(zhuǎn)法調(diào)度Process

BurstTime P1 53

P2 17

P3 68

P4 24甘特圖為（時(shí)間片q＝20ms):

特點(diǎn)：平均等待時(shí)間較高，但響應(yīng)較好P1P2P3P4P1P3