學(xué)院:計算機與信息技術(shù)學(xué)院教師:劉賢梅第三章處理機調(diào)度與死鎖2/4/20231內(nèi)容概述3.1處理機調(diào)度的層次

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

3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則

3.3調(diào)度算法3.4實時調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除

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

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

3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則

3.3調(diào)度算法

3.4實時調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除

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

92.8平均值:

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

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

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

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

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

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

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

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

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

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

PB:申請次序應(yīng)是:R1,R2

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

(1)可利用資源向量Available

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

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

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

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

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

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

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

五個進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝各種資源的數(shù)量分別為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},故系統(tǒng)是安全的。2/4/202367(2)P1請求資源:P1發(fā)出請求向量Request1(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available(3,3,2)③系統(tǒng)先假定可為P1分配資源,并修改Available,Allocation1和Need1向量,由此形成的資源變化情況如圖中的圓括號所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。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},故系統(tǒng)是安全的,可以分配。2/4/202369(3)P4請求資源:P4發(fā)出請求向量Request4(3,3,0),系統(tǒng)按銀行家算法進(jìn)行檢查:①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),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統(tǒng)暫時先假定可為P0分配資源,并修改有關(guān)數(shù)據(jù),如圖所示。2/4/202370最大需求已分配 可用資源(Max)(Allocation) (Available)P0753030

210

P1322302P2902302P3222211P4433002723還需要(Need)020600011431Work=Available=(2,1,0)Finish[]不能滿足任何進(jìn)程的需要,故系統(tǒng)進(jìn)入不安全狀態(tài),此時系統(tǒng)不能分配資源給P0。2/4/202371(5)P0請求資源:P0發(fā)出請求向量Request0(0,1,0),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request0(0,1,0)≤Need0(7,4,3)②Request0(0,1,0)≤Available(2,3,0)③系統(tǒng)先假定可為P0分配資源,并修改Available,Allocation0和Need0向量,如下所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。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},故系統(tǒng)是安全的,可以分配。2/4/202373內(nèi)容概述3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除

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