1、1,一、 處理器調(diào)度的層次,2.5 處理器調(diào)度,處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源。 處理機(jī)調(diào)度算法對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響。 可把處理機(jī)調(diào)度分成三個(gè)層次： 高級(jí)調(diào)度 中級(jí)調(diào)度 低級(jí)調(diào)度,2,1.高級(jí)調(diào)度 也稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度。 作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)調(diào)度算法選擇外存上處于后備隊(duì)列中的某些作業(yè)調(diào)入內(nèi)存，并為他們分配必要的資源、創(chuàng)建作業(yè)相應(yīng)的進(jìn)程，在作業(yè)完成后還要做結(jié)束階段的善后工作。,3,2.低級(jí)調(diào)度 也稱進(jìn)程/線程調(diào)度、短程調(diào)度。 進(jìn)程調(diào)度的主要功能是根據(jù)一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程/內(nèi)核級(jí)線程獲得處理器，讓它使用。 低級(jí)調(diào)度是操作系統(tǒng)最核心部分，執(zhí)行十分頻繁

2、，其調(diào)度策略的好壞直接影響整個(gè)系統(tǒng)的性能。,4,低級(jí)調(diào)度的調(diào)度方式： （1）非剝奪式（非搶先式） 調(diào)度程序一旦把cpu分配給某一進(jìn)程/線程后，便讓他一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件不能運(yùn)行時(shí)，才將cpu分配給其他進(jìn)程。 這種調(diào)度方式通常用于批處理系統(tǒng)中。 優(yōu)點(diǎn)：簡(jiǎn)單，系統(tǒng)開銷小 缺點(diǎn)：難以滿足緊急任務(wù)的要求，實(shí)時(shí)系統(tǒng)不宜采用。,5,（2）剝奪式（搶先式） 當(dāng)一個(gè)進(jìn)程/線程正在處理器上執(zhí)行時(shí)，調(diào)度程序可根據(jù)某種原則剝奪cpu分配給其他進(jìn)程/線程。 這種調(diào)度方式通常用于分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中。 剝奪的原則： 優(yōu)先權(quán)原則 短作業(yè)（進(jìn)程）優(yōu)先原則 時(shí)間片原則,6,3.中級(jí)調(diào)度 又稱平衡調(diào)度，中程調(diào)

3、度 涉及進(jìn)程在內(nèi)外存間的交換，當(dāng)主存資源緊缺時(shí)將暫不運(yùn)行的進(jìn)程從內(nèi)存調(diào)至外存，此時(shí)這個(gè)進(jìn)程處于“掛起”狀態(tài)；當(dāng)進(jìn)程又具備運(yùn)行條件且主存資源有空閑時(shí)，再將進(jìn)城從外存調(diào)至內(nèi)存。 中級(jí)調(diào)度的主要目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。 低級(jí)調(diào)度是各類操作系統(tǒng)必備的，在純粹的分時(shí)系統(tǒng)或?qū)崟r(shí)系統(tǒng)中，通常不需高級(jí)調(diào)度。一般系統(tǒng)都有高級(jí)調(diào)度和低級(jí)調(diào)度；功能完善的系統(tǒng)引入了中級(jí)調(diào)度。,7,處理器三級(jí)調(diào)度模型,8,處理器兩級(jí)調(diào)度模型,9,二、選擇調(diào)度算法的原則,l.資源利用率（特別是CPU利用率） CPU利用率=CPU有效工作時(shí)間/CPU總的運(yùn)行時(shí)間， CPU總的運(yùn)行時(shí)間=CPU有效工作時(shí)間+CPU空閑等待時(shí)間。 2

