第三章-湯小丹-計(jì)算機(jī)操作系統(tǒng)-官方課件-第四版-計(jì)算機(jī)-操作系統(tǒng)--課件學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第三章第三章-湯小丹湯小丹-計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)(co zu x tn)-官方課件官方課件-第四版第四版-計(jì)算機(jī)計(jì)算機(jī)-操作系統(tǒng)操作系統(tǒng)(co zu x tn)-課件課件第一頁(yè)，共127頁(yè)。3.1 處理機(jī)調(diào)度的層次和調(diào)度算處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)法的目標(biāo)在多道程序系統(tǒng)中，調(diào)度的在多道程序系統(tǒng)中，調(diào)度的實(shí)質(zhì)是一種資源分配，處理機(jī)調(diào)實(shí)質(zhì)是一種資源分配，處理機(jī)調(diào)第1頁(yè)/共126頁(yè)第二頁(yè)，共127頁(yè)。3.1.1 3.1.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次(cngc)(cngc)1. 1. 高級(jí)調(diào)度高級(jí)調(diào)度(High Level (High Level 第2頁(yè)/共126頁(yè)第三頁(yè)

2、，共127頁(yè)。3.1.2 3.1.2 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)1. 1. 處理機(jī)調(diào)度算法的共同處理機(jī)調(diào)度算法的共同目標(biāo)目標(biāo)第3頁(yè)/共126頁(yè)第四頁(yè)，共127頁(yè)。(2) 公平性。公平性是指應(yīng)公平性。公平性是指應(yīng)使諸進(jìn)程都獲得合理的使諸進(jìn)程都獲得合理的CPU 時(shí)間，時(shí)間，不會(huì)發(fā)生進(jìn)程饑餓現(xiàn)象。公平性不會(huì)發(fā)生進(jìn)程饑餓現(xiàn)象。公平性是相對(duì)的，對(duì)相同類型的進(jìn)程應(yīng)是相對(duì)的，對(duì)相同類型的進(jìn)程應(yīng)獲得相同的服務(wù)；但對(duì)于不同類獲得相同的服務(wù)；但對(duì)于不同類型的進(jìn)程，由于其緊急程度或重型的進(jìn)程，由于其緊急程度或重要性的不同，則應(yīng)提供不同的服要性的不同，則應(yīng)提供不同的服務(wù)。務(wù)。(3) 平衡性。由于在系統(tǒng)中

3、平衡性。由于在系統(tǒng)中執(zhí)行。執(zhí)行。第4頁(yè)/共126頁(yè)第五頁(yè)，共127頁(yè)。2. 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)(1) 平均周轉(zhuǎn)時(shí)間短。平均周轉(zhuǎn)時(shí)間短。對(duì)每個(gè)用戶而言，都希望自對(duì)每個(gè)用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為己作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為計(jì)算機(jī)系統(tǒng)的管理者，則總是希計(jì)算機(jī)系統(tǒng)的管理者，則總是希Tn1Tn1ii第5頁(yè)/共126頁(yè)第六頁(yè)，共127頁(yè)。為了進(jìn)一步反映調(diào)度的性能，為了進(jìn)一步反映調(diào)度的性能，更清晰地描述各進(jìn)程在其周轉(zhuǎn)時(shí)更清晰地描述各進(jìn)程在其周轉(zhuǎn)時(shí)間中，等待和執(zhí)行時(shí)間的具體分間中，等待和執(zhí)行時(shí)間的具體分 n1isiTTn1W第6頁(yè)/共126頁(yè)第七頁(yè)，共127頁(yè)。(2) 系統(tǒng)吞

4、吐量高。由于吞系統(tǒng)吞吐量高。由于吞吐量是指在單位時(shí)間內(nèi)系統(tǒng)所完吐量是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長(zhǎng)度有關(guān)。事實(shí)上，如業(yè)的平均長(zhǎng)度有關(guān)。事實(shí)上，如果單純是為了獲得高的系統(tǒng)吞吐果單純是為了獲得高的系統(tǒng)吞吐量，就應(yīng)盡量多地選擇短作業(yè)運(yùn)量，就應(yīng)盡量多地選擇短作業(yè)運(yùn)行。行。第7頁(yè)/共126頁(yè)第八頁(yè)，共127頁(yè)。第8頁(yè)/共126頁(yè)第九頁(yè)，共127頁(yè)。第9頁(yè)/共126頁(yè)第十頁(yè)，共127頁(yè)。3.2 3.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度第10頁(yè)/共126頁(yè)第十一頁(yè)，共127頁(yè)。3.2.1 3.2.1 批處理系統(tǒng)批處理系統(tǒng)(xtng)(xtng)中中第11

5、頁(yè)/共126頁(yè)第十二頁(yè)，共127頁(yè)。2. 作業(yè)控制塊作業(yè)控制塊(Job Control Block，JCB)為了管理和調(diào)度為了管理和調(diào)度(diod)作作業(yè)，在多道批處理系統(tǒng)中，為每業(yè)，在多道批處理系統(tǒng)中，為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊JCB，它是作業(yè)在系統(tǒng)中存在的，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)小等小等)、資源使用情況等。、資源使用情況等。第12頁(yè)/共126頁(yè)第十三頁(yè)，共127頁(yè)。3. 作業(yè)運(yùn)行的三個(gè)階段和三作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)種狀態(tài)作業(yè)從進(jìn)入作業(yè)從進(jìn)入(jnr)系統(tǒng)到運(yùn)系統(tǒng)到運(yùn)行結(jié)束，通常需要經(jīng)歷收容、運(yùn)行結(jié)束

