操作系統(tǒng)第3章處理機調(diào)度與死鎖(1)

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

2、temOperating SystemPage 32022-3-17q知識點知識點v處理機調(diào)度及調(diào)度算法處理機調(diào)度及調(diào)度算法v多處理機環(huán)境下的進程（線程）調(diào)度方式多處理機環(huán)境下的進程（線程）調(diào)度方式v產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件v預(yù)防死鎖的方法，死鎖的檢測與解除預(yù)防死鎖的方法，死鎖的檢測與解除 v銀行家算法銀行家算法Operating SystemOperating SystemPage 42022-3-17q處理機是計算機系統(tǒng)中的處理機是計算機系統(tǒng)中的重要資源重要資源q在多道程序環(huán)境下，進程數(shù)目通常在多道程序環(huán)境下，進程數(shù)目通常多于處多于處理機的數(shù)目理機的數(shù)目q系統(tǒng)必須按

3、一定方法系統(tǒng)必須按一定方法動態(tài)地動態(tài)地把處理機把處理機分配分配給給就緒隊列中的一個進程就緒隊列中的一個進程q處理機處理機利用率和系統(tǒng)性能利用率和系統(tǒng)性能（吞吐量、響應(yīng)（吞吐量、響應(yīng)時間）在很大程度上時間）在很大程度上取決于取決于處理機處理機調(diào)度調(diào)度分配處理機的任務(wù)是由進程調(diào)度程序完成分配處理機的任務(wù)是由進程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計的中心問題之一。的。它是操作系統(tǒng)設(shè)計的中心問題之一。WHAT：按什么原則分配：按什么原則分配CPU進程調(diào)度算法進程調(diào)度算法WHEN：何時分配：何時分配CPU 進程調(diào)度的時機進程調(diào)度的時機 HOW：如何分配：如何分配CPU CPU調(diào)度過程（進程調(diào)度過程（進程的上

4、下文切換）的上下文切換）Operating SystemOperating SystemPage 52022-3-17q 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 q 調(diào)度算法調(diào)度算法 q 實時調(diào)度實時調(diào)度 q 多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度q 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q 預(yù)防死鎖的方法預(yù)防死鎖的方法 q 死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 62022-3-17q高級、中級和低級調(diào)度高級、中級和低級調(diào)度q進程調(diào)度的任務(wù)進程調(diào)度的任務(wù)q確定算法的原則確定算法的原則q進程調(diào)度方式進程調(diào)度方式q

5、調(diào)度隊列模型調(diào)度隊列模型q選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Operating SystemOperating SystemPage 72022-3-17q作業(yè)作業(yè)是用戶在一次解題或一個事務(wù)處理過是用戶在一次解題或一個事務(wù)處理過程中程中要求計算機系統(tǒng)所做工作的集合要求計算機系統(tǒng)所做工作的集合，包，包括用戶程序、所需的數(shù)據(jù)及命令等括用戶程序、所需的數(shù)據(jù)及命令等q作業(yè)的狀態(tài)：作業(yè)的狀態(tài)：一個作業(yè)進入系統(tǒng)到運行結(jié)一個作業(yè)進入系統(tǒng)到運行結(jié)束，一般需要經(jīng)歷收容、運行、完成三個束，一般需要經(jīng)歷收容、運行、完成三個階段，與之相對應(yīng)的是作業(yè)的三種狀態(tài)階段，與之相對應(yīng)的是作業(yè)的三種

6、狀態(tài)v后備狀態(tài)后備狀態(tài)v運行狀態(tài)運行狀態(tài)v完成狀態(tài)完成狀態(tài)Operating SystemOperating SystemPage 82022-3-17運行狀態(tài)運行狀態(tài)后備狀態(tài)后備狀態(tài)完成狀態(tài)完成狀態(tài)就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O完成完成I/O請求請求時間片完時間片完作業(yè)作業(yè)注冊注冊作業(yè)作業(yè)調(diào)度調(diào)度進程進程調(diào)度調(diào)度終止終止作業(yè)作業(yè)q作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換狀態(tài)間轉(zhuǎn)換Operating SystemOperating SystemPage 92022-3-173.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 3.1.1 高級、中級和低級調(diào)度高級、中級和低級調(diào)度 1. 高級調(diào)度高級調(diào)度(High Sch

7、eduling) 2. 低級調(diào)度低級調(diào)度(Low Level Scheduling) 3. 中級調(diào)度中級調(diào)度(Intermediate-Level Scheduling) Operating SystemOperating SystemPage 102022-3-17q高級調(diào)度高級調(diào)度(High Scheduling)(High Scheduling) 作業(yè)調(diào)度作業(yè)調(diào)度或或長程調(diào)度（長程調(diào)度（Long-Term Long-Term SchedulingScheduling）v主要任務(wù)是按一定的原則對外存上處于后備主要任務(wù)是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)狀態(tài)的作業(yè)進

