1、第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖n重點重點n掌握掌握進程調(diào)度進程調(diào)度算法，各適用于何種情況算法，各適用于何種情況 n理解常用的幾種理解常用的幾種實時調(diào)度實時調(diào)度算法算法 n理解產(chǎn)生理解產(chǎn)生死鎖死鎖的原因的原因 n掌握掌握銀行家算法銀行家算法避免死鎖避免死鎖n難點難點n多道程序設(shè)計中的各種調(diào)度算法多道程序設(shè)計中的各種調(diào)度算法 n響應(yīng)比高者優(yōu)先調(diào)度算法的計算過程響應(yīng)比高者優(yōu)先調(diào)度算法的計算過程 n銀行家算法銀行家算法 第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖n知識點知識點n處理機調(diào)度及調(diào)度算法處理機調(diào)度及調(diào)度算法n多處理機環(huán)境下的進程（線程）調(diào)度方式多處理機環(huán)境下的進程（線程）

2、調(diào)度方式n產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件n預(yù)防死鎖的方法，死鎖的檢測與解除預(yù)防死鎖的方法，死鎖的檢測與解除 n銀行家算法銀行家算法第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖n處理機是計算機系統(tǒng)中的處理機是計算機系統(tǒng)中的重要資源重要資源n在多道程序環(huán)境下，進程數(shù)目通常多于在多道程序環(huán)境下，進程數(shù)目通常多于處理機的處理機的數(shù)目數(shù)目n系統(tǒng)必須按一定方法系統(tǒng)必須按一定方法動態(tài)地動態(tài)地把處理機把處理機分配給分配給就緒就緒隊列中的一個進程隊列中的一個進程n處理機處理機利用率利用率和和系統(tǒng)性能系統(tǒng)性能（吞吐量、響應(yīng)時間）（吞吐量、響應(yīng)時間）在很大程度上取決于處理機調(diào)度在很大程度上取決于

3、處理機調(diào)度WHAT：按什么原則分配：按什么原則分配CPU進程調(diào)度算法進程調(diào)度算法WHEN：何時分配：何時分配CPU 進程調(diào)度的時機進程調(diào)度的時機 HOW：如何分配：如何分配CPU CPU調(diào)度過程（進程調(diào)度過程（進程的上下文切換）的上下文切換）第三章 處理機調(diào)度與死鎖 3.1 處理機調(diào)度的層次處理機調(diào)度的層次和調(diào)度算法的目標和調(diào)度算法的目標3.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度3.3 進程調(diào)度進程調(diào)度3.4 實時調(diào)度實時調(diào)度 3.5 死鎖描述死鎖描述3.6 預(yù)防死鎖預(yù)防死鎖3.7 避免死鎖避免死鎖3.8 死鎖的檢測與解除死鎖的檢測與解除 3.1.1 處理機調(diào)度的層次處理機調(diào)度的層次n高級調(diào)度高級調(diào)

4、度(High Scheduling)(High Scheduling) 作業(yè)調(diào)度作業(yè)調(diào)度或或長程調(diào)度（長程調(diào)度（Long-Term SchedulingLong-Term Scheduling）n按一定的原則對外存上處于后備狀態(tài)的作業(yè)按一定的原則對外存上處于后備狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)進行選擇，給選中的作業(yè)分配分配內(nèi)存、輸入內(nèi)存、輸入/ /輸輸出設(shè)備等出設(shè)備等必要的資源必要的資源，并，并建立建立相應(yīng)的相應(yīng)的進程進程，放入放入就緒就緒隊列隊列，以使該作業(yè)的進程獲得競爭，以使該作業(yè)的進程獲得競爭處理機的權(quán)利。處理機的權(quán)利。n也稱為也稱為接納調(diào)度（接納調(diào)度（Admission Schedul

5、ingAdmission Scheduling）n時間尺度：通常是分鐘、小時或天。時間尺度：通常是分鐘、小時或天。3.1.1 處理機調(diào)度的層次處理機調(diào)度的層次n低級調(diào)度低級調(diào)度 進程調(diào)度進程調(diào)度或或短程調(diào)度短程調(diào)度（Short-Term Scheduling）n按照某種按照某種策略和方法策略和方法選取選取一個處于一個處于就緒就緒狀態(tài)的狀態(tài)的進程，將處理機進程，將處理機分配分配給它。給它。n常見調(diào)度方式常見調(diào)度方式n非搶占式；非搶占式；n搶占式搶占式。n時間尺度：通常是時間尺度：通常是毫秒級毫秒級的。的。n由于低級調(diào)度算法的由于低級調(diào)度算法的頻繁使用頻繁使用，要求在實現(xiàn)時做到，要求在實現(xiàn)時做到高

6、效。高效。3.1.1 處理機調(diào)度的層次處理機調(diào)度的層次n中級調(diào)度中級調(diào)度( (Intermediate-Level SchedulingIntermediate-Level Scheduling) ) 中程調(diào)度中程調(diào)度(Medium-Term Scheduling)(Medium-Term Scheduling)n引入目的引入目的n提高提高內(nèi)存利用率內(nèi)存利用率和和系統(tǒng)吞吐量。系統(tǒng)吞吐量。使那些暫時不能使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待。調(diào)至外存上去等待。n交換過程交換過程n按照給定的按照給定的原則和策略原則和策略，