6、，通常需要經(jīng)歷收容、運(yùn)第13頁(yè)/共126頁(yè)第十四頁(yè)，共127頁(yè)。3.2.2 3.2.2 作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)是，根作業(yè)調(diào)度的主要任務(wù)是，根據(jù)據(jù)(gnj)JCB(gnj)JCB中的信息，檢查系中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對(duì)資源統(tǒng)中的資源能否滿足作業(yè)對(duì)資源的需求，以及按照一定的調(diào)度算的需求，以及按照一定的調(diào)度算法，從外存的后備隊(duì)列中選取某法，從外存的后備隊(duì)列中選取某第14頁(yè)/共126頁(yè)第十五頁(yè)，共127頁(yè)。3.2.3 3.2.3 先來(lái)先服務(wù)先來(lái)先服務(wù)(FCFS)(FCFS)和短和短作業(yè)優(yōu)先作業(yè)優(yōu)先(SJF)(SJF)調(diào)度算法調(diào)度算法1. 1. 先來(lái)先服務(wù)

7、先來(lái)先服務(wù)(first-come (first-come first-servedfirst-served，F(xiàn)CFS)FCFS)調(diào)度算法調(diào)度算法FCFSFCFS是最簡(jiǎn)單的調(diào)度算法，是最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中程。然后把它放入就緒隊(duì)列。程。然后把它放入就緒隊(duì)列。第15頁(yè)/共126頁(yè)第十六頁(yè)，共127頁(yè)。2. 短作業(yè)優(yōu)先短作業(yè)優(yōu)先(short job first，SJF)的調(diào)度算法的調(diào)度算法由于在實(shí)際情況中，短作業(yè)由于在實(shí)際情況中，短作業(yè)(進(jìn)程進(jìn)程)占有很大比例，為了能使占有很大比例，為了能使它

8、們能比長(zhǎng)作業(yè)優(yōu)先執(zhí)行，而產(chǎn)它們能比長(zhǎng)作業(yè)優(yōu)先執(zhí)行，而產(chǎn)生了短作業(yè)優(yōu)先調(diào)度算法。生了短作業(yè)優(yōu)先調(diào)度算法。1) 短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法第16頁(yè)/共126頁(yè)第十七頁(yè)，共127頁(yè)。2) 短作業(yè)優(yōu)先算法的缺點(diǎn)短作業(yè)優(yōu)先算法的缺點(diǎn)(qudin)SJF調(diào)度算法較之調(diào)度算法較之FCFS算法算法有了明顯的改進(jìn)，但仍然存在不有了明顯的改進(jìn)，但仍然存在不容忽視的缺點(diǎn)容忽視的缺點(diǎn)(qudin)：(1) 必須預(yù)知作業(yè)的運(yùn)行時(shí)必須預(yù)知作業(yè)的運(yùn)行時(shí)間。在采用這種算法時(shí)，要先知間。在采用這種算法時(shí)，要先知第17頁(yè)/共126頁(yè)第十八頁(yè)，共127頁(yè)。(3) 在采用在采用FCFS算法時(shí)，算法時(shí)，人人機(jī)無(wú)法實(shí)現(xiàn)交互。機(jī)無(wú)法實(shí)現(xiàn)

9、交互。第18頁(yè)/共126頁(yè)第十九頁(yè)，共127頁(yè)。3.2.4 3.2.4 優(yōu)先級(jí)調(diào)度算法和高響優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法應(yīng)比優(yōu)先調(diào)度算法1. 1. 優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法(priority-scheduling (priority-scheduling algorithmalgorithm，PSA)PSA)我們可以這樣來(lái)看作業(yè)的優(yōu)我們可以這樣來(lái)看作業(yè)的優(yōu)程度。程度。第19頁(yè)/共126頁(yè)第二十頁(yè)，共127頁(yè)。2. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法(Highest Response Ratio Next，HRRN) 在批處理系統(tǒng)中，在批處理系統(tǒng)中，F(xiàn)CFS算算法所考慮的只是作

10、業(yè)的等待時(shí)間，法所考慮的只是作業(yè)的等待時(shí)間，而忽視了作業(yè)的運(yùn)行時(shí)間。而而忽視了作業(yè)的運(yùn)行時(shí)間。而的性能。的性能。第20頁(yè)/共126頁(yè)第二十一頁(yè)，共127頁(yè)。高響應(yīng)比優(yōu)先算法是如何實(shí)高響應(yīng)比優(yōu)先算法是如何實(shí)現(xiàn)的呢現(xiàn)的呢? 如果我們能為每個(gè)作業(yè)如果我們能為每個(gè)作業(yè)引入一個(gè)動(dòng)態(tài)優(yōu)先級(jí)，即優(yōu)先級(jí)引入一個(gè)動(dòng)態(tài)優(yōu)先級(jí)，即優(yōu)先級(jí)要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)第21頁(yè)/共126頁(yè)第二十二頁(yè)，共127頁(yè)。由于等待時(shí)間與服務(wù)時(shí)間之由于等待時(shí)間與服務(wù)時(shí)間之要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間PR第22頁(yè)/共126頁(yè)第二十三頁(yè)，共127頁(yè)。3.3 3.3 進(jìn)進(jìn) 程程 調(diào)調(diào) 度度第23頁(yè)/共12

