操作系統(tǒng)第三章1

1、Operating SystemOperating SystemPage 12021-10-15Operating SystemOperating SystemPage 22021-10-15q知識(shí)點(diǎn)知識(shí)點(diǎn)v處理機(jī)調(diào)度及調(diào)度算法處理機(jī)調(diào)度及調(diào)度算法v實(shí)時(shí)系統(tǒng)的進(jìn)程（線程）調(diào)度算法實(shí)時(shí)系統(tǒng)的進(jìn)程（線程）調(diào)度算法v產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件v預(yù)防死鎖的方法，死鎖的檢測與解除預(yù)防死鎖的方法，死鎖的檢測與解除 v銀行家算法銀行家算法Operating SystemOperating SystemPage 32021-10-15q重點(diǎn)重點(diǎn)v掌握掌握進(jìn)程調(diào)度進(jìn)程調(diào)度算法，各適用于何種

2、情況算法，各適用于何種情況 v理解產(chǎn)生理解產(chǎn)生死鎖死鎖的原因的原因 v掌握掌握銀行家算法銀行家算法避免避免死鎖死鎖Operating SystemOperating SystemPage 42021-10-15q處理機(jī)是計(jì)算機(jī)系統(tǒng)中的處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源重要資源q在多道程序環(huán)境下，進(jìn)程數(shù)目通常在多道程序環(huán)境下，進(jìn)程數(shù)目通常多于處理機(jī)的多于處理機(jī)的數(shù)目數(shù)目q系統(tǒng)必須按一定方法系統(tǒng)必須按一定方法動(dòng)態(tài)地動(dòng)態(tài)地把處理機(jī)把處理機(jī)分配給分配給就緒就緒隊(duì)列中的一個(gè)進(jìn)程隊(duì)列中的一個(gè)進(jìn)程q處理機(jī)處理機(jī)利用率和系統(tǒng)性能利用率和系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間）（吞吐量、響應(yīng)時(shí)間）在很大程度上在很大程度上取決于

3、取決于處理機(jī)處理機(jī)調(diào)度調(diào)度分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。WHAT：什么是處理機(jī)調(diào)度，按什么原則分配：什么是處理機(jī)調(diào)度，按什么原則分配CPU進(jìn)進(jìn)程調(diào)度算法程調(diào)度算法WHEN：何時(shí)分配：何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī) HOW：如何分配：如何分配CPU CPU調(diào)度過程（進(jìn)程的上下調(diào)度過程（進(jìn)程的上下文切換）文切換）Operating SystemOperating SystemPage 52021-10-15q 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q作業(yè)調(diào)度作業(yè)調(diào)度q

4、進(jìn)程調(diào)度進(jìn)程調(diào)度q 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q 預(yù)防死鎖的方法預(yù)防死鎖的方法 q 死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 62021-10-15q高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)Operating SystemOperating SystemPage 72021-10-15q作業(yè)的概念作業(yè)的概念-批處理系統(tǒng)中使用批處理系統(tǒng)中使用v作業(yè)作業(yè)包括用戶程序、所需的數(shù)據(jù)及作業(yè)說明書包括用戶程序、所

5、需的數(shù)據(jù)及作業(yè)說明書v作業(yè)的狀態(tài)：作業(yè)的狀態(tài)：一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般需要經(jīng)歷一般需要經(jīng)歷收容、運(yùn)行、完成收容、運(yùn)行、完成三個(gè)階段，與三個(gè)階段，與之相對應(yīng)的是作業(yè)的三種狀態(tài)之相對應(yīng)的是作業(yè)的三種狀態(tài)后備后備狀態(tài)狀態(tài)運(yùn)行運(yùn)行狀態(tài)狀態(tài)完成完成狀態(tài)狀態(tài)Operating SystemOperating SystemPage 82021-10-15運(yùn)行狀態(tài)運(yùn)行狀態(tài)后備狀態(tài)后備狀態(tài)完成狀態(tài)完成狀態(tài)就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O完成完成I/O請求請求時(shí)間片完時(shí)間片完作業(yè)作業(yè)注冊注冊作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程進(jìn)程調(diào)度調(diào)度終止終止作業(yè)作業(yè)q作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換狀態(tài)間轉(zhuǎn)換內(nèi)存內(nèi)存外存

6、外存高級(jí)高級(jí)調(diào)度調(diào)度低級(jí)低級(jí)調(diào)度調(diào)度交換區(qū)中級(jí)中級(jí)調(diào)度調(diào)度Operating SystemOperating SystemPage 92021-10-153.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3.1.1 調(diào)度調(diào)度 的層次的層次1. 高級(jí)調(diào)度高級(jí)調(diào)度(High Scheduling)：作業(yè)調(diào)度：作業(yè)調(diào)度 2. 低級(jí)調(diào)度低級(jí)調(diào)度(Low Level Scheduling) ：進(jìn)程調(diào)度：進(jìn)程調(diào)度3. 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Level Scheduling) 批處理系統(tǒng)中有高級(jí)調(diào)度和低級(jí)調(diào)度批處理系統(tǒng)中有高級(jí)調(diào)度和低級(jí)調(diào)度分時(shí)系統(tǒng)用戶命令直接進(jìn)入內(nèi)存，只有低級(jí)調(diào)度分時(shí)

7、系統(tǒng)用戶命令直接進(jìn)入內(nèi)存，只有低級(jí)調(diào)度Operating SystemOperating SystemPage 102021-10-15q高級(jí)調(diào)度高級(jí)調(diào)度(High Scheduling)(High Scheduling)v主要任務(wù)是按一定的原則對外存上處于后備狀主要任務(wù)是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配分配內(nèi)存、內(nèi)存、輸入輸入/ /輸出設(shè)備等輸出設(shè)備等必要的資源必要的資源，并，并建立建立相應(yīng)的相應(yīng)的進(jìn)程進(jìn)程，放入放入就緒就緒隊(duì)列隊(duì)列，以使該作業(yè)的進(jìn)程獲得，以使該作業(yè)的進(jìn)程獲得競爭處理機(jī)的權(quán)利競爭處理機(jī)的權(quán)利v也稱為也稱為接納調(diào)度（

