【正文】 C B E → → → → WE= WA=1 WB= WC= WD= E C D A B 周轉時間 T=結束時間 Tc到達時間 Tin=30=3 周轉時間 T 帶權周轉時間 W=周轉 時間 T/服務時間 r=3/3=1 帶權周轉時 間 W 平均 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 D → B剩余時間 =61=5； C剩余時間 =40=4； 0500結束 下一步 下一步下一步下一步下一步下一步 最短剩余時間（ SRT） 不同調度算法的性能對比分析 : W進程 到達時間 Tin 服務時間 Tr 從平均周轉時間及其平均帶權周轉時間來看，SRT 好于前面的任何一個算法。 ? 必須記錄過去的服務時間，從而 增加了開銷 。只要新進程就緒 ，且有更短的剩余時間，調度程序就可能搶占當前正在運行的進程。 短作業(yè) /進程優(yōu)先（ SJF） 表 HRRN的調度性能 WT進程 到達時間Tin 服務時間Tr 開始時間Ts 結束時間Tc = 0 3 9 15 13 3 9 13 20 15 TA=3 TB=7 TC=9 TD=14 TE=7 = 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 周轉時間 T=結束時間 Tc到達時間 Tin=30=3 周轉時間 T 帶權周轉時間 W=周轉 時間 T/服務時間 Tr=3/3=1 帶權周轉時 間 W 平均 =[(94)+4]/4= =[(96)+5]/5= =[(98)+2]/2= RC RD RE D=[(136)+5]/5=E =[(138)+2]/2= 結束 下一步 下一步下一步 下一步下一步 最高響應比（ HRRN） 不同調度算法對的性能分析 : W進程 到達時間 Tin 服務時間 Tr 從平均周轉時間及其平均帶權周轉時間來看，HRRN 剛好介于 FCFS與 SPF之間，即好于FCFS，次于 SPF。 ? 只要不斷的有短作業(yè)進入系統，就有可能使長作業(yè)長期得不到運行而 “ 餓死 ” 。 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 FCFS 的調度性能 T W進程 到達時間Tin 服務時間 Tr 開始時間Ts 結束時間Tc 周轉時間 T 帶權周轉時間W A 0 3 0 3 TA=3 WA=1 B 2 6 3 9 TB=7 WB= C 4 4 9 13 TC=9 WC= D 6 5 13 18 TD=12 WD=. E 8 2 18 20 TE=12 WE=6 平均 = = 同樣，看到進程 E的不利情況。 （ b）由系統計算優(yōu)先數（內部優(yōu)先數） 例：可按如下公式計算作業(yè)的優(yōu)先數： 優(yōu)先數 = 用戶規(guī)定優(yōu)先數 –作業(yè)處理時間 + 作業(yè)等待時間 –輸出量 24 25 26 27 28 29 30 31 32 ? 時間片大小的確定 ? 太大：退化為 FCFS； ? 太?。合到y開銷過大 ? 系統對響應時間的要求； T=nq ? 就緒隊列中進程的數目； ? 系統的處理能力：（應保證一個時間片處理完常用命令） （ 2） ? 特點：長、短作業(yè)兼顧，有較好的響應時間 ? 短作業(yè)一次完成； ? 中型作業(yè)周轉時間不長； ? 大型作業(yè)不會長期不處理。 ? （ 3）長作業(yè)等待一段時間仍能得到服務。 ? 優(yōu)點：長短兼顧 缺點：需經常計算各進程優(yōu)先級 ： ? 響應比 Rp=（ Tw+Ts） /Ts ? 特點： ? （ 1）短作業(yè) RP大。 ? 特點：簡單，但低優(yōu)先權作業(yè)可能長期不被調度（饑餓）。 ： 1）靜態(tài)優(yōu)先權： ? 進程優(yōu)先權在整個運行期不變。 ][11???niiTnT11 []n ii siTWnT?? ?面向用戶的準則 （ 2）響應時間快：（對交互性作業(yè)） 概念：鍵盤提交請求到首次響應時間 ? 輸入傳送時間 ? 處理時間 ? 響應傳送時間 （ 3）截止時間的保證（特別是實時系統） （ 4）優(yōu)先權準則：（即需要搶占調度） 面向系統的準則 （ 1）吞吐量高（特別是批處理）：單位時間完成作業(yè)數 （ 2）處理機利用率好：（因 CPU貴，特別是大中型多用戶系統） （ 3）各類資源的平衡利用。 ： ? 保存處理機現場信息 ? 按某種算法選取進程 ? 把處理機分配給進程 ? 排隊器 ? 分派器 ? 上下文切換機制：兩對切換 CPU Switch From Process to Process ： 1)非搶占方式： 簡單、系統開銷小，實時性差 (如 win31) 2)搶占方式 （ 1）優(yōu)先權原則 （ 2）短進程優(yōu)先原則 （ 3）時間片原則 ? 引起進程調度的因素有哪些 ？ ? 進程正常終止或異常終止 ? 進程因某種原因阻塞： I/O請求； wait操作等 ? 時間片用完 ? 搶占方式下，就緒隊列中某進程的優(yōu)先權比當前執(zhí)行的進程高 為提高系統吞吐量和內存利用率而引入的一 內 外存對換功能（換出時，進程為掛起或就緒駐外存狀態(tài)） 三級調度的 運行頻率 ?低 中 高 。 ? 一般用于批處理系統，分 /實時系統一般直接入內存，無此環(huán)節(jié)。 ? 作業(yè)步：作業(yè)執(zhí)行過程中的每一個加工步驟 ? 作業(yè)流：作業(yè)進入系統，依次存于外存形成作業(yè)流 作業(yè)控制塊（ JCB） ? 它是作業(yè)在系統中存在的標志，其中保存了系統 對作業(yè)進行管理和調度所需的全部信息。 CPU是計算機系統中的一個十分重要的資源，對它進行高效的調度是操作系統設計的中心問題之一。第三章 處理機調度與死鎖 處理機調度的層次 調度隊列模型和調度準則 調度算法 實時調度 產生死鎖的原因和必要條件 預防死鎖的方法 死鎖的檢測與解除 教學目的與要求 ? 理解處理機調度的概念和調度的層次 ? 掌握各種作業(yè)、進程調度算法和實時調度算法