11、6頁(yè)第二十四頁(yè)，共127頁(yè)。3.3.1 3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式和方式1. 1. 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)第24頁(yè)/共126頁(yè)第二十五頁(yè)，共127頁(yè)。2. 進(jìn)程調(diào)度進(jìn)程調(diào)度(diod)機(jī)制機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度為了實(shí)現(xiàn)進(jìn)程調(diào)度(diod)，在進(jìn)程調(diào)度在進(jìn)程調(diào)度(diod)機(jī)制中，應(yīng)機(jī)制中，應(yīng)第25頁(yè)/共126頁(yè)第二十六頁(yè)，共127頁(yè)。第26頁(yè)/共126頁(yè)第二十七頁(yè)，共127頁(yè)。3. 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式1) 非搶占方式非搶占方式(Nonpreemptive Mode)在采用這種調(diào)度方式時(shí)，一在采用這種調(diào)度方式時(shí)，一第27頁(yè)/共126頁(yè)第二十八頁(yè)，共127

12、頁(yè)。2) 搶占方式搶占方式(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個(gè)正在根據(jù)某種原則，去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。的處理機(jī)重新分配給另一進(jìn)程。在現(xiàn)代在現(xiàn)代OS中廣泛采用搶占方式，中廣泛采用搶占方式，但搶占方式比較復(fù)雜，所需付出但搶占方式比較復(fù)雜，所需付出的系統(tǒng)開(kāi)銷也較大。的系統(tǒng)開(kāi)銷也較大。第28頁(yè)/共126頁(yè)第二十九頁(yè)，共127頁(yè)。3.3.2 3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法1. 1. 輪轉(zhuǎn)法的基本原理輪轉(zhuǎn)法的基本原理在輪轉(zhuǎn)在輪轉(zhuǎn)(RR)(RR)法中，系統(tǒng)將

13、所法中，系統(tǒng)將所有的就緒進(jìn)程按有的就緒進(jìn)程按FCFSFCFS策略排成一策略排成一個(gè)就緒隊(duì)列。系統(tǒng)可設(shè)置每隔一個(gè)就緒隊(duì)列。系統(tǒng)可設(shè)置每隔一定時(shí)間定時(shí)間( (如如3030ms)ms)便產(chǎn)生一次中斷，便產(chǎn)生一次中斷，第29頁(yè)/共126頁(yè)第三十頁(yè)，共127頁(yè)。2. 進(jìn)程切換時(shí)機(jī)進(jìn)程切換時(shí)機(jī)在在RR調(diào)度算法中，應(yīng)在何調(diào)度算法中，應(yīng)在何時(shí)進(jìn)行時(shí)進(jìn)行(jnxng)進(jìn)程的切換，可進(jìn)程的切換，可分為兩種情況：分為兩種情況： 若一個(gè)時(shí)間片若一個(gè)時(shí)間片尚未用完，正在運(yùn)行的進(jìn)程便已尚未用完，正在運(yùn)行的進(jìn)程便已第30頁(yè)/共126頁(yè)第三十一頁(yè)，共127頁(yè)。3. 時(shí)間片大小的確定時(shí)間片大小的確定在輪轉(zhuǎn)算法中，時(shí)間片的大在輪

14、轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的小對(duì)系統(tǒng)性能有很大的影響。影響。 第31頁(yè)/共126頁(yè)第三十二頁(yè)，共127頁(yè)。第32頁(yè)/共126頁(yè)第三十三頁(yè)，共127頁(yè)。第33頁(yè)/共126頁(yè)第三十四頁(yè)，共127頁(yè)。3.3.3 3.3.3 優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法1. 1. 優(yōu)先級(jí)調(diào)度算法的類型優(yōu)先級(jí)調(diào)度算法的類型優(yōu)先級(jí)進(jìn)程調(diào)度算法，是把優(yōu)先級(jí)進(jìn)程調(diào)度算法，是把第34頁(yè)/共126頁(yè)第三十五頁(yè)，共127頁(yè)。2. 優(yōu)先級(jí)的類型優(yōu)先級(jí)的類型1) 靜態(tài)優(yōu)先級(jí)靜態(tài)優(yōu)先級(jí)靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。優(yōu)先級(jí)是利用某一范保持不變。

15、優(yōu)先級(jí)是利用某一范第35頁(yè)/共126頁(yè)第三十六頁(yè)，共127頁(yè)。2) 動(dòng)態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程第36頁(yè)/共126頁(yè)第三十七頁(yè)，共127頁(yè)。3.3.4 3.3.4 多隊(duì)列調(diào)度算法多隊(duì)列調(diào)度算法如前所述的各種調(diào)度算法，如前所述的各種調(diào)度算法，尤其在應(yīng)用于進(jìn)程調(diào)度時(shí)，由于尤其在應(yīng)用于進(jìn)程調(diào)度時(shí)，由于系統(tǒng)中僅設(shè)置一個(gè)進(jìn)程的就緒隊(duì)系統(tǒng)中僅設(shè)置一個(gè)進(jìn)程的就緒隊(duì)列，即低級(jí)調(diào)度算法是固定的、列，即低級(jí)調(diào)度算法是固定的、第37頁(yè)/共126頁(yè)第三十八頁(yè)，共127頁(yè)。3.3.5 3.3.5 多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列(multileved feedback queue)(mu

16、ltileved feedback queue)調(diào)度算法調(diào)度算法第38頁(yè)/共126頁(yè)第三十九頁(yè)，共127頁(yè)。第39頁(yè)/共126頁(yè)第四十頁(yè)，共127頁(yè)。(2) 每個(gè)隊(duì)列都采用每個(gè)隊(duì)列都采用FCFS算算法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按將它放入第一隊(duì)列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該原則等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可撤離內(nèi)完成，便可撤離(chl)系統(tǒng)。系統(tǒng)。第40頁(yè)/共126頁(yè)第四十一頁(yè)，共127頁(yè)。(3) 按隊(duì)列優(yōu)先級(jí)調(diào)度。調(diào)按隊(duì)列優(yōu)先級(jí)調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級(jí)隊(duì)列度程序首先調(diào)

