【正文】 如等待鍵盤輸入所提高的幅度要大于等待磁盤I/O。 ? 當(dāng)一個(gè)進(jìn)程執(zhí)行完一個(gè)完整的時(shí)間片后被中斷搶占處理器，而 被搶占的進(jìn)程優(yōu)先級(jí)降低一級(jí)而進(jìn)入下級(jí)就緒隊(duì)列 ，如此繼續(xù)，直至降到進(jìn)程的基本優(yōu)先級(jí)。每個(gè)優(yōu)先級(jí)一個(gè)就緒隊(duì)列，高序號(hào)隊(duì)列為高優(yōu)先級(jí)，調(diào)度程序從高優(yōu)先級(jí)的隊(duì)列開(kāi)始往下找，如高優(yōu)先級(jí)隊(duì)列為空時(shí)才再往下找，直至找到一個(gè)進(jìn)程。 WindowsNT采用 可搶占動(dòng)態(tài)優(yōu)先級(jí)多級(jí)就緒隊(duì)列調(diào)度算法 。 6） 多級(jí)反饋隊(duì)列調(diào)度算法 n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。如在上例中為前臺(tái)隊(duì)列分配 80％的 CPU時(shí)間，給后臺(tái)隊(duì)列分配 20％的 CPU時(shí)間。這樣，只有較高優(yōu)先權(quán)的就緒隊(duì)列都空時(shí)才調(diào)度最低優(yōu)先權(quán)就緒隊(duì)列的進(jìn)程。 對(duì)多級(jí)就緒隊(duì)列調(diào)度策略有兩種， 一種是各就緒隊(duì)列按進(jìn)程性質(zhì)賦予不同的優(yōu)先權(quán)，優(yōu)先權(quán)高的就緒隊(duì)列的進(jìn)程優(yōu)先被調(diào)度 ，例如上例中前臺(tái)就緒隊(duì)列的優(yōu)先權(quán)比后臺(tái)就緒隊(duì)列的優(yōu)先權(quán)高，所以前臺(tái)隊(duì)列中的進(jìn)程優(yōu)先被調(diào)度。 ? 例如 前后臺(tái)系統(tǒng)可以建立兩個(gè)就緒隊(duì)列 ，批處理作業(yè)所建立進(jìn)程進(jìn)入后臺(tái)就緒隊(duì)列；交互型作業(yè)所建立的進(jìn)程進(jìn)入前臺(tái)就緒隊(duì)列。 優(yōu)先數(shù)＝最近使用 CPU的時(shí)間／ 2＋基本用戶優(yōu)先數(shù)。 用戶態(tài)優(yōu)先權(quán)是可變的，它隨著占用 CPU時(shí)間的增加而降低。處于 用戶態(tài)的優(yōu)先權(quán)相對(duì)較低 ，用戶態(tài)優(yōu)先權(quán)又分為 n+1級(jí)優(yōu)先權(quán)。 ? 在 UNIX系統(tǒng)中處于核心態(tài)和用戶態(tài)的優(yōu)先權(quán)不同。 動(dòng)態(tài)優(yōu)先權(quán) ? 是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。 (Priority)優(yōu)先調(diào)度算法 靜態(tài)優(yōu)先權(quán) 在進(jìn)程創(chuàng)建時(shí)確定，且在 整個(gè)生命期中保持不變 。 按照進(jìn)程的優(yōu)先權(quán)大小來(lái)調(diào)度，使高優(yōu)先權(quán)進(jìn)程得到優(yōu)先處理的調(diào)度策略稱為優(yōu)先權(quán)調(diào)度算法 。 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=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)行。 例： 假定在一個(gè)處理機(jī)上執(zhí)行以下五個(gè)作業(yè)： 作業(yè)號(hào) A B C D E 到達(dá)時(shí)間 0 1 2 3 4 運(yùn)行時(shí)間 4 3 5 2 4 分別采用 FCFS、 SJF、 RR（ 時(shí)間片＝ 1） 和 HRN(響應(yīng)比高者優(yōu)先 ) 四種調(diào)度算法時(shí) ， 試做： （ 1） 畫出調(diào)度圖； （ 2） 計(jì)算每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 ； （ 3）計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 作為新一輪調(diào)度的時(shí)間片 。 最佳的時(shí)間片量值應(yīng)能使分時(shí)用戶得到好的響應(yīng)時(shí)間 。 如果時(shí)間片長(zhǎng)度選擇過(guò)長(zhǎng) （ 大 ） 。 時(shí)間片輪轉(zhuǎn)策略特別適合于分時(shí)系統(tǒng)中使用 ，當(dāng)多個(gè)進(jìn)程駐留在主存中時(shí) ， 在進(jìn)程間轉(zhuǎn)接處理機(jī)的開(kāi)銷一般是不大的 。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片處理機(jī)執(zhí)行時(shí)間。當(dāng)執(zhí)行的 時(shí)間片用完 時(shí)，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它 送就緒隊(duì)列的末尾 ，等待分配下一時(shí)間片再執(zhí)行。 這就克服了短作業(yè)優(yōu)先的缺點(diǎn) ，既照顧了先來(lái)者 ， 又優(yōu)待了短作業(yè) ， 是上述兩種算法的一種較好的折中 。 響應(yīng)比 R不僅是 要求運(yùn)行時(shí)間的函數(shù) ， 而且還是 等待時(shí)間的函數(shù) 。 2 ＝ 調(diào)度算法比較例 先調(diào)度 B 后調(diào)度 A 先調(diào)度 A 后調(diào)度 B 調(diào)度順序 調(diào)度順序 短作業(yè)（進(jìn)程）優(yōu)先算法 SJ（ P） F ? 不一定能真正做到短作業(yè)優(yōu)先調(diào)度 ? 未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)被及時(shí)處理 ? 不利于長(zhǎng)作業(yè)，當(dāng)不斷有短進(jìn)程到達(dá)時(shí)，不保證長(zhǎng)進(jìn)程響應(yīng)的及時(shí)性，甚至可能得不到調(diào)度 Highest Response Ratio Next (HRRN)(作業(yè) )調(diào)度算法 按照高響應(yīng)比優(yōu)先的原則，在每次選擇作業(yè)投入運(yùn)行時(shí)， 先計(jì)算此時(shí)后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比 RP， 然后選擇其值最大的作業(yè)投入運(yùn)行。 ?第 1秒時(shí) B進(jìn)入系統(tǒng)內(nèi)存，第 2秒時(shí) A進(jìn)入內(nèi)存 ?當(dāng) CPU空閑，需要調(diào)度進(jìn)程時(shí)根據(jù)不同的算法選擇 A或 B ?問(wèn)：分別計(jì)算 FCFS算法下和 SJF算法下， A和B的周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間和系統(tǒng)平均周轉(zhuǎn)時(shí)間 B A 調(diào)度算法比較例題 ? FCFS算法－－先來(lái)先服務(wù) ?B：周轉(zhuǎn)時(shí)間為 4＋ 100＝ 104s ? 帶權(quán)周轉(zhuǎn)時(shí)間為 104/100 ＝ ?A：周轉(zhuǎn)時(shí)間為 3+100+5＝ 108s ? 帶權(quán)周轉(zhuǎn)時(shí)間為 108/5 ＝ ?平均帶權(quán)周轉(zhuǎn)時(shí)間為 ( +)247。 作業(yè) 進(jìn)入時(shí)刻 (h) 運(yùn)行時(shí)間 (h) 1 2 3 4 例題： 用 SJF 算法計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 該算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè) 作業(yè) 進(jìn)入時(shí)刻 運(yùn)行時(shí)間 開(kāi)始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn) 1 2 3 4 平均周轉(zhuǎn)時(shí)間 T＝ 平均帶權(quán)周轉(zhuǎn)時(shí)間 T’＝ 最短作業(yè)優(yōu)先法（ SJF） 該算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè) 作業(yè) 進(jìn)入時(shí)刻 運(yùn)行時(shí)間 開(kāi)始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn) 1 2 3 4 平均周轉(zhuǎn)時(shí)間 T＝ 平均帶權(quán)周轉(zhuǎn)時(shí)間 T’＝ 最短作業(yè)優(yōu)先法（ SJF） 該算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè) 作業(yè) 進(jìn)入時(shí)刻 運(yùn)行時(shí)間 開(kāi)始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)