8、行選擇，給選中的作業(yè)分配分配內(nèi)內(nèi)存、輸入存、輸入/ /輸出設(shè)備等輸出設(shè)備等必要的資源必要的資源，并，并建立建立相相應(yīng)的應(yīng)的進程進程，放入放入就緒就緒隊列隊列，以使該作業(yè)的進，以使該作業(yè)的進程獲得競爭處理機的權(quán)利程獲得競爭處理機的權(quán)利v也稱為也稱為接納調(diào)度（接納調(diào)度（Admission SchedulingAdmission Scheduling）v高級調(diào)度的時間尺度通常是分鐘、小時或天高級調(diào)度的時間尺度通常是分鐘、小時或天Operating SystemOperating SystemPage 112022-3-17在每次作業(yè)調(diào)度時，須決定：在每次作業(yè)調(diào)度時，須決定：v接納多少個作業(yè)接納多少個

9、作業(yè) 即允許多少個作業(yè)同時在內(nèi)存中運行，取決于即允許多少個作業(yè)同時在內(nèi)存中運行，取決于多多 道程序度道程序度（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)時間太長系統(tǒng)吞吐量太低 適當(dāng)?shù)恼壑裕杭丛试S多少個作業(yè)同時在內(nèi)存中運行。：即允許多少個作業(yè)同時在內(nèi)存中運行。：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間

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

11、算法的由于低級調(diào)度算法的頻繁使用頻繁使用，要求，要求在實現(xiàn)時做到在實現(xiàn)時做到高效高效Operating SystemOperating SystemPage 132022-3-17q 中級調(diào)度中級調(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)吞吐量。吐量。使那些暫時不能運行的進程不再占使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源

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

13、列模型調(diào)度隊列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Operating SystemOperating SystemPage 152022-3-17q 進程調(diào)度的任務(wù)進程調(diào)度的任務(wù) 是是控制、協(xié)調(diào)進程控制、協(xié)調(diào)進程對對CPUCPU的競爭的競爭, ,即按一定的調(diào)度算法從就緒隊列中選即按一定的調(diào)度算法從就緒隊列中選中一個進程，把中一個進程，把CPUCPU的使用權(quán)交給被選的使用權(quán)交給被選中的進程中的進程Operating SystemOperating SystemPage 162022-3-17q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進程調(diào)度的任務(wù)進程調(diào)度

14、的任務(wù)q 確定算法的原則確定算法的原則q 進程調(diào)度方式進程調(diào)度方式q 調(diào)度隊列模型調(diào)度隊列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Operating SystemOperating SystemPage 172022-3-17q 具有具有公平性公平性q 資源資源利用率高利用率高（特別是（特別是CPUCPU利用率）利用率）q 在交互式系統(tǒng)情況下要追求在交互式系統(tǒng)情況下要追求響應(yīng)時間響應(yīng)時間（越短越好）（越短越好）q 在批處理系統(tǒng)情況下要追求系統(tǒng)在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量吞吐量Operating SystemOperating SystemPage 1820

15、22-3-17q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進程調(diào)度的任務(wù)進程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進程調(diào)度方式進程調(diào)度方式q 調(diào)度隊列模型調(diào)度隊列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Operating SystemOperating SystemPage 192022-3-17q 非搶占方式非搶占方式(Non-preemptive Mode)(Non-preemptive Mode)q 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)Operating SystemOperating Syste

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