17、度最高優(yōu)先級(jí)隊(duì)列中的諸進(jìn)程運(yùn)行，僅當(dāng)?shù)谝魂?duì)列中的諸進(jìn)程運(yùn)行，僅當(dāng)?shù)谝魂?duì)列空閑時(shí)才調(diào)度第二隊(duì)列中的進(jìn)程空閑時(shí)才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；換言之，僅當(dāng)?shù)谶\(yùn)行；換言之，僅當(dāng)?shù)?(i-1)所所第41頁(yè)/共126頁(yè)第四十二頁(yè)，共127頁(yè)。2. 調(diào)度算法的性能調(diào)度算法的性能在多級(jí)反饋在多級(jí)反饋(fnku)隊(duì)列調(diào)隊(duì)列調(diào)度算法中，如果規(guī)定第一個(gè)隊(duì)列度算法中，如果規(guī)定第一個(gè)隊(duì)列第42頁(yè)/共126頁(yè)第四十三頁(yè)，共127頁(yè)。3.3.6 3.3.6 基于公平原則的調(diào)度算基于公平原則的調(diào)度算法法1. 1. 保證調(diào)度算法保證調(diào)度算法保證調(diào)度算法是另外一種類保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出型的調(diào)度算法，

18、它向用戶所做出第43頁(yè)/共126頁(yè)第四十四頁(yè)，共127頁(yè)。在實(shí)施公平調(diào)度算法時(shí)系統(tǒng)在實(shí)施公平調(diào)度算法時(shí)系統(tǒng)中必須具有這樣一些功能：中必須具有這樣一些功能：(1) 跟蹤計(jì)算每個(gè)進(jìn)程自創(chuàng)跟蹤計(jì)算每個(gè)進(jìn)程自創(chuàng)建以來(lái)已經(jīng)執(zhí)行的處理時(shí)間。建以來(lái)已經(jīng)執(zhí)行的處理時(shí)間。(2) 計(jì)算每個(gè)進(jìn)程應(yīng)獲得的計(jì)算每個(gè)進(jìn)程應(yīng)獲得的處理機(jī)時(shí)間，即自創(chuàng)建以來(lái)的時(shí)處理機(jī)時(shí)間，即自創(chuàng)建以來(lái)的時(shí)間除以間除以n。(3) 計(jì)算進(jìn)程獲得處理機(jī)時(shí)計(jì)算進(jìn)程獲得處理機(jī)時(shí)它，并讓該進(jìn)程一直運(yùn)行，直到它，并讓該進(jìn)程一直運(yùn)行，直到超過(guò)最接近它的進(jìn)程比率為止。超過(guò)最接近它的進(jìn)程比率為止。第44頁(yè)/共126頁(yè)第四十五頁(yè)，共127頁(yè)。2. 公平分享調(diào)度算法

19、公平分享調(diào)度算法分配給每個(gè)進(jìn)程相同的處理分配給每個(gè)進(jìn)程相同的處理第45頁(yè)/共126頁(yè)第四十六頁(yè)，共127頁(yè)。3.4 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度在實(shí)時(shí)系統(tǒng)中，可能存在著在實(shí)時(shí)系統(tǒng)中，可能存在著兩類不同性質(zhì)的實(shí)時(shí)任務(wù)，即兩類不同性質(zhì)的實(shí)時(shí)任務(wù)，即第46頁(yè)/共126頁(yè)第四十七頁(yè)，共127頁(yè)。3.4.1 3.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件件1. 1. 提供必要的信息提供必要的信息為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的信息：向調(diào)度程序提供有關(guān)任務(wù)的信息：第47頁(yè)/共126頁(yè)第四十八頁(yè)，共127頁(yè)。(3) 處理時(shí)間，一個(gè)任務(wù)從處理時(shí)間，一個(gè)任務(wù)從開(kāi)始執(zhí)行，

20、直至開(kāi)始執(zhí)行，直至(zhzh)完成時(shí)所完成時(shí)所需的時(shí)間。需的時(shí)間。(4) 資源要求，任務(wù)執(zhí)行時(shí)資源要求，任務(wù)執(zhí)行時(shí)所需的一組資源。所需的一組資源。第48頁(yè)/共126頁(yè)第四十九頁(yè)，共127頁(yè)。2. 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，若處理機(jī)的在實(shí)時(shí)系統(tǒng)中，若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過(guò)，而致使某些實(shí)時(shí)任理機(jī)忙不過(guò)，而致使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致務(wù)不能得到及時(shí)處理，從而導(dǎo)致1PCm1iii第49頁(yè)/共126頁(yè)第五十頁(yè)，共127頁(yè)。提高系統(tǒng)處理能力提高系統(tǒng)處理能力(nngl)的途徑有二：一是采用單處理機(jī)的途徑有二：一是采用單處理機(jī)系

21、統(tǒng)，但須增強(qiáng)其處理能力系統(tǒng)，但須增強(qiáng)其處理能力NPCm1iii第50頁(yè)/共126頁(yè)第五十一頁(yè)，共127頁(yè)。3. 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制(jzh)在含有在含有HRT任務(wù)的實(shí)時(shí)系統(tǒng)任務(wù)的實(shí)時(shí)系統(tǒng)第51頁(yè)/共126頁(yè)第五十二頁(yè)，共127頁(yè)。4. 具有快速切換機(jī)制具有快速切換機(jī)制為保證硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)為保證硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在系統(tǒng)行，在系統(tǒng)(xtng)中還應(yīng)具有中還應(yīng)具有快速切換機(jī)制，使之能進(jìn)行任務(wù)快速切換機(jī)制，使之能進(jìn)行任務(wù)的快速切換。該機(jī)制應(yīng)具有如下的快速切換。該機(jī)制應(yīng)具有如下兩方面的能力：兩方面的能力：(1) 對(duì)中斷的快速響應(yīng)能力。對(duì)中斷的快速響應(yīng)能力。第52頁(yè)/共126頁(yè)第