7、將處于外存，將處于外存對換區(qū)對換區(qū)中的中的重又具備運行條件的就緒進程重又具備運行條件的就緒進程調(diào)入內(nèi)存調(diào)入內(nèi)存，或?qū)⑻?，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進程于內(nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進程交換到外交換到外存存對換區(qū)。對換區(qū)。3.1.1 處理機調(diào)度的層次處理機調(diào)度的層次n進程調(diào)度進程調(diào)度的運行頻率最高，在分時系統(tǒng)中通常是的運行頻率最高，在分時系統(tǒng)中通常是10100 ms便進行一次進程調(diào)度，因此把它稱為便進行一次進程調(diào)度，因此把它稱為短程調(diào)度。為避免進程調(diào)度占用太多的短程調(diào)度。為避免進程調(diào)度占用太多的CPU時間，時間，進程調(diào)度算法不宜太復(fù)雜。進程調(diào)度算法不宜太復(fù)雜。n作業(yè)調(diào)度作業(yè)調(diào)度往往是發(fā)

8、生在一個往往是發(fā)生在一個(批批)作業(yè)運行完畢，作業(yè)運行完畢，退出系統(tǒng)，而需要重新調(diào)入一個退出系統(tǒng)，而需要重新調(diào)入一個(批批)作業(yè)進入內(nèi)作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其運行頻率較低，因此把它稱為長程調(diào)度。由于其運行頻率較低，故允許作業(yè)調(diào)度算法花費較多的時間。故允許作業(yè)調(diào)度算法花費較多的時間。n中級調(diào)度中級調(diào)度的運行頻率基本上介于上述兩種調(diào)度之的運行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。間，因此把它稱為中程調(diào)度。3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n處理調(diào)度算法的共同目標處

9、理調(diào)度算法的共同目標n資源的利用率資源的利用率n公平性公平性n平衡性平衡性n策略強制執(zhí)行策略強制執(zhí)行3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n基本術(shù)語基本術(shù)語n到達時間到達時間n作業(yè)進入后備作業(yè)隊列或新創(chuàng)建進程進入就緒隊列作業(yè)進入后備作業(yè)隊列或新創(chuàng)建進程進入就緒隊列的時刻；的時刻；n服務(wù)時間服務(wù)時間n作業(yè)（進程）占用處理機的時間作業(yè)（進程）占用處理機的時間n開始時間開始時間n作業(yè)被創(chuàng)建進入就緒隊列或進程首次占有處理機的作業(yè)被創(chuàng)建進入就緒隊列或進程首次占有處理機的時刻時刻n完成時間完成時間n用戶獲得作業(yè)執(zhí)行結(jié)果的時刻。用戶獲得作業(yè)執(zhí)行結(jié)果的時刻。3.1.2 處理機調(diào)度算法的目標處理機

10、調(diào)度算法的目標n批處理系統(tǒng)的目標批處理系統(tǒng)的目標n平均周轉(zhuǎn)時間短平均周轉(zhuǎn)時間短n周轉(zhuǎn)時間，周轉(zhuǎn)時間，指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔成為止的這段時間間隔(稱為作業(yè)周轉(zhuǎn)時間稱為作業(yè)周轉(zhuǎn)時間)。它包。它包括四部分時間：括四部分時間：n作業(yè)在外存后備隊列上等待作業(yè)在外存后備隊列上等待(作業(yè)作業(yè))調(diào)度的時間；調(diào)度的時間；n進程在就緒隊列上等待進程調(diào)度的時間進程在就緒隊列上等待進程調(diào)度的時間n進程在進程在CPU上執(zhí)行的時間；上執(zhí)行的時間；n進程等待進程等待I/O操作完成的時間。操作完成的時間。注意注意：此三項在一：此三項在一個作業(yè)的處理過程個作業(yè)的

11、處理過程中可能會發(fā)生多次。中可能會發(fā)生多次。周轉(zhuǎn)時間周轉(zhuǎn)時間=完成時間完成時間-到達時間到達時間3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n批處理系統(tǒng)的目標批處理系統(tǒng)的目標n平均周轉(zhuǎn)時間短平均周轉(zhuǎn)時間短n平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間n帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：進程（或作業(yè)）的進程（或作業(yè)）的周轉(zhuǎn)時間周轉(zhuǎn)時間T與系與系統(tǒng)為它統(tǒng)為它提供服務(wù)的時間提供服務(wù)的時間TS之比，即之比，即W=T/TS 。n平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間niiTnT11niSiiTTnW11帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間周轉(zhuǎn)時間/服務(wù)時間服務(wù)時間3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n批處理系統(tǒng)的

12、目標批處理系統(tǒng)的目標n系統(tǒng)吞吐量高系統(tǒng)吞吐量高n吞吐量吞吐量指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)n作業(yè)調(diào)度的方式和算法對吞吐量的大小有較作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響大影響n處理機利用率高處理機利用率高n各類資源的平衡利用各類資源的平衡利用n使內(nèi)存、外存和使內(nèi)存、外存和I/OI/O設(shè)備的利用率高設(shè)備的利用率高3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n分時系統(tǒng)的目標分時系統(tǒng)的目標n響應(yīng)時間快響應(yīng)時間快n響應(yīng)時間響應(yīng)時間，從用戶通過鍵盤提交一個請求開，從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)中始，直至系統(tǒng)中首次首次產(chǎn)生產(chǎn)生響應(yīng)響應(yīng)為止的時間為止的時

13、間n交互式系統(tǒng)用周轉(zhuǎn)時間衡量不是最佳交互式系統(tǒng)用周轉(zhuǎn)時間衡量不是最佳n均衡性均衡性n系統(tǒng)響應(yīng)時間的快慢與用戶所請求服務(wù)的復(fù)系統(tǒng)響應(yīng)時間的快慢與用戶所請求服務(wù)的復(fù)雜性相適應(yīng)。雜性相適應(yīng)。3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n實時系統(tǒng)的目標實時系統(tǒng)的目標n截止時間保證截止時間保證n截止時間，某任務(wù)必須開始執(zhí)行的最遲時間或必須截止時間，某任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間完成的最遲時間n截止時間是實時系統(tǒng)中的重要指標截止時間是實時系統(tǒng)中的重要指標n可預(yù)測性可預(yù)測性n數(shù)據(jù)的到達或?qū)⒁幚砣蝿?wù)的要求是可預(yù)測的。數(shù)據(jù)的到達或?qū)⒁幚砣蝿?wù)的要求是可預(yù)測的。3.1.2 處理機調(diào)度算

14、法的目標處理機調(diào)度算法的目標n問題的本質(zhì)問題的本質(zhì)n周轉(zhuǎn)時間短周轉(zhuǎn)時間短n 響應(yīng)時間快響應(yīng)時間快n 截止時間保證截止時間保證批處理系統(tǒng)批處理系統(tǒng)分時系統(tǒng)分時系統(tǒng)實時系統(tǒng)實時系統(tǒng)等待時間短等待時間短優(yōu)先級優(yōu)先級3.1.2 處理機調(diào)度算法的目標處理機調(diào)度算法的目標n目標實現(xiàn)目標實現(xiàn)n等待時間短等待時間短n等待時間等待時間，在就緒隊列中等待所花的時間，在就緒隊列中等待所花的時間n調(diào)度算法并不影響進程運行和執(zhí)行調(diào)度算法并不影響進程運行和執(zhí)行I/O的時的時間量；只影響進程在就緒隊列中等待所花費間量；只影響進程在就緒隊列中等待所花費的時間的時間n優(yōu)先級準則優(yōu)先級準則n在在批處理批處理、實時實時和和分時系統(tǒng)

