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

1、第三章處理機調(diào)度與死鎖v為提高處理機利用率、改善系統(tǒng)性能（吞吐量、響應(yīng)時間）需對處理機進行合理分配調(diào)度v處理機調(diào)度的目的：分配處理機3.1處理機調(diào)度的層次處理機調(diào)度的層次高級、中級和低級調(diào)度高級、中級和低級調(diào)度 調(diào)度分三級調(diào)度分三級1. 高級調(diào)度高級調(diào)度 也稱為作業(yè)調(diào)度也稱為作業(yè)調(diào)度作業(yè)：用戶在一次執(zhí)行過程中或一個事務(wù)處理中要求計算機系統(tǒng)所做工作的集合作業(yè)調(diào)度：將外存上后備隊列的作業(yè)調(diào)入內(nèi)存、創(chuàng)建進程并分配資源、插入就緒隊列接納多少個作業(yè)接納哪些作業(yè)分時系統(tǒng)、實時系統(tǒng)中不需要作業(yè)調(diào)度，作業(yè)直接送入內(nèi)存2. 低級調(diào)度低級調(diào)度稱為進程稱為進程調(diào)度調(diào)度選擇選擇就緒隊列中某個進程就緒隊列中某個進程獲得

2、處理機獲得處理機 調(diào)度方式1) 非搶占方式：不允許其它進程搶占已經(jīng)分配出去的處理機。實時系統(tǒng)中，不宜采用這種調(diào)度方式。2)搶占方式：允許調(diào)度程序?qū)⒁逊峙涑鋈サ奶幚頇C重新分配給另一進程。3. 中級調(diào)度中級調(diào)度主要目的：提高內(nèi)存利用率和系統(tǒng)吞吐量。 實現(xiàn)方式：對換暫時不能運行的進程調(diào)至外存上的掛起隊列去等待。當(dāng)進程重新具備運行條件時，中級調(diào)度將掛起隊列中某個進程重新調(diào)入內(nèi)存，掛在就緒隊列上等待進程調(diào)度。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型1. 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型就 緒 隊 列阻 塞 隊 列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)

3、時間片完這種調(diào)度適合于哪種系統(tǒng)？2. 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型就 緒 隊 列進程調(diào)度CPU進程完成等待事件 1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件 2事件2出現(xiàn)等待事件 n事件n出現(xiàn)后 備 隊 列這種調(diào)度適合于哪種系統(tǒng)？3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 就緒隊列進程調(diào)度CPU就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)高高低低中中調(diào)度準則 1. 面向用戶的準則面向用戶的準則 (1) 周轉(zhuǎn)時間短。周轉(zhuǎn)時間短。周轉(zhuǎn)時間周轉(zhuǎn)時間T：從作業(yè)被提交給系統(tǒng)，

4、到作業(yè)完成為止的時間間隔。由由4個部分組成：在后備隊列個部分組成：在后備隊列等待的時間、進程在就緒隊列中等待的時間、在 CPU中執(zhí)行的時間、I/O操作完成的時間。平均周轉(zhuǎn)時間： 11niiTTn平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間： W=T/TS（ TS系統(tǒng)服務(wù)時間即CPU執(zhí)行時間）niSiiTTnW11(2) 響應(yīng)時間快。（評價分時系統(tǒng)，輸入、處理、返回）響應(yīng)時間快。（評價分時系統(tǒng)，輸入、處理、返回） (3) 截止時間的保證。（評價實時系統(tǒng)）截止時間的保證。（評價實時系統(tǒng)） (4) 優(yōu)先權(quán)準則優(yōu)先權(quán)準則。 2. 面向系統(tǒng)的準則面向系統(tǒng)的準則(1)系統(tǒng)吞吐量高q吞吐量是指單位時間內(nèi)完成的作業(yè)數(shù)(2)

5、處理機利用率好(3)各類資源的平衡利用 -各類資源處于忙碌狀態(tài)3.3 調(diào)調(diào) 度度 算算 法法 調(diào)度算法調(diào)度算法 ：資源分配方法。不同的系統(tǒng)，通常采用不同的調(diào)度算法。不同的系統(tǒng)，通常采用不同的調(diào)度算法。1. 先來先服務(wù)調(diào)度算法（既可用于作業(yè)調(diào)度又可用于進程調(diào)度）先來先服務(wù)調(diào)度算法（既可用于作業(yè)調(diào)度又可用于進程調(diào)度） 2. 短作業(yè)短作業(yè)(進程進程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 3. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法(FPF)v 靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)：創(chuàng)建進程時確定且在進程的整個運行期間保持不變。優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示。v 動態(tài)優(yōu)先權(quán)：可以改變。動態(tài)優(yōu)先權(quán)：可以改變。高響應(yīng)比優(yōu)

