第三章計算機操作系統處理機調度與死鎖

學院:計算機與信息技術學院教師:劉賢梅第三章處理機調度與死鎖2/4/20231內容概述3.1處理機調度的層次

3.2調度隊列模型和調度準則3.3調度算法3.4實時調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除處理機調度的主要任務是分配處理機。在多道程序環(huán)境下,進程數目通常多于處理機的數目。系統必須按一定方法動態(tài)地把處理機分配給就緒隊列中的一個進程。處理機利用率和系統性能(吞吐量、響應時間)在很大程度上取決于處理機調度。2/4/202323.1處理機調度的層次3.1.1高級調度3.1.2低級調度3.1.3中級調度2/4/202333.1.1高級調度1.高級調度的含義又稱為作業(yè)調度或長程調度：將外存上處于后備隊列上的作業(yè)調入內存，并創(chuàng)建進程、分配資源，安排在就緒隊列上。2.作業(yè)程序、數據和作業(yè)說明書。以作業(yè)為單位從外存調入內存。2/4/202343.作業(yè)控制塊JCB是作業(yè)在系統中存在的標志。JCB包含的內容：作業(yè)標識用戶名稱、用戶賬戶作業(yè)類型（CPU繁忙型、I/O繁忙型等）、作業(yè)狀態(tài)調度信息（優(yōu)先級、已運行時間）資源需求（預計運行時間、內存大小、I/O設備類型等）進入系統時間、開始處理時間、作業(yè)完成時間、作業(yè)推出時間資源使用情況2/4/202354.作業(yè)調度在每次執(zhí)行作業(yè)調度時，都須做出以下兩個決定：(1)接納多少個作業(yè)取決于多道程序度，即允許多少個作業(yè)同時在內存中運行。作業(yè)太少資源利用率低作業(yè)太多服務質量下降(2)接納哪些作業(yè)：作業(yè)調度算法先來先服務短作業(yè)優(yōu)先優(yōu)先權高優(yōu)先2/4/202363.1處理機調度的層次3.1.1高級調度3.1.2低級調度3.1.3中級調度2/4/202373.1.2低級調度1.低級調度的含義也稱為進程調度或短程調度，決定就緒隊列中的哪個進程應獲得處理機。2.低級調度的功能保存處理機的現場信息按照某種算法選取進程把處理機分配給進程（恢復處理機現場）2/4/202383.進程調度方式(1)非搶占方式(非剝奪方式)(2)搶占方式（剝奪方式)搶占原則優(yōu)先權原則短作業(yè)(進程)優(yōu)先原則時間片原則2/4/202393.1處理機調度的層次3.1.1高級調度3.1.2低級調度3.1.3中級調度2/4/202310中級調度又稱中程調度為了提高內存利用率和系統吞吐量暫時不能運行的進程，而將它們調至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件、且內存又稍有空閑時,由中級調度來決定把外存上的哪些又具備運行條件的就緒進程,重新調入內存,并修改其狀態(tài)為就緒狀態(tài),掛在就緒隊列上等待進程調度3.1.3中級調度對換功能2/4/202311內容概述3.1處理機調度的層次

3.2調度隊列模型和調度準則

3.3調度算法3.4實時調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除

2/4/2023123.2.1調度隊列模型3.2.2選擇調度方式和調度算法的若干準則3.2調度隊列模型和調度準則2/4/2023133.2.1調度隊列模型1.僅有進程調度的調度隊列模型圖3-1僅具有進程調度的調度隊列模型①②③2/4/2023142.具有高級和低級調度的調度隊列模型圖3-2具有高、低兩級調度的調度隊列模型①②③2/4/2023153.同時具有三級調度的調度隊列模型

圖3-3具有三級調度時的調度隊列模型①②③2/4/2023163.2.1調度隊列模型3.2.2選擇調度方式和調度算法的若干準則3.2調度隊列模型和調度準則2/4/2023173.2.2選擇調度方式和調度算法的若干準則1.面向用戶的準則(1)周轉時間短(2)響應時間快(3)截止時間保證(4)優(yōu)先權準則作業(yè)周轉時間：作業(yè)在外存后備隊列上等待作業(yè)調度的時間進程在就緒隊列上等待進程調度的時間進程在CPU上執(zhí)行的時間進程等待I/O操作完成的時間平均周轉時間：平均帶權周轉時間：2/4/2023182.面向系統的準則(1)系統吞吐量高吞吐量指單位時間內系統所完成的作業(yè)數作業(yè)調度的方式和算法對吞吐量的大小有較大影響(2)處理機利用率高(3)各類資源的平衡利用使內存、外存和I/O設備的利用率高2/4/202319內容概述3.1處理機調度的層次

