西安郵電大學(xué)操作系統(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í)時調(diào)度3.5死鎖概述3.6預(yù)防死鎖3.7避免死鎖3.8死鎖的檢測與解除習(xí)題

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

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

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

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

3.中級調(diào)度(IntermediateScheduling)作業(yè)調(diào)度（高級）作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。因此，有時也把作業(yè)調(diào)度稱為接納調(diào)度(AdmissionScheduling)。

低級調(diào)度通常也把低級調(diào)度(LowLevelScheduling)稱為進(jìn)程調(diào)度或短程調(diào)度(ShortTermScheduling)，它所調(diào)度的對象是進(jìn)程(或內(nèi)核級線程)。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實(shí)時三種類型的OS中，都必須配置這級調(diào)度。

1．低級調(diào)度的功能低級調(diào)度用于決定就緒隊(duì)列中的哪個進(jìn)程(或內(nèi)核級線程，為敘述方便，以后只寫進(jìn)程)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。低級調(diào)度的主要功能如下：

(1)保存處理機(jī)的現(xiàn)場信息。在進(jìn)程調(diào)度進(jìn)行調(diào)度時，首先需要保存當(dāng)前進(jìn)程的處理機(jī)的現(xiàn)場信息，如程序計(jì)數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進(jìn)程的進(jìn)程控制塊(PCB)中的相應(yīng)單元。

(2)按某種算法選取進(jìn)程。低級調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等，從就緒隊(duì)列中選取一個進(jìn)程，把它的狀態(tài)改為運(yùn)行狀態(tài)，并準(zhǔn)備把處理機(jī)分配給它。

(3)把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。此時需為選中的進(jìn)程恢復(fù)處理機(jī)現(xiàn)場，即把選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場的信息裝入處理器相應(yīng)的各個寄存器中，把處理器的控制權(quán)交給該進(jìn)程，讓它從取出的斷點(diǎn)處開始繼續(xù)運(yùn)行。

中級調(diào)度中級調(diào)度(IntermediateLevelScheduling)又稱中程調(diào)度(Medium-TermScheduling)。引入中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。中級調(diào)度實(shí)際上就是存儲器管理中的對換功能，

在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時系統(tǒng)中通常是10～100ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時間，進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(批)作業(yè)進(jìn)入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時間。中級調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。

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

調(diào)度隊(duì)列模型

1．僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

在分時系統(tǒng)中，通常僅設(shè)置了進(jìn)程調(diào)度，用戶鍵入的命令和數(shù)據(jù)都直接送入內(nèi)存。對于命令，是由OS為之建立一個進(jìn)程。系統(tǒng)可以把處于就緒狀態(tài)的進(jìn)程組織成棧、樹或一個無序鏈表，至于到底采用其中哪種形式，則與OS類型和所采用的調(diào)度算法有關(guān)。例如，在分時系統(tǒng)中，常把就緒進(jìn)程組織成FIFO隊(duì)列形式。每當(dāng)OS創(chuàng)建一個新進(jìn)程時，便將它掛在就緒隊(duì)列的末尾，然后按時間片輪轉(zhuǎn)方式運(yùn)行。

每個進(jìn)程在執(zhí)行時都可能出現(xiàn)以下三種情況：

(1)任務(wù)在給定的時間片內(nèi)已經(jīng)完成，該進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；

(2)任務(wù)在本次分得的時間片內(nèi)尚未完成，OS便將該任務(wù)再放入就緒隊(duì)列的末尾；

(3)在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，被OS放入阻塞隊(duì)列。

僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

2．具有高級和低級調(diào)度的調(diào)度隊(duì)列模型

在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還需有作業(yè)調(diào)度，由后者按一定的作業(yè)調(diào)度算法，從外存的后備隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進(jìn)程，送入就緒隊(duì)列，然后才由進(jìn)程調(diào)度按照一定的進(jìn)程調(diào)度算法選擇一個進(jìn)程，把處理機(jī)分配給該進(jìn)程。圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。

(1)就緒隊(duì)列的形式。在批處理系統(tǒng)中，最常用的是最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，相應(yīng)地，最常用的就緒隊(duì)列形式是優(yōu)先權(quán)隊(duì)列。進(jìn)程在進(jìn)入優(yōu)先級隊(duì)列時，根據(jù)其優(yōu)先權(quán)的高低，被插入具有相應(yīng)優(yōu)先權(quán)的位置上，這樣，調(diào)度程序總是把處理機(jī)分配給就緒隊(duì)列中的隊(duì)首進(jìn)程。在最高優(yōu)先權(quán)優(yōu)先的調(diào)度算法中，也可采用無序鏈表方式，即每次把新到的進(jìn)程掛在鏈尾，而調(diào)度程序每次調(diào)度時，是依次比較該鏈中各進(jìn)程的優(yōu)先權(quán)，從中找出優(yōu)先權(quán)最高的進(jìn)程，將之從鏈中摘下，并把處理機(jī)分配給它。顯然，無序鏈表方式與優(yōu)先權(quán)隊(duì)列相比，這種方式的調(diào)度效率較低。

