《處理機調度與死鎖》PPT課件

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

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

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

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

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

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

6、片輪轉調度算法最短剩余時間優(yōu)先調度算法均衡法多級反饋隊列調度算法3.3.1先來先服務調度算法其原則按照作業(yè)到達系統(tǒng)或進程進入就緒隊列先后次序來選擇。FIFO是一種非搶占算法。例題進程到達時間服務時間優(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進程不利，響應時間很高，尤其是進程執(zhí)行時間變化很大時3.3.2短作業(yè)(進程)優(yōu)先調度算法短作業(yè)(進程

7、)優(yōu)先調度算法SJ(P)F，是指對短作業(yè)或短進程優(yōu)先調度的算法。它們可以分別用于作業(yè)調度和進程調度。短作業(yè)優(yōu)先(SJF)的調度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調入內存運行。而短進程優(yōu)先(SPF)調度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調度。作業(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調

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