15、分時系統(tǒng)中都可以選擇優(yōu)中都可以選擇優(yōu)先級準則，以便讓緊急任務(wù)先處理先級準則，以便讓緊急任務(wù)先處理n有時還選擇搶占式調(diào)度方式有時還選擇搶占式調(diào)度方式3.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度n3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)n3.2.2 作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)n3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法n3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)n作業(yè)和作業(yè)步作業(yè)和作業(yè)步n作業(yè)作業(yè)(Job)。用戶在一次解題或一個事務(wù)處理過用戶在一次解題或一個事務(wù)處理過程中要求計

16、算機系統(tǒng)所做工作的集合，包括用程中要求計算機系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等。戶程序、所需的數(shù)據(jù)及命令等。n作業(yè)步作業(yè)步(Job Step)。通常，在作業(yè)運行期間，每。通常，在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果。聯(lián)的順序加工步驟才能得到結(jié)果。n例，一個典型的作業(yè)可分成三個作業(yè)步：例，一個典型的作業(yè)可分成三個作業(yè)步： “編譯編譯”作業(yè)步；作業(yè)步； “鏈接裝配鏈接裝配”作業(yè)步；作業(yè)步； “運行運行”作作業(yè)步。業(yè)步。3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)n作業(yè)控制塊（作業(yè)控制塊（J

17、ob control Block,JCB）n作業(yè)在系統(tǒng)中存在的標志；作業(yè)在系統(tǒng)中存在的標志；n包括作業(yè)標識、用戶名稱、用戶賬號、作業(yè)類包括作業(yè)標識、用戶名稱、用戶賬號、作業(yè)類型（型（CPU繁忙型、繁忙型、I/O繁忙型、批量型、終端繁忙型、批量型、終端型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級、作業(yè)運型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級、作業(yè)運行時間）、資源需求（預(yù)計運行時間、要求內(nèi)行時間）、資源需求（預(yù)計運行時間、要求內(nèi)存大?。?、資源使用情況。存大?。?、資源使用情況。3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)n作業(yè)運行的三個階段和三種狀態(tài)作業(yè)運行的三個階段和三種狀態(tài)n一個作業(yè)進入系統(tǒng)到運行結(jié)束，一般需

18、要經(jīng)歷一個作業(yè)進入系統(tǒng)到運行結(jié)束，一般需要經(jīng)歷收容、運行、完成三個階段，與之相對應(yīng)的是收容、運行、完成三個階段，與之相對應(yīng)的是作業(yè)的三種狀態(tài)作業(yè)的三種狀態(tài)n后備狀態(tài)后備狀態(tài)n運行狀態(tài)運行狀態(tài)n完成狀態(tài)完成狀態(tài)3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)n作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換狀態(tài)間轉(zhuǎn)換運行狀態(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è)3.2.2 作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)n作業(yè)調(diào)度的主要功能作業(yè)調(diào)度的主要功能n根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作

19、根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。分配必要的資源。n接納多少個作業(yè)接納多少個作業(yè)n 即允許多少個作業(yè)同時在內(nèi)存中運行，取決于多道程即允許多少個作業(yè)同時在內(nèi)存中運行，取決于多道程序度（序度（Degree of Multiprogramming）n作業(yè)太多作業(yè)太多 服務(wù)質(zhì)量下降服務(wù)質(zhì)量下降n作業(yè)太少作業(yè)太少 資源利用率低資源利用率低3.2.2 作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)n接納哪些

20、作業(yè)接納哪些作業(yè) n取決于作業(yè)調(diào)度算法取決于作業(yè)調(diào)度算法n先來先服務(wù)先來先服務(wù)n短作業(yè)優(yōu)先短作業(yè)優(yōu)先n作業(yè)優(yōu)先級調(diào)度作業(yè)優(yōu)先級調(diào)度n響應(yīng)比調(diào)度響應(yīng)比調(diào)度：即允許多少個作業(yè)同時在內(nèi)存中運行。：即允許多少個作業(yè)同時在內(nèi)存中運行。：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。止的這段時間間隔。：是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。：是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法n先來先服務(wù)先來先服務(wù)(FCFS)/先進先出先進先出(FIFO)調(diào)度算法調(diào)度算法n按照作業(yè)按照作業(yè)/進程進入系統(tǒng)的進程進入系

