操作系統講稿-西安電子科技大學出版社

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

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

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

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

5、性能衡量標準,1.調度目標：,對所有的作業(yè)應該是公平合理的,設備利用率高,單位時間內執(zhí)行盡可能多的作業(yè),每個作業(yè)有盡可能快的響應時間,2.調度衡量標準：,周轉時間 Ti=Tfi-Tsi Ti =Twi+Tri,平均周轉時間T=,帶權周轉時間wi=,帶權平均周轉時間w=,=,=1+,三、作業(yè)調度算法,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進程調度,一、進程調度功能,1.記錄系統中所有進程的執(zhí)行情況,2.從就緒進程中選擇占有處理機的進程,3.進行進程上下文（進程狀態(tài)、有關變量、數據結構的值、硬件寄存器值、PCB等）切換,二、進程調度的時機,1.正在執(zhí)行的進程運行完畢,2.執(zhí)行中的進程變成阻塞狀態(tài),3.分時系統中時間片用完,4.可剝

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

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

9、t),靜態(tài)優(yōu)先數：進程的執(zhí)行期間優(yōu)先數不變,六、進程調度與作業(yè)調度的比較,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臺打印機 ，系統中有4臺打印機，其中P1和P2各分得2臺。,P2 P1,一、死鎖的定義：,死鎖：指各并發(fā)過程彼此互相等待對方所使用的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源，從而造成了一種僵局。如果無外力作用，這些進程永遠不能再向前推進。,二、死鎖產生的原因,競爭資源,進程推進順序不當,P2(Rel(R1))P2(Rel(R2))P2(Req(R1))P2(Req(R2)),P1

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

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

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

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

15、資源的全部可用資源數。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資源。,存在關系：Need=Max-Allocation,3) 銀行家算法,requesti 進程

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

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

18、進程： Finish[i]=false 且 Needi<=work,,(3)如果找到：,Work=work+allocationiFinish[i]=trueGoto b),(4)如果對所有進程都有 finish[i]=true 則系統安全，否則系統不安全。,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,找到了安全序列，所以該時刻系統安全,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）試分配，修改數據結構,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、,找到了安全序列，所以該時刻系統安全,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）試分配，修改數據結構.,7 4 3,2 3 0,（4）運行安全性算法.,找不到安全序列，所以不安全，恢復數據結構

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

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

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

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