28-處理器調(diào)度算法課件

主要內(nèi)容：低級(jí)調(diào)度的功能和類型作業(yè)調(diào)度和低級(jí)調(diào)度算法實(shí)時(shí)調(diào)度算法多處理器調(diào)度算法2.8處理器調(diào)度算法12.8.1低級(jí)調(diào)度的功能低級(jí)調(diào)度負(fù)責(zé)動(dòng)態(tài)地把處理器分配給進(jìn)程或內(nèi)核級(jí)線程。適用于進(jìn)程調(diào)度的算法一般都適用于內(nèi)核級(jí)線程的調(diào)度。注意：用戶級(jí)線程的調(diào)度是用戶程序自己的事情，與操作系統(tǒng)無(wú)關(guān)，不屬于低級(jí)調(diào)度。在純用戶級(jí)線程系統(tǒng)中，低級(jí)調(diào)度的對(duì)象仍然是進(jìn)程；在內(nèi)核級(jí)線程和混合式線程系統(tǒng)中，低級(jí)調(diào)度的對(duì)象是內(nèi)核級(jí)線程低級(jí)調(diào)度的主要功能調(diào)度程序擔(dān)負(fù)兩項(xiàng)任務(wù)：調(diào)度和分派。2調(diào)度實(shí)現(xiàn)調(diào)度策略，確定就緒態(tài)進(jìn)程/線程競(jìng)爭(zhēng)使用處理器的次序的裁決原則，即進(jìn)程/線程何時(shí)應(yīng)該放棄CPU和選擇哪個(gè)進(jìn)程/線程來(lái)執(zhí)行。分派實(shí)現(xiàn)調(diào)度機(jī)制，確定如何時(shí)分復(fù)用CPU，處理上下文交換細(xì)節(jié)，完成進(jìn)程/線程同CPU的綁定以及放棄的實(shí)際工作。什么時(shí)候需要低級(jí)調(diào)度？創(chuàng)建新進(jìn)程/線程；進(jìn)程/線程終止；進(jìn)程/線程阻塞自己；進(jìn)程/線程運(yùn)行過(guò)程中出現(xiàn)異常/中斷；進(jìn)程/線程執(zhí)行系統(tǒng)調(diào)用；進(jìn)程/線程所請(qǐng)求的I/O操作完成；進(jìn)程/線程耗盡時(shí)間片；進(jìn)程/線程改變優(yōu)先級(jí)等。3從概念上看，調(diào)度機(jī)制由三個(gè)邏輯功能模塊組成：隊(duì)列管理程序上下文切換程序分派程序2低級(jí)調(diào)度的基本類型低級(jí)調(diào)度的基本類型是指調(diào)度策略選擇下一個(gè)運(yùn)行進(jìn)程的時(shí)間點(diǎn)和仲裁方式，在其他時(shí)間不能改變已經(jīng)獲得處理器的進(jìn)程的分派情況。分為兩種：剝奪式（搶先式）：當(dāng)進(jìn)程/線程正在處理器上運(yùn)行時(shí)，系統(tǒng)可以根據(jù)規(guī)定的原則剝奪分配給此進(jìn)程/線程的處理器，將其移入就緒隊(duì)列，選擇其他進(jìn)程/線程來(lái)運(yùn)行。有兩種剝奪原則：高優(yōu)先級(jí)的進(jìn)程/線程剝奪低優(yōu)先級(jí)進(jìn)程/線程進(jìn)程/線程的時(shí)間片用完之后被剝奪4非剝奪式（非搶先式）：一旦進(jìn)程/線程獲得處理器開始運(yùn)行后就不再出讓處理器，除非它執(zhí)行結(jié)束，或者主動(dòng)放棄處理器，或者因發(fā)生某個(gè)事件而不能繼續(xù)執(zhí)行。剝奪式策略的開銷比非剝奪式策略的開銷大，主要是調(diào)度程序自身的開銷，以及主存和磁盤的對(duì)換程序、數(shù)據(jù)的開銷。但是，剝奪式策略可以避免進(jìn)程/線程長(zhǎng)時(shí)間地獨(dú)占處理器，對(duì)于實(shí)時(shí)系統(tǒng)和分時(shí)系統(tǒng)有利，能為用戶提供高性能的服務(wù)。操作系統(tǒng)一般使用兩種調(diào)度策略的結(jié)合，而且內(nèi)核關(guān)鍵程序是非剝奪的，用戶進(jìn)程是剝奪式的。5低級(jí)調(diào)度的最初對(duì)象是傳統(tǒng)操作系統(tǒng)中的進(jìn)程，操作系統(tǒng)中引入了線程以后，進(jìn)程只作為中級(jí)調(diào)度的對(duì)象，內(nèi)核級(jí)線程則替代進(jìn)程成為低級(jí)調(diào)度的對(duì)象。適用于進(jìn)程調(diào)度的算法一般都適用于內(nèi)核級(jí)線程的調(diào)度。用戶級(jí)線程的調(diào)度是應(yīng)用程序自己的事。在純用戶級(jí)多線程策略中，低級(jí)調(diào)度的對(duì)象依然是進(jìn)程；在混合策略中，低級(jí)調(diào)度的對(duì)象是內(nèi)核級(jí)線程。

