計(jì)算機(jī)操作系統(tǒng)（第二版）課件：進(jìn)程調(diào)度算法

10月14日,鴻蒙新里程碑！美的發(fā)布物聯(lián)網(wǎng)操作系統(tǒng)1.010月22日,HarmonyOS3.0.0開發(fā)者預(yù)覽版全新發(fā)布Harmony設(shè)計(jì)系統(tǒng)ArkUI3.0ArkCompiler3.0DevEcoStudio3.0TS/JSAPI操作系統(tǒng)實(shí)驗(yàn)室：探索下一代云網(wǎng)端融合架構(gòu)下的未來操作系統(tǒng)，以及著力于新一代移動計(jì)算平臺的研究XR實(shí)驗(yàn)室：拓展在智能計(jì)算技術(shù)領(lǐng)域以及交互領(lǐng)域的研究布局。阿里達(dá)摩院增設(shè)兩大實(shí)驗(yàn)室進(jìn)程調(diào)度先來先服務(wù)調(diào)度算法（FCFS）

短作業(yè)優(yōu)先調(diào)度算法（SJF）

高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）時(shí)間片輪轉(zhuǎn)調(diào)度算法

優(yōu)先級調(diào)度算法多級隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法3.5.2進(jìn)程調(diào)度算法先來先服務(wù)調(diào)度算法（FCFS）

短作業(yè)優(yōu)先調(diào)度算法（SJF）

高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）時(shí)間片輪轉(zhuǎn)調(diào)度算法

優(yōu)先級調(diào)度算法

說明優(yōu)先級調(diào)度的兩種方式、性能特點(diǎn)優(yōu)先級設(shè)計(jì)：靜態(tài)、動態(tài)

案例分析（講授+討論）多級隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度基本概念實(shí)現(xiàn)思路性能分析如何改進(jìn)1.先來先服務(wù)調(diào)度算法（FCFS）作業(yè)名提交時(shí)間要求執(zhí)行時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間ABCD1.01.21.41.52.03.01.20.31.03.06.07.23.06.07.27.52.04.85.86.01.01.64.820.0平均周轉(zhuǎn)時(shí)間：T＝（2.0+4.8+5.8+6.0）/4=4.65平均帶權(quán)周轉(zhuǎn)時(shí)間：W＝(1+1.6+4.8+20)/4=6.85優(yōu)點(diǎn)：實(shí)現(xiàn)簡單；缺點(diǎn)：對長作業(yè)有利，對短作業(yè)不利；平均周轉(zhuǎn)時(shí)間可能較長；沒有考慮任務(wù)的緊迫性3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度=周轉(zhuǎn)時(shí)間/

要求執(zhí)行時(shí)間=完成時(shí)間－

提交時(shí)間總結(jié)其優(yōu)點(diǎn)、缺點(diǎn)？2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度作業(yè)名提交時(shí)間要求執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間ABCD1.01.21.41.52.03.01.20.3算法分類：

--非搶占式調(diào)度：--搶占式調(diào)度算法：按估計(jì)運(yùn)行時(shí)間搶占按剩余運(yùn)行時(shí)間搶占非搶占式調(diào)度：A、B、C、D四個作業(yè)的調(diào)度順序應(yīng)該是怎樣的？算法的基本概念、如何實(shí)現(xiàn)？2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法非搶占式調(diào)度：3.5.2進(jìn)程調(diào)度算法作業(yè)名提交時(shí)間要求執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間ADCB1.01.51.41.22.00.31.23.01.03.03.34.53.03.34.57.52.01.83.16.31.06.02.62.1平均周轉(zhuǎn)時(shí)間：T＝（2.0+1.8+3.1+6.3）/4=3.3平均帶權(quán)周轉(zhuǎn)時(shí)間：W＝(1+6+2.6+2.1)/4=2.93FCFS:T=4.65;W=6.852.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法搶占式調(diào)度：按剩余時(shí)間搶占作業(yè)名提交時(shí)間要求執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間ABCD1.01.21.41.52.03.01.20.3平均周轉(zhuǎn)時(shí)間：平均帶權(quán)周轉(zhuǎn)時(shí)間：1.01.0

