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

1、第三章 處理機調(diào)度與死鎖操作系統(tǒng)Page 12022/10/12第三章 處理機調(diào)度與死鎖重點掌握進程調(diào)度算法，各適用于何種情況 理解常用的幾種實時調(diào)度算法 理解產(chǎn)生死鎖的原因 掌握銀行家算法避免死鎖難點多道程序設(shè)計中的各種調(diào)度算法 響應(yīng)比高者優(yōu)先調(diào)度算法的計算過程 銀行家算法 Page 22022/10/12第三章 處理機調(diào)度與死鎖知識點處理機調(diào)度及調(diào)度算法多處理機環(huán)境下的進程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測與解除 銀行家算法Page 32022/10/12第三章 處理機調(diào)度與死鎖處理機是計算機系統(tǒng)中的重要資源在多道程序環(huán)境下，進程數(shù)目通常多于處理機的數(shù)目系統(tǒng)

2、必須按一定方法動態(tài)地把處理機分配給就緒隊列中的一個進程處理機利用率和系統(tǒng)性能（吞吐量、響應(yīng)時間）在很大程度上取決于處理機調(diào)度分配處理機的任務(wù)是由進程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計的中心問題之一。WHAT：按什么原則分配CPU進程調(diào)度算法WHEN：何時分配CPU 進程調(diào)度的時機 HOW：如何分配CPU CPU調(diào)度過程（進程的上下文切換）Page 42022/10/12第三章 處理機調(diào)度與死鎖 處理機調(diào)度的基本概念 調(diào)度算法 實時調(diào)度 多處理機系統(tǒng)中的調(diào)度 產(chǎn)生死鎖的原因和必要條件 預(yù)防死鎖的方法 死鎖的檢測與解除Page 52022/10/12處理機調(diào)度的基本概念 高級、中級和低級調(diào)度進程調(diào)度

3、的任務(wù)確定算法的原則進程調(diào)度方式調(diào)度隊列模型選擇調(diào)度方式和調(diào)度算法的若干準則Page 62022/10/12處理機調(diào)度的基本概念作業(yè)是用戶在一次解題或一個事務(wù)處理過程中要求計算機系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等作業(yè)的狀態(tài)：一個作業(yè)進入系統(tǒng)到運行結(jié)束，一般需要經(jīng)歷收容、運行、完成三個階段，與之相對應(yīng)的是作業(yè)的三種狀態(tài)后備狀態(tài)運行狀態(tài)完成狀態(tài)Page 72022/10/12運行狀態(tài)處理機調(diào)度的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請求時間片完作業(yè)注冊作業(yè)調(diào)度進程調(diào)度終止作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換Page 82022/10/123.1 處理機調(diào)度的基本概念 3.1.1 高級

4、、中級和低級調(diào)度 1. 高級調(diào)度(High Scheduling) 2. 低級調(diào)度(Low Level Scheduling) 3. 中級調(diào)度(Intermediate-Level Scheduling) Page 92022/10/12高級、中級和低級調(diào)度高級調(diào)度(High Scheduling) 作業(yè)調(diào)度或長程調(diào)度（Long-Term Scheduling）主要任務(wù)是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進程，放入就緒隊列，以使該作業(yè)的進程獲得競爭處理機的權(quán)利也稱為接納調(diào)度（Admission Scheduling）高

5、級調(diào)度的時間尺度通常是分鐘、小時或天Page 102022/10/12高級、中級和低級調(diào)度在每次作業(yè)調(diào)度時，須決定：接納多少個作業(yè) 即允許多少個作業(yè)同時在內(nèi)存中運行，取決于多 道程序度（Degree of Multiprogramming）作業(yè)太多 服務(wù)質(zhì)量下降作業(yè)太少 資源利用率低接納哪些作業(yè) 取決于作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度周轉(zhuǎn)時間太長系統(tǒng)吞吐量太低 適當(dāng)?shù)恼壑远嗟莱绦蚨龋杭丛试S多少個作業(yè)同時在內(nèi)存中運行。周轉(zhuǎn)時間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。吞吐量：是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。Page 112022/10/12高級、中級和低

