湯小丹 操作系統(tǒng) 課件 第三章

第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.2作業(yè)與作業(yè)調(diào)度3.3進(jìn)程調(diào)度3.4實(shí)時(shí)調(diào)度3.5死鎖概述3.6預(yù)防死鎖3.7避免死鎖3.8死鎖的檢測(cè)與解除習(xí)題翻譯：

Endusersuseapplicationsoftwaretoaccomplishspecifictas-ks.Forexample,weusewordprocessingprogramstocreatelett-ers,documents,andreports.However,endusersalsousesystemso-ftwere.Systemsoftwereworkswithendusers,applicationsoftwa-re,andcomputerhardwaretohandlethemajorityoftechnicaldet-ails.Forexample,systemsoftwarecontrolswhereawordproces-singprogramisstoredinmemory,howcommandsareconvertedsothatthesystemunitcanprocessthem,andwhereacompleteddocumentorfileissaved.

3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

在多道程序系統(tǒng)中，調(diào)度的實(shí)質(zhì)是一種資源分配，處理機(jī)調(diào)度是對(duì)處理機(jī)資源進(jìn)行分配。處理機(jī)調(diào)度算法是指根據(jù)處理機(jī)分配策略所規(guī)定的處理機(jī)分配算法。在多道批處理系統(tǒng)中，一個(gè)作業(yè)從提交到獲得處理機(jī)執(zhí)行，直至作業(yè)運(yùn)行完畢，可能需要經(jīng)歷多級(jí)處理機(jī)調(diào)度，下面先來(lái)了解處理機(jī)調(diào)度的層次。3.1.1處理機(jī)調(diào)度的層次

1.高級(jí)調(diào)度(HighLevelScheduling)

又稱(chēng)為作業(yè)調(diào)度、宏觀調(diào)度或長(zhǎng)程調(diào)度，有時(shí)也稱(chēng)作業(yè)調(diào)度為接納調(diào)度。用于決定把后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，為他們分配必要的資源，并創(chuàng)建進(jìn)程。

批處理系統(tǒng)：大多配有作業(yè)調(diào)度；分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)：往往不配置作業(yè)調(diào)度。

2.低級(jí)調(diào)度(LowLevelScheduling)

通常也稱(chēng)為進(jìn)程調(diào)度、微觀調(diào)度或短程調(diào)度（Short-TermScheduling），進(jìn)程調(diào)度是最基本的一種調(diào)度，在三種OS中都有。用于決定就緒隊(duì)列中哪個(gè)進(jìn)程應(yīng)先獲得處理機(jī)，并將處理機(jī)分配給選中的進(jìn)程。3.中級(jí)調(diào)度(IntermediateScheduling)

又稱(chēng)為內(nèi)存調(diào)度、交換調(diào)度或中程調(diào)度（Medium-TermSchedulin-g）。它按一定的算法將外存中已具備運(yùn)行條件的進(jìn)程換入內(nèi)存，而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。

引入中級(jí)調(diào)度的目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)之外存去等待，把此時(shí)的進(jìn)程狀態(tài)稱(chēng)為靜止就緒狀態(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)度。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能。3.1.2處理機(jī)調(diào)度算法的目標(biāo)

1.處理機(jī)調(diào)度算法的共同目標(biāo)

(1)資源利用率。為提高系統(tǒng)的資源利用率，應(yīng)使系統(tǒng)中的處理機(jī)和其它所有資源都盡可能地保持忙碌狀態(tài)，其中最重要的處理機(jī)利用率可用以下方法計(jì)算：(2)公平性。公平性是指應(yīng)使諸進(jìn)程都獲得合理的CPU時(shí)間，不會(huì)發(fā)生進(jìn)程饑餓現(xiàn)象。公平性是相對(duì)的，對(duì)相同類(lèi)型的進(jìn)程應(yīng)獲得相同的服務(wù)；但對(duì)于不同類(lèi)型的進(jìn)程，由于其緊急程度或重要性的不同，則應(yīng)提供不同的服務(wù)。

(3)平衡性。由于在系統(tǒng)中可能具有多種類(lèi)型的進(jìn)程，有的屬于計(jì)算型作業(yè)，有的屬于I/O型。為使系統(tǒng)中的CPU和各種外部設(shè)備都能經(jīng)常處于忙碌狀態(tài)，調(diào)度算法應(yīng)盡可能保持系統(tǒng)資源使用的平衡性。

(4)策略強(qiáng)制執(zhí)行。對(duì)所制訂的策略其中包括安全策略，只要需要，就必須予以準(zhǔn)確地執(zhí)行，即使會(huì)造成某些工作的延遲也要執(zhí)行。

2.批處理系統(tǒng)的目標(biāo)

(1)平均周轉(zhuǎn)時(shí)間短。

對(duì)每個(gè)用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為計(jì)算機(jī)系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時(shí)間最短，這不僅會(huì)有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意。應(yīng)使作業(yè)周轉(zhuǎn)時(shí)間和作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能短。否則，會(huì)使許多用戶的等待時(shí)間過(guò)長(zhǎng)，這將會(huì)引起用戶特別是短作業(yè)用戶的不滿?？砂哑骄苻D(zhuǎn)時(shí)間描述為：為了進(jìn)一步反映調(diào)度的性能，更清晰地描述各進(jìn)程在其周轉(zhuǎn)時(shí)間中，等待和執(zhí)行時(shí)間的具體分配狀況，往往使用帶權(quán)周轉(zhuǎn)時(shí)間，即作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間Ts之比，即W?=?T/Ts。而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為：(2)系統(tǒng)吞吐量高。由于吞吐量是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長(zhǎng)度有關(guān)。事實(shí)上，如果單純是為了獲得高的系統(tǒng)吞吐量，就應(yīng)盡量多地選擇短作業(yè)運(yùn)行。