AB1.2

C1.4

D1.5

ACDDC1.8

C2.9

A4.5

B7.5

AB4.53.51.754.57.56.32.11.42.91.51.251.51.80.31.0T＝（3.5+6.3+1.5+0.3）/4=2.9

W＝(1.75+2.1+1.25+1)/4=1.533.5.2進(jìn)程調(diào)度算法2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：使作業(yè)的平均周轉(zhuǎn)時(shí)間最短；證明：考察4個作業(yè)A、B、C、D，同時(shí)到達(dá)系統(tǒng)，其運(yùn)行時(shí)間分別為a、b、c、d，且abcd

D時(shí)間ACaa+ba+b+ca+b+c+dBA、B、C、D的周轉(zhuǎn)時(shí)間分別為a、a+b、a+b+c和a+b+c+d，因此平均周轉(zhuǎn)時(shí)間為：(4a+3b+2c+d)/4，顯然，當(dāng)abcd時(shí)，平均周轉(zhuǎn)時(shí)間最小。缺點(diǎn)：對長作業(yè)不利（饑餓狀態(tài)）；對緊迫作業(yè)不利；估計(jì)運(yùn)行時(shí)間不準(zhǔn)，難以真正做到短作業(yè)（進(jìn)程）優(yōu)先。

總結(jié)其優(yōu)點(diǎn)、缺點(diǎn)？3.5.2進(jìn)程調(diào)度算法3.高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）作業(yè)名提交時(shí)間要求執(zhí)行時(shí)間ABCD1.01.21.41.52.03.01.20.3順序：A,D,C,B3.3s3.5.2進(jìn)程調(diào)度算法按高響應(yīng)比優(yōu)先調(diào)度算法進(jìn)行調(diào)度，給出下述作業(yè)的調(diào)度順序，并計(jì)算平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間。要求寫出計(jì)算過程。小組討論（7分鐘）基本概念？選擇非強(qiáng)占式or搶占式？如何實(shí)現(xiàn)？3.高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）

優(yōu)點(diǎn)：

首先照顧了短作業(yè)；

同時(shí)也考慮了長作業(yè)的等待時(shí)間，相對比較公平。

缺點(diǎn)：

每次調(diào)度都需要重新計(jì)算所有作業(yè)或就緒進(jìn)程的響應(yīng)比，系統(tǒng)開銷較大；常采用非搶占調(diào)度方式。

不能保證緊迫型任務(wù)得到及時(shí)處理?？偨Y(jié)該算法的優(yōu)點(diǎn)、缺點(diǎn)？3.5.2進(jìn)程調(diào)度算法時(shí)間片太大或太小有什么不好？交互型系統(tǒng)就緒隊(duì)列，F(xiàn)CFS交互型請求CPU進(jìn)程調(diào)度運(yùn)行完成時(shí)間片到，未完成時(shí)間片大小的確定：T=Nq系統(tǒng)的響應(yīng)時(shí)間就緒進(jìn)程的數(shù)量進(jìn)程調(diào)度及切換開銷CPU的運(yùn)行速度4、

時(shí)間片輪轉(zhuǎn)調(diào)度算法3.5.2進(jìn)程調(diào)度算法算法的基本概念、如何實(shí)現(xiàn)？時(shí)間片輪轉(zhuǎn)調(diào)度算法的改進(jìn)將固定時(shí)間片改為可變時(shí)間片：每當(dāng)一輪開始時(shí)，系統(tǒng)根據(jù)響應(yīng)時(shí)間及當(dāng)前就緒進(jìn)程數(shù)目重新計(jì)算時(shí)間片：q=T/N將單就緒隊(duì)列改為多就緒隊(duì)列：

如按優(yōu)先級組建多個就緒隊(duì)列。4、