6、先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法v 優(yōu)先權(quán)優(yōu)先權(quán)=(等待時間等待時間+要求服務(wù)時間要求服務(wù)時間)/要求服務(wù)時間要求服務(wù)時間 響應(yīng)比響應(yīng)比 Rp=響應(yīng)時間響應(yīng)時間/要求服務(wù)時間要求服務(wù)時間例：在一個批處理單道系統(tǒng)中，采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法?，F(xiàn)有3個作業(yè)，進入系統(tǒng)的時間和需要計算的時間如下表所示：（1）求出每個作業(yè)的開始時間、完成時間及周轉(zhuǎn)時間并填入表中。（2）計算三個作業(yè)的平均周轉(zhuǎn)時間為多少？ （1）平均周轉(zhuǎn)時間：（60+120+70）分鐘/3=83.33分鐘（2）帶權(quán)平均周轉(zhuǎn)時間：？作作業(yè)業(yè)進進入入時時間間估估計計運運行行時時間間（分分鐘鐘）開開始始時時間間結(jié)結(jié)束束時時間間周周轉(zhuǎn)轉(zhuǎn)時時

7、間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時時間間JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 T = 112.5作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 W = 4.97545019.9分別采用FCFS、SJF、FPF求出每個作業(yè)的開始時間、完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間并填入表中。計算系統(tǒng)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。先來先服務(wù)調(diào)度算法計算結(jié)果先來先服務(wù)調(diào)度算法計算結(jié)果作作業(yè)業(yè)進進入入時時間間估估計計運運行行

8、時時間間（分分鐘鐘）開開始始時時間間結(jié)結(jié)束束時時間間周周轉(zhuǎn)轉(zhuǎn)時時間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時時間間JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 T = 112.5作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 W = 4.97545019.9最短作業(yè)優(yōu)先作業(yè)算法計算結(jié)果最短作業(yè)優(yōu)先作業(yè)算法計算結(jié)果作作業(yè)業(yè)進進入入時時間間估估計計運運行行時時間間（分分鐘鐘）開開始始時時間間結(jié)結(jié)束束時時間間周周轉(zhuǎn)轉(zhuǎn)時時間間（分分

9、鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時時間間JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502010：1010：30402作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 T = 95作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 W = 3.2538013最高響應(yīng)比優(yōu)先作業(yè)算法計算結(jié)果最高響應(yīng)比優(yōu)先作業(yè)算法計算結(jié)果 作作業(yè)業(yè) 進進入入時時間間 估估計計運運行行時時間間 （分分鐘鐘） 開開始始時時間間 結(jié)結(jié)束束時時間間 周周轉(zhuǎn)轉(zhuǎn)時時間間 （分分鐘鐘） 帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時時間間 JOB1 8：00 120 8：00 10：

10、00 120 1 JOB2 8：50 50 10：10 11：00 130 2.6 JOB3 9：00 10 10：00 10：10 70 7 JOB4 9：50 20 11：00 11：20 90 4.5 作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 T =102.5 作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時時間間 W = 3.775 410 15.1 4.基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 基本原理：系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。確定時間片大小考慮的因素系統(tǒng)對響應(yīng)時間的要求：響應(yīng)時間=時間片*進程數(shù)。就緒隊列中的

11、進程數(shù)目：時間片與就緒進程數(shù)成反比。系統(tǒng)處理能力：人所能承受的響應(yīng)時間一定，系統(tǒng)速度快則時間片可增長。q=1q=4ABCDEBCDEABCEACEABCDEAA1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17時間片大小對進程執(zhí)行時間的影響5. 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法：不需事先知道各進程的執(zhí)行時間，且還可以滿足各種類型進程需要優(yōu)優(yōu)先先權(quán)權(quán)降降低低時時間間片片增增大大就緒隊列1就緒隊列2就緒隊列3就緒隊列nCPUCPUCPUCPUS1S2S3Sn(時間片： S1S2 S3Sn)3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件死鎖死鎖:多個

12、進程在運行過程中因爭奪資源而造成的一種僵局，多個進程在運行過程中因爭奪資源而造成的一種僵局，若無外力作用，進程都將無法再向前推進。若無外力作用，進程都將無法再向前推進。 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 非剝奪資源：磁帶機、打印機R1R2P1P2資源追逐，各不相讓資源追逐，各不相讓占有并等待占有并等待臨時性資源：由一個進程產(chǎn)生，被另一個進程使用后便無用的資源。進程進程P1進程進程P2消息S3消息S1進程進程P3消息消息S2P1：Release(S1);Request(S3)P2：Release(S2);Request(S1)P3：Release(S3);Request(S2)不可能發(fā)生死鎖P1：R

