第三章計(jì)算機(jī)操作系統(tǒng)處理機(jī)調(diào)度與死鎖

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

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

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

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

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

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

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

3.3調(diào)度算法

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

2/4/2023203.2.1先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法2/4/2023213.2.1先來(lái)先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法1.先來(lái)先服務(wù)調(diào)度算法(FCFS)按照作業(yè)進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長(zhǎng)的作業(yè)。是一種最簡(jiǎn)單的調(diào)度算法，即可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。FCFS算法比較有利于長(zhǎng)作業(yè)(進(jìn)程),而不利于短作業(yè)(進(jìn)程)。2/4/202322內(nèi)存無(wú)限大，作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS。作業(yè)名進(jìn)入磁盤(pán)需要服務(wù)裝入主存開(kāi)始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時(shí)間 時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間A 01 B 1 100 C 2 1 D 3 100 執(zhí)行順序:A->B->C->D周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤(pán)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間00111131101100121022021991.99101102100100先來(lái)先服務(wù)調(diào)度算法(FCFS)平均值:10025.99752/4/2023232.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。調(diào)度過(guò)程SJF：從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。SPF：從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。2/4/2023241）內(nèi)存無(wú)限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤(pán)需要服務(wù)裝入主存開(kāi)始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時(shí)間 時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間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)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤(pán)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間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)度算法也存在不容忽視的缺點(diǎn):(1)該算法對(duì)長(zhǎng)作業(yè)不利。由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來(lái)的)短作業(yè)(進(jìn)程),將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度,因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。(3)由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的,而用戶又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間,致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。2/4/2023263.2.1先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(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)中，也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。(2)搶占式優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求,故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中,以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。2/4/2023282.優(yōu)先權(quán)的類型(1)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地。(2)動(dòng)態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán),是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的,以便獲得更好的調(diào)度性能。2/4/2023293.高響應(yīng)比優(yōu)先調(diào)度算法(HRF)該算法是FCFS和SJF的結(jié)合，克服了兩種算法的缺點(diǎn)。響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)由于等待時(shí)間與服務(wù)時(shí)間之和,就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為2/4/202330對(duì)高響應(yīng)比優(yōu)先調(diào)度算法(HRF)的解釋(1)如果作業(yè)的等待時(shí)間相同,則要求服務(wù)的時(shí)間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短作業(yè)。(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí),作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間,等待時(shí)間愈長(zhǎng),其優(yōu)先權(quán)愈高,因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。(3)對(duì)于長(zhǎng)作業(yè),作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高,當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí),其優(yōu)先級(jí)便可升到很高,從而也可獲得處理機(jī)。2/4/2023313.2.1先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法2/4/2023323.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

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

3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除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ìng)爭(zhēng)資源引起進(jìn)程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪，如處理機(jī)、內(nèi)存等。不可剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給某個(gè)進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放，如磁帶機(jī)、打印機(jī)等。競(jìng)爭(zhēng)非剝奪性資源系統(tǒng)中的非剝奪性資源由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要，進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪這些資源而限入僵局。2/4/202340圖3-12I/O設(shè)備共享時(shí)的死鎖情況請(qǐng)求請(qǐng)求配分已配分已2/4/202341圖3-13進(jìn)程之間通信時(shí)的死鎖競(jìng)爭(zhēng)臨時(shí)性資源臨時(shí)性資源區(qū)別于永久性資源，指由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用后就再也無(wú)用的資源，也稱為消耗性資源。申請(qǐng)釋放申請(qǐng)釋放申請(qǐng)釋放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)。此時(shí)P1保持了資源R1，P2保持了資源R2，系統(tǒng)處于不安全狀態(tài)。因?yàn)?，這時(shí)兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運(yùn)行到P1;Request(R2)時(shí)，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)行到P2;Request(R1)時(shí)，也將因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)程對(duì)所分配到的資源進(jìn)行排它性的使用。臨界(獨(dú)占)資源,即一次只有一個(gè)進(jìn)程可以使用資源。2.請(qǐng)求和保持條件進(jìn)程已經(jīng)至少保持了一個(gè)資源,但又提出了新的資源請(qǐng)求,而該資源又已被其他進(jìn)程占有。3.不剝奪條件進(jìn)程已獲得的資源在未使用完之前不能被剝奪。4.環(huán)路等待條件在發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程--資源的環(huán)形鏈。當(dāng)計(jì)算機(jī)系統(tǒng)同時(shí)具備下面4個(gè)必要條件時(shí),會(huì)發(fā)生死鎖。只要有一個(gè)必要條件不滿足,則死鎖就可以排除。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ù)防死鎖。 通過(guò)設(shè)置限制條件,破壞產(chǎn)生死鎖的必要條件的一個(gè)或幾個(gè)。(2)避免死鎖。在分配資源時(shí),用某種方法防止系統(tǒng)進(jìn)入不安全的狀態(tài)。(3)檢測(cè)死鎖。確定與死鎖有關(guān)的進(jìn)程和資源,采取措施,清除死鎖。(4)解除死鎖。與檢測(cè)死鎖配套的一種措施。2/4/202348內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法

