2023學(xué)年完整公開課版處理機(jī)調(diào)度

處理機(jī)調(diào)度

目錄3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)進(jìn)程調(diào)度實(shí)時調(diào)度3.23.33.4死鎖概述預(yù)防死鎖避免死鎖3.53.633.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)引述調(diào)度：多道程序系統(tǒng)中，決定該輪到哪個任務(wù)運(yùn)行了。作業(yè)要想獲得執(zhí)行所需資源，必須要經(jīng)過調(diào)度。做這項(xiàng)工作的就是調(diào)度程序。

一個批處理作業(yè)，可能經(jīng)歷三級調(diào)度：3.1.1高級調(diào)度（作業(yè)調(diào)度）3.1.2低級調(diào)度（進(jìn)程調(diào)度）3.1.3中級調(diào)度（內(nèi)存調(diào)度）43.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.1處理機(jī)調(diào)度的層次1.高級調(diào)度

作業(yè)調(diào)度或長程調(diào)度，其主要功能是根據(jù)某種算法，把外存上處于后備隊(duì)列中的哪幾個作業(yè)調(diào)入內(nèi)存。2.低級調(diào)度

進(jìn)程調(diào)度或短程調(diào)度，它所調(diào)度的對象是進(jìn)程。低級調(diào)度用于決定就緒隊(duì)列中的哪個進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派進(jìn)程執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。53.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.1處理機(jī)調(diào)度的層次3.中級調(diào)度內(nèi)存調(diào)度目的：提高內(nèi)存利用率和系統(tǒng)吞吐量方法：將那些暫時不能運(yùn)行的進(jìn)程調(diào)至外存上等待（此時進(jìn)程狀態(tài)稱為掛起狀態(tài)）當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時由中級調(diào)度來決定把外存的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存。屬于對換功能（第四章）的一部分63.1.1處理機(jī)調(diào)度的層次3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)低級調(diào)度運(yùn)行頻率最高，不宜復(fù)雜。高級調(diào)度發(fā)生在一批作業(yè)完成，重新調(diào)入一批作業(yè)到內(nèi)存的時候，執(zhí)行頻率低中級調(diào)度介于上述兩者之間。73.2進(jìn)程調(diào)度進(jìn)程調(diào)度的方式（1）非搶占方式：進(jìn)程占用處理機(jī)直至自愿放棄或發(fā)生某事件被阻塞時，在把處理機(jī)分配給其他進(jìn)程。（2）搶占方式：允許暫停某個正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配給另一個進(jìn)程。

搶占必須遵循一定的原則：優(yōu)先權(quán)原則，時間片原則等8調(diào)度算法調(diào)度算法：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。不同類型的系統(tǒng)和系統(tǒng)目標(biāo)，采用不同的調(diào)度算法。常用的調(diào)度算法先來先服務(wù) 短作業(yè)（進(jìn)程）優(yōu)先 優(yōu)先權(quán)—高響應(yīng)比優(yōu)先 時間片輪轉(zhuǎn)法 調(diào)度算法有的適用于高級調(diào)度，有的適用于低級調(diào)度，有的既可用于高級調(diào)度，也可用于低級調(diào)度。3.2進(jìn)程調(diào)度9調(diào)度算法需要了解幾個時間的參數(shù)（1）服務(wù)時間Ts：進(jìn)程預(yù)期需要的執(zhí)行時間。（2）周轉(zhuǎn)時間T：進(jìn)程從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束所經(jīng)歷的全部時間。（3）帶權(quán)周轉(zhuǎn)時間T/Ts：周轉(zhuǎn)時間/服務(wù)時間。進(jìn)程到達(dá)時間服務(wù)時間A03B26C44D65E823.2進(jìn)程調(diào)度調(diào)度算法1.先來先服務(wù)調(diào)度算法（FCFS）調(diào)度策略：非搶占每一個進(jìn)入系統(tǒng)的進(jìn)程都放入就緒隊(duì)列當(dāng)前運(yùn)行的進(jìn)程結(jié)束，選擇就緒隊(duì)列中等待最久的進(jìn)程（最先來的）適用于高級調(diào)度和低級調(diào)度3.2進(jìn)程調(diào)度11調(diào)度算法1.先來先服務(wù)調(diào)度算法（FCFS）A3B6C4D5E205101520ABCDEABCDEDEE3.2進(jìn)程調(diào)度調(diào)度算法1.先來先服務(wù)調(diào)度算法（FCFS）12有利于長作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。3.2進(jìn)程調(diào)度13調(diào)度算法2.短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法(SJF/SPF)調(diào)度策略：非搶占當(dāng)前進(jìn)程運(yùn)行結(jié)束后選擇就緒隊(duì)列中服務(wù)時間最短的進(jìn)程適用于高級調(diào)度和低級調(diào)度3.2進(jìn)程調(diào)度142.短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法(SJF/SPF)01234567891011121314151617181920ABCDEBCDE63452BCDECDDAA15有效降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐率缺點(diǎn)：對長作業(yè)不利，如D，甚至長作業(yè)無法被調(diào)度沒考慮作業(yè)緊迫性根據(jù)用戶估計(jì)的執(zhí)行時間而定，會有人的因素干擾算法。2.短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法(SJF/SPF)16調(diào)度算法3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法(HRRN)優(yōu)先權(quán)調(diào)度算法的類型（1）非搶占式優(yōu)先權(quán)算法進(jìn)程運(yùn)行直到完成或因某事件放棄處理機(jī)（2）搶占式優(yōu)先權(quán)調(diào)度算法進(jìn)程執(zhí)行期間，有出現(xiàn)另一個優(yōu)先權(quán)更高的進(jìn)程，則調(diào)度程序立即停止當(dāng)前進(jìn)程，將處理機(jī)分配給新到的進(jìn)程。3.2進(jìn)程調(diào)度調(diào)度算法3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法(HRRN)優(yōu)先權(quán)的類型（1）靜態(tài)優(yōu)先權(quán)創(chuàng)建進(jìn)程時確定，在進(jìn)程的整個運(yùn)行期間保持不變。（2）動態(tài)優(yōu)先權(quán)創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變。173.2進(jìn)程調(diào)度調(diào)度算法3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法(HRRN)進(jìn)程到達(dá)時間服務(wù)時間A03B26C44D65E82183.2進(jìn)程調(diào)度193.高優(yōu)先權(quán)優(yōu)先調(diào)度算法(HRRN)調(diào)度策略：非搶占策略選擇就緒隊(duì)列中響應(yīng)比(優(yōu)先權(quán))最高的進(jìn)程A3B6C4D5E205101520B(1+1/6)C(1+5/4)D(1+3/5)E(1+1/2)D(1+7/5)E(1+5/2)BCDEA20等待時間相同時，有利于短作業(yè)要求服務(wù)時間相同時，先來先服務(wù)長作業(yè)隨著等待時間優(yōu)先級增加，從而可以獲得處理機(jī)。折中算法，但每次調(diào)度前要計(jì)算響應(yīng)比，增加系統(tǒng)開銷。3高優(yōu)先權(quán)優(yōu)先調(diào)度算法(HRRN)21調(diào)度算法4.基于時間片的輪轉(zhuǎn)調(diào)度算法（RR）調(diào)度策略：搶占策略僅適用于低級調(diào)度切換進(jìn)程的時機(jī)若一個時間片尚未用完，進(jìn)程已完成，將它從就緒隊(duì)列中刪除，啟動一個新的時間片。時間片用完，由調(diào)度程序停止該進(jìn)程，再將CPU分給隊(duì)首進(jìn)程。時間片的選擇最好略大于一次典型的交互所需要的時間3.2進(jìn)程調(diào)度22調(diào)度算法4.基于時間片的輪轉(zhuǎn)調(diào)度算法（RR）進(jìn)程到達(dá)時間服務(wù)時間A03B26C44D65E823.2進(jìn)程調(diào)度234基于時間片的輪轉(zhuǎn)調(diào)度算法RR(4)01234567891011121314151617181920ABCDEBCDE63452BCDBDBEBEDEDDA24ABCDE05101520四個單位ABCDE05101520一個單位4基于時間片的輪轉(zhuǎn)調(diào)度算法

