1、1 1第三章 處理機調(diào)度與死鎖第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1 處理機調(diào)度的層次和調(diào)度算法的目標(biāo)3.2 作業(yè)與作業(yè)調(diào)度3.3 進(jìn)程調(diào)度3.4 實時調(diào)度3.5 死鎖概述3.6 預(yù)防死鎖3.7 避免死鎖3.8 死鎖的檢測與解除習(xí)題2 2第三章 處理機調(diào)度與死鎖3.1 處理機調(diào)度的層次和調(diào)度算法的目標(biāo)在多道程序系統(tǒng)中，調(diào)度的實質(zhì)是一種資源分配，處理機調(diào)度是對處理機資源進(jìn)行分配。處理機調(diào)度算法是指根據(jù)處理機分配策略所規(guī)定的處理機分配算法。在多道批處理系統(tǒng)中，一個作業(yè)從提交到獲得處理機執(zhí)行，直至作業(yè)運行完畢，可能需要經(jīng)歷多級處理機調(diào)度，下面先來了解處理機調(diào)度的層次。3 3第三章 處理

2、機調(diào)度與死鎖3.1.1 處理機調(diào)度的層次1. 高級調(diào)度(High Level Scheduling)2. 低級調(diào)度(Low Level Scheduling)3. 中級調(diào)度(Intermediate Scheduling)4 4第三章 處理機調(diào)度與死鎖3.1.2 處理機調(diào)度算法的目標(biāo)1. 處理機調(diào)度算法的共同目標(biāo)(1) 資源利用率。為提高系統(tǒng)的資源利用率，應(yīng)使系統(tǒng)中的處理機和其它所有資源都盡可能地保持忙碌狀態(tài)，其中最重要的處理機利用率可用以下方法計算：5 5第三章 處理機調(diào)度與死鎖(2) 公平性。公平性是指應(yīng)使諸進(jìn)程都獲得合理的CPU 時間，不會發(fā)生進(jìn)程饑餓現(xiàn)象。公平性是相對的，對相同類型的進(jìn)

3、程應(yīng)獲得相同的服務(wù)；但對于不同類型的進(jìn)程，由于其緊急程度或重要性的不同，則應(yīng)提供不同的服務(wù)。(3) 平衡性。由于在系統(tǒng)中可能具有多種類型的進(jìn)程，有的屬于計算型作業(yè)，有的屬于I/O型。為使系統(tǒng)中的CPU和各種外部設(shè)備都能經(jīng)常處于忙碌狀態(tài)，調(diào)度算法應(yīng)盡可能保持系統(tǒng)資源使用的平衡性。(4) 策略強制執(zhí)行。對所制訂的策略其中包括安全策略，只要需要，就必須予以準(zhǔn)確地執(zhí)行，即使會造成某些工作的延遲也要執(zhí)行。6 6第三章 處理機調(diào)度與死鎖2. 批處理系統(tǒng)的目標(biāo)(1) 平均周轉(zhuǎn)時間短。 對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時間最短，這不僅會有效地提高系

4、統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意。應(yīng)使作業(yè)周轉(zhuǎn)時間和作業(yè)的平均周轉(zhuǎn)時間盡可能短。否則，會使許多用戶的等待時間過長，這將會引起用戶特別是短作業(yè)用戶的不滿。可把平均周轉(zhuǎn)時間描述為：Tn1Tn1ii7 7第三章 處理機調(diào)度與死鎖為了進(jìn)一步反映調(diào)度的性能，更清晰地描述各進(jìn)程在其周轉(zhuǎn)時間中，等待和執(zhí)行時間的具體分配狀況，往往使用帶權(quán)周轉(zhuǎn)時間，即作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間Ts之比，即W=T/Ts。而平均帶權(quán)周轉(zhuǎn)時間則可表示為：n1isiTTn1W8 8第三章 處理機調(diào)度與死鎖(2) 系統(tǒng)吞吐量高。由于吞吐量是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長度有關(guān)。事

5、實上，如果單純是為了獲得高的系統(tǒng)吞吐量，就應(yīng)盡量多地選擇短作業(yè)運行。(3) 處理機利用率高。對于大、中型計算機，CPU價格十分昂貴，致使處理機的利用率成為衡量系統(tǒng)性能的十分重要的指標(biāo)；而調(diào)度方式和算法又對處理機的利用率起著十分重要的作用。如果單純是為使處理機利用率高，應(yīng)盡量多地選擇計算量大的作業(yè)運行。由上所述可以看出，這些要求之間是存在著一定矛盾的。9 9第三章 處理機調(diào)度與死鎖3. 分時系統(tǒng)的目標(biāo)(1) 響應(yīng)時間快。(2) 均衡性。 10 10第三章 處理機調(diào)度與死鎖4. 實時系統(tǒng)的目標(biāo)(1) 截止時間的保證。(2) 可預(yù)測性。 11 11第三章 處理機調(diào)度與死鎖3.2 作業(yè)與作業(yè)調(diào)度在多道