62.8.2作業(yè)調(diào)度和低級(jí)調(diào)度算法1.先來(lái)先服務(wù)算法

(1)策略：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來(lái)挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。

這是一種非剝奪式算法。

(2)效果：算法容易實(shí)現(xiàn)，效率不高，只顧及作業(yè)等候時(shí)間，沒(méi)考慮作業(yè)要求服務(wù)時(shí)間的長(zhǎng)短，不利于短作業(yè)而優(yōu)待了長(zhǎng)作業(yè)。有利于CPU繁忙型作業(yè)而不利于I/O繁忙型作業(yè)。

例如，三個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：

作業(yè)名所需CPU時(shí)間作業(yè)128作業(yè)29作業(yè)337采用FCFS算法，三個(gè)作業(yè)的周轉(zhuǎn)時(shí)間分別為：28、37和40，因此，平均作業(yè)周轉(zhuǎn)時(shí)間T=(28+37+40)/3=35若三個(gè)作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間約為29。若三個(gè)作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時(shí)間約為18。FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)提交的順序有關(guān)。82.最短作業(yè)優(yōu)先算法SJF（ShortestJobFirst）

(1)策略：最短作業(yè)優(yōu)先算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。這是一種非剝奪式調(diào)度算法。

(2)性能：算法易于實(shí)現(xiàn)，效率不高，弱點(diǎn)是需要預(yù)先知道作業(yè)所需的CPU時(shí)間，而這個(gè)時(shí)間只能靠估計(jì)，估計(jì)值很難精確，若估計(jì)過(guò)低，系統(tǒng)可能提前終止該作業(yè)；忽視了作業(yè)等待時(shí)間，會(huì)出現(xiàn)饑餓現(xiàn)象；由于缺少剝奪機(jī)制，對(duì)分時(shí)、實(shí)時(shí)處理很不理想。最短作業(yè)優(yōu)先算法SJF算法的調(diào)度時(shí)間：每一個(gè)作業(yè)完成時(shí)。9例如，四個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需CPU時(shí)間作業(yè)19作業(yè)24作業(yè)310作業(yè)48假設(shè)系統(tǒng)中沒(méi)有其他作業(yè)，現(xiàn)實(shí)施SJF調(diào)度算法，?SJF的作業(yè)調(diào)度順序?yàn)樽鳂I(yè)2、4、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間 T=(4+12+21+31)/4=17

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=(4/4+12/8+21/9+31/10)/4=1.98?如果對(duì)它們施行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時(shí)間T=(9+13+23+31)/4=19

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間

W=(9/9+13/4+23/10+31/8)/4=2.5110SJF的平均作業(yè)周轉(zhuǎn)時(shí)間比FCFS要小，故它的調(diào)度性能比FCFS好。缺陷：實(shí)現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運(yùn)行時(shí)間，否則調(diào)度就沒(méi)有依據(jù)，要精確知道一個(gè)作業(yè)的運(yùn)行時(shí)間是辦不到的。

