《OS調(diào)度與死鎖》PPT課件

1、第 3 章 調(diào)度與死鎖操作系統(tǒng)原理與Windows 2003實踐教程1精選PPT第三章調(diào)度與死鎖3.1 處理機(jī)調(diào)度3.2 調(diào)度算法3.3 死鎖3.4 死鎖的預(yù)防3.5 死鎖的避免和銀行家算法3.6 死鎖的檢測與解除 3.7 Windows2003處理器3.8 本章小結(jié)2精選PPT3.1 處理器調(diào)度3.1.1調(diào)度的層次3.1.2進(jìn)程調(diào)度3.1.3調(diào)度隊列模型3精選PPT調(diào)度的層次高級調(diào)度：也稱作業(yè)調(diào)度中級調(diào)度：即交換調(diào)度低級調(diào)度：也稱進(jìn)程調(diào)度4精選PPTprocesserprocesserRAMmemory高級調(diào)度中級調(diào)度低級調(diào)度5精選PPT高級調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度 高級調(diào)度的時間尺度通

2、常是分鐘、小時或天中級調(diào)度涉及進(jìn)程在內(nèi)外存間的交換，從存儲器資源管理的角度來看，把進(jìn)程的部分或全部換出到外存上，可為當(dāng)前運行進(jìn)程的執(zhí)行提供所需內(nèi)存空間，將當(dāng)前進(jìn)程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問低級調(diào)度也稱微觀調(diào)度，從處理機(jī)資源分配的角度來看，處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運行狀態(tài)，低級調(diào)度的時間尺度通常是毫秒級的。由于低級調(diào)度算法的頻繁使用，要求在實現(xiàn)時做到高效6精選PPT處理機(jī)的三級調(diào)度7精選PPT作業(yè)調(diào)度與進(jìn)程調(diào)度8精選PPT處理機(jī)調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換9精選PPT進(jìn)程調(diào)度進(jìn)程調(diào)度的功能記錄系統(tǒng)中所有進(jìn)程的狀態(tài)、優(yōu)先數(shù)和資源需求確定調(diào)度算法分配處理器給進(jìn)程

3、 10精選PPT進(jìn)程調(diào)度的時機(jī)：正在執(zhí)行的進(jìn)程執(zhí)行完畢執(zhí)行進(jìn)程調(diào)用阻塞原語將自己阻塞起來變?yōu)樽枞麪顟B(tài)執(zhí)行進(jìn)程調(diào)用P操作，因資源不足而被阻塞；或調(diào)用V操作激活了等待資源的進(jìn)程隊列。執(zhí)行進(jìn)程提出I/O請求，被阻塞分時系統(tǒng)中時間片用完執(zhí)行系統(tǒng)調(diào)用完畢，由系統(tǒng)程序返回用戶進(jìn)程時，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進(jìn)程執(zhí)行。11精選PPT調(diào)度隊列模型具有一級調(diào)度的調(diào)度隊列模型 12精選PPT兩級調(diào)度簡化隊列圖 13精選PPT具有高、低兩級調(diào)度的調(diào)度隊列模型 14精選PPT具有三級調(diào)度的調(diào)度隊列模型 15精選PPT3.2 調(diào)度算法3.2.1算法的衡量3.2.2先來先服務(wù)調(diào)度算法3.2.3短者

4、優(yōu)先調(diào)度算法3.2.4最短剩余時間優(yōu)先調(diào)度算法3.2.5最高響應(yīng)比優(yōu)先調(diào)度算法3.2.6時間片輪轉(zhuǎn)法3.2.7優(yōu)先級調(diào)度算法3.2.8多級反饋隊列調(diào)度算法16精選PPT確定調(diào)度策略時應(yīng)考慮的主要因素：所用算法應(yīng)保證實現(xiàn)系統(tǒng)的設(shè)計目標(biāo)公平性原則均衡使用資源兼顧響應(yīng)時間和資源利用率基于相對優(yōu)先級，但避免無限延期系統(tǒng)開銷不應(yīng)大大17精選PPT算法的衡量常用的評價準(zhǔn)則包括： CPU利用率 吞吐量 周轉(zhuǎn)時間 就緒等待時間 響應(yīng)時間18精選PPTCPU利用率： CPU利用率CPU有效工作時間CPU總運行時間CPU總運行時間CPU有效工作時間CPU空閑時間19精選PPT吞吐量： 單位時間內(nèi)CPU完成作業(yè)的數(shù)

