操作系統(tǒng)課件(2.3 處理器調(diào)度)

操作系統(tǒng)OperatingSystems徐小龍////xuxl@南京郵電大學(xué)NanjingUniversityofPostsandTelecommunicationsOS處理器調(diào)度WindowsLinuxMacOSOpenStackAndroidLinux處理器調(diào)度本講內(nèi)容1.處理器調(diào)度的層次2.處理器調(diào)度的算法3.單道環(huán)境下的調(diào)度4.多道環(huán)境下的調(diào)度5.低級(jí)調(diào)度方式算法

調(diào)度層次1中級(jí)調(diào)度新建態(tài)掛起就緒態(tài)掛起等待態(tài)高級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)等待態(tài)終止態(tài)處理器調(diào)度的層次作業(yè)是用戶向計(jì)算機(jī)提交的任務(wù)實(shí)體，而進(jìn)程則是完成任務(wù)的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位一個(gè)作業(yè)可由多個(gè)進(jìn)程組成，且必須至少由一個(gè)進(jìn)程組成，反過(guò)來(lái)不成立Linux等分時(shí)系統(tǒng)中，并不強(qiáng)調(diào)作業(yè)概念處理器調(diào)度的層次作業(yè)與進(jìn)程2處理器調(diào)度的算法調(diào)度原則2合理性：既要保證系統(tǒng)實(shí)現(xiàn)特殊功能要求，同時(shí)要對(duì)各個(gè)任務(wù)合理地分配到處理器份額有效性：處理器、內(nèi)存和I/O設(shè)備得到合理有效的分配，使系統(tǒng)資源得到充分的利用理想目標(biāo)3單位時(shí)間內(nèi)運(yùn)行盡可能多的作業(yè)使處理器盡可能保持“忙碌”響應(yīng)時(shí)間和周轉(zhuǎn)時(shí)間能夠盡可能短使各種I/O設(shè)備得以充分利用對(duì)所有的作業(yè)都是公平合理的處理器調(diào)度的算法設(shè)計(jì)理念4處理器調(diào)度的算法調(diào)度算法應(yīng)與系統(tǒng)設(shè)計(jì)目標(biāo)保持一致注意系統(tǒng)資源均衡使用保證提交的作業(yè)在截止時(shí)間內(nèi)完成設(shè)法縮短作業(yè)平均周轉(zhuǎn)時(shí)間大多數(shù)操作系統(tǒng)都采用比較簡(jiǎn)單的調(diào)度算法調(diào)度決策因素5作業(yè)到達(dá)時(shí)間預(yù)先為作業(yè)確定的優(yōu)先級(jí)作業(yè)所需的CPU時(shí)間其他的資源要求存儲(chǔ)要求處理器調(diào)度的算法性能衡量主要指標(biāo)6作業(yè)平均周轉(zhuǎn)時(shí)間假定有n個(gè)作業(yè)，其中作業(yè)i進(jìn)入系統(tǒng)時(shí)間為Si，它被選中執(zhí)行，得到結(jié)果的時(shí)間為Ei，其周轉(zhuǎn)時(shí)間為T(mén)i＝Ei–Si

則這批作業(yè)平均周轉(zhuǎn)時(shí)間為：處理器調(diào)度的算法

ri為作業(yè)i的實(shí)際執(zhí)行時(shí)間T：衡量不同調(diào)度算法對(duì)同一個(gè)作業(yè)流的性能W：同一調(diào)度算法對(duì)不同作業(yè)流的性能衡量性能衡量主要指標(biāo)6平均帶權(quán)周轉(zhuǎn)時(shí)間處理器調(diào)度的算法先來(lái)先服務(wù)算法FCFS最短作業(yè)優(yōu)先算法SJF最短剩余時(shí)間優(yōu)先算法SRTF處理器調(diào)度的算法典型算法7最高響應(yīng)比優(yōu)先算法HRN響應(yīng)比=作業(yè)周轉(zhuǎn)時(shí)間/作業(yè)處理時(shí)間=（作業(yè)處理時(shí)間+作業(yè)等待時(shí)間）/作業(yè)處理時(shí)間=1+（作業(yè)等待時(shí)間/作業(yè)處理時(shí)間）處理器調(diào)度本講內(nèi)容1.處理器調(diào)度的層次2.處理器調(diào)度的算法3.單道環(huán)境下的調(diào)度4.多道環(huán)境下的調(diào)度5.低級(jí)調(diào)度方式算法

單道環(huán)境下的調(diào)度作業(yè)進(jìn)入時(shí)間運(yùn)行時(shí)間（分鐘）JOB18：00120JOB28：5050JOB39：0010JOB49：5020先來(lái)先服務(wù)調(diào)度算法單道環(huán)境下的調(diào)度最短作業(yè)優(yōu)先調(diào)度算法單道環(huán)境下的調(diào)度最高響應(yīng)比優(yōu)先調(diào)度算法單道環(huán)境下的調(diào)度處理器調(diào)度本講內(nèi)容1.處理器調(diào)度的層次2.處理器調(diào)度的算法3.單道環(huán)境下的調(diào)度4.多道環(huán)境下的調(diào)度5.低級(jí)調(diào)度方式算法