具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型

(2)設(shè)置多個阻塞隊(duì)列。對于小型系統(tǒng)，可以只設(shè)置一個阻塞隊(duì)列；但當(dāng)系統(tǒng)較大時，若仍只有一個阻塞隊(duì)列，其長度必然會很長，隊(duì)列中的進(jìn)程數(shù)可以達(dá)到數(shù)百個，這將嚴(yán)重影響對阻塞隊(duì)列操作的效率。故在大、中型系統(tǒng)中通常都設(shè)置了若干個阻塞隊(duì)列，每個隊(duì)列對應(yīng)于某一種進(jìn)程阻塞事件。

3．同時具有三級調(diào)度的調(diào)度隊(duì)列模型當(dāng)在OS中引入中級調(diào)度后，人們可把進(jìn)程的就緒狀態(tài)分為內(nèi)存就緒(表示進(jìn)程在內(nèi)存中就緒)和外存就緒(進(jìn)程在外存中就緒)。類似地，也可把阻塞狀態(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。圖3-3示出了具有三級調(diào)度的調(diào)度隊(duì)列模型。

具有三級調(diào)度時的調(diào)度隊(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時間，不會發(fā)生進(jìn)程饑餓現(xiàn)象。公平性是相對的，對相同類型的進(jìn)程應(yīng)獲得相同的服務(wù)；但對于不同類型的進(jìn)程，由于其緊急程度或重要性的不同，則應(yīng)提供不同的服務(wù)。

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

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

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

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

所謂周轉(zhuǎn)時間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔(稱為作業(yè)周轉(zhuǎn)時間)。它包括四部分時間：作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時間，進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時間，進(jìn)程在CPU上執(zhí)行的時間，以及進(jìn)程等待I/O操作完成的時間。其中的后三項(xiàng)在一個作業(yè)的整個處理過程中可能會發(fā)生多次。

可把平均周轉(zhuǎn)時間描述為：

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

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

對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計(jì)算機(jī)系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時間最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意。應(yīng)使作業(yè)周轉(zhuǎn)時間和作業(yè)的平均周轉(zhuǎn)時間盡可能短。否則，會使許多用戶的等待時間過長，這將會引起用戶特別是短作業(yè)用戶的不滿。為了進(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)時間則可表示為：

(2)系統(tǒng)吞吐量高。由于吞吐量是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長度有關(guān)。事實(shí)上，如果單純是為了獲得高的系統(tǒng)吞吐量，就應(yīng)盡量多地選擇短作業(yè)運(yùn)行。

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

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

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

常把響應(yīng)時間的長短用來評價分時系統(tǒng)的性能，這是選擇分時系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一。所謂響應(yīng)時間，是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間，或者說，直到屏幕上顯示出結(jié)果為止的一段時間間隔。它包括三部分時間：從鍵盤輸入的請求信息傳送到處理機(jī)的時間，處理機(jī)對請求信息進(jìn)行處理的時間，以及將所形成的響應(yīng)信息回送到終端顯示器的時間。

(2)均衡性。

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

(1)截止時間的保證。

這是評價實(shí)時系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時調(diào)度算法的重要準(zhǔn)則。所謂截止時間，是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。對于嚴(yán)格的實(shí)時系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn)，否則將可能造成難以預(yù)料的后果。

(2)可預(yù)測性。

3.2作業(yè)與作業(yè)調(diào)度

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

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

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

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

(1)作業(yè)(Job)。作業(yè)是一個比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。

(2)作業(yè)步(JobStep)。通常，在作業(yè)運(yùn)行期間，每個作業(yè)都必須經(jīng)過若干個相對獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。例如，一個典型的作業(yè)可分成三個作業(yè)步：①“編譯”作業(yè)步，通過執(zhí)行編譯程序?qū)υ闯绦蜻M(jìn)行編譯，產(chǎn)生若干個目標(biāo)程序段；②“連結(jié)裝配”作業(yè)步，將“編譯”作業(yè)步所產(chǎn)生的若干個目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序；③“運(yùn)行”作業(yè)步，將可執(zhí)行的目標(biāo)程序讀入內(nèi)存并控制其運(yùn)行。

