3.5進(jìn)程調(diào)度進(jìn)程調(diào)度的基本概念進(jìn)程調(diào)度算法Linux調(diào)度算法解析3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念調(diào)度的層次：高級調(diào)度；中級調(diào)度；低級調(diào)度進(jìn)程調(diào)度的功能：CPU調(diào)度+CPU切換進(jìn)程調(diào)度方式：非搶占方式；搶占方式進(jìn)程調(diào)度時(shí)機(jī)選擇進(jìn)程調(diào)度方式及調(diào)度算法應(yīng)考慮的因素

系統(tǒng)設(shè)計(jì)目標(biāo)；調(diào)度的公平性；資源的均衡利用；合理的系統(tǒng)開銷調(diào)度性能的評價(jià)指標(biāo)

CPU的利用率；系統(tǒng)吞吐量；周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間；響應(yīng)時(shí)間；對截止時(shí)間的保證3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念1.并發(fā)技術(shù)回顧多個(gè)進(jìn)程在一個(gè)CPU上交替執(zhí)行，提高了資源利用率和系統(tǒng)吞吐量CPU時(shí)間進(jìn)程1進(jìn)程2進(jìn)程3進(jìn)程1進(jìn)程2進(jìn)程3movax,[30]movbx,[50]addax,bx……

進(jìn)程1movax,100movbx,50addax,bx……

進(jìn)程2movax,200movbx,50addax,bx……

進(jìn)程3切換問題：CPU從運(yùn)行進(jìn)程1到運(yùn)行進(jìn)程2

，系統(tǒng)要做哪些工作？CPUCPU切換CPU3.5進(jìn)程調(diào)度2.進(jìn)程調(diào)度與分派3.5.1進(jìn)程調(diào)度的基本概念next=PickNext(ReadyQueue);switch(current,next);從所有就緒進(jìn)程中，按一定策略選擇下一個(gè)即將參與運(yùn)行的進(jìn)程——進(jìn)程調(diào)度切換進(jìn)程上下文：即保存前一個(gè)進(jìn)程的CPU現(xiàn)場信息，恢復(fù)下一個(gè)運(yùn)行進(jìn)程的現(xiàn)場信息——分派當(dāng)系統(tǒng)中作業(yè)或進(jìn)程申請資源的數(shù)量超出資源本身的配置情況時(shí)，系統(tǒng)需要確定優(yōu)先將有限的資源分配給哪個(gè)或哪些作業(yè)或進(jìn)程使用——調(diào)度高級調(diào)度，中級調(diào)度，低級調(diào)度3.5進(jìn)程調(diào)度3.調(diào)度的層次3.5.1進(jìn)程調(diào)度的基本概念高級調(diào)度：又稱作業(yè)調(diào)度或長程調(diào)度就緒隊(duì)列作業(yè)調(diào)度外存?zhèn)潢?duì)列內(nèi)存后考慮的問題：接納多少個(gè)作業(yè)：多道程序度接納哪些作業(yè)：作業(yè)調(diào)度算法3.5進(jìn)程調(diào)度3.調(diào)度的層次3.5.1進(jìn)程調(diào)度的基本概念低級調(diào)度：又稱進(jìn)程調(diào)度考慮的問題：調(diào)度標(biāo)準(zhǔn)：進(jìn)程調(diào)度算法調(diào)度時(shí)機(jī)：什么時(shí)候調(diào)度進(jìn)程調(diào)度就緒隊(duì)列內(nèi)存CPU中級調(diào)度：對換

引人中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。外存文件區(qū)外存交換區(qū)內(nèi)存內(nèi)存緊張時(shí)換出內(nèi)存寬松時(shí)換入3.5進(jìn)程調(diào)度3.調(diào)度的層次3.5.1進(jìn)程調(diào)度的基本概念考慮的問題：交換哪些進(jìn)程什么時(shí)候交換3.5進(jìn)程調(diào)度3.調(diào)度的層次3.5.1進(jìn)程調(diào)度的基本概念三級調(diào)度非搶占方式：一旦進(jìn)程占用CPU就一直運(yùn)行，直到終止或等待。搶占方式：系統(tǒng)強(qiáng)行剝奪已分配給現(xiàn)運(yùn)行進(jìn)程的CPU，而重新分配給其他進(jìn)程運(yùn)行。

搶占原則：

時(shí)間片原則；優(yōu)先權(quán)原則；剩余運(yùn)行時(shí)間等。搶占方式的實(shí)現(xiàn)機(jī)制：