6、批處理系統(tǒng)中，作業(yè)是用戶提交給系統(tǒng)的一項相對獨立的工作。操作員把用戶提交的作業(yè)通過相應(yīng)的輸入設(shè)備輸入到磁盤存儲器，并保存在一個后備作業(yè)隊列中。再由作業(yè)調(diào)度程序?qū)⑵鋸耐獯嬲{(diào)入內(nèi)存。12 12第三章 處理機調(diào)度與死鎖3.2.1 批處理系統(tǒng)中的作業(yè)1. 作業(yè)和作業(yè)步(1) 作業(yè)(Job)。(2) 作業(yè)步(Job Step)。13 13第三章 處理機調(diào)度與死鎖2. 作業(yè)控制塊(Job Control Block，JCB)為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中，為每個作業(yè)設(shè)置了一個作業(yè)控制塊JCB，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。通常在JCB中包含的內(nèi)容有：

7、作業(yè)標(biāo)識、用戶名稱、用戶賬號、作業(yè)類型(CPU 繁忙型、I/O 繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)運行時間)、資源需求(預(yù)計運行時間、要求內(nèi)存大小等)、資源使用情況等。14 14第三章 處理機調(diào)度與死鎖3. 作業(yè)運行的三個階段和三種狀態(tài) 作業(yè)從進(jìn)入系統(tǒng)到運行結(jié)束，通常需要經(jīng)歷收容、運行和完成三個階段。相應(yīng)的作業(yè)也就有“后備狀態(tài)”、“運行狀態(tài)”和“完成狀態(tài)”。(1) 收容階段。(2) 運行階段。(3) 完成階段。 15 15第三章 處理機調(diào)度與死鎖3.2.2 作業(yè)調(diào)度的主要任務(wù) 作業(yè)調(diào)度的主要任務(wù)是，根據(jù)JCB中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對資源的需求，以及按照一

8、定的調(diào)度算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程排在就緒隊列上等待調(diào)度。因此，也把作業(yè)調(diào)度稱為接納調(diào)度(Admission Scheduling)。在每次執(zhí)行作業(yè)調(diào)度時，都需做出以下兩個決定。 1. 接納多少個作業(yè)2. 接納哪些作業(yè)16 16第三章 處理機調(diào)度與死鎖3.2.3 先來先服務(wù)(FCFS)和短作業(yè)優(yōu)先(SJF)調(diào)度算法 1. 先來先服務(wù)(first-come first-served，F(xiàn)CFS)調(diào)度算法FCFS是最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時，系統(tǒng)將按照作業(yè)到達(dá)的先后次

9、序來進(jìn)行調(diào)度，或者說它是優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管該作業(yè)所需執(zhí)行時間的長短，從后備作業(yè)隊列中選擇幾個最先進(jìn)入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源和創(chuàng)建進(jìn)程。然后把它放入就緒隊列。17 17第三章 處理機調(diào)度與死鎖2. 短作業(yè)優(yōu)先(short job first，SJF)的調(diào)度算法 由于在實際情況中，短作業(yè)(進(jìn)程)占有很大比例，為了能使它們能比長作業(yè)優(yōu)先執(zhí)行，而產(chǎn)生了短作業(yè)優(yōu)先調(diào)度算法。1) 短作業(yè)優(yōu)先算法SJF算法是以作業(yè)的長短來計算優(yōu)先級，作業(yè)越短，其優(yōu)先級越高。作業(yè)的長短是以作業(yè)所要求的運行時間來衡量的。SJF算法可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算

10、法用于作業(yè)調(diào)度時，它將從外存的作業(yè)后備隊列中選擇若干個估計運行時間最短的作業(yè)，優(yōu)先將它們調(diào)入內(nèi)存運行。18 18第三章 處理機調(diào)度與死鎖2) 短作業(yè)優(yōu)先算法的缺點SJF調(diào)度算法較之FCFS算法有了明顯的改進(jìn)，但仍然存在不容忽視的缺點：(1) 必須預(yù)知作業(yè)的運行時間。在采用這種算法時，要先知道每個作業(yè)的運行時間。即使是程序員也很難準(zhǔn)確估計作業(yè)的運行時間，如果估計過低，系統(tǒng)就可能按估計的時間終止作業(yè)的運行，但此時作業(yè)并未完成，故一般都會偏長估計。(2) 對長作業(yè)非常不利，長作業(yè)的周轉(zhuǎn)時間會明顯地增長。更嚴(yán)重的是，該算法完全忽視作業(yè)的等待時間，可能使作業(yè)等待時間過長，出現(xiàn)饑餓現(xiàn)象。19 19第三章

11、處理機調(diào)度與死鎖(3) 在采用FCFS算法時，人機無法實現(xiàn)交互。(4) 該調(diào)度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)能得到及時處理。2020第三章 處理機調(diào)度與死鎖3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法1. 優(yōu)先級調(diào)度算法(priority-scheduling algorithm，PSA)我們可以這樣來看作業(yè)的優(yōu)先級，對于先來先服務(wù)調(diào)度算法，作業(yè)的等待時間就是作業(yè)的優(yōu)先級，等待時間越長，其優(yōu)先級越高。對于短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的長短就是作業(yè)的優(yōu)先級，作業(yè)所需運行的時間越短，其優(yōu)先級越高。但上述兩種優(yōu)先級都不能反映作業(yè)的緊迫程度。 21 21第三章 處理機調(diào)度與死鎖2.

12、 高響應(yīng)比優(yōu)先調(diào)度算法(Highest Response Ratio Next，HRRN) 在批處理系統(tǒng)中，F(xiàn)CFS算法所考慮的只是作業(yè)的等待時間，而忽視了作業(yè)的運行時間。而SJF算法正好與之相反，只考慮作業(yè)的運行時間，而忽視了作業(yè)的等待時間。高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時間，又考慮作業(yè)運行時間的調(diào)度算法，因此既照顧了短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善了處理機調(diào)度的性能。2222第三章 處理機調(diào)度與死鎖高響應(yīng)比優(yōu)先算法是如何實現(xiàn)的呢? 如果我們能為每個作業(yè)引入一個動態(tài)優(yōu)先級，即優(yōu)先級是可以改變的，令它隨等待時間延長而增加，這將使長作業(yè)的優(yōu)先級在等待期間不斷地增加，等到