RR(4)和RR(1)的對比25調(diào)度算法練習(xí)題1請按照FCFS、SPF、HRRN、RR(1)算法對上面的進(jìn)程進(jìn)行調(diào)度，要求畫出調(diào)度過程。進(jìn)程名達(dá)到時間服務(wù)時間A03B16C32D55E74調(diào)度算法練習(xí)題2請按照FCFS、SPF、HRRN、RR(2)算法對上面的進(jìn)程進(jìn)行調(diào)度，要求畫出調(diào)度過程。進(jìn)程名達(dá)到時間服務(wù)時間A03B24C37D62E94262701234567891011121314151617181920ABCDEBCDE43724BCCDDEEAFCFS2801234567891011121314151617181920ABCDEBCDE43724BCCDCECASPF2901234567891011121314151617181920ABCDEBCDE43724B(1/4)C(0/7)C(4/7)D(1/2)D(8/2)E(5/4)EAHRRN3001234567891011121314151617181920ABCDEBCDE43724BAACBCBBDCDCECEECCEECCARR(2)31表中列出了五個進(jìn)程的執(zhí)行時間在某一時刻這五個進(jìn)程按照P0，P1，P2，P3，P4的順序同時到達(dá)，現(xiàn)分別采用FCFS（先來先服務(wù)）、SPF（短進(jìn)程優(yōu)先）算法對進(jìn)程進(jìn)行調(diào)度，進(jìn)程名執(zhí)行時間（ms）P020P115P235P325P440請?jiān)诒砀裰刑顚懜鬟M(jìn)程的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，并計(jì)算進(jìn)程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。調(diào)度算法323.3實(shí)時操作系統(tǒng)Real-TimeOperatingSystem對外部輸入的信息，實(shí)時操作系統(tǒng)能夠在規(guī)定的時間內(nèi)處理完畢并做出反應(yīng)正確性：不僅依靠計(jì)算邏輯的正確，而且要求在規(guī)定的時間內(nèi)得到該結(jié)果通常給定一個開始時間或者結(jié)束時間的最后期限多用于工業(yè)、軍事等控制領(lǐng)域或?qū)崟r信息處理方面333.3實(shí)時操作系統(tǒng)

嵌入式操作系統(tǒng)的實(shí)時性都比較強(qiáng)，可歸為RTOSVxWorks操作系統(tǒng)美國WindRiver公司于1983年設(shè)計(jì)開發(fā)，實(shí)時性強(qiáng)，內(nèi)核可極微（據(jù)說最小可8K），可靠性較高等，主要