3最短剩余時(shí)間優(yōu)先SRTF算法把SJF算法改為搶占式的調(diào)度算法：當(dāng)一個(gè)作業(yè)正在執(zhí)行時(shí)，一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來(lái)還需的CPU時(shí)間短，SRTF強(qiáng)行趕走當(dāng)前正在執(zhí)行作業(yè)，此算法不但適用于作業(yè)調(diào)度，同樣也適用于進(jìn)程調(diào)度。最短剩余時(shí)間優(yōu)先SRTF算法的調(diào)度時(shí)間：每一個(gè)新作業(yè)到來(lái)時(shí)11一個(gè)例子,假如四個(gè)就緒作業(yè)到達(dá)系統(tǒng)和所需CPU時(shí)間如下：作業(yè)名到達(dá)系統(tǒng)時(shí)間CPU時(shí)間(毫秒)Job108Job214Job329Job435J1J2J4

J1

J301510172612Job1從0開始執(zhí)行，就緒隊(duì)列僅一個(gè)作業(yè)。Job2在時(shí)間1到達(dá)，Job1剩余時(shí)間（7毫秒）大于JOB2所需時(shí)間（4毫秒），Job1被剝奪，Job2被調(diào)度執(zhí)行。平均等待時(shí)間是（（10-1）+（1-1）+（17-2）+（5-3））/4=26/4=6.5毫秒。采用非搶占式SJF調(diào)度，那么，平均等待時(shí)間是7.75毫秒。134.響應(yīng)比最高者優(yōu)先(HRRF)算法先來(lái)先服務(wù)算法FCFS與最短作業(yè)優(yōu)先SJF算都法是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時(shí)間而忽視了作業(yè)的計(jì)算時(shí)問(wèn)，SJF只考慮用戶估計(jì)的作業(yè)計(jì)算時(shí)間而忽視了作業(yè)等待時(shí)間。響應(yīng)比最高者優(yōu)先(HRRF)算法是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時(shí)間，又考慮作業(yè)的運(yùn)行時(shí)間，既照顧短作業(yè)又不使長(zhǎng)作業(yè)的等待時(shí)間過(guò)長(zhǎng)，改進(jìn)了調(diào)度性能。缺點(diǎn)是每次計(jì)算各道作業(yè)的響應(yīng)比會(huì)有一定的時(shí)間開銷，需要估計(jì)期待的服務(wù)時(shí)間，性能比SJF略差。響應(yīng)比定義：作業(yè)進(jìn)入系統(tǒng)后的等待時(shí)間與估計(jì)計(jì)算時(shí)間之和稱作該作業(yè)的響應(yīng)時(shí)間，作業(yè)的響應(yīng)時(shí)間除以作業(yè)估計(jì)計(jì)算時(shí)間稱作響應(yīng)比，即：響應(yīng)比＝1+已等待時(shí)間/估計(jì)運(yùn)行時(shí)間

14每當(dāng)調(diào)度一個(gè)作業(yè)運(yùn)行時(shí)，都要計(jì)算后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比，選擇響應(yīng)比最高者投入運(yùn)行。響應(yīng)比最高者優(yōu)先(HRRF)算法的效果：

?短作業(yè)容易得到較高響應(yīng)比，

?長(zhǎng)作業(yè)等待時(shí)間足夠長(zhǎng)后，也將獲得足夠高的響應(yīng)比，?饑餓現(xiàn)象不會(huì)發(fā)生。響應(yīng)比最高者優(yōu)先(HRRF)算法的調(diào)度時(shí)間：每一個(gè)新作業(yè)到來(lái)時(shí)15HRRF算法舉例例如，以下四個(gè)作業(yè)先后到達(dá)系統(tǒng)進(jìn)入調(diào)度：作業(yè)名到達(dá)時(shí)間所需CPU時(shí)間作業(yè)1020作業(yè)2515作業(yè)3105作業(yè)4151016SJF的作業(yè)調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，

平均作業(yè)周轉(zhuǎn)時(shí)間T=(20+25+35+50)/4=32.5

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間

W=(20/20+25/5+35/10+50/15)/4=3.2如果對(duì)它們施行FCFS調(diào)度算法，

