【正文】 低；而有的系統(tǒng)恰恰相反 。 第三章 處理機調(diào)度與死鎖 (1) 進程類型。 (2) 進程對資源的需求。 (3) 用戶要求。 第三章 處理機調(diào)度與死鎖 2) 動態(tài)優(yōu)先權(quán)是指 ， 在創(chuàng)建進程時所賦予的優(yōu)先權(quán) ， 是可以隨進程的推進或隨其等待時間的增加而改變的 ， 以便獲得更好的調(diào)度性能 。 例如 ， 我們可以規(guī)定 ， 在就緒隊列中的進程 ， 隨其等待時間的增長 ， 其優(yōu)先權(quán)以速率 a提高 。 若所有的進程都具有相同的優(yōu)先權(quán)初值 ， 則顯然是最先進入就緒隊列的進程 ， 將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機 ， 此即 FCFS算法 。 若所有的就緒進程具有各不相同的優(yōu)先權(quán)初值 ，那么 ， 對于優(yōu)先權(quán)初值低的進程 ， 在等待了足夠的時間后 ，其優(yōu)先權(quán)便可能升為最高 ， 從而可以獲得處理機 。 當采用搶占式優(yōu)先權(quán)調(diào)度算法時 ， 如果再規(guī)定當前進程的優(yōu)先權(quán)以速率 b下降 ， 則可防止一個長作業(yè)長期地壟斷處理機 。 第三章 處理機調(diào)度與死鎖 3. 高響應比優(yōu)先調(diào)度算法 要求服務時間要求服務時間等待時間優(yōu)先權(quán) ??優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時間與服務時間之和 ， 就是系統(tǒng)對該作業(yè)的響應時間 ， 故該優(yōu)先權(quán)又相當于響應比 RP。 據(jù)此 ， 又可表示為： 要求服務時間響應時間要求服務時間要求服務時間等待時間優(yōu)先權(quán) ???第三章 處理機調(diào)度與死鎖 (1) 如果作業(yè)的等待時間相同 ， 則要求服務的時間愈短 ， 其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) 。 (2) 當要求服務的時間相同時 ， 作業(yè)的優(yōu)先權(quán)決定于其等待時間 ， 等待時間愈長 ， 其優(yōu)先權(quán)愈高 ， 因而它實現(xiàn)的是先來先服務 。 (3) 對于長作業(yè) ， 作業(yè)的優(yōu)先級可以隨等待時間的增加而提高 ， 當其等待時間足夠長時 ， 其優(yōu)先級便可升到很高 ， 從而也可獲得處理機 。 第三章 處理機調(diào)度與死鎖 基于時間片的輪轉(zhuǎn)調(diào)度算法 1. 在早期的時間片輪轉(zhuǎn)法中 ， 系統(tǒng)將所有的就緒進程按先來先服務的原則 ， 排成一個隊列 ， 每次調(diào)度時 ， 把 CPU分配給隊首進程 ， 并令其執(zhí)行一個時間片 。 時間片的大小從幾ms到幾百 ms。 當執(zhí)行的時間片用完時 ， 由一個計時器發(fā)出時鐘中斷請求 ， 調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行 ，并將它送往就緒隊列的末尾；然后 ， 再把處理機分配給就緒隊列中新的隊首進程 ， 同時也讓它執(zhí)行一個時間片 。 這樣就可以保證就緒隊列中的所有進程 ， 在一給定的時間內(nèi) ， 均能獲得一時間片的處理機執(zhí)行時間 。 第三章 處理機調(diào)度與死鎖 2. 多級反饋隊列調(diào)度算法 (1) 應設置多個就緒隊列 ， 并為各個隊列賦予不同的優(yōu)先級 。 第一個隊列的優(yōu)先級最高 ， 第二個隊列次之 ， 其余各隊列的優(yōu)先權(quán)逐個降低 。 該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同 ， 在優(yōu)先權(quán)愈高的隊列中 ， 為每個進程所規(guī)定的執(zhí)行時間片就愈小 。 例如 ， 第二個隊列的時間片要比第一個隊列的時間片長一倍 ， ……， 第 i+1個隊列的時間片要比第 i個隊列的時間片長一倍 。 圖 35 是多級反饋隊列算法的示意 。 第三章 處理機調(diào)度與死鎖 圖 35 多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至 C P U至 C P U至 C P U至 C P U( 時間片： S1＜ S2＜ S3)第三章 處理機調(diào)度與死鎖 (2) 當一個新進程進入內(nèi)存后 ， 首先將它放入第一隊列的末尾 ， 按 FCFS原則排隊等待調(diào)度 。 當輪到該進程執(zhí)行時 ，如它能在該時間片內(nèi)完成 ， 便可準備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成 ， 調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾 ， 再同樣地按 FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成 ， 再依次將它放入第三隊列 ， ……， 如此下去 ， 當一個長作業(yè) (進程 )從第一隊列依次降到第 n隊列后 ， 在第 n隊列中便采取按時間片輪轉(zhuǎn)的方式運行 。 第三章 處理機調(diào)度與死鎖 (3) 僅當?shù)谝魂犃锌臻e時 ， 調(diào)度程序才調(diào)度第二隊列中的進程運行； 僅當?shù)?1~(i1) 隊列均空時 ， 才會調(diào)度第 i隊列中的進程運行 。 如果處理機正在第 i隊列中為某進程服務時 ， 又有新進程進入優(yōu)先權(quán)較高的隊列 (第 1~(i1)中的任何一個隊列 )， 則此時新進程將搶占正在運行進程的處理機 ， 即由調(diào)度程序把正在運行的進程放回到第 i隊列的末尾 ， 把處理機分配給新到的高優(yōu)先權(quán)進程 。 第三章 處理機調(diào)度與死鎖 3. 多級反饋隊列調(diào)度算法的性能 (1) 終端型作業(yè)用戶 。 (2) 短批處理作業(yè)用戶 。 (3) 長批處理作業(yè)用戶 。 第三章 處理機調(diào)度與死鎖 實 時 調(diào) 度 實現(xiàn)實時調(diào)度的基本條件 1. 提供必要的信息 (1) 就緒時間。 (2) 開始截止時間和完成截止時間。 (3) 處理時間。 (4) 資源要求。 (5) 優(yōu)先級。 第三章 處理機調(diào)度與死鎖 2. 系統(tǒng)處理能力強 在實時系統(tǒng)中 ， 通常都有著多個實時任務 。 若處理機的處理能力不夠強 ， 則有可能因處理機忙不過來而使某些實時任務不能得到及時處理 ， 從而導致發(fā)生難以預料的后果 。假定系統(tǒng)中有 m個周期性的硬實時任務 ， 它們的處理時間可表示為 Ci， 周期時間表示為 Pi， 則在單處理機情況下 ， 必須滿足下面的限制條件： ???mi iiPC11第三章 處理機調(diào)度與死鎖 系統(tǒng)才是可調(diào)度的 。 假如系統(tǒng)中有 6個硬實時任務 ， 它們的周期時間都是 50 ms， 而每次的處理時間為 10 ms， 則不難算出 ， 此時是不能滿足上式的 ， 因而系統(tǒng)是不可調(diào)度的 。 解決的方法是提高系統(tǒng)的處理能力 ， 其途徑有二：其一仍是采用單處理機系統(tǒng) ， 但須增強其處理能力 ， 以顯著地減少對每一個任務的處理時間；其二是采用多處理機系統(tǒng) 。假定系統(tǒng)中的處理機數(shù)為 N， 則應將上述的限制條件改為： ???mi ii NPC1第三章 處理機調(diào)度與死鎖 3. 采用搶占式調(diào)度機制 當一個優(yōu)先權(quán)更高的任務到達時 ， 允許將當前任務暫時掛起 ， 而令高優(yōu)先權(quán)任務立即投入運行 ， 這樣便可滿足該硬實時任務對截止時間的要求 。 但這種調(diào)度機制比較復雜 。 對于一些小的實時系統(tǒng) ， 如果能預知任務的開始截止時間 ，則對實時任務的調(diào)度可采用非搶占調(diào)度機制 ， 以簡化調(diào)度程序和對任務調(diào)度時所花費的系統(tǒng)開銷 。 但在設計這種調(diào)度機制時 ，應使所有的實時任務都比較小 ， 并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后 ， 能及時地將自己阻塞起來 ， 以便釋放出處理機 ， 供調(diào)度程序去調(diào)度那種開始截止時間即將到達的任務 。 第三章 處理機調(diào)度與死鎖 4. 具有快速切換機制 (1) 對外部中斷的快速響應能力 。 為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應 ， 要求系統(tǒng)具有快速硬件中斷機構(gòu) ， 還應使禁止中斷的時間間隔盡量短 ， 以免耽誤時機 (其它緊迫任務 )。 (2) 快速的任務分派能力 。 在完成任務調(diào)度后 ， 便應進行任務切換 。 為了提高分派程序進行任務切換時的速度 ， 應使系統(tǒng)中的每個運行功能單位適當?shù)男?， 以減少任務切換的時間開銷 。 第三章 處理機調(diào)度與死鎖 實時調(diào)度算法的分類 1. 非搶占式調(diào)度算法 (1) 非搶占式輪轉(zhuǎn)調(diào)度算法。 (2) 非搶占式優(yōu)先調(diào)度算法。 第三章 處理機調(diào)度與死鎖 2. 搶占式調(diào)度算法 (1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。 (2) 立即搶占