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

1、Operating SystemOperating SystemPage 13/17/2022Operating SystemOperating Systemq重點(diǎn)重點(diǎn)v掌握掌握進(jìn)程調(diào)度進(jìn)程調(diào)度算法，各適用于何種情況算法，各適用于何種情況 v理解常用的幾種理解常用的幾種實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度算法算法 v理解產(chǎn)生理解產(chǎn)生死鎖死鎖的原因的原因 v掌握掌握銀行家算法銀行家算法避免避免死鎖死鎖q難點(diǎn)難點(diǎn)v多道程序設(shè)計(jì)中的各種調(diào)度算法多道程序設(shè)計(jì)中的各種調(diào)度算法 v響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過程響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過程 v銀行家算法銀行家算法 Page 23/17/2022Operating Sys

2、temOperating Systemq知識(shí)點(diǎn)知識(shí)點(diǎn)v處理機(jī)調(diào)度及調(diào)度算法處理機(jī)調(diào)度及調(diào)度算法v多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式v產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件v預(yù)防死鎖的方法，死鎖的檢測(cè)與解除預(yù)防死鎖的方法，死鎖的檢測(cè)與解除 v銀行家算法銀行家算法Page 33/17/2022Operating SystemOperating Systemq處理機(jī)是計(jì)算機(jī)系統(tǒng)中的處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源重要資源q在多道程序環(huán)境下，進(jìn)程數(shù)目通常在多道程序環(huán)境下，進(jìn)程數(shù)目通常多于處多于處理機(jī)的數(shù)目理機(jī)的數(shù)目q系統(tǒng)必須按一定方法系統(tǒng)必須按一定方法動(dòng)態(tài)

3、地動(dòng)態(tài)地把處理機(jī)把處理機(jī)分配分配給給就緒隊(duì)列中的一個(gè)進(jìn)程就緒隊(duì)列中的一個(gè)進(jìn)程q處理機(jī)處理機(jī)利用率和系統(tǒng)性能利用率和系統(tǒng)性能（吞吐量、響應(yīng)（吞吐量、響應(yīng)時(shí)間）在很大程度上時(shí)間）在很大程度上取決于取決于處理機(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：按什么原則分配：按什么原則分配CPU進(jìn)程調(diào)度算法進(jìn)程調(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)程的上下文切換）的上下文切換）Pag

4、e 43/17/2022Operating SystemOperating Systemq 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q 調(diào)度算法調(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 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除Page 53/17/2022Operating SystemOperating Systemq高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q確定算法的原則確定算法的原則q進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型q選擇

5、調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page 63/17/2022Operating SystemOperating Systemq作業(yè)作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過是用戶在一次解題或一個(gè)事務(wù)處理過程中程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合要求計(jì)算機(jī)系統(tǒng)所做工作的集合，包，包括用戶程序、所需的數(shù)據(jù)及命令等括用戶程序、所需的數(shù)據(jù)及命令等q作業(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)歷收容、運(yùn)行、完成三個(gè)束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè)階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)v后備狀態(tài)后備狀態(tài)v運(yùn)行狀

6、態(tài)運(yùn)行狀態(tài)v完成狀態(tài)完成狀態(tài)Page 73/17/2022Operating SystemOperating System運(yùn)行狀態(tài)運(yùn)行狀態(tài)后備狀態(tài)后備狀態(tài)完成狀態(tài)完成狀態(tài)就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O完成完成I/O請(qǐng)求請(qǐng)求時(shí)間片完時(shí)間片完作業(yè)作業(yè)注冊(cè)注冊(cè)作業(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)換Page 83/17/2022Operating SystemOperating System3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3.1.1 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度 1. 高級(jí)調(diào)度高級(jí)調(diào)度(High Scheduling) 2. 低級(jí)調(diào)

7、度低級(jí)調(diào)度(Low Level Scheduling) 3. 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Level Scheduling) Page 93/17/2022Operating SystemOperating Systemq高級(jí)調(diào)度高級(jí)調(diào)度(High Scheduling)(High Scheduling) 作業(yè)調(diào)度作業(yè)調(diào)度或或長程調(diào)度（長程調(diào)度（Long-Term Long-Term SchedulingScheduling）v主要任務(wù)是按一定的原則對(duì)外存上處于后備主要任務(wù)是按一定的原則對(duì)外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配分配內(nèi)內(nèi)