時(shí)間片輪轉(zhuǎn)調(diào)度算法有哪些改進(jìn)思路呢？3.5.2進(jìn)程調(diào)度算法5、優(yōu)先級調(diào)度算法優(yōu)先級進(jìn)程調(diào)度算法的類型非強(qiáng)占式優(yōu)先級調(diào)度算法強(qiáng)占式優(yōu)先級調(diào)度算法批處理系統(tǒng)、要求不嚴(yán)格的實(shí)時(shí)系統(tǒng)非強(qiáng)占式優(yōu)先級調(diào)度算法要求嚴(yán)格的實(shí)時(shí)系統(tǒng)哪個小組分析下這兩種調(diào)度方式的概念、性能特點(diǎn)及適用場景？解決復(fù)雜問題：

折中！5、優(yōu)先級調(diào)度算法優(yōu)先級設(shè)計(jì)進(jìn)程類型靜態(tài)優(yōu)先級進(jìn)程對資源的需求進(jìn)程的估計(jì)運(yùn)行時(shí)間如何確定進(jìn)程的靜態(tài)優(yōu)先級呢？靜態(tài)優(yōu)先級有什么不好呢？“饑餓”問題1973年工作人員關(guān)閉MIT的IBM7094時(shí)，發(fā)現(xiàn)一個1967年提交的低優(yōu)先級進(jìn)程一直未得到運(yùn)行動態(tài)優(yōu)先級如何設(shè)計(jì)動態(tài)優(yōu)先級呢？隨等待時(shí)間延長而提升隨占用CPU時(shí)間延長而降低隨剩余運(yùn)行時(shí)間縮短而提升完成I/O操作后提升5、優(yōu)先級調(diào)度算法Win2000的優(yōu)先級策略基于動態(tài)優(yōu)先級搶占的多處理機(jī)線程調(diào)度系統(tǒng)進(jìn)程靜態(tài)優(yōu)先級實(shí)時(shí)高級中上中級中下空閑

③進(jìn)程與線程優(yōu)先級的關(guān)系

進(jìn)程優(yōu)先級實(shí)時(shí)24高級13中上10中級8中下6空閑4Time_critical311515151515Highest2615121086Above_normal251411975Normal241310864Below_normal23129753Lowest22118642Idle2111111Win2000的優(yōu)先級策略5、優(yōu)先級調(diào)度算法線程優(yōu)先級5、優(yōu)先級調(diào)度算法Win2000的優(yōu)先級策略線程I/O操作完成線程信號量或事件等待結(jié)束前臺進(jìn)程中的線程完成一個等待操作

線程動態(tài)優(yōu)先級提升策略線程處于就緒狀態(tài)超過一定時(shí)間降低策略線程在CPU上運(yùn)行完一個時(shí)間配額哪個小組來分析下每種優(yōu)先級調(diào)整策略的目的是什么？5、優(yōu)先級調(diào)度算法

linux及華為openEuler系統(tǒng)的調(diào)度策略調(diào)度類表示一個具體實(shí)現(xiàn)的調(diào)度器停機(jī)調(diào)度類調(diào)度停機(jī)進(jìn)程，如遷移線程限期調(diào)度類調(diào)度限期進(jìn)程實(shí)時(shí)調(diào)度類調(diào)度實(shí)時(shí)進(jìn)程公平調(diào)度類調(diào)度普通進(jìn)程空閑調(diào)度類調(diào)度空閑線程，即0號線程優(yōu)先級逐級降低5、優(yōu)先級調(diào)度算法

