操作系統(tǒng)講稿-西安電子科技大學(xué)出版社

1、第四章 處理機(jī)調(diào)度與死鎖,掌握調(diào)度的層次及進(jìn)程調(diào)度與作業(yè)調(diào)度的關(guān)系掌握各種作業(yè)調(diào)度算法及每種算法的作業(yè)周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間死鎖的原因，產(chǎn)生死鎖的四個(gè)必要條件以及死鎖的解決。,本章重點(diǎn)：,各種作業(yè)調(diào)度算法及每種算法的作業(yè)周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間死鎖的解決,本章難點(diǎn)：,分級(jí)調(diào)度作業(yè)調(diào)度進(jìn)程調(diào)度死鎖小結(jié),4．1分級(jí)調(diào)度,作業(yè)的狀態(tài)及轉(zhuǎn)換,處理機(jī)調(diào)度：如何從眾多的作業(yè)隊(duì)列中選擇一道或幾道進(jìn)入內(nèi)存，進(jìn)入內(nèi)存的若干進(jìn)程又如何

2、去競(jìng)爭(zhēng)CPU的使用權(quán)，這稱為處理機(jī)調(diào)度。,處理機(jī)調(diào)度分4級(jí)：作業(yè)調(diào)度、交換調(diào)度、進(jìn)程調(diào)度、線程調(diào)度。,作業(yè)調(diào)度：負(fù)責(zé)從后備隊(duì)列中選擇作業(yè)投入運(yùn)行。將作業(yè)從運(yùn)行狀態(tài)變成完成狀態(tài)。,進(jìn)程調(diào)度：則將進(jìn)程從就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)。,交換調(diào)度：負(fù)責(zé)將外存交換區(qū)中的進(jìn)程調(diào)入內(nèi)存。將內(nèi)存進(jìn)程調(diào)入外存交換區(qū)。,四者關(guān)系,作業(yè)調(diào)度,,提交,收容,,內(nèi)存,就緒,,就緒,執(zhí)行,,,交換調(diào)度,,,等待,,,等待,進(jìn)程調(diào)度,,,,,完成,線程調(diào)度,,作業(yè)調(diào)

3、度：,又稱高級(jí)調(diào)度，,宏觀調(diào)度。,其主要任務(wù)是對(duì)大量的后備作業(yè)以一定的原則進(jìn)行挑選，給選中的作業(yè)分配內(nèi)存、I/O設(shè)備等必要的資源，建立相應(yīng)的進(jìn)程，這時(shí)該作業(yè)所對(duì)應(yīng)的進(jìn)程具有使用CPU的權(quán)力。作業(yè)完成時(shí)負(fù)責(zé)收回資源,進(jìn)程調(diào)度：,又稱低級(jí)調(diào)度，,微觀調(diào)度。,其任務(wù)是按照某種原則將CPU分配給某一就緒進(jìn)程，即確定哪個(gè)進(jìn)程在什么時(shí)候獲得處理機(jī)，使用多長(zhǎng)時(shí)間。,二者聯(lián)系：作業(yè)調(diào)度創(chuàng)建進(jìn)程調(diào)度所需要進(jìn)程。,二者區(qū)別：,①處理對(duì)象不同；,②完

4、成任務(wù)不同。,交換調(diào)度：,又稱中級(jí)調(diào)度，,其主要任務(wù)是按照給定的原則和策略，將處于外存交換區(qū)中的就緒進(jìn)程或等待進(jìn)程調(diào)入內(nèi)存，或者把內(nèi)存中的就緒進(jìn)程或等待進(jìn)程交換到外存中。,4．2作業(yè)調(diào)度,一、作業(yè)調(diào)度功能,1.數(shù)據(jù)結(jié)構(gòu)：JCB用于記錄作業(yè)相關(guān)信息,2.從后備隊(duì)列中挑選一部分作業(yè)投入運(yùn)行,3.為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作：建立進(jìn)程分配資源,4.作業(yè)完成后做善后處理工作：收回資源，輸出執(zhí)行時(shí)間等作業(yè)管理信息,二、作業(yè)調(diào)度目標(biāo)及

