第3章處理機調(diào)度與死鎖

第三章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除3.1處理機調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)(作業(yè)調(diào)度)

在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。

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

2)接納哪些作業(yè)2.低級調(diào)度(LowLevelScheduling)（進程調(diào)度）

1)非搶占方式(Non-preemptiveMode)

在采用非搶占調(diào)度方式時，可能引起進程調(diào)度的因素可歸結(jié)為這樣幾個：①正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；②執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；③在進程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。2)搶占方式(PreemptiveMode)搶占的原則有：優(yōu)先權(quán)原則。(2)短作業(yè)(進程)優(yōu)先原則。(3)時間片原則。3.中級調(diào)度(Intermediate-LevelScheduling)

中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)。引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進程重又具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。3.1.2調(diào)度隊列模型1.僅有進程調(diào)度的調(diào)度隊列模型圖3-1僅具有進程調(diào)度的調(diào)度隊列模型2.具有高級和低級調(diào)度的調(diào)度隊列模型圖3-2具有高、低兩級調(diào)度的調(diào)度隊列模型就緒隊列的形式。

(2)設(shè)置多個阻塞隊列。

圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。3.同時具有三級調(diào)度的調(diào)度隊列模型圖3-3具有三級調(diào)度時的調(diào)度隊列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時間短。

可把平均周轉(zhuǎn)時間描述為：作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為:(2)響應(yīng)時間快。(3)截止時間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。2.面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。3.2調(diào)度算法3.2.1先來先服務(wù)和短作業(yè)(進程)優(yōu)先調(diào)度算法1.先來先服務(wù)調(diào)度算法圖3-4FCFS和SJF調(diào)度算法的性能2.短作業(yè)(進程)優(yōu)先調(diào)度算法

短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。SJ(P)F調(diào)度算法也存在不容忽視的缺點：

(1)該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時間由10增至16，其帶權(quán)周轉(zhuǎn)時間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進程)進入系統(tǒng)的后備隊列(就緒隊列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進來的)短作業(yè)(進程)，將導(dǎo)致長作業(yè)(進程)長期不被調(diào)度。

(2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進程)會被及時處理。

(3)由于作業(yè)(進程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法

在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中。2)搶占式優(yōu)先權(quán)調(diào)度算法在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當(dāng)前進程(原優(yōu)先權(quán)最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。因此，在采用這種調(diào)度算法時，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進程i時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進程j的優(yōu)先權(quán)Pj進行比較。如果Pi≤Pj，原進程Pj便繼續(xù)執(zhí)行；但如果是Pi＞Pj,則立即停止Pj的執(zhí)行，做進程切換，使i進程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。2.優(yōu)先權(quán)的類型1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。確定進程優(yōu)先權(quán)的依據(jù)有如下三個方面：進程類型。(2)進程對資源的需求。(3)用戶要求。2)動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進入就緒隊列的進程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機，此即FCFS算法。若所有的就緒進程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。3.高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)的變化規(guī)律可描述為：由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：(1)如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。

(2)當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。

(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.時間片輪轉(zhuǎn)法在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。時間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間。2.多級反饋隊列調(diào)度算法(1)應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。圖3-5是多級反饋隊列算法的示意。圖3-5多級反饋隊列調(diào)度算法(2)當(dāng)一個新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。當(dāng)輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當(dāng)一個長作業(yè)(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運行。(3)僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進程運行；僅當(dāng)?shù)?~(i-1)隊列均空時，才會調(diào)度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務(wù)時，又有新進程進入優(yōu)先權(quán)較高的隊列(第1~(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權(quán)進程。3.多級反饋隊列調(diào)度算法的性能終端型作業(yè)用戶。(2)短批處理作業(yè)用戶。(3)長批處理作業(yè)用戶。

3.3進程調(diào)度

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

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

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

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

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

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

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

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

(1)排隊器。

(2)分派器。

(3)上下文切換器。圖3-1進程調(diào)度機制

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

1)非搶占方式(NonpreemptiveMode)

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

2)搶占方式(PreemptiveMode)

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

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

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

2.進程切換時機

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

3.時間片大小的確定

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

影響。

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

(2)進程對資源的需求。

(3)用戶要求。

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

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

如前所述的各種調(diào)度算法，尤其在應(yīng)用于進程調(diào)度時，由于系統(tǒng)中僅設(shè)置一個進程的就緒隊列，即低級調(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)設(shè)置多個就緒隊列。

圖3-4是多級反饋隊列算法的示意圖。圖3-4多級反饋隊列調(diào)度算法

(2)每個隊列都采用FCFS算法。當(dāng)新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可撤離系統(tǒng)。否則，即它在一個時間片結(jié)束時尚未完成，調(diào)度程序?qū)⑵滢D(zhuǎn)入第二隊列的末尾等待調(diào)度；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，依此類推。當(dāng)進程最后被降到第n隊列后，在第n隊列中便采取按RR方式運行。

