操作系統(tǒng)課件-第4章調(diào)度與死鎖

第4章調(diào)度與死鎖本章要點●調(diào)度類型與準(zhǔn)則

●調(diào)度算法

●死鎖的預(yù)防與避免

●死鎖的基本概念

●死鎖的檢測與解除

●4.1調(diào)度類型與準(zhǔn)則調(diào)度類型●高級調(diào)度●低級調(diào)度●中級調(diào)度調(diào)度的層次高級調(diào)度中級調(diào)度低級調(diào)度又稱作業(yè)調(diào)度、宏觀調(diào)度任務(wù)：決定將外存上后備隊列中的哪些作業(yè)調(diào)入內(nèi)存。調(diào)度工作決定接納多少作業(yè)：取決于多道的程度，即內(nèi)存允許放多少個作業(yè)。接納哪些作業(yè)：有調(diào)度算法決定。適用于批處理系統(tǒng)又稱進(jìn)程調(diào)度、微觀調(diào)度任務(wù)：決定就緒隊列中的哪些進(jìn)程將獲得處理機。調(diào)度方式非剝奪式剝奪式搶占原則時間片優(yōu)先權(quán)進(jìn)程長短適用于分時、實時、批處理系統(tǒng)又稱對換程序主要作用：內(nèi)存和外存對換區(qū)之間進(jìn)行進(jìn)程對換，以解決內(nèi)存緊張問題。進(jìn)程調(diào)度方式●不可剝奪方式不可剝奪方式也被稱為非搶占方式。采用這種調(diào)度方式時，一旦把處理機分配給某個進(jìn)程，該進(jìn)程將一直執(zhí)行下去，直到運行完畢或因某種原因不能運行，才把處理機分配給其它進(jìn)程，決不允許其它進(jìn)程強占正在運行進(jìn)程占有的處理機?！窨蓜儕Z方式可剝奪方式也被稱為搶占方式。在這種方式下，允許一個進(jìn)程按照某種原則，搶占其它進(jìn)程占有的處理機。搶占采用優(yōu)先權(quán)原則的比較多，也就是說，如果一個進(jìn)程比正在運行進(jìn)程的優(yōu)先級高，則它可以搶占處理機而運行。進(jìn)程調(diào)度時機●進(jìn)程退出●進(jìn)程阻塞●新進(jìn)程創(chuàng)建●中斷發(fā)生●時鐘中斷

調(diào)度的性能準(zhǔn)則●面向用戶的準(zhǔn)則●響應(yīng)時間快響應(yīng)時間：從用戶通過鍵盤提交請求到首次得到響應(yīng)的時間●周轉(zhuǎn)時間短：周轉(zhuǎn)時間：作業(yè)從提交到完成的時間間隔?！駜?yōu)先權(quán)準(zhǔn)則●截止時間的保證●面向系統(tǒng)的準(zhǔn)則●系統(tǒng)吞吐量單位時間內(nèi)完成的作業(yè)數(shù)。●處理機利用率●各類資源平衡利用●公平周轉(zhuǎn)時間定義●周轉(zhuǎn)時間Ti●平均周轉(zhuǎn)時間