22、五十三頁(yè)，共127頁(yè)。3.4.2 3.4.2 實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類(fn li) (fn li) 可以按不同方式對(duì)實(shí)時(shí)調(diào)度可以按不同方式對(duì)實(shí)時(shí)調(diào)度第53頁(yè)/共126頁(yè)第五十四頁(yè)，共127頁(yè)。1. 非搶占式調(diào)度算法非搶占式調(diào)度算法第54頁(yè)/共126頁(yè)第五十五頁(yè)，共127頁(yè)。2. 搶占式調(diào)度算法搶占式調(diào)度算法可根據(jù)搶占發(fā)生可根據(jù)搶占發(fā)生(fshng)時(shí)時(shí)間的不同而進(jìn)一步分成以下兩種間的不同而進(jìn)一步分成以下兩種調(diào)度算法：調(diào)度算法：第55頁(yè)/共126頁(yè)第五十六頁(yè)，共127頁(yè)。第56頁(yè)/共126頁(yè)第五十七頁(yè)，共127頁(yè)。3.4.3 3.4.3 最早截止時(shí)間最早截止時(shí)間(shjin)(sh

23、jin)優(yōu)先優(yōu)先EDF(Earliest Deadline EDF(Earliest Deadline 第57頁(yè)/共126頁(yè)第五十八頁(yè)，共127頁(yè)。第58頁(yè)/共126頁(yè)第五十九頁(yè)，共127頁(yè)。2. 搶占式調(diào)度方式用于周期搶占式調(diào)度方式用于周期(zhuq)實(shí)時(shí)任務(wù)實(shí)時(shí)任務(wù)圖圖3-7示出了將該算法用于搶示出了將該算法用于搶第59頁(yè)/共126頁(yè)第六十頁(yè)，共127頁(yè)。第60頁(yè)/共126頁(yè)第六十一頁(yè)，共127頁(yè)。3.4.4 3.4.4 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF(Least Laxity First)LLF(Least Laxity First)算法算法該算法在確定任務(wù)的優(yōu)先級(jí)該算法在確定任務(wù)的

24、優(yōu)先級(jí)時(shí)，根據(jù)的是任務(wù)的緊急時(shí)，根據(jù)的是任務(wù)的緊急( (或松或松弛弛) )程度。任務(wù)緊急程度愈高，程度。任務(wù)緊急程度愈高，賦予該任務(wù)的優(yōu)先級(jí)就愈高，以賦予該任務(wù)的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行使之優(yōu)先執(zhí)行(zhxng)(zhxng)。該算法主要用于可搶占調(diào)度該算法主要用于可搶占調(diào)度、A3A3、和和B1B1、B2B2、B3B3、，見(jiàn)圖，見(jiàn)圖3-83-8。第61頁(yè)/共126頁(yè)第六十二頁(yè)，共127頁(yè)。第62頁(yè)/共126頁(yè)第六十三頁(yè)，共127頁(yè)。第63頁(yè)/共126頁(yè)第六十四頁(yè)，共127頁(yè)。3.4.5 3.4.5 優(yōu)先級(jí)倒置優(yōu)先級(jí)倒置(priority (priority inversion proble

25、m) inversion problem) 1. 1. 優(yōu)先級(jí)倒置的形成優(yōu)先級(jí)倒置的形成當(dāng)前當(dāng)前OSOS廣泛采用優(yōu)先級(jí)調(diào)度廣泛采用優(yōu)先級(jí)調(diào)度第64頁(yè)/共126頁(yè)第六十五頁(yè)，共127頁(yè)。假如假如P3最先執(zhí)行，在執(zhí)行了最先執(zhí)行，在執(zhí)行了P(mutex)操作后，進(jìn)入到臨界區(qū)操作后，進(jìn)入到臨界區(qū)第65頁(yè)/共126頁(yè)第六十六頁(yè)，共127頁(yè)。第66頁(yè)/共126頁(yè)第六十七頁(yè)，共127頁(yè)。2. 優(yōu)先級(jí)倒置的解決方法優(yōu)先級(jí)倒置的解決方法一種簡(jiǎn)單的解決方法是規(guī)定：一種簡(jiǎn)單的解決方法是規(guī)定：第67頁(yè)/共126頁(yè)第六十八頁(yè)，共127頁(yè)。第68頁(yè)/共126頁(yè)第六十九頁(yè)，共127頁(yè)。3.5 死死 鎖鎖 概概 述述3.5.

26、1 資源問(wèn)題資源問(wèn)題在系統(tǒng)中有許多在系統(tǒng)中有許多(xdu)不不第69頁(yè)/共126頁(yè)第七十頁(yè)，共127頁(yè)。1. 可重用性資源和消耗性資可重用性資源和消耗性資源源1) 可重用性資源可重用性資源可重用性資源是一種可供用可重用性資源是一種可供用戶重復(fù)使用多次的資源，它具有戶重復(fù)使用多次的資源，它具有如下性質(zhì)：如下性質(zhì)：(1) 每一個(gè)可重用性資源中每一個(gè)可重用性資源中的單元只能分配給一個(gè)進(jìn)程的單元只能分配給一個(gè)進(jìn)程(jnchng)使用，不允許多個(gè)進(jìn)使用，不允許多個(gè)進(jìn)程程(jnchng)共享。共享。(3) 系統(tǒng)中每一類可重用性系統(tǒng)中每一類可重用性資源中的單元數(shù)目是相對(duì)固定的，資源中的單元數(shù)目是相對(duì)固定的，

27、進(jìn)程進(jìn)程(jnchng)在運(yùn)行期間既不在運(yùn)行期間既不能創(chuàng)建也不能刪除它。能創(chuàng)建也不能刪除它。第70頁(yè)/共126頁(yè)第七十一頁(yè)，共127頁(yè)。2) 可消耗性資源可消耗性資源可消耗性資源又稱為臨時(shí)性可消耗性資源又稱為臨時(shí)性資源，它是在進(jìn)程運(yùn)行期間，由資源，它是在進(jìn)程運(yùn)行期間，由進(jìn)程動(dòng)態(tài)地創(chuàng)建和消耗的，它具進(jìn)程動(dòng)態(tài)地創(chuàng)建和消耗的，它具有如下性質(zhì)：有如下性質(zhì)： 每一類可消耗性每一類可消耗性資源的單元數(shù)目在進(jìn)程運(yùn)行期間資源的單元數(shù)目在進(jìn)程運(yùn)行期間第71頁(yè)/共126頁(yè)第七十二頁(yè)，共127頁(yè)。2. 可搶占性資源和不可搶占可搶占性資源和不可搶占性資源性資源1) 可搶占性資源可搶占性資源可把系統(tǒng)中的資源分成兩類，可