兩道環(huán)境下有四個(gè)作業(yè)系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)被調(diào)度運(yùn)行后不再退出當(dāng)作業(yè)投入運(yùn)行后，可按照作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序多道環(huán)境下的調(diào)度作業(yè)進(jìn)入時(shí)間估計(jì)運(yùn)行時(shí)間（分鐘）JOB110：0030JOB210：0520JOB310：105JOB410：201010：00，JOB1進(jìn)入，JOB1被調(diào)入執(zhí)行10：05，JOB2到達(dá)，JOB2也被調(diào)入10：10，JOB3到達(dá)輸入井，JOB3不能進(jìn)入內(nèi)存10：20，JOB4到達(dá)輸入井，JOB4不能進(jìn)入內(nèi)存10：25，JOB2運(yùn)行結(jié)束，退出，JOB3進(jìn)入內(nèi)存10：30，JOB3運(yùn)行結(jié)束，退出，JOB4進(jìn)入內(nèi)存10：40，JOB4運(yùn)行結(jié)束，退出，JOB1繼續(xù)運(yùn)行11：05，JOB1運(yùn)行結(jié)束，退出多道環(huán)境下的調(diào)度作業(yè)進(jìn)入時(shí)間估計(jì)運(yùn)行時(shí)間（分鐘）JOB110：0030JOB210：0520JOB310：105JOB410：2010兩道環(huán)境下有四個(gè)作業(yè)多道環(huán)境下的調(diào)度處理器調(diào)度本講內(nèi)容1.處理器調(diào)度的層次2.處理器調(diào)度的算法3.單道環(huán)境下的調(diào)度4.多道環(huán)境下的調(diào)度5.低級(jí)調(diào)度方式算法

低級(jí)調(diào)度流程1記住進(jìn)程的狀態(tài)決定進(jìn)程什么時(shí)候獲得處理器決定進(jìn)程占用處理器多長(zhǎng)時(shí)間把處理器分配給進(jìn)程收回處理器低級(jí)調(diào)度方式算法可剝奪式（可搶占式Preemptive）：比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU，提供給具有更高優(yōu)先級(jí)的進(jìn)程使用，或是當(dāng)運(yùn)行進(jìn)程時(shí)間片用完后被剝奪不可剝奪式（不可搶占式Non-preemptive）：某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去低級(jí)調(diào)度方式算法低級(jí)調(diào)度方式2先來(lái)先服務(wù)算法時(shí)間片輪轉(zhuǎn)調(diào)度算法優(yōu)先權(quán)調(diào)度多級(jí)反饋隊(duì)列調(diào)度保證調(diào)度算法彩票調(diào)度算法低級(jí)調(diào)度方式算法先來(lái)先服務(wù)算法1按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序分配處理器進(jìn)程一旦占有處理器將一直運(yùn)行，直到結(jié)束或阻塞算法容易實(shí)現(xiàn)算法效率不高，不利于I/O頻繁的進(jìn)程低級(jí)調(diào)度方式算法時(shí)間片輪轉(zhuǎn)調(diào)度算法2就緒隊(duì)列中的每個(gè)進(jìn)程輪流地運(yùn)行一個(gè)時(shí)間片時(shí)間片結(jié)束時(shí)，強(qiáng)迫當(dāng)前進(jìn)程讓出處理器，等候下一輪調(diào)度算法可防止很少使用外圍設(shè)備的進(jìn)程過(guò)長(zhǎng)占用處理器，使要使用外圍設(shè)備的進(jìn)程有機(jī)會(huì)去啟動(dòng)外圍設(shè)備低級(jí)調(diào)度方式算法輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，進(jìn)程切換開(kāi)銷較大，開(kāi)銷與時(shí)間片的大小有關(guān)時(shí)間片取選低級(jí)調(diào)度方式算法時(shí)間片輪轉(zhuǎn)調(diào)度算法2時(shí)間片取值太小，多數(shù)進(jìn)程不能在一個(gè)時(shí)間片內(nèi)運(yùn)行完畢，切換頻繁，開(kāi)銷增大時(shí)間片取值太大，隨就緒隊(duì)列里進(jìn)程數(shù)目增加，輪轉(zhuǎn)一次的總時(shí)間增大，對(duì)每個(gè)進(jìn)程的響應(yīng)速度放慢了時(shí)間片大小的確定要從進(jìn)程個(gè)數(shù)、切換開(kāi)銷、系統(tǒng)效率和響應(yīng)時(shí)間等方面綜合考慮保證調(diào)度算法3對(duì)每個(gè)任務(wù)做出明確的性能保證，然后去實(shí)現(xiàn)它在一個(gè)有n個(gè)進(jìn)程運(yùn)行的系統(tǒng)中，保證每個(gè)進(jìn)程獲得CPU處理能力的1/n跟蹤各個(gè)進(jìn)程自創(chuàng)建以來(lái)已經(jīng)使用了多少CPU時(shí)間，根據(jù)各個(gè)進(jìn)程應(yīng)獲得的CPU時(shí)間，計(jì)算實(shí)際獲得的C