平均作業(yè)周轉(zhuǎn)時(shí)間T=(20+35+40+50)/4=36.25

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間

W=(20/20+35/15+40/5+50/10)/4=4.117對(duì)作業(yè)流執(zhí)行HRRF調(diào)度算法開始只有作業(yè)1，被選中執(zhí)行時(shí)間20；作業(yè)1執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)3被選中，執(zhí)行時(shí)間5；作業(yè)3執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)2被選中，執(zhí)行時(shí)間15；作業(yè)2執(zhí)行完畢，作業(yè)4被選中，執(zhí)行時(shí)間10；平均作業(yè)周轉(zhuǎn)時(shí)間T=(20+25+40+50)/4=33.75平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=(20/20+25/5+40/15+50/10)/4=3.4185.優(yōu)先級(jí)調(diào)度算法這種算法是根據(jù)確定的優(yōu)先級(jí)來(lái)選取進(jìn)程/線程，每次總是選擇優(yōu)先級(jí)最高的作業(yè)?？梢圆扇儕Z與非剝奪兩種形式：剝奪式：后到來(lái)的優(yōu)先級(jí)高的進(jìn)程強(qiáng)迫正在運(yùn)行的低優(yōu)先級(jí)進(jìn)程暫停；非剝奪式：同時(shí)到來(lái)的進(jìn)程中選擇高優(yōu)先級(jí)的進(jìn)程先運(yùn)行，但是后到來(lái)的高優(yōu)先級(jí)進(jìn)程只能等當(dāng)前正在運(yùn)行的低優(yōu)先級(jí)進(jìn)程結(jié)束或者主動(dòng)出讓處理器。規(guī)定用戶進(jìn)程優(yōu)先級(jí)的方法：一種是由用戶自己提出進(jìn)程的優(yōu)先級(jí)。另一種是由系統(tǒng)綜合考慮有關(guān)因素來(lái)確定用戶進(jìn)程的優(yōu)先級(jí)。19?進(jìn)程/線程優(yōu)先級(jí)的確定有兩種方式：靜態(tài)：在創(chuàng)建進(jìn)程/線程時(shí)即確定，在整個(gè)生命周期里不改變；動(dòng)態(tài)：進(jìn)程/線程的優(yōu)先級(jí)隨時(shí)間而改變；?另一種是由系統(tǒng)綜合考慮有關(guān)因素來(lái)確定用戶進(jìn)程的優(yōu)先數(shù)。206.輪轉(zhuǎn)調(diào)度算法（時(shí)間片調(diào)度）?每次把CPU分配給就緒隊(duì)列首進(jìn)程（線程）使用規(guī)定的時(shí)間間隔（時(shí)間片），就緒隊(duì)列中的每一個(gè)進(jìn)程（線程）輪流運(yùn)行一個(gè)時(shí)間片，當(dāng)時(shí)間片耗盡，就強(qiáng)迫當(dāng)前進(jìn)程（線程）讓出CPU，轉(zhuǎn)到就緒隊(duì)列隊(duì)尾，等待下一輪調(diào)度。?需要使用間隔時(shí)鐘。能夠防止那些很少使用設(shè)備的進(jìn)程（線程）長(zhǎng)時(shí)間占用處理器，導(dǎo)致要使用設(shè)備的那些進(jìn)程（線程）沒(méi)有機(jī)會(huì)啟動(dòng)設(shè)備。輪轉(zhuǎn)調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費(fèi)在進(jìn)程（線程）切換上的開銷比較大，這個(gè)開銷與時(shí)間片的大小有關(guān)。時(shí)間片的選?。簳r(shí)間片太小，導(dǎo)致進(jìn)程頻繁切換，開銷顯著增大，因此，從系統(tǒng)效率看，時(shí)間片應(yīng)該大一些；時(shí)間片太大，隨著進(jìn)程數(shù)目增加，每個(gè)進(jìn)程輪轉(zhuǎn)一次所耗費(fèi)的時(shí)間加長(zhǎng)，導(dǎo)致每個(gè)進(jìn)程（線程）的相應(yīng)速度放慢，因此，從響應(yīng)時(shí)間看，時(shí)間片應(yīng)該小一些。21為了滿足用戶對(duì)響應(yīng)事件的要求，要么限制就緒隊(duì)列中進(jìn)程（線程）數(shù)量，要么采用動(dòng)態(tài)的時(shí)間片長(zhǎng)度，根據(jù)當(dāng)前負(fù)載狀況，及時(shí)調(diào)整時(shí)間片大小。綜合起來(lái)，確定時(shí)間片的長(zhǎng)度要從進(jìn)程數(shù)目、切換開銷、系統(tǒng)效率和響應(yīng)時(shí)間等多個(gè)方面加以考慮。