●帶權(quán)周轉(zhuǎn)時間●平均帶權(quán)周轉(zhuǎn)時間●先來先服務(wù)調(diào)度算法●短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法●時間片輪轉(zhuǎn)調(diào)度算法●優(yōu)先權(quán)調(diào)度算法●多級反饋隊列……●4.2調(diào)度算法先來先服務(wù)FCFS與短作業(yè)優(yōu)先SJF算法思想對于作業(yè)調(diào)度，從后備作業(yè)中選擇最先進(jìn)入該隊列的作業(yè)，將他們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊列。對于進(jìn)程調(diào)度，從就緒隊列中選擇最先進(jìn)入該隊列的進(jìn)程，分配處理機，使之運行。特點易于實現(xiàn)有利用長作業(yè)，短作業(yè)不滿。算法思想短作業(yè)優(yōu)先是從后備隊列中選擇估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存。短進(jìn)程優(yōu)先是從就緒隊列中選擇估計運行時間最短的進(jìn)程，將處理機分配給它，使之執(zhí)行并一直到完成或因發(fā)生某事件而阻塞放棄處理機時，再重新調(diào)度。特點極端情況下，長作業(yè)得不到調(diào)度。作業(yè)或進(jìn)程的長短只能估計，不準(zhǔn)確。完全不考慮緊迫程度，使緊急事件得不到處理。FCFSSJFFCFS與SJF比較時間片輪轉(zhuǎn)調(diào)度算法●算法思想●進(jìn)程按FCFS在就緒隊列排隊，調(diào)度程序把CPU分配給隊首進(jìn)程，令其執(zhí)行一個時間片，一個時間片執(zhí)行完畢將進(jìn)程排在隊尾?！駮r間片大小的確定 響應(yīng)時間T=用戶數(shù)目N*時間片q●響應(yīng)時間T 當(dāng)N一定，T與q成正比。T若要求快，則q也要小?！窬途w隊列的進(jìn)程數(shù)N T一定，q與N成反比。N越多，q要小。●系統(tǒng)的處理能力 保證用戶鍵入的常用命令能在一個時間片內(nèi)處理完畢。時間片大小系統(tǒng)處理能力比較●算法思想從后備隊列中選擇若干優(yōu)先權(quán)最高的作業(yè)，將它們調(diào)入內(nèi)存?；驈木途w隊列中選擇優(yōu)先權(quán)最高的進(jìn)程，將處理機分配給它。●優(yōu)先權(quán)類型靜態(tài)優(yōu)先權(quán)確定因素：進(jìn)程類型、進(jìn)程對資源的需求、用戶要求。動態(tài)優(yōu)先權(quán)確定因素：等待時間、運行時間。●特點：綜合考慮各種情況優(yōu)先權(quán)調(diào)度算法●算法思想●根據(jù)作業(yè)的性質(zhì)和類型不同，將就緒隊列再分為若干個子隊列，每個進(jìn)程分屬于一個隊列?！裨诙嗉夑犃械幕A(chǔ)上，不但設(shè)多個隊列，且為每個隊列賦予不同的優(yōu)先權(quán)，第一個隊列的優(yōu)先權(quán)最高，第二個隊列次之，其余隊列的優(yōu)先權(quán)逐個降低?！窀鱾€隊列中的進(jìn)程執(zhí)行時間片大小逐漸增大。●新進(jìn)程投入第一個隊列。●調(diào)度從第一個隊列進(jìn)行，僅當(dāng)?shù)谝粋€隊列為空時，才調(diào)度第二個隊列中的進(jìn)程。多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法●4.3死鎖的基本概念一組競爭系統(tǒng)資源或相互通信的進(jìn)程相互的“永久”阻塞。若無外力作用，這組進(jìn)程將永遠(yuǎn)不能繼續(xù)執(zhí)行。產(chǎn)生死鎖的原因●資源數(shù)<要求該種資源的進(jìn)程數(shù)●進(jìn)程的推進(jìn)順序非法進(jìn)程P……get(A);……get(B);……release(A);……release(B);……

進(jìn)程Q……get(B);……get(A);……release(B);……release(A);……A、B分別代表某種資源進(jìn)程的推進(jìn)順序不當(dāng)死鎖●(1)、(2)、(4)、(5)正常運行●(3)、(6)發(fā)生死鎖進(jìn)程的推進(jìn)順序合適不死鎖進(jìn)程P對資源的申請、釋放次序改變后不死鎖！交換P操作的位置voidproducer()//生產(chǎn)者進(jìn)程{while(true){produceanitemindata_p;P(empty);P(mutex);buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full);}}voidconsumer()//消費者進(jìn)程{while(true){P(mutex); P(full); data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;}}問題的提出：對于生產(chǎn)者-消費者問題，如果將P操作的位置交換，將產(chǎn)生什么樣的后果？？消費者先行死鎖！voidproducer()//生產(chǎn)者進(jìn)程{while(true){produceanitemindata_p;P(mutex); P(empty); buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full); }}voidconsumer()//消費者進(jìn)程{while(true){P(full); P(mutex); data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c; }}？生產(chǎn)者運行N次后——死鎖！交換P操作的位置產(chǎn)生死鎖的四個必要條件不剝奪條件互斥條件請求保持條件環(huán)路條件采用預(yù)先靜態(tài)分配方法系統(tǒng)要求所有進(jìn)程一次性地申請其所需的全部資源優(yōu)點：方法簡單缺點：進(jìn)程延遲運行資源浪費用戶有時提不出他要使用的全部資源去掉“不剝奪條件”互斥條件不可禁止去掉“請求保持條件”去掉“環(huán)路“條件方法占有某些資源的進(jìn)程，當(dāng)它有新的資源請求被拒絕時，該進(jìn)程停止運行，并釋放它所占有的資源。當(dāng)它再次被執(zhí)行時，重新申請資源。如果一個進(jìn)程請求另一個進(jìn)程占有的資源，操作系統(tǒng)可以剝奪后者占有的資源，要求它釋放資源并將資源分配給前者使用