2.作業(yè)控制塊(JobControlBlock，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)容有：作業(yè)標(biāo)識、用戶名稱、用戶賬號、作業(yè)類型(CPU繁忙型、I/O繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)運(yùn)行時間)、資源需求(預(yù)計(jì)運(yùn)行時間、要求內(nèi)存大小等)、資源使用情況等。每當(dāng)作業(yè)進(jìn)入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立一個JCB，根據(jù)作業(yè)類型將它插入相應(yīng)的后備隊(duì)列中。作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，被調(diào)度到的作業(yè)將會裝入內(nèi)存。在作業(yè)運(yùn)行期間，系統(tǒng)就按照J(rèn)CB中的信息對作業(yè)進(jìn)行控制。當(dāng)一個作業(yè)執(zhí)行結(jié)束進(jìn)入完成狀態(tài)時，系統(tǒng)負(fù)責(zé)回收分配給它的資源，撤消它的作業(yè)控制塊。

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

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

(1)收容階段。

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

(3)完成階段。

3.2.2作業(yè)調(diào)度的主要任務(wù)

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

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

2.接納哪些作業(yè)

1)決定接納多少個作業(yè)作業(yè)調(diào)度每次要接納多少個作業(yè)進(jìn)入內(nèi)存，取決于多道程序度(DegreeofMultiprogramming)，即允許多少個作業(yè)同時在內(nèi)存中運(yùn)行。當(dāng)內(nèi)存中同時運(yùn)行的作業(yè)數(shù)目太多時，可能會影響到系統(tǒng)的服務(wù)質(zhì)量，比如，使周轉(zhuǎn)時間太長。但如果在內(nèi)存中同時運(yùn)行作業(yè)的數(shù)量太少時，又會導(dǎo)致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低，因此，多道程序度的確定應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度等情況做適當(dāng)?shù)恼壑浴?/p>

2)決定接納哪些作業(yè)

應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。最簡單的是先來先服務(wù)調(diào)度算法，這是指將最早進(jìn)入外存的作業(yè)最先調(diào)入內(nèi)存；較常用的一種算法是短作業(yè)優(yōu)先調(diào)度算法，是將外存上最短的作業(yè)最先調(diào)入內(nèi)存；另一種較常用的是基于作業(yè)優(yōu)先級的調(diào)度算法，該算法是將外存上優(yōu)先級最高的作業(yè)優(yōu)先調(diào)入內(nèi)存；比較好的一種算法是“響應(yīng)比高者優(yōu)先”的調(diào)度算法。我們將在后面對上述幾種算法作較為詳細(xì)的介紹。

在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，總是先駐留在外存的后備隊(duì)列上，因此需要有作業(yè)調(diào)度的過程，以便將它們分批地裝入內(nèi)存。然而在分時系統(tǒng)中，為了做到及時響應(yīng)，用戶通過鍵盤輸入的命令或數(shù)據(jù)等都是被直接送入內(nèi)存的，因而無需再配置上述的作業(yè)調(diào)度機(jī)制，但也需要有某些限制性措施來限制進(jìn)入系統(tǒng)的用戶數(shù)。即，如果系統(tǒng)尚未飽和，將接納所有授權(quán)用戶，否則，將拒絕接納。類似地，在實(shí)時系統(tǒng)中通常也不需要作業(yè)調(diào)度。

3.2.3先來先服務(wù)(FCFS)和短作業(yè)優(yōu)先(SJF)調(diào)度算法

1.先來先服務(wù)(first-comefirst-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á)的先后次序來進(jìn)行調(diào)度，或者說它是優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管該作業(yè)所需執(zhí)行時間的長短，從后備作業(yè)隊(duì)列中選擇幾個最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源和創(chuàng)建進(jìn)程。然后把它放入就緒隊(duì)列。

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

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

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

SJF算法是以作業(yè)的長短來計(jì)算優(yōu)先級，作業(yè)越短，其優(yōu)先級越高。作業(yè)的長短是以作業(yè)所要求的運(yùn)行時間來衡量的。SJF算法可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算法用于作業(yè)調(diào)度時，它將從外存的作業(yè)后備隊(duì)列中選擇若干個估計(jì)運(yùn)行時間最短的作業(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)行時間。在采用這種算法時，要先知道每個作業(yè)的運(yùn)行時間。即使是程序員也很難準(zhǔn)確估計(jì)作業(yè)的運(yùn)行時間，如果估計(jì)過低，系統(tǒng)就可能按估計(jì)的時間終止作業(yè)的運(yùn)行，但此時作業(yè)并未完成，故一般都會偏長估計(jì)。

(2)對長作業(yè)非常不利，長作業(yè)的周轉(zhuǎn)時間會明顯地增長。更嚴(yán)重的是，該算法完全忽視作業(yè)的等待時間，可能使作業(yè)等待時間過長，出現(xiàn)饑餓現(xiàn)象。

