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

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

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

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

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

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

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

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

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

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

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

引入中級調(diào)度的目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)之外存去等待，把此時的進程狀態(tài)稱為靜止就緒狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。中級調(diào)度實際上就是存儲器管理中的對換功能。3.1.2處理機調(diào)度算法的目標

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

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

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

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

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

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

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

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

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

(1)響應時間快。

(2)均衡性。

4.實時系統(tǒng)的目標

(1)截止時間的保證。

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

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

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

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

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

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

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

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

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

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

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

(1)收容階段。

(2)運行階段。

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

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

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

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

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

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

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

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

由于在實際情況中，短作業(yè)(進程)占有很大比例，為了能使它們能比長作業(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)度和進程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算法用于作業(yè)調(diào)度時，它將從外存的作業(yè)后備隊列中選擇若干個估計運行時間最短的作業(yè)，優(yōu)先將它們調(diào)入內(nèi)存運行。2)短作業(yè)優(yōu)先算法的缺點

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

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

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

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

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

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

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

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

缺點：在利用該算法時，每次要進行調(diào)度之前，都需要先做響應比的計算，顯然會增加系統(tǒng)開銷。?3.3進程調(diào)度

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

1.進程調(diào)度的任務

進程調(diào)度的任務主要有三：

(1)保存處理機的現(xiàn)場信息。

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

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

2.進程調(diào)度機制

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

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

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

(3)上下文切換器。

圖3-1進程調(diào)度機制

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

1)非搶占方式(NonpreemptiveMode)

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

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

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

2、短進程優(yōu)先原則：允許新到的短進程可以搶占當前長進程的處理機

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

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

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

2.進程切換時機

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

3.時間片大小的確定

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

影響。

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

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

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

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

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

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

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

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

(1)進程類型：系統(tǒng)進程高于用戶進程

(2)進程對資源的需求：對資源要求少的進程應賦予較高的優(yōu)先級

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

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

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

1.調(diào)度機制

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

(1)設置多個就緒隊列。

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

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

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

(1)終端型用戶。

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

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

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

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

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

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

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

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

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

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

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

3.4實時調(diào)度

課程導入：

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

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

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

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

1.提供必要的信息

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

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

(2)開始截止時間和完成截止時間，對于典型的實時應用，只須知道開始截止時間，或者完成截止時間。(3)處理時間，一個任務從開始執(zhí)行，直至完成時所需的時間。

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

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

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

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

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

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

4.具有快速切換機制

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

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

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

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

3.5死鎖概述

3.5.1資源問題

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

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

1)可重用性資源

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

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

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

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

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

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

1)可搶占性資源

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

2)不可搶占性資源

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

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

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

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

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

3.進程推進順序不當引起死鎖

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

在進程P1和P2并發(fā)執(zhí)行時，如果按圖3-14中的曲線①所示的順序推進：P1：Request(R1)→P1：Request(R2)→P1：Releast(R1)→P1：Release(R2)→P2：Request(R2)→P2：Request(R1)→P2：Release(R2)→P2：Release(R1)，兩個進程可順利完成。類似地，若按圖中曲線②和③所示的順序推進，兩進程也可以順利完成。我們稱這種不會引起進程死鎖的推進順序是合法的。2)進程推進順序非法

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

1.死鎖的定義

死鎖（DeadLock）：是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種狀態(tài)時，若無外力作用，它們都將無法向前推進。

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

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

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

(1)互斥條件。

(2)請求和保持條件。

(3)不可搶占條件。

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

3.處理死鎖的方法

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

(1)預防死鎖。

(2)避免死鎖。

(3)檢測死鎖。

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

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

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

1.第一種協(xié)議

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

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

2.第二種協(xié)議

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

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

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

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

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

1.安全狀態(tài)

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

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

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

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

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

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

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

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

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

(2)最大需求矩陣Max。

(3)分配矩陣Allocation。

(4)需求矩陣Need。

2.銀行家算法

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

(1)如果Request?i[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。

(2)如果Request?i[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。(3)系統(tǒng)試探著把資源分配給進程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)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。

3.安全性算法

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

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

①Finish[i]=false;

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

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

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

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

Finish[i]=true;

gotostep2;

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

4.銀行家算法之例

假定系統(tǒng)中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表(1)?T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進行分析(如圖3-16所示)可知，在T0時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。圖3-16T0時刻的安全序列(2)?P1請求資源：P1發(fā)出請求向量Request1(1,0,2)，系統(tǒng)按銀行家算法進行檢查：

①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)按銀行家算法進行檢查：

①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)按銀行家算法進行檢查：

①Request0(0，2，0)≤Need0(7，4，3)；

②Request0(0，2，0)≤Available(2，3，0)；

③系統(tǒng)暫時先假定可為P0分配資源，并修改有關數(shù)據(jù)，如圖3-18所示。圖3-18為P0分配資源后的有關資源數(shù)據(jù)(5)進行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。

3.8死鎖的檢測與解除

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

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

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

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

1.資源分配圖(ResourceAllocationGraph)

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

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

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

2．死鎖定理

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

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

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