【文章內(nèi)容簡(jiǎn)介】 這種搶占式的優(yōu)先權(quán)調(diào)度算法 ， 能更好地滿(mǎn)足緊迫作業(yè)的要求 ， 故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中 ， 以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中 。 第三章 處理機(jī)調(diào)度與死鎖 2. 優(yōu)先權(quán)的類(lèi)型 1) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的 ， 且在進(jìn)程的整個(gè)運(yùn)行期間保持不變 。 一般地 ， 優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的 。 第三章 處理機(jī)調(diào)度與死鎖 (1) 進(jìn)程類(lèi)型。 (2) 進(jìn)程對(duì)資源的需求。 (3) 用戶(hù)要求。 靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行，系統(tǒng)開(kāi)銷(xiāo)小，但不夠精確， 很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè) (進(jìn)程 )長(zhǎng)期沒(méi)有被調(diào)度的情況。 因此，僅在要求不高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。 第三章 處理機(jī)調(diào)度與死鎖 2) 在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先數(shù) ， 但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化 。 如等待時(shí)間長(zhǎng)優(yōu)先數(shù)可改變 。 可以防止某個(gè)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī) 。 第三章 處理機(jī)調(diào)度與死鎖 3. 高響應(yīng)比優(yōu)先調(diào)度算法 要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán) ??優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和 ， 就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間 ， 故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比 RP。 據(jù)此 ， 又可表示為： 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán) ???第三章 處理機(jī)調(diào)度與死鎖 (1) 如果作業(yè)的等待時(shí)間相同 ， 則要求服務(wù)的時(shí)間愈短 ， 其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) 。 (2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí) ， 作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間 ， 等待時(shí)間愈長(zhǎng) ， 其優(yōu)先權(quán)愈高 ， 因而它實(shí)現(xiàn)的是先來(lái)先服務(wù) 。 (3) 對(duì)于長(zhǎng)作業(yè) ， 作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高 ， 當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí) ， 其優(yōu)先級(jí)便可升到很高 ， 從而也可獲得處理機(jī) 。 該調(diào)度算法的特點(diǎn)： 第三章 處理機(jī)調(diào)度與死鎖 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 1. (RR— Round Robin) 把 CPU劃分成若干時(shí)間片 ,并且按順序賦給就緒隊(duì)列中的每一個(gè)進(jìn)程 ， 進(jìn)程輪流占有 CPU， 當(dāng)時(shí)間片用完時(shí) ， 即使進(jìn)程未執(zhí)行完畢 ， 系統(tǒng)也剝奪該進(jìn)程的 CPU， 將該進(jìn)程排在就緒隊(duì)列末尾 。 同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程運(yùn)行 。 時(shí)間片可以分為幾十 ms到幾百 ms不等 。 （ 皇帝輪流做 ， 今年到我家 ） 第三章 處理機(jī)調(diào)度與死鎖 例子： 圖 35示出了時(shí)間片分別為 q=1和 q=4時(shí) ， A、 B、 C、 D、 E五個(gè)進(jìn)程的運(yùn)行情況； 圖 36為 q=1和 q=4時(shí)各進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間 。 圖中的 RR(Round Robin)表示輪轉(zhuǎn)調(diào)度算法 。 第三章 處理機(jī)調(diào)度與死鎖 圖 35 q=1和 q=4時(shí)的進(jìn)程運(yùn)行情況 ABCDEABCDEABCEACE( a ) q ＝ 1( b ) q ＝ 41 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17t第三章 處理機(jī)調(diào)度與死鎖 圖 36 q=1和 q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 作業(yè) 情況 時(shí) 間 片 服務(wù)時(shí)間 4 3 4 2 4 完成時(shí)間 15 12 16 9 17 周轉(zhuǎn)時(shí)間 15 11 14 6 13 1 1 .8 RR q =1 帶權(quán)周轉(zhuǎn)時(shí)間 3 .7 5 3 .6 7 3 .5 3 3 .3 3 3 .4 6 完成時(shí)間 4 7 11 13 17 周轉(zhuǎn)時(shí)間 4 6 9 10 13 8 .4 RR q =4 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2 .2 5 5 3 .3 3 2 .5 第三章 處理機(jī)調(diào)度與死鎖 2. 多級(jí)反饋隊(duì)列調(diào)度算法 算法特點(diǎn) : (1)設(shè)置多個(gè)就緒隊(duì)列 ， 并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí) 。 第一個(gè)隊(duì)列的優(yōu)先級(jí)最高 ， 第二個(gè)隊(duì)列次之 ， 其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低 。 (2)該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同 ， 在優(yōu)先權(quán)愈高的隊(duì)列中 ， 為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小 。 第三章 處理機(jī)調(diào)度與死鎖 (3)最后一級(jí)采用時(shí)間片輪轉(zhuǎn) ， 其他隊(duì)列采用先進(jìn)先出； (4)系統(tǒng)從第一級(jí)調(diào)度 ， 當(dāng)?shù)谝患?jí)為空時(shí) ， 系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列 ， ..… 。 （ 5） 當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片 ， 放棄 CPU時(shí) ，則進(jìn)入下一級(jí)隊(duì)列等待調(diào)度；如果進(jìn)程處于等待狀態(tài)重新被喚醒時(shí) ， 進(jìn)入原來(lái)的就緒隊(duì)列； （ 6） 當(dāng)進(jìn)程第一次就緒時(shí) ， 進(jìn)入第一級(jí)隊(duì)列 。 第三章 處理機(jī)調(diào)度與死鎖 圖 35 多級(jí)反饋隊(duì)列調(diào)度算法 就緒隊(duì)列 1 就緒隊(duì)列 2 就緒隊(duì)列 3 就緒隊(duì)列 n S 1 S 2 S 3 至 CPU 至 CPU 至 CPU 至 CPU (時(shí)間片： S 1 ＜ S 2 ＜ S 3 ) 第三章 處理機(jī)調(diào)度與死鎖 3. 多級(jí)反饋隊(duì)列調(diào)度算法的性能 （ 1）終端型用戶(hù)：由于主要是短的交互式作業(yè)，一般會(huì)保證在一級(jí)調(diào)度內(nèi)完成，會(huì)令用戶(hù)滿(mǎn)意。 （ 2）短批處理作業(yè)：一般會(huì)在 2級(jí)內(nèi)得到處理； （ 3）長(zhǎng)批處理作業(yè)：在此調(diào)度算法中肯定會(huì)被輪轉(zhuǎn)調(diào)度得到執(zhí)行，不會(huì)擔(dān)心長(zhǎng)時(shí)間得不到相應(yīng)。 第三章 處理機(jī)調(diào)度與死鎖 實(shí) 時(shí) 調(diào) 度 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的