(3)按隊列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列中的諸進程運行，僅當(dāng)?shù)谝魂犃锌臻e時才調(diào)度第二隊列中的進程運行；換言之，僅當(dāng)?shù)?～(i-1)所有隊列均空時，才會調(diào)度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務(wù)時又有新進程進入任一優(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)計算每個進程應(yīng)獲得的處理機時間，即自創(chuàng)建以來的時間除以n。

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

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

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

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

分配給每個進程相同的處理機時間，顯然，這對諸進程而言，是體現(xiàn)了一定程度的公平，但如果各個用戶所擁有的進程數(shù)不同，就會發(fā)生對用戶的不公平問題。3.3實時調(diào)度3.3.1實現(xiàn)實時調(diào)度的基本條件1.提供必要的信息就緒時間。(2)開始截止時間和完成截止時間。(3)處理時間。(4)資源要求。(5)優(yōu)先級。2.系統(tǒng)處理能力強

在實時系統(tǒng)中，通常都有著多個實時任務(wù)。若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務(wù)不能得到及時處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實時任務(wù)，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件：

系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個硬實時任務(wù)，它們的周期時間都是50ms，而每次的處理時間為10ms，則不難算出，此時是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機系統(tǒng)，但須增強其處理能力，以顯著地減少對每一個任務(wù)的處理時間；其二是采用多處理機系統(tǒng)。假定系統(tǒng)中的處理機數(shù)為N，則應(yīng)將上述的限制條件改為：3.采用搶占式調(diào)度機制

當(dāng)一個優(yōu)先權(quán)更高的任務(wù)到達(dá)時，允許將當(dāng)前任務(wù)暫時掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運行，這樣便可滿足該硬實時任務(wù)對截止時間的要求。但這種調(diào)度機制比較復(fù)雜。對于一些小的實時系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時間，則對實時任務(wù)的調(diào)度可采用非搶占調(diào)度機制，以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費的系統(tǒng)開銷。但在設(shè)計這種調(diào)度機制時，應(yīng)使所有的實時任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地將自己阻塞起來，以便釋放出處理機，供調(diào)度程序去調(diào)度那種開始截止時間即將到達(dá)的任務(wù)。4.具有快速切換機制

該機制應(yīng)具有如下兩方面的能力：

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