8、存、輸入存、輸入/ /輸出設(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)度（接納調(diào)度（Admission SchedulingAdmission Scheduling）v高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天Page 103/17/2022Operating SystemOperating System在每次作業(yè)調(diào)度時(shí)，須決定：在每次作業(yè)調(diào)度時(shí)，須決定：v接納多少個(gè)作業(yè)接納多少個(gè)作業(yè) 即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存

9、中運(yùn)行，取決于即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多多 道程序度道程序度（Degree of Multiprogramming）作業(yè)太多作業(yè)太多 服務(wù)質(zhì)量下降服務(wù)質(zhì)量下降作業(yè)太少作業(yè)太少 資源利用率低資源利用率低v接納哪些作業(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í)間間隔。：是指在單

10、位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。Page 113/17/2022Operating SystemOperating Systemq 低級(jí)調(diào)度低級(jí)調(diào)度 進(jìn)程調(diào)度進(jìn)程調(diào)度或或短程調(diào)度短程調(diào)度（Short-Term Scheduling）v主要任務(wù)是按照某種主要任務(wù)是按照某種策略和方法策略和方法選取選取一個(gè)處于一個(gè)處于就緒就緒狀態(tài)的進(jìn)程，將處理機(jī)狀態(tài)的進(jìn)程，將處理機(jī)分配分配給它給它v常見的低級(jí)調(diào)度有常見的低級(jí)調(diào)度有非搶占式非搶占式和和搶占式搶占式兩種兩種v低級(jí)調(diào)度的時(shí)間尺度通常是低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)毫秒級(jí)的。的。由于低級(jí)調(diào)度算法的由于低級(jí)調(diào)度算法的頻繁使用

11、頻繁使用，要求，要求在實(shí)現(xiàn)時(shí)做到在實(shí)現(xiàn)時(shí)做到高效高效Page 123/17/2022Operating SystemOperating Systemq 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Level (Intermediate-Level Scheduling)Scheduling) 中程調(diào)度中程調(diào)度(Medium-Term Scheduling)(Medium-Term Scheduling)v引入目的引入目的是為了提高是為了提高內(nèi)存利用率內(nèi)存利用率和和系統(tǒng)吞系統(tǒng)吞吐量。吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上用寶貴的內(nèi)存

12、資源，而將它們調(diào)至外存上去等待去等待v主要任務(wù)主要任務(wù)是按照給定的是按照給定的原則和策略原則和策略，將處，將處于外存于外存對(duì)換區(qū)對(duì)換區(qū)中的重又具備運(yùn)行條件的就中的重又具備運(yùn)行條件的就緒進(jìn)程緒進(jìn)程調(diào)入內(nèi)存調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進(jìn)程或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存交換到外存對(duì)換區(qū)對(duì)換區(qū)Page 133/17/2022Operating SystemOperating Systemq 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型q 選擇調(diào)度方

13、式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page 143/17/2022Operating SystemOperating Systemq 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù) 是是控制、協(xié)調(diào)進(jìn)程控制、協(xié)調(diào)進(jìn)程對(duì)對(duì)CPUCPU的競爭的競爭, ,即按一定的調(diào)度算法從就緒隊(duì)列中選即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把中一個(gè)進(jìn)程，把CPUCPU的使用權(quán)交給被選的使用權(quán)交給被選中的進(jìn)程中的進(jìn)程Page 153/17/2022Operating SystemOperating Systemq 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法

14、的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page 163/17/2022Operating SystemOperating Systemq 具有具有公平性公平性q 資源資源利用率高利用率高（特別是（特別是CPUCPU利用率）利用率）q 在交互式系統(tǒng)情況下要追求在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間響應(yīng)時(shí)間（越短越好）（越短越好）q 在批處理系統(tǒng)情況下要追求系統(tǒng)在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量吞吐量Page 173/17/2022Operating SystemOperating Systemq 高級(jí)、中級(jí)和低

15、級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page 183/17/2022Operating SystemOperating Systemq 非搶占方式非搶占方式(Non-preemptive Mode)(Non-preemptive Mode)q 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)Page 193/17/2022Operating SystemOperating Syste