21、統(tǒng)的先后次序先后次序進行調(diào)度，進行調(diào)度，先進入系統(tǒng)者先調(diào)度；即啟動等待時間最長的先進入系統(tǒng)者先調(diào)度；即啟動等待時間最長的作業(yè)作業(yè)/進程進程n最簡單的調(diào)度算法，既可用于最簡單的調(diào)度算法，既可用于作業(yè)調(diào)度作業(yè)調(diào)度，也可，也可用于用于進程調(diào)度進程調(diào)度3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法進程名到達時間 服務(wù)時間 開始時間 完成時間 周轉(zhuǎn)時間帶權(quá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 E0

22、5101518t3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法n先來先服務(wù)（先進先出）先來先服務(wù)（先進先出）n優(yōu)缺點優(yōu)缺點n比較有利于比較有利于長作業(yè)（進程），長作業(yè)（進程），而不利于短而不利于短作作業(yè)（進程）業(yè)（進程）n 有利于有利于CPU繁忙型作業(yè)繁忙型作業(yè)（進程）（進程） ，而不利，而不利于于I/O繁忙型作業(yè)繁忙型作業(yè)（進程）（進程）n 用于用于批處理系統(tǒng)批處理系統(tǒng)，不適于，不適于分時系統(tǒng)分時系統(tǒng)3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法n先來先服務(wù)（先進先出）先來先服務(wù)（先進先出）n等待時間：等待時間：J1 = 0; J2 =0; J3 = 10

23、0；J4=100n平均等待時間：平均等待時間：(0 + 0 + 100+100)/4 = 50n平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(1+100+101+200)/4=100.5n平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：(1+1+101+2)/4=26.25作業(yè)作業(yè)到達到達時間時間服務(wù)服務(wù)時間時間開始時開始時間間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間J10 1J21100J31 1J42100011101101102102202 1 1100 1101 101200 23.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法n先來先服務(wù)（先進先出）先來先服務(wù)（先進先出）n等待時間

24、：等待時間：J1 = 0; J2 = 1; J3 = 0；J4=100n平均等待時間：平均等待時間：(0 + 1 + 0+100) / 4 = 25.25n平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(1 + 1 + 101 + 200）/4=75.75n平均帶權(quán)周轉(zhuǎn)時間：（平均帶權(quán)周轉(zhuǎn)時間：（1+1+1.01+2）/4=1.2525作業(yè)作業(yè)到達到達時間時間服務(wù)服務(wù)時間時間開始時開始時間間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間J101J311J21100J421000112 2102102202 1 1 1 1101 1.01200 23.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)

25、優(yōu)先算法n短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)Fn按按運行時間長短運行時間長短進行調(diào)度，即先啟動要求運行時進行調(diào)度，即先啟動要求運行時間最短的作業(yè)（進程）間最短的作業(yè)（進程）n短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)(SJF)的調(diào)度算法：從后備隊列中選擇的調(diào)度算法：從后備隊列中選擇一個或若干個一個或若干個估計運行時間估計運行時間最短的作業(yè)，調(diào)入內(nèi)最短的作業(yè)，調(diào)入內(nèi)存運行；存運行；n短進程優(yōu)先短進程優(yōu)先(SPF)(SPF)調(diào)度算法：從就緒隊列中選出一調(diào)度算法：從就緒隊列中選出一估計運行時間估計運行時間最短的進程，將處理機分配給它，最短的進程，將處理機分配給它，使它

26、立即使它立即執(zhí)行并一直執(zhí)行到完成執(zhí)行并一直執(zhí)行到完成，或，或發(fā)生某事件發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。而被阻塞放棄處理機時，再重新調(diào)度。3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法作業(yè)名到達時間 服務(wù)時間 開始時間 完成時間 周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均04A13B25C32D44E0441短作業(yè)短作業(yè)/短進程優(yōu)先（短進程優(yōu)先（SJF/SPF）：）：4631.56982.6791392.251318163.282.1A A A AB B BC C C C CD DE E E E05101518t3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法nSJ(

27、P)F調(diào)度算法的缺點調(diào)度算法的缺點n對對長作業(yè)不利長作業(yè)不利。嚴重的是，由于調(diào)度程序總是。嚴重的是，由于調(diào)度程序總是優(yōu)先調(diào)度短作業(yè)優(yōu)先調(diào)度短作業(yè)(進程進程)，將導(dǎo)致長作業(yè)，將導(dǎo)致長作業(yè)(進程進程)長長期不被調(diào)度期不被調(diào)度饑餓饑餓n不能保證不能保證緊迫性緊迫性作業(yè)作業(yè)(進程進程)會被會被及時處理；及時處理；n不一定能真正做到短作業(yè)優(yōu)先調(diào)度。由于作業(yè)不一定能真正做到短作業(yè)優(yōu)先調(diào)度。由于作業(yè)(進程進程)的長短只是根據(jù)的長短只是根據(jù)用戶用戶所提供的所提供的估計執(zhí)行估計執(zhí)行時間時間而定的，而用戶又可能會而定的，而用戶又可能會有意或無意有意或無意地地縮縮短短其作業(yè)的估計其作業(yè)的估計運行時間運行時間。n優(yōu)先

28、級調(diào)度算法優(yōu)先級調(diào)度算法n對于對于先來先服務(wù)先來先服務(wù)算法，作業(yè)的等待時間就是作算法，作業(yè)的等待時間就是作業(yè)的優(yōu)先級，業(yè)的優(yōu)先級，等待時間越長等待時間越長，優(yōu)先級越高。，優(yōu)先級越高。n對于對于短作業(yè)優(yōu)先短作業(yè)優(yōu)先算法，作業(yè)的長短就是作業(yè)的算法，作業(yè)的長短就是作業(yè)的優(yōu)先級，作業(yè)所優(yōu)先級，作業(yè)所需時間越短需時間越短，其優(yōu)先級越高。，其優(yōu)先級越高。n在優(yōu)先級算法，根據(jù)作業(yè)的緊迫程度，由外部在優(yōu)先級算法，根據(jù)作業(yè)的緊迫程度，由外部給予作業(yè)不同的優(yōu)先級，然后根據(jù)優(yōu)先級調(diào)度給予作業(yè)不同的優(yōu)先級，然后根據(jù)優(yōu)先級調(diào)度3.2.4 優(yōu)先級和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級和高響應(yīng)比優(yōu)先調(diào)度算法n高響應(yīng)比優(yōu)先調(diào)度算法（高

29、響應(yīng)比優(yōu)先調(diào)度算法（HRRN）nFCFS和和SJF的結(jié)合，克服了兩種算法的缺點的結(jié)合，克服了兩種算法的缺點n調(diào)度策略調(diào)度策略：響應(yīng)比：響應(yīng)比最高的作業(yè)優(yōu)先啟動最高的作業(yè)優(yōu)先啟動n因因等待時間等待時間+服務(wù)時間服務(wù)時間=該作業(yè)的該作業(yè)的響應(yīng)時間響應(yīng)時間，故，故該優(yōu)先級又相當(dāng)于該優(yōu)先級又相當(dāng)于響應(yīng)比響應(yīng)比RP。據(jù)此，又可表示。據(jù)此，又可表示為為3.2.4 優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法優(yōu)先級優(yōu)先級= 等待時間等待時間+要求服務(wù)時間要求服務(wù)時間 要求服務(wù)時間要求服務(wù)時間Rp= 等待時間等待時間+要求服務(wù)時間要求服務(wù)時間 要求服務(wù)時間要求服務(wù)時間 響應(yīng)時間響應(yīng)時間要求服務(wù)時間