(3)在采用FCFS算法時，人—機(jī)無法實(shí)現(xiàn)交互。

(4)該調(diào)度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)能得到及時處理。3.2.4優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法

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

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

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

在批處理系統(tǒng)中，F(xiàn)CFS算法所考慮的只是作業(yè)的等待時間，而忽視了作業(yè)的運(yùn)行時間。而SJF算法正好與之相反，只考慮作業(yè)的運(yùn)行時間，而忽視了作業(yè)的等待時間。高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時間，又考慮作業(yè)運(yùn)行時間的調(diào)度算法，因此既照顧了短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善了處理機(jī)調(diào)度的性能。高響應(yīng)比優(yōu)先算法是如何實(shí)現(xiàn)的呢?如果我們能為每個作業(yè)引入一個動態(tài)優(yōu)先級，即優(yōu)先級是可以改變的，令它隨等待時間延長而增加，這將使長作業(yè)的優(yōu)先級在等待期間不斷地增加，等到足夠的時間后，必然有機(jī)會獲得處理機(jī)。該優(yōu)先級的變化規(guī)律可描述為：

由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先級又相當(dāng)于響應(yīng)比RP。據(jù)此，優(yōu)先又可表示為：

3.3進(jìn)

程

調(diào)

度

進(jìn)程調(diào)度是OS中必不可少的一種調(diào)度。因此在三種類型的OS中，都無一例外地配置了進(jìn)程調(diào)度。此外它也是對系統(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)場信息。

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

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

(1)保存處理機(jī)的現(xiàn)場信息。在進(jìn)程調(diào)度進(jìn)行調(diào)度時，首先需要保存當(dāng)前進(jìn)程的處理機(jī)的現(xiàn)場信息，如程序計(jì)數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進(jìn)程的進(jìn)程控制塊(PCB)中的相應(yīng)單元。

(2)按某種算法選取進(jìn)程。低級調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等，從就緒隊(duì)列中選取一個進(jìn)程，把它的狀態(tài)改為運(yùn)行狀態(tài)，并準(zhǔn)備把處理機(jī)分配給它。

(3)把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。此時需為選中的進(jìn)程恢復(fù)處理機(jī)現(xiàn)場，即把選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場的信息裝入處理器相應(yīng)的各個寄存器中，把處理器的控制權(quán)交給該進(jìn)程，讓它從取出的斷點(diǎn)處開始繼續(xù)運(yùn)行。

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

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

(1)排隊(duì)器。

(2)分派器。

(3)上下文切換器。

(1)排隊(duì)器。為了提高進(jìn)程調(diào)度的效率，應(yīng)事先將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個或多個隊(duì)列，以便調(diào)度程序能最快地找到它。(2)分派器(分派程序)。分派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，從就緒隊(duì)列中取出該進(jìn)程，然后進(jìn)行上下文切換，將處理機(jī)分配給它

(3)上下文切換機(jī)制。當(dāng)對處理機(jī)進(jìn)行切換時，會發(fā)生兩對上下文切換操作。在第一對上下文切換時，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二對上下文切換時，將移出運(yùn)行程序，而把新選進(jìn)程的CPU現(xiàn)場信息裝入到處理機(jī)的各個相應(yīng)寄存器中。

應(yīng)當(dāng)指出，上下文切換將花去不少的處理機(jī)時間，即使是現(xiàn)代計(jì)算機(jī)，每一次上下文切換大約需要花費(fèi)幾毫秒的時間，該時間大約可執(zhí)行上千條指令。為此，現(xiàn)在已有通過硬件(采用兩組或多組寄存器)的方法來減少上下文切換的時間。一組寄存器供處理機(jī)在系統(tǒng)態(tài)時使用，另一組寄存器供應(yīng)用程序使用。在這種條件下的上下文切換只需改變指針，使其指向當(dāng)前寄存器組即可。

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

1)非搶占方式(NonpreemptiveMode)

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

(1)正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；

(2)執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；

(3)在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時系統(tǒng)中，不宜采用這種調(diào)度方式。

2)搶占方式(PreemptiveMode)

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

(1)優(yōu)先權(quán)原則。通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程，使之執(zhí)行；或者說，允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。

(2)短作業(yè)(進(jìn)程)優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程)明顯的短時，將暫停當(dāng)前長作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行；

或者說，短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長作業(yè)(進(jìn)程)的處理機(jī)。

(3)時間片原則。各進(jìn)程按時間片輪流運(yùn)行，當(dāng)一個時間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時系統(tǒng)、大多數(shù)的實(shí)時系統(tǒng)，以及要求較高的批處理系統(tǒng)。