6、級調(diào)度低級調(diào)度 進程調(diào)度或短程調(diào)度（Short-Term Scheduling）主要任務(wù)是按照某種策略和方法選取一個處于就緒狀態(tài)的進程，將處理機分配給它常見的低級調(diào)度有非搶占式和搶占式兩種低級調(diào)度的時間尺度通常是毫秒級的。由于低級調(diào)度算法的頻繁使用，要求在實現(xiàn)時做到高效Page 122022/10/12高級、中級和低級調(diào)度中級調(diào)度(Intermediate-Level Scheduling) 中程調(diào)度(Medium-Term Scheduling)引入目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待主要任務(wù)是按照給定的原則和策略，將

7、處于外存對換區(qū)中的重又具備運行條件的就緒進程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進程交換到外存對換區(qū)Page 132022/10/12處理機調(diào)度的基本概念 高級、中級和低級調(diào)度 進程調(diào)度的任務(wù) 確定算法的原則 進程調(diào)度方式 調(diào)度隊列模型 選擇調(diào)度方式和調(diào)度算法的若干準則Page 142022/10/12進程調(diào)度的任務(wù) 進程調(diào)度的任務(wù) 是控制、協(xié)調(diào)進程對CPU的競爭,即按一定的調(diào)度算法從就緒隊列中選中一個進程，把CPU的使用權(quán)交給被選中的進程Page 152022/10/12處理機調(diào)度的基本概念 高級、中級和低級調(diào)度 進程調(diào)度的任務(wù) 確定算法的原則 進程調(diào)度方式 調(diào)度隊列模型 選擇調(diào)度

8、方式和調(diào)度算法的若干準則Page 162022/10/12確定算法的原則 具有公平性 資源利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應(yīng)時間（越短越好） 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量Page 172022/10/12處理機調(diào)度的基本概念 高級、中級和低級調(diào)度 進程調(diào)度的任務(wù) 確定算法的原則 進程調(diào)度方式 調(diào)度隊列模型 選擇調(diào)度方式和調(diào)度算法的若干準則Page 182022/10/12進程調(diào)度方式非搶占方式(Non-preemptive Mode)搶占方式(Preemptive Mode)Page 192022/10/12進程調(diào)度方式非搶占方式(Non-preemptive

9、Mode) 當(dāng)某一進程正在處理機上執(zhí)行時，即使有某個更為重要或緊迫的進程進入就緒隊列，該進程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進入完成或阻塞狀態(tài)時，才把處理機分配給更為重要或緊迫的進程引起進程調(diào)度的因素正在執(zhí)行的進程執(zhí)行完畢， 或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；在進程通信或同步過程中執(zhí)行了某種原語操作，如wait、Block、Wakeup原語優(yōu)點：算法簡單，系統(tǒng)開銷小缺點：緊急任務(wù)不能及時響應(yīng)；短進程到達要等待長進程運行結(jié)束Page 202022/10/12進程調(diào)度方式搶占方式(Preemptive Mode) 當(dāng)某一進程正在處理機上執(zhí)行時，若有某個更為

10、重要或緊迫的進程進入就緒隊列，則立即暫停正在執(zhí)行的進程，將處理機分配給這個更為重要或緊迫的進程搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則 允許高優(yōu)先權(quán)的新到進程搶占當(dāng)前進程的處理機短作業(yè)(進程)優(yōu)先原則允許執(zhí)行時間短的新到進程搶占當(dāng)前進程的處理機 時間片原則 時間片用完后停止執(zhí)行，重新進行調(diào)度，適用于分時系統(tǒng) 優(yōu)點：適于時間要求嚴格的實時系統(tǒng)缺點：調(diào)度算法復(fù)雜，系統(tǒng)開銷大Page 212022/10/12處理機調(diào)度的基本概念 高級、中級和低級調(diào)度 進程調(diào)度的任務(wù) 確定算法的原則 進程調(diào)度方式 調(diào)度隊列模型 選擇調(diào)度方式和調(diào)度算法的若干準則Page 222022/10/12調(diào)度隊列模型僅有進程調(diào)度的調(diào)度

11、隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型Page 232022/10/12調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型在分時系統(tǒng)中，通常僅設(shè)有進程調(diào)度系統(tǒng)把這些進程組織成一個就緒隊列每個進程在執(zhí)行時，可能有以下幾種情況進程獲得CPU正在執(zhí)行任務(wù)在給定時間片內(nèi)已完成，釋放處理機后為完成狀態(tài)任務(wù)在時間片內(nèi)未完成，進入就緒隊列末尾在執(zhí)行期間因某事件而阻塞Page 242022/10/12調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型就緒隊列阻塞隊列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完P(guān)age 252022/10/12調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型在批處