(3)處理機(jī)利用率高。對(duì)于大、中型計(jì)算機(jī)，CPU價(jià)格十分昂貴，致使處理機(jī)的利用率成為衡量系統(tǒng)性能的十分重要的指標(biāo)；而調(diào)度方式和算法又對(duì)處理機(jī)的利用率起著十分重要的作用。如果單純是為使處理機(jī)利用率高，應(yīng)盡量多地選擇計(jì)算量大的作業(yè)運(yùn)行。由上所述可以看出，這些要求之間是存在著一定矛盾的。

3.分時(shí)系統(tǒng)的目標(biāo)

(1)響應(yīng)時(shí)間快。

(2)均衡性。

4.實(shí)時(shí)系統(tǒng)的目標(biāo)

(1)截止時(shí)間的保證。

(2)可預(yù)測(cè)性。3.2作業(yè)與作業(yè)調(diào)度

在多道批處理系統(tǒng)中，作業(yè)是用戶提交給系統(tǒng)的一項(xiàng)相對(duì)獨(dú)立的工作。操作員把用戶提交的作業(yè)通過(guò)相應(yīng)的輸入設(shè)備輸入到磁盤(pán)存儲(chǔ)器，并保存在一個(gè)后備作業(yè)隊(duì)列中。再由作業(yè)調(diào)度程序?qū)⑵鋸耐獯嬲{(diào)入內(nèi)存。3.2.1批處理系統(tǒng)中的作業(yè)

1.作業(yè)和作業(yè)步

(1)作業(yè)(Job)。

包含程序、數(shù)據(jù)、作業(yè)說(shuō)明書(shū)

(2)作業(yè)步(JobStep)。

作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過(guò)若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果。每一個(gè)加工步驟稱(chēng)為一個(gè)作業(yè)步。

2.作業(yè)控制塊(JobControlBlock，JCB)

為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中，為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊JCB，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。通常在JCB中包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱(chēng)、用戶賬號(hào)、作業(yè)類(lèi)型(CPU繁忙型、I/O繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級(jí)、作業(yè)運(yùn)行時(shí)間)、資源需求(預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小等)、資源使用情況等。

3.作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)

作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，通常需要經(jīng)歷收容、運(yùn)行和完成三個(gè)階段。相應(yīng)的作業(yè)也就有“后備狀態(tài)”、“運(yùn)行狀態(tài)”和“完成狀態(tài)”。

(1)收容階段。

(2)運(yùn)行階段。

一個(gè)作業(yè)從第一次進(jìn)入就緒狀態(tài)開(kāi)始，直到它運(yùn)行結(jié)束前，在此期間都處于運(yùn)行狀態(tài)。

(3)完成階段。3.2.2作業(yè)調(diào)度的主要任務(wù)

作業(yè)調(diào)度的主要任務(wù)是，根據(jù)JCB中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對(duì)資源的需求，以及按照一定的調(diào)度算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上等待調(diào)度。因此，也把作業(yè)調(diào)度稱(chēng)為接納調(diào)度(AdmissionScheduling)。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都需做出以下兩個(gè)決定。

1.接納多少個(gè)作業(yè)

2.接納哪些作業(yè)應(yīng)選擇后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。最簡(jiǎn)單的是先來(lái)先服務(wù)算法：將最早進(jìn)入外存的作業(yè)優(yōu)先調(diào)入內(nèi)存；較常用的一種是短作業(yè)優(yōu)先調(diào)度算法：將外存上所需執(zhí)行時(shí)間最短的作業(yè)優(yōu)先調(diào)入內(nèi)存；另一種較常用的是基于作業(yè)優(yōu)先級(jí)的調(diào)度算法：將外存上作業(yè)優(yōu)先級(jí)最高的作業(yè)優(yōu)先調(diào)入內(nèi)存；比較好的一種算法是“響應(yīng)比高優(yōu)先”的調(diào)度算法。3.2.3先來(lái)先服務(wù)(FCFS)和短作業(yè)優(yōu)先(SJF)調(diào)度算法

1.先來(lái)先服務(wù)(first-comefirst-served，F(xiàn)CFS)調(diào)度算法

FCFS是最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，系統(tǒng)將按照作業(yè)到達(dá)的先后次序來(lái)進(jìn)行調(diào)度，或者說(shuō)它是優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)，而不管該作業(yè)所需執(zhí)行時(shí)間的長(zhǎng)短，從后備作業(yè)隊(duì)列中選擇幾個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源和創(chuàng)建進(jìn)程。然后把它放入就緒隊(duì)列。從表上可以看出，其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間竟高達(dá)100，這是不能容忍的；而長(zhǎng)作業(yè)D的帶權(quán)周轉(zhuǎn)時(shí)間僅為1.99。據(jù)此可知，F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）。CPU繁忙型作業(yè)：該類(lèi)作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算而很少請(qǐng)求I/O。如通常的科學(xué)計(jì)算。I/O繁忙型作業(yè)：指CPU進(jìn)行處理時(shí)，需頻繁的請(qǐng)求I/O。目前大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)。FCFS算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。

2.短作業(yè)優(yōu)先(shortjobfirst，SJF)的調(diào)度算法

由于在實(shí)際情況中，短作業(yè)(進(jìn)程)占有很大比例，為了能使它們能比長(zhǎng)作業(yè)優(yōu)先執(zhí)行，而產(chǎn)生了短作業(yè)優(yōu)先調(diào)度算法。

1)短作業(yè)優(yōu)先算法

SJF算法是以作業(yè)的長(zhǎng)短來(lái)計(jì)算優(yōu)先級(jí)，作業(yè)越短，其優(yōu)先級(jí)越高。作業(yè)的長(zhǎng)短是以作業(yè)所要求的運(yùn)行時(shí)間來(lái)衡量的。SJF算法可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算法用于作業(yè)調(diào)度時(shí)，它將從外存的作業(yè)后備隊(duì)列中選擇若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，優(yōu)先將它們調(diào)入內(nèi)存運(yùn)行。2)短作業(yè)優(yōu)先算法的缺點(diǎn)