（1）內(nèi)核完全不可搶占；如winNT，傳統(tǒng)unix（2）內(nèi)核部分可搶占：如unixSVR4,linux；（3）內(nèi)核完全可搶占：如solaris、win2000.4.進(jìn)程調(diào)度方式:按分配處理器的方式，進(jìn)程調(diào)度有兩種方式：3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念5.可能的進(jìn)程調(diào)度時(shí)機(jī):

分時(shí)系統(tǒng)中時(shí)間片用完；

當(dāng)前進(jìn)程本身狀態(tài)發(fā)生轉(zhuǎn)換：進(jìn)程終止；進(jìn)程等待

進(jìn)程從系統(tǒng)調(diào)用中返回用戶態(tài)；

系統(tǒng)從中斷處理中返回用戶態(tài)；

就緒隊(duì)列中出現(xiàn)比當(dāng)前進(jìn)程優(yōu)先級更高的進(jìn)程；3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念6.選擇進(jìn)程調(diào)度方式及調(diào)度算法應(yīng)考慮的因素:

系統(tǒng)設(shè)計(jì)目標(biāo)

批處理系統(tǒng)；交互式系統(tǒng)；實(shí)時(shí)系統(tǒng)；網(wǎng)絡(luò)系統(tǒng)調(diào)度的公平性資源的均衡利用

各類資源的均衡利用；多個(gè)同類資源的均衡利用

合理的系統(tǒng)開銷

調(diào)度開銷:運(yùn)行調(diào)度算法的開銷，上下文切換開銷3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念7.調(diào)度性能的評價(jià)指標(biāo):CPU利用率：40%～90%系統(tǒng)吞吐量：單位時(shí)間完成的任務(wù)數(shù)量

CPU利用率高+系統(tǒng)開銷小響應(yīng)時(shí)間：交互式系統(tǒng)

從用戶提交一個(gè)請求開始，到系統(tǒng)首次對該請求產(chǎn)生響應(yīng)為止的時(shí)間間隔。

對截止時(shí)間的保證：實(shí)時(shí)系統(tǒng)

3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念周轉(zhuǎn)時(shí)間/帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間：

從作業(yè)進(jìn)入系統(tǒng)起，直到作業(yè)全部運(yùn)行完成出系統(tǒng)為止，中間所經(jīng)歷的時(shí)間。

平均周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間

問題思考：3.5.1進(jìn)程調(diào)度的基本概念作業(yè)名需要執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間J110ms200sJ2200s300s帶權(quán)周轉(zhuǎn)時(shí)間2000001.5作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時(shí)間。7.調(diào)度性能的評價(jià)指標(biāo):

平均帶權(quán)周轉(zhuǎn)時(shí)間:8.設(shè)計(jì)調(diào)度方式及算法時(shí)的矛盾問題:響應(yīng)時(shí)間短與公平性之間的矛盾3.5進(jìn)程調(diào)度3.5.1進(jìn)程調(diào)度的基本概念響應(yīng)時(shí)間短提高交互型任務(wù)的優(yōu)先級

交互型任務(wù)總是優(yōu)先調(diào)度批處理任務(wù)長期得不到調(diào)度不公平響應(yīng)時(shí)間短與吞吐量大之間的矛盾響應(yīng)時(shí)間短縮小時(shí)間片，提高CPU調(diào)度的頻率

CPU調(diào)度及切換開銷大降低了系統(tǒng)的吞吐量保證截止時(shí)間與公平性之間的矛盾保證任務(wù)截止時(shí)間基于優(yōu)先級搶占調(diào)度低優(yōu)先級任務(wù)長期得不到調(diào)度不公平8.設(shè)計(jì)調(diào)度算法時(shí)的矛盾問題:3.5進(jìn)程調(diào)度一.進(jìn)程調(diào)度的基本概念保證截止時(shí)間與吞吐量大之間的矛盾保證截止時(shí)間基于優(yōu)先級搶占調(diào)度

CPU調(diào)度及切換開銷大降低了系統(tǒng)的吞吐量提高了CPU調(diào)度的頻率其他矛盾……

如資源的均衡利用與保證截止時(shí)間或響應(yīng)時(shí)間短等方面的矛盾