16、mq 非搶占方式非搶占方式(Non-preemptive Mode)(Non-preemptive Mode) 當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，該進(jìn)程仍繼為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，該進(jìn)程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進(jìn)入完成續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進(jìn)入完成或阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊或阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程迫的進(jìn)程v引起進(jìn)程調(diào)度的因素引起進(jìn)程調(diào)度的因素正在執(zhí)行的進(jìn)程執(zhí)行完畢，正在執(zhí)行的進(jìn)程執(zhí)行完畢， 或因發(fā)生某事或因發(fā)生某事件而不能再繼續(xù)執(zhí)行件而不

17、能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出執(zhí)行中的進(jìn)程因提出I/OI/O請(qǐng)求而暫停執(zhí)行；請(qǐng)求而暫停執(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á)要等待長進(jìn)程運(yùn)行結(jié)束程運(yùn)行結(jié)束Page 203/17/2022Operating SystemOperating Systemq 搶占方式搶占方式(Preemptive Mode)(Preemptive Mod

18、e) 當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程為重要或緊迫的進(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)程的處理機(jī)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī) 時(shí)間片原則時(shí)間片原則 時(shí)間片用

19、完后停止執(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)開銷大Page 213/17/2022Operating SystemOperating Systemq 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page 223/17/2022Operating S

20、ystemOperating Systemq 僅有進(jìn)程調(diào)度的調(diào)度隊(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ì)列模型Page 233/17/2022Operating SystemOperating Systemq 僅有進(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)程

21、獲得CPUCPU正在執(zhí)行正在執(zhí)行任務(wù)在給定時(shí)間片內(nèi)任務(wù)在給定時(shí)間片內(nèi)已完成已完成，釋放處理，釋放處理機(jī)后為完成狀態(tài)機(jī)后為完成狀態(tài)任務(wù)在時(shí)間片內(nèi)任務(wù)在時(shí)間片內(nèi)未完成未完成，進(jìn)入就緒隊(duì)列，進(jìn)入就緒隊(duì)列末尾末尾在執(zhí)行期間因某事件而阻塞在執(zhí)行期間因某事件而阻塞Page 243/17/2022Operating SystemOperating Systemq僅有進(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í)間片完P(guān)age 253/17/2022Operating Sys

22、temOperating Systemq 具有高級(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ì)列的形式在批處理系統(tǒng)中，常用高優(yōu)先權(quán)隊(duì)列。在批處理系統(tǒng)中，常用高優(yōu)先權(quán)隊(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設(shè)置多個(gè)阻塞隊(duì)列設(shè)置多個(gè)阻塞隊(duì)列根據(jù)事件的不同設(shè)置多個(gè)隊(duì)列提高效率根據(jù)事件的不同設(shè)置多個(gè)隊(duì)列提高效率Page 263/1

23、7/2022Operating SystemOperating System進(jìn)程調(diào)度進(jìn)程調(diào)度CPU進(jìn)程完成進(jìn)程完成時(shí)間片完時(shí)間片完就就 緒緒隊(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 1Page 273/17/2022Operating SystemOperating Systemq同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型

24、同時(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ì)列阻塞隊(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)CPUPage 283/17/2022Operating SystemOperating Systemq 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型q選擇調(diào)度方式和調(diào)度

25、算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？Page 293/17/2022Operating SystemOperating System3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1. 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 2. 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 Page 303/17/2022Operating SystemOperating System3.1.3 選擇調(diào)度

26、方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1. 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時(shí)間短。周轉(zhuǎn)時(shí)間短。 (2) 響應(yīng)時(shí)間快。響應(yīng)時(shí)間快。 (3) 截止時(shí)間的保證。截止時(shí)間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)則。優(yōu)先權(quán)準(zhǔn)則。 Page 313/17/2022Operating SystemOperating Systemq 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短平均周轉(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與系統(tǒng)為它與系統(tǒng)為它提供服務(wù)的時(shí)間提供服務(wù)的時(shí)間T TS S之比，即

27、之比，即W=T/TW=T/TS S 。而。而平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為則可表示為: : Page 323/17/2022Operating SystemOperating Systemq面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v響應(yīng)時(shí)間快響應(yīng)時(shí)間快響應(yīng)時(shí)間響應(yīng)時(shí)間是指從用戶通過鍵盤提交一個(gè)請(qǐng)求是指從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)中開始，直至系統(tǒng)中首次首次產(chǎn)生產(chǎn)生響應(yīng)響應(yīng)為止的時(shí)間為止的時(shí)間交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳v截止時(shí)間保證截止時(shí)間保證截止時(shí)間截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間間或必須

28、完成的最遲時(shí)間截止時(shí)間是截止時(shí)間是實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)中的重要指標(biāo)中的重要指標(biāo)Page 333/17/2022Operating SystemOperating Systemq面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則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)等待時(shí)間短等待時(shí)間短優(yōu)先權(quán)優(yōu)先權(quán)Page 343/17/2022Operating SystemOperating Systemq面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v等待時(shí)間短等待時(shí)間短等待時(shí)間等待時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間調(diào)度算法并不影響進(jìn)程