30、要求服務(wù)時間= 3.2.4 優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法n對對HRRN的小結(jié)的小結(jié)n等待時間相同等待時間相同的作業(yè)，則的作業(yè)，則要求服務(wù)的時間愈短要求服務(wù)的時間愈短，其其優(yōu)先級愈高優(yōu)先級愈高，n要求服務(wù)的時間相同要求服務(wù)的時間相同的作業(yè)，則的作業(yè)，則等待時間愈長等待時間愈長，其其優(yōu)先級愈高優(yōu)先級愈高，n長作業(yè)，優(yōu)先級長作業(yè)，優(yōu)先級隨等待時間的增加隨等待時間的增加而提高，其而提高，其等待時間足夠長時，其優(yōu)先級便可升到很高，等待時間足夠長時，其優(yōu)先級便可升到很高， 從而也可獲得處理機，從而也可獲得處理機，n是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)是一種折衷，既照顧了短作

31、業(yè)，又考慮了作業(yè)到達的先后次序，又不會使長作業(yè)長期得不到到達的先后次序，又不會使長作業(yè)長期得不到服務(wù)。服務(wù)。缺點：要進行響應(yīng)比計算，增加了系統(tǒng)開銷缺點：要進行響應(yīng)比計算，增加了系統(tǒng)開銷對短作業(yè)有利對短作業(yè)有利先來先服務(wù)先來先服務(wù)對長作業(yè)有利對長作業(yè)有利優(yōu)先級優(yōu)先級= 等待時間等待時間+要求服務(wù)時間要求服務(wù)時間 要求服務(wù)時間要求服務(wù)時間 響應(yīng)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間= 優(yōu)先級優(yōu)先級= 等待時間等待時間+服務(wù)時間服務(wù)時間 服務(wù)時間服務(wù)時間當(dāng)前時間當(dāng)前時間-到達時間到達時間+服務(wù)時間服務(wù)時間 服務(wù)時間服務(wù)時間= 作業(yè)作業(yè)名名到達到達時間時間服務(wù)服務(wù)時間時間響應(yīng)比響應(yīng)比開始開始時間時間完成

32、完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均04A13B25C32D44E04411418143.54762914122.479638.42.38高響應(yīng)比優(yōu)先，非高響應(yīng)比優(yōu)先，非搶占式搶占式21.41.51231.752.42.253.53.2.4 優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法作業(yè)作業(yè)到達到達時間時間要求服務(wù)要求服務(wù)時間時間開始執(zhí)行開始執(zhí)行時間時間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間J18.0 2.0J28.6 0.6J38.8 0.2J49.0 0.5平均平均8.08.69.09.69.210.111.39.63.3 1.651.0

33、 1.670.4 2.01.1 2.2/9.2/8.81.45 1.88/10.1高響應(yīng)比優(yōu)先，高響應(yīng)比優(yōu)先，搶占式搶占式3.2.4 優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法優(yōu)先級和高優(yōu)先比優(yōu)先調(diào)度算法3.3 進程調(diào)度進程調(diào)度n3.3.1 進程調(diào)度的任務(wù)、機制和方式進程調(diào)度的任務(wù)、機制和方式n3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法n3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法n3.3.4 多隊列調(diào)度算法多隊列調(diào)度算法n3.3.5 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法n3.3.6 基于公平原則的調(diào)度算法基于公平原則的調(diào)度算法3.3.1 進程調(diào)度的任務(wù)、機制和方式進程調(diào)度的任務(wù)、機制和方式n進程調(diào)度的任務(wù)進程調(diào)

34、度的任務(wù)n保存處理機的現(xiàn)場信息保存處理機的現(xiàn)場信息。將正在運行進程的上。將正在運行進程的上下文保存到下文保存到PCB及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。n按某種算法選取進程按某種算法選取進程?？刂?、協(xié)調(diào)進程對?？刂?、協(xié)調(diào)進程對CPU的競爭，即按一定的調(diào)度算法從就緒隊列中選的競爭，即按一定的調(diào)度算法從就緒隊列中選中一個進程。中一個進程。n把處理器分配給進程把處理器分配給進程。把。把CPU的使用權(quán)交給被的使用權(quán)交給被選中的進程，并裝入選中進程的上下文。選中的進程，并裝入選中進程的上下文。3.3.1 進程調(diào)度的任務(wù)、機制和方式進程調(diào)度的任務(wù)、機制和方式n進程調(diào)度機制進程調(diào)度機制 根據(jù)預(yù)定的算法，

35、根據(jù)預(yù)定的算法，將系統(tǒng)中所有的就緒進將系統(tǒng)中所有的就緒進程排成一個或多個隊列，程排成一個或多個隊列，以便調(diào)度程序能最快地以便調(diào)度程序能最快地找到它。找到它。分派程序把由進程調(diào)度程分派程序把由進程調(diào)度程序所選定的進程，從就緒序所選定的進程，從就緒隊列中取出該進程，然后隊列中取出該進程，然后進行上下文切換，將處理進行上下文切換，將處理機分配給它機分配給它 。 OS保存當(dāng)前進程的保存當(dāng)前進程的上下文，裝入分派程序的上下文，裝入分派程序的上下文；上下文； 將移出分派程序，將移出分派程序，把新選進程的把新選進程的CPU現(xiàn)場信現(xiàn)場信息裝入到處理機的各個相息裝入到處理機的各個相應(yīng)寄存器中。應(yīng)寄存器中。 3.

36、3.1 進程調(diào)度的任務(wù)、機制和方式進程調(diào)度的任務(wù)、機制和方式n進程調(diào)度方式進程調(diào)度方式n非搶占方式非搶占方式(Non-preemptive Mode)n搶占方式搶占方式(Preemptive Mode)3.3.1 進程調(diào)度的任務(wù)、機制和方式進程調(diào)度的任務(wù)、機制和方式n進程調(diào)度方式進程調(diào)度方式非搶占方式非搶占方式n進程正在處理機上執(zhí)行時，進程正在處理機上執(zhí)行時，新就緒新就緒的進程進入的進程進入就緒隊列，就緒隊列，該進程仍繼續(xù)該進程仍繼續(xù)執(zhí)行，直到其完成或執(zhí)行，直到其完成或發(fā)生某種事件而進入完成或阻塞狀態(tài)時，才轉(zhuǎn)發(fā)生某種事件而進入完成或阻塞狀態(tài)時，才轉(zhuǎn)讓處理機。讓處理機。n引起進程調(diào)度的因素引起進