28、把系統(tǒng)中的資源分成兩類，一類是可搶占性資源，是指某進(jìn)一類是可搶占性資源，是指某進(jìn)第72頁(yè)/共126頁(yè)第七十三頁(yè)，共127頁(yè)。3.5.2 3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖1. 1. 競(jìng)爭(zhēng)競(jìng)爭(zhēng)(jngzhng)(jngzhng)不可搶不可搶占性資源引起死鎖占性資源引起死鎖第73頁(yè)/共126頁(yè)第七十四頁(yè)，共127頁(yè)。第74頁(yè)/共126頁(yè)第七十五頁(yè)，共127頁(yè)。第75頁(yè)/共126頁(yè)第七十六頁(yè)，共127頁(yè)。2. 競(jìng)爭(zhēng)可消耗資源引起死鎖競(jìng)爭(zhēng)可消耗資源引起死鎖現(xiàn)在進(jìn)一步介紹競(jìng)爭(zhēng)可消耗現(xiàn)在進(jìn)一步介紹競(jìng)爭(zhēng)可消耗第76頁(yè)/共126頁(yè)第七十七頁(yè)，共127頁(yè)。第77頁(yè)/共126頁(yè)第七十八頁(yè)，共127頁(yè)

29、。3. 進(jìn)程推進(jìn)順序不當(dāng)引起死進(jìn)程推進(jìn)順序不當(dāng)引起死鎖鎖除了系統(tǒng)中多個(gè)進(jìn)程對(duì)資源除了系統(tǒng)中多個(gè)進(jìn)程對(duì)資源第78頁(yè)/共126頁(yè)第七十九頁(yè)，共127頁(yè)。1) 進(jìn)程推進(jìn)順序合法進(jìn)程推進(jìn)順序合法(hf)在進(jìn)程在進(jìn)程P1和和P2并發(fā)執(zhí)行時(shí)，并發(fā)執(zhí)行時(shí)，如果按圖如果按圖3-14中的曲線所示的中的曲線所示的順序推進(jìn)：順序推進(jìn)：P1：Request(R1)P1：Request(R2)P1：Releast(R1)P1：推進(jìn)順序是合法推進(jìn)順序是合法(hf)的。的。第79頁(yè)/共126頁(yè)第八十頁(yè)，共127頁(yè)。2) 進(jìn)程推進(jìn)順序非法進(jìn)程推進(jìn)順序非法若并發(fā)進(jìn)程若并發(fā)進(jìn)程P1和和P2按圖按圖3-14中曲線所示的順序推進(jìn)，它

30、們中曲線所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)將進(jìn)入不安全區(qū)D內(nèi)。此時(shí)內(nèi)。此時(shí)P1保保持了資源持了資源R1，P2保持了資源保持了資源R2，系統(tǒng)系統(tǒng)(xtng)處于不安全狀態(tài)。處于不安全狀態(tài)。第80頁(yè)/共126頁(yè)第八十一頁(yè)，共127頁(yè)。第81頁(yè)/共126頁(yè)第八十二頁(yè)，共127頁(yè)。3.5.3 3.5.3 死鎖的定義、必要條件死鎖的定義、必要條件和處理和處理(chl)(chl)方法方法第82頁(yè)/共126頁(yè)第八十三頁(yè)，共127頁(yè)。2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件雖然進(jìn)程在運(yùn)行過(guò)程中可能雖然進(jìn)程在運(yùn)行過(guò)程中可能會(huì)發(fā)生死鎖，但產(chǎn)生進(jìn)程死鎖是會(huì)發(fā)生死鎖，但產(chǎn)生進(jìn)程死鎖是必須具備一定條件的。綜上所述必須