13、足夠的時間后，必然有機會獲得處理機。該優(yōu)先級的變化規(guī)律可描述為：要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)2323第三章 處理機調(diào)度與死鎖由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先級又相當(dāng)于響應(yīng)比RP。據(jù)此，優(yōu)先又可表示為：要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間PR2424第三章 處理機調(diào)度與死鎖3.3 進(jìn) 程 調(diào) 度進(jìn)程調(diào)度是OS中必不可少的一種調(diào)度。因此在三種類型的OS中，都無一例外地配置了進(jìn)程調(diào)度。此外它也是對系統(tǒng)性能影響最大的一種處理機調(diào)度，相應(yīng)的，有關(guān)進(jìn)程調(diào)度的算法也較多。2525第三章 處理機調(diào)度與死鎖3.3.1 進(jìn)程調(diào)度的任務(wù)、機制和方式 1. 進(jìn)程

14、調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)主要有三：(1) 保存處理機的現(xiàn)場信息。(2) 按某種算法選取進(jìn)程。(3) 把處理器分配給進(jìn)程。 2626第三章 處理機調(diào)度與死鎖2. 進(jìn)程調(diào)度機制為了實現(xiàn)進(jìn)程調(diào)度，在進(jìn)程調(diào)度機制中，應(yīng)具有如下三個基本部分，如圖3-1所示。(1) 排隊器。 (2) 分派器。 (3) 上下文切換器。 2727第三章 處理機調(diào)度與死鎖圖3-1 進(jìn)程調(diào)度機制2828第三章 處理機調(diào)度與死鎖3. 進(jìn)程調(diào)度方式1) 非搶占方式(Nonpreemptive Mode)在采用這種調(diào)度方式時，一旦把處理機分配給某進(jìn)程后，就一直讓它運行下去，決不會因為時鐘中斷或任何其它原因去搶占當(dāng)前正在運行進(jìn)程的處理機

15、，直至該進(jìn)程完成，或發(fā)生某事件而被阻塞時，才把處理機分配給其它進(jìn)程。2929第三章 處理機調(diào)度與死鎖2) 搶占方式(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機重新分配給另一進(jìn)程。在現(xiàn)代OS中廣泛采用搶占方式，這是因為：對于批處理機系統(tǒng)，可以防止一個長進(jìn)程長時間地占用處理機，以確保處理機能為所有進(jìn)程提供更為公平的服務(wù)。在分時系統(tǒng)中，只有采用搶占方式才有可能實現(xiàn)人機交互。在實時系統(tǒng)中，搶占方式能滿足實時任務(wù)的需求。但搶占方式比較復(fù)雜，所需付出的系統(tǒng)開銷也較大。3030第三章 處理機調(diào)度與死鎖3.3.2 輪轉(zhuǎn)調(diào)度算法1.

16、輪轉(zhuǎn)法的基本原理在輪轉(zhuǎn)(RR)法中，系統(tǒng)將所有的就緒進(jìn)程按FCFS策略排成一個就緒隊列。系統(tǒng)可設(shè)置每隔一定時間(如30ms)便產(chǎn)生一次中斷，去激活進(jìn)程調(diào)度程序進(jìn)行調(diào)度，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。當(dāng)它運行完畢后，又把處理機分配給就緒隊列中新的隊首進(jìn)程，也讓它執(zhí)行一個時間片。這樣，就可以保證就緒隊列中的所有進(jìn)程在確定的時間段內(nèi)，都能獲得一個時間片的處理機時間。31 31第三章 處理機調(diào)度與死鎖2. 進(jìn)程切換時機在RR調(diào)度算法中，應(yīng)在何時進(jìn)行進(jìn)程的切換，可分為兩種情況： 若一個時間片尚未用完，正在運行的進(jìn)程便已經(jīng)完成，就立即激活調(diào)度程序，將它從就緒隊列中刪除，再調(diào)度就緒隊列中隊首

17、的進(jìn)程運行，并啟動一個新的時間片。 在一個時間片用完時，計時器中斷處理程序被激活。如果進(jìn)程尚未運行完畢，調(diào)度程序?qū)阉屯途w隊列的末尾。3232第三章 處理機調(diào)度與死鎖3. 時間片大小的確定在輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的影響。 圖3-2示出了時間片大小對響應(yīng)時間的影響，其中圖(a)是時間片略大于典型交互的時間，而圖(b)是時間片小于典型交互的時間。圖3-3示出了時間片分別為q=1和q=4時對平均周轉(zhuǎn)時間的影響。 3333第三章 處理機調(diào)度與死鎖圖3-2 時間片大小對響應(yīng)時間的影響3434第三章 處理機調(diào)度與死鎖圖3-3 q=1和q=4時進(jìn)程的周轉(zhuǎn)時間3535第三章 處理機調(diào)度與

18、死鎖3.3.3 優(yōu)先級調(diào)度算法1. 優(yōu)先級調(diào)度算法的類型優(yōu)先級進(jìn)程調(diào)度算法，是把處理機分配給就緒隊列中優(yōu)先級最高的進(jìn)程。這時，又可進(jìn)一步把該算法分成如下兩種。(1) 非搶占式優(yōu)先級調(diào)度算法。(2) 搶占式優(yōu)先級調(diào)度算法。 3636第三章 處理機調(diào)度與死鎖2. 優(yōu)先級的類型1) 靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級是在創(chuàng)建進(jìn)程時確定的，在進(jìn)程的整個運行期間保持不變。優(yōu)先級是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如0255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。確定進(jìn)程優(yōu)先級大小的依據(jù)有如下三個：(1) 進(jìn)程類型。(2) 進(jìn)程對資源的需求。(3) 用戶要求。3737第三章 處理機調(diào)度與死鎖2) 動態(tài)優(yōu)先級動態(tài)優(yōu)先級是指