8、接納調(diào)度（Admission SchedulingAdmission Scheduling）v高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天Operating SystemOperating SystemPage 112021-10-15在每次作業(yè)調(diào)度時(shí)，須決定：在每次作業(yè)調(diào)度時(shí)，須決定：v接納多少個(gè)作業(yè)接納多少個(gè)作業(yè) 即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多多 道程序度道程序度（Degree of Multiprogramming）作業(yè)太多作業(yè)太多 服務(wù)質(zhì)量下降服務(wù)質(zhì)量下降作業(yè)太少作業(yè)太少 資源利用率低資源利用率低v接納

9、哪些作業(yè)接納哪些作業(yè) 取決于作業(yè)調(diào)度算法取決于作業(yè)調(diào)度算法先來先服務(wù)先來先服務(wù)短作業(yè)優(yōu)先短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度響應(yīng)比調(diào)度周轉(zhuǎn)時(shí)間太長系統(tǒng)吞吐量太低 適當(dāng)?shù)恼壑裕杭丛试S多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。：即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。止的這段時(shí)間間隔。：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。Operating SystemOperating SystemPage 122021-10-15q 低級(jí)調(diào)度低級(jí)調(diào)度v主要任務(wù)是按照某種主要任務(wù)是按照某種

10、策略和方法策略和方法選取選取一個(gè)處一個(gè)處于于就緒就緒狀態(tài)的進(jìn)程，將處理機(jī)狀態(tài)的進(jìn)程，將處理機(jī)分配分配給它給它v低級(jí)調(diào)度的時(shí)間尺度通常是低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)毫秒級(jí)的。由于的。由于低級(jí)調(diào)度算法的低級(jí)調(diào)度算法的頻繁使用頻繁使用，要求在實(shí)現(xiàn)時(shí)做，要求在實(shí)現(xiàn)時(shí)做到到高效高效Operating SystemOperating SystemPage 132021-10-15q 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Level (Intermediate-Level Scheduling)Scheduling)v引入目的引入目的是為了提高是為了提高內(nèi)存利用率內(nèi)存利用率和和系統(tǒng)吞吐系統(tǒng)吞吐量。量

11、。v主要任務(wù)主要任務(wù)是按照給定的是按照給定的原則和策略原則和策略，將那些，將那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存，將處于外存暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存，將處于外存對換區(qū)對換區(qū)中的重又具備運(yùn)行條件的就緒進(jìn)程中的重又具備運(yùn)行條件的就緒進(jìn)程調(diào)調(diào)入內(nèi)存入內(nèi)存 Operating SystemOperating SystemPage 142021-10-15q 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)Operating SystemOperating System1.共同目標(biāo)共同目標(biāo)Page 152021-10-15q 具有具有公平性公平性q 資源資源利用率高利用率

12、高（特別是（特別是CPUCPU利用率），利用率），盡可能保持忙的狀態(tài)盡可能保持忙的狀態(tài)q 系統(tǒng)資源使用的平衡性系統(tǒng)資源使用的平衡性O(shè)perating SystemOperating SystemPage 162021-10-152. 批處理系統(tǒng)的目標(biāo)v周轉(zhuǎn)時(shí)間短（周轉(zhuǎn)時(shí)間短（P90P90）平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間niiTnT11niSiiTTnW11帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：進(jìn)程（或作業(yè)）的進(jìn)程（或作業(yè)）的周轉(zhuǎn)時(shí)周轉(zhuǎn)時(shí)間間T T與運(yùn)行時(shí)間與運(yùn)行時(shí)間T TS S之比，即之比，即W=T/TW=T/TS S 。而。而平均平均帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間則可表示為則可表示為: : Operating S

13、ystemOperating Systemv系統(tǒng)吞吐量高系統(tǒng)吞吐量高吞吐量吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響大影響v處理機(jī)利用率高處理機(jī)利用率高v各類資源的平衡利用各類資源的平衡利用使內(nèi)存、外存和使內(nèi)存、外存和I/OI/O設(shè)備的利用率高設(shè)備的利用率高Page 172021-10-15Operating SystemOperating SystemPage 182021-10-153. 分時(shí)系統(tǒng)的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)v響應(yīng)時(shí)間快響應(yīng)時(shí)間快響應(yīng)時(shí)間響應(yīng)時(shí)間是指從用戶通過鍵盤提交一個(gè)請求是

14、指從用戶通過鍵盤提交一個(gè)請求開始，直至系統(tǒng)中開始，直至系統(tǒng)中首次首次產(chǎn)生產(chǎn)生響應(yīng)響應(yīng)為止的時(shí)間為止的時(shí)間響應(yīng)時(shí)間與服務(wù)的復(fù)雜性適應(yīng)即可響應(yīng)時(shí)間與服務(wù)的復(fù)雜性適應(yīng)即可Operating SystemOperating System4.實(shí)時(shí)系統(tǒng)的目標(biāo)實(shí)時(shí)系統(tǒng)的目標(biāo)v截止時(shí)間保證截止時(shí)間保證截止時(shí)間截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間間或必須完成的最遲時(shí)間截止時(shí)間是截止時(shí)間是實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)中的重要指標(biāo)中的重要指標(biāo)v可預(yù)測可預(yù)測提前預(yù)測做出準(zhǔn)備處理提前預(yù)測做出準(zhǔn)備處理Page 192021-10-15Operating SystemOperati

15、ng SystemPage 202021-10-15q 調(diào)度算法調(diào)度算法v 周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短v 響應(yīng)時(shí)間快響應(yīng)時(shí)間快v 截止時(shí)間保證截止時(shí)間保證批處理系統(tǒng)批處理系統(tǒng)分時(shí)系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)Operating SystemOperating SystemPage 212021-10-15q 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q作業(yè)調(diào)度作業(yè)調(diào)度q進(jìn)程調(diào)度進(jìn)程調(diào)度q 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q 預(yù)防死鎖的方法預(yù)防死鎖的方法 q 死鎖的檢測與解除死鎖的檢測與解除Operating Syste

16、mOperating SystemPage 222021-10-15q 先來先服務(wù)先來先服務(wù)q 短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法q 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法Operating SystemOperating SystemPage 232021-10-15q 先來先服務(wù)先來先服務(wù)(FCFS)調(diào)度算法調(diào)度算法v按照作業(yè)按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)進(jìn)程進(jìn)入系統(tǒng)/就緒隊(duì)列的就緒隊(duì)列的先后次序先后次序進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長的作業(yè)待時(shí)間最長的作業(yè)/進(jìn)程進(jìn)程v是一種最簡單的調(diào)度算法，即可用于是一種最簡單的調(diào)度算法，即可用于作業(yè)調(diào)作業(yè)調(diào)度度