17、發(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)開銷小缺點缺點：緊急任務(wù)不：緊急任務(wù)不能及時響應(yīng)；短進能及時響應(yīng)；短進程到達要等待長進程到達要等待長進程運行結(jié)束程運行結(jié)束Operating SystemOperating SystemPage 212022-3-17q 搶占方式搶占方式(Preemptive Mode

18、)(Preemptive Mode) 當(dāng)某一進程正在處理機上執(zhí)行時，若有某個當(dāng)某一進程正在處理機上執(zhí)行時，若有某個更為重要或緊迫的進程進入就緒隊列，則立即更為重要或緊迫的進程進入就緒隊列，則立即暫停正在執(zhí)行的進程，將處理機分配給這個更暫停正在執(zhí)行的進程，將處理機分配給這個更為重要或緊迫的進程為重要或緊迫的進程搶占式調(diào)度主要有以下原則搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則優(yōu)先權(quán)原則 允許高優(yōu)先權(quán)的新到進程搶允許高優(yōu)先權(quán)的新到進程搶占當(dāng)前進程的處理機占當(dāng)前進程的處理機短作業(yè)短作業(yè)( (進程進程) )優(yōu)先原則優(yōu)先原則允許執(zhí)行時間短允許執(zhí)行時間短的新到進程搶占當(dāng)前進程的處理機的新到進程搶占當(dāng)前進程的處理機

19、 時間片原則時間片原則 時間片用完后停止執(zhí)行，時間片用完后停止執(zhí)行，重新進行調(diào)度，適用于分時系統(tǒng)重新進行調(diào)度，適用于分時系統(tǒng) 優(yōu)點優(yōu)點：適于時間要：適于時間要求嚴(yán)格的實時系統(tǒng)求嚴(yán)格的實時系統(tǒng)缺點缺點：調(diào)度算法復(fù)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大雜，系統(tǒng)開銷大Operating SystemOperating SystemPage 222022-3-17q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進程調(diào)度的任務(wù)進程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進程調(diào)度方式進程調(diào)度方式q 調(diào)度隊列模型調(diào)度隊列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Operating S

20、ystemOperating SystemPage 232022-3-17q 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型q 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型q 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型Operating SystemOperating SystemPage 242022-3-17q 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型v在分時系統(tǒng)中，通常僅設(shè)有進程調(diào)度在分時系統(tǒng)中，通常僅設(shè)有進程調(diào)度v系統(tǒng)把這些進程組織成一個系統(tǒng)把這些進程組織成一個就緒隊列就緒隊列v每個進程在執(zhí)行時，可能有以下幾種情況每個進程在執(zhí)行時

21、，可能有以下幾種情況進程獲得進程獲得CPUCPU正在執(zhí)行正在執(zhí)行任務(wù)在給定時間片內(nèi)任務(wù)在給定時間片內(nèi)已完成已完成，釋放處理，釋放處理機后為完成狀態(tài)機后為完成狀態(tài)任務(wù)在時間片內(nèi)任務(wù)在時間片內(nèi)未完成未完成，進入就緒隊列，進入就緒隊列末尾末尾在執(zhí)行期間因某事件而阻塞在執(zhí)行期間因某事件而阻塞Operating SystemOperating SystemPage 252022-3-17q僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型就就 緒緒隊隊 列列阻阻 塞塞隊隊列列進程調(diào)度進程調(diào)度CPU進程完成進程完成等待事件等待事件交互用戶交互用戶事事件件出出現(xiàn)現(xiàn)時間片完時間片完Operating Sys

22、temOperating SystemPage 262022-3-17q 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型v在批處理系統(tǒng)中，不僅需要在批處理系統(tǒng)中，不僅需要進程調(diào)度進程調(diào)度，而，而且還要有且還要有作業(yè)調(diào)度作業(yè)調(diào)度v就緒隊列的形式就緒隊列的形式在批處理系統(tǒng)中，常用高優(yōu)先權(quán)隊列。在批處理系統(tǒng)中，常用高優(yōu)先權(quán)隊列。進程進入就緒隊列時，按優(yōu)先權(quán)高低插進程進入就緒隊列時，按優(yōu)先權(quán)高低插入相應(yīng)位置，調(diào)度程序總是把處理機分入相應(yīng)位置，調(diào)度程序總是把處理機分配給就緒隊首進程配給就緒隊首進程v設(shè)置多個阻塞隊列設(shè)置多個阻塞隊列根據(jù)事件的不同設(shè)置多個隊列提高效率根據(jù)事件的不同設(shè)置多個