19、在創(chuàng)建進(jìn)程之初，先賦予其一個優(yōu)先級，然后其值隨進(jìn)程的推進(jìn)或等待時間的增加而改變，以便獲得更好的調(diào)度性能。 3838第三章 處理機調(diào)度與死鎖3.3.4 多隊列調(diào)度算法如前所述的各種調(diào)度算法，尤其在應(yīng)用于進(jìn)程調(diào)度時，由于系統(tǒng)中僅設(shè)置一個進(jìn)程的就緒隊列，即低級調(diào)度算法是固定的、單一的，無法滿足系統(tǒng)中不同用戶對進(jìn)程調(diào)度策略的不同要求，在多處理機系統(tǒng)中，這種單一調(diào)度策略實現(xiàn)機制的缺點更顯突出，由此，多級隊列調(diào)度算法能夠在一定程度上彌補這一缺點。3939第三章 處理機調(diào)度與死鎖3.3.5 多級反饋隊列(multileved feedback queue)調(diào)度算法 1. 調(diào)度機制多級反饋隊列調(diào)度算法的調(diào)度機

20、制可描述如下：(1) 設(shè)置多個就緒隊列。 圖3-4是多級反饋隊列算法的示意圖。4040第三章 處理機調(diào)度與死鎖圖3-4 多級反饋隊列調(diào)度算法41 41第三章 處理機調(diào)度與死鎖(2) 每個隊列都采用FCFS算法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可撤離系統(tǒng)。否則，即它在一個時間片結(jié)束時尚未完成，調(diào)度程序?qū)⑵滢D(zhuǎn)入第二隊列的末尾等待調(diào)度；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，依此類推。當(dāng)進(jìn)程最后被降到第n隊列后，在第n隊列中便采取按RR方式運行。4242第三章 處理機調(diào)度與死鎖(3) 按

21、隊列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列中的諸進(jìn)程運行，僅當(dāng)?shù)谝魂犃锌臻e時才調(diào)度第二隊列中的進(jìn)程運行；換言之，僅當(dāng)?shù)?(i-1)所有隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運行。如果處理機正在第i隊列中為某進(jìn)程服務(wù)時又有新進(jìn)程進(jìn)入任一優(yōu)先級較高的隊列，此時須立即把正在運行的進(jìn)程放回到第i隊列的末尾，而把處理機分配給新到的高優(yōu)先級進(jìn)程。4343第三章 處理機調(diào)度與死鎖2. 調(diào)度算法的性能在多級反饋隊列調(diào)度算法中，如果規(guī)定第一個隊列的時間片略大于多數(shù)人機交互所需之處理時間時，便能較好地滿足各種類型用戶的需要。(1) 終端型用戶。(2) 短批處理作業(yè)用戶。(3) 長批處理作業(yè)用戶。4444第三章

22、處理機調(diào)度與死鎖3.3.6 基于公平原則的調(diào)度算法 1. 保證調(diào)度算法保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出的保證并不是優(yōu)先運行，而是明確的性能保證，該算法可以做到調(diào)度的公平性。一種比較容易實現(xiàn)的性能保證是處理機分配的公平性。如果在系統(tǒng)中有n個相同類型的進(jìn)程同時運行，為公平起見，須保證每個進(jìn)程都獲得相同的處理機時間1/n。 4545第三章 處理機調(diào)度與死鎖在實施公平調(diào)度算法時系統(tǒng)中必須具有這樣一些功能：(1) 跟蹤計算每個進(jìn)程自創(chuàng)建以來已經(jīng)執(zhí)行的處理時間。(2) 計算每個進(jìn)程應(yīng)獲得的處理機時間，即自創(chuàng)建以來的時間除以n。(3) 計算進(jìn)程獲得處理機時間的比率，即進(jìn)程實際執(zhí)行的處理時

23、間和應(yīng)獲得的處理機時間之比。(4) 比較各進(jìn)程獲得處理機時間的比率。如進(jìn)程A的比率最低，為0.5，而進(jìn)程B的比率為0.8，進(jìn)程C的比率為1.2等。(5) 調(diào)度程序應(yīng)選擇比率最小的進(jìn)程將處理機分配給它，并讓該進(jìn)程一直運行，直到超過最接近它的進(jìn)程比率為止。4646第三章 處理機調(diào)度與死鎖2. 公平分享調(diào)度算法分配給每個進(jìn)程相同的處理機時間，顯然，這對諸進(jìn)程而言，是體現(xiàn)了一定程度的公平，但如果各個用戶所擁有的進(jìn)程數(shù)不同，就會發(fā)生對用戶的不公平問題。 4747第三章 處理機調(diào)度與死鎖3.4 實 時 調(diào) 度在實時系統(tǒng)中，可能存在著兩類不同性質(zhì)的實時任務(wù)，即HRT任務(wù)和SRT任務(wù)，它們都聯(lián)系著一個截止時間

24、。為保證系統(tǒng)能正常工作，實時調(diào)度必須能滿足實時任務(wù)對截止時間的要求。為此，實現(xiàn)實時調(diào)度應(yīng)具備一定的條件。4848第三章 處理機調(diào)度與死鎖3.4.1 實現(xiàn)實時調(diào)度的基本條件1. 提供必要的信息為了實現(xiàn)實時調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的信息：(1) 就緒時間，是指某任務(wù)成為就緒狀態(tài)的起始時間，在周期任務(wù)的情況下，它是事先預(yù)知的一串時間序列。(2) 開始截止時間和完成截止時間，對于典型的實時應(yīng)用，只須知道開始截止時間，或者完成截止時間。4949第三章 處理機調(diào)度與死鎖(3) 處理時間，一個任務(wù)從開始執(zhí)行，直至完成時所需的時間。(4) 資源要求，任務(wù)執(zhí)行時所需的一組資源。(5) 優(yōu)先級，如果某任