13、equest(S3);Release(S1)P2：Request(S1);Release(S2)P3：Request(S2);Release(S3)可能發(fā)生死鎖產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 (1)互斥條件互斥條件 (2) 請求和保持條件（占有并等待）請求和保持條件（占有并等待）(3) 不剝奪條件不剝奪條件 (4) 環(huán)路等待條件環(huán)路等待條件 1.必要條件（缺一不可）必要條件（缺一不可）2.必須同時成立或存在必須同時成立或存在處理死鎖的基本方法處理死鎖的基本方法(1) 預(yù)防死鎖預(yù)防死鎖 (2) 避免死鎖避免死鎖(3) 檢測死鎖檢測死鎖 (4) 解除死鎖解除死鎖 最好是預(yù)防，逐最好是預(yù)防，逐

14、個降格個降格主動措施主動措施（被動措施）（被動措施）（挽救措施）（挽救措施）3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 預(yù)防死鎖預(yù)防死鎖 1. 摒棄摒棄“請求和保持請求和保持”條件條件 2. 摒棄摒棄“不剝奪不剝奪”條件條件 3. 摒棄摒棄“環(huán)路等待環(huán)路等待”條件條件 由于互斥條件由于互斥條件不可破壞不可破壞,至少至少破壞破壞1/4變成要變成要破壞破壞1/3.形成死鎖形成死鎖,要要求求4個條件同個條件同時成立時成立, 至少至少破壞其中破壞其中1個個就行就行!系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) v安全狀態(tài)：系統(tǒng)能按某種順序如P1,P2, Pn（ 稱P1,P2, Pn為安全序列 ），為每個進程分配資源，使每個進程

15、都能順利完成。v不安全狀態(tài)：不存在安全序列的狀態(tài)。v避免死鎖的實質(zhì)：如何使系統(tǒng)不進入不安全狀態(tài)。安全狀態(tài)例安全狀態(tài)例假定系統(tǒng)中有三個進程P1、 P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示： 進 程 最 大 需 求 已 分 配 可 用 P1P2P310495223安全序列？安全序列？p1p2p3 ， p2p3p1 ，p2p1 p3利用銀行家算法避免死鎖利用銀行家算法避免死鎖 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 可利用資源向量Availabl

16、e：一個含有m個元素的數(shù)組，其中，每一個元素代表一類可用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其值隨資源的分配和回收而動態(tài)地改變。 最大需求矩陣Max：是一個nm的矩陣，定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。 分配矩陣Allocation：是一個nm的矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。 需求矩陣Need：是一個nm的矩陣，表示每個進程尚需的該類資源數(shù)。v上述三個矩陣的關(guān)系： Need i, j = Max i , j Allocation i , j 其中： Need i, j =k表示進程i還需要 Rj 類資源 k 個。 Max

17、i , j =k 表示進程i 需要 Rj 類資源的最大數(shù)目為 k 。 Allocation i , j =k 表示進程i 當(dāng)前已分得 Rj類資源的數(shù)目為 k 。 Availablej=k表示系統(tǒng)中現(xiàn)有Rj類資源k個。銀行家算法：Requesti j = k進程尚需要的資源Requesti = Needi1出 錯N等 待NRequesti = AvailableY是否有足夠的是否有足夠的可可利用資源利用資源2系統(tǒng)把要求的資源試探分配給進程PiAvailable := Available - Requesti;Allocation := Allocationi + Requesti;Needi :

18、=Needi - RequestiY3系統(tǒng)執(zhí)行安全性算法4分配資源給進程Y試探分配作廢Nv安全性算法：v 向量 Work 表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，其初始化為當(dāng)前可用的資源數(shù)。v 向量 Finish 是布爾型數(shù)組，表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。初始化為 false。v 安全性檢查的步驟： (1) Work:=Available; Finish:=false; (2) 尋找滿足條件的i： a. Finishi=false; b. NeediWork; 如果不存在，則轉(zhuǎn)(4) (3) Work:=Work+Allocationi; Finishi:=true; 轉(zhuǎn)(2) (4) 若對所有i，F(xiàn)inishi=true，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個進程假定系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源和三類資源A, B, C，各種資源的數(shù)量分別為，各種資源的數(shù)量分別為10、5、7。 T0時刻的資源分配表時刻的資源分配表 T0時刻的安全性：時刻的安全性： T0時刻的安全序列時刻的安全序列 P1請求資源：請求資源：P1發(fā)出請求向量發(fā)