設(shè)計(jì)調(diào)度算法時(shí)必須綜合考慮多個(gè)因素，不可能設(shè)計(jì)完美的調(diào)度算法，只能根據(jù)系統(tǒng)的主要目標(biāo)進(jìn)行折衷權(quán)衡。這是設(shè)計(jì)操作系統(tǒng)等復(fù)雜系統(tǒng)時(shí)的主要特點(diǎn)。先來先服務(wù)調(diào)度算法（FCFS）

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

高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）

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

時(shí)間片輪轉(zhuǎn)調(diào)度算法

多級隊(duì)列調(diào)度算法

多級反饋隊(duì)列調(diào)度算法3.5.2進(jìn)程調(diào)度算法:3.5進(jìn)程調(diào)度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)度=完成時(shí)間－

提交時(shí)間=周轉(zhuǎn)時(shí)間/

要求執(zhí)行時(shí)間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)度：2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法非搶占式調(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í)間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.932.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法搶占式調(diào)度：按剩余時(shí)間搶占3.5.2進(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平均周轉(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.532.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：使作業(yè)的平均周轉(zhuǎn)時(shí)間最短；可以證明：對于一組同時(shí)到達(dá)的作業(yè)，采用SJF算法將得到一個(gè)最小的平均周轉(zhuǎn)時(shí)間。例如，考察4個(gè)作業(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)先。

3.5.2進(jìn)程調(diào)度算法3.高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度思考：選擇何種調(diào)度方式？非強(qiáng)占式or搶占式？小組討論：按高響應(yīng)比優(yōu)先調(diào)度算法進(jìn)行調(diào)度，給出下述作業(yè)的調(diào)度順序，并計(jì)算平均周轉(zhuǎn)時(shí)間。要求寫出計(jì)算過程。作業(yè)名提交時(shí)間要求執(zhí)行時(shí)間ABCD1.01.21.41.52.03.01.20.3順序：A,D,C,B3.高響應(yīng)比優(yōu)先調(diào)度算法（HRRF）3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度

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

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

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

缺點(diǎn)：

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

不能保證緊迫型任務(wù)得到及時(shí)處理。4.優(yōu)先級調(diào)度算法優(yōu)先級進(jìn)程調(diào)度算法的類型：通常用一個(gè)整數(shù)表示優(yōu)先級非強(qiáng)占式優(yōu)先級調(diào)度算法

強(qiáng)占式優(yōu)先級調(diào)度算法

優(yōu)先級的設(shè)計(jì)方法：靜態(tài)優(yōu)先級：進(jìn)程創(chuàng)建時(shí)確定其優(yōu)先級，整個(gè)生命周期中不改變。

確定依據(jù)：進(jìn)程類型；

進(jìn)程對資源的需求；

進(jìn)程的估計(jì)運(yùn)行時(shí)間3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度關(guān)于優(yōu)先級調(diào)度算法中的“饑餓”問題，曾經(jīng)有個(gè)有趣的故事，據(jù)說，1973年工作人員在關(guān)閉MIT的IBM7094時(shí)，發(fā)現(xiàn)一個(gè)低優(yōu)先級進(jìn)程是于1967年提交的，但因優(yōu)先級太低一直未得到運(yùn)行。對于低優(yōu)先級進(jìn)程會(huì)如何？動(dòng)態(tài)優(yōu)先級改變思路：進(jìn)程使用CPU超過一定數(shù)值時(shí)，降低優(yōu)先級進(jìn)程I/O操作后，增加優(yōu)先級進(jìn)程等待時(shí)間超過一定數(shù)值時(shí)，提高優(yōu)先級

優(yōu)點(diǎn)：可防止一個(gè)進(jìn)程長期壟斷或長期等待CPU4.優(yōu)先級調(diào)度算法3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度

優(yōu)先級的設(shè)計(jì)方法：動(dòng)態(tài)優(yōu)先級：

進(jìn)程創(chuàng)建時(shí)賦一個(gè)優(yōu)先級初值，運(yùn)行期間動(dòng)態(tài)調(diào)整其權(quán)值。

優(yōu)先級算法舉例：例：有5個(gè)進(jìn)程P1、P2、P3、P4、P5，它們同時(shí)依次進(jìn)入就緒隊(duì)列，其靜態(tài)優(yōu)先級和需要的處理機(jī)時(shí)間如下所示，采用非搶占式的調(diào)度方式，給出調(diào)度順序，并計(jì)算平均周轉(zhuǎn)時(shí)間。進(jìn)程處理機(jī)時(shí)間

優(yōu)先級P1103P211P323P414P552

調(diào)度順序：

P2→P5→P1→P3→P44.優(yōu)先級調(diào)度算法3.5.2進(jìn)程調(diào)度算法

早期linux進(jìn)程調(diào)度算法：Linux常采用不設(shè)就緒隊(duì)列的基于動(dòng)態(tài)優(yōu)先級的時(shí)間片輪轉(zhuǎn)調(diào)度算法。每次調(diào)度時(shí)選擇動(dòng)態(tài)優(yōu)先級最高的進(jìn)程運(yùn)行。

①linux優(yōu)先級類型：靜態(tài)優(yōu)先級動(dòng)態(tài)優(yōu)先級nice();setpriority()同時(shí)表示了該進(jìn)程的時(shí)間片長度4.優(yōu)先級調(diào)度算法3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度②linux動(dòng)態(tài)優(yōu)先級改變原則：每當(dāng)時(shí)鐘中斷發(fā)生時(shí)，當(dāng)前進(jìn)程的動(dòng)態(tài)優(yōu)先級減1，當(dāng)動(dòng)態(tài)優(yōu)先級變?yōu)?時(shí)，當(dāng)前進(jìn)程轉(zhuǎn)變?yōu)榫途w態(tài)，系統(tǒng)重新進(jìn)行調(diào)度；當(dāng)所有就緒進(jìn)程的動(dòng)態(tài)優(yōu)先級都為0時(shí)，重新計(jì)算所有進(jìn)程的動(dòng)態(tài)優(yōu)先級：