25、務(wù)的開始截止時間錯過，勢必引起故障，則應(yīng)為該任務(wù)賦予“絕對”優(yōu)先級；如果其開始截止時間的錯過，對任務(wù)的繼續(xù)運行無重大影響，則可為其賦予“相對”優(yōu)先級，供調(diào)度程序參考。5050第三章 處理機調(diào)度與死鎖2. 系統(tǒng)處理能力強在實時系統(tǒng)中，若處理機的處理能力不夠強，則有可能因處理機忙不過，而致使某些實時任務(wù)不能得到及時處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實時任務(wù)HRT，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件系統(tǒng)才是可調(diào)度的：1PCm1iii51 51第三章 處理機調(diào)度與死鎖提高系統(tǒng)處理能力的途徑有二：一是采用單處理機系統(tǒng)，但須

26、增強其處理能力，以顯著地減少對每一個任務(wù)的處理時間；二是采用多處理機系統(tǒng)。假定系統(tǒng)中的處理機數(shù)為N，則應(yīng)將上述的限制條件改為：NPCm1iii5252第三章 處理機調(diào)度與死鎖3. 采用搶占式調(diào)度機制在含有HRT任務(wù)的實時系統(tǒng)中，廣泛采用搶占機制。這樣便可滿足HRT任務(wù)對截止時間的要求。但這種調(diào)度機制比較復(fù)雜。 5353第三章 處理機調(diào)度與死鎖4. 具有快速切換機制為保證硬實時任務(wù)能及時運行，在系統(tǒng)中還應(yīng)具有快速切換機制，使之能進(jìn)行任務(wù)的快速切換。該機制應(yīng)具有如下兩方面的能力：(1) 對中斷的快速響應(yīng)能力。對緊迫的外部事件請求中斷能及時響應(yīng)，要求系統(tǒng)具有快速硬件中斷機構(gòu)，還應(yīng)使禁止中斷的時間間隔

27、盡量短，以免耽誤時機(其它緊迫任務(wù))。(2) 快速的任務(wù)分派能力。為了提高分派程序進(jìn)行任務(wù)切換時的速度，應(yīng)使系統(tǒng)中的每個運行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時間開銷。5454第三章 處理機調(diào)度與死鎖3.4.2 實時調(diào)度算法的分類 可以按不同方式對實時調(diào)度算法加以分類： 根據(jù)實時任務(wù)性質(zhì)，可將實時調(diào)度的算法分為硬實時調(diào)度算法和軟實時調(diào)度算法； 按調(diào)度方式，則可分為非搶占調(diào)度算法和搶占調(diào)度算法。 5555第三章 處理機調(diào)度與死鎖1. 非搶占式調(diào)度算法(1) 非搶占式輪轉(zhuǎn)調(diào)度算法。(2) 非搶占式優(yōu)先調(diào)度算法。 5656第三章 處理機調(diào)度與死鎖2. 搶占式調(diào)度算法可根據(jù)搶占發(fā)生時間的不同而進(jìn)一步分

28、成以下兩種調(diào)度算法：(1) 基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法。(2) 立即搶占(Immediate Preemption)的優(yōu)先級調(diào)度算法。圖3-5中的(a)、(b)、(c)、(d)分別示出了四種情況的調(diào)度時間。 5757第三章 處理機調(diào)度與死鎖圖3-5 實時進(jìn)程調(diào)度5858第三章 處理機調(diào)度與死鎖3.4.3 最早截止時間優(yōu)先EDF(Earliest Deadline First)算法 1. 非搶占式調(diào)度方式用于非周期實時任務(wù)圖3-6示出了將該算法用于非搶占調(diào)度方式之例。 5959第三章 處理機調(diào)度與死鎖圖3-6EDF算法用于非搶占調(diào)度方式6060第三章 處理機調(diào)度與死鎖2. 搶占式調(diào)度方式

29、用于周期實時任務(wù)圖3-7示出了將該算法用于搶占調(diào)度方式之例。在該例中有兩個周期任務(wù)，任務(wù)A和任務(wù)B的周期時間分別為20 ms和50 ms，每個周期的處理時間分別為10ms和25ms。61 61第三章 處理機調(diào)度與死鎖圖3-7 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例6262第三章 處理機調(diào)度與死鎖3.4.4 最低松弛度優(yōu)先LLF(Least Laxity First)算法該算法在確定任務(wù)的優(yōu)先級時，根據(jù)的是任務(wù)的緊急(或松弛)程度。任務(wù)緊急程度愈高，賦予該任務(wù)的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。 該算法主要用于可搶占調(diào)度方式中。假如在一個實時系統(tǒng)中有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)

30、行一次，執(zhí)行時間為10ms，任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。由此可知，任務(wù)A和B每次必須完成的時間分別為：A1、A2、A3、和B1、B2、B3、，見圖3-8。 6363第三章 處理機調(diào)度與死鎖圖3-8 A和B任務(wù)每次必須完成的時間6464第三章 處理機調(diào)度與死鎖圖3-9示出了具有兩個周期性實時任務(wù)的調(diào)度情況。 圖3-9 利用ELLF算法進(jìn)行調(diào)度的情況6565第三章 處理機調(diào)度與死鎖3.4.5 優(yōu)先級倒置(priority inversion problem) 1. 優(yōu)先級倒置的形成當(dāng)前OS廣泛采用優(yōu)先級調(diào)度算法和搶占方式，然而在系統(tǒng)中存在著影響進(jìn)程運行的資源而可能產(chǎn)生“優(yōu)先級