17、，也可用于，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度q 幾個(gè)術(shù)語幾個(gè)術(shù)語v到達(dá)時(shí)間、開始時(shí)間到達(dá)時(shí)間、開始時(shí)間v完成時(shí)間、等待時(shí)間完成時(shí)間、等待時(shí)間v周轉(zhuǎn)時(shí)間：完成時(shí)間周轉(zhuǎn)時(shí)間：完成時(shí)間-到達(dá)時(shí)間到達(dá)時(shí)間v帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間服務(wù)時(shí)間Operating SystemOperating SystemPage 242021-10-15作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間平均平均04A13B25C32D44E044476先來先服務(wù)（先進(jìn)先出）：先來先服務(wù)（先進(jìn)先出）：71210121411141

18、8141225.53.592.8A A A A B B B C C C C C D D E E E E05101518tOperating SystemOperating SystemPage 252021-10-15q 先來先服務(wù)先來先服務(wù)（先進(jìn)先出）（先進(jìn)先出）優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)v 比較有利于比較有利于長作業(yè)長作業(yè) ，而不利于，而不利于短作業(yè)短作業(yè) v 有利于有利于CPU繁忙型作業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程） ，而不利于，而不利于I/O繁忙型作業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程）Operating SystemOperating SystemPage 262021-10-15q短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先

19、調(diào)度算法SJFSJFv短作業(yè)短作業(yè) 優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ FSJ F，以要求，以要求運(yùn)行時(shí)間運(yùn)行時(shí)間長短長短進(jìn)行調(diào)度，即啟動(dòng)估計(jì)運(yùn)行時(shí)間最短的作進(jìn)行調(diào)度，即啟動(dòng)估計(jì)運(yùn)行時(shí)間最短的作業(yè)業(yè)v可以分別用于可以分別用于作業(yè)調(diào)度作業(yè)調(diào)度和和進(jìn)程調(diào)度進(jìn)程調(diào)度Operating SystemOperating SystemPage 272021-10-15作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間平均平均04A13B25C32D44E0441短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJF）：）：4633/26988/391399/41

20、3181616/582.1A A A AB B BC C C C CD DE E E E05101518tOperating SystemOperating SystemPage 282021-10-15qFCFS/SJF調(diào)度算法的性能調(diào)度算法的性能SJFSJF能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量 作業(yè)作業(yè)調(diào)度調(diào)度 情況情況 算法算法進(jìn)程名進(jìn)程名ABCDE平均平均到達(dá)時(shí)間到達(dá)時(shí)間01234服務(wù)時(shí)間服務(wù)時(shí)間43524FCFS完成時(shí)間完成時(shí)間47121418周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJ

21、F完成時(shí)間完成時(shí)間4918613周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12.673.11.52.252.1SJFSJF平均周轉(zhuǎn)平均周轉(zhuǎn)時(shí)間和平均帶時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間明權(quán)周轉(zhuǎn)時(shí)間明顯改善顯改善Operating SystemOperating SystemPage 292021-10-15qSJ F調(diào)度算法也存在不容忽視的缺點(diǎn)調(diào)度算法也存在不容忽視的缺點(diǎn)v對對長作業(yè)不利長作業(yè)不利。 由于調(diào)度程序總是優(yōu)先調(diào)度那由于調(diào)度程序總是優(yōu)先調(diào)度那些些( (即使是后進(jìn)來的即使是后進(jìn)來的) )短作業(yè)短作業(yè) ，將導(dǎo)致長作業(yè)，將導(dǎo)致長作業(yè) 長長期不被調(diào)度期不被調(diào)度饑餓饑餓v完全未考慮作業(yè)完全未考

22、慮作業(yè) 的的緊迫程度緊迫程度，因而不能保證，因而不能保證緊緊迫性迫性作業(yè)作業(yè) 會(huì)被會(huì)被及時(shí)處理及時(shí)處理v由于作業(yè)由于作業(yè) 的長短只是根據(jù)的長短只是根據(jù)用戶用戶所提供的所提供的估計(jì)執(zhí)估計(jì)執(zhí)行時(shí)間行時(shí)間而定的，而用戶又可能會(huì)而定的，而用戶又可能會(huì)有意或無意有意或無意地地縮縮短短其作業(yè)的估計(jì)其作業(yè)的估計(jì)運(yùn)行時(shí)間運(yùn)行時(shí)間，致使該算法不一定能，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。真正做到短作業(yè)優(yōu)先調(diào)度。Operating SystemOperating SystemPage 302021-10-15q先來先服務(wù)先來先服務(wù)q短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法q優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)優(yōu)先調(diào)度算法Opera

23、ting SystemOperating SystemPage 312021-10-15q根據(jù)作業(yè)的緊迫程度賦予作業(yè)相應(yīng)的優(yōu)先級(jí)，優(yōu)根據(jù)作業(yè)的緊迫程度賦予作業(yè)相應(yīng)的優(yōu)先級(jí)，優(yōu)先級(jí)高的優(yōu)先運(yùn)行先級(jí)高的優(yōu)先運(yùn)行q優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)：優(yōu)先級(jí)不變靜態(tài)優(yōu)先權(quán)：優(yōu)先級(jí)不變v動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)Operating SystemOperating SystemPage 322021-10-15進(jìn)程進(jìn)程名名到達(dá)到達(dá)時(shí)間時(shí)間服務(wù)服務(wù)時(shí)間時(shí)間靜態(tài)優(yōu)靜態(tài)優(yōu)先權(quán)先權(quán)開始開始時(shí)間時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間平均平均靜態(tài)優(yōu)先權(quán)（靜態(tài)優(yōu)先權(quán)（1為高優(yōu)先權(quán)）為高優(yōu)先權(quán)）04A4

24、13B225C332D544E1044148418111010/311161414/516181515/29.42.93Operating SystemOperating SystemPage 332021-10-15q高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（HRF）v是是FCFS和和SJF的結(jié)合，既考慮運(yùn)行時(shí)間又的結(jié)合，既考慮運(yùn)行時(shí)間又考慮到達(dá)時(shí)間，克服了兩種算法的缺點(diǎn)考慮到達(dá)時(shí)間，克服了兩種算法的缺點(diǎn)v調(diào)度策略調(diào)度策略：響應(yīng)比：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)最高的作業(yè)優(yōu)先啟動(dòng)v因因等待時(shí)間等待時(shí)間+服務(wù)時(shí)間服務(wù)時(shí)間=該作業(yè)的該作業(yè)的響應(yīng)時(shí)間響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比