(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進行任務(wù)切換。為了提高分派程序進行任務(wù)切換時的速度，應(yīng)使系統(tǒng)中的每個運行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時間開銷。3.3.2實時調(diào)度算法的分類1.非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法。(2)非搶占式優(yōu)先調(diào)度算法。2.搶占式調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。(2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法。圖3-6實時進程調(diào)度3.3.3常用的幾種實時調(diào)度算法1.最早截止時間優(yōu)先即EDF(EarliestDeadlineFirst)算法圖3-7EDF算法用于非搶占調(diào)度方式2.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法

該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在200ms時必須完成，而它本身所需的運行時間就有100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100ms。又如，另一任務(wù)在400ms時必須完成，它本身需要運行150ms，則其松弛程度為250ms。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊列最前面，調(diào)度程序總是選擇就緒隊列中的隊首任務(wù)執(zhí)行。該算法主要用于可搶占調(diào)度方式中。假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。圖3-8A和B任務(wù)每次必須完成的時間

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

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

類似地，可算出B1的松弛度為15ms，故調(diào)度程序應(yīng)選擇B2運行。在t3=30ms時，A2的松弛度已減為0(即40-10-30)，而B1的松弛度為15ms(即50-5-30)，于是調(diào)度程序應(yīng)搶占B1的處理機而調(diào)度A2運行。在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尚未進入第4周期，而任務(wù)B已進入第2周期，故再調(diào)度B2執(zhí)行。在t7=70ms時，A4的松弛度已減至0ms(即80-10-70)，而B2的松弛度為20ms(即100-10-70)，故此時調(diào)度又應(yīng)搶占B2的處理機而調(diào)度A4執(zhí)行。圖3-9利用ELLF算法進行調(diào)度的情況3.4多處理機系統(tǒng)中的調(diào)度3.4.1多處理器系統(tǒng)的類型(1)緊密耦合(TightlyCoupted)MPS。這通常是通過高速總線或高速交叉開關(guān)，來實現(xiàn)多個處理器之間的互連的。它們共享主存儲器系統(tǒng)和I/O設(shè)備，并要求將主存儲器劃分為若干個能獨立訪問的存儲器模塊，以便多個處理機能同時對主存進行訪問。系統(tǒng)中的所有資源和進程，都由操作系統(tǒng)實施統(tǒng)一的控制和管理。(2)松散耦合(LooselyCoupled)MPS。在松散耦合MPS中，通常是通過通道或通信線路，來實現(xiàn)多臺計算機之間的互連。每臺計算機都有自己的存儲器和I/O設(shè)備，并配置了OS來管理本地資源和在本地運行的進程。因此，每一臺計算機都能獨立地工作，必要時可通過通信線路與其它計算機交換信息，以及協(xié)調(diào)它們之間的工作。2.對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)(1)對稱多處理器系統(tǒng)SMPS(SymmetricMultiProcessorSystem)。在系統(tǒng)中所包含的各處理器單元，在功能和結(jié)構(gòu)上都是相同的，當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)。例如，IBM公司的SR/6000ModelF50,便是利用4片PowerPC處理器構(gòu)成的。

(2)非對稱多處理器系統(tǒng)。在系統(tǒng)中有多種類型的處理單元，它們的功能和結(jié)構(gòu)各不相同，其中只有一個主處理器，有多個從處理器。3.4.2進程分配方式1.對稱多處理器系統(tǒng)中的進程分配方式在SMP系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為一個處理器池(Processorpool)，由調(diào)度程序或基于處理器的請求，將任何一個進程分配給池中的任何一個處理器去處理。在進行進程分配時，可采用以下兩種方式之一。

1)靜態(tài)分配(StaticAssigenment)方式

2)動態(tài)分配(DynamicAssgement)方式2.非對稱MPS中的進程分配方式對于非對稱MPS，其OS大多采用主—從(Master-Slave)式OS，即OS的核心部分駐留在一臺主機上(Master)，而從機(Slave)上只是用戶程序，進程調(diào)度只由主機執(zhí)行。每當(dāng)從機空閑時，便向主機發(fā)送一索求進程的信號，然后，便等待主機為它分配進程。在主機中保持有一個就緒隊列，只要就緒隊列不空，主機便從其隊首摘下一進程分配給請求的從機。從機接收到分配的進程后便運行該進程，該進程結(jié)束后從機又向主機發(fā)出請求。3.4.3進程(線程)調(diào)度方式

1.自調(diào)度(Self-Scheduling)方式

