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

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

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

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

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

1.面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短。周轉(zhuǎn)時(shí)間T：從作業(yè)被提交給系統(tǒng)，到作業(yè)完成為止的時(shí)間間隔。由4個(gè)部分組成：在后備隊(duì)列等待的時(shí)間、進(jìn)程在就緒隊(duì)列中等待的時(shí)間、在CPU中執(zhí)行的時(shí)間、I/O操作完成的時(shí)間。平均周轉(zhuǎn)時(shí)間：平均帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：W=T/TS（TS系統(tǒng)服務(wù)時(shí)間即CPU執(zhí)行時(shí)間）(2)響應(yīng)時(shí)間快。（評(píng)價(jià)分時(shí)系統(tǒng)，輸入、處理、返回）(3)截止時(shí)間的保證。（評(píng)價(jià)實(shí)時(shí)系統(tǒng)）(4)優(yōu)先權(quán)準(zhǔn)則。2.面向系統(tǒng)的準(zhǔn)則(1)系統(tǒng)吞吐量高吞吐量是指單位時(shí)間內(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)程時(shí)確定且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示。動(dòng)態(tài)優(yōu)先權(quán)：可以改變。高響應(yīng)比優(yōu)先調(diào)度算法

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

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

產(chǎn)生死鎖的原因非剝奪資源：磁帶機(jī)、打印機(jī)資源追逐，各不相讓占有并等待臨時(shí)性資源：由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(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)請(qǐng)求和保持條件（占有并等待）(3)不剝奪條件(4)環(huán)路等待條件1.必要條件（缺一不可）2.必須同時(shí)成立或存在處理死鎖的基本方法

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

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

預(yù)防死鎖

摒棄“請(qǐng)求和保持”條件2.

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

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

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

，p2→p3→p1

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

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

類資源k個(gè)。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個(gè)。銀行家算法：Requesti[j]=k進(jìn)程尚需要的資源Requesti<=Needi1出錯(cuò)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)若對(duì)所有i，F(xiàn)inish[i]=true，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)銀行家算法之例

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

T0時(shí)刻的資源分配表

T0時(shí)刻的安全性：

T0時(shí)刻的安全序列

P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量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向量。④再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。P1申請(qǐng)資源時(shí)的安全性檢查P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request