25、響應(yīng)比RP。據(jù)此，又。據(jù)此，又可表示為可表示為時(shí)時(shí)間間務(wù)務(wù)時(shí)時(shí)間間權(quán)權(quán)務(wù)務(wù)時(shí)時(shí)間間等等待待+ + 要要求求服服優(yōu)優(yōu)先先= =要要求求服服時(shí)間務(wù)時(shí)間響應(yīng)時(shí)間權(quán)務(wù)時(shí)間務(wù)時(shí)間等等待待+ + 要要求求服服優(yōu)優(yōu)先先= = =要要求求服服要要求求服服Operating SystemOperating SystemPage 342021-10-15q 對對HRF的小結(jié)的小結(jié)v等待時(shí)間相同等待時(shí)間相同的作業(yè)，則的作業(yè)，則要求服務(wù)的時(shí)間愈要求服務(wù)的時(shí)間愈短短，其，其優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高，v要求服務(wù)的時(shí)間相同要求服務(wù)的時(shí)間相同的作業(yè)，則的作業(yè)，則等待時(shí)間愈等待時(shí)間愈長長，其，其優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高，v長作業(yè)，優(yōu)先

26、權(quán)長作業(yè)，優(yōu)先權(quán)隨等待時(shí)間的增加隨等待時(shí)間的增加而提高，而提高，其等待時(shí)間足夠長時(shí)，其優(yōu)先權(quán)便可升到很其等待時(shí)間足夠長時(shí)，其優(yōu)先權(quán)便可升到很高，高， 從而也可獲得處理機(jī)從而也可獲得處理機(jī)v這種算法是一種折衷，既照顧了短作業(yè)，又這種算法是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長作考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長作業(yè)長期得不到服務(wù)。業(yè)長期得不到服務(wù)。缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開銷缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開銷時(shí)間務(wù)時(shí)間響應(yīng)時(shí)間權(quán)務(wù)時(shí)間務(wù)時(shí)間等等待待+ + 要要求求服服優(yōu)優(yōu)先先= = =要要求求服服要要求求服服對短作業(yè)有利對短作業(yè)有利是先來先服務(wù)是先來先服

27、務(wù)對長作業(yè)有利對長作業(yè)有利Operating SystemOperating Systemq例：單道程序系統(tǒng)中，下列作業(yè)若采用響應(yīng)比高者優(yōu)先的算法調(diào)度，請列出各個(gè)作業(yè)的運(yùn)行次序。作業(yè)名作業(yè)名提交時(shí)間提交時(shí)間計(jì)算時(shí)間計(jì)算時(shí)間A8:5090分鐘B9:0024分鐘C9:3060分鐘Page 352021-10-15Operating SystemOperating SystemPage 362021-10-15q處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q作業(yè)調(diào)度作業(yè)調(diào)度q進(jìn)程調(diào)度進(jìn)程調(diào)度q實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件

28、 q預(yù)防死鎖的方法預(yù)防死鎖的方法 q死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 372021-10-15q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù) 保存保存當(dāng)前進(jìn)程的處理機(jī)信息，按一定當(dāng)前進(jìn)程的處理機(jī)信息，按一定的調(diào)度算法從就緒隊(duì)列中的調(diào)度算法從就緒隊(duì)列中選中選中一個(gè)進(jìn)程，一個(gè)進(jìn)程，將其狀態(tài)改為運(yùn)行狀態(tài)，將選中進(jìn)行的處將其狀態(tài)改為運(yùn)行狀態(tài)，將選中進(jìn)行的處理機(jī)信息理機(jī)信息恢復(fù)恢復(fù)到處理機(jī)中，把到處理機(jī)中，把CPUCPU的使用權(quán)的使用權(quán)交給被選中的進(jìn)程。交給被選中的進(jìn)程。Operating SystemOperating SystemPage 3

29、82021-10-15q 非搶占方式非搶占方式(Non-preemptive Mode)(Non-preemptive Mode)q 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)Operating SystemOperating SystemPage 392021-10-15q 非搶占方式非搶占方式(Non-preemptive Mode)(Non-preemptive Mode) 不能暫停在不能暫停在CPUCPU上執(zhí)行的進(jìn)程，上執(zhí)行的進(jìn)程，需要等到其完成需要等到其完成或發(fā)生某種事件而進(jìn)入阻塞狀態(tài)時(shí)，才把處理機(jī)或發(fā)生某種事件而進(jìn)入阻塞狀態(tài)時(shí)，才把處理機(jī)分

30、配給其他進(jìn)程分配給其他進(jìn)程v引起進(jìn)程調(diào)度的因素引起進(jìn)程調(diào)度的因素- -進(jìn)程主動(dòng)讓出進(jìn)程主動(dòng)讓出cpucpu正在執(zhí)行的進(jìn)程執(zhí)行完畢，正在執(zhí)行的進(jìn)程執(zhí)行完畢， 或因發(fā)生某事或因發(fā)生某事件而不能再繼續(xù)執(zhí)行件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出執(zhí)行中的進(jìn)程因提出I/OI/O請求而暫停執(zhí)行；請求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如操作，如waitwait、BlockBlock、WakeupWakeup原語原語優(yōu)點(diǎn)優(yōu)點(diǎn)：算法簡單，：算法簡單，系統(tǒng)開銷小系統(tǒng)開銷小缺點(diǎn)缺點(diǎn)：緊急任務(wù)不：緊急任務(wù)不能及時(shí)響應(yīng)；短進(jìn)能及時(shí)響應(yīng)；短進(jìn)程到達(dá)要等待長進(jìn)程到達(dá)要等待

31、長進(jìn)程運(yùn)行結(jié)束程運(yùn)行結(jié)束Operating SystemOperating SystemPage 402021-10-15q 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode) 可以立即暫停正在執(zhí)行的進(jìn)程可以立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程。配給這個(gè)更為重要或緊迫的進(jìn)程。搶占式調(diào)度主要有以下原則搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則優(yōu)先權(quán)原則 允許高優(yōu)先權(quán)的新到進(jìn)程搶允許高優(yōu)先權(quán)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)占當(dāng)前進(jìn)程的處理機(jī)短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先原則優(yōu)先原則允許執(zhí)行時(shí)間短允許執(zhí)行時(shí)間短的新到進(jìn)程搶占當(dāng)前進(jìn)程