動(dòng)態(tài)優(yōu)先級=（動(dòng)態(tài)優(yōu)先級/2）取整+靜態(tài)優(yōu)先級

早期linux進(jìn)程調(diào)度算法：4.優(yōu)先級調(diào)度算法3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度基于優(yōu)先級的搶占式多處理機(jī)調(diào)度系統(tǒng)。①6種進(jìn)程優(yōu)先級：實(shí)時(shí)（24）；高級（13）；中上（10）；中級（8）；中下（6）；空閑（4）；②線程優(yōu)先級：動(dòng)態(tài)優(yōu)先級創(chuàng)建線程時(shí)，需指出其相對優(yōu)先級。

win2000/xp線程調(diào)度策略：4.優(yōu)先級調(diào)度算法3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度③進(jìn)程與線程優(yōu)先級的關(guān)系：進(jìn)程優(yōu)先級實(shí)時(shí)24高級13中上10中級8中下6空閑4Time_critical311515151515Highest2615121086Above_normal251411975Normal241310864Below_normal23129753Lowest22118642Idle2111111

win2000/xp線程調(diào)度策略：4.優(yōu)先級調(diào)度算法④線程動(dòng)態(tài)優(yōu)先級改變策略：

提升策略：線程I/O操作完成；線程信號量或事件等待結(jié)束；前臺(tái)進(jìn)程中的線程完成一個(gè)等待操作；線程處于就緒狀態(tài)超過一定時(shí)間，但沒能進(jìn)入運(yùn)行狀態(tài)；

降低策略：線程在CPU上運(yùn)行完一個(gè)時(shí)間配額后，降低一級優(yōu)先級。

win2000/xp線程調(diào)度策略：4.優(yōu)先級調(diào)度算法5.時(shí)間片輪轉(zhuǎn)調(diào)度算法：交互型系統(tǒng)3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度就緒隊(duì)列，F(xiàn)CFS交互型請求CPU進(jìn)程調(diào)度運(yùn)行完成時(shí)間片到，未完成時(shí)間片大小的確定：N為就緒隊(duì)列中進(jìn)程數(shù)，T為系統(tǒng)響應(yīng)時(shí)間，q為時(shí)間片

T=Nq系統(tǒng)的響應(yīng)時(shí)間就緒進(jìn)程的數(shù)量進(jìn)程調(diào)度及切換開銷CPU的運(yù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)先級組建多個(gè)就緒隊(duì)列。5.時(shí)間片輪轉(zhuǎn)調(diào)度算法：交互型系統(tǒng)3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度5.時(shí)間片輪轉(zhuǎn)調(diào)度算法3.5.2進(jìn)程調(diào)度算法算法舉例假設(shè)一個(gè)系統(tǒng)采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，時(shí)間片長度為20ms，4個(gè)進(jìn)程P1，P2，P3，P4依次進(jìn)入系統(tǒng)，各進(jìn)程所需要的運(yùn)行時(shí)間為：53ms，17ms，68ms，