1)自調(diào)度機制在多處理器系統(tǒng)中，自調(diào)度方式是最簡單的一種調(diào)度方式。它是直接由單處理機環(huán)境下的調(diào)度方式演變而來的。在系統(tǒng)中設(shè)置有一個公共的進程或線程就緒隊列，所有的處理器在空閑時，都可自己到該隊列中取得一進程(或線程)來運行。在自調(diào)度方式中，可采用在單處理機環(huán)境下所用的調(diào)度算法，如先來先服務(wù)(FCFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。2)自調(diào)度方式的優(yōu)點自調(diào)度方式的主要優(yōu)點表現(xiàn)為：首先，系統(tǒng)中的公共就緒隊列可按照單處理機系統(tǒng)中所采用的各種方式加以組織；其調(diào)度算法也可沿用單處理機系統(tǒng)所用的算法，亦即，很容易將單處理機環(huán)境下的調(diào)度機制移植到多處理機系統(tǒng)中，故它仍然是當(dāng)前多處理機系統(tǒng)中較常用的調(diào)度方式。其次，只要系統(tǒng)中有任務(wù)，或者說只要公共就緒隊列不空，就不會出現(xiàn)處理機空閑的情況，也不會發(fā)生處理器忙閑不均的現(xiàn)象，因而有利于提高處理器的利用率。3)自調(diào)度方式的缺點瓶頸問題。(2)低效性。(3)線程切換頻繁。2.成組調(diào)度(GangScheduling)方式

在成組調(diào)度時，如何為應(yīng)用程序分配處理器時間，

1)面向所有應(yīng)用程序平均分配處理器時間

2)面向所有線程平均分配處理器時間圖3-10兩種分配處理器時間的方法3.專用處理器分配(DedicatedProcessorAssigement)方式圖3-11線程數(shù)對加速比的影響3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因競爭資源。(2)進程間推進順序非法。1.競爭資源引起進程死鎖可剝奪和非剝奪性資源2)競爭非剝奪性資源3)競爭臨時性資源圖3-12I/O設(shè)備共享時的死鎖情況圖3-13進程之間通信時的死鎖2.進程推進順序不當(dāng)引起死鎖1)進程推進順序合法圖3-14進程推進順序?qū)λ梨i的影響2)進程推進順序非法若并發(fā)進程P1和P2按曲線④所示的順序推進，它們將進入不安全區(qū)D內(nèi)。此時P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因為，這時兩進程再向前推進，便可能發(fā)生死鎖。例如，當(dāng)P1運行到P1:Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運行到P2:Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進程死鎖。3.5.2產(chǎn)生死鎖的必要條件互斥條件(2)請求和保持條件(3)不剝奪條件(4)環(huán)路等待條件3.5.3處理死鎖的基本方法預(yù)防死鎖。(2)避免死鎖。(3)檢測死鎖。(4)解除死鎖。3.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖摒棄“請求和保持”條件2.摒棄“不剝奪”條件3.摒棄“環(huán)路等待”條件3.6.2系統(tǒng)安全狀態(tài)

1.安全狀態(tài)在避免死鎖的方法中，允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程；否則，令進程等待。所謂安全狀態(tài)，是指系統(tǒng)能按某種進程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。2.安全狀態(tài)之例我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P3104952233.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。因為，此時也無法再找到一個安全序列，例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。3.6.3利用銀行家算法避免死鎖1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max［i,j］=K，則表示進程i需要Rj類資源的最大數(shù)目為K。

(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。如果Allocation［i,j］=K，則表示進程i當(dāng)前已分得Rj類資源的數(shù)目為K。

(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need［i,j］=K，則表示進程i還需要Rj類資源K個，方能完成其任務(wù)。Need［i,j］=Max［i,j］-Allocation［i,j］

2.銀行家算法設(shè)Requesti是進程Pi的請求向量，如果Requesti［j］=K，表示進程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：

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

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

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。3.安全性算法(1)設(shè)置兩個向量：①工作向量Work:它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］∶=false;當(dāng)有足夠資源分配給進程時，再令Finish［i］∶=true。(2)從進程集合中找到一個能滿足下述條件的進程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。

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

Work［j］∶=Work［i］+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時刻的安全性：圖3-16T0時刻的安全序列(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查：①Request1(1,0,2)≤Need