37、程調(diào)度的因素n正在執(zhí)行的進程執(zhí)行完畢，正在執(zhí)行的進程執(zhí)行完畢， 或因發(fā)生某事或因發(fā)生某事件而不能再繼續(xù)執(zhí)行件而不能再繼續(xù)執(zhí)行n執(zhí)行中的進程因提出執(zhí)行中的進程因提出I/OI/O請求而暫停執(zhí)行；請求而暫停執(zhí)行；n在進程通信或同步過程中執(zhí)行了某種原語操在進程通信或同步過程中執(zhí)行了某種原語操作，如作，如waitwait、BlockBlock、WakeupWakeup原語原語優(yōu)點優(yōu)點：算法簡單，：算法簡單，系統(tǒng)開銷小系統(tǒng)開銷小缺點缺點：緊急任務(wù)不：緊急任務(wù)不能及時響應(yīng)；短進能及時響應(yīng)；短進程到達要等待長進程到達要等待長進程運行結(jié)束程運行結(jié)束n進程調(diào)度方式進程調(diào)度方式搶占方式搶占方式n進程正在處理機上執(zhí)行

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

39、，適用于分時系統(tǒng)進行調(diào)度，適用于分時系統(tǒng)優(yōu)點優(yōu)點：適于時間要：適于時間要求嚴格的實時系統(tǒng)求嚴格的實時系統(tǒng)缺點缺點：調(diào)度算法復(fù)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大雜，系統(tǒng)開銷大3.3.1 進程調(diào)度的任務(wù)、機制和方式進程調(diào)度的任務(wù)、機制和方式3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法n輪轉(zhuǎn)法的基本原理輪轉(zhuǎn)法的基本原理n系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把成一個隊列，每次調(diào)度時，把CPU分配給隊首分配給隊首進程，并令其執(zhí)行一個時間片進程，并令其執(zhí)行一個時間片n當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時時鐘中斷鐘

40、中斷請求，調(diào)度程序便停止該進程的執(zhí)行，請求，調(diào)度程序便停止該進程的執(zhí)行，并將其放就緒隊列尾；然后，再把處理機分配并將其放就緒隊列尾；然后，再把處理機分配給就緒隊列中新的隊首給就緒隊列中新的隊首n時間片的大小從幾時間片的大小從幾ms到幾百到幾百ms缺點：緊迫任務(wù)響應(yīng)慢。缺點：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時間片中采用：時間片+優(yōu)先級優(yōu)先級3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法n進程切換時間進程切換時間n任務(wù)在給定時間片內(nèi)任務(wù)在給定時間片內(nèi)已完成已完成，則將它標記為終，則將它標記為終止?fàn)顟B(tài)，立即激活調(diào)度程序進行調(diào)度；止?fàn)顟B(tài)，立即激活調(diào)度程序進行調(diào)度；n任務(wù)在時間片內(nèi)任務(wù)在時間片內(nèi)未完成未完成，計時

41、器中斷處理程序，計時器中斷處理程序被激活，則將進程進入就緒隊列末尾，啟動調(diào)被激活，則將進程進入就緒隊列末尾，啟動調(diào)度程序調(diào)度；度程序調(diào)度；3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法n時間片大小的確定時間片大小的確定n時間片選擇問題時間片選擇問題n固定時間片固定時間片n可變時間片可變時間片n與時間片大小有關(guān)的因素與時間片大小有關(guān)的因素n系統(tǒng)響應(yīng)時間系統(tǒng)響應(yīng)時間n就緒進程個數(shù)就緒進程個數(shù)nCPUCPU能力能力 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法進程名進程名到達時間到達時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均A B C D

42、E A B C D E A B C E A C E C05101518t04A03B05C02D04E01234912151718153.75124183.694.5174.2514.24.02若到達時間若到達時間為為0 0、1 1、2 2、3 3、4 4，又如，又如何？何？基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法進程名進程名到達時間到達時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均A B A C B D A E C B D A E C E C E C05101518t04A13B25C32D44E0135711101217

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

44、統(tǒng)要求不嚴的實時系統(tǒng)中中3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法n優(yōu)先級調(diào)度算法的類型優(yōu)先級調(diào)度算法的類型n搶占式搶占式n把處理機分配給優(yōu)先級最高的進程，在執(zhí)行期把處理機分配給優(yōu)先級最高的進程，在執(zhí)行期間，只要出現(xiàn)另一個優(yōu)先級更高的進程，則進間，只要出現(xiàn)另一個優(yōu)先級更高的進程，則進程調(diào)度程序就程調(diào)度程序就立即停止立即停止當(dāng)前進程的執(zhí)行，并將當(dāng)前進程的執(zhí)行，并將處理機分配給新到的優(yōu)先級最高的進程處理機分配給新到的優(yōu)先級最高的進程n只要只要系統(tǒng)中系統(tǒng)中出現(xiàn)出現(xiàn)一個新的就緒進程，一個新的就緒進程，就進行就進行優(yōu)優(yōu)先級先級比較比較n能更好地能更好地滿足緊迫作業(yè)滿足緊迫作業(yè)的要求，故而常用于要的要求，故

45、而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中高的批處理和分時系統(tǒng)中3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法n優(yōu)先級的類型優(yōu)先級的類型n靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級n靜態(tài)優(yōu)先級在創(chuàng)建進程時確定，且在進程的整靜態(tài)優(yōu)先級在創(chuàng)建進程時確定，且在進程的整個運行期間個運行期間保持不變保持不變。一般地，優(yōu)先級是利用。一般地，優(yōu)先級是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，某一范圍內(nèi)的一個整數(shù)來表示的，例如，0 0 7 7或或0 0 255255， 又把該整數(shù)稱為又把該整數(shù)稱為優(yōu)先數(shù)優(yōu)先數(shù)n確定進程靜態(tài)優(yōu)先級的依據(jù)確定進程靜態(tài)優(yōu)先級的依據(jù)n進程類型進