5、量20精選PPT周轉(zhuǎn)時間： Tit ci t si其中，t si表示作業(yè)i的提交時間，即作業(yè)i到達(dá)系統(tǒng)的時間；t ci表示作業(yè)i的完成時刻平均周轉(zhuǎn)時間：21精選PPT就緒等待時間 ： 作業(yè)在就緒隊列中的等待時間22精選PPT響應(yīng)時間： 從提交第一個請求到產(chǎn)生第一個響應(yīng)所用的時間 23精選PPT先來先服務(wù)調(diào)度算法實現(xiàn)思想：“排隊買票”，即按照作業(yè)到達(dá)系統(tǒng)或是進(jìn)程進(jìn)入就緒隊列的先后次序作為選擇 依據(jù)就緒隊列（后備隊列）按照進(jìn)入的先后次序為序，選擇時選取隊列的隊首進(jìn)程（作業(yè)）24精選PPT【例3-1】假設(shè)一個系統(tǒng)有5個進(jìn)程P1、P2、P3、P4、P5，已知它們的到達(dá)時間和運行時間，用FCFS算法進(jìn)行

6、調(diào)度。 25精選PPT26精選PPT周轉(zhuǎn)時間/服務(wù)時間27精選PPTFCFS的優(yōu)點：簡單、容易實現(xiàn) 有利于長進(jìn)程（作業(yè)），不利于短進(jìn)程（作業(yè)）有利于CPU型作業(yè)，不利于I/O型作業(yè) FCFS的缺點：屬于不可搶占策略，表面上對于所有的作業(yè)和進(jìn)程都是公平的 ，但系統(tǒng)吞吐量不大，效率較低28精選PPT短者優(yōu)先調(diào)度算法實現(xiàn)思想：從就緒隊列中挑選所需的運行時間（估計時間）最短的進(jìn)程（作業(yè)）運行 就緒隊列（后備隊列）按照進(jìn)程（作業(yè)）的運行為序，選擇時選取隊列的隊首進(jìn)程（作業(yè)）即為最短者，新來的進(jìn)程（作業(yè)）依據(jù)運行時間的長短插入到隊列的合適位置。29精選PPT【例3-2】設(shè)系統(tǒng)中有5個進(jìn)程中A，B，C，D，

7、E，它們到來的時間依次為0，1，2，3，4，運行時間依次為4，3，5，2，4，試用FCFC算法和短者優(yōu)先調(diào)度算法調(diào)度。FCFS：進(jìn)程的執(zhí)行順序依次為ABCDE SJF：進(jìn)程的執(zhí)行順序依次為ADBEC。 30精選PPT31精選PPTSJF（SPF）的優(yōu)點：簡單、容易實現(xiàn) 有利于短進(jìn)程（作業(yè)），不利于長進(jìn)程（作業(yè)）有利于保障系統(tǒng)吞吐量 SJF（SPF）的缺點：對于長進(jìn)程（作業(yè)）是不公平的32精選PPT最短剩余時間優(yōu)先調(diào)度算法實現(xiàn)思想：讓運行到進(jìn)程完成時所需運行時間最短的進(jìn)程優(yōu)先得到處理，其中包括新進(jìn)入系統(tǒng)的進(jìn)程 。就緒隊列（后備隊列）按照進(jìn)程（作業(yè)）的剩余運行時間的長短為序，選擇時選取隊列的隊首進(jìn)