5、性能衡量標(biāo)準(zhǔn),1.調(diào)度目標(biāo)：,對(duì)所有的作業(yè)應(yīng)該是公平合理的,設(shè)備利用率高,單位時(shí)間內(nèi)執(zhí)行盡可能多的作業(yè),每個(gè)作業(yè)有盡可能快的響應(yīng)時(shí)間,2.調(diào)度衡量標(biāo)準(zhǔn)：,周轉(zhuǎn)時(shí)間 Ti=Tfi-Tsi Ti =Twi+Tri,平均周轉(zhuǎn)時(shí)間T=,帶權(quán)周轉(zhuǎn)時(shí)間wi=,帶權(quán)平均周轉(zhuǎn)時(shí)間w=,=,=1+,三、作業(yè)調(diào)度算法,1.先到先服務(wù)FCFS ：優(yōu)先選擇最先到達(dá)的作業(yè),T=175/5=35,W=10.2/5≈2.04,2.短作業(yè)優(yōu)先SJF

6、：優(yōu)先選擇最少運(yùn)行時(shí)間的作業(yè),T=33,W=1. 8,3.響應(yīng)比高者優(yōu)先考慮 ：,T=34,W=1. 91,響應(yīng)比=等待時(shí)間/運(yùn)行時(shí)間,4．3進(jìn)程調(diào)度,一、進(jìn)程調(diào)度功能,1.記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況,2.從就緒進(jìn)程中選擇占有處理機(jī)的進(jìn)程,3.進(jìn)行進(jìn)程上下文（進(jìn)程狀態(tài)、有關(guān)變量、數(shù)據(jù)結(jié)構(gòu)的值、硬件寄存器值、PCB等）切換,二、進(jìn)程調(diào)度的時(shí)機(jī),1.正在執(zhí)行的進(jìn)程運(yùn)行完畢,2.執(zhí)行中的進(jìn)程變成阻塞狀態(tài),3.分時(shí)系統(tǒng)中時(shí)間片用完,4.可剝

7、奪調(diào)度方式中有優(yōu)先級(jí)高的進(jìn)程進(jìn)入就緒隊(duì)列,三、進(jìn)程調(diào)度性能衡量標(biāo)準(zhǔn),1.定性標(biāo)準(zhǔn)：,（1）可靠性：一次進(jìn)程調(diào)度是否能引起數(shù)據(jù)結(jié)構(gòu)的破壞,（2）簡(jiǎn)潔性：調(diào)度程序的國(guó)度繁瑣將引起較大的系統(tǒng)開銷,2.定量標(biāo)準(zhǔn),（1）CPU的利用率,（2）進(jìn)程在就緒隊(duì)列中的等待時(shí)間與執(zhí)行時(shí)間之比,四、進(jìn)程調(diào)度調(diào)度方式,1.可剝奪 ：,2.不可剝奪：,五、進(jìn)程調(diào)度算法,1.先到先服務(wù)FCFS：優(yōu)先調(diào)度最先進(jìn)入就緒隊(duì)列的進(jìn)程,2.輪轉(zhuǎn)法 （Round Robin）

8、：將CPU的處理時(shí)間分成固定大小的時(shí)間片，一個(gè)進(jìn)程在被調(diào)度程序選中后用完了系統(tǒng)規(guī)定的時(shí)間片但未完成要求的任務(wù)，自動(dòng)到就緒隊(duì)列隊(duì)尾,3.多級(jí)反饋隊(duì)列法（ Round Robin with Multiple Feedback）：,優(yōu)先級(jí),高,,低,RL1,RL2,RLn,,時(shí)間片,短,,長(zhǎng),,,4.優(yōu)先數(shù)法 ：優(yōu)先調(diào)度優(yōu)先級(jí)最高的進(jìn)程,動(dòng)態(tài)優(yōu)先數(shù)：優(yōu)先數(shù)隨著進(jìn)程的執(zhí)行而發(fā)生變化,5. SCBF(Short CPU Burst Firs

9、t),靜態(tài)優(yōu)先數(shù)：進(jìn)程的執(zhí)行期間優(yōu)先數(shù)不變,六、進(jìn)程調(diào)度與作業(yè)調(diào)度的比較,4.4進(jìn)程死鎖,例： P1 打印機(jī) 繪圖儀 P2 繪圖儀 打印機(jī),Pi思考P（S(i+1) mod 5）拿左叉P（S(i) ）拿右叉；吃飯；放左叉；V（ S(i+1) mod 5 ）放右叉V（S(i)）;,例：哲學(xué)家就餐問題,0,1,2,3,4,思考,吃飯,0,1,2,3,4,例：P2