46、程類型: :系統(tǒng)進程，用戶進程系統(tǒng)進程，用戶進程n進程對資源的需求進程對資源的需求n用戶要求用戶要求問題：用戶將優(yōu)先級設(shè)的較高，對其他進程不利！問題：用戶將優(yōu)先級設(shè)的較高，對其他進程不利！ 短進程優(yōu)先對長進程不利！短進程優(yōu)先對長進程不利！3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法n動態(tài)優(yōu)先級動態(tài)優(yōu)先級n隨隨進程的推進進程的推進或隨其或隨其等待時間等待時間的增加而改變。的增加而改變。n例，在例，在就緒隊列中的進程就緒隊列中的進程，優(yōu)先級隨，優(yōu)先級隨等待時間的等待時間的增長增長，以某一速率提高；以某一速率提高；n相同優(yōu)先級初值相同優(yōu)先級初值的進程，則的進程，則最先進入最先進入就緒隊列就緒隊列的進程，

47、的進程，優(yōu)先優(yōu)先獲得處理機，即獲得處理機，即FCFS算法算法n各不相同各不相同的的優(yōu)先級初值優(yōu)先級初值的就緒進程，則的就緒進程，則優(yōu)先級優(yōu)先級初值低初值低的進程，在的進程，在等待了足夠的時間等待了足夠的時間后，其后，其優(yōu)優(yōu)先級便可能升為最高先級便可能升為最高，從而可以獲得處理機，從而可以獲得處理機n當(dāng)采用搶占式優(yōu)先級調(diào)度算法時，如果再當(dāng)采用搶占式優(yōu)先級調(diào)度算法時，如果再規(guī)定當(dāng)規(guī)定當(dāng)前進程前進程的優(yōu)先級的優(yōu)先級以某一速率下降以某一速率下降，則可防止一個，則可防止一個長作業(yè)長期地長作業(yè)長期地壟斷壟斷處理機。處理機。進程進程到達到達時間時間服務(wù)服務(wù)時間時間開始開始時間時間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間

48、時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間P10 7P21 5P32 3P43 2P54 4平均等待時間：平均等待時間：(14 + 5 + 0+2+7) / 5 = 5.6平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：(21 + 10 + 3 + 4 + 11）/5=9.8平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：(3+2+1+2+2.75）/5=2.15012557/7111115/152121 310 2 3 1 4 211 2.753.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法實例實例n搶占式搶占式短進程優(yōu)先短進程優(yōu)先SPF調(diào)度調(diào)度3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法實例實例進程進程名名到達到達時間時間服務(wù)服務(wù)時間時間靜態(tài)優(yōu)靜

49、態(tài)優(yōu)先級先級開始開始時間時間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均靜態(tài)優(yōu)先級，靜態(tài)優(yōu)先級，非搶占式非搶占式（1為最高優(yōu)先級）為最高優(yōu)先級）04A413B225C332D544E104414841811103.331116142.81618157.59.42.93考慮一下考慮一下?lián)屨际綋屨际?，情況如何？，情況如何？進程進程名名到達到達時間時間服務(wù)服務(wù)時間時間靜態(tài)優(yōu)靜態(tài)優(yōu)先級先級開始開始時間時間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均高優(yōu)先級優(yōu)先調(diào)度算法04A413B225C332D544E101616448411431813112.2161815

50、7.59.83.14靜態(tài)優(yōu)先級，靜態(tài)優(yōu)先級，搶占式搶占式（1為高優(yōu)先級）為高優(yōu)先級）A B B B E E E E C C C C C A A A D D05101518tB AA CDEA CD3.3.4 多隊列調(diào)度多隊列調(diào)度算法算法n單一就緒隊列單一就緒隊列多個就緒隊列多個就緒隊列n例，將就緒進程分別進入前臺和后臺就緒隊列例，將就緒進程分別進入前臺和后臺就緒隊列n前臺前臺就緒隊列是交互性作業(yè)的進程，通常采用時間就緒隊列是交互性作業(yè)的進程，通常采用時間片輪轉(zhuǎn)。片輪轉(zhuǎn)。n后臺后臺的就緒隊列是批處理作業(yè)的進程，通常采用優(yōu)的就緒隊列是批處理作業(yè)的進程，通常采用優(yōu)先級或短作業(yè)優(yōu)先算法。先級或短作業(yè)優(yōu)

51、先算法。n調(diào)度方式有兩種：調(diào)度方式有兩種：n優(yōu)先調(diào)度前臺，若前臺無可運行進程，才調(diào)度后臺。優(yōu)先調(diào)度前臺，若前臺無可運行進程，才調(diào)度后臺。n分配占用分配占用CPU的時間比例，如：前臺的時間比例，如：前臺80%，后臺，后臺20%3.3.5 多級反饋多級反饋(multileved feedback)隊列調(diào)度算法隊列調(diào)度算法n調(diào)度機制調(diào)度機制 n設(shè)置設(shè)置多個就緒隊列多個就緒隊列，各個隊列賦予，各個隊列賦予不同的優(yōu)先級不同的優(yōu)先級n第一個隊列的優(yōu)先級最高，第二個隊列次之，第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先級逐個降低其余各隊列的優(yōu)先級逐個降低n各個隊列中進程執(zhí)行各個隊列中進程執(zhí)行時間

52、片的大小也各不相同時間片的大小也各不相同，在在優(yōu)先級愈高優(yōu)先級愈高的隊列中，為每個進程所規(guī)定的的隊列中，為每個進程所規(guī)定的執(zhí)行執(zhí)行時間片就愈小時間片就愈小。例，。例，第二個第二個隊列的時間片隊列的時間片要要比第一個比第一個隊列的時間片隊列的時間片長一倍長一倍，第，第i i+1+1個個隊列的時間片要比第隊列的時間片要比第i i個隊列的時間片長一倍個隊列的時間片長一倍就緒隊列就緒隊列1 13.3.5 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法就緒隊列就緒隊列2 2就緒隊列就緒隊列3 3就緒隊列就緒隊列nS1S2S3至至CPU至至CPU至至CPU至至CPU( (時間片：時間片：S1 S2 S3) )v

53、調(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ā)生，則回到原來的就緒隊列回到原來的就緒隊列3.3.5 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法n多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法n注意注意n僅當(dāng)?shù)趦H當(dāng)?shù)?(i-1) 隊列均空時，才會調(diào)度第隊列均空時，才會調(diào)度第i隊列中的進隊列中的進程運行程