8、程（作業(yè)）即為最短者，新入隊的進(jìn)程（作業(yè)）依據(jù)剩余運行時間的長短插入到隊列的合適位置。33精選PPT優(yōu)點：可以用于分時系統(tǒng)，保證及時響應(yīng)用戶要求 屬于可搶占策略，使短進(jìn)程一進(jìn)入系統(tǒng)就能立即得到服務(wù)，從而降低作業(yè)的平均等待時間缺點：系統(tǒng)開銷增加需要保存進(jìn)程的運行情況記錄，以比較其剩余時間大小搶占本身消耗處理器時間 34精選PPT最高響應(yīng)比優(yōu)先調(diào)度算法實現(xiàn)思想：綜合FCFS和短者優(yōu)先算法的特點 就緒隊列（后備隊列）按照進(jìn)程（作業(yè)）到來的先后次序為序，選擇時計算隊列全部進(jìn)程的響應(yīng)比，選擇最高響應(yīng)比的進(jìn)程（作業(yè)）運行。35精選PPT【例3-3】假設(shè)一個系統(tǒng)有4個進(jìn)程P1、P2、P3、P4，已知它們的到

9、達(dá)時間和運行時間，試用最高響應(yīng)比優(yōu)先算法進(jìn)行調(diào)度。 36精選PPT37精選PPT38精選PPTHRF的優(yōu)點：短進(jìn)程（作業(yè)）由于計算響應(yīng)比的分 母大而可以得到大的響應(yīng)比，優(yōu)先執(zhí)行，長進(jìn)程（作業(yè)）的響應(yīng)比會隨著等待時間的加長越來越大，得到執(zhí)行機(jī)會。39精選PPT時間片輪轉(zhuǎn)法實現(xiàn)思想：從就緒隊列中的每個運行指定的時間片，時間片到，無論是否運行完畢都執(zhí)行下一個進(jìn)程。就緒隊列（后備隊列）按照進(jìn)程（作業(yè)）到來的先后為序，選擇時選取隊列的隊首進(jìn)程（作業(yè)）運行一個時間片。40精選PPT【例3-4】設(shè)系統(tǒng)中有四個進(jìn)程P1，P2，P3，P4依次進(jìn)入系統(tǒng)，但彼此相差時間很小，可以近似看作“同時”到達(dá)。四個進(jìn)程分別需

10、要運行12，5，3和6個時間單位，時間片分別為1和4時系統(tǒng)運行的情形： 41精選PPT42精選PPT時間片的大小是關(guān)鍵過大：時間片輪轉(zhuǎn)法退化成先來先服務(wù)算法過?。禾幚砥髟谶M(jìn)程間的轉(zhuǎn)接工作過于頻繁，開銷變大，而處理器真正用于運行用戶程序的時間將會減少 43精選PPT優(yōu)先級調(diào)度算法實現(xiàn)思想：按照進(jìn)程（作業(yè)）的優(yōu)先級大小來調(diào)度，使高優(yōu)先級進(jìn)程（作業(yè)）得到優(yōu)先處理 就緒隊列（后備隊列）按照進(jìn)程（作業(yè)）的優(yōu)先級從高到低，選擇時選取隊列的隊首進(jìn)程（作業(yè)）即為優(yōu)先級最高的，新進(jìn)程據(jù)其優(yōu)先級大小入就緒隊列相應(yīng)位置44精選PPT進(jìn)程調(diào)度策略：非搶占優(yōu)先級調(diào)度搶占優(yōu)先級調(diào)度優(yōu)先級的確定：靜態(tài)優(yōu)先級動態(tài)優(yōu)先級45精