32、的處理機(jī)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī) 時(shí)間片原則時(shí)間片原則 時(shí)間片用完后停止執(zhí)行，時(shí)間片用完后停止執(zhí)行，重新進(jìn)行調(diào)度，適用于分時(shí)系統(tǒng)重新進(jìn)行調(diào)度，適用于分時(shí)系統(tǒng) 優(yōu)點(diǎn)優(yōu)點(diǎn)：適于時(shí)間要：適于時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)求嚴(yán)格的實(shí)時(shí)系統(tǒng)缺點(diǎn)缺點(diǎn)：調(diào)度算法復(fù)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大雜，系統(tǒng)開銷大Operating SystemOperating Systemq時(shí)間片輪轉(zhuǎn)算法時(shí)間片輪轉(zhuǎn)算法q優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法q多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法Page 412021-10-15Operating SystemOperating SystemPage 422021-10-15q 簡單的時(shí)間

33、片輪轉(zhuǎn)法簡單的時(shí)間片輪轉(zhuǎn)法(RRRound Robin)v系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每個(gè)進(jìn)程依次執(zhí)行一個(gè)時(shí)間片成一個(gè)隊(duì)列，每個(gè)進(jìn)程依次執(zhí)行一個(gè)時(shí)間片v時(shí)間片的大小從幾時(shí)間片的大小從幾ms到幾百到幾百ms優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時(shí)間片中采用：時(shí)間片+優(yōu)先權(quán)優(yōu)先權(quán)Operating SystemOperating SystemPag

34、e 432021-10-15v分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇時(shí)間片選擇問題問題固定時(shí)間片固定時(shí)間片可變時(shí)間片可變時(shí)間片時(shí)間片大?。禾☆l繁切換，太大變?yōu)橄葋硐葧r(shí)間片大?。禾☆l繁切換，太大變?yōu)橄葋硐确?wù)服務(wù)與與時(shí)間片大小時(shí)間片大小有關(guān)的因素有關(guān)的因素系統(tǒng)響應(yīng)時(shí)間系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)就緒進(jìn)程個(gè)數(shù)CPUCPU能力能力 Operating SystemOperating SystemPage 442021-10-15基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 （1）系統(tǒng)對響應(yīng)時(shí)間的要求）系統(tǒng)對響應(yīng)時(shí)間的要求 數(shù)目N和時(shí)間片q成反比，即T=Nq，因此在進(jìn)程數(shù)一

35、定時(shí)，作為分時(shí)系統(tǒng)首先就是必須滿足系統(tǒng)對響應(yīng)時(shí)間的要求。時(shí)間片的長短將正比于系統(tǒng)所要求的響應(yīng)時(shí)間。（2）就緒隊(duì)列中進(jìn)程的數(shù)目）就緒隊(duì)列中進(jìn)程的數(shù)目 在分時(shí)系統(tǒng)中，就緒隊(duì)列上所有的進(jìn)程數(shù)，是隨著在終端上機(jī)的用戶數(shù)目而改變的，但系統(tǒng)應(yīng)保證，當(dāng)所有終端用戶上機(jī)時(shí)，獲得較好的響應(yīng)時(shí)間。（3）系統(tǒng)的處理能力）系統(tǒng)的處理能力 系統(tǒng)的處理能力是必須保證用戶鍵入的常用命令能在一個(gè)時(shí)間片內(nèi)處理完畢，否則將無法保證得到滿意的響應(yīng)時(shí)間，而且會(huì)使平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間都很長。 Operating SystemOperating SystemPage 452021-10-15進(jìn)程名進(jìn)程名到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服

36、務(wù)時(shí)間 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間平均平均A B C D E A B C D E A B C E A C E C05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到達(dá)時(shí)間若到達(dá)時(shí)間為為0 0、1 1、2 2、3 3、4 4，又如，又如何？何？Operating SystemOperating SystemPage 462021-10-15q優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)v動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)Operating SystemOper

37、ating SystemPage 472021-10-15q優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)運(yùn)行期間創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)運(yùn)行期間保持保持不變不變。 v確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)進(jìn)程類型進(jìn)程類型: :系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于一般用戶進(jìn)程進(jìn)程對資源的需求：進(jìn)程對資源的需求：如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量少的進(jìn)程，應(yīng)賦予較高的優(yōu)先權(quán)。 用戶要求：用戶要求：由用戶進(jìn)程的緊迫程度和用戶所付費(fèi)用的多少來確定優(yōu)先權(quán)。 Operating SystemOperating SystemPage 482021-10-15v動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先

38、權(quán)隨隨進(jìn)程的推進(jìn)進(jìn)程的推進(jìn)或隨其或隨其等待時(shí)間等待時(shí)間的增加而改變，以的增加而改變，以獲得更好的調(diào)度性能獲得更好的調(diào)度性能可規(guī)定，在可規(guī)定，在就緒隊(duì)列中的進(jìn)程就緒隊(duì)列中的進(jìn)程，隨其，隨其等待時(shí)間的等待時(shí)間的增長增長，其優(yōu)先權(quán)，其優(yōu)先權(quán)以速率以速率a提高提高當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)規(guī)定當(dāng)前進(jìn)程前進(jìn)程的優(yōu)先權(quán)的優(yōu)先權(quán)以速率以速率b下降下降，則可防止一個(gè)長，則可防止一個(gè)長作業(yè)長期地作業(yè)長期地壟斷壟斷處理機(jī)處理機(jī)Operating SystemOperating SystemPage 492021-10-15q優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類

39、型v非搶占式非搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法v搶占式搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法Operating SystemOperating SystemPage 502021-10-15q優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型v非搶占式非搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法特點(diǎn)：系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)特點(diǎn)：系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便的進(jìn)程后，該進(jìn)程便一一直執(zhí)行直執(zhí)行下去，直至完成，或因發(fā)生某事下去，直至完成，或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)才將處件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)才將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程理機(jī)重新分配給另一

40、優(yōu)先權(quán)最高的進(jìn)程主要主要用于批處理系統(tǒng)用于批處理系統(tǒng)中，也可用于某些中，也可用于某些對實(shí)時(shí)性對實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中中Operating SystemOperating SystemPage 512021-10-15q優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型v搶占式搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行期間，只要出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則期間，只要出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則進(jìn)程調(diào)度程序就進(jìn)程調(diào)度程序就立即停止立即停止當(dāng)前進(jìn)程的執(zhí)行，并當(dāng)前進(jìn)程的執(zhí)行，并將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程將