SJF調(diào)度算法較之FCFS算法有了明顯的改進(jìn)，但仍然存在不容忽視的缺點(diǎn)：

(1)必須預(yù)知作業(yè)的運(yùn)行時(shí)間。在采用這種算法時(shí)，要先知道每個(gè)作業(yè)的運(yùn)行時(shí)間。即使是程序員也很難準(zhǔn)確估計(jì)作業(yè)的運(yùn)行時(shí)間，如果估計(jì)過(guò)低，系統(tǒng)就可能按估計(jì)的時(shí)間終止作業(yè)的運(yùn)行，但此時(shí)作業(yè)并未完成，故一般都會(huì)偏長(zhǎng)估計(jì)。

(2)對(duì)長(zhǎng)作業(yè)非常不利，長(zhǎng)作業(yè)的周轉(zhuǎn)時(shí)間會(huì)明顯地增長(zhǎng)。更嚴(yán)重的是，該算法完全忽視作業(yè)的等待時(shí)間，可能使作業(yè)等待時(shí)間過(guò)長(zhǎng)，出現(xiàn)饑餓現(xiàn)象。(3)在采用FCFS算法時(shí)，人—機(jī)無(wú)法實(shí)現(xiàn)交互。

(4)該調(diào)度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)能得到及時(shí)處理。通過(guò)上表可以看出，采用SJF算法后，不論是平均周轉(zhuǎn)時(shí)間還是平均帶權(quán)周轉(zhuǎn)時(shí)間，都有較明顯的改善，尤其是對(duì)短作業(yè)D，其周轉(zhuǎn)時(shí)間由原來(lái)的11降為3；帶權(quán)周轉(zhuǎn)時(shí)間從5.5降到了1.5。而平均帶權(quán)周轉(zhuǎn)時(shí)間從2.8降到了2.1。這說(shuō)明SJF調(diào)度算法能有效的降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量。3.2.4優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法

1.優(yōu)先級(jí)調(diào)度算法(priority-schedulingalgorithm，PSA)

我們可以這樣來(lái)看作業(yè)的優(yōu)先級(jí)，對(duì)于先來(lái)先服務(wù)調(diào)度算法，作業(yè)的等待時(shí)間就是作業(yè)的優(yōu)先級(jí)，等待時(shí)間越長(zhǎng)，其優(yōu)先級(jí)越高。對(duì)于短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的長(zhǎng)短就是作業(yè)的優(yōu)先級(jí)，作業(yè)所需運(yùn)行的時(shí)間越短，其優(yōu)先級(jí)越高。但上述兩種優(yōu)先級(jí)都不能反映作業(yè)的緊迫程度。

2.高響應(yīng)比優(yōu)先調(diào)度算法(HighestResponseRatioNext，HRRN)

在批處理系統(tǒng)中，F(xiàn)CFS算法所考慮的只是作業(yè)的等待時(shí)間，而忽視了作業(yè)的運(yùn)行時(shí)間。而SJF算法正好與之相反，只考慮作業(yè)的運(yùn)行時(shí)間，而忽視了作業(yè)的等待時(shí)間。高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時(shí)間，又考慮作業(yè)運(yùn)行時(shí)間的調(diào)度算法，因此既照顧了短作業(yè)，又不致使長(zhǎng)作業(yè)的等待時(shí)間過(guò)長(zhǎng)，從而改善了處理機(jī)調(diào)度的性能。高響應(yīng)比優(yōu)先算法是如何實(shí)現(xiàn)的呢?如果我們能為每個(gè)作業(yè)引入一個(gè)動(dòng)態(tài)優(yōu)先級(jí)，即優(yōu)先級(jí)是可以改變的，令它隨等待時(shí)間延長(zhǎng)而增加，這將使長(zhǎng)作業(yè)的優(yōu)先級(jí)在等待期間不斷地增加，等到足夠的時(shí)間后，必然有機(jī)會(huì)獲得處理機(jī)。該優(yōu)先級(jí)的變化規(guī)律可描述為：由于等待時(shí)間與服務(wù)時(shí)間之和就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先級(jí)又相當(dāng)于響應(yīng)比RP。據(jù)此，優(yōu)先又可表示為：1、如果等待時(shí)間相同，要求服務(wù)時(shí)間越短，優(yōu)先級(jí)越高，類(lèi)似于SJF算法。2、要求服務(wù)時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)又決定于其等待時(shí)間，類(lèi)似于FCFS算法3、對(duì)于長(zhǎng)作業(yè)的優(yōu)先級(jí)，可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，也可獲得處理機(jī)。

缺點(diǎn)：在利用該算法時(shí)，每次要進(jìn)行調(diào)度之前，都需要先做響應(yīng)比的計(jì)算，顯然會(huì)增加系統(tǒng)開(kāi)銷(xiāo)。?3.3進(jìn)程調(diào)度

進(jìn)程調(diào)度是OS中必不可少的一種調(diào)度。因此在三種類(lèi)型的OS中，都無(wú)一例外地配置了進(jìn)程調(diào)度。此外它也是對(duì)系統(tǒng)性能影響最大的一種處理機(jī)調(diào)度，相應(yīng)的，有關(guān)進(jìn)程調(diào)度的算法也較多。3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式

1.進(jìn)程調(diào)度的任務(wù)

進(jìn)程調(diào)度的任務(wù)主要有三：

(1)保存處理機(jī)的現(xiàn)場(chǎng)信息。

(2)按某種算法選取進(jìn)程。

(3)把處理器分配給進(jìn)程。

2.進(jìn)程調(diào)度機(jī)制

為了實(shí)現(xiàn)進(jìn)程調(diào)度，在進(jìn)程調(diào)度機(jī)制中，應(yīng)具有如下三個(gè)基本部分，如圖3-1所示。

(1)排隊(duì)器。為了提高進(jìn)程調(diào)度的效率，事先將系統(tǒng)中的所有就緒進(jìn)程按照一定的策略排成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程序能最快找到它。

