處理機調(diào)度與死鎖(3)-閱讀頁
2025-06-03 23:06本頁面
【正文】 ， 以便獲得更好的調(diào)度性能 。 據(jù)此 ， 優(yōu)先權(quán)變化規(guī)律又可表示為： 要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間 ???Rp淮海工學(xué)院計算機科學(xué)系 高響應(yīng)比優(yōu)先調(diào)度算法特點： ① 如果作業(yè)的等待時間相同 ， 則要求服務(wù)的時間愈短 ， 其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) ； ② 當(dāng)要求服務(wù)的時間相同時 ， 作業(yè)的優(yōu)先權(quán)決定于其等待時間 ， 等待時間愈長 ， 其優(yōu)先權(quán)愈高 ， 因而它實現(xiàn)的是先來先服務(wù) ； ③ 對于長作業(yè) ， 作業(yè)的優(yōu)先級可以隨等待時間的增加而提高 ， 當(dāng)其等待時間足夠長時 ， 其優(yōu)先級便可升到很高 ， 從而也可獲得處理機 ， 避免了長作業(yè)饑餓現(xiàn)象 。劃分為時間片輪轉(zhuǎn)和多級反饋隊列調(diào)度算法 1）時間片輪轉(zhuǎn)法 FIFO原則排隊，每次調(diào)度時，把 CPU分配給隊首進程，并令其執(zhí)行一個時間片（如 20ms）。如此反復(fù)和輪轉(zhuǎn)，就可以保證就緒隊列中的所有進程，在一給定的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間。 原理如下： ① 設(shè)置多個就緒隊列 ， 并賦予不同的優(yōu)先級和時間片： 第一個隊列的優(yōu)先級最高 ， 第二個隊列次之 ， 其余各隊列的優(yōu)先權(quán)逐個降低 。 圖 35 是多級反饋隊列算法的示意 。 當(dāng)輪到該進程執(zhí)行時 ， 如它能在該時間片內(nèi)完成 ， 便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成 ， 調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾 ， 再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成 ， 再依次將它放入第三隊列 ， …… ， 如此下去 ， 當(dāng)一個長作業(yè) (進程 )從第一隊列依次降到第 n隊列后 ， 在第 n隊列中便采取按時間片輪轉(zhuǎn)的方式運行 。 如果處理機正在第 i隊列中為某進程服務(wù)時 ， 又有新進程進入優(yōu)先權(quán)較高的隊列 (第 1~(i1)中的任何一個隊列 )， 則此時新進程將搶占正在運行進程的處理機 ， 即由調(diào)度程序把正在運行的進程放回到第 i隊列的末尾 ， 把處理機分配給新到的高優(yōu)先權(quán)進程 。 (2) 短批處理作業(yè)用戶：短作業(yè)優(yōu)先運行結(jié)束 。 淮海工學(xué)院計算機科學(xué)系 作業(yè) 31 ? P101： 7 淮海工學(xué)院計算機科學(xué)系 實 時 調(diào) 度 實現(xiàn)實時調(diào)度的基本條件 為了實現(xiàn)對實時進程進行有效調(diào)度，系統(tǒng)必須滿足下述條件： 1. 提供必要的信息 ① 就緒時間： 進程進入就緒狀態(tài)的開始時間，有周期性和非周期性 ② 開始截止時間和完成截止時間： 開始處理或完成任務(wù)的最遲時間 ③ 處理時間： 指一個進程從開始執(zhí)行到完成需要的處理時間； ④ 資源要求： 指處理一個任務(wù)時所需要的資源； ⑤ 優(yōu)先級： 用于標(biāo)識一個任務(wù)得到處理的輕重緩急。實時調(diào)度強調(diào)對實時進程或任務(wù)處理（響應(yīng)）的及時性和緊迫性。處理機能力必須滿足： 假定系統(tǒng)中有 m個周期性的硬實時任務(wù) ， 它們的處理時間分別 Ci， 周期時間分別為 Pi， 則在單處理機情況下 ， 其處理能力必須滿足條件： ???mi iiPC11處理機滿足此條件時，才是可調(diào)度的；否則，調(diào)度不過來。 但這種調(diào)度機制比較復(fù)雜 。 淮海工學(xué)院計算機科學(xué)系 實時調(diào)度算法的分類 1. 非搶占式調(diào)度算法 ① 非搶占式輪轉(zhuǎn)調(diào)度算法： 控制多個相同對象；每對象一個實時進程；建立一個 FIFO進程就緒隊列，按照 FCFS輪轉(zhuǎn)調(diào)度。 ② 非搶占式優(yōu)先調(diào)度算法： 就緒隊列按優(yōu)先級進隊排序，調(diào)度始終先調(diào)度隊首進程。 調(diào)度性能： 響應(yīng)達到幾十毫秒至幾毫秒，適應(yīng)大多數(shù)控制系統(tǒng)。 調(diào)度性能： 調(diào)度延遲為幾毫秒至 100微秒。實際上進程就緒隊列按照開始截至?xí)r間早晚排隊，每次調(diào)度隊首進程。 EDF算法用于非搶占調(diào)度方式 1 3 4 2開始截止時間任務(wù)執(zhí)行任務(wù)到達1 2 3 41 3 4 2t淮海工學(xué)院計算機科學(xué)系 2. 最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 調(diào)度策略： 算法根據(jù)任務(wù)緊急 (或松弛 )的程度 ， 來確定任務(wù)的優(yōu)先級 。 例如說明： 一個任務(wù)在 200ms時必須完成 ， 而它本身所需的運行時間就有100ms， 因此 ， 調(diào)度程序必須在 100 ms之前調(diào)度執(zhí)行 ， 該任務(wù)的緊急程度(松弛程度 )為 100 ms。 該算法主要用于可搶占調(diào)度方式中 。 解：任務(wù) A的松馳度為 10ms， 任務(wù) B的松馳度為 25ms
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1