24ms，計(jì)算其平均周轉(zhuǎn)時(shí)間。P1P2P3P4P1P3P4P1P3P302037577797117121134154162平均周轉(zhuǎn)時(shí)間：(134+37+162+121)/4＝113.5msSJF的平均周轉(zhuǎn)時(shí)間：(94+17+162+41)/4＝78.5ms6.多級隊(duì)列調(diào)度算法：3.5.2進(jìn)程調(diào)度算法3.5進(jìn)程調(diào)度系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列優(yōu)先級不同；每個(gè)隊(duì)列有自己獨(dú)立的進(jìn)程調(diào)度算法；

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

……進(jìn)程隊(duì)列最高優(yōu)先級最低優(yōu)先級CPU7.多級反饋隊(duì)列調(diào)度算法按調(diào)度級別（優(yōu)先級）設(shè)置多個(gè)就緒進(jìn)程隊(duì)列按優(yōu)先級（或就緒隊(duì)列）設(shè)置不同時(shí)間片各級就緒隊(duì)列按FCFS組織，按時(shí)間片調(diào)度，每個(gè)進(jìn)程被調(diào)度后運(yùn)行一個(gè)當(dāng)前隊(duì)列的時(shí)間片長度最后一級按時(shí)間片輪轉(zhuǎn)方式組織調(diào)度各隊(duì)列間按搶占式優(yōu)先級算法調(diào)度新進(jìn)程運(yùn)行完成運(yùn)行完成CPU第二個(gè)就緒隊(duì)列，F(xiàn)CFSS2時(shí)間片到，未完成運(yùn)行完成時(shí)間片到，未完成CPU第n個(gè)就緒隊(duì)列，F(xiàn)CFSSn時(shí)間片到，未完成（時(shí)間片：S1<S2<Sn）CPU第一個(gè)就緒隊(duì)列，F(xiàn)CFSS18.調(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ì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為100ms。ⅱ當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為500ms。④調(diào)度效果：

優(yōu)先照顧I∕O量大的進(jìn)程；適當(dāng)照顧計(jì)算量大的進(jìn)程。進(jìn)程調(diào)度算法思考題:1、進(jìn)程調(diào)度算法中，可以設(shè)計(jì)成可搶占式的算法有（

）A．先來先服務(wù)調(diào)度算法B.最高響應(yīng)比優(yōu)先調(diào)度算法C．最短作業(yè)優(yōu)先調(diào)度算法D.時(shí)間片輪轉(zhuǎn)調(diào)度算法2、若每個(gè)作業(yè)只能建立一個(gè)進(jìn)程，為了照顧短作業(yè)用戶，應(yīng)采用（

）；為了照顧緊急性作業(yè)，應(yīng)采用（

）；為了實(shí)現(xiàn)人機(jī)交互，應(yīng)采用（

）；為了使短作業(yè)、長作業(yè)和交互作業(yè)用戶都滿意，應(yīng)采用（

）。A．FCFS調(diào)度算法；B.短作業(yè)優(yōu)先調(diào)度算法；C.時(shí)間片輪轉(zhuǎn)算法D．多級反饋隊(duì)列調(diào)度算法；E.基于優(yōu)先級的剝奪調(diào)度算法3、若某單處理機(jī)多進(jìn)程系統(tǒng)中有多個(gè)就緒進(jìn)程，則下列關(guān)于處理機(jī)調(diào)度的敘述中，正確的有哪些？（可多選

）A.在進(jìn)程結(jié)束時(shí)能進(jìn)行處理機(jī)調(diào)度B.創(chuàng)建新進(jìn)程后能進(jìn)行處理機(jī)調(diào)度C.在進(jìn)程處于臨界區(qū)時(shí)不能進(jìn)行處理機(jī)調(diào)度D.在系統(tǒng)調(diào)用完成并返回用戶態(tài)時(shí)能進(jìn)行處理機(jī)調(diào)度進(jìn)程調(diào)度算法思考題:4、有3個(gè)作業(yè)J1，J2，J3，其運(yùn)行時(shí)間分別是2,6,4小時(shí)，假設(shè)它們同時(shí)到達(dá)系統(tǒng)，并在同一處理器上以單道方式運(yùn)行，則平均周轉(zhuǎn)時(shí)間最小的執(zhí)行序列是_______。5、下列選項(xiàng)中，提升進(jìn)程優(yōu)先級的合理時(shí)機(jī)有（

）。A．進(jìn)程時(shí)間片用完B.進(jìn)程剛完成I/O操作，進(jìn)入就緒隊(duì)列C.進(jìn)程長期處于就緒隊(duì)列中D.進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)E.剛創(chuàng)建完成的新進(jìn)程F.剛被V操作喚醒的進(jìn)程G.當(dāng)進(jìn)行進(jìn)程調(diào)度時(shí)，提升就緒隊(duì)列中進(jìn)程的優(yōu)先級