29、運(yùn)行和執(zhí)行調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時(shí)的時(shí)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)的時(shí)間的時(shí)間v優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則在在批處理批處理、實(shí)時(shí)實(shí)時(shí)和和分時(shí)系統(tǒng)分時(shí)系統(tǒng)中都可以選擇優(yōu)中都可以選擇優(yōu)先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理有時(shí)還選擇搶占式調(diào)度方式有時(shí)還選擇搶占式調(diào)度方式Page 353/17/2022Operating SystemOperating Systemq面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則v系統(tǒng)吞吐量高系統(tǒng)吞吐量高吞吐量吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對(duì)吞吐量的

30、大小有較作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較大影響大影響v處理機(jī)利用率高處理機(jī)利用率高v各類資源的平衡利用各類資源的平衡利用使內(nèi)存、外存和使內(nèi)存、外存和I/OI/O設(shè)備的利用率高設(shè)備的利用率高基于這樣的準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？基于這樣的準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？Page 363/17/2022Operating SystemOperating Systemq處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(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死

31、鎖的檢測(cè)與解除死鎖的檢測(cè)與解除Page 373/17/2022Operating SystemOperating Systemq在在OS中中調(diào)度的實(shí)質(zhì)是一種資源分配調(diào)度的實(shí)質(zhì)是一種資源分配，因而，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法所規(guī)定的資源分配算法q問題提出問題提出q如何制定分配策略：對(duì)不同的系統(tǒng)和系統(tǒng)如何制定分配策略：對(duì)不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)先，時(shí)間片輪轉(zhuǎn)等先，時(shí)間片輪轉(zhuǎn)等q有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn)有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn)程調(diào)度，有些兩者皆

32、可程調(diào)度，有些兩者皆可Page 383/17/2022Operating SystemOperating Systemq 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法q 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法q 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page 393/17/2022Operating SystemOperating Systemq 先來先服務(wù)先來先服務(wù)(FCFS)/先進(jìn)先出先進(jìn)先出(FIFO)調(diào)度算法調(diào)度算法v按照作業(yè)按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的進(jìn)程進(jìn)入系統(tǒng)的先后次序先后次序進(jìn)行調(diào)度，進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待

33、時(shí)間最長的作業(yè)的作業(yè)/進(jìn)程進(jìn)程v是一種最簡單的調(diào)度算法，即可用于是一種最簡單的調(diào)度算法，即可用于作業(yè)調(diào)作業(yè)調(diào)度度，也可用于，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度q 幾個(gè)術(shù)語幾個(gè)術(shù)語v到達(dá)時(shí)間、服務(wù)時(shí)間、開始時(shí)間到達(dá)時(shí)間、服務(wù)時(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í)間Page 403/17/2022Operating SystemOperating System進(jìn)程名進(jìn)程名到達(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)

34、時(shí)間平均平均04A13B25C32D44E044476先來先服務(wù)（先進(jìn)先出）：先來先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518tPage 413/17/2022Operating SystemOperating Systemq 先來先服務(wù)先來先服務(wù)（先進(jìn)先出）（先進(jìn)先出）優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)v 比較有利于比較有利于長作業(yè)（進(jìn)程）長作業(yè)（進(jìn)程），而不利于，而不利于短作業(yè)短作業(yè)（進(jìn)程）（進(jìn)程）v 有利于有利于CPU繁忙型作業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程） ，而不利于，而不利于I/O繁忙型作