4、.吞吐率 單位時(shí)間內(nèi)處理的作業(yè)數(shù)。 評(píng)價(jià)批處理系統(tǒng)性能的另一個(gè)重要指標(biāo)。 3.公平性 確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPU份額或其他資源份額，不會(huì)出現(xiàn)餓死情況。,10,4.響應(yīng)時(shí)間 交互式進(jìn)程從提交一個(gè)請(qǐng)求(命令)到接收到響應(yīng)之間的時(shí)間間隔稱響應(yīng)時(shí)間。 響應(yīng)時(shí)間包括：請(qǐng)求傳送到CPU時(shí)間、CPU處理請(qǐng)求的時(shí)間、響應(yīng)回送到終端顯示器的時(shí)間。 使交互式用戶的響應(yīng)時(shí)間盡可能短，或盡快處理實(shí)時(shí)任務(wù)，這是分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)衡量調(diào)度性能的一個(gè)重要指標(biāo)。,11,5.周轉(zhuǎn)時(shí)間 批處理用戶從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時(shí)間間隔稱作業(yè)周轉(zhuǎn)時(shí)間。 包括四部分時(shí)間：在外存后備隊(duì)列上等待作業(yè)調(diào)度的時(shí)間，相應(yīng)進(jìn)程

5、在就緒隊(duì)列中等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在cpu上執(zhí)行的時(shí)間、進(jìn)程等待I/O操作完成的時(shí)間。 應(yīng)使作業(yè)周轉(zhuǎn)時(shí)間或平均作業(yè)周轉(zhuǎn)時(shí)間盡可能短，這是批處理系統(tǒng)衡量調(diào)度性能的一個(gè)重要指標(biāo)。,12,周轉(zhuǎn)時(shí)間ti 作業(yè)i提交給系統(tǒng)的時(shí)刻是ts，完成時(shí)刻是tf，該作業(yè)的周轉(zhuǎn)時(shí)間ti為：ti = tf ts。 周轉(zhuǎn)時(shí)間=作業(yè)等待時(shí)間+作業(yè)運(yùn)行時(shí)間。 為了提高系統(tǒng)的性能，要讓若干個(gè)用戶的平均作業(yè)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間最小。 平均作業(yè)周轉(zhuǎn)時(shí)間 T T = (ti) / n,13,帶權(quán)周轉(zhuǎn)時(shí)間 wi 如果作業(yè)i的周轉(zhuǎn)時(shí)間為ti，所需運(yùn)行時(shí)間為tk，則 wi=ti /tk 平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間 W W = (wi)

6、/ n,14,三、作業(yè)與進(jìn)程的關(guān)系 1. 作業(yè)的基本概念 （1）作業(yè)（job） 用戶提交給操作系統(tǒng)計(jì)算的一個(gè)獨(dú)立任務(wù)。 （2）作業(yè)步（job step） 一個(gè)作業(yè)可劃分成若干加工步驟，稱為一個(gè)作業(yè)步。 典型的作業(yè)控制過程： “編譯”、“鏈接” “裝入”、“運(yùn)行”,15,（3）作業(yè)控制塊（ Job Control Block ，JCB） 為有效地管理作業(yè)，必須為進(jìn)入系統(tǒng)的每個(gè)作業(yè)建立作業(yè)控制塊。JCB是在批作業(yè)進(jìn)入系統(tǒng)時(shí)，由Spooling系統(tǒng)建立的，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時(shí)，JCB也被撤銷。 JCB保存有系統(tǒng)對(duì)于作業(yè)進(jìn)行管理所需要的全部信息。,16,主要信息見圖。,17,2. 批處

7、理作業(yè)的組織和管理,一個(gè)作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束經(jīng)歷四個(gè)不同的狀態(tài)： 輸入狀態(tài)： 后備狀態(tài)： 執(zhí)行狀態(tài)： 完成狀態(tài)：,18,作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系,19,作業(yè)是任務(wù)實(shí)體，進(jìn)程是完成任務(wù)的執(zhí)行實(shí)體;沒有作業(yè)任務(wù)，進(jìn)程無(wú)事可干，沒有進(jìn)程，作業(yè)任務(wù)沒法完成。 作業(yè)概念更多地用在批處理操作系統(tǒng)，而進(jìn)程則可以用在各種多道程序設(shè)計(jì)系統(tǒng)。,20,2.6 處理器調(diào)度算法,不同系統(tǒng)中由于其類型和系統(tǒng)目標(biāo)不同，采用的調(diào)度算法也不同。 有多種調(diào)度算法，有的算法僅適用于作業(yè)調(diào)度，有的僅適用于進(jìn)程/線程調(diào)度，但大多數(shù)對(duì)二者都適用。 一、先來先服務(wù)（First Come First Served，F(xiàn)CFS ） 最簡(jiǎn)單的