23、隊列提高效率Operating SystemOperating SystemPage 272022-3-17進程調(diào)度進程調(diào)度CPU進程完成進程完成時間片完時間片完就就 緒緒隊隊列列12等待事件等待事件等待事件等待事件等待事件等待事件n12n事件事件 出現(xiàn)出現(xiàn)事件事件 出現(xiàn)出現(xiàn)事件事件 出現(xiàn)出現(xiàn)后后備備 隊隊列列作業(yè)作業(yè)調(diào)度調(diào)度與上一模型的主要區(qū)別：就緒隊列的形式；與上一模型的主要區(qū)別：就緒隊列的形式； 設(shè)置多個阻塞隊列設(shè)置多個阻塞隊列阻阻隊隊列列塞塞2 2阻阻隊隊列列塞塞n n阻阻隊隊列列塞塞1 1Operating SystemOperating SystemPage 282022-3-17

24、q同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型就緒隊列就緒隊列進程調(diào)度進程調(diào)度就緒，掛起隊列就緒，掛起隊列中級調(diào)度中級調(diào)度阻塞，掛起隊列阻塞，掛起隊列阻塞隊列阻塞隊列等待事件等待事件進程完成進程完成時間片完時間片完作業(yè)調(diào)度作業(yè)調(diào)度交互型作業(yè)交互型作業(yè)后備隊列后備隊列批量作業(yè)批量作業(yè)掛起掛起掛起掛起事事件件出出現(xiàn)現(xiàn)事件出現(xiàn)事件出現(xiàn)CPUOperating SystemOperating SystemPage 292022-3-17q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進程調(diào)度的任務(wù)進程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進程調(diào)度方式進程調(diào)度方式q 調(diào)度隊列模型

25、調(diào)度隊列模型q選擇調(diào)度方式和調(diào)度算法的若干準(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)如何考慮？Operating SystemOperating SystemPage 302022-3-173.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)則 Operating SystemOperating SystemPage 31202

26、2-3-173.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1. 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時間短。周轉(zhuǎn)時間短。 (2) 響應(yīng)時間快。響應(yīng)時間快。 (3) 截止時間的保證。截止時間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)則。優(yōu)先權(quán)準(zhǔn)則。 Operating SystemOperating SystemPage 322022-3-17q 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v周轉(zhuǎn)時間短周轉(zhuǎn)時間短平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間niiTnT11niSiiTTnW11帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：進程（或作業(yè)）的進程（或作業(yè)）的周轉(zhuǎn)時周轉(zhuǎn)時間間T T與系統(tǒng)為它與系統(tǒng)為它提供服務(wù)的時間提

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

28、時間或必須完成的最遲時間間或必須完成的最遲時間截止時間是截止時間是實時系統(tǒng)實時系統(tǒng)中的重要指標(biāo)中的重要指標(biāo)Operating SystemOperating SystemPage 342022-3-17q面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v 周轉(zhuǎn)時間短周轉(zhuǎn)時間短v 響應(yīng)時間快響應(yīng)時間快v 截止時間保證截止時間保證批處理系統(tǒng)批處理系統(tǒng)分時系統(tǒng)分時系統(tǒng)實時系統(tǒng)實時系統(tǒng)等待時間短等待時間短優(yōu)先權(quán)優(yōu)先權(quán)Operating SystemOperating SystemPage 352022-3-17q面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v等待時間短等待時間短等待時間等待時間是在就緒隊列中等待所花的時間是在就緒隊列中等

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

30、數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響大影響v處理機利用率高處理機利用率高v各類資源的平衡利用各類資源的平衡利用使內(nèi)存、外存和使內(nèi)存、外存和I/OI/O設(shè)備的利用率高設(shè)備的利用率高基于這樣的準(zhǔn)則，你設(shè)計操作系統(tǒng)的調(diào)度策略應(yīng)如何？基于這樣的準(zhǔn)則，你設(shè)計操作系統(tǒng)的調(diào)度策略應(yīng)如何？Operating SystemOperating SystemPage 372022-3-17q處理機調(diào)度的基本概念處理機調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實時調(diào)度實時調(diào)度 q多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度q產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q預(yù)

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