3.2調度隊列模型和調度準則

3.3調度算法

3.4實時調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除

2/4/2023203.2.1先來先服務和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權優(yōu)先調度算法3.2.3基于時間片的輪轉調度算法3.2調度算法2/4/2023213.2.1先來先服務和短作業(yè)(進程)優(yōu)先調度算法1.先來先服務調度算法(FCFS)按照作業(yè)進入系統的先后次序進行調度，先進入系統者先調度；即啟動等待時間最長的作業(yè)。是一種最簡單的調度算法，即可用于作業(yè)調度，也可用于進程調度。FCFS算法比較有利于長作業(yè)(進程),而不利于短作業(yè)(進程)。2/4/202322內存無限大，作業(yè)調度和進程調度都采用FCFS。作業(yè)名進入磁盤需要服務裝入主存開始執(zhí)行結束執(zhí)行周轉帶權周轉 時間 時間時間時間時間時間時間A 01 B 1 100 C 2 1 D 3 100 執(zhí)行順序:A->B->C->D周轉時間=結束執(zhí)行時間-進入磁盤時間帶權周轉時間=周轉時間/服務時間00111131101100121022021991.99101102100100先來先服務調度算法(FCFS)平均值:10025.99752/4/2023232.短作業(yè)(進程)優(yōu)先調度算法SJ(P)F對短作業(yè)或短進程優(yōu)先調度的算法?？梢苑謩e用于作業(yè)調度和進程調度。調度過程SJF：從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調入內存運行。SPF：從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調度。2/4/2023241）內存無限大,作業(yè)調度和進程調度都采用FCFS作業(yè)名進入磁盤需要服務裝入主存開始執(zhí)行結束執(zhí)行周轉帶權周轉 時間 時間時間時間時間時間時間A 04 B 1 3 C 2 5 D 3 2 E 4 4執(zhí)行順序:A->B->C->D->E2）作業(yè)調度和進程調度都采用SJFA 04 B 1 3 C 2 5 D 3 2 E 4 4周轉時間=結束執(zhí)行時間-進入磁盤時間帶權周轉時間=周轉時間/服務時間0044113476221214115.5712102短作業(yè)(進程)優(yōu)先調度算法SJ(P)F41418143.500441136988/324631.513181616/5491399/4平均值:

92.8平均值:

82.1執(zhí)行順序:A->D->B->E->C2/4/202325SJ(P)F調度算法也存在不容忽視的缺點:(1)該算法對長作業(yè)不利。由于調度程序總是優(yōu)先調度那些(即使是后進來的)短作業(yè)(進程),將導致長作業(yè)(進程)長期不被調度。(2)該算法完全未考慮作業(yè)的緊迫程度,因而不能保證緊迫性作業(yè)(進程)會被及時處理。(3)由于作業(yè)(進程)的長短只是根據用戶所提供的估計執(zhí)行時間而定的,而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間,致使該算法不一定能真正做到短作業(yè)優(yōu)先調度。2/4/2023263.2.1先來先服務和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權優(yōu)先調度算法3.2.3基于時間片的輪轉調度算法3.2調度算法2/4/2023273.2.2高優(yōu)先權優(yōu)先調度算法1.優(yōu)先權調度算法的類型