3.3.2輪轉(zhuǎn)調(diào)度算法

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

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

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

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

3.時間片大小的確定

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

影響。

如選擇很小的時間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，但會頻繁地發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開銷；反之，如選擇太長的時間片，使得每個進(jìn)程都能在一個時間片內(nèi)完成，時間片輪轉(zhuǎn)算法便退化為FCFS算法，無法滿足交互式用戶的需求。一個較為可取的大小是，時間片略大于一次典型的交互所需要的時間。這樣可使大多數(shù)進(jìn)程在一個時間片內(nèi)完成。

圖示出了時間片大小對響應(yīng)時間的影響，其中圖(a)是時間片略大于典型交互的時間，而圖(b)是時間片小于典型交互的時間。圖3-3示出了時間片分別為q?=?1和q?=?4時對平均周轉(zhuǎn)時間的影響。

圖3-2時間片大小對響應(yīng)時間的影響q=1和q=4時的進(jìn)程運(yùn)行情況

圖3-3q?=?1和q?=?4時進(jìn)程的周轉(zhuǎn)時間3.3.3優(yōu)先級調(diào)度算法

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

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

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

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

1)非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實(shí)時性要求不嚴(yán)的實(shí)時系統(tǒng)中。

2)搶占式優(yōu)先權(quán)調(diào)度算法在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此，在采用這種調(diào)度算法時，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。

2.優(yōu)先級的類型

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

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

確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個方面：

(1)進(jìn)程類型。通常，系統(tǒng)進(jìn)程(如接收進(jìn)程、對換進(jìn)程、磁盤I/O進(jìn)程)的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。

(2)進(jìn)程對資源的需求。如進(jìn)程的估計(jì)執(zhí)行時間及內(nèi)存需要量的多少，對這些要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)。

(3)用戶要求。這是由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來確定優(yōu)先權(quán)的。靜態(tài)優(yōu)先權(quán)法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進(jìn)程)長期沒有被調(diào)度的情況。因此，僅在要求不高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。

2)動態(tài)優(yōu)先級

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

例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機(jī)。

3.3.4多隊(duì)列調(diào)度算法

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

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

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

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

圖3-4是多級反饋隊(duì)列算法的示意圖。

(1)應(yīng)設(shè)置多個就緒隊(duì)列，并為各個隊(duì)列賦予不同的優(yōu)先級。第一個隊(duì)列的優(yōu)先級最高，第二個隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊(duì)列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊(duì)列的時間片要比第一個隊(duì)列的時間片長一倍，……，第i+1個隊(duì)列的時間片要比第i個隊(duì)列的時間片長一倍。(2)每個隊(duì)列都采用FCFS算法。當(dāng)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可撤離系統(tǒng)。否則，即它在一個時間片結(jié)束時尚未完成，調(diào)度程序?qū)⑵滢D(zhuǎn)入第二隊(duì)列的末尾等待調(diào)度；如果它在第二隊(duì)列中運(yùn)行一個時間片后仍未完成，再依次將它放入第三隊(duì)列，……，依此類推。當(dāng)進(jìn)程最后被降到第n隊(duì)列后，在第n隊(duì)列中便采取按RR方式運(yùn)行。

(3)按隊(duì)列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊(duì)列中的諸進(jìn)程運(yùn)行，僅當(dāng)?shù)谝魂?duì)列空閑時才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；換言之，僅當(dāng)?shù)?～(i-1)所有隊(duì)列均空時，才會調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時又有新進(jìn)程進(jìn)入任一優(yōu)先級較高的隊(duì)列，此時須立即把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，而把處理機(jī)分配給新到的高優(yōu)先級進(jìn)程。

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

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

(1)終端型用戶。

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

(3)長批處理作業(yè)用戶。

(1)終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)(進(jìn)程)在第一隊(duì)列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。

(2)短批處理作業(yè)用戶。對于很短的批處理型作業(yè)，開始時像終端型作業(yè)一樣，如果僅在第一隊(duì)列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時間。對于稍長的作業(yè)，通常也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。

(3)長批處理作業(yè)用戶。對于長作業(yè)，它將依次在第1，2，…，n個隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。

3.3.6基于公平原則的調(diào)度算法

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

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

在實(shí)施公平調(diào)度算法時系統(tǒng)中必須具有這樣一些功能：

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

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

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

(4)比較各進(jìn)程獲得處理機(jī)時間的比率。如進(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)行，直到超過最接近它的進(jìn)程比率為止。

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

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

3.4實(shí)

時

調(diào)

度

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

1.提供必要的信息

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

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