227.多級(jí)反饋隊(duì)列調(diào)度（反饋循環(huán)隊(duì)列或多隊(duì)列策略）

Multi-levelFeedbackQueue,MLFQ(1)主要思想：是將就緒進(jìn)程分為兩級(jí)或多級(jí)，系統(tǒng)相應(yīng)建立兩個(gè)或多個(gè)就緒進(jìn)程隊(duì)列，較高優(yōu)先級(jí)的隊(duì)列一般分配給較短的時(shí)間片。處理器調(diào)度每次先從高級(jí)就緒進(jìn)程隊(duì)列中選取可占有處理器的進(jìn)程，只有在選不到時(shí)，才從較低級(jí)的就緒進(jìn)程隊(duì)列中選取。同一隊(duì)列中的進(jìn)程按先來(lái)先服務(wù)原則排隊(duì)。開始工作時(shí)，每當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先進(jìn)入高優(yōu)先級(jí)隊(duì)列等候調(diào)度，若能在該級(jí)隊(duì)列的一個(gè)時(shí)間片內(nèi)執(zhí)行完成，則撤離系統(tǒng)，否則進(jìn)入低一級(jí)的隊(duì)列等候調(diào)度，對(duì)列級(jí)別越低，時(shí)間片就越大，低優(yōu)先級(jí)隊(duì)列中的進(jìn)程獲得調(diào)度時(shí)運(yùn)行的時(shí)間就長(zhǎng)一些。(2)效果：性能較好，能滿足各類用戶的需要。23對(duì)分時(shí)交互式作業(yè)：通?？稍谧罡邇?yōu)先級(jí)隊(duì)列規(guī)定的一個(gè)時(shí)間片內(nèi)完成，響應(yīng)時(shí)間快。對(duì)于短的批處理作業(yè)，通常只需要在第一隊(duì)列和第二隊(duì)列中各執(zhí)行一個(gè)時(shí)間片就能完成，周轉(zhuǎn)時(shí)間仍然很短。對(duì)于長(zhǎng)批處理型作業(yè)：可以從高到低在各優(yōu)先級(jí)隊(duì)列中運(yùn)行一個(gè)時(shí)間片直到在某個(gè)級(jí)別隊(duì)列中執(zhí)行完畢或者在最后一個(gè)隊(duì)列中經(jīng)過(guò)若干個(gè)時(shí)間片執(zhí)行完畢.MLFQ調(diào)度算法會(huì)導(dǎo)致饑餓問(wèn)題：例如一個(gè)長(zhǎng)作業(yè)進(jìn)入系統(tǒng)，它最終必將進(jìn)入優(yōu)先級(jí)最低的就緒隊(duì)列，如果不斷有新的短作業(yè)進(jìn)入系統(tǒng)，且形成穩(wěn)定的作業(yè)流，則長(zhǎng)作業(yè)只能永遠(yuǎn)等待。解決的辦法是：對(duì)于在低優(yōu)先級(jí)隊(duì)列中等待時(shí)間足夠長(zhǎng)的進(jìn)程提高優(yōu)先級(jí)，從而讓它獲得運(yùn)行機(jī)會(huì)。248彩票調(diào)度算法：基本思想：為進(jìn)程發(fā)放針對(duì)系統(tǒng)各種資源（包括CPU時(shí)間）的彩票，當(dāng)調(diào)度程序需要決策時(shí)，隨機(jī)選擇一張彩票，則持有該彩票的進(jìn)程將獲得資源。進(jìn)程獲取資源（運(yùn)行時(shí)間）的概率與彩票的數(shù)量成正比。彩票算法的特點(diǎn)：彩票調(diào)度算法的反應(yīng)非常迅速。進(jìn)程之間可以交換彩票。彩票算法可以解決其它算法很難保證解決的問(wèn)題。252.8.3實(shí)時(shí)調(diào)度1.實(shí)時(shí)操作系統(tǒng)的特性(1)特性?實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。?實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒng)、自動(dòng)駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒(méi)有響應(yīng)一樣糟糕。(2)實(shí)時(shí)系統(tǒng)分類通常分為硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)：實(shí)時(shí)系統(tǒng)通常分為硬實(shí)時(shí)（hardrealtime）系統(tǒng)和軟實(shí)時(shí)（softrealtime）系統(tǒng)。前者意味著存在必須滿足的時(shí)間限制；后者意味著偶爾超過(guò)時(shí)間限制時(shí)可以容忍的。(3)實(shí)時(shí)系統(tǒng)要響應(yīng)的事件分類：分為周期性（每隔一段固定的時(shí)間發(fā)生）和非周期性事件（在不可預(yù)測(cè)的時(shí)間發(fā)生）。26(4)實(shí)時(shí)任務(wù)的可調(diào)度性假如有m個(gè)周期性事件，事件i的周期為Pi，每個(gè)事件需要Ci秒的CPU時(shí)間來(lái)處理，則只有滿足以下條件：C1/P1+C2/P2+…+Cm/Pm≤1時(shí)，才可能處理所有的負(fù)載。滿足該條件的實(shí)時(shí)系統(tǒng)稱作任務(wù)可調(diào)度的（schedulable）。例如，一個(gè)軟實(shí)時(shí)系統(tǒng)處理三個(gè)事件流，其周期分別為100ms，200ms和500ms，如果事件處理時(shí)間分別為50ms，30ms和100ms，則這個(gè)系統(tǒng)是可調(diào)度的，因?yàn)?0/100+30/200+100/500=0.5+0.15+0.2=0.85≤127如果加入周期為1秒的第4個(gè)事件，則其處理時(shí)間不能超過(guò)a：50/100+30/200+100/500+a/1000=1a=150ms，否則該系統(tǒng)將不可調(diào)度。盡管在理論上采取了下面將要討論的實(shí)時(shí)調(diào)度算法后就可將通用操作系統(tǒng)改造成實(shí)時(shí)操作系統(tǒng)，但實(shí)際上，通用操作系統(tǒng)的進(jìn)程切換開銷太大，以至于只能滿足那些限制較松的實(shí)時(shí)應(yīng)用。因此多數(shù)實(shí)時(shí)系統(tǒng)都使用專用的實(shí)時(shí)操作系統(tǒng)，這些系統(tǒng)一般規(guī)模小、進(jìn)程切換快、中斷屏蔽和處理時(shí)間短。