3.7死鎖的檢測(cè)與解除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ù)防死鎖摒棄“請(qǐng)求和保持”條件摒棄“不剝奪”條件摒棄“環(huán)路等待”條件原理：該方法是通過(guò)對(duì)資源分配的原則進(jìn)行限制，從而使產(chǎn)生死鎖的四個(gè)必要條件中的第2、3、4個(gè)條件之一不能成立，來(lái)預(yù)防產(chǎn)生死鎖。

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

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

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

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

PB:申請(qǐng)次序應(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)程動(dòng)態(tài)地申請(qǐng)資源,但系統(tǒng)在進(jìn)行資源分配之前,應(yīng)先計(jì)算此次資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài),則將資源分配給進(jìn)程;否則,令進(jìn)程等待。安全狀態(tài)：指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…,Pn)(稱〈P1,P2,…,Pn〉序列為安全序列),來(lái)為每個(gè)進(jìn)程Pi分配其所需資源,直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求,使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列,則稱系統(tǒng)處于不安全狀態(tài)。3.6.2系統(tǒng)安全狀態(tài)2/4/2023572.安全狀態(tài)之例假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3,共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī),P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻,進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī),尚有3臺(tái)空閑未分配,如下表所示:進(jìn)程最大需求已分配可用P1P2P310495223安全序列<P2，P1，P3>2/4/2023583.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源,則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如,在T0時(shí)刻以后,P3又請(qǐng)求1臺(tái)磁帶機(jī),若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3,則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)?此時(shí)也無(wú)法再找到一個(gè)安全序列,例如,把其余的2臺(tái)分配給P2,這樣,在P2完成后只能釋放出4臺(tái),既不能滿足P1尚需5臺(tái)的要求,也不能滿足P3尚需6臺(tái)的要求,致使它們都無(wú)法推進(jìn)到完成,彼此都在等待對(duì)方釋放資源,即陷入僵局,結(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

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

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

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

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

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

設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量,如果Requesti(1,0,2),表示進(jìn)程Pi需要1個(gè)R1類型的資源,需要0個(gè)R2類型的資源,需要2個(gè)R3類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后,系統(tǒng)按下述步驟進(jìn)行檢查:(1)如果Requesti≤Needi,便轉(zhuǎn)向步驟2;否則認(rèn)為出錯(cuò),因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。(2)如果Requesti≤Available,便轉(zhuǎn)向步驟(3);否則,表示尚無(wú)足夠資源,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ù)原來(lái)的資源分配狀態(tài),讓進(jìn)程Pi等待。2/4/2023643.安全性算法(1)設(shè)置兩個(gè)向量初值;①工作向量Work;它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目,它含有m個(gè)元素,在執(zhí)行安全算法開(kāi)始時(shí),Work:=Available;②Finish[];它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程,使之運(yùn)行完成。開(kāi)始時(shí)先做Finish[i]:=false;當(dāng)有足夠資源分配給進(jìn)程時(shí),再令Finish[i]:=true2/4/202365(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(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.銀行家算法之例

五個(gè)進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝各種資源的數(shù)量分別為10、5、7。(1)在T0時(shí)刻的安全性：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在該時(shí)刻存在著一個(gè)安全序列{P1，P3，P4，P0,P2},故系統(tǒng)是安全的。2/4/202367(2)P1請(qǐng)求資源:P1發(fā)出請(qǐng)求向量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向量,由此形成的資源變化情況如圖中的圓括號(hào)所示。④再利用安全性算法檢查此時(shí)系統(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在該時(shí)刻存在著一個(gè)安全序列{P1，P3，P4，P0,P2},故系統(tǒng)是安全的,可以分配。2/4/202369(3)P4請(qǐng)求資源:P4發(fā)出請(qǐng)求向量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請(qǐng)求資源:P0發(fā)出請(qǐng)求向量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)暫時(shí)先假定可為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),此時(shí)系統(tǒng)不能分配資源給P0。2/4/202371(5)P0請(qǐng)求資源:P0發(fā)出請(qǐng)求向量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向量,如下所示。④再利用安全性算法檢查此時(shí)系統(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在該時(shí)刻存在著一個(gè)安全序列{P1，P3，P4，P0,P2},故系統(tǒng)是安全的,可以分配。2/4/202373內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除

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