(2)開始截止時間和完成截止時間，對于典型的實(shí)時應(yīng)用，只須知道開始截止時間，或者完成截止時間。

(3)處理時間，一個任務(wù)從開始執(zhí)行，直至完成時所需的時間。

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

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

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

在實(shí)時系統(tǒng)中，若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過，而致使某些實(shí)時任務(wù)不能得到及時處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實(shí)時任務(wù)HRT，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件系統(tǒng)才是可調(diào)度的：假如系統(tǒng)中有6個硬實(shí)時任務(wù)，它們的周期時間都是50ms，而每次的處理時間為10ms，則不難算出，此時是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。

提高系統(tǒng)處理能力的途徑有二：一是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對每一個任務(wù)的處理時間；二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：

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

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

在含有硬實(shí)時任務(wù)的實(shí)時系統(tǒng)中，廣泛采用搶占機(jī)制。當(dāng)一個優(yōu)先權(quán)更高的任務(wù)到達(dá)時，允許將當(dāng)前任務(wù)暫時掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時任務(wù)對截止時間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。

對于一些小型實(shí)時系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時間，則對實(shí)時任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制，以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費(fèi)的系統(tǒng)開銷。但在設(shè)計(jì)這種調(diào)度機(jī)制時，應(yīng)使所有的實(shí)時任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地將自己阻塞起來，以便釋放出處理機(jī)，供調(diào)度程序去調(diào)度那種開始截止時間即將到達(dá)的任務(wù)。

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

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

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

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

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

1.非搶占式調(diào)度算法

(1)非搶占式輪轉(zhuǎn)調(diào)度算法。

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

1)非搶占式輪轉(zhuǎn)調(diào)度算法該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺計(jì)算機(jī)控制若干個相同的(或類似的)對象，為每一個被控對象建立一個實(shí)時任務(wù)，并將它們排成一個輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列中的第一個任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，而調(diào)度程序再選擇下一個(隊(duì)首)任務(wù)運(yùn)行。這種調(diào)度算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時間，可用于要求不太嚴(yán)格的實(shí)時控制系統(tǒng)中。

2)非搶占式優(yōu)先調(diào)度算法

如果在實(shí)時系統(tǒng)中存在著要求較為嚴(yán)格(響應(yīng)時間為數(shù)百毫秒)的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級。當(dāng)這些實(shí)時任務(wù)到達(dá)時，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行。這種調(diào)度算法在做了精心的處理后，有可能獲得僅為數(shù)秒至數(shù)百毫秒級的響應(yīng)時間，因而可用于有一定要求的實(shí)時控制系統(tǒng)中。

2.搶占式調(diào)度算法

在要求較嚴(yán)格的(響應(yīng)時間為數(shù)十毫秒以下)的實(shí)時系統(tǒng)中，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法?？筛鶕?jù)搶占發(fā)生時間的不同而進(jìn)一步分成以下兩種調(diào)度算法：

(1)基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法。

(2)立即搶占(ImmediatePreemption)的優(yōu)先級調(diào)度算法。

1)基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實(shí)時任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級高于當(dāng)前任務(wù)的優(yōu)先級，這時并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時鐘中斷到來時，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實(shí)時系統(tǒng)中。

2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請求中斷的緊迫任務(wù)。這種算法能獲得非?？斓捻憫?yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。

圖3-5實(shí)時進(jìn)程調(diào)度3.4.3最早截止時間優(yōu)先EDF(EarliestDeadlineFirst)算法

該算法是根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。該算法要求在系統(tǒng)中保持一個實(shí)時任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時間的早晚排序；當(dāng)然，具有最早截止時間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序在選擇任務(wù)時，總是選擇就緒隊(duì)列中的第一個任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。最早截止時間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。

1.非搶占式調(diào)度方式用于非周期實(shí)時任務(wù)

該例中具有四個非周期任務(wù)，它們先后到達(dá)。系統(tǒng)首先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、3又先后到達(dá)。由于任務(wù)3的開始截止時間早于任務(wù)2，故系統(tǒng)在任務(wù)1后將調(diào)度任務(wù)3執(zhí)行。在此期間又到達(dá)作業(yè)4，其開始截止時間仍是早于任務(wù)2的，故在任務(wù)3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4執(zhí)行，最后才調(diào)度任務(wù)2執(zhí)行。

2.搶占式調(diào)度方式用于周期實(shí)時任務(wù)

在該例中有兩個周期任務(wù)，任務(wù)A和任務(wù)B的周期時間分別為20ms和50ms，每個周期的處理時間分別為10?ms和25?ms。圖中的第一行示出了兩個任務(wù)的到達(dá)時間、最后期限和執(zhí)行時間圖。其中任務(wù)A的到達(dá)時間為0、20、40、…；任務(wù)A的最后期限為20、40、60、…；任務(wù)B的到達(dá)時間為0、50、100、…；任務(wù)B的最后期限為50、100、150、…(注：單位皆為ms)。

