《處理機調(diào)度與死鎖》PPT課件

《《處理機調(diào)度與死鎖》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2作業(yè)調(diào)度3.3調(diào)度算法3.4實時調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除3.1處理機調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度處理器調(diào)度分為三級：高級調(diào)度（作業(yè)調(diào)度）（長程調(diào)度）中級調(diào)度（中期調(diào)度）低級調(diào)度（進(jìn)程調(diào)度）（短程調(diào)度）按某種原則從后備狀態(tài)挑選作業(yè)調(diào)入內(nèi)存運行為作業(yè)創(chuàng)建進(jìn)程為選中作業(yè)分配資源1.高級調(diào)度(LowLevelScheduling)2.中程調(diào)度決定哪些作業(yè)允許參于競爭處理機資源。作用：起到短期調(diào)整系統(tǒng)負(fù)荷，以平順系統(tǒng)。方式：“掛起”，“解

2、掛”。3.低級調(diào)度按某種原則將處理機分配給就緒進(jìn)程。進(jìn)程調(diào)度屬操作系統(tǒng)內(nèi)核，執(zhí)行頻率很高。進(jìn)程調(diào)度是最基本的一種調(diào)度，它可以采用非搶占方式或搶占方式。1)非搶占方式(Non-preemptiveMode)在采用非搶占調(diào)度方式時，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個：①正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；②執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；③在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。2)搶

3、占方式(PreemptiveMode)搶占的原則有：優(yōu)先權(quán)原則。(2)短作業(yè)(進(jìn)程)優(yōu)先原則。(3)時間片原則。4.處理機三級調(diào)度關(guān)系新建就緒掛起阻塞掛起就緒阻塞運行退出長程調(diào)度長程調(diào)度中程調(diào)度中程調(diào)度進(jìn)程調(diào)度調(diào)度和進(jìn)程狀態(tài)轉(zhuǎn)換3.1.2調(diào)度隊列模型1.僅有進(jìn)程調(diào)度的調(diào)度隊列模型僅具有進(jìn)程調(diào)度的調(diào)度隊列模型2.具有高級和低級調(diào)度的調(diào)度隊列模型具有高、低兩級調(diào)度的調(diào)度隊列模型就緒隊列的形式。(2)設(shè)置多個阻塞隊列。圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。3.同時具有三級調(diào)度的調(diào)度隊列模型具有三級調(diào)

4、度時的調(diào)度隊列模型就緒隊列進(jìn)程調(diào)度CPU就緒掛起隊列中級調(diào)度阻塞掛起隊列阻塞隊列等待事件進(jìn)程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.2.1作業(yè)調(diào)度的職能記錄已進(jìn)入系統(tǒng)的作業(yè)情況JCB調(diào)度算法：按照某種調(diào)度算法從后備狀態(tài)挑選作業(yè)運行。運行準(zhǔn)備：為選中作業(yè)創(chuàng)建進(jìn)程，分配主存和外設(shè)。結(jié)束善后處理：收回資源，輸出必要信息。作業(yè)進(jìn)入后備狀態(tài)建立作業(yè)退出系統(tǒng)時撤消3.2作業(yè)調(diào)度3.2.2作業(yè)控制塊作業(yè)存在唯一標(biāo)志作業(yè)調(diào)度的依據(jù)記錄作業(yè)的有關(guān)信息，反映作業(yè)運行情況內(nèi)容進(jìn)入系統(tǒng)時建立退出系統(tǒng)時撤消作業(yè)名資源要求資源使用情況類型說明狀態(tài)

5、3.2.3調(diào)度性能的衡量平均周轉(zhuǎn)時間：作業(yè)kTk=Tck-Tsk=T等待+T運行平均周轉(zhuǎn)時間T=1/n?Tk帶權(quán)周轉(zhuǎn)時間：作業(yè)kWk=Tk/TRk平均帶權(quán)周轉(zhuǎn)時間W=1/n?WkK=1nK=1nTck：作業(yè)K完成時間Tsk：作業(yè)K提交時間TRk：作業(yè)K運行時間3.2.4選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則周轉(zhuǎn)時間短。響應(yīng)時間快。(3)截止時間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。2.面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。3.3調(diào)度算法先進(jìn)先服務(wù)調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法最高響應(yīng)比優(yōu)先時間

6、片輪轉(zhuǎn)調(diào)度算法最短剩余時間優(yōu)先調(diào)度算法均衡法多級反饋隊列調(diào)度算法3.3.1先來先服務(wù)調(diào)度算法其原則按照作業(yè)到達(dá)系統(tǒng)或進(jìn)程進(jìn)入就緒隊列先后次序來選擇。FIFO是一種非搶占算法。例題進(jìn)程到達(dá)時間服務(wù)時間優(yōu)先數(shù)10322265344346565821作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)5039131820T=1/5（3+7+9+12+12）=8.60W=1/5（1+1.17+2.25+2.40+6.00）=2.56特點:吞吐量不定、耗費最小、無饑餓、對偏重于I/O進(jìn)程不利，響應(yīng)時間很高，尤其是進(jìn)程執(zhí)行時間變化很大時3.3.2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法短作業(yè)(進(jìn)程

7、)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選出一估計運行時間最短的進(jìn)程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。作業(yè)1作業(yè)2作業(yè)5作業(yè)3作業(yè)4039111520T=1/5（3+7+11+14+3）=7.60W=1/5（1+1.17+2.75+2.80+1.50）=1.84SJ(P)F調(diào)

8、度算法也存在不容忽視的缺點：(1)該算法對長作業(yè)不利，更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊列(就緒隊列)，