32、，有些適用于進程調(diào)度，有些兩者皆可程調(diào)度，有些兩者皆可Operating SystemOperating SystemPage 392022-3-17q 先來先服務(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 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Operating SystemOperating SystemPage 402022-3-17q 先來先服務(wù)先來先服務(wù)(FCFS)/先進先出先進先出(FIFO)調(diào)度算法調(diào)度算法v按照作業(yè)按照作業(yè)/進程進入系統(tǒng)的進程進入系統(tǒng)的先后次序先后次序進行調(diào)度，進行調(diào)度，先進入系統(tǒng)者先調(diào)度；即啟動等待時間最

33、長先進入系統(tǒng)者先調(diào)度；即啟動等待時間最長的作業(yè)的作業(yè)/進程進程v是一種最簡單的調(diào)度算法，即可用于是一種最簡單的調(diào)度算法，即可用于作業(yè)調(diào)作業(yè)調(diào)度度，也可用于，也可用于進程調(diào)度進程調(diào)度q 幾個術(shù)語幾個術(shù)語v到達時間、服務(wù)時間、開始時間到達時間、服務(wù)時間、開始時間v完成時間、等待時間完成時間、等待時間v周轉(zhuǎn)時間：完成時間周轉(zhuǎn)時間：完成時間-到達時間到達時間v帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/服務(wù)時間服務(wù)時間Operating SystemOperating SystemPage 412022-3-17進程名進程名到達時間到達時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)

34、時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均04A13B25C32D44E044476先來先服務(wù)（先進先出）：先來先服務(wù)（先進先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518tOperating SystemOperating SystemPage 422022-3-17q 先來先服務(wù)先來先服務(wù)（先進先出）（先進先出）優(yōu)缺點優(yōu)缺點v 比較有利于比較有利于長作業(yè)（進程）長作業(yè)（進程），而不利于，而不利于短作短作業(yè)（進程）業(yè)（進程）v 有利于有利于CPU繁忙型作業(yè)（進程）繁忙型作業(yè)（進程） ，