linux及華為openEuler系統(tǒng)的調(diào)度策略CFS調(diào)度器調(diào)度普通進(jìn)程虛擬運(yùn)行時(shí)間VTi當(dāng)兩個進(jìn)程實(shí)際運(yùn)行時(shí)間T相等時(shí)，nice值小的進(jìn)程，其VTi越大還是越小？將nice值轉(zhuǎn)換為Wi5、優(yōu)先級調(diào)度算法團(tuán)隊(duì)自主研發(fā)：HDU-edge-OS無人車、無人機(jī)、無人船等實(shí)時(shí)控制系統(tǒng)基于靜態(tài)優(yōu)先級搶占的多處理器進(jìn)程調(diào)度算法關(guān)于優(yōu)先級大小的論述中，正確的是（）計(jì)算型作業(yè)的優(yōu)先級，應(yīng)高于I/O型作業(yè)的優(yōu)先級用戶進(jìn)程的優(yōu)先級，應(yīng)高于系統(tǒng)進(jìn)程的優(yōu)先級在動態(tài)優(yōu)先級中，隨著作業(yè)等待時(shí)間的增加，其優(yōu)先級降低在動態(tài)優(yōu)先級中，隨著進(jìn)程執(zhí)行時(shí)間的增加，其優(yōu)先級降低ABCD提交單選題10分下列調(diào)度算法中，不可能導(dǎo)致饑餓現(xiàn)象的是（）靜態(tài)優(yōu)先級調(diào)度非搶占式短作業(yè)優(yōu)先時(shí)間片輪轉(zhuǎn)搶占式短作業(yè)優(yōu)先ABCD提交單選題10分下列選項(xiàng)中，提升進(jìn)程優(yōu)先級的合理時(shí)機(jī)有（

）進(jìn)程時(shí)間片用完進(jìn)程剛完成I/O操作，進(jìn)入就緒隊(duì)列進(jìn)程長期處于就緒隊(duì)列中進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)ABCD提交剛創(chuàng)建完成的新進(jìn)程E剛被V操作喚醒的進(jìn)程F當(dāng)進(jìn)行進(jìn)程調(diào)度時(shí)，提升就緒隊(duì)列中進(jìn)程的優(yōu)先級G多選題10分若某單處理機(jī)多進(jìn)程系統(tǒng)中有多個就緒進(jìn)程，則下列關(guān)于處理機(jī)調(diào)度的敘述中，錯誤的是（）在進(jìn)程結(jié)束時(shí)能進(jìn)行處理機(jī)調(diào)度創(chuàng)建新進(jìn)程后能進(jìn)行處理機(jī)調(diào)度在進(jìn)程處于臨界區(qū)時(shí)不能進(jìn)行處理機(jī)調(diào)度在系統(tǒng)調(diào)用完成并返回用戶態(tài)時(shí)能進(jìn)行處理機(jī)調(diào)度ABCD提交單選題10分系統(tǒng)中設(shè)置多個就緒隊(duì)列，每個隊(duì)列優(yōu)先級不同；每個隊(duì)列有自己獨(dú)立的進(jìn)程調(diào)度算法；

一個進(jìn)程依據(jù)其屬性固定位于某個就緒隊(duì)列中。實(shí)時(shí)進(jìn)程隊(duì)列系統(tǒng)進(jìn)程隊(duì)列交互式進(jìn)程隊(duì)列批處理進(jìn)程隊(duì)列

……進(jìn)程隊(duì)列最高優(yōu)先級最低優(yōu)先級CPU各隊(duì)列分別采用什么調(diào)度算法更合適呢？6、

多級隊(duì)列調(diào)度算法進(jìn)程采用靜態(tài)優(yōu)先級如果采用非搶占式調(diào)度，該如何實(shí)現(xiàn)？如果采用搶占式調(diào)度，該如何實(shí)現(xiàn)？按調(diào)度級別（優(yōu)先級）設(shè)置多個就緒進(jìn)程隊(duì)列按優(yōu)先級（或就緒隊(duì)列）設(shè)置不同時(shí)間片各級就緒隊(duì)列按FCFS組織，按時(shí)間片調(diào)度，每個進(jìn)程被調(diào)度后運(yùn)行一個當(dāng)前隊(duì)列的時(shí)間片長度最后一級按時(shí)間片輪轉(zhuǎn)方式組織調(diào)度各隊(duì)列間按搶占式優(yōu)先級算法調(diào)度新進(jìn)程運(yùn)行完成運(yùn)行完成CPU第二個就緒隊(duì)列，F(xiàn)CFSS2時(shí)間片到，未完成運(yùn)行完成時(shí)間片到，未完成CPU第n個就緒隊(duì)列，F(xiàn)CFSSn時(shí)間片到，未完成（時(shí)間片：S1<S2<Sn）CPU第一個就緒隊(duì)列，F(xiàn)CFSS1分析該算法的性能優(yōu)缺點(diǎn)？7、