31、倒置”的現(xiàn)象，即高優(yōu)先級進(jìn)程(或線程)被低優(yōu)先級進(jìn)程(或線程)延遲或阻塞。我們通過一個例子來說明該問題。 6666第三章 處理機調(diào)度與死鎖假如P3最先執(zhí)行，在執(zhí)行了P(mutex)操作后，進(jìn)入到臨界區(qū)CS-3。在時刻a，P2就緒，因為它比P3的優(yōu)先級高，P2搶占了P3的處理機而運行，如圖3-10所示。 6767第三章 處理機調(diào)度與死鎖圖3-10 優(yōu)先級倒置示意圖6868第三章 處理機調(diào)度與死鎖2. 優(yōu)先級倒置的解決方法一種簡單的解決方法是規(guī)定：假如進(jìn)程P3在進(jìn)入臨界區(qū)后P3所占用的處理機就不允許被搶占。 圖3-11示出了采用動態(tài)優(yōu)先級繼承方法后，P1、P2、P3三個進(jìn)程的運行情況。 6969第

32、三章 處理機調(diào)度與死鎖圖3-11 采用了動態(tài)優(yōu)先級繼承方法的運行情況7070第三章 處理機調(diào)度與死鎖3.5 死 鎖 概 述3.5.1 資源問題在系統(tǒng)中有許多不同類型的資源，其中可以引起死鎖的主要是，需要采用互斥訪問方法的、不可以被搶占的資源，即在前面介紹的臨界資源。系統(tǒng)中這類資源有很多，如打印機、數(shù)據(jù)文件、隊列、信號量等。71 71第三章 處理機調(diào)度與死鎖1. 可重用性資源和消耗性資源1) 可重用性資源 可重用性資源是一種可供用戶重復(fù)使用多次的資源，它具有如下性質(zhì)：(1) 每一個可重用性資源中的單元只能分配給一個進(jìn)程使用，不允許多個進(jìn)程共享。(2) 進(jìn)程在使用可重用性資源時，須按照這樣的順序：

33、 請求資源。如果請求資源失敗，請求進(jìn)程將會被阻塞或循環(huán)等待。 使用資源。進(jìn)程對資源進(jìn)行操作，如用打印機進(jìn)行打??； 釋放資源。當(dāng)進(jìn)程使用完后自己釋放資源。(3) 系統(tǒng)中每一類可重用性資源中的單元數(shù)目是相對固定的，進(jìn)程在運行期間既不能創(chuàng)建也不能刪除它。7272第三章 處理機調(diào)度與死鎖2) 可消耗性資源可消耗性資源又稱為臨時性資源，它是在進(jìn)程運行期間，由進(jìn)程動態(tài)地創(chuàng)建和消耗的，它具有如下性質(zhì)： 每一類可消耗性資源的單元數(shù)目在進(jìn)程運行期間是可以不斷變化的，有時它可以有許多，有時可能為0； 進(jìn)程在運行過程中，可以不斷地創(chuàng)造可消耗性資源的單元，將它們放入該資源類的緩沖區(qū)中，以增加該資源類的單元數(shù)目。 進(jìn)程

34、在運行過程中，可以請求若干個可消耗性資源單元，用于進(jìn)程自己的消耗，不再將它們返回給該資源類中。 7373第三章 處理機調(diào)度與死鎖2. 可搶占性資源和不可搶占性資源1) 可搶占性資源可把系統(tǒng)中的資源分成兩類，一類是可搶占性資源，是指某進(jìn)程在獲得這類資源后，該資源可以再被其它進(jìn)程或系統(tǒng)搶占。2) 不可搶占性資源另一類資源是不可搶占性資源，即一旦系統(tǒng)把某資源分配給該進(jìn)程后，就不能將它強行收回，只能在進(jìn)程用完后自行釋放。 7474第三章 處理機調(diào)度與死鎖3.5.2 計算機系統(tǒng)中的死鎖 1. 競爭不可搶占性資源引起死鎖通常系統(tǒng)中所擁有的不可搶占性資源其數(shù)量不足以滿足多個進(jìn)程運行的需要，使得進(jìn)程在運行過程

35、中，會因爭奪資源而陷入僵局。 7575第三章 處理機調(diào)度與死鎖我們可將上面的問題利用資源分配圖進(jìn)行描述，用方塊代表可重用的資源(文件)，用圓圈代表進(jìn)程，見圖3-12所示。 7676第三章 處理機調(diào)度與死鎖圖3-12共享文件時的死鎖情況 7777第三章 處理機調(diào)度與死鎖2. 競爭可消耗資源引起死鎖現(xiàn)在進(jìn)一步介紹競爭可消耗資源所引起的死鎖。圖3-13示出了在三個進(jìn)程之間，在利用消息通信機制進(jìn)行通信時所形成的死鎖情況。 7878第三章 處理機調(diào)度與死鎖 圖3-13 進(jìn)程之間通信時的死鎖 7979第三章 處理機調(diào)度與死鎖3. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖除了系統(tǒng)中多個進(jìn)程對資源的競爭會引發(fā)死鎖外，進(jìn)程在運

36、行過程中，對資源進(jìn)行申請和釋放的順序是否合法，也是在系統(tǒng)中是否會產(chǎn)生死鎖的一個重要因素。 8080第三章 處理機調(diào)度與死鎖1) 進(jìn)程推進(jìn)順序合法在進(jìn)程P1和P2并發(fā)執(zhí)行時，如果按圖3-14中的曲線所示的順序推進(jìn)：P1：Request(R1)P1：Request(R2)P1：Releast(R1)P1：Release(R2)P2：Request(R2)P2：Request(R1)P2：Release(R2)P2：Release(R1)，兩個進(jìn)程可順利完成。類似地，若按圖中曲線和所示的順序推進(jìn)，兩進(jìn)程也可以順利完成。我們稱這種不會引起進(jìn)程死鎖的推進(jìn)順序是合法的。81 81第三章 處理機調(diào)度與死鎖2