41、處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程注意注意：只要只要系統(tǒng)中系統(tǒng)中出現(xiàn)出現(xiàn)一個(gè)新的就緒進(jìn)程，一個(gè)新的就緒進(jìn)程，就就進(jìn)行進(jìn)行優(yōu)先權(quán)優(yōu)先權(quán)比較比較該調(diào)度算法，能更好地該調(diào)度算法，能更好地滿足緊迫作業(yè)滿足緊迫作業(yè)的要求，的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中 Operating SystemOperating SystemPage 522021-10-15q其中，其中，RQRQ為就緒隊(duì)列指針，為就緒隊(duì)列指針，EPEP為運(yùn)行隊(duì)列指針。為運(yùn)行隊(duì)列指針。Operating SystemOperating SystemPage 532021-10-15q 僅有進(jìn)程調(diào)度的調(diào)

42、度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型q 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型q 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型Operating SystemOperating SystemPage 542021-10-15q 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型v在分時(shí)系統(tǒng)中，通常僅設(shè)有進(jìn)程調(diào)度在分時(shí)系統(tǒng)中，通常僅設(shè)有進(jìn)程調(diào)度v系統(tǒng)把這些進(jìn)程組織成一個(gè)系統(tǒng)把這些進(jìn)程組織成一個(gè)就緒隊(duì)列就緒隊(duì)列v每個(gè)進(jìn)程在執(zhí)行時(shí)，可能有以下幾種情況每個(gè)進(jìn)程在執(zhí)行時(shí)，可能有以下幾種情況進(jìn)程獲得進(jìn)程獲得CPUCPU正在執(zhí)行正在執(zhí)行任務(wù)在給定時(shí)間片內(nèi)任務(wù)在給定

43、時(shí)間片內(nèi)已完成已完成，釋放處理機(jī)，釋放處理機(jī)后為完成狀態(tài)后為完成狀態(tài)任務(wù)在時(shí)間片內(nèi)任務(wù)在時(shí)間片內(nèi)未完成未完成，進(jìn)入就緒隊(duì)列末，進(jìn)入就緒隊(duì)列末尾尾在執(zhí)行期間因某事件而阻塞進(jìn)入阻塞隊(duì)列在執(zhí)行期間因某事件而阻塞進(jìn)入阻塞隊(duì)列Operating SystemOperating SystemPage 552021-10-15q僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就就 緒緒隊(duì)隊(duì) 列列阻阻 塞塞隊(duì)隊(duì)列列進(jìn)程調(diào)度進(jìn)程調(diào)度CPU進(jìn)程完成進(jìn)程完成等待事件等待事件交互用戶交互用戶事事件件出出現(xiàn)現(xiàn)時(shí)間片完時(shí)間片完Operating SystemOperating SystemPage 562021-10

44、-15q 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型v在批處理系統(tǒng)中，不僅需要在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度進(jìn)程調(diào)度，而，而且還要有且還要有作業(yè)調(diào)度作業(yè)調(diào)度v就緒隊(duì)列的形式就緒隊(duì)列的形式進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，按優(yōu)先權(quán)高低插進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，按優(yōu)先權(quán)高低插入相應(yīng)位置，調(diào)度程序總是把處理機(jī)分入相應(yīng)位置，調(diào)度程序總是把處理機(jī)分配給就緒隊(duì)首進(jìn)程配給就緒隊(duì)首進(jìn)程v根據(jù)事件的不同設(shè)置多個(gè)阻塞隊(duì)列根據(jù)事件的不同設(shè)置多個(gè)阻塞隊(duì)列Operating SystemOperating SystemPage 572021-10-15進(jìn)程調(diào)度進(jìn)程調(diào)度CPU進(jìn)程完成進(jìn)程完成時(shí)間片完時(shí)間片完就就 緒

45、緒隊(duì)隊(duì)列列12等待事件等待事件等待事件等待事件等待事件等待事件n12n事件事件 出現(xiàn)出現(xiàn)事件事件 出現(xiàn)出現(xiàn)事件事件 出現(xiàn)出現(xiàn)后后備備 隊(duì)隊(duì)列列作業(yè)作業(yè)調(diào)度調(diào)度與上一模型的主要區(qū)別：就緒隊(duì)列的形式；與上一模型的主要區(qū)別：就緒隊(duì)列的形式； 設(shè)置多個(gè)阻塞隊(duì)列設(shè)置多個(gè)阻塞隊(duì)列阻阻隊(duì)隊(duì)列列塞塞2 2阻阻隊(duì)隊(duì)列列塞塞n n阻阻隊(duì)隊(duì)列列塞塞1 1Operating SystemOperating SystemPage 582021-10-15q同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列就緒隊(duì)列進(jìn)程調(diào)度進(jìn)程調(diào)度就緒，掛起隊(duì)列就緒，掛起隊(duì)列中級(jí)調(diào)度中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞，掛起隊(duì)列阻

46、塞隊(duì)列阻塞隊(duì)列等待事件等待事件進(jìn)程完成進(jìn)程完成時(shí)間片完時(shí)間片完作業(yè)調(diào)度作業(yè)調(diào)度交互型作業(yè)交互型作業(yè)后備隊(duì)列后備隊(duì)列批量作業(yè)批量作業(yè)掛起掛起掛起掛起事事件件出出現(xiàn)現(xiàn)事件出現(xiàn)事件出現(xiàn)CPUOperating SystemOperating SystemPage 592021-10-15 多級(jí)隊(duì)列調(diào)度多級(jí)隊(duì)列調(diào)度前臺(tái)前臺(tái)的就緒隊(duì)列是交互性作業(yè)的進(jìn)程，采用時(shí)間片輪轉(zhuǎn)。后臺(tái)后臺(tái)的就緒隊(duì)列是批處理作業(yè)的進(jìn)程，采用優(yōu)先權(quán)或短作業(yè)優(yōu)先算法。調(diào)度方式有兩種：(1) 優(yōu)先調(diào)度前臺(tái)，若前臺(tái)無可運(yùn)行進(jìn)程，才調(diào)度后臺(tái)。(2) 分配占用CPU的時(shí)間比例，如：前臺(tái)80%，后臺(tái)20%。Operating SystemOper