8、調(diào)度算法，即可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。 按作業(yè)（進(jìn)程）來到的先后次序進(jìn)行調(diào)度。,21,優(yōu)點(diǎn)：易于實(shí)現(xiàn) 缺點(diǎn)：調(diào)度程序每次選擇的作業(yè)是等待時(shí)間最久的，而不管作業(yè)的運(yùn)行時(shí)間的長(zhǎng)短，此算法效率低； 有利于長(zhǎng)作業(yè)，不利于短作業(yè),平均周轉(zhuǎn)時(shí)間=9 平均帶權(quán)周轉(zhuǎn)時(shí)間=2.8,例：,22,二、最短作業(yè)（進(jìn)程）優(yōu)先算法SJF：Shortest Job FirstSPF：Shortest Process First,可用于作業(yè)調(diào)度和進(jìn)程調(diào)度。 估計(jì)作業(yè)（進(jìn)程）的CPU運(yùn)行時(shí)間，選取估計(jì)時(shí)間最短的作業(yè)（進(jìn)程）投入運(yùn)行。 上例：,平均周轉(zhuǎn)時(shí)間=8 平均帶權(quán)周轉(zhuǎn)時(shí)間=2.1,23,優(yōu)點(diǎn)： (1)易于實(shí)現(xiàn)。 (

9、2)在一般情況下這種調(diào)度算法比先來先服務(wù)調(diào)度算法的調(diào)度性能比FCFS好。 缺點(diǎn)： (1)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間是用戶估計(jì)的，不一定準(zhǔn)確，所以實(shí)現(xiàn)時(shí)不一定真正做到短作業(yè)優(yōu)先調(diào)度。 (2)對(duì)長(zhǎng)作業(yè)不利 若系統(tǒng)不斷接受新作業(yè)，就有可能使長(zhǎng)作業(yè)長(zhǎng)時(shí)間得不到調(diào)度。出現(xiàn)饑餓現(xiàn)象 (3)缺少剝奪機(jī)制，對(duì)分時(shí)、實(shí)時(shí)系統(tǒng)仍不理想,24,三、響應(yīng)比最高者優(yōu)先算法（HRRF:Highest Response Ratio First）,FCFS與SJF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時(shí)間而忽視了作業(yè)的計(jì)算時(shí)問，SJF只考慮用戶估計(jì)的作業(yè)計(jì)算時(shí)間而忽視了作業(yè)等待時(shí)間。 HRRF是介乎這兩者之間的折衷算法，既考慮

10、作業(yè)等待時(shí)間，又考慮作業(yè)的運(yùn)行時(shí)間，既照顧短作業(yè)又不使長(zhǎng)作業(yè)的等待時(shí)間過長(zhǎng)，改進(jìn)了調(diào)度性能。,25,響應(yīng)比R = 作業(yè)周轉(zhuǎn)時(shí)間 / 作業(yè)處理時(shí)間 =（作業(yè)處理時(shí)間+作業(yè)等待時(shí)間）/ 作業(yè)處理時(shí)間 = 1 +（作業(yè)等待時(shí)間 / 作業(yè)處理時(shí)間）,響應(yīng)比最高者優(yōu)先算法:每次調(diào)度時(shí)，計(jì)算所有作業(yè)的響應(yīng)比，選擇響應(yīng)比最高的調(diào)度。 短作業(yè)容易得到較高響應(yīng)比， 長(zhǎng)作業(yè)等待時(shí)間足夠長(zhǎng)后，也將獲得足夠高的響應(yīng)比，饑餓現(xiàn)象不會(huì)發(fā)生。,26,計(jì)算響應(yīng)比導(dǎo)致一定的時(shí)間開銷，此算法性能介于FCFS和SJF之間。,平均周轉(zhuǎn)時(shí)間=8.4 平均帶權(quán)周轉(zhuǎn)時(shí)間=2.38,上例：,27,四、優(yōu)先級(jí)調(diào)度算法 （HPFHighest