(1)非搶占式優(yōu)先權算法主要用于批處理系統中，也可用于某些對實時性要求不嚴的實時系統中。(2)搶占式優(yōu)先權調度算法能更好地滿足緊迫作業(yè)的要求,故而常用于要求比較嚴格的實時系統中,以及對性能要求較高的批處理和分時系統中。2/4/2023282.優(yōu)先權的類型(1)靜態(tài)優(yōu)先權在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。一般地。(2)動態(tài)優(yōu)先權在創(chuàng)建進程時所賦予的優(yōu)先權,是可以隨進程的推進或隨其等待時間的增加而改變的,以便獲得更好的調度性能。2/4/2023293.高響應比優(yōu)先調度算法(HRF)該算法是FCFS和SJF的結合，克服了兩種算法的缺點。響應比最高的作業(yè)優(yōu)先啟動由于等待時間與服務時間之和,就是系統對該作業(yè)的響應時間，故該優(yōu)先權又相當于響應比RP。據此，又可表示為2/4/202330對高響應比優(yōu)先調度算法(HRF)的解釋(1)如果作業(yè)的等待時間相同,則要求服務的時間愈短,其優(yōu)先權愈高,因而該算法有利于短作業(yè)。(2)當要求服務的時間相同時,作業(yè)的優(yōu)先權決定于其等待時間,等待時間愈長,其優(yōu)先權愈高,因而它實現的是先來先服務。(3)對于長作業(yè),作業(yè)的優(yōu)先級可以隨等待時間的增加而提高,當其等待時間足夠長時,其優(yōu)先級便可升到很高,從而也可獲得處理機。2/4/2023313.2.1先來先服務和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權優(yōu)先調度算法3.2.3基于時間片的輪轉調度算法3.2調度算法2/4/2023323.2.3基于時間片的輪轉調度算法