12、理系統(tǒng)中，不僅需要進程調(diào)度，而且還要有作業(yè)調(diào)度就緒隊列的形式在批處理系統(tǒng)中，常用高優(yōu)先權(quán)隊列。進程進入就緒隊列時，按優(yōu)先權(quán)高低插入相應(yīng)位置，調(diào)度程序總是把處理機分配給就緒隊首進程設(shè)置多個阻塞隊列根據(jù)事件的不同設(shè)置多個隊列提高效率Page 262022/10/12調(diào)度隊列模型進程調(diào)度CPU進程完成時間片完就緒隊列12等待事件等待事件等待事件n12n事件出現(xiàn)事件出現(xiàn)事件出現(xiàn)后備隊列作業(yè)調(diào)度與上一模型的主要區(qū)別：就緒隊列的形式； 設(shè)置多個阻塞隊列阻隊列塞2阻隊列塞n阻隊列塞1Page 272022/10/12調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型就緒隊列進程調(diào)度就緒，掛起隊列中級調(diào)度阻塞，掛起隊

13、列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起掛起事件出現(xiàn)事件出現(xiàn)CPUPage 282022/10/12處理機調(diào)度的基本概念 高級、中級和低級調(diào)度 進程調(diào)度的任務(wù) 確定算法的原則 進程調(diào)度方式 調(diào)度隊列模型選擇調(diào)度方式和調(diào)度算法的若干準則如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？Page 292022/10/123.1.3 選擇調(diào)度方式和調(diào)度算法的若干準則 1. 面向用戶的準則 2. 面向系統(tǒng)的準則 Page 302022/10/123.1.3 選擇調(diào)度方式和調(diào)度算法的若干準則 1. 面向用戶的準則 (1) 周轉(zhuǎn)

14、時間短。 (2) 響應(yīng)時間快。 (3) 截止時間的保證。 (4) 優(yōu)先權(quán)準則。 Page 312022/10/12選擇調(diào)度方式和調(diào)度算法的若干準則面向用戶的準則周轉(zhuǎn)時間短平均周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間：進程（或作業(yè)）的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比，即W=T/TS 。而平均帶權(quán)周轉(zhuǎn)時間則可表示為: Page 322022/10/12選擇調(diào)度方式和調(diào)度算法的若干準則面向用戶的準則響應(yīng)時間快響應(yīng)時間是指從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時間交互式系統(tǒng)用周轉(zhuǎn)時間衡量不是最佳截止時間保證截止時間是指某任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間截止時間是實時系統(tǒng)中的重

15、要指標Page 332022/10/12選擇調(diào)度方式和調(diào)度算法的若干準則面向用戶的準則 周轉(zhuǎn)時間短 響應(yīng)時間快 截止時間保證批處理系統(tǒng)分時系統(tǒng)實時系統(tǒng)等待時間短優(yōu)先權(quán)Page 342022/10/12選擇調(diào)度方式和調(diào)度算法的若干準則面向用戶的準則等待時間短等待時間是在就緒隊列中等待所花的時間調(diào)度算法并不影響進程運行和執(zhí)行I/O的時間量；只影響進程在就緒隊列中等待所花費的時間優(yōu)先權(quán)準則在批處理、實時和分時系統(tǒng)中都可以選擇優(yōu)先權(quán)準則，以便讓緊急任務(wù)先處理有時還選擇搶占式調(diào)度方式Page 352022/10/12選擇調(diào)度方式和調(diào)度算法的若干準則面向系統(tǒng)的準則系統(tǒng)吞吐量高吞吐量指單位時間內(nèi)系統(tǒng)所完成的

16、作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響處理機利用率高各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高基于這樣的準則，你設(shè)計操作系統(tǒng)的調(diào)度策略應(yīng)如何？Page 362022/10/12第三章 處理機調(diào)度與死鎖處理機調(diào)度的基本概念 調(diào)度算法 實時調(diào)度 多處理機系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件 預(yù)防死鎖的方法 死鎖的檢測與解除Page 372022/10/12調(diào)度算法在OS中調(diào)度的實質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法問題提出如何制定分配策略：對不同的系統(tǒng)和系統(tǒng)目標，通常采用不同的算法，如短作業(yè)優(yōu)先，時間片輪轉(zhuǎn)等有些算法適用于作業(yè)調(diào)度，有