35、而不利于，而不利于I/O繁忙型作業(yè)（進程）繁忙型作業(yè)（進程）v 用于批處理系統(tǒng)，不適于分時系統(tǒng)用于批處理系統(tǒng)，不適于分時系統(tǒng)Operating SystemOperating SystemPage 432022-3-17q短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)Fv短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)F，以要求，以要求運運行時間長短行時間長短進行調(diào)度，即啟動要求運行時間最進行調(diào)度，即啟動要求運行時間最短的作業(yè)短的作業(yè)v可以分別用于可以分別用于作業(yè)調(diào)度作業(yè)調(diào)度和和進程調(diào)度進程調(diào)度v短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)(SJ

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

37、2-3-17進程名進程名到達時間到達時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均04A13B25C32D44E0441短作業(yè)短作業(yè)/短進程優(yōu)先（短進程優(yōu)先（SJF/SPF）：）：4633/26988/391399/413181616/540/52.1A A A AB B BC C C C CD DE E E E05101518tOperating SystemOperating SystemPage 452022-3-17qFCFS/SJF調(diào)度算法的性能調(diào)度算法的性能SJFSJF能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量能有效

38、地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量 作業(yè)作業(yè)調(diào)度調(diào)度 情況情況 算法算法進程名進程名ABCDE平均平均到達時間到達時間01234服務(wù)時間服務(wù)時間43524FCFS完成時間完成時間47121418周轉(zhuǎn)時間周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間完成時間4918613周轉(zhuǎn)時間周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.1SJFSJF平均周轉(zhuǎn)平均周轉(zhuǎn)時間和平均帶時間和平均帶權(quán)周轉(zhuǎn)時間明權(quán)周轉(zhuǎn)時間明顯改善顯改善Operating SystemOperating SystemPage 462022-3-17qSJ(

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

40、提供的所提供的估估計執(zhí)行時間計執(zhí)行時間而定的，而用戶又可能會而定的，而用戶又可能會有意或無意有意或無意地地縮短縮短其作業(yè)的估計其作業(yè)的估計運行時間運行時間，致使該算法不一，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。定能真正做到短作業(yè)優(yōu)先調(diào)度。Operating SystemOperating SystemPage 472022-3-17q先來先服務(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基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Operating SystemOperating SystemPage 482022-3-17q優(yōu)先權(quán)調(diào)度算法的類

41、型優(yōu)先權(quán)調(diào)度算法的類型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 492022-3-17q優(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)度算法特點：系統(tǒng)一旦把處理機分配給就緒隊特點：系統(tǒng)一旦把處理機分配給就緒隊列中列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進程后，該進程便的進程后，該進程便一一直執(zhí)行直執(zhí)行下去，直至完成，或因發(fā)生某事下去，直至完成，或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)才將處件使該進程放棄處理機時，系統(tǒng)才將處理機重新分配給另一優(yōu)先權(quán)最高的進程

42、理機重新分配給另一優(yōu)先權(quán)最高的進程主要主要用于批處理系統(tǒng)用于批處理系統(tǒng)中，也可用于某些中，也可用于某些對實時性對實時性要求不嚴(yán)的實時系統(tǒng)要求不嚴(yán)的實時系統(tǒng)中中Operating SystemOperating SystemPage 502022-3-17q優(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)度算法把處理機分配給優(yōu)先權(quán)最高的進程，但在執(zhí)行把處理機分配給優(yōu)先權(quán)最高的進程，但在執(zhí)行期間，只要出現(xiàn)另一個優(yōu)先權(quán)更高的進程，則期間，只要出現(xiàn)另一個優(yōu)先權(quán)更高的進程，則進程調(diào)度程序就進程調(diào)度程序就立即停止立即停止當(dāng)前進程的執(zhí)行，并當(dāng)前進程的執(zhí)行，并將處理機分配給新到的優(yōu)

43、先權(quán)最高的進程將處理機分配給新到的優(yōu)先權(quán)最高的進程注意注意：只要只要系統(tǒng)中系統(tǒng)中出現(xiàn)出現(xiàn)一個新的就緒進程，一個新的就緒進程，就就進行進行優(yōu)先權(quán)優(yōu)先權(quán)比較比較該調(diào)度算法，能更好地該調(diào)度算法，能更好地滿足緊迫作業(yè)滿足緊迫作業(yè)的要求，的要求，故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中對性能要求較高的批處理和分時系統(tǒng)中Operating SystemOperating SystemPage 512022-3-17q優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)v動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)Operating SystemOperating

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

45、erating SystemPage 532022-3-17確定進程優(yōu)先權(quán)的依據(jù)有如下三個方面：進程類型。進程類型。系統(tǒng)進程的優(yōu)先權(quán)高于一般用戶進程。 (2) 進程對資源的需求。進程對資源的需求。如進程的估計執(zhí)行時間及內(nèi)存需要量少的進程，應(yīng)賦予較高的優(yōu)先權(quán)。 (3) 用戶要求。用戶要求。由用戶進程的緊迫程度和用戶所付費用的多少來確定優(yōu)先權(quán)。 Operating SystemOperating SystemPage 542022-3-17q優(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)建進程時確定，且在進程的整個靜態(tài)優(yōu)先權(quán)在創(chuàng)建進程時確定，且在進程的整個運行期間運行期間保持不變保持

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

47、優(yōu)先對長進程不利！Operating SystemOperating SystemPage 552022-3-17v動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)隨隨進程的推進進程的推進或隨其或隨其等待時間等待時間的增加而改變，以獲的增加而改變，以獲得更好的調(diào)度性能得更好的調(diào)度性能可規(guī)定，在可規(guī)定，在就緒隊列中的進程就緒隊列中的進程，隨其，隨其等待時間的增等待時間的增長長，其優(yōu)先權(quán)，其優(yōu)先權(quán)以速率以速率a提高提高具有具有相同相同優(yōu)先權(quán)優(yōu)先權(quán)初值初值的進程，則的進程，則最先進入最先進入就緒就緒隊列，其將因其動態(tài)優(yōu)先權(quán)變得最高而隊列，其將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲優(yōu)先獲得得處理機，此即處理機，此即FCFS算法算法具有各