11、選PPT【例3-5】假設(shè)一個系統(tǒng)有5個進(jìn)程P1、P2、P3、P4、P5，已知它們的到達(dá)時間、運行時間和優(yōu)先數(shù)如表3-7所示，試用靜態(tài)優(yōu)先級調(diào)度算法進(jìn)行調(diào)度。 46精選PPT47精選PPT48精選PPT多級反饋隊列調(diào)度算法49精選PPT3.3 死鎖3.3.1死鎖的定義3.3.2產(chǎn)生死鎖的必要條件3.3.3對死鎖采取的對策50精選PPT交通死鎖 51精選PPT死鎖的定義死鎖，是指兩個或兩個以上的進(jìn)程，因競爭系統(tǒng)共享資源而產(chǎn)生的無止境地相互等待的狀態(tài)，此時計算機(jī)系統(tǒng)所處的狀態(tài)即處于死鎖狀態(tài)。陷入死鎖狀態(tài)的進(jìn)程稱之為死鎖進(jìn)程 52精選PPT例：現(xiàn)有兩個進(jìn)程PA和PB，各自按以下順序使用PV操作并行運行

12、，其中S1和S2分別代表系統(tǒng)中一臺打印機(jī)和一臺掃描儀的信號量，初值均為1進(jìn)程PA：P(S1)；P(S2)；V(S1)；V(S2)； 進(jìn)程PB：P(S2)；P(S1)；V(S2)；V(S1)； 53精選PPT產(chǎn)生死鎖的根本原因：資源有限進(jìn)程推進(jìn)的順序不合理54精選PPT產(chǎn)生死鎖的必要條件互斥條件：進(jìn)程訪問的臨界資源是互斥的不可搶占條件：一個資源僅能被占有它的進(jìn)程主動釋放，不能被其他進(jìn)程強(qiáng)行搶占。占有且申請：進(jìn)程在申請新資源的同時，保持對已有資源的占有。環(huán)路等待條件：存在一個進(jìn)程資源的環(huán)形鏈55精選PPT對死鎖采取的對策置之不理駝鳥策略運行前預(yù)防死鎖的預(yù)防。運行中避免死鎖的避免。運行中解除死鎖的檢

13、測與恢復(fù)。 56精選PPT3.4 死鎖的預(yù)防設(shè)法破壞產(chǎn)生死鎖的四個必要條件之一，從而保證系統(tǒng)不發(fā)生死鎖破壞互斥條件破壞不可搶占條件破壞占有且申請條件破壞環(huán)路等待條件此方法較容易實現(xiàn)，但由于所施加的限制往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。57精選PPT“資源一性分配策略”算法規(guī)定任一進(jìn)程必須預(yù)先申請所需要的全部資源，而且當(dāng)且僅當(dāng)該進(jìn)程的全部要求都能得到滿足時，系統(tǒng)才一次性分配，然后啟動該進(jìn)程運行 。58精選PPT“資源有序分配策略”算法把資源事先分類編號，按序分配，使進(jìn)程在申請、占用資源時不會形成環(huán)路。 59精選PPT3.5 死鎖的避免和銀行家算法3.5.1系統(tǒng)安全狀態(tài)3.5.

14、2銀行家算法3.5.3銀行家算法的例子60精選PPT系統(tǒng)安全狀態(tài)安全狀態(tài)是指系統(tǒng)中的所有進(jìn)程能按某種順序（P1，P2，Pn）分配其所需的資源，直到的有進(jìn)程都可以運行完畢。此進(jìn)程序列（P1，P2，Pn）稱為安全序列若存在這樣一個安全序列，則系統(tǒng)是安全的；否則，如果在系統(tǒng)中無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。61精選PPT死鎖與不安全狀態(tài)的關(guān)系62精選PPT銀行家算法基本思想：當(dāng)一個新的進(jìn)程進(jìn)入系統(tǒng)時，其所需要每種資源的最大數(shù)目，不能超過系統(tǒng)中資源的總數(shù)。當(dāng)用戶申請資源時，系統(tǒng)判斷此資源分配是否使系統(tǒng)仍處于安全狀態(tài)，若是則分配，否則該進(jìn)程等待，直到其他進(jìn)程釋放足夠的資源。 63精選P