(2)分派器。分派器根據(jù)進(jìn)程調(diào)度程序所選定的進(jìn)程，將其從就緒隊(duì)列中取出，然后進(jìn)行從分派器到新選出進(jìn)程間的上下文切換，將處理機(jī)分配給新選出的進(jìn)程

(3)上下文切換器。

圖3-1進(jìn)程調(diào)度機(jī)制

3.進(jìn)程調(diào)度方式

1)非搶占方式(NonpreemptiveMode)

在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，就一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷或任何其它原因去搶占當(dāng)前正在運(yùn)行進(jìn)程的處理機(jī)，直至該進(jìn)程完成，或發(fā)生某事件而被阻塞時(shí)，才把處理機(jī)分配給其它進(jìn)程。2)搶占方式(PreemptiveMode)

這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。在現(xiàn)代OS中廣泛采用搶占方式，這是因?yàn)椋簩?duì)于批處理機(jī)系統(tǒng)，可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間地占用處理機(jī)，以確保處理機(jī)能為所有進(jìn)程提供更為公平的服務(wù)。在分時(shí)系統(tǒng)中，只有采用搶占方式才有可能實(shí)現(xiàn)人—機(jī)交互。在實(shí)時(shí)系統(tǒng)中，搶占方式能滿足實(shí)時(shí)任務(wù)的需求。但搶占方式比較復(fù)雜，所需付出的系統(tǒng)開(kāi)銷(xiāo)也較大。搶占不是一種任意性的行為，必須遵循一定的原則：

1、優(yōu)先權(quán)原則：允許優(yōu)先級(jí)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)

2、短進(jìn)程優(yōu)先原則：允許新到的短進(jìn)程可以搶占當(dāng)前長(zhǎng)進(jìn)程的處理機(jī)

3、時(shí)間片原則：各進(jìn)程按時(shí)間片輪轉(zhuǎn)運(yùn)行時(shí)，當(dāng)正在執(zhí)行的進(jìn)程的一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新調(diào)度3.3.2輪轉(zhuǎn)調(diào)度算法

1.輪轉(zhuǎn)法的基本原理

在輪轉(zhuǎn)(RR)法中，系統(tǒng)將所有的就緒進(jìn)程按FCFS策略排成一個(gè)就緒隊(duì)列。系統(tǒng)可設(shè)置每隔一定時(shí)間(如30?ms)便產(chǎn)生一次中斷，去激活進(jìn)程調(diào)度程序進(jìn)行調(diào)度，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)它運(yùn)行完畢后，又把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，也讓它執(zhí)行一個(gè)時(shí)間片。這樣，就可以保證就緒隊(duì)列中的所有進(jìn)程在確定的時(shí)間段內(nèi)，都能獲得一個(gè)時(shí)間片的處理機(jī)時(shí)間。

2.進(jìn)程切換時(shí)機(jī)

在RR調(diào)度算法中，應(yīng)在何時(shí)進(jìn)行進(jìn)程的切換，可分為兩種情況：①若一個(gè)時(shí)間片尚未用完，正在運(yùn)行的進(jìn)程便已經(jīng)完成，就立即激活調(diào)度程序，將它從就緒隊(duì)列中刪除，再調(diào)度就緒隊(duì)列中隊(duì)首的進(jìn)程運(yùn)行，并啟動(dòng)一個(gè)新的時(shí)間片。②在一個(gè)時(shí)間片用完時(shí)，計(jì)時(shí)器中斷處理程序被激活。如果進(jìn)程尚未運(yùn)行完畢，調(diào)度程序?qū)阉屯途w隊(duì)列的末尾。

3.時(shí)間片大小的確定

在輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的

影響。

圖3-2示出了時(shí)間片大小對(duì)響應(yīng)時(shí)間的影響，其中圖(a)是時(shí)間片略大于典型交互的時(shí)間，而圖(b)是時(shí)間片小于典型交互的時(shí)間。圖3-3示出了時(shí)間片分別為q?=?1和q?=?4時(shí)對(duì)平均周轉(zhuǎn)時(shí)間的影響。圖3-2時(shí)間片大小對(duì)響應(yīng)時(shí)間的影響圖3-3q?=?1和q?=?4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間3.3.3優(yōu)先級(jí)調(diào)度算法

1.優(yōu)先級(jí)調(diào)度算法的類(lèi)型

優(yōu)先級(jí)進(jìn)程調(diào)度算法，是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程。這時(shí)，又可進(jìn)一步把該算法分成如下兩種。

(1)非搶占式優(yōu)先級(jí)調(diào)度算法。

(2)搶占式優(yōu)先級(jí)調(diào)度算法。

2.優(yōu)先級(jí)的類(lèi)型

1)靜態(tài)優(yōu)先級(jí)

靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。優(yōu)先級(jí)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如0～255中的某一整數(shù)，又把該整數(shù)稱(chēng)為優(yōu)先數(shù)。確定進(jìn)程優(yōu)先級(jí)大小的依據(jù)有如下三個(gè)：

(1)進(jìn)程類(lèi)型：系統(tǒng)進(jìn)程高于用戶進(jìn)程

(2)進(jìn)程對(duì)資源的需求：對(duì)資源要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先級(jí)

(3)用戶要求：根據(jù)進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少確定優(yōu)先級(jí)2)動(dòng)態(tài)優(yōu)先級(jí)

動(dòng)態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程之初，先賦予其一個(gè)優(yōu)先級(jí)，然后其值隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變，以便獲得更好的調(diào)度性能。3.3.4多隊(duì)列調(diào)度算法

