【文章內(nèi)容簡介】 Rp=作業(yè)響應時間 tR /要求執(zhí)行的時間 Page 63 2022/5/27 調(diào)度算法 ?先來先服務和短作業(yè)優(yōu)先算法 ?高優(yōu)先權優(yōu)先調(diào)度算法 ?基于時間片的輪轉(zhuǎn)調(diào)度算法 Page 64 2022/5/27 ? 簡單的時間片輪轉(zhuǎn)法 (RR— Round Robin)將系統(tǒng)中所有的就緒進程按照 FCFS原則，排成一個隊列； ? 每次調(diào)度時將 CPU分派給隊首進程，讓其執(zhí)行一個時間片。時間片的長度從幾個 ms到幾百 ms； ? 在一個時間片結(jié)束時，發(fā)生時鐘中斷； ? 調(diào)度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程； ? 進程可以未使用完一個時間片，就出讓 CPU（如阻塞） 。 優(yōu)點：公平。保證就緒隊列中所有進程在一給定的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間 缺點：緊迫任務響應慢。 UNIX中采用：時間片 +優(yōu)先權 ⑤ Page 65 2022/5/27 進程名 到達時間 服務時間 開始時間 完成時間 周轉(zhuǎn)時間 帶權周 轉(zhuǎn)時間 平均 A B C D E A B C D E A B C E A C E C 0 5 10 15 18 t 0 4 A 0 3 B 0 5 C 0 2 D 0 4 E 0 1 2 3 4 9 12 15 17 18 15 15/4 11 11/3 16 16/5 6 6/2 13 13/4 若到達時間為 0、 4，又如何？ Page 66 2022/5/27 基于時間片的輪轉(zhuǎn)調(diào)度算法 ?時間片長度變化的影響 ? 過長 － 退化為 FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應時間長。 ? 過短 － 用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應時間長。 ?對響應時間的要求： ? R(響應時間 )=Nmax(進程數(shù)目 )*q(時間片 ) ?時間片長度的影響因素： ? 就緒進程的數(shù)目：數(shù)目越多，時間片越小（當響應時間一定時） ? 系統(tǒng)的處理能力：應當使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應時間，平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間延長。 Page 67 2022/5/27 2. 多級隊列調(diào)度 前臺 的就緒隊列是交互性作業(yè)的進程 ， 采用時間片輪轉(zhuǎn) 。 后臺 的就緒隊列是批處理作業(yè)的進程 ， 采用優(yōu)先權或短作業(yè)優(yōu)先算法 。 調(diào)度方式有兩種： (1) 優(yōu)先調(diào)度前臺 ， 若前臺無可運行進程 ， 才調(diào)度后臺 。 (2) 分配占用 CPU的時間比例 ， 如：前臺 80%， 后臺 20%。 基于時間片的輪轉(zhuǎn)調(diào)度算法 ⑥ Page 68 2022/5/27 基于時間片的輪轉(zhuǎn)調(diào)度算法 ?多級反饋隊列調(diào)度算法 ?設置 多個就緒隊列 ，并為各個隊列賦予 不同的優(yōu)先級 ?第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權逐個降低 ?該算法賦予各個隊列中進程執(zhí)行 時間片的大小也各不相同 ，在 優(yōu)先權愈高 的隊列中，為每個進程所規(guī)定的執(zhí)行 時間片就愈小 。例如， 第二個 隊列的時間片要 比第一個 隊列的時間片 長一倍 ， ……，第 i+1個隊列的時間片要比第 i個隊列的時間片長一倍 ⑦ Page 69 2022/5/27 就緒隊列 1 基于時間片的輪轉(zhuǎn)調(diào)度算法 就緒隊列 2 就緒隊列 3 就緒隊列 n S 1 S 2 S 3 至 CPU 至 CPU 至 CPU 至 CPU (時間片： S 1 ＜ S 2 ＜ S 3 ) ?調(diào)度方式 高 低 優(yōu)先級 時間片 小 大 S n 按 FIFO原則排隊等待調(diào)度 尚未完成轉(zhuǎn)入第二隊列的末尾，按FIFO原則等待調(diào)度 采取按時間片輪轉(zhuǎn)的方式運行 因等待而放棄 CPU后，進入阻塞隊列，一旦等待的事件發(fā)生，則回到原來的就緒隊列 Page 70 2022/5/27 基于時間片的輪轉(zhuǎn)調(diào)度算法 ?注意 ? 僅當?shù)?1~(i1) 隊列均空時，才會調(diào)度第 i隊列中的進程運行 ? 第 i隊列 中某進程正在運行時，又有 新 進程進入 優(yōu)先權較高 的隊列 (第 1~(i1)中的任何一個隊列 )，則此時 新進程將搶占 正在運行進程的處理機，調(diào)度程序把正在運行的進程 放回到第 i隊列 的末尾 ? 第 i隊列 中某進程正在運行時，該進程因等待事件發(fā)生而進入阻塞隊列，等待事件發(fā)生后，調(diào)度程序把進程 放回到第 i隊列 的末尾 Page 71 2022/5/27 基于時間片的輪轉(zhuǎn)調(diào)度算法 ?多級反饋隊列調(diào)度算法的性能 ?終端型作業(yè)用戶 ? 終端型作業(yè)用戶所提交的作業(yè)多屬于 交互型 作業(yè)，通常 較小 ，系統(tǒng)只要能使這些作業(yè)在第一隊列所 規(guī)定的時間片內(nèi)完成 即可 ?短批處理作業(yè)用戶 ? 若在第 1隊列中執(zhí)行 一個時間片 即可完成，便可獲得與終端型作業(yè)一樣的響應時間 ? 如在第一個隊列中不能完成，只需在第 3隊列中各執(zhí)行一個時間片 ?長批處理作業(yè)用戶 ? 長作業(yè)將依次在第 1， 2， 3… ， n隊列中執(zhí)行，最終按輪轉(zhuǎn)方式運行 Page 72 2022/5/27 進程調(diào)度 要解決的問題 WHAT：按什么原則分配 CPU — 進程調(diào)度算法 WHEN：何時分配 CPU — 進程調(diào)度的時機 HOW： 如何分配 CPU — CPU調(diào)度過程（進程的上下文切換） Page 73 2022/5/27 補充 :進程調(diào)度的時機 ?當一個進程 運行完畢 或由于某種錯誤而終止運行 ?當一個進程在運行中處于 等待 狀態(tài)（等待 I/O） ?分時系統(tǒng)中 時間片到 ?當有一個 優(yōu)先級更高 的進程就緒（可搶占式） 例如：新創(chuàng)建一個進程，一個阻塞進程變成就緒 ?在進程通信中，執(zhí)行中的進程執(zhí)行了某種原語操作（ P操作，阻塞原語，喚醒原語） Page 74 2022/5/27 * 保存現(xiàn)場 ：順序保存，最后一步保存PSW * 選擇要運行的程序 （如果沒有就緒進程 ,系統(tǒng)會安排一個 閑逛進程 (idle)， 沒有其他進程時該進程一直運行 ,在執(zhí)行過程中可接收中斷） * 恢復現(xiàn)場： 最后一步恢復選中進程的PSW 補充：調(diào)度的實施過程 CPU調(diào)度過程 Page 75 2022/5/27 課堂練習 : 假如有 4道作業(yè)，它們的提交時間及運行時間如下表所示： 采用單道運行，試問下述調(diào)度算法下，它們的調(diào)度順序，并分別計算各調(diào)度算法下三個作業(yè)的平均周轉(zhuǎn)時間 T 和平均帶權周轉(zhuǎn)時間 W。 （ 1） FCFS（ 先來先服務） （ 2） SJF（ 短作業(yè)優(yōu)先） （ 3） HRF（ 響應比高者優(yōu)先） n n T=1/N（ ∑Ti） ,Ti=結(jié)束時刻 提交時刻 。 W=1/N（ ∑Wi） , Wi= Ti /作業(yè) i 實際執(zhí)行時間 i=1 i=1 作業(yè)號 提交時刻 運行時間（分鐘） 1 8： 00 120 2 8： 30 30 3 9： 00 6 4 9： 30 12 Page 76 2022/5/27 （ 1） FCFS： 調(diào)度順序為 1 2 3 4 ? T=1/4（ 120+120+96+78） = ? W=1/4（ 1+4+16+） = 作業(yè)號 到達時刻 要求運行時間 （分鐘） 結(jié)束時刻 周轉(zhuǎn)時間 Ti（ 分鐘） 帶權周轉(zhuǎn)時間 Wi 1 8： 00 120 10： 00 120 1 2 8： 30 30 10： 30 120 4 3 9： 00 6 10： 36 96 16 4 9： 30 12 10： 48 78 Page 77 2022/5/27 （ 2） SJF(SPF)： 調(diào)度順序為 1 3 4 2 ?T=1/4（ 120+66+48+138） =93分鐘 ?W=1/4（ 1+11+4+） = 作業(yè)號 到達時刻 要求運行時間 （分鐘） 結(jié)束時刻 周轉(zhuǎn)時間 Ti（ 分鐘） 帶權周轉(zhuǎn)時間 Wi 1 8： 00 120 10： 00 120 1 3 9： 00 6 10： 06 66 11 4 9： 30 12 10： 18 48 4 2 8： 30 30 10： 48 138 Page 78 2022/5/27 ?（ 3） HRF ?作業(yè) 1最先到達并運行，當作業(yè) 1 完成時（ 10： 00），作業(yè) 4都到達，則計算它們的響應比 ： 作業(yè) 2響應比 =（ 90+30） /30=4 作業(yè) 3響應比 =（ 60+6） /6=11 作業(yè) 4響應比 =（ 30+12） /12= 由于作業(yè) 3的響應比最高，所以作業(yè) 3先運行。 ?當作業(yè) 3完成時（ 10： 06），計算作業(yè) 4的響應比： 作業(yè) 2響應比 =（ 96+30） /30= 作業(yè) 4響應比 =（ 36+12） /12=4 由于作業(yè) 2的響應比大于作業(yè) 4，所以接著作業(yè) 2運行；最后由作業(yè) 4運行。 Page 79 2022/5/27 （ 3） HRF： 調(diào)度順序為 1 3 2 4 ? T=1/4（ 120+66+126+78） = ? W=1/4（ 1+11++） = 作業(yè)號 到達時刻 要求運行時間 （分鐘） 結(jié)束時刻 周轉(zhuǎn)時間 Ti（ 分鐘） 帶權周轉(zhuǎn)時間 Wi 1 8： 00 120 10： 00 120 1 3 9： 00 6 10： 06 66 11 2 8： 30 30 10： 36 126 4 9： 30 12 10： 48 78 Page 80 2022/5/27 （ 1）先來先服務算法 （ FCFS： First Come First Serve） （ 2）最短作業(yè)優(yōu)先算法 （ SJF： Shortest Job First） （ 3）最高響應比優(yōu)先算法 （ HRN： Highest Response Ratio Next） 響應比 R =（作業(yè)運行時間 + 作業(yè)等待時間） / 作業(yè)運行時間 = 1 +（作業(yè)等待時間 / 作業(yè)運行時間） （ 4）基于優(yōu)先數(shù)調(diào)度算法 （ HPF： Highest Priority First） 常見的作業(yè)調(diào)度算法 Page 81 2022/5/27 實時調(diào)度 ?實時系統(tǒng) ?實時系統(tǒng)的特點 ?對實時系統(tǒng)的要求 ?實時調(diào)度算法 Page 82 2022/5/27 ?實時系統(tǒng)是那些時間因素非常關鍵的系統(tǒng)。 ?實時系統(tǒng)包括監(jiān)控系統(tǒng)、自動駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應即使正確，也和沒有響應一樣糟糕。 Page 83 2022/5/27 實時任務的類型 ? 根據(jù)對截止時間的要求來劃分 ? 硬實時任務 ：系統(tǒng)必須滿足任務對截止時間的要求，否則可能出現(xiàn)難以預測的結(jié)果； ? 軟實時任務 ：它也聯(lián)系著一個截止時間，但并不嚴格，若偶爾超過時間限制也是可以容忍的。 ? 實時系統(tǒng)響應的事件分為 ? 周期性實時任務 ：要求按指定的周期循環(huán)執(zhí)行，以便周期性地控制某個外部事件； ? 非周期性實時任務 ：任務的執(zhí)行無明顯的周期性，但都必須聯(lián)系著一個截止時間。 Page 84 2022/5/27 實時系統(tǒng)的特點 ?有限等待時間 ?有限響應時間 ?用戶控制 ?可靠性高 ?系統(tǒng)出錯處理能力強 Page 85 2022/5/27 對實時系統(tǒng)的要求 ?要求更詳細的調(diào)度信息：如，就緒時間、開始或完成截止時間、處理時間、資源要求、優(yōu)先級（絕對優(yōu)先級或相對優(yōu)先級）； ?采用基于優(yōu)先級的隨時搶先式調(diào)度； ?快速中斷響應，具有快速硬件中斷機構(gòu)，應使禁止中斷的時間盡量短； ?快速上下文切換：相應地采用較小的調(diào)度單位（如線程）。 Page 86 2022/5/27 ? 為了保證滿足實時任務對截止時間的要求，實時系統(tǒng)必須具備足夠強的處理能力和快速的切換機制。 假定系統(tǒng)中有 m個周期性的硬實時任務，它們的處理時間可表示為 Ci，周期時間表示為 Pi，則在單處理機情況下，必須滿足下面的限制條件：才可能處理所有的負載。