31、具備一定條件的。綜上所述第83頁(yè)/共126頁(yè)第八十四頁(yè)，共127頁(yè)。3. 處理處理(chl)死鎖的方法死鎖的方法目前處理目前處理(chl)死鎖的方法死鎖的方法第84頁(yè)/共126頁(yè)第八十五頁(yè)，共127頁(yè)。3.6 3.6 預(yù)預(yù) 防防 死死 鎖鎖第85頁(yè)/共126頁(yè)第八十六頁(yè)，共127頁(yè)。3.6.1 3.6.1 破壞破壞“請(qǐng)求和保持請(qǐng)求和保持”條條件件為了能破壞為了能破壞“請(qǐng)求和保持請(qǐng)求和保持”條件，系統(tǒng)必須保證做到：當(dāng)一條件，系統(tǒng)必須保證做到：當(dāng)一個(gè)進(jìn)程在請(qǐng)求資源時(shí)，它不能持個(gè)進(jìn)程在請(qǐng)求資源時(shí)，它不能持第86頁(yè)/共126頁(yè)第八十七頁(yè)，共127頁(yè)。2. 第二種協(xié)議第二種協(xié)議第87頁(yè)/共126頁(yè)第八十

32、八頁(yè)，共127頁(yè)。3.6.2 3.6.2 破壞破壞“不可搶占不可搶占”條件條件為了能破壞為了能破壞“不可搶占不可搶占”條條件，協(xié)議中規(guī)定件，協(xié)議中規(guī)定(gudng)(gudng)，當(dāng)，當(dāng)一個(gè)已經(jīng)保持了某些不可被搶占一個(gè)已經(jīng)保持了某些不可被搶占第88頁(yè)/共126頁(yè)第八十九頁(yè)，共127頁(yè)。3.6.3 3.6.3 破壞破壞“循環(huán)循環(huán)(xnhun)(xnhun)等等待待”條件條件第89頁(yè)/共126頁(yè)第九十頁(yè)，共127頁(yè)。3.7 3.7 避避 免免 死死 鎖鎖第90頁(yè)/共126頁(yè)第九十一頁(yè)，共127頁(yè)。3.7.13.7.1系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)在死鎖避免方法中，把系統(tǒng)在死鎖避免方法中，把系統(tǒng)的狀態(tài)分為

33、安全狀態(tài)和不安全狀的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)，可態(tài)。當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)，可避免發(fā)生死鎖。反之避免發(fā)生死鎖。反之(fnzh)(fnzh)，第91頁(yè)/共126頁(yè)第九十二頁(yè)，共127頁(yè)。2. 安全狀態(tài)之例安全狀態(tài)之例假定假定(jidng)系統(tǒng)中有三個(gè)系統(tǒng)中有三個(gè)進(jìn)程進(jìn)程P1、P2和和P3，共有，共有12臺(tái)磁帶臺(tái)磁帶第92頁(yè)/共126頁(yè)第九十三頁(yè)，共127頁(yè)。3. 由安全狀態(tài)向不安全狀態(tài)由安全狀態(tài)向不安全狀態(tài)第93頁(yè)/共126頁(yè)第九十四頁(yè)，共127頁(yè)。3.7.2 3.7.2 利用銀行家算法避免利用銀行家算法避免(bmin)(bmin)死鎖死鎖最有代表性的避免最有代表性的避免

34、(bmin)(bmin)死鎖的算法是死鎖的算法是DijkstraDijkstra的銀行家的銀行家第94頁(yè)/共126頁(yè)第九十五頁(yè)，共127頁(yè)。1. 銀行家算法銀行家算法(sun f)中的中的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)銀行家算法為了實(shí)現(xiàn)銀行家算法(sun f)，在系統(tǒng)中必須設(shè)置這樣四個(gè)，在系統(tǒng)中必須設(shè)置這樣四個(gè)數(shù)據(jù)結(jié)構(gòu)，分別用來(lái)描述系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)，分別用來(lái)描述系統(tǒng)中第95頁(yè)/共126頁(yè)第九十六頁(yè)，共127頁(yè)。2. 銀行家算法銀行家算法(sun f)設(shè)設(shè)Requesti是進(jìn)程是進(jìn)程Pi的請(qǐng)求的請(qǐng)求向量，如果向量，如果Requestij=K，表示，表示進(jìn)程進(jìn)程Pi需要需要K個(gè)個(gè)Rj類型的資源。類型的資源

35、。當(dāng)當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：述步驟進(jìn)行檢查：第96頁(yè)/共126頁(yè)第九十七頁(yè)，共127頁(yè)。(3) 系統(tǒng)試探著把資源分配系統(tǒng)試探著把資源分配(fnpi)給進(jìn)程給進(jìn)程Pi，并修改下面數(shù)，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：據(jù)結(jié)構(gòu)中的數(shù)值：Availablej = Availablej-Requestij; Allocationi, j = Allocationi, j+Requestij;恢復(fù)原來(lái)的資源分配恢復(fù)原來(lái)的資源分配(fnpi)狀態(tài)，狀態(tài)，讓進(jìn)程讓進(jìn)程Pi等待。等待。第97頁(yè)/共126頁(yè)第九十八頁(yè)，共127頁(yè)。3. 安全性算法安全性算法系統(tǒng)所執(zhí)行的安全性

36、算法可系統(tǒng)所執(zhí)行的安全性算法可描述描述(mio sh)如下：如下：(1) 設(shè)置兩個(gè)向量：設(shè)置兩個(gè)向量： 工作工作向量向量Work，它表示系統(tǒng)可提供給，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)true。第98頁(yè)/共126頁(yè)第九十九頁(yè)，共127頁(yè)。(2) 從進(jìn)程集合中找到一個(gè)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：能滿足下述條件的進(jìn)程： Finishi=false; Needi, jWorkj;若找到，執(zhí)行步驟若找到，執(zhí)行步驟(3)，否則，否則，執(zhí)行步驟執(zhí)行步驟(4)。(3) 當(dāng)進(jìn)程當(dāng)進(jìn)程Pi獲得資源后，可獲得資源后，可第99頁(yè)/共126頁(yè)第一百頁(yè)，共127頁(yè)。