某系統(tǒng)的設(shè)計(jì)目標(biāo)是：優(yōu)先照顧磁盤I/O完成的進(jìn)程；其次照顧其他I/O完成的進(jìn)程；適當(dāng)照顧計(jì)算量大的進(jìn)程；系統(tǒng)應(yīng)盡可能快的響應(yīng)用戶的請求。請?jiān)O(shè)計(jì)滿足該目標(biāo)的調(diào)度算法，要求：

（1）畫出進(jìn)程狀態(tài)轉(zhuǎn)換圖；

（2）說明算法設(shè)計(jì)思路：進(jìn)程狀態(tài)設(shè)置、調(diào)度相關(guān)進(jìn)程隊(duì)列設(shè)置；調(diào)度算法的思路描述。

課堂討論：調(diào)度算法設(shè)計(jì)二.進(jìn)程調(diào)度算法課堂小組討論

運(yùn)行首先選擇30ms

因磁盤I∕O而等待

高優(yōu)先就緒

低優(yōu)先

就緒進(jìn)程調(diào)度進(jìn)程調(diào)度時(shí)間片到請求磁盤I/O磁盤I/O完成第三選擇

100ms105①進(jìn)程狀態(tài)運(yùn)行狀態(tài)就緒狀態(tài)因I/O而等待狀態(tài)②隊(duì)列結(jié)構(gòu)低優(yōu)先級就緒隊(duì)列中等優(yōu)先級就緒隊(duì)列高優(yōu)先級就緒隊(duì)列因其他I/O而等待隊(duì)列因磁盤I/O而等待隊(duì)列

因其他I∕O而等待

中優(yōu)先就緒請求其他I/O其他I/O完成第二選擇30ms3.5.3Linux進(jìn)程調(diào)度算法解析3.5進(jìn)程調(diào)度1.Linux調(diào)度器的發(fā)展Linux2.4內(nèi)核的優(yōu)先級調(diào)度器普通進(jìn)程：動(dòng)態(tài)優(yōu)先級（權(quán)值weight），與進(jìn)程的時(shí)間片長度有關(guān)實(shí)時(shí)進(jìn)程：靜態(tài)優(yōu)先級實(shí)時(shí)進(jìn)程調(diào)度策略有兩種：SCHED_FIFO和SCHED_RR2.4內(nèi)核調(diào)度器的主要不足之處：

調(diào)度時(shí)間開銷是O(n)

每次重新計(jì)算進(jìn)程優(yōu)先級開銷較大對交互式進(jìn)程的優(yōu)化并不完善內(nèi)核是非搶占的，因此對實(shí)時(shí)進(jìn)程的支持不夠3.5.3Linux進(jìn)程調(diào)度算法解析3.5進(jìn)程調(diào)度1.Linux調(diào)度器的發(fā)展Linux2.6內(nèi)核的O(1)調(diào)度器

調(diào)度時(shí)間開銷為O(1)，與系統(tǒng)中就緒進(jìn)程數(shù)量無關(guān)就緒隊(duì)列設(shè)置3.5.3Linux進(jìn)程調(diào)度算法解析1.Linux調(diào)度器的發(fā)展Linux2.6內(nèi)核的O(1)調(diào)度器

調(diào)度時(shí)間開銷為O(1)，與系統(tǒng)中就緒進(jìn)程數(shù)量無關(guān)位示圖設(shè)置●●3.5.3Linux進(jìn)程調(diào)度算法解析1.Linux調(diào)度器的發(fā)展Linux2.6內(nèi)核的O(1)調(diào)度器支持內(nèi)核搶占，能更好地支持實(shí)時(shí)進(jìn)程分散計(jì)算各進(jìn)程優(yōu)先級及時(shí)間片，減小了計(jì)算的時(shí)間開銷根據(jù)一些經(jīng)驗(yàn)公式調(diào)整進(jìn)程優(yōu)先級，適當(dāng)照顧交互式進(jìn)程prio=max(100,min(static_prio-bonus+5,139))3.5進(jìn)程調(diào)度3.5.3Linux進(jìn)程調(diào)度算法解析1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFS3.5進(jìn)程調(diào)度設(shè)計(jì)思想：