10、、P1都需3臺(tái)打印機(jī) ，系統(tǒng)中有4臺(tái)打印機(jī)，其中P1和P2各分得2臺(tái)。,P2 P1,一、死鎖的定義：,死鎖：指各并發(fā)過程彼此互相等待對(duì)方所使用的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源，從而造成了一種僵局。如果無外力作用，這些進(jìn)程永遠(yuǎn)不能再向前推進(jìn)。,二、死鎖產(chǎn)生的原因,競(jìng)爭(zhēng)資源,進(jìn)程推進(jìn)順序不當(dāng),P2(Rel(R1))P2(Rel(R2))P2(Req(R1))P2(Req(R2)),P1

11、Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2),三、產(chǎn)生死鎖的四個(gè)必要條件,1.互斥條件,2.部分分配,3.不剝奪條件（不可搶占）,4.環(huán)路條件,四、死鎖的解決,1.死鎖的預(yù)防：打破死鎖存在條件中的一個(gè)或幾個(gè)有三種方法：,1）打破互斥和不剝奪條件：一個(gè)已保持了某些資源的進(jìn)程。若新的資源要求不能立即得到滿足，它必須釋放已保持的所有資源，以后需要時(shí)再重新申請(qǐng)，這意味著一個(gè)進(jìn)程已占有的資源，在運(yùn)行過程中可能

12、暫時(shí)地釋放或說被剝奪。,2）打破部分分配條件：系統(tǒng)要求所有進(jìn)程一次性申請(qǐng)所需的全部資源。若系統(tǒng)有足夠的資源分配給一個(gè)進(jìn)程時(shí)，便一次把所需資源分配給該進(jìn)程。這樣，進(jìn)程在整個(gè)運(yùn)行期間為會(huì)提出任何要求，但系統(tǒng)浪費(fèi)嚴(yán)重，降低了并發(fā)性。,3）打破環(huán)路條件：將所有資源編號(hào)，申請(qǐng)時(shí)按順序申請(qǐng)，先申請(qǐng)小號(hào)，再申請(qǐng)大號(hào)，這樣，能保證申請(qǐng)到最大號(hào)者，肯定運(yùn)行完成。,2、死鎖的避免,1）安全與不安全狀態(tài)：允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源，系統(tǒng)進(jìn)行資源分配前先計(jì)算資源分配

13、的安全性，若此次分配不會(huì)導(dǎo)致 進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程，否則進(jìn)程等待。,安全狀態(tài)：指將系統(tǒng)按照某種順序如來為每一個(gè)進(jìn)程分配其所需資源，直到最大需求使每個(gè)進(jìn)程可順序完成，若系統(tǒng)不存在這樣一個(gè)安全系列，則系統(tǒng)處于不安全狀態(tài)。只要系統(tǒng)處于安全狀態(tài)，便可避免進(jìn)死鎖狀態(tài)。,例：三個(gè)進(jìn)程P1,P2,和P3所需要磁帶機(jī)10，4，9系統(tǒng)中其12臺(tái)。,T0時(shí)刻 最大需求P110P24P39,T0時(shí)刻存在

14、一個(gè)安全序列 所以系統(tǒng)安全。,如果 P3 請(qǐng)求 1 臺(tái), 狀態(tài)發(fā)生變化.,已分配 522,可用3,還需527,找不到一個(gè)安全序列. 狀態(tài)不安全. 請(qǐng)求不能滿足。,如果 P1 請(qǐng)求 1 臺(tái), 狀態(tài)發(fā)生變化. 結(jié)果如何？,如果 P2 請(qǐng)求 1 臺(tái), 狀態(tài)發(fā)生變化. 結(jié)果又如何？,2）數(shù)據(jù)結(jié)構(gòu),（1） 可用資源向量 available[m]: available[i] 代表資源i的可用資源數(shù)。初值為系統(tǒng)中所配置的該類