35、業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程）v 用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)Page 423/17/2022Operating SystemOperating Systemq短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)Fv短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)F，以要求，以要求運(yùn)運(yùn)行時(shí)間長短行時(shí)間長短進(jìn)行調(diào)度，即啟動(dòng)要求運(yùn)行時(shí)間最進(jìn)行調(diào)度，即啟動(dòng)要求運(yùn)行時(shí)間最短的作業(yè)短的作業(yè)v可以分別用于可以分別用于作業(yè)調(diào)度作業(yè)調(diào)度和和進(jìn)程調(diào)度進(jìn)程調(diào)度v短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)(SJF)的調(diào)度算法，是從后備隊(duì)列的調(diào)

36、度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間估計(jì)運(yùn)行時(shí)間最短的作業(yè)，最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行；而短進(jìn)程優(yōu)先將它們調(diào)入內(nèi)存運(yùn)行；而短進(jìn)程優(yōu)先(SPF)(SPF)調(diào)調(diào)度算法，則是從就緒隊(duì)列中選出一度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)估計(jì)運(yùn)行時(shí)間間最短的進(jìn)程，將處理機(jī)分配給它，使它立即最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成執(zhí)行并一直執(zhí)行到完成，或，或發(fā)生某事件發(fā)生某事件而被阻而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度塞放棄處理機(jī)時(shí)，再重新調(diào)度Page 433/17/2022Operating SystemOperating System進(jìn)程名進(jìn)程名到達(dá)時(shí)間

37、到達(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è)/短進(jìn)程優(yōu)先（短進(jìn)程優(yōu)先（SJF/SPF）：）：4633/26988/391399/413181616/540/52.1A A A AB B BC C C C CD DE E E E05101518tPage 443/17/2022Operating SystemOperating SystemqFCFS/SJF調(diào)度算法的性能調(diào)度算法的性能SJFSJF能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量能有效地降低作業(yè)的平均等待時(shí)間，提高系

38、統(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.8SJF完成時(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í)間明顯改善顯改善Page 453/17/2022Operating SystemOperating SystemqSJ(P)F調(diào)度算法也存在不容忽視的缺

39、點(diǎn)調(diào)度算法也存在不容忽視的缺點(diǎn)v對(duì)對(duì)長作業(yè)不利長作業(yè)不利。嚴(yán)重的是，若一長作業(yè)。嚴(yán)重的是，若一長作業(yè)(進(jìn)程進(jìn)程)進(jìn)進(jìn)入系統(tǒng)的后備隊(duì)列入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列就緒隊(duì)列)，由于調(diào)度程序總，由于調(diào)度程序總是優(yōu)先調(diào)度那些是優(yōu)先調(diào)度那些(即使是后進(jìn)來的即使是后進(jìn)來的)短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)，將導(dǎo)致長作業(yè)將導(dǎo)致長作業(yè)(進(jìn)程進(jìn)程)長期不被調(diào)度長期不被調(diào)度饑餓饑餓v完全未考慮作業(yè)完全未考慮作業(yè)(進(jìn)程進(jìn)程)的的緊迫程度緊迫程度，因而不能保，因而不能保證證緊迫性緊迫性作業(yè)作業(yè)(進(jìn)程進(jìn)程)會(huì)被會(huì)被及時(shí)處理及時(shí)處理v由于作業(yè)由于作業(yè)(進(jìn)程進(jìn)程)的長短只是根據(jù)的長短只是根據(jù)用戶用戶所提供的所提供的估估計(jì)執(zhí)行時(shí)間計(jì)執(zhí)

40、行時(shí)間而定的，而用戶又可能會(huì)而定的，而用戶又可能會(huì)有意或無意有意或無意地地縮短縮短其作業(yè)的估計(jì)其作業(yè)的估計(jì)運(yùn)行時(shí)間運(yùn)行時(shí)間，致使該算法不一，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。定能真正做到短作業(yè)優(yōu)先調(diào)度。Page 463/17/2022Operating SystemOperating Systemq先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法q高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法q基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page 473/17/2022Operating SystemOperating Systemq優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型v非搶占式

41、非搶占式優(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)度算法Page 483/17/2022Operating SystemOperating Systemq優(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ī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)

42、程主要主要用于批處理系統(tǒng)用于批處理系統(tǒng)中，也可用于某些中，也可用于某些對(duì)實(shí)時(shí)性對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中中Page 493/17/2022Operating SystemOperating Systemq優(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)程將處理機(jī)分配給新到

