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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、一個安全序列 所以系統(tǒng)安全。,如果 P3 請求 1 臺, 狀態(tài)發(fā)生變化.,已分配 522,可用3,還需527,找不到一個安全序列. 狀態(tài)不安全. 請求不能滿足。,如果 P1 請求 1 臺, 狀態(tài)發(fā)生變化. 結(jié)果如何？,如果 P2 請求 1 臺, 狀態(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個。,(2)Max[m,n]: max[i,j]=k 表示進程i最多需要k個Rj資源。,(3)Allocation[m,n]: allocation[i,j]=k 表示進程i已分得k個Rj資源。,(4)Need[m,n]: need[i,j]=k 表示進程i還需要k個Rj資源。,存在關(guān)系：Need=Max-Allocation,3) 銀行家算法,requesti 進程

16、Pi的請求向量。 requesti [j]=k 進程Pi申請k個Rj ，Pi發(fā)出請求后，系統(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等待,恢復原來的數(shù)據(jù)結(jié)構(gòu)。,4)安全性算法,設(shè)置兩個向量：工作向量work,表示系統(tǒng)能夠提供給進程的資源數(shù)；Finish，表示系統(tǒng)是否有足夠的資源滿足每個進程，初始時Work=Available，F(xiàn)inish=false,(2)從進程集合中找滿足下列條件的

18、進程： Finish[i]=false 且 Needi<=work,,(3)如果找到：,Work=work+allocationiFinish[i]=trueGoto b),(4)如果對所有進程都有 finish[i]=true 則系統(tǒng)安全，否則系統(tǒng)不安全。,5)銀行家算法的例,進程 {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時刻的安全性:,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,找到了安全序列，所以該時刻系統(tǒng)安全,P1 請求： 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）運行安全性算法.,（2）request1<=available,（3）試分配，修改數(shù)據(jù)結(jié)構(gòu),1 2 2,3 3 2,R,T1時刻的安全性:,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、,找到了安全序列，所以該時刻系統(tǒng)安全,P4 請求 request4(3,3,0),（1）request4<=need4,（2）request4<=available is not satisfied.,4 3 1,2 3 0,P4 wait,P0 請求 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）運行安全性算法.,找不到安全序列，所以不安全，恢復數(shù)據(jù)結(jié)構(gòu)

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

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

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

29、，沒有進程所需要的資源數(shù)超過系統(tǒng)的資源總擁有量，試對下面列出的各種情況說明是否會發(fā)生死鎖，為什么？,情況序號系統(tǒng)中進程數(shù) 資源總量A12B21C22D23,4.系統(tǒng)中有3種資源A、B、C，5個進程P1、P2、P3、P4、P5，系統(tǒng)中有A、B、C的數(shù)量分別是17、5、20，T0時刻系統(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提出請求Request2（0，3，4）后，系統(tǒng)能否將資源分配給它？為什么？,（3）在（2）的基礎(chǔ)上，如果P4提出請求Request4（2，0，1）后，系統(tǒng)能否實施分配？為什么？,（4）在（3）的基礎(chǔ)上，如果P1提出請