期望每個(gè)進(jìn)程都能同時(shí)在CPU上并行執(zhí)行，且各進(jìn)程的執(zhí)行速度相同，各占CPU的1/n的時(shí)間。虛擬運(yùn)行時(shí)間：vruntime將進(jìn)程nice值轉(zhuǎn)換為權(quán)重weight宏P(guān)RIO_TO_NICE(prio)1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFS虛擬運(yùn)行時(shí)間：vruntime將進(jìn)程nice值轉(zhuǎn)換為權(quán)重weight1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFS虛擬運(yùn)行時(shí)間：vruntime

CPU運(yùn)行期periodperiod是就緒隊(duì)列中所有任務(wù)運(yùn)行完一遍的時(shí)間

進(jìn)程運(yùn)行時(shí)間計(jì)算：例：系統(tǒng)有兩個(gè)兩個(gè)就緒進(jìn)程A和B，WA=15（nice值19），WB=110（nice值10）：TA=2.4ms，TB=17.6ms1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFS虛擬運(yùn)行時(shí)間：vruntime進(jìn)程虛擬運(yùn)行時(shí)間：structload_weight{unsignedlongweight;//進(jìn)程權(quán)重Winv_weight;//232/W的值};

完全公平調(diào)度器：CFS虛擬運(yùn)行時(shí)間：調(diào)度舉例CPU實(shí)際時(shí)間(ms)TA(ms)VTA(ms)TB(ms)VTB(ms)說明（每次period中，A可運(yùn)行2.4ms，B可運(yùn)行17.6ms）101068300A用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，調(diào)度B運(yùn)行201068310109B未用完可運(yùn)行時(shí)間，B繼續(xù)運(yùn)行301068320218B用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，B繼續(xù)運(yùn)行401068330327B用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，B繼續(xù)運(yùn)行501068340436B用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，B繼續(xù)運(yùn)行601068350545B用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，B繼續(xù)運(yùn)行701068360654B用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，B繼續(xù)運(yùn)行801068370763B用完可運(yùn)行時(shí)間，重新調(diào)度，VTA＜VTB，調(diào)度A運(yùn)行9020136670763A用完可運(yùn)行時(shí)間，重新調(diào)度，VTB＜VTA，調(diào)度B運(yùn)行以此類推……，總是企圖讓所有進(jìn)程的VT趨向于相等，實(shí)現(xiàn)公平調(diào)度1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)

進(jìn)程描述符task_struck結(jié)構(gòu)：struct

task_struct

{

volatile

long

state;

/*

進(jìn)程狀態(tài)*/

int

prio,

static_prio,

normal_prio;

/*

進(jìn)程優(yōu)先級*/

unsigned

int

rt_priority;

/*

實(shí)時(shí)進(jìn)程的實(shí)時(shí)優(yōu)先級*/

const

struct

sched_class

*sched_class;

/*

進(jìn)程的調(diào)度器類*/

struct

sched_entity

se;

/*

普通進(jìn)程調(diào)度實(shí)體*/

struct

sched_rt_entity

rt;

/*

實(shí)時(shí)進(jìn)程調(diào)度實(shí)體*/

......

};

1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)

調(diào)度實(shí)體sched_entity：structsched_entity{structload_weight load;/*進(jìn)程權(quán)重結(jié)構(gòu)：weight和inv_weight*/structrb_node run_node;/*在紅黑樹中的節(jié)點(diǎn)*/unsignedint on_rq;/*若進(jìn)程在就緒隊(duì)列中，則置為1*/u64 exec_start;/*進(jìn)程本次調(diào)入CPU執(zhí)行的開始實(shí)際時(shí)間*/u64 sum_exec_runtime;/*進(jìn)程總共執(zhí)行的實(shí)際時(shí)間*/u64 vruntime;/*進(jìn)程總共執(zhí)行的虛擬時(shí)間*/u64 prev_sum_exec_runtime;/*進(jìn)程前一次投入運(yùn)行的總的執(zhí)行時(shí)間*/

......

};