15、PT使用的數(shù)據(jù)結(jié)構(gòu)：（系統(tǒng)中有n個進(jìn)程，m類資源）Available：長度為m的向量Availablej為系統(tǒng)中資源類Rj的當(dāng)前可用數(shù)（j=1,2,m)Max：nm階矩陣Mi,j=K表示進(jìn)程Pi需要Rj類資源最大數(shù)目為K。Allocation：nm階矩陣Allocationi,j=K，表示進(jìn)程Pi當(dāng)前已分得Rj類資源數(shù)為K。Need：nm階矩陣Needi,j=K，表示進(jìn)程Pi還需要Rj類資源數(shù)目為K顯然Needi,j=Maxi,j-Allocationi,j。64精選PPT銀行家算法設(shè)Requesti是進(jìn)程Pi提出的資源申請向量當(dāng)進(jìn)程Pi提出資源申請Requesti K時，按照銀行家算法，系統(tǒng)

16、將執(zhí)行下列步驟：1）若RequestiNeedi，轉(zhuǎn)2），否則錯誤返回。2）若RequestiAvailable，轉(zhuǎn)3），否則資源不足，進(jìn)程Pi需要等待。65精選PPT3）假設(shè)系統(tǒng)滿足Pi的請求為其分配資源，則：AvailableAvailable Requesti；AllocationiAllocationiRequesti；NeediNeediRequest i；4）執(zhí)行安全性算法，若系統(tǒng)新狀態(tài)是安全的，則分配完成；如果系統(tǒng)處于不安全狀態(tài)，那么進(jìn)程Pi等待Requesti，并且恢復(fù)到系統(tǒng)原來的狀態(tài)。66精選PPT安全性算法 1） Work=Available； Finishi=False，

17、i=1,2,n 2）存在Pi滿足：Finishi=False, NeediWork, 執(zhí)行3)；否則執(zhí)行4）。3）修改：Work=Work+Allocationi；Finishi=True；轉(zhuǎn)向2）。4）若所有：Finishi=True，i=1，2，n，則該系統(tǒng)處于安全狀態(tài)。否則處于不安全狀態(tài)。67精選PPT銀行家算法的優(yōu)點：采用死鎖動態(tài)策略，系統(tǒng)資源利用率提高了銀行家算法的缺點：要求被分配每類資源數(shù)量、客戶數(shù)固定不變，這在多道程序系統(tǒng)中是難以做到的。算法保證客戶請求在有限的時間內(nèi)得到滿足，但無法滿足實時客戶的快速響應(yīng)要求。尋找安全序列，增加了系統(tǒng)的開銷。68精選PPT銀行家算法的例子 【例3

18、-6】假設(shè)系統(tǒng)中有五個進(jìn)程P0，P1，P2，P3，P4和三種類型的資源A，B，C，每一種資源的數(shù)量分別為10、5、7,在T0時刻系統(tǒng)的資源分配情況如表：69精選PPTA，B，C=10，5，7T0時刻的資源分配表 資源情況進(jìn)程MAXAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P443300243170精選PPT（1）T0時刻的安全性：利用安全性算法有：Work=Available（3，3，2）；Finishi=False，i=1，2，3，4，5。1）有Finish1=False

19、，Need1Work，即（1，2，2）（3，3，2），所以Work=Work+Allocation（3，3，2）+（2，0，0）（5，3，2）；Finish1=True。2）有Finish3=False，Need3Work，即（0，1，1）（5，3，2），所以Work=Work+Allocation（5，3，2）+（2，1，1）（7，4，3）；Finish3=True。3）有Finish4=False，Need4Work，即（4，3，1）（7，4，3），所以Work=Work+Allocation（7，4，3）+（0，0，2）（7，4，5）；Finish4=True。4）有Finish2=Fa

20、lse，Need2Work，即（6，0，0）（7，4，5），所以Work=Work+Allocation（7，4，5）+（3，0，2）（10，4，7）；Finish2=True。5）有Finish0=False，Need0Work，即（7，4，3）（10，4，7），所以Work=Work+Allocation（10，4，7）+（0，1，0）（10，5，7）；Finish0=True。 所以，有安全序列P1，P3，P4，P2，P0，使得對i=1，2，3，4，5，均有Finishi=True，則T0時刻該系統(tǒng)處于安全狀態(tài)。 71精選PPT安全性算法的計算可簡化為下表：T0時刻的安全序列WorkNe