37、) 進(jìn)程推進(jìn)順序非法若并發(fā)進(jìn)程P1和P2按圖3-14中曲線所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時P1保持了資源R1，P2保持了資源R2，系統(tǒng)處于不安全狀態(tài)。此刻，如果兩個進(jìn)程繼續(xù)向前推進(jìn)，就可能發(fā)生死鎖。例如，當(dāng)P1運行到P1：Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運行到P2：Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖，這樣的進(jìn)程推進(jìn)順序就是非法的。8282第三章 處理機調(diào)度與死鎖圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響8383第三章 處理機調(diào)度與死鎖3.5.3 死鎖的定義、必要條件和處理方法 1. 死鎖的定義在一組進(jìn)程發(fā)生死鎖的情況下，這

38、組死鎖進(jìn)程中的每一個進(jìn)程，都在等待另一個死鎖進(jìn)程所占有的資源。 8484第三章 處理機調(diào)度與死鎖2. 產(chǎn)生死鎖的必要條件雖然進(jìn)程在運行過程中可能會發(fā)生死鎖，但產(chǎn)生進(jìn)程死鎖是必須具備一定條件的。綜上所述不難看出，產(chǎn)生死鎖必須同時具備下面四個必要條件，只要其中任一個條件不成立，死鎖就不會發(fā)生：(1) 互斥條件。(2) 請求和保持條件。(3) 不可搶占條件。(4) 循環(huán)等待條件。8585第三章 處理機調(diào)度與死鎖3. 處理死鎖的方法目前處理死鎖的方法可歸結(jié)為四種：(1) 預(yù)防死鎖。(2) 避免死鎖。(3) 檢測死鎖。(4) 解除死鎖。8686第三章 處理機調(diào)度與死鎖3.6 預(yù) 防 死 鎖預(yù)防死鎖的方法

39、是通過破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個，以避免發(fā)生死鎖。由于互斥條件是非共享設(shè)備所必須的，不僅不能改變，還應(yīng)加以保證，因此主要是破壞產(chǎn)生死鎖的后三個條件。8787第三章 處理機調(diào)度與死鎖3.6.1 破壞“請求和保持”條件 為了能破壞“請求和保持”條件，系統(tǒng)必須保證做到：當(dāng)一個進(jìn)程在請求資源時，它不能持有不可搶占資源。該保證可通過如下兩個不同的協(xié)議實現(xiàn)：1. 第一種協(xié)議該協(xié)議規(guī)定，所有進(jìn)程在開始運行之前，必須一次性地申請其在整個運行過程中所需的全部資源。 8888第三章 處理機調(diào)度與死鎖2. 第二種協(xié)議該協(xié)議是對第一種協(xié)議的改進(jìn)，它允許一個進(jìn)程只獲得運行初期所需的資源后，便開始運行。 8

40、989第三章 處理機調(diào)度與死鎖3.6.2 破壞“不可搶占”條件 為了能破壞“不可搶占”條件，協(xié)議中規(guī)定，當(dāng)一個已經(jīng)保持了某些不可被搶占資源的進(jìn)程，提出新的資源請求而不能得到滿足時，它必須釋放已經(jīng)保持的所有資源，待以后需要時再重新申請。這意味著進(jìn)程已占有的資源會被暫時地釋放，或者說是被搶占了，從而破壞了“不可搶占”條件。9090第三章 處理機調(diào)度與死鎖3.6.3 破壞“循環(huán)等待”條件 一個能保證“循環(huán)等待”條件不成立的方法是，對系統(tǒng)所有資源類型進(jìn)行線性排序，并賦予不同的序號。 91 91第三章 處理機調(diào)度與死鎖3.7 避 免 死 鎖避免死鎖同樣是屬于事先預(yù)防的策略，但并不是事先采取某種限制措施，

41、破壞產(chǎn)生死鎖的必要條件，而是在資源動態(tài)分配過程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)，以避免發(fā)生死鎖。這種方法所施加的限制條件較弱，可能獲得較好的系統(tǒng)性能，目前常用此方法來避免發(fā)生死鎖。9292第三章 處理機調(diào)度與死鎖3.7.1系統(tǒng)安全狀態(tài) 在死鎖避免方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。當(dāng)系統(tǒng)處于安全狀態(tài)時，可避免發(fā)生死鎖。反之，當(dāng)系統(tǒng)處于不安全狀態(tài)時，則可能進(jìn)入到死鎖狀態(tài)。1. 安全狀態(tài)在該方法中，允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次資源分配的安全性。 9393第三章 處理機調(diào)度與死鎖2. 安全狀態(tài)之例假定系統(tǒng)中有三個進(jìn)程P1、P2和P3，共有12臺磁帶機。進(jìn)程P1總

42、共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：9494第三章 處理機調(diào)度與死鎖3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。 9595第三章 處理機調(diào)度與死鎖3.7.2 利用銀行家算法避免死鎖最有代表性的避免死鎖的算法是Dijkstra的銀行家算法。起這樣的名字是由于該算法原本是為銀行系統(tǒng)設(shè)計的，以確保銀行在發(fā)放現(xiàn)金貸款時，不會發(fā)生不能滿足所有客戶需要的情況。在OS中也可用它來實現(xiàn)避免死鎖。9696第三章 處理機調(diào)度與死鎖1. 銀行家算

43、法中的數(shù)據(jù)結(jié)構(gòu)為了實現(xiàn)銀行家算法，在系統(tǒng)中必須設(shè)置這樣四個數(shù)據(jù)結(jié)構(gòu)，分別用來描述系統(tǒng)中可利用的資源、所有進(jìn)程對資源的最大需求、系統(tǒng)中的資源分配，以及所有進(jìn)程還需要多少資源的情況。(1) 可利用資源向量Available。(2) 最大需求矩陣Max。(3) 分配矩陣Allocation。(4) 需求矩陣Need。9797第三章 處理機調(diào)度與死鎖2. 銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requestij=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1) 如果RequestijNeedi, j，便轉(zhuǎn)向步驟(2)； 否則認(rèn)為出錯，因為它所

