《中斷與處理機(jī)調(diào)度》ppt課件-全文預(yù)覽
【正文】 33 平均周轉(zhuǎn)時(shí)間 =(27+29+33)/3= 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(1++)/3= T W0 27 30 35 P1 P2 P3 先到先服務(wù)算法 (Cont.) ? 優(yōu)點(diǎn)： ? “ 公平 ” ； ? 缺點(diǎn) : ? 短作業(yè)等待時(shí)間長。通常 α取 。 (min) ? 系統(tǒng)開銷 。 處理機(jī)調(diào)度 ? 處理機(jī)調(diào)度算法 ? 按什么原則分配 ? 處理機(jī)調(diào)度時(shí)機(jī) ? 何時(shí)重新分配 ? 處理機(jī)調(diào)度過程 ? 如何完成分配 處理機(jī)調(diào)度算法 ? 考慮因素（ scheduling criteria） ? CPU利用率 。 (min) ? 響應(yīng)時(shí)間 。 CPU burst vs. I/O burst ? 下一個(gè) CPU burst的長度估算 ? 令 τn是估計(jì)的第 n個(gè) CPU陣發(fā)期的長度， tn的值是進(jìn)程最近一次 CPU陣發(fā)期長度，則有如下估算公式： ? τn+1=αtn + (1α)τn ? 參數(shù) α(0≤α≤1)控制 tn和 τn在公式中起的作用：當(dāng) α=0時(shí)， τn+1=τn；當(dāng) α=1時(shí)， τn+1=tn。 ? 進(jìn)程運(yùn)行 ,直到結(jié)束或等待 先到先服務(wù)算法 ? FCFS（ First Come First Serve) ? 按進(jìn)程申請 CPU（就緒）的次序。 最短剩余時(shí)間優(yōu)先算法 (SRTN) ? Shortest Remaining Time Next ? 可剝奪 SJF ? Process Arrival time Burst time ? P1 0 12 ? P2 1 9 ? P3 3 6 ? P4 5 3 ? Gantt圖 P1 P2 P3 P4 P3 P2 P1 0 1 3 5 8 12 19 30 最短剩余時(shí)間優(yōu)先算法 (Cont.) 進(jìn)程 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 P1 0 12 0 30 30 P2 1 9 1 19 18 2 P3 3 6 3 12 9 P4 5 3 5 8 3 1 平均周轉(zhuǎn)時(shí)間 =(30+18+9+3)/4=15 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(+2++1)/4= 平均等待時(shí)間＝ (18+9+3+0)/ 4 ＝ (ms) P1 P2 P3 P4 P3 P2 P1 0 1 3 5 8 12 19 30 (HRN) ? Highest Response Ratio Next ? RR=(BT+WT)/BT=1+WT/BT ? 其中 : ? BT=burst time ? WT=wait time ? 優(yōu)點(diǎn) : ? 同時(shí)到達(dá)任務(wù) , 短者優(yōu)先 ? 長作業(yè)隨等待時(shí)間增加響應(yīng)比增加 最高優(yōu)先數(shù)算法 (HPF) ? 靜態(tài)優(yōu)先數(shù) (static) ? 優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。 最高優(yōu)先數(shù)算法 (Cont.) ? 非剝奪式優(yōu)先數(shù) ? 獲得處理機(jī)的進(jìn)程運(yùn)行，直至 ? 終止 ? 等待 ? 剝奪式優(yōu)先數(shù) ? 獲得處理機(jī)的進(jìn)程運(yùn)行，直至 ? 終止 ? 等待 ? 出現(xiàn)高優(yōu)先級(jí)的進(jìn)程 最高優(yōu)先數(shù)算法 (Cont.) ? 可搶占 CPU ? Process Arrival time Priority Burst time ? P1 0 0 8 ? P2 2 1 5 ? P3 4 3 7 ? P4 0 2 3 ? P5 5 7 2 ? Gantt Chart 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 最高優(yōu)先數(shù)算法 (Cont.) TW進(jìn)程 到達(dá)時(shí)間 運(yùn)行時(shí)間 優(yōu)先級(jí) 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 P1 0 8 0 17 25 25 P2 2 5 1 3 17 15 3 P3 4 7 3 4 13 9 P4 0 3 2 0 3 3 1 P5 5 2 7 5 7 2 1 平均周轉(zhuǎn)時(shí)間 =(25+15+9+3+2)/5= 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(+3++1+1)/5= 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 最高優(yōu)先數(shù)算法 (Cont.) ? 例子 UNIX： preemptive+dynamic priority（可搶占 CPU動(dòng)態(tài)優(yōu)先數(shù)）。 ? 改進(jìn)輪轉(zhuǎn) ? 時(shí)間片長度不定，可變。 運(yùn)行 s1時(shí)間片 運(yùn)行 s2時(shí)間片 …. 創(chuàng)建喚醒 優(yōu)先級(jí) 時(shí)間片 運(yùn)行 sn時(shí)間片 Q1 ( RR, HPF1 ) Q2 ( RR, HPF2 ) Qn ( RR, HPFn ) 反饋排隊(duì)算法 (Cont.) ? 調(diào)度效果：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1