【正文】 8SJ F帶權(quán)周轉(zhuǎn)時間 2 2. 67 3. 1 1. 5 2. 25 2. 1例解： 作業(yè)號 A B C D E 平均到達(dá)時間 0 1 2 3 4運(yùn)行時間 4 3 5 2 4完成時間 15 ③ 12 ② 18 ⑤ 9 ① 17 ④周轉(zhuǎn)時間 15 11 16 6 13 12 . 4RR帶權(quán)周轉(zhuǎn)時間 3. 75 3. 67 3. 2 3 3. 25 3. 37完成時間 4 ① 7 ② 14 ④ 9 ③ 18 ⑤周轉(zhuǎn)時間 4 6 12 6 14 8. 4HRR N帶權(quán)周轉(zhuǎn)時間 1 2 2. 4 3 3. 5 2. 38例解 1 例解 2 ? 高響應(yīng)比優(yōu)先 (HRRN)(作業(yè) )調(diào)度算法計(jì)算： T=0：只有作業(yè) A已到達(dá)，調(diào)度作業(yè) A運(yùn)行 。 T=4：作業(yè) A完成，作業(yè) B、 C、 D、 E已到達(dá)，計(jì)算作業(yè) B、 C、 D、E響應(yīng)比 RP分別為： 1+3/ 1+2/ 1+1/ 1+0/4，作業(yè) B響應(yīng)比最大調(diào)度運(yùn)行。 T=7：作業(yè) B完成，作業(yè) C、 D、 E已到達(dá)，計(jì)算作業(yè) C、 D、 E響應(yīng)比 RP分別為： 1+5/ 1+4/ 1+3/4，作業(yè) D響應(yīng)比最大調(diào)度運(yùn)行。 T=9：作業(yè) D完成，作業(yè) C、 E已到達(dá)，計(jì)算作業(yè) C、 E響應(yīng)比 RP分別為： 1+7/ 1+5/4，作業(yè) C響應(yīng)比最大調(diào)度運(yùn)行。 T=14：作業(yè) C完成，只有作業(yè) E未完成，調(diào)度作業(yè) E運(yùn)行 。 按照進(jìn)程的優(yōu)先權(quán)大小來調(diào)度，使高優(yōu)先權(quán)進(jìn)程得到優(yōu)先處理的調(diào)度策略稱為優(yōu)先權(quán)調(diào)度算法 。 進(jìn)程的優(yōu)先權(quán)的設(shè)置可以是 靜態(tài)的，也可以是 動態(tài) 的。 (Priority)優(yōu)先調(diào)度算法 靜態(tài)優(yōu)先權(quán) 在進(jìn)程創(chuàng)建時確定，且在 整個生命期中保持不變 。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有：進(jìn)程類型，通常 系統(tǒng)進(jìn)程 （例如對換進(jìn)程）的優(yōu)先權(quán)高于一般用戶態(tài)進(jìn)程的優(yōu)先權(quán) ；進(jìn)程對資源的需求，如進(jìn)程執(zhí)行時間及內(nèi)存需要的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)；根據(jù)用戶要求，由用戶的緊迫程度及用戶所付費(fèi)用的多少來確定進(jìn)程的優(yōu)先權(quán)。 動態(tài)優(yōu)先權(quán) ? 是指在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。 改變優(yōu)先權(quán)的因數(shù) ，隨系統(tǒng)不同而不同，最?？紤]的因素的進(jìn)程的等待時間，已使用處理機(jī)的時間，或者資源使用情況等。 ? 在 UNIX系統(tǒng)中處于核心態(tài)和用戶態(tài)的優(yōu)先權(quán)不同。進(jìn)程處于 核心態(tài)的優(yōu)先權(quán)高 ，處于核心態(tài)的進(jìn)程優(yōu)先權(quán)又分二類，一類是因等待磁盤 I/O、等待緩沖器等不可中斷優(yōu)先權(quán)最高，而另一類因等待 TTY輸入輸出等可中斷優(yōu)先權(quán)其次。處于 用戶態(tài)的優(yōu)先權(quán)相對較低 ，用戶態(tài)優(yōu)先權(quán)又分為 n+1級優(yōu)先權(quán)。 優(yōu)先數(shù)為 0級的優(yōu)先權(quán)最高 ， 優(yōu)先數(shù)為 n級的優(yōu)先權(quán)最低 。 用戶態(tài)優(yōu)先權(quán)是可變的，它隨著占用 CPU時間的增加而降低。核心每隔 1秒鐘便按下述公式對各進(jìn)程重新計(jì)算其用戶優(yōu)先數(shù)（優(yōu)先數(shù)與優(yōu)先權(quán)成反比關(guān)系）。 優(yōu)先數(shù)＝最近使用 CPU的時間／ 2＋基本用戶優(yōu)先數(shù)。 例題： ? 假定要在處理機(jī)上執(zhí)行如下作業(yè)： 作業(yè) 執(zhí)行時間 優(yōu)先級 1 2 3 4 10 1 2 1 3 1 3 4 5 5 2 2 5 1 3 4 作業(yè)的執(zhí)行順序?yàn)椋? 6．多級隊(duì)列調(diào)度算法 ? 多隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同，將 就緒隊(duì)列再分為若干個子隊(duì)列 ，所有的作業(yè)（或進(jìn)程）按其性質(zhì)排入相應(yīng)的隊(duì)列中，而不同的就緒隊(duì)列采用不同的調(diào)度算法。 ? 例如 前后臺系統(tǒng)可以建立兩個就緒隊(duì)列 ，批處理作業(yè)所建立進(jìn)程進(jìn)入后臺就緒隊(duì)列；交互型作業(yè)所建立的進(jìn)程進(jìn)入前臺就緒隊(duì)列。 前臺采用時間片輪轉(zhuǎn)算法 ，進(jìn)程按 FCFS等策略排序， 后臺采用高優(yōu)先權(quán)的調(diào)度算法或者短作業(yè)優(yōu)先的調(diào)度算法 。 對多級就緒隊(duì)列調(diào)度策略有兩種， 一種是各就緒隊(duì)列按進(jìn)程性質(zhì)賦予不同的優(yōu)先權(quán)，優(yōu)先權(quán)高的就緒隊(duì)列的進(jìn)程優(yōu)先被調(diào)度 ，例如上例中前臺就緒隊(duì)列的優(yōu)先權(quán)比后臺就緒隊(duì)列的優(yōu)先權(quán)高，所以前臺隊(duì)列中的進(jìn)程優(yōu)先被調(diào)度。 而只有當(dāng)優(yōu)先權(quán)高的就緒隊(duì)列空時，方才調(diào)度優(yōu)先權(quán)其次的就緒隊(duì)列進(jìn)程， 在上例中只有前臺隊(duì)列空時，才調(diào)度后臺就緒隊(duì)列。這樣，只有較高優(yōu)先權(quán)的就緒隊(duì)列都空時才調(diào)度最低優(yōu)先權(quán)就緒隊(duì)列的進(jìn)程。 另一種調(diào)度就緒隊(duì)列的方式是為每個隊(duì)列分配一定的占用 CPU時間的比例 。如在上例中為前臺隊(duì)列分配 80％的 CPU時間，給后臺隊(duì)列分配 20％的 CPU時間。 ，首先將它放入第一隊(duì)列的末尾，按 FCFS原則排隊(duì)等待調(diào)度。 6） 多級反饋隊(duì)列調(diào)度算法 n隊(duì)列中便采取按時間片輪轉(zhuǎn)的方式運(yùn)行。 第一隊(duì)列空閑時 ， 調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行 ；如果處理機(jī)正在第 i隊(duì)列中為某進(jìn)程服務(wù)時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列 (第 1~(i1)中的任何一個隊(duì)列 )，則此時新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第 i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。 WindowsNT采用 可搶占動態(tài)優(yōu)先級多級就緒隊(duì)列調(diào)度算法 。 NT執(zhí)行體支持 32級優(yōu)先級，并將它們分成兩類，實(shí)時優(yōu)先級（ 16－ 31）和可變優(yōu)先級（ 1－ 15）， 0級為系統(tǒng)保留。每個優(yōu)先級一個就緒隊(duì)列，高序號隊(duì)列為高優(yōu)先級，調(diào)度程序從高優(yōu)先級的隊(duì)列開始往下找，如高優(yōu)先級隊(duì)列為空時才再往下找，直至找到一個進(jìn)程。 各個就緒隊(duì)列中進(jìn)程執(zhí)行時間片的大小也各不相同，在 優(yōu)先級越高的隊(duì)列中，每個進(jìn)程的執(zhí)行時間片就規(guī)定得越小 。 ? 當(dāng)一個進(jìn)程執(zhí)行完一個完整的時間片后被中斷搶占處理器，而 被搶占的進(jìn)程優(yōu)先級降低一級而進(jìn)入下級就緒隊(duì)列 ，如此繼續(xù)，直至降到進(jìn)程的基本優(yōu)先級。 而一個進(jìn)程從阻塞態(tài)變?yōu)榫途w態(tài)時要提高優(yōu)先級 ，提高的幅度與等待的事件有關(guān)。如等待鍵盤輸入所提高的幅度要大于等待磁盤I/O。 圖： 多級反饋隊(duì)列 就緒隊(duì)列 1 時間片 S1 時間片完 時間片完 就緒隊(duì)列 2 時間片 S2S1 運(yùn)行 運(yùn)行 運(yùn)行 就緒隊(duì)列 n 時間片 SnSn1 完成 完成 完成 時間片完 阻塞隊(duì)列 i 阻塞 阻塞 阻塞 事件發(fā)生