如前所述的各種調(diào)度算法，尤其在應(yīng)用于進(jìn)程調(diào)度時(shí)，由于系統(tǒng)中僅設(shè)置一個(gè)進(jìn)程的就緒隊(duì)列，即低級(jí)調(diào)度算法是固定的、單一的，無(wú)法滿足系統(tǒng)中不同用戶對(duì)進(jìn)程調(diào)度策略的不同要求，在多處理機(jī)系統(tǒng)中，這種單一調(diào)度策略實(shí)現(xiàn)機(jī)制的缺點(diǎn)更顯突出，由此，多級(jí)隊(duì)列調(diào)度算法能夠在一定程度上彌補(bǔ)這一缺點(diǎn)。3.3.5多級(jí)反饋隊(duì)列(multilevedfeedbackqueue)調(diào)度算法

1.調(diào)度機(jī)制

多級(jí)反饋隊(duì)列調(diào)度算法的調(diào)度機(jī)制可描述如下：

(1)設(shè)置多個(gè)就緒隊(duì)列。

圖3-4是多級(jí)反饋隊(duì)列算法的示意圖。圖3-4多級(jí)反饋隊(duì)列調(diào)度算法(2)每個(gè)隊(duì)列都采用FCFS算法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可撤離系統(tǒng)。否則，即它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序?qū)⑵滢D(zhuǎn)入第二隊(duì)列的末尾等待調(diào)度；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，依此類(lèi)推。當(dāng)進(jìn)程最后被降到第n隊(duì)列后，在第n隊(duì)列中便采取按RR方式運(yùn)行。(3)按隊(duì)列優(yōu)先級(jí)調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級(jí)隊(duì)列中的諸進(jìn)程運(yùn)行，僅當(dāng)?shù)谝魂?duì)列空閑時(shí)才調(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)先級(jí)較高的隊(duì)列，此時(shí)須立即把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，而把處理機(jī)分配給新到的高優(yōu)先級(jí)進(jìn)程。

2.調(diào)度算法的性能

在多級(jí)反饋隊(duì)列調(diào)度算法中，如果規(guī)定第一個(gè)隊(duì)列的時(shí)間片略大于多數(shù)人機(jī)交互所需之處理時(shí)間時(shí)，便能較好地滿足各種類(lèi)型用戶的需要。

(1)終端型用戶。

(2)短批處理作業(yè)用戶。

(3)長(zhǎng)批處理作業(yè)用戶。3.3.6基于公平原則的調(diào)度算法

1.保證調(diào)度算法

保證調(diào)度算法是另外一種類(lèi)型的調(diào)度算法，它向用戶所做出的保證并不是優(yōu)先運(yùn)行，而是明確的性能保證，該算法可以做到調(diào)度的公平性。一種比較容易實(shí)現(xiàn)的性能保證是處理機(jī)分配的公平性。如果在系統(tǒng)中有n個(gè)相同類(lèi)型的進(jìn)程同時(shí)運(yùn)行，為公平起見(jiàn)，須保證每個(gè)進(jìn)程都獲得相同的處理機(jī)時(shí)間1/n。在實(shí)施公平調(diào)度算法時(shí)系統(tǒng)中必須具有這樣一些功能：

(1)跟蹤計(jì)算每個(gè)進(jìn)程自創(chuàng)建以來(lái)已經(jīng)執(zhí)行的處理時(shí)間。

(2)計(jì)算每個(gè)進(jìn)程應(yīng)獲得的處理機(jī)時(shí)間，即自創(chuàng)建以來(lái)的時(shí)間除以n。

(3)計(jì)算進(jìn)程獲得處理機(jī)時(shí)間的比率，即進(jìn)程實(shí)際執(zhí)行的處理時(shí)間和應(yīng)獲得的處理機(jī)時(shí)間之比。

(4)比較各進(jìn)程獲得處理機(jī)時(shí)間的比率。如進(jìn)程A的比率最低，為0.5，而進(jìn)程B的比率為0.8，進(jìn)程C的比率為1.2等。

(5)調(diào)度程序應(yīng)選擇比率最小的進(jìn)程將處理機(jī)分配給它，并讓該進(jìn)程一直運(yùn)行，直到超過(guò)最接近它的進(jìn)程比率為止。

2.公平分享調(diào)度算法

分配給每個(gè)進(jìn)程相同的處理機(jī)時(shí)間，顯然，這對(duì)諸進(jìn)程而言，是體現(xiàn)了一定程度的公平，但如果各個(gè)用戶所擁有的進(jìn)程數(shù)不同，就會(huì)發(fā)生對(duì)用戶的不公平問(wèn)題。

3.4實(shí)時(shí)調(diào)度

課程導(dǎo)入：

實(shí)時(shí)系統(tǒng)：并非指一類(lèi)快速計(jì)算的系統(tǒng)，而是指能及時(shí)響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)限內(nèi)，即截止期內(nèi)，完成對(duì)該事件地處理并控制相關(guān)設(shè)備和任務(wù)協(xié)調(diào)一致運(yùn)行的計(jì)算機(jī)系統(tǒng)。

硬實(shí)時(shí)（HardReal-Time，HRT）：事件的截止期錯(cuò)過(guò)會(huì)對(duì)外部環(huán)境造成嚴(yán)重后果，甚至系統(tǒng)崩潰，例如：飛行器控制系統(tǒng)、復(fù)雜核電控制系統(tǒng)等。

軟實(shí)時(shí)（SoftReal-Time，SRT）：個(gè)別任務(wù)可以不滿足截止期的時(shí)間要求，但會(huì)在一定程度上造成系統(tǒng)性能的下降。

在實(shí)時(shí)系統(tǒng)中，可能存在著兩類(lèi)不同性質(zhì)的實(shí)時(shí)任務(wù)，即HRT任務(wù)和SRT任務(wù)，它們都聯(lián)系著一個(gè)截止時(shí)間。為保證系統(tǒng)能正常工作，實(shí)時(shí)調(diào)度必須能滿足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。為此，實(shí)現(xiàn)實(shí)時(shí)調(diào)度應(yīng)具備一定的條件。3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件

1.提供必要的信息

為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的信息：