1.時間片輪轉法就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。當執(zhí)行的時間片用完時，停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片?？梢员ＷC就緒隊列中的所有進程,在一給定的時間內,均能獲得一時間片的處理機執(zhí)行時間。2/4/202333圖3-5多級反饋隊列調度算法2.多級反饋隊列調度算法優(yōu)先級高2/4/202334設置多個就緒隊列,并為各個隊列賦予不同的優(yōu)先級，各隊列的優(yōu)先權逐個降低。各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。調度方式當一個新進程進入內存后,首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執(zhí)行時,如它能在該時間片內完成,便可準備撤離系統;如果它在一個時間片結束時尚未完成,調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列,……,如此下去，當一個長作業(yè)(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉的方式運行。2/4/202335僅當第一隊列空閑時,調度程序才調度第二隊列中的進程運行;僅當第1~(i-1)隊列均空時,才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時,又有新進程進入優(yōu)先權較高的隊列(第1~(i-1)中的任何一個隊列),則此時新進程將搶占正在運行進程的處理機,即由調度程序把正在運行的進程放回到第i隊列的末尾,把處理機分配給新到的高優(yōu)先權進程。2/4/2023363.多級反饋隊列調度算法的性能(1)終端型作業(yè)用戶終端型作業(yè)用戶所提交的作業(yè)多屬于交互型作業(yè)，通常較小，系統只要能使這些作業(yè)在第一隊列所規(guī)定的時間片內完成即可。(2)短批處理作業(yè)用戶若在第1隊列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應時間。如在第一個隊列中不能完成，只需在第2、3隊列中各執(zhí)行一個時間片。(3)長批處理作業(yè)用戶長作業(yè)將依次在第1,2,3…,n隊列中執(zhí)行，最終按輪轉方式運行。2/4/202337內容概述3.1處理機調度的層次3.2調度隊列模型和調度準則3.3調度算法3.4實時調度3.5產生死鎖的原因和必要條件

3.6預防死鎖的方法3.7死鎖的檢測與解除2/4/2023383.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因3.5.2產生死鎖的必要條件3.5.3處理死鎖的基本方法2/4/2023393.5.1產生死鎖的原因1.競爭資源引起進程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進程在獲得這類資源后，該資源可以再被其他進程或系統剝奪，如處理機、內存等。不可剝奪性資源是指當系統把這類資源分配給某個進程后，再不能強行收回，只能在進程用完后自行釋放，如磁帶機、打印機等。競爭非剝奪性資源系統中的非剝奪性資源由于數量有限而不能滿足進程運行的需要，進程在運行過程中因爭奪這些資源而限入僵局。2/4/202340圖3-12I/O設備共享時的死鎖情況請求請求配分已配分已2/4/202341圖3-13進程之間通信時的死鎖競爭臨時性資源臨時性資源區(qū)別于永久性資源，指由一個進程產生，被另一進程使用后就再也無用的資源，也稱為消耗性資源。申請釋放申請釋放申請釋放2/4/2023422.進程推進順序不當引起死鎖

圖3-14進程推進順序對死鎖的影響P1進程進度P2進程進度2/4/202343若并發(fā)進程P1和P2按曲線④所示的順序推進，它們將進入不安全區(qū)D內。此時P1保持了資源R1，P2保持了資源R2，系統處于不安全狀態(tài)。因為，這時兩進程再向前推進，便可能發(fā)生死鎖。例如，當P1運行到P1;Request(R2)時，將因R2已被P2占用而阻塞；當P2運行到P2;Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進程死鎖。2/4/2023443.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因3.5.2產生死鎖的必要條件3.5.3處理死鎖的基本方法2/4/2023453.5.2產生死鎖的必要條件1.互斥條件進程對所分配到的資源進行排它性的使用。臨界(獨占)資源,即一次只有一個進程可以使用資源。2.請求和保持條件進程已經至少保持了一個資源,但又提出了新的資源請求,而該資源又已被其他進程占有。3.不剝奪條件進程已獲得的資源在未使用完之前不能被剝奪。4.環(huán)路等待條件在發(fā)生死鎖時,必然存在一個進程--資源的環(huán)形鏈。當計算機系統同時具備下面4個必要條件時,會發(fā)生死鎖。只要有一個必要條件不滿足,則死鎖就可以排除。2/4/2023463.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因3.5.2產生死鎖的必要條件3.5.3處理死鎖的基本方法2/4/2023473.5.3處理死鎖的基本方法(1)預防死鎖。 通過設置限制條件,破壞產生死鎖的必要條件的一個或幾個。(2)避免死鎖。在分配資源時,用某種方法防止系統進入不安全的狀態(tài)。(3)檢測死鎖。確定與死鎖有關的進程和資源,采取措施,清除死鎖。(4)解除死鎖。與檢測死鎖配套的一種措施。2/4/202348內容概述3.1處理機調度的基本概念3.2調度算法3.3實時調度3.4多處理機系統中的調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法

3.7死鎖的檢測與解除2/4/2023493.6預防死鎖的方法3.6.1預防死鎖3.6.2系統安全狀態(tài)3.6.3利用銀行家算法避免死鎖2/4/2023503.6.1預防死鎖摒棄“請求和保持”條件摒棄“不剝奪”條件摒棄“環(huán)路等待”條件原理：該方法是通過對資源分配的原則進行限制，從而使產生死鎖的四個必要條件中的第2、3、4個條件之一不能成立，來預防產生死鎖。

互斥：這個條件不可能被禁止。2/4/202351預防死鎖1.摒棄“請求和保持”條件所有進程在開始運行之前必須一次性的申請整個運行過程所需的全部資源。優(yōu)點:簡單、易于實現、安全。缺點:(1)資源浪費嚴重

(2)進程延遲運行2/4/202352預防死鎖2.摒棄“不剝奪”條件系統規(guī)定:進程逐個地申請所需資源當一個已經保持了某些資源的進程申請新資源而不能得到滿足時,必須放棄所有已保持的資源實現復雜、代價高昴(例如:打印機)2/4/202353預防死鎖3.摒棄“環(huán)路等待”條件系統將所有資源按類型分配序號并排隊(例如打印機為1、磁帶機為2、磁盤為3、等等)。所有進程申請資源必須按序號遞增的順序對比前兩種方法:資源利用率和系統吞吐量較高缺點:(1)序號固定,限制了新設備類型的增加

(2)資源浪費(不像前邊那么嚴重,考慮進程使用資源順序了)(3)限制用戶自由編程(因限制了序號)2/4/202354例如:進程PA,使用資源的順序是R1,R2;

進程PB,使用資源的順序是R2,R1;若采用無限制條件,有可能形成環(huán)路條件,造成死鎖。采用有序資源分配法:R1的編號為1,R2的編號為2;PA:申請次序應是:R1,R2

PB:申請次序應是:R1,R2

這樣就破壞了環(huán)路條件,避免了死鎖的發(fā)生。2/4/2023553.6預防死鎖的方法3.6.1預防死鎖3.6.2系統安全狀態(tài)3.6.3利用銀行家算法避免死鎖2/4/2023561.安全狀態(tài)避免死鎖：允許進程動態(tài)地申請資源,但系統在進行資源分配之前,應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態(tài),則將資源分配給進程;否則,令進程等待。安全狀態(tài)：指系統能按某種進程順序(P1,P2,…,Pn)(稱〈P1,P2,…,Pn〉序列為安全序列),來為每個進程Pi分配其所需資源,直至滿足每個進程對資源的最大需求,使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列,則稱系統處于不安全狀態(tài)。3.6.2系統安全狀態(tài)2/4/2023572.安全狀態(tài)之例假定系統中有三個進程P1、P2和P3,共有12臺磁帶機。進程P1總共要求10臺磁帶機,P2和P3分別要求4臺和9臺。假設在T0時刻,進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機,尚有3臺空閑未分配,如下表所示:進程最大需求已分配可用P1P2P310495223安全序列<P2，P1，P3>2/4/2023583.由安全狀態(tài)向不安全狀態(tài)的轉換如果不按照安全序列分配資源,則系統可能會由安全狀態(tài)進入不安全狀態(tài)。例如,在T0時刻以后,P3又請求1臺磁帶機,若此時系統把剩余3臺中的1臺分配給P3,則系統便進入不安全狀態(tài)。因為,此時也無法再找到一個安全序列,例如,把其余的2臺分配給P2,這樣,在P2完成后只能釋放出4臺,既不能滿足P1尚需5臺的要求,也不能滿足P3尚需6臺的要求,致使它們都無法推進到完成,彼此都在等待對方釋放資源,即陷入僵局,結果導致死鎖。2/4/2023593.6預防死鎖的方法3.6.1預防死鎖3.6.2系統安全狀態(tài)3.6.3利用銀行家算法避免死鎖2/4/2023603.6.3利用銀行家算法避免死鎖1.銀行家算法中的數據結構

(1)可利用資源向量Available

這是一個含有m個元素的數組,其中的每一個元素代表一類可利用的資源數目,其初始值是系統中所配置的該類全部可用資源的數目,其數值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K,則表示系統中現有Rj類資源K個。(2)最大需求矩陣Max

這是一個n×m的矩陣,它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K,則表示進程i需要Rj類資源的最大數目為K。2/4/202361(3)分配矩陣Allocation

這也是一個n×m的矩陣,它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K,則表示進程i當前已分得Rj類資源的數目為K(4)需求矩陣Need

這也是一個n×m的矩陣,用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K,則表示進程i還需要Rj類資源K個,方能完成其任務

Need[i,j]=Max[i,j]-Allocation[i,j]2/4/2023622.銀行家算法

設Requesti是進程Pi的請求向量,如果Requesti(1,0,2),表示進程Pi需要1個R1類型的資源,需要0個R2類型的資源,需要2個R3類型的資源。當Pi發(fā)出資源請求后,系統按下述步驟進行檢查:(1)如果Requesti≤Needi,便轉向步驟2;否則認為出錯,因為它所需要的資源數已超過它所宣布的最大值。(2)如果Requesti≤Available,便轉向步驟(3);否則,表示尚無足夠資源,Pi須等待。2/4/202363(3)系統試探著把資源分配給進程Pi,并修改下面數據結構中的數值; Available:=Available-Requesti; Allocationi:=Allocationi+Requesti; Needi:=Needi-Requesti;(4)系統執(zhí)行安全性算法,檢查此次資源分配后,系統是否處于安全狀態(tài)。若安全,才正式將資源分配給進程Pi,以完成本次分配;否則,將本次的試探分配作廢,恢復原來的資源分配狀態(tài),讓進程Pi等待。2/4/2023643.安全性算法(1)設置兩個向量初值;①工作向量Work;它表示系統可提供給進程繼續(xù)運行所需的各類資源數目,它含有m個元素,在執(zhí)行安全算法開始時,Work:=Available;②Finish[];它表示系統是否有足夠的資源分配給進程,使之運行完成。開始時先做Finish[i]:=false;當有足夠資源分配給進程時,再令Finish[i]:=true2/4/202365(2)從進程集合中找到一個能滿足下述條件的進程;①Finish[i]=false;②Needi≤Work;若找到,執(zhí)行步驟(3),否則,執(zhí)行步驟(4)(3)當進程Pi獲得資源后,可順利執(zhí)行,直至完成,并釋放出分配給它的資源,故應執(zhí)行;

Work:=Work+Allocation;Finish[i]:=true;gotostep2;(4)如果所有進程的Finish[i]=true都滿足,則表示系統處于安全狀態(tài);否則,系統處于不安全狀態(tài)2/4/202366最大需求已分配 可用資源(Max)(Allocation) (Available)P0753010 332P1322200P2902302P3222211P4433002743還需要(Need)1226000114314.銀行家算法之例

五個進程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝各種資源的數量分別為10、5、7。(1)在T0時刻的安全性：Work=Available=(3,3,2)Finish[]分配給P1,完成后Work=(5,3,2)ture分配給P3,完成后Work=(7,4,3)ture分配給P4,完成后Work=(7,4,5)ture分配給P0,完成后Work=(7,5,5)ture分配給P2,完成后Work=(10,5,7)ture在該時刻存在著一個安全序列{P1，P3，P4，P0,P2},故系統是安全的。2/4/202367(2)P1請求資源:P1發(fā)出請求向量Request1(1,0,2),系統按銀行家算法進行檢查:①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available(3,3,2)③系統先假定可為P1分配資源,并修改Available,Allocation1和Need1向量,由此形成的資源變化情況如圖中的圓括號所示。④再利用安全性算法檢查此時系統是否安全。2/4/202368最大需求已分配 可用資源(Max)(Allocation) (Available)P0753010 230

P1322302

P2902302P3222211P4433002743還需要(Need)020600011431Work=Available=(2,3,0)Finish[]分配給P1,完成后Work=(5,3,2)ture分配給P3,完成后Work=(7,4,3)ture分配給P4,完成后Work=(7,4,5)ture分配給P0,完成后Work=(7,5,5)ture分配給P2,完成后Work=(10,5,7)ture在該時刻存在著一個安全序列{P1，P3，P4，P0,P2},故系統是安全的,可以分配。2/4/202369(3)P4請求資源:P4發(fā)出請求向量Request4(3,3,0),系統按銀行家算法進行檢查:①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≥Available(2,3,0),讓P4等待。(4)P0請求資源:P0發(fā)出請求向量Requst0(0,2,0),系統按銀行家算法進行檢查:①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統暫時先假定可為P0分配資源,并修改有關數據,如圖所示。2/4/202370最大需求已分配 可用資源(Max)(Allocation) (Available)P0753030

210

P1322302P2902302P3222211P4433002723還需要(Need)020600011431Work=Available=(2,1,0)Finish[]不能滿足任何進程的需要,故系統進入不安全狀態(tài),此時系統不能分配資源給P0。2/4/202371(5)P0請求資源:P0發(fā)出請求向量Request0(0,1,0),系統按銀行家算法進行檢查:①Request0(0,1,0)≤Need0(7,4,3)②Request0(0,1,0)≤Available(2,3,0)③系統先假定可為P0分配資源,并修改Available,Allocation0和Need0向量,如下所示。④再利用安全性算法檢查此時系統是否安全。2/4/202372最大需求已分配 可用資源(Max)(Allocation) (Available)P0753020

220

P1322302P2902302P3222211P4433002733還需要(Need)020600011431Work=Available=(2,2,0)Finish[]分配給P1,完成后Work=(5,2,2)ture分配給P3,完成后Work=(7,3,3)ture分配給P4,完成后Work=(7,3,5)ture分配給P0,完成后Work=(7,5,5)ture分配給P2,完成后Work=(10,5,7)ture在該時刻存在著一個安全序列{P1，P3，P4，P0,P2},故系統是安全的,可以分配。2/4/202373內容概述3.1處理機調度的基本概念3.2調度算法3.3實時調度3.4多處理機系統中的調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除

2/4/2023743.7死鎖的檢測與解除3.7.1死鎖的檢測3.7.2死鎖的解除2/4/2023753.7.1死鎖的檢測1.資源分配圖(ResourceAllocationGraph)由一組結點N和一組邊E組成的一個對偶G=(N,E)把N分為兩個互斥的子集,即一組進程結點P={p1,p2,…,pn}和一組資源結點R={r1,r2,…,rn},N=P∪R凡屬于E中的一個邊e∈E,都連著P中的一個結點和R中的一個結點,e={pi,rj}