47、ating SystemPage 602021-10-15q多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 v設(shè)置設(shè)置多個(gè)就緒隊(duì)列多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予，并為各個(gè)隊(duì)列賦予不同不同的優(yōu)先級(jí)的優(yōu)先級(jí)第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行行時(shí)間片就愈小時(shí)間片就愈小。例如，。例如，第二個(gè)第二個(gè)隊(duì)列的時(shí)間片隊(duì)列的時(shí)間片要要比第一個(gè)比第一個(gè)隊(duì)列的時(shí)間片隊(duì)列的時(shí)間片長一倍長一倍，第，第i i+1+1個(gè)隊(duì)列的時(shí)間片要比第個(gè)隊(duì)列的時(shí)間片

48、要比第i i個(gè)隊(duì)列的時(shí)間片長個(gè)隊(duì)列的時(shí)間片長一倍一倍Operating SystemOperating SystemPage 612021-10-15就緒隊(duì)列就緒隊(duì)列1 1就緒隊(duì)列就緒隊(duì)列2 2就緒隊(duì)列就緒隊(duì)列3 3就緒隊(duì)列就緒隊(duì)列n nS1S2S3至至CPU至至CPU至至CPU至至CPU( (時(shí)間片：時(shí)間片：S1 S2 S3) )v調(diào)度方式調(diào)度方式高高低低優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片小小大大Sn按按FIFO原則原則排隊(duì)等待調(diào)排隊(duì)等待調(diào)度度尚未完成轉(zhuǎn)入第二尚未完成轉(zhuǎn)入第二隊(duì)列的末尾，按隊(duì)列的末尾，按FIFO原則等待調(diào)原則等待調(diào)度度采取按時(shí)間片輪采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行轉(zhuǎn)的方式運(yùn)行因等待而放棄因等

49、待而放棄CPU后，后，進(jìn)入阻塞隊(duì)列，一旦進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則等待的事件發(fā)生，則回到原來的就緒隊(duì)列回到原來的就緒隊(duì)列Operating SystemOperating SystemPage 622021-10-15v注意注意僅當(dāng)?shù)趦H當(dāng)?shù)?(i-1) 1(i-1) 隊(duì)列均空時(shí)，才會(huì)調(diào)度第隊(duì)列均空時(shí)，才會(huì)調(diào)度第i i隊(duì)隊(duì)列中的進(jìn)程運(yùn)行列中的進(jìn)程運(yùn)行第第i i隊(duì)列隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，又有中某進(jìn)程正在運(yùn)行時(shí)，又有新新進(jìn)程進(jìn)進(jìn)程進(jìn)入入優(yōu)先權(quán)較高優(yōu)先權(quán)較高的隊(duì)列的隊(duì)列( (第第1(i-1)1(i-1)中的任何一中的任何一個(gè)隊(duì)列個(gè)隊(duì)列) )，則此時(shí)，則此時(shí)新進(jìn)程將搶占新進(jìn)程將搶占正在運(yùn)行進(jìn)

50、程正在運(yùn)行進(jìn)程的處理機(jī)，調(diào)度程序把正在運(yùn)行的進(jìn)程的處理機(jī)，調(diào)度程序把正在運(yùn)行的進(jìn)程放回放回到第到第i i隊(duì)列隊(duì)列的末尾的末尾第第i i隊(duì)列隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后，事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后，調(diào)度程序把進(jìn)程調(diào)度程序把進(jìn)程放回到第放回到第i i隊(duì)列隊(duì)列的末尾的末尾Operating SystemOperating SystemPage 632021-10-15q多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法的性能v終端型作業(yè)用戶終端型作業(yè)用戶終端型作業(yè)用戶所提交的作業(yè)多屬于終端型作業(yè)用戶所提交的作業(yè)多屬

51、于交互型交互型作作業(yè)，通常業(yè)，通常較小較小，系統(tǒng)只要能使這些作業(yè)在第一，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成規(guī)定的時(shí)間片內(nèi)完成即可即可v短批處理作業(yè)用戶短批處理作業(yè)用戶若在第若在第1 1隊(duì)列中執(zhí)行隊(duì)列中執(zhí)行一個(gè)時(shí)間片一個(gè)時(shí)間片即可完成，便即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間如在第一個(gè)隊(duì)列中不能完成，只需在第如在第一個(gè)隊(duì)列中不能完成，只需在第2 2、3 3隊(duì)隊(duì)列中各執(zhí)行一個(gè)時(shí)間片列中各執(zhí)行一個(gè)時(shí)間片v長批處理作業(yè)用戶長批處理作業(yè)用戶長作業(yè)將依次在第長作業(yè)將依次在第1 1，2 2，33，n n隊(duì)列中執(zhí)行，隊(duì)列中執(zhí)行，最終按輪轉(zhuǎn)方式運(yùn)行最終

52、按輪轉(zhuǎn)方式運(yùn)行Operating SystemOperating SystemPage 642021-10-15主動(dòng)放棄主動(dòng)放棄CPUCPUq當(dāng)一個(gè)進(jìn)程當(dāng)一個(gè)進(jìn)程運(yùn)行完畢運(yùn)行完畢或由于某種錯(cuò)誤而終止運(yùn)行或由于某種錯(cuò)誤而終止運(yùn)行q當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待等待狀態(tài)（等待狀態(tài)（等待I/OI/O）q在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作（作（P P操作，阻塞原語，喚醒原語）操作，阻塞原語，喚醒原語）被迫放棄被迫放棄CPUCPUq分時(shí)系統(tǒng)中分時(shí)系統(tǒng)中時(shí)間片到時(shí)間片到q當(dāng)有一個(gè)當(dāng)有一個(gè)優(yōu)先級(jí)更高優(yōu)先級(jí)更高的進(jìn)程到（可搶占式）的進(jìn)程到（

53、可搶占式） 例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)阻塞進(jìn)程變成就緒例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)阻塞進(jìn)程變成就緒Operating SystemOperating SystemPage 652021-10-15q只要只要OS取得對取得對CPU的控制，進(jìn)程切換就可能發(fā)的控制，進(jìn)程切換就可能發(fā)生生:v超級(jí)用戶調(diào)用超級(jí)用戶調(diào)用來自程序的顯式請求來自程序的顯式請求 (如：打開文件如：打開文件)，該，該進(jìn)程通常會(huì)被阻塞進(jìn)程通常會(huì)被阻塞v陷阱陷阱最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退出狀態(tài)退出狀態(tài)v中斷中斷 外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至移