43、的優(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)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中Page 503/17/2022Operating SystemOperating Systemq優(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)Page 513/17/2022Operating SystemOperating

44、 Systemq優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)運(yùn)行期間運(yùn)行期間保持不變保持不變。一般地，優(yōu)先權(quán)是利用某一。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0 0 7 7或或0 0 255255， 又把該整數(shù)稱為又把該整數(shù)稱為優(yōu)先數(shù)優(yōu)先數(shù)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)程，用戶進(jìn)程系統(tǒng)進(jìn)程，用戶進(jìn)程進(jìn)程對(duì)資源的需求進(jìn)程對(duì)資源的需求用戶要求用戶要求Page 523/17/2022Operating SystemOp

45、erating System確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：進(jìn)程類型。進(jìn)程類型。系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于一般用戶進(jìn)程。 (2) 進(jìn)程對(duì)資源的需求。進(jìn)程對(duì)資源的需求。如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量少的進(jìn)程，應(yīng)賦予較高的優(yōu)先權(quán)。 (3) 用戶要求。用戶要求。由用戶進(jìn)程的緊迫程度和用戶所付費(fèi)用的多少來確定優(yōu)先權(quán)。 Page 533/17/2022Operating SystemOperating Systemq優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)運(yùn)行期間運(yùn)行期間保持不變保持不變。一般地，優(yōu)先權(quán)是利用某一。

46、一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0 0 7 7或或0 0 255255， 又把該整數(shù)稱為又把該整數(shù)稱為優(yōu)先數(shù)優(yōu)先數(shù)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)程，用戶進(jìn)程系統(tǒng)進(jìn)程，用戶進(jìn)程進(jìn)程對(duì)資源的需求進(jìn)程對(duì)資源的需求用戶要求用戶要求v靜態(tài)優(yōu)先權(quán)特點(diǎn)靜態(tài)優(yōu)先權(quán)特點(diǎn)系統(tǒng)開銷小、不夠精確、一般用在要求不高的系系統(tǒng)開銷小、不夠精確、一般用在要求不高的系統(tǒng)中統(tǒng)中問題：用戶將優(yōu)先權(quán)設(shè)的較高，對(duì)其他進(jìn)程不利！問題：用戶將優(yōu)先權(quán)設(shè)的較高，對(duì)其他進(jìn)程不利！ 短進(jìn)程優(yōu)先對(duì)長進(jìn)程不利！短進(jìn)程優(yōu)先對(duì)長進(jìn)程不利！Page 54

47、3/17/2022Operating SystemOperating Systemv動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(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提高提高具有具有相同相同優(yōu)先權(quán)優(yōu)先權(quán)初值初值的進(jìn)程，則的進(jìn)程，則最先進(jìn)入最先進(jìn)入就緒就緒隊(duì)列，其將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而隊(duì)列，其將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲優(yōu)先獲得得處理機(jī)，此即處理機(jī)，此即FCFS算法算法具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則

48、具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則優(yōu)優(yōu)先權(quán)初值低先權(quán)初值低的進(jìn)程，在的進(jìn)程，在等待了足夠的時(shí)間等待了足夠的時(shí)間后，后，其其優(yōu)先權(quán)便可能升為最高優(yōu)先權(quán)便可能升為最高，從而可以獲得處理，從而可以獲得處理機(jī)機(jī)當(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è)長作業(yè)，則可防止一個(gè)長作業(yè)長期地長期地壟斷壟斷處理機(jī)處理機(jī)Page 553/17/2022Operating SystemOperating System進(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í)間

49、時(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)）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下考慮一下?lián)屨际綋屨际剑闆r如何？，情況如何？Page 563/17/2022Operating SystemOperating Systemq高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（HRF）v是是FCFS和和SJF的結(jié)合，克服了兩種算法的的結(jié)合，克服了兩種算法的缺點(diǎn)缺點(diǎn)v調(diào)度策略調(diào)度策略：響應(yīng)比：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)最高的作業(yè)優(yōu)先啟動(dòng)