48、不相同的優(yōu)先權(quán)初值的就緒進程，則具有各不相同的優(yōu)先權(quán)初值的就緒進程，則優(yōu)優(yōu)先權(quán)初值低先權(quán)初值低的進程，在的進程，在等待了足夠的時間等待了足夠的時間后，后，其其優(yōu)先權(quán)便可能升為最高優(yōu)先權(quán)便可能升為最高，從而可以獲得處理，從而可以獲得處理機機當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前規(guī)定當(dāng)前進程進程的優(yōu)先權(quán)的優(yōu)先權(quán)以速率以速率b下降下降，則可防止一個長作業(yè)，則可防止一個長作業(yè)長期地長期地壟斷壟斷處理機處理機Operating SystemOperating SystemPage 562022-3-17進程進程名名到達到達時間時間服務(wù)服務(wù)時間時間靜態(tài)優(yōu)靜態(tài)優(yōu)先權(quán)

49、先權(quán)開始開始時間時間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均靜態(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)屨际綋屨际?，情況如何？，情況如何？Operating SystemOperating SystemPage 572022-3-17q高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（HRF）v是是FCFS和和SJF的結(jié)合，克服了兩種算法的的結(jié)合，克服了兩種算法的缺點缺點v調(diào)度策略調(diào)度策略：響應(yīng)比：響應(yīng)比最高

50、的作業(yè)優(yōu)先啟動最高的作業(yè)優(yōu)先啟動v因因等待時間等待時間+服務(wù)時間服務(wù)時間=該作業(yè)的該作業(yè)的響應(yīng)時間響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比響應(yīng)比RP。據(jù)此，又。據(jù)此，又可表示為可表示為時時間間務(wù)務(wù)時時間間權(quán)權(quán)務(wù)務(wù)時時間間等等待待+ + 要要求求服服優(yōu)優(yōu)先先= =要要求求服服時間務(wù)時間響應(yīng)時間權(quán)務(wù)時間務(wù)時間等等待待+ + 要要求求服服優(yōu)優(yōu)先先= = =要要求求服服要要求求服服Operating SystemOperating SystemPage 582022-3-17q 對對HRF的小結(jié)的小結(jié)v等待時間相同等待時間相同的作業(yè)，則的作業(yè)，則要求服務(wù)的時間愈要求服務(wù)的時間愈短短，其，其

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

52、間權(quán)務(wù)時間務(wù)時間等等待待+ + 要要求求服服優(yōu)優(yōu)先先= = =要要求求服服要要求求服服對短作業(yè)有利對短作業(yè)有利是先來先服務(wù)是先來先服務(wù)對長作業(yè)有利對長作業(yè)有利Operating SystemOperating SystemPage 592022-3-17q先來先服務(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基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Operating SystemOperating SystemPage 602022-3-17q 簡單的時間片輪轉(zhuǎn)法簡單的時間片輪轉(zhuǎn)法(RRRound Robin)v系統(tǒng)將所有的就緒進程按先來先服務(wù)

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

54、的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間缺點：緊迫任務(wù)響應(yīng)慢。缺點：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時間片中采用：時間片+優(yōu)先權(quán)優(yōu)先權(quán)Operating SystemOperating SystemPage 612022-3-17進程名進程名到達時間到達時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均A B C D E A B C D E A B C E A C E C05101518t04A03B05C02D04E012349121517181515/41212/31818/599/2171

55、7/414.24.02若到達時間若到達時間為為0 0、1 1、2 2、3 3、4 4，又如，又如何？何？Operating SystemOperating SystemPage 622022-3-17v分時系統(tǒng)中常用時間片輪轉(zhuǎn)法分時系統(tǒng)中常用時間片輪轉(zhuǎn)法時間片選擇時間片選擇問題問題固定時間片固定時間片可變時間片可變時間片時間片大小時間片大小與與時間片大小時間片大小有關(guān)的因素有關(guān)的因素系統(tǒng)響應(yīng)時間系統(tǒng)響應(yīng)時間就緒進程個數(shù)就緒進程個數(shù)CPUCPU能力能力 Operating SystemOperating SystemPage 632022-3-173.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的

56、輪轉(zhuǎn)調(diào)度算法 2. 時間片大小的確定時間片大小的確定（1）系統(tǒng)對響應(yīng)時間的要求）系統(tǒng)對響應(yīng)時間的要求 數(shù)目N和時間片q成反比，即T=Nq，因此在進程數(shù)一定時，作為分時系統(tǒng)首先就是必須滿足系統(tǒng)對響應(yīng)時間的要求。時間片的長短將正比于系統(tǒng)所要求的響應(yīng)時間。（2）就緒隊列中進程的數(shù)目）就緒隊列中進程的數(shù)目 在分時系統(tǒng)中，就緒隊列上所有的進程數(shù)，是隨著在終端上機的用戶數(shù)目而改變的，但系統(tǒng)應(yīng)保證，當(dāng)所有終端用戶上機時，獲得較好的響應(yīng)時間。（3）系統(tǒng)的處理能力）系統(tǒng)的處理能力 系統(tǒng)的處理能力是必須保證用戶鍵入的常用命令能在一個時間片內(nèi)處理完畢，否則將無法保證得到滿意的響應(yīng)時間，而且會使平均周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)

