第三章處理機(jī)調(diào)度與死鎖為提高處理機(jī)利用率、改善系統(tǒng)性能（吞吐量、響應(yīng)時間）需對處理機(jī)進(jìn)行合理分配調(diào)度處理機(jī)調(diào)度的目的：分配處理機(jī)3.1處理機(jī)調(diào)度的層次高級、中級和低級調(diào)度調(diào)度分三級1.高級調(diào)度

也稱為作業(yè)調(diào)度作業(yè)：用戶在一次執(zhí)行過程中或一個事務(wù)處理中要求計算機(jī)系統(tǒng)所做工作的集合作業(yè)調(diào)度：將外存上后備隊列的作業(yè)調(diào)入內(nèi)存、創(chuàng)建進(jìn)程并分配資源、插入就緒隊列接納多少個作業(yè)接納哪些作業(yè)分時系統(tǒng)、實(shí)時系統(tǒng)中不需要作業(yè)調(diào)度，作業(yè)直接送入內(nèi)存2.低級調(diào)度稱為進(jìn)程調(diào)度選擇就緒隊列中某個進(jìn)程獲得處理機(jī)

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

高低中調(diào)度準(zhǔn)則

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

---各類資源處于忙碌狀態(tài)3.3調(diào)度算法

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

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

基本原理：系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。確定時間片大小考慮的因素@系統(tǒng)對響應(yīng)時間的要求：響應(yīng)時間=時間片*進(jìn)程數(shù)。@就緒隊列中的進(jìn)程數(shù)目：時間片與就緒進(jìn)程數(shù)成反比。@系統(tǒng)處理能力：人所能承受的響應(yīng)時間一定，系統(tǒng)速度快則時間片可增長。q=1q=4ABCDEBCDEABCEACEABCDEAA1234567891011121314151617時間片大小對進(jìn)程執(zhí)行時間的影響5.多級反饋隊列調(diào)度算法：不需事先知道各進(jìn)程的執(zhí)行時間，且還可以滿足各種類型進(jìn)程需要優(yōu)先權(quán)降低時間片增大就緒隊列1就緒隊列2就緒隊列3就緒隊列nCPUCPUCPUCPUS1S2S3Sn(時間片：S1<S2<S3<Sn)3.5產(chǎn)生死鎖的原因和必要條件死鎖:多個進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，若無外力作用，進(jìn)程都將無法再向前推進(jìn)。

產(chǎn)生死鎖的原因非剝奪資源：磁帶機(jī)、打印機(jī)資源追逐，各不相讓占有并等待臨時性資源：由一個進(jìn)程產(chǎn)生，被另一個進(jìn)程使用后便無用的資源。進(jìn)程P1進(jìn)程P2消息S3消息S1進(jìn)程P3消息S2P1：Release(S1);Request(S3)P2：Release(S2);Request(S1)P3：Release(S3);Request(S2)不可能發(fā)生死鎖P1：Request(S3);Release(S1)P2：Request(S1);Release(S2)P3：Request(S2);Release(S3)可能發(fā)生死鎖產(chǎn)生死鎖的必要條件

互斥條件(2)請求和保持條件（占有并等待）(3)不剝奪條件(4)環(huán)路等待條件1.必要條件（缺一不可）2.必須同時成立或存在處理死鎖的基本方法

預(yù)防死鎖(2)避免死鎖(3)檢測死鎖(4)解除死鎖

最好是預(yù)防，逐個降格主動措施（被動措施）（挽救措施）3.6預(yù)防死鎖的方法

預(yù)防死鎖

摒棄“請求和保持”條件2.

摒棄“不剝奪”條件3.摒棄“環(huán)路等待”條件

由于互斥條件不可破壞,至少破壞1/4變成要破壞1/3.形成死鎖,要求4個條件同時成立,至少破壞其中1個就行!系統(tǒng)安全狀態(tài)

安全狀態(tài)：系統(tǒng)能按某種順序如﹤P1,P2,…Pn﹥（稱﹤P1,P2,…Pn﹥?yōu)榘踩蛄校?，為每個進(jìn)程分配資源，使每個進(jìn)程都能順利完成。不安全狀態(tài)：不存在安全序列的狀態(tài)。避免死鎖的實(shí)質(zhì)：如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。安全狀態(tài)例假定系統(tǒng)中有三個進(jìn)程P1、P2和P3，共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī)，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機(jī)，尚有3臺空閑未分配，如下表所示：進(jìn)程最大需求已分配可用P1P2P310495223安全序列？p1→p2→p3

，p2→p3→p1

，p2→p1→p3利用銀行家算法避免死鎖

銀行家算法中的數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available：一個含有m個元素的數(shù)組，其中，每一個元素代表一類可用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其值隨資源的分配和回收而動態(tài)地改變。最大需求矩陣Max：是一個n×m的矩陣，定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。分配矩陣Allocation：是一個n×m的矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。需求矩陣Need：是一個n×m的矩陣，表示每個進(jìn)程尚需的該類資源數(shù)。上述三個矩陣的關(guān)系：Need[i,j]=Max[i,j]–Allocation[i,j]其中：Need[i,j]=k表示進(jìn)程i還需要Rj

類資源k個。Max[i,j]=k表示進(jìn)程i需要Rj

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

:=Needi-RequestiY3系統(tǒng)執(zhí)行安全性算法4分配資源給進(jìn)程Y試探分配作廢N安全性算法：向量

Work

表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，其初始化為當(dāng)前可用的資源數(shù)。向量

Finish

是布爾型數(shù)組，表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。初始化為false。安全性檢查的步驟：(1)Work:=Available;Finish:=false;(2)尋找滿足條件的i：

a.Finish[i]=false;b.Need[i]≤Work;

如果不存在，則轉(zhuǎn)(4)(3)Work:=Work+Allocation[i];Finish[i]:=true;轉(zhuǎn)(2)(4)若對所有i，F(xiàn)inish[i]=true，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)銀行家算法之例

假定系統(tǒng)中有五個進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7。

T0時刻的資源分配表

T0時刻的安全性：

T0時刻的安全序列

P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③試分配：系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量。④再利用安全性算法檢查此時系統(tǒng)是否安全。P1申請資源時的安全性檢查P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request