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