17、些適用于進程調(diào)度，有些兩者皆可Page 382022/10/12調(diào)度算法 先來先服務(wù)和短作業(yè)優(yōu)先算法 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 基于時間片的輪轉(zhuǎn)調(diào)度算法Page 392022/10/12先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)(FCFS)/先進先出(FIFO)調(diào)度算法按照作業(yè)/進程進入系統(tǒng)的先后次序進行調(diào)度，先進入系統(tǒng)者先調(diào)度；即啟動等待時間最長的作業(yè)/進程是一種最簡單的調(diào)度算法，即可用于作業(yè)調(diào)度，也可用于進程調(diào)度幾個術(shù)語到達時間、服務(wù)時間、開始時間完成時間、等待時間周轉(zhuǎn)時間：完成時間-到達時間帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/服務(wù)時間Page 402022/10/12先來先服務(wù)和短作業(yè)優(yōu)先算法進程名到達時間服

18、務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均04A13B25C32D44E044476先來先服務(wù)（先進先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518tPage 412022/10/12先來先服務(wù)和短作業(yè)優(yōu)先算法 先來先服務(wù)（先進先出）優(yōu)缺點 比較有利于長作業(yè)（進程），而不利于短作業(yè)（進程） 有利于CPU繁忙型作業(yè)（進程） ，而不利于I/O繁忙型作業(yè)（進程） 用于批處理系統(tǒng)，不適于分時系統(tǒng)Page 422022/10/12先來先服務(wù)和短作業(yè)優(yōu)先算法短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)

19、F，以要求運行時間長短進行調(diào)度，即啟動要求運行時間最短的作業(yè)可以分別用于作業(yè)調(diào)度和進程調(diào)度短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行；而短進程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度Page 432022/10/12先來先服務(wù)和短作業(yè)優(yōu)先算法進程名到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均04A13B25C32D44E0441短作業(yè)/短進程優(yōu)先（SJF/SPF）：4633/26988/391399/

20、413181616/540/52.1AAAABBBCCCCCDDEEEE05101518tPage 442022/10/12FCFS/SJF調(diào)度算法的性能先來先服務(wù)和短作業(yè)優(yōu)先算法SJF能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量 作業(yè)調(diào)度 情況 算法進程名ABCDE平均到達時間01234服務(wù)時間43524FCFS完成時間47121418周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間4918613周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.1SJF平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間明顯改善Page 452022/10/12先來先服務(wù)和短作業(yè)優(yōu)

21、先算法SJ(P)F調(diào)度算法也存在不容忽視的缺點對長作業(yè)不利。嚴重的是，若一長作業(yè)(進程)進入系統(tǒng)的后備隊列(就緒隊列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進來的)短作業(yè)(進程)，將導(dǎo)致長作業(yè)(進程)長期不被調(diào)度饑餓完全未考慮作業(yè)(進程)的緊迫程度，因而不能保證緊迫性作業(yè)(進程)會被及時處理由于作業(yè)(進程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。Page 462022/10/12調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Page 472022/10/12高優(yōu)

22、先權(quán)優(yōu)先（HPF，Highest Priority First）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法Page 482022/10/12高優(yōu)先權(quán)優(yōu)先（HPF，Highest Priority First）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)調(diào)度算法特點：系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成，或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)才將處理機重新分配給另一優(yōu)先權(quán)最高的進程主要用于批處理系統(tǒng)中，也可用于某些對實時性要求不嚴的實時系統(tǒng)中Page 492022/10/12高優(yōu)先權(quán)優(yōu)先（HPFHighest Priori

23、ty First）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型搶占式優(yōu)先權(quán)調(diào)度算法把處理機分配給優(yōu)先權(quán)最高的進程，但在執(zhí)行期間，只要出現(xiàn)另一個優(yōu)先權(quán)更高的進程，則進程調(diào)度程序就立即停止當(dāng)前進程的執(zhí)行，并將處理機分配給新到的優(yōu)先權(quán)最高的進程注意：只要系統(tǒng)中出現(xiàn)一個新的就緒進程，就進行優(yōu)先權(quán)比較該調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中Page 502022/10/12高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)Page 512022/10/12高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進程時確定，且在進程的整個運行期