50、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)比響應(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)先先= = =要要求求服服要要求求服服Page 573/17/2022Operating SystemOperating Systemq 對(duì)對(duì)HRF的小結(jié)的小結(jié)v等待時(shí)間相同等待時(shí)間相同的作業(yè)，則的作業(yè)，則要求服務(wù)的時(shí)間愈要求服務(wù)的時(shí)間愈短短，其，其優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高，v要求服務(wù)

51、的時(shí)間相同要求服務(wù)的時(shí)間相同的作業(yè)，則的作業(yè)，則等待時(shí)間愈等待時(shí)間愈長長，其，其優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高，v長作業(yè)，優(yōu)先權(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è)長期得業(yè)到達(dá)的先后次序，又不會(huì)使長作業(yè)長期得不到服務(wù)。不到服務(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í)間等等待待+ +

52、要要求求服服優(yōu)優(yōu)先先= = =要要求求服服要要求求服服對(duì)短作業(yè)有利對(duì)短作業(yè)有利是先來先服務(wù)是先來先服務(wù)對(duì)長作業(yè)有利對(duì)長作業(yè)有利Page 583/17/2022Operating SystemOperating Systemq先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法q高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法q基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page 593/17/2022Operating SystemOperating Systemq 簡單的時(shí)間片輪轉(zhuǎn)法簡單的時(shí)間片輪轉(zhuǎn)法(RRRound Robin)v系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排系統(tǒng)將所有的就緒進(jìn)程按先

53、來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片v當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)時(shí)鐘中斷鐘中斷請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行，請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首給就緒隊(duì)列中新的隊(duì)首v時(shí)間片的大小從幾時(shí)間片的大小從幾ms到幾百到幾百ms優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理

54、機(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)Page 603/17/2022Operating SystemOperating System進(jìn)程名進(jìn)程名到達(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í)間平均平均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í)間

55、若到達(dá)時(shí)間為為0 0、1 1、2 2、3 3、4 4，又如，又如何？何？Page 613/17/2022Operating SystemOperating Systemv分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇時(shí)間片選擇問題問題固定時(shí)間片固定時(shí)間片可變時(shí)間片可變時(shí)間片時(shí)間片大小時(shí)間片大小與與時(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能力能力 Page 623/17/2022Operating SystemOperating System3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 2. 時(shí)間片大小的

56、確定時(shí)間片大小的確定（1）系統(tǒng)對(duì)響應(yīng)時(shí)間的要求）系統(tǒng)對(duì)響應(yīng)時(shí)間的要求 數(shù)目N和時(shí)間片q成反比，即T=Nq，因此在進(jìn)程數(shù)一定時(shí)，作為分時(shí)系統(tǒng)首先就是必須滿足系統(tǒng)對(duì)響應(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í)間都很長。 Page 633/

57、17/2022Operating SystemOperating System2. 多級(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%。3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 Page 643/17/2022Operating SystemOperating Systemq多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 v設(shè)置設(shè)置多個(gè)就緒隊(duì)列多個(gè)就緒隊(duì)列，并

58、為各個(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è)降低該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的時(shí)間片的大小也各不相同大小也各不相同，在，在優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高的隊(duì)列中，的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小時(shí)間片就愈小。例如，例如，第二個(gè)第二個(gè)隊(duì)列的時(shí)間片要隊(duì)列的時(shí)間片要比第一個(gè)比第一個(gè)隊(duì)隊(duì)列的時(shí)間片列的時(shí)間片長一倍長一倍，第，第i i+1+1個(gè)隊(duì)列的時(shí)個(gè)隊(duì)列的時(shí)間片要比第間片要比第i i個(gè)隊(duì)列的時(shí)間片長一倍個(gè)

59、隊(duì)列的時(shí)間片長一倍Page 653/17/2022Operating SystemOperating System就緒隊(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)行因等待而放棄因等待而放棄CPU后，后，進(jìn)入阻塞隊(duì)列，一旦進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則等待的事件發(fā)生，則回到原來的就緒隊(duì)列回到原來的就緒隊(duì)列Page 663/17/2022Operating SystemOperating Systemv注意注意僅當(dāng)?shù)趦H當(dāng)?shù)?(i-1) 隊(duì)列均空時(shí)，才會(huì)調(diào)度第隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列隊(duì)列中的進(jìn)程運(yùn)行中的進(jìn)程運(yùn)行第第i隊(duì)列隊(duì)列