54、運行n第第i隊列隊列中某進程正在運行時，又有中某進程正在運行時，又有新新進程進入進程進入優(yōu)先優(yōu)先級較高級較高的隊列的隊列(第第1(i-1)中的任何一個隊列中的任何一個隊列)，則此時，則此時新進程將搶占新進程將搶占正在運行進程的處理機，調(diào)度程序把正在運行進程的處理機，調(diào)度程序把正在運行的進程正在運行的進程放回到第放回到第i隊列隊列的末尾的末尾n第第i隊列隊列中某進程正在運行時，該進程因等待事件發(fā)中某進程正在運行時，該進程因等待事件發(fā)生而進入阻塞隊列，等待事件發(fā)生后，調(diào)度程序把生而進入阻塞隊列，等待事件發(fā)生后，調(diào)度程序把進程進程放回到第放回到第i隊列隊列的末尾的末尾3.3.5 多級反饋隊列調(diào)度算法

55、多級反饋隊列調(diào)度算法n調(diào)度算法的性能調(diào)度算法的性能n終端型作業(yè)用戶終端型作業(yè)用戶n提交的作業(yè)多屬于提交的作業(yè)多屬于交互型交互型作業(yè)，通常作業(yè)，通常較小較小，系統(tǒng)只要能，系統(tǒng)只要能使這些作業(yè)在第一隊列所使這些作業(yè)在第一隊列所規(guī)定的時間片內(nèi)完成規(guī)定的時間片內(nèi)完成即可即可n短批處理作業(yè)用戶短批處理作業(yè)用戶n若在第若在第1隊列中執(zhí)行隊列中執(zhí)行一個時間片一個時間片即可完成，便可獲得與終即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時間端型作業(yè)一樣的響應(yīng)時間n如在第一個隊列中不能完成，只需在第如在第一個隊列中不能完成，只需在第2、3隊列中各執(zhí)隊列中各執(zhí)行一個時間片行一個時間片n長批處理作業(yè)用戶長批處理作業(yè)用戶n

56、長作業(yè)將依次在第長作業(yè)將依次在第1，2，3，n隊列中執(zhí)行，隊列中執(zhí)行，最終按輪最終按輪轉(zhuǎn)方式運行轉(zhuǎn)方式運行3.3.6 基于公平原則的調(diào)度算法基于公平原則的調(diào)度算法n保證調(diào)度算法保證調(diào)度算法n向用戶做出明確的性能保證向用戶做出明確的性能保證n易實現(xiàn)的算法：處理機分配的公平性易實現(xiàn)的算法：處理機分配的公平性n當(dāng)工作時已有當(dāng)工作時已有n個用戶登錄在系統(tǒng)，則將獲得個用戶登錄在系統(tǒng)，則將獲得CPU處理能力的處理能力的1/n。類似的，在一個有。類似的，在一個有n個進程運行的個進程運行的用戶系統(tǒng)中，每個進程將獲得用戶系統(tǒng)中，每個進程將獲得CPU處理能力的處理能力的1/n。n實現(xiàn)方法實現(xiàn)方法nOS應(yīng)記錄及計算

57、應(yīng)記錄及計算,各個進程在一定時間段內(nèi)各個進程在一定時間段內(nèi),已經(jīng)使已經(jīng)使用的用的CPU時間和應(yīng)該得到的時間和應(yīng)該得到的CPU時間時間,二者之比小者二者之比小者優(yōu)先級高優(yōu)先級高3.3.6 基于公平原則的調(diào)度算法基于公平原則的調(diào)度算法n公平分享調(diào)度算法公平分享調(diào)度算法n每個用戶分配到每個用戶分配到CPUCPU時間的一部分，而調(diào)度程時間的一部分，而調(diào)度程序以一種強制的方式選擇進程。這樣，如果兩序以一種強制的方式選擇進程。這樣，如果兩個用戶都得到獲得個用戶都得到獲得50% CPU50% CPU時間的保證，那么時間的保證，那么無論一個用戶有多少進程存在，每個用戶都會無論一個用戶有多少進程存在，每個用戶都

58、會得到應(yīng)有的得到應(yīng)有的CPUCPU份額。份額。n例，用戶例，用戶1 1有有4 4個進程個進程A A、B B、C C和和D D，而用戶，而用戶2 2只只有有1 1個進程個進程E E。如果采用輪轉(zhuǎn)調(diào)度，一個滿足所。如果采用輪轉(zhuǎn)調(diào)度，一個滿足所有限制條件的可能序列是：有限制條件的可能序列是： A E B E C E D A E B E C E D E A E B E C E D E E A E B E C E D E 3.3.6 線程調(diào)度線程調(diào)度nOS只調(diào)度核心級線程；只調(diào)度核心級線程；n用戶級線程必須映射到內(nèi)核線程才能運行；用戶級線程必須映射到內(nèi)核線程才能運行；n本地調(diào)度（進程競爭范圍，本地調(diào)度（

59、進程競爭范圍，PCS）n線程庫決定如何將哪個線程調(diào)度到有效的線程庫決定如何將哪個線程調(diào)度到有效的LWP上。上。nM:M，M:On全局調(diào)度（系統(tǒng)競爭范圍，全局調(diào)度（系統(tǒng)競爭范圍，SCS）n內(nèi)核決定調(diào)度那一個線程到內(nèi)核決定調(diào)度那一個線程到CPU上運行。上運行。nO:O僅采用僅采用SCSnPCS根據(jù)優(yōu)先級完成，由程序員設(shè)置。根據(jù)優(yōu)先級完成，由程序員設(shè)置。線程調(diào)度線程調(diào)度API#include #include #define NUM_THREADS 5int main(int argc, char *argv ) int i, scope;pthread_t tidNUM_THREADS;pthre

60、ad_attr_t attr;/* get the default attributes */pthread_attr_init(&attr);/* set the scheduling algorithm to PROCESS or SYSTEM */pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);/* set the scheduling policy - FIFO, RT, or OTHER */pthread_attr_setschedpolicy(&attr, SCHED_OTHER);線程調(diào)度線程調(diào)度API/* create the thr