為了說明通常的優(yōu)先級調(diào)度不能適用于實(shí)時系統(tǒng)，該圖特增加了第二和第三行。在第二行中假定任務(wù)A具有較高的優(yōu)先級，所以在t=0ms時，先調(diào)度A1執(zhí)行，在A1完成后(t=10ms)才調(diào)度B1執(zhí)行；在t=20ms時，調(diào)度A2執(zhí)行；在t=30ms時，A2完成，又調(diào)度B1執(zhí)行；在t=40ms時，調(diào)度A3執(zhí)行；在t=50ms時，雖然A3已完成，但B1已錯過了它的最后期限，這說明了利用通常的優(yōu)先級調(diào)度已經(jīng)失敗。第三行與第二行類似，只是假定任務(wù)B具有較高的優(yōu)先級。

第四行是采用最早截止時間優(yōu)先算法的時間圖。在t=0時，A1和B1同時到達(dá)，由于A1的截止時間比B1早，故調(diào)度A1執(zhí)行；在t=10時，A1完成，又調(diào)度B1執(zhí)行；在t=20時，A2到達(dá)，由于A2的截止時間比B2早，B1被中斷而調(diào)度A2執(zhí)行；在t=30時，A2完成，又重新調(diào)度B1執(zhí)行；在t=40時，A3又到達(dá)，但B1的截止時間要比A3早，仍應(yīng)讓B1繼續(xù)執(zhí)行直到完成(t=45)，然后再調(diào)度A3執(zhí)行；在t=55時，A3完成，又調(diào)度B2執(zhí)行。在該例中利用最早截止時間優(yōu)先算法可以滿足系統(tǒng)的要求。

3.4.4最低松弛度優(yōu)先LLF(LeastLaxityFirst)算法

該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在200ms時必須完成，而它本身所需的運(yùn)行時間就有100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100ms。又如，另一任務(wù)在400ms時必須完成，它本身需要運(yùn)行150ms，則其松弛程度為250ms。在實(shí)現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實(shí)時任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。

該算法主要用于可搶占調(diào)度方式中。假如在一個實(shí)時系統(tǒng)中，有兩個周期性實(shí)時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。由此可得知任務(wù)A和B每次必須完成的時間分別為：A1、A2、A3、…和B1、B2、B3、…，見圖3-11。為保證不遺漏任何一次截止時間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。

在剛開始時(t1?=?0)，A1必須在20ms時完成，而它本身運(yùn)行又需10ms，可算出A1的松弛度為10ms；B1必須在50ms時完成，而它本身運(yùn)行就需25ms，可算出B1的松弛度為25ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2?=?10ms時，A2的松弛度可按下式算出：

A2的松弛度?=?必須完成時間

-?其本身的運(yùn)行時間

-?當(dāng)前時間

=?40ms-10ms-10ms?=?20ms

類似地，可算出B1的松弛度為15ms，故調(diào)度程序應(yīng)選擇B2運(yùn)行。在t3?=?30ms時，A2的松弛度已減為0(即40?-?10?-?30)，而B1的松弛度為15ms(即50?-?5?-?30)，于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行。在t4?=?40ms時，A3的松弛度為10ms(即60?-?10?-?40)，而B1的松弛度僅為5ms(即50?-?5?-?40)，故又應(yīng)重新調(diào)度B1執(zhí)行。在t5?=?45ms時，B1執(zhí)行完成，而此時A3的松弛度已減為5ms(即60?-?10?-?45)，而B2的松弛度為30ms(即100?-?25?-?45)，于是又應(yīng)調(diào)度A3執(zhí)行。在t6?=?55ms時，任務(wù)A尚未進(jìn)入第4周期，而任務(wù)B已進(jìn)入第2周期，故再調(diào)度B2執(zhí)行。在t7?=?70ms時，A4的松弛度已減至0ms(即80?-?10?-?70)，而B2的松弛度為20ms(即100?-?10?-?70)，故此時調(diào)度又應(yīng)搶占B2的處理機(jī)而調(diào)度A4執(zhí)行。圖3-9示出了具有兩個周期性實(shí)時任務(wù)的調(diào)度情況。

圖3-9利用ELLF算法進(jìn)行調(diào)度的情況3.4.5優(yōu)先級倒置(priorityinversionproblem)

1.優(yōu)先級倒置的形成