54、至IH（中斷處理程序）（中斷處理程序）Operating SystemOperating SystemPage 662021-10-15作業(yè)作業(yè)1234提交時(shí)間提交時(shí)間(時(shí)時(shí))8.08.59.09.5運(yùn)行時(shí)間運(yùn)行時(shí)間(小時(shí)小時(shí))2.00.50.10.2例例1 1 設(shè)某系統(tǒng)的作業(yè)提交時(shí)間和運(yùn)行時(shí)間如下設(shè)某系統(tǒng)的作業(yè)提交時(shí)間和運(yùn)行時(shí)間如下表表, ,請分別計(jì)算采用請分別計(jì)算采用先來先服務(wù)先來先服務(wù)算法和算法和短作業(yè)短作業(yè)優(yōu)先優(yōu)先算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。間。進(jìn)程進(jìn)程A B CDE提交時(shí)間提交時(shí)間 02468運(yùn)行時(shí)間運(yùn)行時(shí)間 36452Operatin

55、g SystemOperating SystemPage 672021-10-15例例2 2 有有5 5個(gè)批處理的作業(yè)（個(gè)批處理的作業(yè)（A A，B B，C C，D D，E E）幾乎同）幾乎同時(shí)到達(dá)一個(gè)計(jì)算中心，估計(jì)的運(yùn)行時(shí)間分別為時(shí)到達(dá)一個(gè)計(jì)算中心，估計(jì)的運(yùn)行時(shí)間分別為2 2，4 4，6 6，8 8，1010分鐘，他們的優(yōu)先級(jí)分別為分鐘，他們的優(yōu)先級(jí)分別為1 1，2 2，3 3，4 4，5 5（1 1為最底）。對下面的每一種調(diào)度算法，為最底）。對下面的每一種調(diào)度算法，分別計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間：分別計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間：1 1、最高優(yōu)先級(jí)優(yōu)先；、最高優(yōu)先級(jí)優(yōu)先；2 2、短作業(yè)優(yōu)先；、短作業(yè)優(yōu)

56、先；Operating SystemOperating SystemPage 682021-10-15q現(xiàn)有現(xiàn)有5 5個(gè)作業(yè)，他們的到達(dá)時(shí)間和運(yùn)行時(shí)間如下表，請用個(gè)作業(yè)，他們的到達(dá)時(shí)間和運(yùn)行時(shí)間如下表，請用FCFSFCFS、SJFSJF算法分別進(jìn)行調(diào)度，計(jì)算平均周轉(zhuǎn)時(shí)間和平均算法分別進(jìn)行調(diào)度，計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)號(hào)作業(yè)號(hào)ABCDE到達(dá)時(shí)間到達(dá)時(shí)間02468運(yùn)行時(shí)間運(yùn)行時(shí)間364522. 在一個(gè)單道批處理系統(tǒng)中，有三個(gè)作業(yè)進(jìn)入系統(tǒng)的時(shí)間和在一個(gè)單道批處理系統(tǒng)中，有三個(gè)作業(yè)進(jìn)入系統(tǒng)的時(shí)間和運(yùn)行的時(shí)間如下，計(jì)算采用響應(yīng)比高者優(yōu)先的調(diào)度算法時(shí)每運(yùn)行的時(shí)間如下，計(jì)算采用

57、響應(yīng)比高者優(yōu)先的調(diào)度算法時(shí)每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間。個(gè)作業(yè)的周轉(zhuǎn)時(shí)間。作業(yè)作業(yè)123進(jìn)入系統(tǒng)時(shí)間進(jìn)入系統(tǒng)時(shí)間9:009:109:15運(yùn)行時(shí)間運(yùn)行時(shí)間60分鐘分鐘45分鐘分鐘25分鐘分鐘Operating SystemOperating SystemPage 692021-10-15q 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q作業(yè)調(diào)度作業(yè)調(diào)度q進(jìn)程調(diào)度進(jìn)程調(diào)度q 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q 預(yù)防死鎖的方法預(yù)防死鎖的方法 q 死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating

58、Systemq實(shí)現(xiàn)實(shí)時(shí)調(diào)度需要提供的信息v任務(wù)變?yōu)榫途w狀態(tài)的時(shí)間v開始截止時(shí)間或完成截止時(shí)間v處理所需時(shí)間v資源要求v優(yōu)先級(jí)：根據(jù)錯(cuò)過截止時(shí)間的后果嚴(yán)重程度設(shè)置Page 702021-10-15Operating SystemOperating SystemPage 712021-10-1571q 按實(shí)時(shí)任務(wù)性質(zhì)分按實(shí)時(shí)任務(wù)性質(zhì)分硬實(shí)時(shí)調(diào)度算法與軟實(shí)時(shí)調(diào)度算法硬實(shí)時(shí)調(diào)度算法與軟實(shí)時(shí)調(diào)度算法 q 按調(diào)度方式分按調(diào)度方式分非搶占式與搶占式調(diào)度算法非搶占式與搶占式調(diào)度算法 Operating SystemOperating SystemPage 722021-10-1572q最早截止時(shí)間優(yōu)先最早截止

59、時(shí)間優(yōu)先EDFEDF（Earliest Deadline FirstEarliest Deadline First）算法）算法q最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLFLLF（Least Laxity FirstLeast Laxity First）算法）算法Operating SystemOperating SystemPage 732021-10-15q最早截止時(shí)間優(yōu)先算法（最早截止時(shí)間優(yōu)先算法（EDF）v截止時(shí)間越早優(yōu)先級(jí)越高截止時(shí)間越早優(yōu)先級(jí)越高vEDF算法可用于搶占式調(diào)度，也可用于非搶占式算法可用于搶占式調(diào)度，也可用于非搶占式調(diào)度。調(diào)度。v非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)非搶占式調(diào)度

60、方式用于非周期實(shí)時(shí)任務(wù)v搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)Operating SystemOperating SystemPage 742021-10-1574t1342134212 34EDFEDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式_ _適用于非周期實(shí)時(shí)任務(wù)適用于非周期實(shí)時(shí)任務(wù)開始截止時(shí)間開始截止時(shí)間任務(wù)執(zhí)行任務(wù)執(zhí)行任務(wù)到達(dá)任務(wù)到達(dá)四個(gè)非周期性任務(wù)：Operating SystemOperating SystemPage 752021-10-1575例：該例中兩個(gè)周期性任務(wù)，任務(wù)例：該例中兩個(gè)周期性任務(wù)，任務(wù)A A的周期時(shí)間是的周期時(shí)間是20ms20ms，