282.實(shí)時(shí)調(diào)度算法(1)單比率調(diào)度算法

基本思想：為每個(gè)進(jìn)程分配一個(gè)與事件發(fā)生頻率成正比的優(yōu)先數(shù)。例如，周期為20ms的進(jìn)程優(yōu)先數(shù)為50，周期為100ms的進(jìn)程優(yōu)先數(shù)為10，運(yùn)行時(shí)調(diào)度程序總是調(diào)度優(yōu)先數(shù)最高的就緒進(jìn)程，并采取搶占式分配策略。(2)限期調(diào)度算法基本思想：當(dāng)一個(gè)事件發(fā)生時(shí)，對(duì)應(yīng)的進(jìn)程就按照截止期限被加入就緒進(jìn)程隊(duì)列。對(duì)于一個(gè)周期性事件，其截止期限即為事件下一次發(fā)生的時(shí)間。該調(diào)度算法首先運(yùn)行隊(duì)首進(jìn)程，即截止時(shí)間最近的那個(gè)進(jìn)程。29(3)最少裕度法基本思想：首先計(jì)算各個(gè)進(jìn)程的富裕時(shí)間，即裕度（laxity），然后選擇裕度最少的進(jìn)程執(zhí)行。裕度=截止時(shí)間-(就緒時(shí)間+計(jì)算時(shí)間)302.8.4多處理器調(diào)度現(xiàn)代操作系統(tǒng)往往采用進(jìn)程調(diào)度與線程調(diào)度相結(jié)合的方式來(lái)完成多處理器調(diào)度。1.多處理器調(diào)度的設(shè)計(jì)要點(diǎn)（有三點(diǎn)）