15、資源的全部可用資源數(shù)。available[j]=k; Rj類資源有k個(gè)。,(2)Max[m,n]: max[i,j]=k 表示進(jìn)程i最多需要k個(gè)Rj資源。,(3)Allocation[m,n]: allocation[i,j]=k 表示進(jìn)程i已分得k個(gè)Rj資源。,(4)Need[m,n]: need[i,j]=k 表示進(jìn)程i還需要k個(gè)Rj資源。,存在關(guān)系：Need=Max-Allocation,3) 銀行家算法,requesti 進(jìn)程

16、Pi的請(qǐng)求向量。 requesti [j]=k 進(jìn)程Pi申請(qǐng)k個(gè)Rj ，Pi發(fā)出請(qǐng)求后，系統(tǒng)按如下方法做.,(1) if requesti <=Needi, then go to (b) else error,(2) if requesti <=Available, then go to (c) else Pi waits,(3)系統(tǒng)試分配, 修改數(shù)據(jù)結(jié)構(gòu)。,Available= Available- requestiNe

17、edi= Needi- requestiallocationi= allocationi + requesti,(4)系統(tǒng)執(zhí)行安全性算法，若安全，正式分配，否則，試探作廢，Pi等待,恢復(fù)原來的數(shù)據(jù)結(jié)構(gòu)。,4)安全性算法,設(shè)置兩個(gè)向量：工作向量work,表示系統(tǒng)能夠提供給進(jìn)程的資源數(shù)；Finish，表示系統(tǒng)是否有足夠的資源滿足每個(gè)進(jìn)程，初始時(shí)Work=Available，F(xiàn)inish=false,(2)從進(jìn)程集合中找滿足下列條件的

18、進(jìn)程： Finish[i]=false 且 Needi<=work,,(3)如果找到：,Work=work+allocationiFinish[i]=trueGoto b),(4)如果對(duì)所有進(jìn)程都有 finish[i]=true 則系統(tǒng)安全，否則系統(tǒng)不安全。,5)銀行家算法的例,進(jìn)程 {p0,p1,p2,p3,p4} 資源{A,B,C} 最大可用資源 {10,5,7}At the moment T0:,Max

19、allocationneedavailable ABCABCABCABCP0 7 5 30 1 07 4 33 3 2P1 3 2 22 0 01 2 2P2 9 0 23 0 26 0 0P3 2 2 22 1 10 1 1P4 4 3 30 0 24 3 1,R,T0時(shí)刻的安全性:,work needallo

20、cationwork+allocation finish,ABC ABC ABCABC,P1 3 3 2 1 2 22 0 05 3 2 true,P3 5 3 2 0 1 12 1 17 4 3 true,P4 7 4 3 4 3 10 0 27 4 5 true,P0 7 4 5 7

21、4 30 1 07 5 5 true,P2 7 5 5 6 0 03 0 210 5 7 true,找到了安全序列，所以該時(shí)刻系統(tǒng)安全,P1 請(qǐng)求： request1(1,0,2),MaxallocationneedavailableABCABCABCABCP07 5 30 1 07 4 32 3 0P13 2 2

22、3 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1,（1）request1<=need1,（4）運(yùn)行安全性算法.,（2）request1<=available,（3）試分配，修改數(shù)據(jù)結(jié)構(gòu),1 2 2,3 3 2,R,T1時(shí)刻的安全性:,workneedallocationwork+allocati

23、onfinish,ABCABCABCABC,P12 3 00 2 03 0 25 3 2 true,P35 3 20 1 12 1 17 4 3 true,P47 4 34 3 10 0 27 4 5 true,P07 4 57 4 30 1 07 5 5 true,P27 5 56 0 03 0 210 5 7 true