57、時間都很長。 Operating SystemOperating SystemPage 642022-3-172. 多級隊列調(diào)度多級隊列調(diào)度前臺前臺的就緒隊列是交互性作業(yè)的進程，采用時間片輪轉(zhuǎn)。后臺后臺的就緒隊列是批處理作業(yè)的進程，采用優(yōu)先權(quán)或短作業(yè)優(yōu)先算法。調(diào)度方式有兩種：(1) 優(yōu)先調(diào)度前臺，若前臺無可運行進程，才調(diào)度后臺。(2) 分配占用CPU的時間比例，如：前臺80%，后臺20%。3.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 Operating SystemOperating SystemPage 652022-3-17q多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 v設(shè)置

58、設(shè)置多個就緒隊列多個就緒隊列，并為各個隊列賦予，并為各個隊列賦予不同不同的優(yōu)先級的優(yōu)先級第一個隊列的優(yōu)先級最高，第二個隊列次第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低之，其余各隊列的優(yōu)先權(quán)逐個降低該算法賦予各個隊列中進程執(zhí)行該算法賦予各個隊列中進程執(zhí)行時間片的時間片的大小也各不相同大小也各不相同，在，在優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高的隊列中，的隊列中，為每個進程所規(guī)定的執(zhí)行為每個進程所規(guī)定的執(zhí)行時間片就愈小時間片就愈小。例如，例如，第二個第二個隊列的時間片要隊列的時間片要比第一個比第一個隊隊列的時間片列的時間片長一倍長一倍，第，第i i+1+1個隊列的時個隊列的時間片要比第間片要

59、比第i i個隊列的時間片長一倍個隊列的時間片長一倍Operating SystemOperating SystemPage 662022-3-17就緒隊列就緒隊列1 1就緒隊列就緒隊列2 2就緒隊列就緒隊列3 3就緒隊列就緒隊列n nS1S2S3至至CPU至至CPU至至CPU至至CPU( (時間片：時間片：S1 S2 S3) )v調(diào)度方式調(diào)度方式高高低低優(yōu)先級優(yōu)先級時間片時間片小小大大Sn按按FIFO原則原則排隊等待調(diào)排隊等待調(diào)度度尚未完成轉(zhuǎn)入第二尚未完成轉(zhuǎn)入第二隊列的末尾，按隊列的末尾，按FIFO原則等待調(diào)原則等待調(diào)度度采取按時間片輪采取按時間片輪轉(zhuǎn)的方式運行轉(zhuǎn)的方式運行因等待而放棄因等待而放棄CPU后，后，進入阻塞隊列，一旦進入阻塞隊列，一旦等待的事件發(fā)生，則等待的事件發(fā)生，則回到原來的就緒隊列回到原來的就緒隊列Operating SystemOperating SystemPage 672022-3-17v注意注意僅當(dāng)?shù)趦H當(dāng)?shù)?(i-1) 隊列均空時，才會調(diào)度第隊列均空時，才會調(diào)度第i隊列隊列中的進