(1)就緒時(shí)間，是指某任務(wù)成為就緒狀態(tài)的起始時(shí)間，在周期任務(wù)的情況下，它是事先預(yù)知的一串時(shí)間序列。

(2)開(kāi)始截止時(shí)間和完成截止時(shí)間，對(duì)于典型的實(shí)時(shí)應(yīng)用，只須知道開(kāi)始截止時(shí)間，或者完成截止時(shí)間。(3)處理時(shí)間，一個(gè)任務(wù)從開(kāi)始執(zhí)行，直至完成時(shí)所需的時(shí)間。

(4)資源要求，任務(wù)執(zhí)行時(shí)所需的一組資源。

(5)優(yōu)先級(jí)，如果某任務(wù)的開(kāi)始截止時(shí)間錯(cuò)過(guò)，勢(shì)必引起故障，則應(yīng)為該任務(wù)賦予“絕對(duì)”優(yōu)先級(jí)；如果其開(kāi)始截止時(shí)間的錯(cuò)過(guò)，對(duì)任務(wù)的繼續(xù)運(yùn)行無(wú)重大影響，則可為其賦予“相對(duì)”優(yōu)先級(jí)，供調(diào)度程序參考。

2.系統(tǒng)處理能力強(qiáng)

在實(shí)時(shí)系統(tǒng)中，若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過(guò)，而致使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)HRT，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件系統(tǒng)才是可調(diào)度的：提高系統(tǒng)處理能力的途徑有二：一是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：

3.采用搶占式調(diào)度機(jī)制

在含有HRT任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。這樣便可滿足HRT任務(wù)對(duì)截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。

4.具有快速切換機(jī)制

為保證硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在系統(tǒng)中還應(yīng)具有快速切換機(jī)制，使之能進(jìn)行任務(wù)的快速切換。該機(jī)制應(yīng)具有如下兩方面的能力：

(1)對(duì)中斷的快速響應(yīng)能力。對(duì)緊迫的外部事件請(qǐng)求中斷能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。

(2)快速的任務(wù)分派能力。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開(kāi)銷(xiāo)。3.4.2實(shí)時(shí)調(diào)度算法的分類(lèi)

可以按不同方式對(duì)實(shí)時(shí)調(diào)度算法加以分類(lèi)：①根據(jù)實(shí)時(shí)任務(wù)性質(zhì)，可將實(shí)時(shí)調(diào)度的算法分為硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)調(diào)度算法；②按調(diào)度方式，則可分為非搶占調(diào)度算法和搶占調(diào)度算法。

3.5死鎖概述

3.5.1資源問(wèn)題

在系統(tǒng)中有許多不同類(lèi)型的資源，其中可以引起死鎖的主要是，需要采用互斥訪問(wèn)方法的、不可以被搶占的資源，即在前面介紹的臨界資源。系統(tǒng)中這類(lèi)資源有很多，如打印機(jī)、數(shù)據(jù)文件、隊(duì)列、信號(hào)量等。

1.可重用性資源和消耗性資源

1)可重用性資源

可重用性資源是一種可供用戶重復(fù)使用多次的資源，它具有如下性質(zhì)：

(1)每一個(gè)可重用性資源中的單元只能分配給一個(gè)進(jìn)程使用，不允許多個(gè)進(jìn)程共享。

(2)進(jìn)程在使用可重用性資源時(shí)，須按照這樣的順序：①請(qǐng)求資源。如果請(qǐng)求資源失敗，請(qǐng)求進(jìn)程將會(huì)被阻塞或循環(huán)等待。②使用資源。進(jìn)程對(duì)資源進(jìn)行操作，如用打印機(jī)進(jìn)行打?。虎坩尫刨Y源。當(dāng)進(jìn)程使用完后自己釋放資源。

(3)系統(tǒng)中每一類(lèi)可重用性資源中的單元數(shù)目是相對(duì)固定的，進(jìn)程在運(yùn)行期間既不能創(chuàng)建也不能刪除它。2)可消耗性資源

可消耗性資源又稱(chēng)為臨時(shí)性資源，它是在進(jìn)程運(yùn)行期間，由進(jìn)程動(dòng)態(tài)地創(chuàng)建和消耗的，它具有如下性質(zhì)：①每一類(lèi)可消耗性資源的單元數(shù)目在進(jìn)程運(yùn)行期間是可以不斷變化的，有時(shí)它可以有許多，有時(shí)可能為0；②進(jìn)程在運(yùn)行過(guò)程中，可以不斷地創(chuàng)造可消耗性資源的單元，將它們放入該資源類(lèi)的緩沖區(qū)中，以增加該資源類(lèi)的單元數(shù)目。③進(jìn)程在運(yùn)行過(guò)程中，可以請(qǐng)求若干個(gè)可消耗性資源單元，用于進(jìn)程自己的消耗，不再將它們返回給該資源類(lèi)中。

2.可搶占性資源和不可搶占性資源

1)可搶占性資源

可把系統(tǒng)中的資源分成兩類(lèi)，一類(lèi)是可搶占性資源，是指某進(jìn)程在獲得這類(lèi)資源后，該資源可以再被其它進(jìn)程或系統(tǒng)搶占。

2)不可搶占性資源

另一類(lèi)資源是不可搶占性資源，即一旦系統(tǒng)把某資源分配給該進(jìn)程后，就不能將它強(qiáng)行收回，只能在進(jìn)程用完后自行釋放。3.5.2計(jì)算機(jī)系統(tǒng)中的死鎖

1.競(jìng)爭(zhēng)不可搶占性資源引起死鎖

通常系統(tǒng)中所擁有的不可搶占性資源其數(shù)量不足以滿足多個(gè)進(jìn)程運(yùn)行的需要，使得進(jìn)程在運(yùn)行過(guò)程中，會(huì)因爭(zhēng)奪資源而陷入僵局。我們可將上面的問(wèn)題利用資源分配圖進(jìn)行描述，用方塊代表可重用的資源(文件)，用圓圈代表進(jìn)程，見(jiàn)圖3-12所示。圖3-12共享文件時(shí)的死鎖情況

