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

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

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

4、進程調度進程調度q 實時調度實時調度 q 多處理機系統(tǒng)中的調度多處理機系統(tǒng)中的調度q 產生死鎖的原因和必要條件產生死鎖的原因和必要條件 q 預防死鎖的方法預防死鎖的方法 q 死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 62021-10-15q高級、中級和低級調度高級、中級和低級調度q處理機調度算法的目標處理機調度算法的目標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)：一個作業(yè)進入系統(tǒng)到運行結束，一個作業(yè)進入系統(tǒng)到運行結束，一般需要經歷一般需要經歷收容、運行、完成收容、運行、完成三個階段，與三個階段，與之相對應的是作業(yè)的三種狀態(tài)之相對應的是作業(yè)的三種狀態(tài)后備后備狀態(tài)狀態(tài)運行運行狀態(tài)狀態(tài)完成完成狀態(tài)狀態(tài)Operating SystemOperating SystemPage 82021-10-15運行狀態(tài)運行狀態(tài)后備狀態(tài)后備狀態(tài)完成狀態(tài)完成狀態(tài)就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O完成完成I/O請求請求時間片完時間片完作業(yè)作業(yè)注冊注冊作業(yè)作業(yè)調度調度進程進程調度調度終止終止作業(yè)作業(yè)q作業(yè)作業(yè)狀態(tài)間轉換狀態(tài)間轉換內存內存外存

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

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

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

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

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

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

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

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

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

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

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

17、，也可用于，也可用于進程調度進程調度q 幾個術語幾個術語v到達時間、開始時間到達時間、開始時間v完成時間、等待時間完成時間、等待時間v周轉時間：完成時間周轉時間：完成時間-到達時間到達時間v帶權周轉時間：周轉時間帶權周轉時間：周轉時間/服務時間服務時間Operating SystemOperating SystemPage 242021-10-15作業(yè)名作業(yè)名到達時間到達時間 服務時間服務時間 開始時間開始時間 完成時間完成時間 周轉時間周轉時間帶權周帶權周轉時間轉時間平均平均04A13B25C32D44E044476先來先服務（先進先出）：先來先服務（先進先出）：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 先來先服務先來先服務（先進先出）（先進先出）優(yōu)缺點優(yōu)缺點v 比較有利于比較有利于長作業(yè)長作業(yè) ，而不利于，而不利于短作業(yè)短作業(yè) v 有利于有利于CPU繁忙型作業(yè)（進程）繁忙型作業(yè)（進程） ，而不利于，而不利于I/O繁忙型作業(yè)（進程）繁忙型作業(yè)（進程）Operating SystemOperating SystemPage 262021-10-15q短作業(yè)優(yōu)先調度算法短作業(yè)優(yōu)先

19、調度算法SJFSJFv短作業(yè)短作業(yè) 優(yōu)先調度算法優(yōu)先調度算法SJ FSJ F，以要求，以要求運行時間運行時間長短長短進行調度，即啟動估計運行時間最短的作進行調度，即啟動估計運行時間最短的作業(yè)業(yè)v可以分別用于可以分別用于作業(yè)調度作業(yè)調度和和進程調度進程調度Operating SystemOperating SystemPage 272021-10-15作業(yè)名作業(yè)名到達時間到達時間 服務時間服務時間 開始時間開始時間 完成時間完成時間 周轉時間周轉時間帶權周帶權周轉時間轉時間平均平均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調度算法的性能調度算法的性能SJFSJF能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量 作業(yè)作業(yè)調度調度 情況情況 算法算法進程名進程名ABCDE平均平均到達時間到達時間01234服務時間服務時間43524FCFS完成時間完成時間47121418周轉時間周轉時間461011149帶權周轉時間帶權周轉時間1225.53.52.8SJ

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

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

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

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

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

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

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

28、 q預防死鎖的方法預防死鎖的方法 q死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 372021-10-15q 進程調度的任務進程調度的任務 保存保存當前進程的處理機信息，按一定當前進程的處理機信息，按一定的調度算法從就緒隊列中的調度算法從就緒隊列中選中選中一個進程，一個進程，將其狀態(tài)改為運行狀態(tài)，將選中進行的處將其狀態(tài)改為運行狀態(tài)，將選中進行的處理機信息理機信息恢復恢復到處理機中，把到處理機中，把CPUCPU的使用權的使用權交給被選中的進程。交給被選中的進程。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í)行的進程，上執(zhí)行的進程，需要等到其完成需要等到其完成或發(fā)生某種事件而進入阻塞狀態(tài)時，才把處理機或發(fā)生某種事件而進入阻塞狀態(tài)時，才把處理機分

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

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

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

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

34、e 432021-10-15v分時系統(tǒng)中常用時間片輪轉法分時系統(tǒng)中常用時間片輪轉法時間片選擇時間片選擇問題問題固定時間片固定時間片可變時間片可變時間片時間片大小：太小頻繁切換，太大變?yōu)橄葋硐葧r間片大小：太小頻繁切換，太大變?yōu)橄葋硐确辗张c與時間片大小時間片大小有關的因素有關的因素系統(tǒng)響應時間系統(tǒng)響應時間就緒進程個數(shù)就緒進程個數(shù)CPUCPU能力能力 Operating SystemOperating SystemPage 442021-10-15基于時間片的輪轉調度算法基于時間片的輪轉調度算法 （1）系統(tǒng)對響應時間的要求）系統(tǒng)對響應時間的要求 數(shù)目N和時間片q成反比，即T=Nq，因此在進程數(shù)一

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

36、務時間 開始時間開始時間 完成時間完成時間 周轉時間周轉時間帶權周帶權周轉時間轉時間平均平均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若到達時間若到達時間為為0 0、1 1、2 2、3 3、4 4，又如，又如何？何？Operating SystemOperating SystemPage 462021-10-15q優(yōu)先權的類型優(yōu)先權的類型v靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權v動態(tài)優(yōu)先權動態(tài)優(yōu)先權Operating SystemOper

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

59、時間優(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最早截止時間優(yōu)先算法（最早截止時間優(yōu)先算法（EDF）v截止時間越早優(yōu)先級越高截止時間越早優(yōu)先級越高vEDF算法可用于搶占式調度，也可用于非搶占式算法可用于搶占式調度，也可用于非搶占式調度。調度。v非搶占式調度方式用于非周期實時任務非搶占式調度

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