多級反饋隊(duì)列調(diào)度算法8.調(diào)度算法設(shè)計(jì)舉例

運(yùn)行首先選擇

100ms

因I∕O

而等待

高優(yōu)先就緒

低優(yōu)先就緒進(jìn)程調(diào)度進(jìn)程調(diào)度時(shí)間片到請求I/OI/O完成其次選擇

500ms分析：1）進(jìn)程狀態(tài)設(shè)置？調(diào)度隊(duì)列設(shè)置？2）這個算法實(shí)現(xiàn)的思路是怎樣的？3）調(diào)度效果是怎樣的8.調(diào)度算法設(shè)計(jì)舉例

運(yùn)行首先選擇

100ms

因I∕O

而等待

高優(yōu)先就緒

低優(yōu)先就緒進(jìn)程調(diào)度進(jìn)程調(diào)度時(shí)間片到請求I/OI/O完成其次選擇

500ms105①進(jìn)程狀態(tài)運(yùn)行狀態(tài)就緒狀態(tài)因I/O而等待狀態(tài)②隊(duì)列結(jié)構(gòu)低優(yōu)先就緒隊(duì)列高優(yōu)先就緒隊(duì)列因I/O而等待隊(duì)列③進(jìn)程調(diào)度算法：優(yōu)先調(diào)度與時(shí)間片調(diào)度相結(jié)合的調(diào)度算法

ⅰ當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行，分配時(shí)間片為100ms。ⅱ當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行，分配時(shí)間片為500ms。④調(diào)度效果：

優(yōu)先照顧I∕O量大的進(jìn)程；適當(dāng)照顧計(jì)算量大的進(jìn)程。3.5.1進(jìn)程調(diào)度基本概念各種調(diào)度算法的基本概念、性能特點(diǎn)本節(jié)知識小結(jié)哪個小組來總結(jié)下？3.5進(jìn)程調(diào)度3.5.3多處理器調(diào)度多處理器調(diào)度的背景CPU緩存內(nèi)存總線鯤鵬920處理器架構(gòu)8個集群計(jì)算DIE8個集群計(jì)算DIE8個集群I/ODIEChip3.5進(jìn)程調(diào)度3.5.3多處理器調(diào)度多處理器調(diào)度的背景CPU緩存內(nèi)存總線CPU0緩存CPU1緩存內(nèi)存總線兩者間的核心差別在于對硬件緩存的使用、多處理器間的數(shù)據(jù)共享緩存一致性問題CPU間數(shù)據(jù)共享問題負(fù)載均衡問題緩存親和性問題3.5進(jìn)程調(diào)度3.5.3多處理器調(diào)度多處理器調(diào)度策略CPU0P1缺乏可擴(kuò)展性違背緩存親和性P2P3P4P5CPU1單隊(duì)列調(diào)度存在的問題違背緩存親和性P1P2P3P4P5單隊(duì)列運(yùn)行情況引入親和度機(jī)制后的單隊(duì)列運(yùn)行情況3.5.3多處理器調(diào)度3.5.3多處理器調(diào)度多處理器調(diào)度策略CPU0P1初期均衡，后期可能不均衡P3P2P4CPU1多隊(duì)列調(diào)度存在的問題就緒進(jìn)程跨CPU遷移解決思路分析下這種方式的性能優(yōu)缺點(diǎn)？3.5.3多