2.競(jìng)爭(zhēng)可消耗資源引起死鎖

現(xiàn)在進(jìn)一步介紹競(jìng)爭(zhēng)可消耗資源所引起的死鎖。圖3-13示出了在三個(gè)進(jìn)程之間，在利用消息通信機(jī)制進(jìn)行通信時(shí)所形成的死鎖情況。圖3-13進(jìn)程之間通信時(shí)的死鎖

3.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

除了系統(tǒng)中多個(gè)進(jìn)程對(duì)資源的競(jìng)爭(zhēng)會(huì)引發(fā)死鎖外，進(jìn)程在運(yùn)行過(guò)程中，對(duì)資源進(jìn)行申請(qǐng)和釋放的順序是否合法，也是在系統(tǒng)中是否會(huì)產(chǎn)生死鎖的一個(gè)重要因素。1)進(jìn)程推進(jìn)順序合法

在進(jìn)程P1和P2并發(fā)執(zhí)行時(shí)，如果按圖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)，兩個(gè)進(jìn)程可順利完成。類(lèi)似地，若按圖中曲線②和③所示的順序推進(jìn)，兩進(jìn)程也可以順利完成。我們稱(chēng)這種不會(huì)引起進(jìn)程死鎖的推進(jìn)順序是合法的。2)進(jìn)程推進(jìn)順序非法

若并發(fā)進(jìn)程P1和P2按圖3-14中曲線④所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時(shí)P1保持了資源R1，P2保持了資源R2，系統(tǒng)處于不安全狀態(tài)。此刻，如果兩個(gè)進(jìn)程繼續(xù)向前推進(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)程死鎖，這樣的進(jìn)程推進(jìn)順序就是非法的。圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響3.5.3死鎖的定義、必要條件和處理方法

1.死鎖的定義

死鎖（DeadLock）：是指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法向前推進(jìn)。

在一組進(jìn)程發(fā)生死鎖的情況下，這組死鎖進(jìn)程中的每一個(gè)進(jìn)程，都在等待另一個(gè)死鎖進(jìn)程所占有的資源。

2.產(chǎn)生死鎖的必要條件

雖然進(jìn)程在運(yùn)行過(guò)程中可能會(huì)發(fā)生死鎖，但產(chǎn)生進(jìn)程死鎖是必須具備一定條件的。綜上所述不難看出，產(chǎn)生死鎖必須同時(shí)具備下面四個(gè)必要條件，只要其中任一個(gè)條件不成立，死鎖就不會(huì)發(fā)生：

(1)互斥條件。

(2)請(qǐng)求和保持條件。

(3)不可搶占條件。

(4)循環(huán)等待條件。

3.處理死鎖的方法

目前處理死鎖的方法可歸結(jié)為四種：

(1)預(yù)防死鎖。

(2)避免死鎖。

(3)檢測(cè)死鎖。

(4)解除死鎖。?3.6預(yù)防死鎖

預(yù)防死鎖的方法是通過(guò)破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，以避免發(fā)生死鎖。由于互斥條件是非共享設(shè)備所必須的，不僅不能改變，還應(yīng)加以保證，因此主要是破壞產(chǎn)生死鎖的后三個(gè)條件。3.6.1破壞“請(qǐng)求和保持”條件

為了能破壞“請(qǐng)求和保持”條件，系統(tǒng)必須保證做到：當(dāng)一個(gè)進(jìn)程在請(qǐng)求資源時(shí)，它不能持有不可搶占資源。該保證可通過(guò)如下兩個(gè)不同的協(xié)議實(shí)現(xiàn)：

1.第一種協(xié)議

該協(xié)議規(guī)定，所有進(jìn)程在開(kāi)始運(yùn)行之前，必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過(guò)程中所需的全部資源。

缺點(diǎn)：資源被嚴(yán)重浪費(fèi)；使進(jìn)程經(jīng)常會(huì)發(fā)生饑餓現(xiàn)象。

2.第二種協(xié)議

該協(xié)議是對(duì)第一種協(xié)議的改進(jìn)，它允許一個(gè)進(jìn)程只獲得運(yùn)行初期所需的資源后，便開(kāi)始運(yùn)行。3.6.2破壞“不可搶占”條件

為了能破壞“不可搶占”條件，協(xié)議中規(guī)定，當(dāng)一個(gè)已經(jīng)保持了某些不可被搶占資源的進(jìn)程，提出新的資源請(qǐng)求而不能得到滿足時(shí)，它必須釋放已經(jīng)保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。這意味著進(jìn)程已占有的資源會(huì)被暫時(shí)地釋放，或者說(shuō)是被搶占了，從而破壞了“不可搶占”條件。3.6.3破壞“循環(huán)等待”條件

一個(gè)能保證“循環(huán)等待”條件不成立的方法是，對(duì)系統(tǒng)所有資源類(lèi)型進(jìn)行線性排序，并賦予不同的序號(hào)。?3.7避免死鎖

避免死鎖同樣是屬于事先預(yù)防的策略，但并不是事先采取某種限制措施，破壞產(chǎn)生死鎖的必要條件，而是在資源動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)，以避免發(fā)生死鎖。這種方法所施加的限制條件較弱，可能獲得較好的系統(tǒng)性能，目前常用此方法來(lái)避免發(fā)生死鎖。3.7.1系統(tǒng)安全狀態(tài)

在死鎖避免方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)，可避免發(fā)生死鎖。反之，當(dāng)系統(tǒng)處于不安全狀態(tài)時(shí)，則可能進(jìn)入到死鎖狀態(tài)。

1.安全狀態(tài)

在該方法中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次資源分配的安全性。

2.安全狀態(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)空閑未分配，如下表所示：

3.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換

如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。3.7.2利用銀行家算法避免死鎖