11、Priority First）,為作業(yè)或進(jìn)程確定優(yōu)先級(jí)，選擇優(yōu)先級(jí)最高的作業(yè)或進(jìn)程調(diào)度。 1.兩種方式 非剝奪式：某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去。 剝奪式：當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU，提供給具有更高優(yōu)先級(jí)的進(jìn)程使用。 采用這種調(diào)度算法的關(guān)鍵是如何確定進(jìn)程的優(yōu)先級(jí)、一個(gè)進(jìn)程的優(yōu)先級(jí)確定之后是固定的，還是隨著該進(jìn)程運(yùn)行的情況的變化而變化。,28,2.優(yōu)先級(jí)類型 （1）靜態(tài)優(yōu)先級(jí) 在進(jìn)程創(chuàng)建時(shí)確定優(yōu)先級(jí)，在進(jìn)程運(yùn)行時(shí)保持不變。 確定優(yōu)先級(jí)方法： 系統(tǒng)確定（內(nèi)部?jī)?yōu)先級(jí)） ：考慮進(jìn)程運(yùn)行時(shí)間、使用資源，進(jìn)程類型。

12、用戶確定（外部?jī)?yōu)先級(jí)） ：考慮進(jìn)程緊迫程度，計(jì)費(fèi)與進(jìn)程優(yōu)先級(jí)有關(guān)。 （2）動(dòng)態(tài)優(yōu)先級(jí) 在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先級(jí)，系統(tǒng)在運(yùn)行的過程中，根據(jù)系統(tǒng)的設(shè)計(jì)目標(biāo)，不斷地調(diào)整進(jìn)程的優(yōu)先級(jí)，這種方法的優(yōu)點(diǎn)是能比較客觀地反映進(jìn)程的實(shí)際情況和保證達(dá)到系統(tǒng)設(shè)計(jì)目標(biāo)。 如等待時(shí)間長(zhǎng)優(yōu)先級(jí)可改變 。,29,五、時(shí)間片輪轉(zhuǎn)調(diào)度算法(Round Robin，RR) 分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法。 把CPU劃分成若干時(shí)間片,并且按順序分配給就緒隊(duì)列中的每一個(gè)進(jìn)程，進(jìn)程輪流占有CPU，當(dāng)時(shí)間片用完時(shí)，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該進(jìn)程排在就緒隊(duì)列末尾，等候下一輪調(diào)度。 1.時(shí)間片大小的確定 時(shí)間片大小對(duì)系

13、統(tǒng)性能有很大影響。時(shí)間片太小，會(huì)導(dǎo)致頻繁切換，增大系統(tǒng)開銷；時(shí)間片太大，輪轉(zhuǎn)一次時(shí)間加長(zhǎng)，進(jìn)程在一個(gè)時(shí)間片內(nèi)完成，時(shí)間片輪轉(zhuǎn)算法退化為FCFS算法，無(wú)法滿足交互式用戶需求。 確定時(shí)間片長(zhǎng)度要從進(jìn)程數(shù)目、切換開銷、系統(tǒng)效率和響應(yīng)時(shí)間等多方面加以考慮。,30,2.RR改進(jìn) RR由于采用固定時(shí)間片和僅有一個(gè)就緒隊(duì)列，所以服務(wù)質(zhì)量不夠理想，進(jìn)一步改進(jìn)沿兩個(gè)方向： （1）將固定時(shí)間片改為可變時(shí)間片 引入可變時(shí)間片輪轉(zhuǎn)調(diào)度算法 （2）將單就緒隊(duì)列改為多就緒隊(duì)列 引入多級(jí)反饋隊(duì)列調(diào)度算法,31,六、多級(jí)反饋隊(duì)列調(diào)度算法 （MLFQ：Multi-level Feedback Queue）,設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第一個(gè)隊(duì)列最高，第二個(gè)次之；各個(gè)隊(duì)列時(shí)間片大小也不同，在優(yōu)先級(jí)越高的隊(duì)列中，為每個(gè)進(jìn)程分配的時(shí)間片越小。 處理器調(diào)度先從第一個(gè)就緒進(jìn)程隊(duì)列中選取進(jìn)程，同一隊(duì)列中的進(jìn)程按FCFS算法進(jìn)行排隊(duì)。只有在未選到時(shí)，才從較低級(jí)的就緒進(jìn)程隊(duì)列中選取。 當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先放在第一個(gè)隊(duì)列末尾，到輪到該進(jìn)程執(zhí)行時(shí)，如在該時(shí)間片完成，便可撤離系統(tǒng)；若未完成，則將該進(jìn)程