缺點該策略實現(xiàn)起來比較復(fù)雜，而且要付出很大代價。反復(fù)申請、釋放，使進(jìn)程執(zhí)行無限延遲，不僅延遲了周轉(zhuǎn)時間。還增加了系統(tǒng)開銷，降低了系統(tǒng)吞吐量。采用資源的有序分配令所有資源排隊，并賦予不同的序號。當(dāng)進(jìn)程請求資源時，必須嚴(yán)格按遞增的次序提出，從而消除了環(huán)路。缺點：定好序號后，增加新設(shè)備類型受到限制。盡管定序號時考慮大多數(shù)作業(yè)使用資源的順序。但會發(fā)生使用順序與規(guī)定順序不一致的情況，造成資源浪費。限制用戶簡單、自主地編程。死鎖的預(yù)防措施低效！●死鎖的預(yù)防4.4死鎖的預(yù)防與避免●安全狀態(tài)是指系統(tǒng)至少存在一個安全序列<P1,P2,…,Pn>，按照這個序列為進(jìn)程分配資源，直到滿足最大需求，每個進(jìn)程都可順序完成?！袢粝到y(tǒng)不存在這樣一個安全序列，則系統(tǒng)處于不安全狀態(tài)。避免死鎖是通過明智的選擇，確保系統(tǒng)永遠(yuǎn)不會到達(dá)死鎖點。即動態(tài)地決定是否分配資源給進(jìn)程！安全狀態(tài)—與—不安全狀態(tài)死鎖的避免系統(tǒng)有三個進(jìn)程P1、P2、P3，共有12臺磁帶機，進(jìn)程P1要求10臺，P2要求4臺，P3要求9臺。在T0時刻，進(jìn)程P1、P2、P3已獲得5、2、2臺，尚有3臺未分配，問：系統(tǒng)是否處于安全狀態(tài)？進(jìn)程最大需求已分配可用P1 10 5 3P242P392存在安全序列<P2,P1,P3>！——實例安全狀態(tài)銀行家算法數(shù)據(jù)結(jié)構(gòu)定義Resource=(R1,R2,…，Rm)系統(tǒng)中每種資源的總量

Available=(V1,V2,…，Vm)沒有分配的每種資源總量

C11C12…C1m C21C21…C2mNeed= …… 每個進(jìn)程對每種資源的需求 ……

Cn1Cn2…Cnm

A11A12…A1m A21A21…A2mAllocation= ……當(dāng)前分配情況 ……

An1An2…Anm

●進(jìn)行資源預(yù)分配●實施安全檢測

●安全：真正資源分配

●不安全：回到預(yù)分配前狀態(tài)算法描述安全狀態(tài)——實例(a)初始狀態(tài)：

●4個進(jìn)程

●3類資源(b)

●讓P1運行，不行

●讓P2運行，OK(c)●讓P1運行，OK(d)●讓P3運行，OK●存在安全序列<P2,P1,P3,P4>不安全狀態(tài)●圖（a）定義的矩陣，假設(shè)P2請求1個R1和1個R3，如果同意了這個請求，系統(tǒng)的狀態(tài)回到上圖的（a），前面已經(jīng)分析了這是一個安全狀態(tài)?！竦偃缭趫D（a）的狀態(tài)下P1請求1個R1和1個R3，如果滿足P1的請求，則系統(tǒng)就有了圖2-31（b）的狀態(tài)，●狀態(tài)(b)是不是安全呢？答案是：不安全。

——實例！●●資源分配圖

●該圖是由一組結(jié)點N和一組邊E組成的一對偶G=（N，E）

●

N被分成兩個互斥的子集，一組進(jìn)程結(jié)點P={p1,p2,…,pn}，一組資源結(jié)點R={r1,r2,…,rn}，N=PUR

●凡屬于E中的一個邊e∈E，都連接著P中的一個結(jié)點和R中的一個結(jié)點，e={pi,rj}是資源請求邊，由進(jìn)程pi指向資源rj，它表示進(jìn)程pi請求一個單位的資源rj。e={rj，pi}是資源分配邊，由資源rj指向進(jìn)程pi，它表示一個單位的資源rj分配給進(jìn)程pi。4.5死鎖的檢測與解除死鎖的檢測●在圖中找出一個既不阻塞又非獨立的進(jìn)程結(jié)點pi，消去pi所有的請求邊和分配邊，使之成為孤立結(jié)點?！裨谶M(jìn)行一系列簡化后，能消去圖中所有的邊，使所有進(jìn)程都成為孤立結(jié)點，則稱該圖是可以完全簡化的，否則若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的。當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的，S為死鎖狀態(tài)。資源分配圖的簡化死鎖的解除●當(dāng)發(fā)現(xiàn)死鎖時，應(yīng)立即把它們從死鎖中解脫出來，常采用的兩種方法是：●剝奪資源●從其它進(jìn)程剝奪足夠數(shù)量的資