24、間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，07或0255， 又把該整數(shù)稱為優(yōu)先數(shù)確定進程靜態(tài)優(yōu)先權(quán)的依據(jù)進程類型:系統(tǒng)進程，用戶進程進程對資源的需求用戶要求Page 522022/10/12確定進程優(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)。 Page 532022/10/12高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進程時確定，且在進程的整個運行期間保持不變。一

25、般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，07或0255， 又把該整數(shù)稱為優(yōu)先數(shù)確定進程靜態(tài)優(yōu)先權(quán)的依據(jù)進程類型:系統(tǒng)進程，用戶進程進程對資源的需求用戶要求靜態(tài)優(yōu)先權(quán)特點系統(tǒng)開銷小、不夠精確、一般用在要求不高的系統(tǒng)中問題：用戶將優(yōu)先權(quán)設(shè)的較高，對其他進程不利！ 短進程優(yōu)先對長進程不利！Page 542022/10/12高優(yōu)先權(quán)優(yōu)先調(diào)度算法動態(tài)優(yōu)先權(quán)隨進程的推進或隨其等待時間的增加而改變，以獲得更好的調(diào)度性能可規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高具有相同優(yōu)先權(quán)初值的進程，則最先進入就緒隊列，其將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機，此即FCFS算法具有

26、各不相同的優(yōu)先權(quán)初值的就緒進程，則優(yōu)先權(quán)初值低的進程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機Page 552022/10/12進程名到達時間服務(wù)時間靜態(tài)優(yōu)先權(quán)開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均靜態(tài)優(yōu)先權(quán)，非搶占式（1為高優(yōu)先權(quán)）高優(yōu)先權(quán)優(yōu)先調(diào)度算法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下?lián)屨际剑闆r如何？Page 562022/10/12高優(yōu)先權(quán)優(yōu)先調(diào)度算法高響應(yīng)比

27、優(yōu)先調(diào)度算法（HRF）是FCFS和SJF的結(jié)合，克服了兩種算法的缺點調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先啟動因等待時間+服務(wù)時間=該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為Page 572022/10/12高優(yōu)先權(quán)優(yōu)先調(diào)度算法對HRF的小結(jié)等待時間相同的作業(yè)，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，要求服務(wù)的時間相同的作業(yè)，則等待時間愈長，其優(yōu)先權(quán)愈高，長作業(yè)，優(yōu)先權(quán)隨等待時間的增加而提高，其等待時間足夠長時，其優(yōu)先權(quán)便可升到很高， 從而也可獲得處理機是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，又不會使長作業(yè)長期得不到服務(wù)。缺點：要進行響應(yīng)比計算，增加了系統(tǒng)開銷對短作業(yè)

28、有利是先來先服務(wù)對長作業(yè)有利Page 582022/10/12調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Page 592022/10/12基于時間片的輪轉(zhuǎn)調(diào)度算法簡單的時間片輪轉(zhuǎn)法(RRRound Robin)系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便停止該進程的執(zhí)行，并將其放就緒隊列尾；然后，再把處理機分配給就緒隊列中新的隊首時間片的大小從幾ms到幾百ms優(yōu)點：公平。保證就緒隊列中所有進程在一給定的時間內(nèi)，均能獲得一時間片的處理機

29、執(zhí)行時間缺點：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時間片+優(yōu)先權(quán)Page 602022/10/12基于時間片的輪轉(zhuǎn)調(diào)度算法進程名到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到達時間為0、1、2、3、4，又如何？Page 612022/10/12基于時間片的輪轉(zhuǎn)調(diào)度算法分時系統(tǒng)中常用時間片輪轉(zhuǎn)法時間片選擇問題固定時間片可變時間片時間片大小與時間片大小有關(guān)的因素系統(tǒng)響應(yīng)時間就緒進程個數(shù)CPU能力 Page

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

31、2022/10/122. 多級隊列調(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)度算法 Page 642022/10/12基于時間片的輪轉(zhuǎn)調(diào)度算法多級反饋隊列調(diào)度算法 設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，第i+1個隊列的時間片要比第i個隊列的時間片長一倍Page 652022/10/12就緒隊列1基于時間片的輪轉(zhuǎn)調(diào)度算法就緒隊列2就緒隊列3就緒隊列nS1S2S3至CPU至CPU至CPU至CPU(時間片：S1S2S3)調(diào)度方式高低優(yōu)先級時間片小大Sn按FIFO原則排隊等待調(diào)度尚未完成轉(zhuǎn)入第二隊