37、4. 銀行家算法之例銀行家算法之例假定系統(tǒng)中有五個(gè)進(jìn)程假定系統(tǒng)中有五個(gè)進(jìn)程P0, 第100頁(yè)/共126頁(yè)第一百零一頁(yè)，共127頁(yè)。第101頁(yè)/共126頁(yè)第一百零二頁(yè)，共127頁(yè)。(1) T0時(shí)刻的安全性：利用時(shí)刻的安全性：利用安全性算法對(duì)安全性算法對(duì)T0時(shí)刻的資源分配時(shí)刻的資源分配第102頁(yè)/共126頁(yè)第一百零三頁(yè)，共127頁(yè)。第103頁(yè)/共126頁(yè)第一百零四頁(yè)，共127頁(yè)。(2) P1請(qǐng)求資源：請(qǐng)求資源：P1發(fā)出請(qǐng)發(fā)出請(qǐng)求向量求向量Request1(1, 0, 2)，系統(tǒng)按，系統(tǒng)按銀行家算法進(jìn)行檢查：銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2)； Re

38、quest1(1, 0, 第104頁(yè)/共126頁(yè)第一百零五頁(yè)，共127頁(yè)。第105頁(yè)/共126頁(yè)第一百零六頁(yè)，共127頁(yè)。(3) P4請(qǐng)求資源：請(qǐng)求資源：P4發(fā)出請(qǐng)發(fā)出請(qǐng)求向量求向量Request4(3，3，0)，系統(tǒng)，系統(tǒng)按銀行家算法進(jìn)行按銀行家算法進(jìn)行(jnxng)檢查：檢查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，讓，讓P4等待。等待。第106頁(yè)/共126頁(yè)第一百零七頁(yè)，共127頁(yè)。第107頁(yè)/共126頁(yè)第一百零八頁(yè)，共127頁(yè)。(5) 進(jìn)行安全性檢查：可用進(jìn)行安全性檢查：可用第108頁(yè)/共126頁(yè)第一百

39、零九頁(yè)，共127頁(yè)。3.8 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除如果在系統(tǒng)中，既不采取死如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會(huì)發(fā)生死鎖。算法，系統(tǒng)很可能會(huì)發(fā)生死鎖。第109頁(yè)/共126頁(yè)第一百一十頁(yè)，共127頁(yè)。3.8.1 3.8.1 死鎖的檢測(cè)死鎖的檢測(cè)為了能對(duì)系統(tǒng)中是否已發(fā)生為了能對(duì)系統(tǒng)中是否已發(fā)生了死鎖進(jìn)行檢測(cè)，在系統(tǒng)中必須：了死鎖進(jìn)行檢測(cè)，在系統(tǒng)中必須： 保存有關(guān)資源的請(qǐng)求和分配保存有關(guān)資源的請(qǐng)求和分配第110頁(yè)/共126頁(yè)第一百一十一頁(yè)，共127頁(yè)。該圖是由一組結(jié)點(diǎn)該圖是由一組結(jié)點(diǎn)N和一組和一組邊邊E所組成的一個(gè)對(duì)偶所組成的一個(gè)

40、對(duì)偶G=(N, E)，它具有下述形式的定義和限，它具有下述形式的定義和限制：制：(1) 把把N分為兩個(gè)互斥的子集，分為兩個(gè)互斥的子集，即一組進(jìn)程結(jié)點(diǎn)即一組進(jìn)程結(jié)點(diǎn)P=P1, P2, , Pn和一組資源結(jié)點(diǎn)和一組資源結(jié)點(diǎn)R=R1, R2, , Rn，N=PR。在圖。在圖3-19所示的例子所示的例子(l zi)中，中，P=P1, ，R=，N= 。圖圖3-19中示出了兩個(gè)請(qǐng)求邊和兩中示出了兩個(gè)請(qǐng)求邊和兩個(gè)分配邊，即個(gè)分配邊，即E=(P1, R2), (R2, P2), (P2, R1), (R1, P1)。第111頁(yè)/共126頁(yè)第一百一十二頁(yè)，共127頁(yè)。第112頁(yè)/共126頁(yè)第一百一十三頁(yè)，共12

41、7頁(yè)。2死鎖定理死鎖定理(dngl)我們可以利用把資源分配圖我們可以利用把資源分配圖加以簡(jiǎn)化的方法加以簡(jiǎn)化的方法(圖圖3-19)，來(lái)檢，來(lái)檢測(cè)當(dāng)系統(tǒng)處于測(cè)當(dāng)系統(tǒng)處于S狀態(tài)時(shí)，是否為狀態(tài)時(shí)，是否為死鎖狀態(tài)。簡(jiǎn)化方法如下：死鎖狀態(tài)。簡(jiǎn)化方法如下：(1) 在資源分配圖中，找出在資源分配圖中，找出第113頁(yè)/共126頁(yè)第一百一十四頁(yè)，共127頁(yè)。第114頁(yè)/共126頁(yè)第一百一十五頁(yè)，共127頁(yè)。(2) P1釋放資源后，便可使釋放資源后，便可使P2獲得資源而繼續(xù)運(yùn)行，直至獲得資源而繼續(xù)運(yùn)行，直至P2完成完成(wn chng)后又釋放出它所后又釋放出它所占有的全部資源，形成圖占有的全部資源，形成圖(c)所示所示第115頁(yè)/共126頁(yè)第一百一十六頁(yè)，共127頁(yè)。3死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)類似死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)類似于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：(1) 可利用資源向量可利用資源向量Available，它表示了它表示了m類資源中每一類資源類資源中每一類資源的可用數(shù)目。的可用數(shù)