當(dāng)前OS廣泛采用優(yōu)先級調(diào)度算法和搶占方式，然而在系統(tǒng)中存在著影響進(jìn)程運(yùn)行的資源而可能產(chǎn)生“優(yōu)先級倒置”的現(xiàn)象，即高優(yōu)先級進(jìn)程(或線程)被低優(yōu)先級進(jìn)程(或線程)延遲或阻塞。我們通過一個例子來說明該問題。

假如P3最先執(zhí)行，在執(zhí)行了P(mutex)操作后，進(jìn)入到臨界區(qū)CS-3。在時刻a，P2就緒，因?yàn)樗萈3的優(yōu)先級高，P2搶占了P3的處理機(jī)而運(yùn)行，如圖3-10所示。

2.優(yōu)先級倒置的解決方法

一種簡單的解決方法是規(guī)定：假如進(jìn)程P3在進(jìn)入臨界區(qū)后P3所占用的處理機(jī)就不允許被搶占。

圖3-11采用了動態(tài)優(yōu)先級繼承方法的運(yùn)行情況

3.5死

鎖

概

述

3.5.1資源問題

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

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

1)可重用性資源

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

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

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

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

2)可消耗性資源

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

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

1)可搶占性資源

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

2)不可搶占性資源

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

3.5.2計(jì)算機(jī)系統(tǒng)中的死鎖

1.競爭不可搶占性資源引起死鎖

通常系統(tǒng)中所擁有的不可搶占性資源其數(shù)量不足以滿足多個進(jìn)程運(yùn)行的需要，使得進(jìn)程在運(yùn)行過程中，會因爭奪資源而陷入僵局。

我們可將上面的問題利用資源分配圖進(jìn)行描述，用方塊代表可重用的資源(文件)，用圓圈代表進(jìn)程，見圖3-12所示。

圖3-12共享文件時的死鎖情況

2.競爭可消耗資源引起死鎖

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

圖3-13進(jìn)程之間通信時的死鎖

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

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

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)順序是合法的。

2)進(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運(yùn)行到P1：Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)行到P2：Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖，這樣的進(jìn)程推進(jìn)順序就是非法的。圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響3.5.3死鎖的定義、必要條件和處理方法

1.死鎖的定義

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

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

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

(1)互斥條件。

(2)請求和保持條件。

(3)不可搶占條件。

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

3.處理死鎖的方法

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

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

(2)避免死鎖。

(3)檢測死鎖。

(4)解除死鎖。

3.6預(yù)

防

死

鎖

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

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

1.第一種協(xié)議

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

2.第二種協(xié)議

該協(xié)議是對第一種協(xié)議的改進(jìn)，它允許一個進(jìn)程只獲得運(yùn)行初期所需的資源后，便開始運(yùn)行。

3.6.2破壞“不可搶占”條件

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

一個能保證“循環(huán)等待”條件不成立的方法是，對系統(tǒng)所有資源類型進(jìn)行線性排序，并賦予不同的序號。

3.7避

免

死

鎖

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

2.安全狀態(tài)之例

假定系統(tǒng)中有三個進(jìn)程P1、P2和P3，共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī)，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機(jī)，尚有3臺空閑未分配，如下表所示：

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

如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。

3.7.2利用銀行家算法避免死鎖

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

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

為了實(shí)現(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。

2.銀行家算法

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

(1)如果Request?i[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；

否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。

(2)如果Request?i[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；

否則，表示尚無足夠資源，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ù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。

3.安全性算法

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

(1)設(shè)置兩個向量：①工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work:=Available；②Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finish[i]:=false；當(dāng)有足夠資源分配給進(jìn)程時，再令Finish[i]:=true。

(2)從進(jìn)程集合中找到一個能滿足下述條件的進(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)中有五個進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表

(1)?T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進(jìn)行分析(如圖3-16所示)可知，在T0時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。圖3-16T0時刻的安全序列

(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)先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示；

④再利用安全性算法檢查此時系統(tǒng)是否安全，如圖3-17所示。圖3-17P1申請資源時的安全性檢查

(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)，系統(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所示。圖3-18為P0分配資源后的有關(guān)資源數(shù)據(jù)

(5)進(jìn)行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資源。

3.8死鎖的檢測與解除

如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會發(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)中解脫出來。3.8.1死鎖的檢測

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

1.資源分配圖(ResourceAllocationGraph)

系統(tǒng)死鎖，可利用資源分配圖來描述。

該圖是由一組結(jié)點(diǎn)N和一組邊E所組成的一個對偶G?=?(N,E)，它具有下述形式的定義和限制：

(1)把N分為兩個互斥的子集，即一組進(jìn)程結(jié)點(diǎn)P={P1,P2,…,Pn}和一組資源結(jié)點(diǎn)