?設(shè)計(jì)要點(diǎn)之一是如何把處理器分配給進(jìn)程：假定在多處理器系統(tǒng)中所有的處理器都相同，則可采用兩種策略分配處理器：靜態(tài)分配策略：把一個(gè)進(jìn)程永久地分配給一個(gè)處理器，分配在創(chuàng)建時(shí)執(zhí)行，每個(gè)處理器對(duì)應(yīng)一個(gè)低級(jí)調(diào)度隊(duì)列。動(dòng)態(tài)分配策略：所有處理器共用一個(gè)就緒隊(duì)列。當(dāng)一個(gè)處理器空閑時(shí)，就選擇一個(gè)就緒進(jìn)程占有該處理器運(yùn)行，一個(gè)進(jìn)程可以在任意時(shí)間在任意處理器上運(yùn)行。31操作系統(tǒng)在多處理機(jī)系統(tǒng)中是怎樣分布呢？方法之一是采用主從式管理結(jié)構(gòu)，操作系統(tǒng)的核心部分運(yùn)行在一個(gè)特殊的處理器上，其他處理器運(yùn)行用戶程序。當(dāng)用戶程序需要請(qǐng)求操作系統(tǒng)服務(wù)時(shí)，請(qǐng)求將被傳送到主處理器上的操作系統(tǒng)。這種實(shí)現(xiàn)方式的缺點(diǎn)是（1）整個(gè)系統(tǒng)的堅(jiān)定性與主處理器上運(yùn)行的操作系統(tǒng)關(guān)系過(guò)大；（2）主處理器極易成為系統(tǒng)的瓶頸。方法之二是采用分布式管理結(jié)構(gòu)，操作系統(tǒng)可以在所有處理器上運(yùn)行，每個(gè)處理器也可以自我調(diào)度。還可以把操作系統(tǒng)內(nèi)核分成幾部分，分別放在不同處理器上運(yùn)行。?設(shè)計(jì)要點(diǎn)之二是否要在單個(gè)處理器上支持多道程序設(shè)計(jì)。，答案不明朗。?設(shè)計(jì)要點(diǎn)之三是實(shí)際指派進(jìn)程的方法。323.多處理器的調(diào)度算法

?實(shí)驗(yàn)證明，隨著處理器數(shù)目的增多，復(fù)雜低級(jí)調(diào)度算法的有效性逐步下降。?多數(shù)采取動(dòng)態(tài)分配策略的多處理器系統(tǒng)中，低級(jí)調(diào)度算法往往采用最簡(jiǎn)單的FCFS或優(yōu)先數(shù)算法。就緒進(jìn)程組成一個(gè)隊(duì)列或多個(gè)按照優(yōu)先數(shù)排列的隊(duì)列。?多處理器調(diào)度的主要研究對(duì)象是線程調(diào)度算法。?盡管線程也給單處理器系統(tǒng)帶來(lái)很大益處，但在多處理器環(huán)境中線程的作用才真正得到充分發(fā)揮。33多處理器環(huán)境中線程調(diào)度的幾種算法：1）負(fù)載共享調(diào)度算法?基本思想：進(jìn)程并不分配給一個(gè)特定處理器，系統(tǒng)維護(hù)一個(gè)全局性就緒線程隊(duì)列，當(dāng)一個(gè)處理器空閑時(shí)，就選擇一個(gè)就緒線程占有處理器運(yùn)行。

負(fù)載共享調(diào)度算法優(yōu)點(diǎn)：?把負(fù)載均分到所有可用處理器上，保證了處理器效率的提高。?不需要一個(gè)集中的調(diào)度程序，一旦一個(gè)處理器空閑，調(diào)度程序就可以運(yùn)行在該處理器上以選擇下一個(gè)運(yùn)行的線程。?運(yùn)行線程的選擇可以采用