處理機(jī)調(diào)度與死鎖n-展示頁(yè)
2025-05-08 12:28本頁(yè)面
【正文】 ? 理解死鎖的基本概念 ? 掌握死鎖的處理方法 教學(xué)重點(diǎn) ：各種作業(yè)、進(jìn)程調(diào)度算法和死鎖 的處理方法等。 教學(xué)難點(diǎn) ：作業(yè)、進(jìn)程調(diào)度算法 , 死鎖 處理機(jī)調(diào)度的層次 對(duì)資源進(jìn)行有效的調(diào)度是非常必要的，我們生活中也會(huì)經(jīng)常遇到，如：調(diào)度銀行出納員服務(wù)顧客請(qǐng)求問題等。 處理機(jī)調(diào)度的層次 （作業(yè)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度） 作業(yè)和作業(yè)步 ? 作業(yè)：包含程序、數(shù)據(jù)和作業(yè)說明書 。 ? 內(nèi)容： ? 作業(yè)標(biāo)識(shí)，用戶名，作業(yè)類型，作業(yè)狀態(tài)，調(diào)度信息等 ? 進(jìn)入系統(tǒng)－ 建立 JCB插入相應(yīng)后備隊(duì)列 作業(yè)調(diào)度 作業(yè)控制－ 作業(yè)結(jié)束－ 回收資源 作業(yè)調(diào)度 ? 將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建 PCB等，插入就緒隊(duì)列。 ? 調(diào)度特性 ? 接納作業(yè)數(shù)（內(nèi)存駐留數(shù)，多道程序度） 太多 ――― 周轉(zhuǎn)時(shí)間 T長(zhǎng) 太少 ――― 系統(tǒng)效率低 ? 接納策略：即采用何種調(diào)度算法： FCFS、短作業(yè)優(yōu)先等 低級(jí)調(diào)度 （進(jìn)程調(diào)度，短程調(diào)度） 主要是決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)， 然后由分派程序（ Dispatcher）分派處理機(jī)。 中級(jí)調(diào)度（中程） 3. 2調(diào)度的隊(duì)列模型和調(diào)度準(zhǔn)則 就緒隊(duì)列 CPU 阻塞隊(duì)列 交互用戶 時(shí)間片完 進(jìn)程調(diào)度 進(jìn)程完成 等待事件 事件出現(xiàn) 、低級(jí)調(diào)度的隊(duì)列模型 就緒隊(duì)列 CPU 阻塞隊(duì)列 時(shí)間片完 進(jìn)程調(diào)度 進(jìn)程完成 等待事件 1 事件 1出現(xiàn) 后備隊(duì)列 阻塞隊(duì)列 等待事件 2 事件 2出現(xiàn) 作業(yè)調(diào)度 就緒隊(duì)列 CPU 就緒、掛起隊(duì)列 時(shí)間片完 進(jìn)程調(diào)度 進(jìn)程完成 后備隊(duì)列 阻塞、掛起隊(duì)列 事件出現(xiàn) 作業(yè)調(diào)度 阻塞隊(duì)列 等待事件 掛起 事件出現(xiàn) 中級(jí)調(diào)度 交互型作業(yè) 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 面向用戶的準(zhǔn)則 （ 1）周轉(zhuǎn)時(shí)間短（常用于批處理系統(tǒng)） 概念：作業(yè)從提交 ―― 完成的時(shí)間 .分為： ? 駐外存等待調(diào)度時(shí)間 ? 駐內(nèi)存等待調(diào)度時(shí)間 ? 執(zhí)行時(shí)間 ? 阻塞時(shí)間 面向用戶的準(zhǔn)則 ? 平均周轉(zhuǎn)時(shí)間 ? 平均帶權(quán) ? 可見帶權(quán) w越小越好 ,Ts為實(shí)際服務(wù)時(shí)間 。 ——是一個(gè)資源分配問題 （進(jìn)程）優(yōu)先調(diào)度算法 （ FCFS） ? 特點(diǎn)：簡(jiǎn)單，有利于長(zhǎng)作業(yè)（進(jìn)程） 即 CPU繁忙性作業(yè) ,不利于短作業(yè)（進(jìn)程） （進(jìn)程）優(yōu)先調(diào)度算法： SJ(P)F ? 提高了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間（從而提高了系統(tǒng)吞吐量） ? 特點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能得不到服務(wù) ? 估計(jì)時(shí)間不易確定 先來(lái)先服務(wù)算法實(shí)例 圖 34 FCFS和 SJ(P)F比較 ? 非搶占式優(yōu)先權(quán)算法 ? 搶占式優(yōu)先權(quán)算法，實(shí)時(shí)性更好。 ? 確定優(yōu)先權(quán)依據(jù) ? 進(jìn)程類型 ? 進(jìn)程對(duì)資源的需求； ? 根據(jù)用戶需求。 （例子 MIT IBM7049 ） (2) 2）動(dòng)態(tài)優(yōu)先權(quán)： ? 如：優(yōu)先權(quán)隨執(zhí)行時(shí)間而下降，隨等待時(shí)間而升高。 ? （ 2） Ts（要求服務(wù)時(shí)間）相同的進(jìn)程間相當(dāng)于FCFS。 22 常見的批處理作業(yè)調(diào)度算法 ?先來(lái)先服務(wù)算法（ FCFS： First Come First Serve） ?最短作業(yè)優(yōu)先算法（ SJF： Shortest Job First） ?最短剩余時(shí)間優(yōu)先（ SRTF: Shortest Remaining Time First） ?最高響應(yīng)比優(yōu)先算法（ HRRF： Highest Response Ratio First） 響應(yīng)比 R = 響應(yīng)時(shí)間 /要求服務(wù)時(shí)間 =（等待時(shí)間 +要求服務(wù)時(shí)間） /要求服務(wù)時(shí)間 = 1 +（等待時(shí)間 /要求服務(wù)時(shí)間） 23 ?基于優(yōu)先數(shù)調(diào)度算法 （ HPF： Highest Priority First） （ a）由用戶規(guī)定優(yōu)先數(shù)（外部?jī)?yōu)先數(shù)） 用戶提交作業(yè)時(shí)，根據(jù)急迫程度規(guī)定適當(dāng)?shù)膬?yōu)先數(shù)，作業(yè)調(diào)度程序根據(jù) JCB優(yōu)先數(shù)決定進(jìn)入內(nèi)存的次序。 就緒隊(duì)列 1 至 CPU S1 就緒隊(duì)列 2 S2 至 CPU 就緒隊(duì)列 3 S3 至 CPU 就緒隊(duì)列 n Sn 至 CPU 時(shí)間片： S1S2S3 圖 3－ 5多級(jí)隊(duì)列反饋調(diào)度算法 36 進(jìn)程調(diào)度算法 對(duì)下表，分別采用先來(lái)先服務(wù)（ FCFS）、非搶占最短進(jìn)程優(yōu)先（ SPF）及搶占的最短剩余時(shí)間優(yōu)先（ SRT）、高響應(yīng)比優(yōu)先（ HRRN）、時(shí)間片輪轉(zhuǎn)（ RR,時(shí)間片 q=1）、多級(jí)反饋隊(duì)列（ FB，第 i級(jí)隊(duì)列的時(shí)間片 =2i1）調(diào)度算法進(jìn)行 CPU調(diào)度，求出各進(jìn)程的執(zhí)行情況以及平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 先來(lái)先服務(wù)（ FCFS） 短作業(yè) /進(jìn)程優(yōu)先（ SJ(P)F） 降低對(duì)長(zhǎng)進(jìn)程有利的一種方法就是短進(jìn)程優(yōu)先策略： 表 SPF 的調(diào)度性能 WT進(jìn)程 到達(dá)時(shí)間Tin 服務(wù)時(shí)間Tr 開始時(shí)間Ts 結(jié)束時(shí)間Tc = 0 3 11 15 9 3 9 15 20 11 TA=3 TB=7 TC=11 TD=14 TE=3 = 8 3 6 4 5 2 2 0 4 6 A B C D E → → → → WE= WA=1 WB= WC= WD= E C D A B 周轉(zhuǎn)時(shí)間 T=結(jié)束時(shí)間 Tc到達(dá)時(shí)間 Tin=30=3 周轉(zhuǎn)時(shí)間 T 帶權(quán)周轉(zhuǎn)時(shí)間 W=周轉(zhuǎn) 時(shí)間 T/服務(wù)時(shí)間 Tr=3/3=1 帶權(quán)周轉(zhuǎn)時(shí) 間 W 平均 結(jié)束 下一步 下一步下一步下一步下一步下一步下一步 SJF對(duì)短作業(yè)有利，明顯的作業(yè) E提前接受了服務(wù)，并且整體性能也得到了提高； SJF的問題： ? SJF需要事先知道或至少需要 估計(jì)每個(gè)作業(yè)所需的處理機(jī)時(shí)間 。 ? SJF 偏向短作業(yè)，不利于分時(shí)系統(tǒng)（由于不可搶占性）。 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 FCFS SPF HRRN T進(jìn)程 調(diào)度算法 最短剩余時(shí)間（ SRT） ? SRT是針對(duì) SPF 增加了 強(qiáng)占機(jī)制 的一種調(diào)度算法，它總是 選擇預(yù)期剩余時(shí)間最短的進(jìn)程 。 ? SRT不象 FCFS偏向長(zhǎng)進(jìn)程，也不象輪轉(zhuǎn)法（下個(gè)算法）產(chǎn)生額外的中斷，從而 減少了開銷 。 ? 從周轉(zhuǎn)時(shí)間
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1