24、,找到了安全序列，所以該時(shí)刻系統(tǒng)安全,P4 請(qǐng)求 request4(3,3,0),（1）request4<=need4,（2）request4<=available is not satisfied.,4 3 1,2 3 0,P4 wait,P0 請(qǐng)求 request0(0,2,0),MaxallocationneedavailableABCABCABCABCP07 5 30 3 0

25、7 2 32 1 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1,（1）request0<=need0,（2）request0<=available.,（3）試分配，修改數(shù)據(jù)結(jié)構(gòu).,7 4 3,2 3 0,（4）運(yùn)行安全性算法.,找不到安全序列，所以不安全，恢復(fù)數(shù)據(jù)結(jié)構(gòu)

26、，P0等待,五、死鎖的檢測(cè)和恢復(fù),當(dāng)系統(tǒng)為進(jìn)程分配資源時(shí)，若未采取任何限制性措施保證不進(jìn)入死鎖狀態(tài)，則系統(tǒng)必須提供解除死鎖的手段。,1.資源分配圖,2死鎖定理,當(dāng)且僅當(dāng)S的資源分配圖是不可完全簡(jiǎn)化的，S為死鎖狀態(tài)。,死的解除：,1.終止死鎖進(jìn)程；,2.按一定順序中止進(jìn)程直至釋放到有足夠的資源來完成剩下的進(jìn)程為止；,3.從被鎖住進(jìn)程中強(qiáng)迫剝奪資源以解除死鎖。,,4．5 小結(jié),處理機(jī)調(diào)度定義、層次、四者所在位置作業(yè)調(diào)度與進(jìn)程調(diào)度的任務(wù)、

27、功能、關(guān)系 作業(yè)調(diào)度功能、衡量標(biāo)準(zhǔn)作業(yè)調(diào)度算法 進(jìn)程調(diào)度功能、時(shí)機(jī)、衡量標(biāo)準(zhǔn)、方式進(jìn)程調(diào)度算法兩類調(diào)度算法的比較死鎖定義 死鎖產(chǎn)生原因；產(chǎn)生死鎖的四個(gè)必要條件；死鎖的解決： 預(yù)防、 避免 、檢測(cè)和恢復(fù),1.銀行家算法中出現(xiàn)下述資源分配：,作業(yè),allocationneedavailableABCDABCDABCDP0003200121622P110001750P2

28、13542356P303320652P400140656,（1）該狀態(tài)是否安全？,（2）如果P2提出請(qǐng)求Request2（1，2，2，2）后，系統(tǒng)能否將資源分配給它？,2.有相同類型的5個(gè)資源被4個(gè)進(jìn)程所共享，且每個(gè)進(jìn)程最多需要2個(gè)這樣的資源才可以運(yùn)行完畢，試問系統(tǒng)是否會(huì)由于這種資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。,3. 已知某系統(tǒng)中的所有資源都是相同的，系統(tǒng)中的進(jìn)程嚴(yán)格按照一次一個(gè)的方式申請(qǐng)或者釋放資源。在此系統(tǒng)中

29、，沒有進(jìn)程所需要的資源數(shù)超過系統(tǒng)的資源總擁有量，試對(duì)下面列出的各種情況說明是否會(huì)發(fā)生死鎖，為什么？,情況序號(hào)系統(tǒng)中進(jìn)程數(shù) 資源總量A12B21C22D23,4.系統(tǒng)中有3種資源A、B、C，5個(gè)進(jìn)程P1、P2、P3、P4、P5，系統(tǒng)中有A、B、C的數(shù)量分別是17、5、20，T0時(shí)刻系統(tǒng)狀態(tài)如下：,MaxAlocationABCABC

30、P15 5 92 1 2P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 4,（1）該狀態(tài)是否安全？為什么？,（2）如果P2提出請(qǐng)求Request2（0，3，4）后，系統(tǒng)能否將資源分配給它？為什么？,（3）在（2）的基礎(chǔ)上，如果P4提出請(qǐng)求Request4（2，0，1）后，系統(tǒng)能否實(shí)施分配？為什么？,（4）在（3）的基礎(chǔ)上，如果P1提出請(qǐng)