最有代表性的避免死鎖的算法是Dijkstra的銀行家算法。起這樣的名字是由于該算法原本是為銀行系統(tǒng)設(shè)計(jì)的，以確保銀行在發(fā)放現(xiàn)金貸款時(shí)，不會(huì)發(fā)生不能滿足所有客戶需要的情況。在OS中也可用它來(lái)實(shí)現(xiàn)避免死鎖。

1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

為了實(shí)現(xiàn)銀行家算法，在系統(tǒng)中必須設(shè)置這樣四個(gè)數(shù)據(jù)結(jié)構(gòu)，分別用來(lái)描述系統(tǒng)中可利用的資源、所有進(jìn)程對(duì)資源的最大需求、系統(tǒng)中的資源分配，以及所有進(jìn)程還需要多少資源的情況。

(1)可利用資源向量Available。

(2)最大需求矩陣Max。

(3)分配矩陣Allocation。

(4)需求矩陣Need。

2.銀行家算法

設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Request?i[j]=K，表示進(jìn)程Pi需要K個(gè)Rj類(lèi)型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1)如果Request?i[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。

(2)如果Request?i[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無(wú)足夠資源，Pi須等待。(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[j]=Available[j]?-?Request?i[j];

Allocation[i,j]=Allocation[i,j]?+?Request?i[j];

Need[i,j]=Need[i,j]?-?Request?i[j];

(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。

3.安全性算法

系統(tǒng)所執(zhí)行的安全性算法可描述如下：

(1)設(shè)置兩個(gè)向量：①工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類(lèi)資源數(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]:=true。(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：

①Finish[i]=false;

②Need[i,j]≤Work[j];

若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。

(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work[j]=Work[j]+Allocation[i,j];

Finish[i]=true;

gotostep2;

(4)如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

4.銀行家算法之例

假定系統(tǒng)中有五個(gè)進(jìn)程{P0,P1,P2,P3,P4}和三類(lèi)資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖3-15所示。圖3-15T0時(shí)刻的資源分配表(1)?T0時(shí)刻的安全性：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析(如圖3-16所示)可知，在T0時(shí)刻存在著一個(gè)安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。圖3-16T0時(shí)刻的安全序列(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)≤Available1(3,3,2)；

③系統(tǒng)先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號(hào)所示；

④再利用安全性算法檢查此時(shí)系統(tǒng)是否安全，如圖3-17所示。圖3-17P1申請(qǐng)資源時(shí)的安全性檢查(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)求向量Request0(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ù)，如圖3-18所示。圖3-18為P0分配資源后的有關(guān)資源數(shù)據(jù)(5)進(jìn)行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。

3.8死鎖的檢測(cè)與解除

如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會(huì)發(fā)生死鎖。在這種情況下，系統(tǒng)應(yīng)當(dāng)提供兩個(gè)算法：

①死鎖檢測(cè)算法。該方法用于檢測(cè)系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。

②死鎖解除算法。當(dāng)認(rèn)定系統(tǒng)中已發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來(lái)。3.8.1死鎖的檢測(cè)

為了能對(duì)系統(tǒng)中是否已發(fā)生了死鎖進(jìn)行檢測(cè)，在系統(tǒng)中必須：①保存有關(guān)資源的請(qǐng)求和分配信息；②提供一種算法，它利用這些信息來(lái)檢測(cè)系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。

1.資源分配圖(ResourceAllocationGraph)

系統(tǒng)死鎖，可利用資源分配圖來(lái)描述。該圖是由一組結(jié)點(diǎn)N和一組邊E所組成的一個(gè)對(duì)偶G?=?(N,E)，它具有下述形式的定義和限制：

(1)把N分為兩個(gè)互斥的子集，即一組進(jìn)程結(jié)點(diǎn)P={P1,P2,…,Pn}和一組資源結(jié)點(diǎn)R={R1,R2,…,Rn}，N?=?P∪R。在圖3-19所示的例子中，P?=?{P1,P2}，R?=?{R1,R2}，N?=?{R1,R2}∪{P1,P2}。

(2)凡屬于E中的一個(gè)邊e∈E，都連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)，e?=?{Pi,Rj}是資源請(qǐng)求邊，由進(jìn)程Pi指向資源Rj，它表示進(jìn)程Pi請(qǐng)求一個(gè)單位的Rj資源。E?=?{Rj,Pi}是資源分配邊，由資源Rj指向進(jìn)程Pi，它表示把一個(gè)單位的資源Rj分配給進(jìn)程Pi。圖3-19中示出了兩個(gè)請(qǐng)求邊和兩個(gè)分配邊，即E?=?{(P1,R2),(R2,P2),(P2,R1),(R1,P1)}。圖3-19每類(lèi)資源有多個(gè)時(shí)的情況

2．死鎖定理

我們可以利用把資源分配圖加以簡(jiǎn)化的方法(圖3-19)，來(lái)檢測(cè)當(dāng)系統(tǒng)處于S狀態(tài)時(shí)，是否為死鎖狀態(tài)。簡(jiǎn)化方法如下：

(1)在資源分配圖中，找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)Pi。在順利的情況下，Pi可獲得所需資源而繼續(xù)運(yùn)行，直至運(yùn)行完畢，再釋放其所占有的全部資源，這相當(dāng)于消去Pi的請(qǐng)求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。在圖3-20(a)中，將P1的兩個(gè)分配邊和一個(gè)請(qǐng)求邊消去，便形成圖(b)所示的情況。圖3-20資源分配圖的簡(jiǎn)化(2)?P1釋放資源后，便可使P2獲得資源而繼續(xù)運(yùn)行，直至P2完成后又釋放出它所占有的全部資源，形成圖(c)所示的情況，即將P2的兩條請(qǐng)求邊和一條分配邊消去。

(3)在進(jìn)行一系列的簡(jiǎn)化后，若能消去圖中所有的邊，使所有的進(jìn)程結(jié)點(diǎn)都成為孤立結(jié)點(diǎn)，則稱(chēng)該圖是可完全簡(jiǎn)化