21、edAllocationWork+AllocationFinishABCABCABCABCP1332122200532TrueP3532011211743TrueP4743431002745TrueP27456003021047TrueP010477430101057True72精選PPT（2）P1請求資源Request1（1，0，2） 對于P1的請求，按照銀行家算法有：1）Request1（1，0，2）Need1（1，2，2）。2）Request1（1，0，2）Available（3，3，2）。3）假設(shè)滿足P1的請求為其分配資源，則：AvailableAvailable Request1（3

22、，3，2）（1，0，2）（2，3，0）；AllocationiAllocationiRequesti（2，0，0）+（1，0，2）（3，0，2）；NeediNeediRequest i（1，2，2）（1，0，2）（0，2，0）；由此形成的系統(tǒng)資源分配情況表。73精選PPT P1申請資源時的資源分配表 MAXAllocationNeedAvailableABCABCABCABCP0753010743 230( 332)P1322302(2 00)020(122)P2902302600P3222211011P443300243174精選PPT執(zhí)行安全性算法，檢測新狀態(tài)是否安全P1申請資源時的安全性

23、檢查存在安全序列P1，P3，P4，P0，P2，因此，系統(tǒng)在將資源分配給P1后是安全的，故可以立即將P1所申請的資源分配給它。WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532TrueP3532011211743TrueP4743431002745TrueP0745743010755TrueP27556003021057True75精選PPT（3）P4請求資源Request4（3，3，0） 對于P4的請求，按照銀行家算法有：1）Request4（3，3，0）Need4（4，3，1）。2）Request4（3，3，0）

24、Available（2，3，0），故讓P4等待。 76精選PPT（4）P0請求資源Request0（0，2，0），按照銀行家算法有：1）Request0（0，2，0）Need0（7，4，3）。2）Request0（0，2，0）Available（2，3，0）。3）假設(shè)滿足P0的請求，則：AvailableAvailable Request0（2，3，0）（0，2，0）（2，1，0）；Allocation0Allocation0Request0（0，1，0）+（0，2，0）（0，3，0）；Need0Need0Request 0（7，4，3）（0，2，0）（7，2，3）；77精選PPT P0申請資

25、源時的資源分配表 MAXAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P443300243178精選PPT4）利用安全性算法，檢測此時系統(tǒng)是否安全。從表中可以看出：可用資源Available（2，1，0）已經(jīng)不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)。因此，系統(tǒng)不能滿足進(jìn)程P0申請資源的請求，為其分配資源。 79精選PPT【練習(xí)3-1】1）該狀態(tài)是否安全？2）如果進(jìn)程P2提出Request2（1，2，2，2）后，系統(tǒng)能否將資源分配給它？為什么？AllocationNeedAv

26、ailableP0003200121622P110001750P213542356P303320652P40014065680精選PPT3.6 死鎖的檢測與解除3.6.1死鎖的檢測3.6.2死鎖檢測的時機(jī)3.6.3死鎖的恢復(fù)81精選PPT死鎖檢測與恢復(fù)：是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來。 82精選PPT死鎖的檢測檢測死鎖實質(zhì)上是確定是否存在環(huán)路等待，一旦發(fā)現(xiàn)這種環(huán)路便認(rèn)定死鎖存在，并識別出該環(huán)路所涉及的有關(guān)進(jìn)程，以供系統(tǒng)采用適當(dāng)?shù)拇胧﹣斫獬梨i。83精選PPT資源分配圖 84精選PPT死鎖定理：如果資源分配圖中不存在環(huán)路，則系統(tǒng)不存在死鎖；反之，如果資源分配圖中存在環(huán)路，則系統(tǒng)中可能存在死鎖，也可能不存在死鎖。 85精選PPT圖中存在著兩個環(huán)路：P1R1P2R3P3R2P1P2R3P3R2P2分析