44、需要的資源數(shù)已超過它所宣布的最大值。(2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)； 否則，表示尚無足夠資源，Pi須等待。9898第三章 處理機調(diào)度與死鎖(3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej = Availablej-Requestij; Allocationi, j = Allocationi, j+Requestij; Needi, j = Needi, j-Requestij;(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探

45、分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。9999第三章 處理機調(diào)度與死鎖3. 安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：(1) 設(shè)置兩個向量： 工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work := Available； Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做Finishi := false；當(dāng)有足夠資源分配給進(jìn)程時，再令Finishi := true。100100第三章 處理機調(diào)度與死鎖(2) 從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程： Finishi=false; Needi

46、, jWorkj;若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。(3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj = Workj+Allocationi, j;Finishi =true;go to step 2;(4) 如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。101101第三章 處理機調(diào)度與死鎖假定系統(tǒng)中有五個進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。102102第三章 處理機調(diào)度與死鎖圖3

47、-15 T0時刻的資源分配表103103第三章 處理機調(diào)度與死鎖(1) T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進(jìn)行分析(如圖3-16所示)可知，在T0時刻存在著一個安全序列P1, P3, P4, P2, P0，故系統(tǒng)是安全的。104104第三章 處理機調(diào)度與死鎖圖3-16 T0時刻的安全序列105105第三章 處理機調(diào)度與死鎖(2) P1請求資源：P1發(fā)出請求向量Request1(1, 0, 2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2)； Request1(1, 0, 2)Available1(3, 3, 2)； 系統(tǒng)先假定

48、可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示； 再利用安全性算法檢查此時系統(tǒng)是否安全，如圖3-17所示。106106第三章 處理機調(diào)度與死鎖圖3-17 P1申請資源時的安全性檢查107107第三章 處理機調(diào)度與死鎖(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ā)出請求向量Request0(0，2，0

49、)，系統(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ù)，如圖3-18所示。108108第三章 處理機調(diào)度與死鎖圖3-18 為P0分配資源后的有關(guān)資源數(shù)據(jù)109109第三章 處理機調(diào)度與死鎖(5) 進(jìn)行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資源。110110第三章 處理機調(diào)度與死鎖3.8 死鎖的檢測與解除 如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會

50、發(fā)生死鎖。在這種情況下，系統(tǒng)應(yīng)當(dāng)提供兩個算法： 死鎖檢測算法。該方法用于檢測系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。 死鎖解除算法。當(dāng)認(rèn)定系統(tǒng)中已發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來。111111第三章 處理機調(diào)度與死鎖3.8.1 死鎖的檢測 為了能對系統(tǒng)中是否已發(fā)生了死鎖進(jìn)行檢測，在系統(tǒng)中必須： 保存有關(guān)資源的請求和分配信息； 提供一種算法，它利用這些信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。1. 資源分配圖(Resource Allocation Graph)系統(tǒng)死鎖，可利用資源分配圖來描述。 112112第三章 處理機調(diào)度與死鎖該圖是由一組結(jié)點N和一組邊E所組成的一個對偶G=(N,

51、E)，它具有下述形式的定義和限制： (1) 把N分為兩個互斥的子集，即一組進(jìn)程結(jié)點P=P1, P2, , Pn和一組資源結(jié)點R=R1, R2, , Rn，N=PR。在圖3-19所示的例子中，P=P1, P2，R=R1, R2，N=R1, R2P1, P2。(2) 凡屬于E中的一個邊eE，都連接著P中的一個結(jié)點和R中的一個結(jié)點，e=Pi, Rj是資源請求邊，由進(jìn)程Pi指向資源Rj，它表示進(jìn)程Pi請求一個單位的Rj資源。E=Rj, Pi是資源分配邊，由資源Rj指向進(jìn)程Pi，它表示把一個單位的資源Rj分配給進(jìn)程Pi。圖3-19中示出了兩個請求邊和兩個分配邊，即E=(P1, R2), (R2, P2)

52、, (P2, R1), (R1, P1)。113113第三章 處理機調(diào)度與死鎖圖3-19 每類資源有多個時的情況114114第三章 處理機調(diào)度與死鎖2死鎖定理我們可以利用把資源分配圖加以簡化的方法(圖3-19)，來檢測當(dāng)系統(tǒng)處于S狀態(tài)時，是否為死鎖狀態(tài)。簡化方法如下：(1) 在資源分配圖中，找出一個既不阻塞又非獨立的進(jìn)程結(jié)點Pi。在順利的情況下，Pi可獲得所需資源而繼續(xù)運行，直至運行完畢，再釋放其所占有的全部資源，這相當(dāng)于消去Pi的請求邊和分配邊，使之成為孤立的結(jié)點。在圖3-20(a)中，將P1的兩個分配邊和一個請求邊消去，便形成圖(b)所示的情況。115115第三章 處理機調(diào)度與死鎖圖3-2

53、0 資源分配圖的簡化116116第三章 處理機調(diào)度與死鎖(2) P1釋放資源后，便可使P2獲得資源而繼續(xù)運行，直至P2完成后又釋放出它所占有的全部資源，形成圖(c)所示的情況，即將P2的兩條請求邊和一條分配邊消去。(3) 在進(jìn)行一系列的簡化后，若能消去圖中所有的邊，使所有的進(jìn)程結(jié)點都成為孤立結(jié)點，則稱該圖是可完全簡化的；若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的。117117第三章 處理機調(diào)度與死鎖3死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)類似于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：(1) 可利用資源向量Available，它表示了m類資源中每一類資源的可用數(shù)目。(2) 把不占用資源的進(jìn)程(