1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)CFS就緒隊(duì)列cfs_rq：部分字段structcfs_rq{structload_weightload;/*就緒隊(duì)列進(jìn)程的總權(quán)重*/unsignedlongnr_running;/*就緒隊(duì)列中的進(jìn)程數(shù)量*/u64exec_clock;/*CPU實(shí)際執(zhí)行總時(shí)間*/u64min_vruntime;/*為新進(jìn)程或剛被喚醒的進(jìn)程設(shè)置vruntime*/structrb_roottasks_timeline;/*紅黑樹的根節(jié)點(diǎn)*/structrb_node*rb_leftmost;/*紅黑樹中最左邊的節(jié)點(diǎn)，即下一個(gè)被調(diào)度進(jìn)程*/structrb_node*rb_load_balance_curr;/*負(fù)載平衡的下一個(gè)被調(diào)度進(jìn)程節(jié)點(diǎn)*/structsched_entity*curr;/*當(dāng)前正在CPU上運(yùn)行的進(jìn)程的調(diào)度實(shí)體*/unsignedlongnr_spread_over;}；

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)CPU就緒隊(duì)列rq：部分字段structrq{spinlock_t

lock;/*就緒隊(duì)列的自旋鎖*/unsignedlongnr_running;/*就緒隊(duì)列中的進(jìn)程總數(shù)*/unsignedcharidle_at_tick;/*當(dāng)前CPU是否處于空閑狀態(tài)*/structload_weightload;/*就緒隊(duì)列總權(quán)重*/u64nr_switches;/*該CPU進(jìn)程切換次數(shù)*/structcfs_rqcfs;/*該CPU的CFS調(diào)度器的就緒隊(duì)列*/structrt_rqrt;/*該CPU的實(shí)時(shí)進(jìn)程就緒隊(duì)列*/unsignedlongnr_uninterruptible;/*該CPU上可中斷睡眠的進(jìn)程數(shù)*/structtask_struct*curr,*idle;structmm_struct*prev_mm;/*該CPU上最后運(yùn)行進(jìn)程的mm_struct*/intcpu;/*本就緒隊(duì)列對應(yīng)的CPU*/

…

}

完全公平調(diào)度器：CFSCFS調(diào)度器的模塊化調(diào)度五種調(diào)度器類：

stop_sched_class→dl_sched_class→rt_sched_class→fair_sched_class→idle_sched_class調(diào)度器類與調(diào)度策略的對應(yīng)關(guān)系：stop_sched_class：只使用在某些特殊情況，如在CPU之間遷移任務(wù)實(shí)現(xiàn)負(fù)載平衡時(shí)dl_sched_class：SCHED_DEADLINE，實(shí)時(shí)進(jìn)程調(diào)度策略rt_sched_class：SCHED_RR與SCHED_FIFO調(diào)度策略fair_sched_class：SCHED_NORMAL與SCHED_BACH調(diào)度策略idle_sched_class：SCHED_IDLE調(diào)度策略

完全公平調(diào)度器：CFSCFS調(diào)度器的模塊化調(diào)度調(diào)度器類結(jié)構(gòu)：structsched_class{conststructsched_class*next;structtask_struct*(*pick_next_task)(structrq*rq);void(*put_prev_task)(structrq*rq,structtask_struct*p);void(*task_tick)(structrq*rq,structtask_struct*p);

…};3.5.3Linux進(jìn)程調(diào)度算法解析2.CFS調(diào)度器的實(shí)現(xiàn)CFS調(diào)度器類結(jié)構(gòu)定義staticconststructsched_classfair_sched_class={.next=&idle_sched_class,/*指向下一個(gè)調(diào)度器對象*/.enqueue_task=enqueue_task_fair,.dequeue_task=dequeue_task_fair,.pick_next_task=pick_next_task_fair,.put_prev_task=put_prev_task_fair,.task_tick=task_tick_fair,

…};3.5.3Linux進(jìn)程調(diào)度算法解析2.CFS調(diào)度器的實(shí)現(xiàn)CFS調(diào)度器類結(jié)構(gòu)定義staticvoidenqueue_task_fair(structrq*rq,structtask_struct*p,intwakeup)功能：將指定進(jìn)程加入到其所在的cfs_rq就緒隊(duì)列中staticvoiddequeue_task_fair(structrq*rq,structtask_struct*p,intsleep)功能：將指定進(jìn)程從所在cfs_rq中刪除staticvoidyield_task_fair(structrq*rq)功能：調(diào)用進(jìn)程讓出CPU使用權(quán)staticvoidcheck_preempt_wakeup(structrq*rq,structtask_struct*p)功能：檢查剛創(chuàng)建的新進(jìn)程或剛被喚醒的進(jìn)程P是否應(yīng)該搶占當(dāng)前運(yùn)行進(jìn)程3.5.3Linux進(jìn)程調(diào)