第3章 處理機(jī)調(diào)度與死鎖(1-2)

第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除作業(yè)的狀態(tài)及其轉(zhuǎn)換批處理系統(tǒng)才有作業(yè)的概念，分時(shí)系統(tǒng)沒有作業(yè)的概念；作業(yè)的狀態(tài)分為：提交、后備、運(yùn)行和完成；提交狀態(tài)：作業(yè)再輸入設(shè)備上并準(zhǔn)備進(jìn)入外存輸入井前的狀態(tài)。用戶作業(yè)通常包括：程序、數(shù)據(jù)和作業(yè)說明書后備狀態(tài)：由SPOOLing輸入程序輸入到外存輸入井中，為其建立作業(yè)控制塊（JCB），并將JCB插入到后備作業(yè)隊(duì)列中的狀態(tài)運(yùn)行狀態(tài)：作業(yè)被作業(yè)調(diào)度程序選中，由外存輸入井調(diào)入到內(nèi)存，為其分配了所需的資源并建立了進(jìn)程，此時(shí)作業(yè)就進(jìn)入到運(yùn)行狀態(tài)。完成狀態(tài)：當(dāng)作業(yè)正常結(jié)束或異常終止時(shí)，就進(jìn)入完成狀態(tài)。由作業(yè)調(diào)度程序做收尾工作：撤銷JCB、回收分給該作業(yè)的系統(tǒng)資源等。3.1處理機(jī)調(diào)度的基本概念作業(yè)的狀態(tài)及其轉(zhuǎn)換提交后備運(yùn)行就緒阻塞就緒阻塞完成SPOOLing程序作業(yè)調(diào)度程序進(jìn)程調(diào)度程序中級(jí)調(diào)度外存外存輸入井輸入設(shè)備內(nèi)存在多道批處理系統(tǒng)中，一個(gè)作業(yè)從提交到后備作業(yè)隊(duì)列，再調(diào)入內(nèi)從經(jīng)運(yùn)行到完成，可能需要經(jīng)歷三級(jí)調(diào)度：1.高級(jí)調(diào)度（HighScheduling)

高級(jí)調(diào)度又稱為作業(yè)調(diào)度或宏觀調(diào)度或長(zhǎng)程調(diào)度，其主要功能是根據(jù)一定的算法，從后備作業(yè)隊(duì)列（一批作業(yè)）中選出若干個(gè)作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程和分配必要的資源，然后將創(chuàng)建的新進(jìn)程放入進(jìn)程就緒隊(duì)列中，使其處于就緒狀態(tài)。當(dāng)作業(yè)運(yùn)行結(jié)束時(shí)，還要做一些善后工作（資源回收）3.1.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度特點(diǎn)：1）多道批處理系統(tǒng)需要作業(yè)調(diào)度；分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)一般不需要高級(jí)調(diào)度。2）每次調(diào)度多少作業(yè)（程序）？需由系統(tǒng)規(guī)定的多道程序度而定；3）調(diào)度那些作業(yè)？由調(diào)度算法（策略）而定，如先來先服務(wù)，短作業(yè)優(yōu)先調(diào)度，優(yōu)先權(quán)調(diào)度算法等。2.中級(jí)調(diào)度(Intermediate-LevelScheduling)中級(jí)調(diào)度又稱之為中程調(diào)度(Medium-TermScheduling)，中級(jí)調(diào)度主要任務(wù)是實(shí)施進(jìn)程在內(nèi)、外存間的交換；中級(jí)調(diào)度的主要功能是在內(nèi)存使用緊張時(shí)，將一些暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存對(duì)換到外存上等待（此時(shí)的進(jìn)程狀態(tài)稱為掛起狀態(tài)或駐留外存狀態(tài)）。以后，當(dāng)外存有足夠的空閑空間時(shí)，再將合適的進(jìn)程重新?lián)Q入內(nèi)存，等待進(jìn)程調(diào)度。引入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。

3.低級(jí)調(diào)度(LowLevelScheduling)低級(jí)調(diào)度又稱進(jìn)程調(diào)度或微觀調(diào)度或短程調(diào)度，其主要功能是根據(jù)一定的算法，將CPU分派給就緒進(jìn)程隊(duì)列中的某一進(jìn)程。執(zhí)行低級(jí)調(diào)度功能的程序稱為進(jìn)程調(diào)度程序，由它實(shí)現(xiàn)CPU在進(jìn)程間的切換。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，在一般操作系統(tǒng)（包括：多道批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)）中都必須有進(jìn)程調(diào)度，而且它的策略的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。4、進(jìn)程調(diào)度方式

非搶占方式（Nonpreemptive）：在這種調(diào)度方式下，一旦一個(gè)進(jìn)程被選中運(yùn)行，它就一直運(yùn)行下去，直到它運(yùn)行結(jié)束并自愿放棄CPU，或者因等待某一事件而被阻塞或終止時(shí)為止，才把CPU出讓給其他進(jìn)程，即得到CPU的進(jìn)程不管運(yùn)行多長(zhǎng)時(shí)間，都一直運(yùn)行下去，不會(huì)因?yàn)楫?dāng)前進(jìn)程以外的原因而被迫讓出CPU。引起調(diào)度的原因：1）當(dāng)前進(jìn)程運(yùn)行結(jié)束或發(fā)生某事件而終止；2）當(dāng)前進(jìn)程因提出I/O請(qǐng)求而阻塞；3）進(jìn)程之間通信或同步而由于執(zhí)行原語(yǔ)而等待。搶占方式（Preemptive）：搶占方式允許調(diào)度程序根據(jù)某種策略中止當(dāng)前進(jìn)程的執(zhí)行，將其移入就緒隊(duì)列，并將處理機(jī)分派給另一個(gè)進(jìn)程使之投入運(yùn)行。

搶占原則：1）優(yōu)先權(quán)原則：允許高優(yōu)先權(quán)進(jìn)程搶占低優(yōu)先權(quán)的CPU；2）短作業(yè)原則：允許短進(jìn)程搶占長(zhǎng)進(jìn)程的處理機(jī)；3）時(shí)間片原則：分時(shí)系統(tǒng)中的當(dāng)前進(jìn)程，若時(shí)間片規(guī)定的時(shí)間用完，不管是否運(yùn)行結(jié)束，都要立即中止放到就緒隊(duì)列中，再將CPU分派給其它進(jìn)程。3.1.2調(diào)度隊(duì)列模型 不同OS對(duì)高級(jí)、中級(jí)和低級(jí)調(diào)度的選取形成了不同的調(diào)度隊(duì)列模型，共有3種類型。1、僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

常在分時(shí)系統(tǒng)中設(shè)置僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型。終端用戶的登錄注冊(cè)以及交互命令的輸入執(zhí)行，系統(tǒng)都將為其建立進(jìn)程，并放在FIFO就緒隊(duì)列中，按照時(shí)間片輪轉(zhuǎn)調(diào)度執(zhí)行。進(jìn)程的調(diào)度和變化過程如下圖所示。圖3-1僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型P1P2P42.具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還需要作業(yè)調(diào)度。若OS中僅包含高級(jí)調(diào)度和低級(jí)調(diào)度就形成了具有高級(jí)和低級(jí)調(diào)度的隊(duì)列模型。進(jìn)程調(diào)度常以最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，就緒隊(duì)列形式為優(yōu)先權(quán)隊(duì)列。阻塞隊(duì)列按照不同事件排隊(duì)就緒隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時(shí)間片完等待事件2事件2出現(xiàn)……等待事件n事件n出現(xiàn)后備隊(duì)列……3.同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型作業(yè)CPU就緒掛起隊(duì)列阻塞掛起隊(duì)列阻塞隊(duì)列就緒隊(duì)列時(shí)間片到進(jìn)程調(diào)度作業(yè)調(diào)度調(diào)入中級(jí)調(diào)度事件出現(xiàn)交互式用戶等待事件進(jìn)程完成掛起調(diào)出掛起調(diào)出事件出現(xiàn)

具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短：周轉(zhuǎn)周期是指作業(yè)從提交給系統(tǒng)開始，到作業(yè)完成為止所消耗的時(shí)間。常用于衡量系統(tǒng)性能、作業(yè)調(diào)度算法的優(yōu)劣的重要指標(biāo)?？砂哑骄苻D(zhuǎn)時(shí)間描述為：作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:響應(yīng)時(shí)間快：分時(shí)系統(tǒng)性能的主要評(píng)價(jià)指標(biāo)。響應(yīng)時(shí)間指用戶從鍵盤鍵入一個(gè)命令開始，到系統(tǒng)首次給出響應(yīng)信息為止這段時(shí)間。截止時(shí)間的保證：評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)。截止時(shí)間是指系統(tǒng)為處理某事件/任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。優(yōu)先權(quán)準(zhǔn)則：批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中的調(diào)度算法都應(yīng)該遵循的原則。這種調(diào)度思想就是“急事急辦”，優(yōu)先權(quán)高者為急。2.面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高：評(píng)價(jià)批處理系統(tǒng)整體性能的重要指標(biāo)。吞吐量是指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。作業(yè)調(diào)度算法對(duì)系統(tǒng)吞吐量有直接影響，選擇確定時(shí)應(yīng)考慮這一準(zhǔn)則。處理機(jī)利用率好：CPU的利用率是衡量大中型系統(tǒng)性能的重要指標(biāo)。各類資源的平衡利用：選擇適當(dāng)調(diào)度算法，保證各種資源的利用都處于忙碌狀態(tài)。3.2調(diào)度算法1、先來先服務(wù)（FCFS）調(diào)度算法適應(yīng)范圍：適應(yīng)作業(yè)調(diào)度和進(jìn)程調(diào)度；調(diào)度過程：FCFS用于作業(yè)（進(jìn)程）調(diào)度時(shí)，從后備（就緒）隊(duì)列中選擇若干或一個(gè)先到來的作業(yè)（進(jìn)程）投入運(yùn)行。進(jìn)程在分派到CPU進(jìn)入運(yùn)行過程中，只有當(dāng)進(jìn)程運(yùn)行結(jié)束或因某事件發(fā)生而被阻塞才放棄CPU。算法特點(diǎn)：算法容易實(shí)現(xiàn)，但效率不高；只顧及作業(yè)等候時(shí)間，沒考慮作業(yè)要求服務(wù)時(shí)間的長(zhǎng)短，不利于短作業(yè)而優(yōu)待了長(zhǎng)作業(yè)；作業(yè)調(diào)度不分輕重緩急，人人平等；FCFS為非搶占式調(diào)度。先來先服務(wù)（FCFS）調(diào)度算法效率舉例表注：周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間；帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間2、短作業(yè)/進(jìn)程（SJF/SPF）優(yōu)先調(diào)度算法適應(yīng)范圍：適應(yīng)作業(yè)調(diào)度和進(jìn)程調(diào)度。SJF/SPF算法以進(jìn)入系統(tǒng)的作業(yè)/進(jìn)程所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的作業(yè)/進(jìn)程投入運(yùn)行。算法特點(diǎn)：算法易于實(shí)現(xiàn)，效率不高；忽視長(zhǎng)作業(yè)等待時(shí)間，會(huì)出現(xiàn)饑餓現(xiàn)象；不考慮緊迫作業(yè)/進(jìn)程的需求；長(zhǎng)短時(shí)間人為估計(jì)，不可靠，會(huì)出現(xiàn)以長(zhǎng)亂短。SPF算法類型：搶占或非搶占式。搶占式SPF調(diào)度算法在新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，將其運(yùn)行時(shí)間與當(dāng)前進(jìn)程的剩余運(yùn)行時(shí)間相比，若更短時(shí)，可搶占CPU；非搶占式SPF算法允許當(dāng)前運(yùn)行進(jìn)程先執(zhí)行直到釋放CPU為止?？蓳屨糞PF調(diào)度有時(shí)稱為最短剩余時(shí)間優(yōu)先（shortest-remaining-time-first）調(diào)度。

FCFS和SJF調(diào)度算法的性能分析

例題：假如5個(gè)就緒進(jìn)程其到達(dá)系統(tǒng)和所需CPU時(shí)間如下表所示（單位：毫秒），如果忽略I/O以及其他開銷，分別計(jì)算采用FCFS、非搶占式SPF和搶占式SPF調(diào)度算法進(jìn)行CPU調(diào)度的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)和運(yùn)行時(shí)間進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間A03B26C44D65E82解答如下：（1）采用FCFS的調(diào)度順序?yàn)椋篈BCDE039131820平均周轉(zhuǎn)時(shí)間為：

T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6帶權(quán)平均周轉(zhuǎn)時(shí)間為：W=2.56（2）采用非搶占SJF的調(diào)度順序?yàn)椋篈BECD039111520平均周轉(zhuǎn)時(shí)間為：T=7.6帶權(quán)平均周轉(zhuǎn)時(shí)間為：W=1.84（3）采用搶占SJF的調(diào)度順序?yàn)椋浩骄苻D(zhuǎn)時(shí)間為：T=7.2帶權(quán)平均周轉(zhuǎn)時(shí)間為：W=1.59AB1ECB2038101520D43、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（priority-schedulingalgorithm）

1）優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法：在此方式下，系統(tǒng)一旦把CPU分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給就緒隊(duì)列中另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。搶占式優(yōu)先權(quán)算法：在此方式下，系統(tǒng)把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程使之執(zhí)行。但在其執(zhí)行期間，只要又有更高優(yōu)先權(quán)新進(jìn)程進(jìn)入就緒隊(duì)列，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。適應(yīng)較嚴(yán)格的實(shí)時(shí)系統(tǒng)、性能要求較高的批處理和分時(shí)系統(tǒng)。2）優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0~9中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。

優(yōu)先權(quán)的確定準(zhǔn)則：系統(tǒng)進(jìn)程者優(yōu)先；資源需求少者優(yōu)先；用戶需求緊迫者優(yōu)先。動(dòng)態(tài)優(yōu)先權(quán)：動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變的，以便獲得更好的調(diào)度性能。（如等待時(shí)間與優(yōu)先權(quán)成正比）4、高響應(yīng)比優(yōu)先調(diào)度算法動(dòng)態(tài)優(yōu)先權(quán)的變化規(guī)律可描述為：系統(tǒng)對(duì)作業(yè)的響應(yīng)時(shí)間=等待時(shí)間+服務(wù)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，優(yōu)先權(quán)變化規(guī)律又可表示為：高響應(yīng)比優(yōu)先調(diào)度算法特點(diǎn)：如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)；當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)；對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)，避免了長(zhǎng)作業(yè)饑餓現(xiàn)象。5、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

時(shí)間片調(diào)度算法適用于分時(shí)系統(tǒng)。劃分為時(shí)間片輪轉(zhuǎn)和多級(jí)反饋隊(duì)列調(diào)度算法1）時(shí)間片輪轉(zhuǎn)法輪轉(zhuǎn)法調(diào)度做法是：系統(tǒng)將所有的就緒進(jìn)程按FIFO原則排隊(duì)，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片（如20ms）。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。如此反復(fù)和輪轉(zhuǎn)，就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。FCBA

….CPUA

BC時(shí)間片輪轉(zhuǎn)算法圖示完成2）多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法是目前公認(rèn)的一種性能比較優(yōu)良的調(diào)度算法，兼?zhèn)淞饲笆龈鞣N算法的優(yōu)點(diǎn)。原理如下：設(shè)置多個(gè)就緒隊(duì)列，并賦予不同的優(yōu)先級(jí)和時(shí)間片：第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。圖3-5是多級(jí)反饋隊(duì)列算法的示意。多級(jí)反饋隊(duì)列調(diào)度算法新進(jìn)程進(jìn)入（64ms）調(diào)度原則：當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。搶占原則：僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?~i隊(duì)列均空時(shí)，才會(huì)調(diào)度第i+1隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1~(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。多級(jí)反饋隊(duì)列調(diào)度算法的性能與特點(diǎn)終端型作業(yè)用戶：短小作業(yè)及時(shí)完成，用戶滿意。(2)短批處理作業(yè)用戶：短作業(yè)優(yōu)先運(yùn)行結(jié)束。(3)長(zhǎng)批處理作業(yè)用戶：不出現(xiàn)饑餓現(xiàn)象。作業(yè)3-1P101：1、4、6、73.3實(shí)時(shí)調(diào)度3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件為了實(shí)現(xiàn)對(duì)實(shí)時(shí)進(jìn)程進(jìn)行有效調(diào)度，系統(tǒng)必須滿足下述條件：1.提供必要的信息就緒時(shí)間：進(jìn)程進(jìn)入就緒狀態(tài)的開始時(shí)間，有周期性和非周期性開始截止時(shí)間和完成截止時(shí)間：開始處理或完成任務(wù)的最遲時(shí)間處理時(shí)間：指一個(gè)進(jìn)程從開始執(zhí)行到完成需要的處理時(shí)間；資源要求：指處理一個(gè)任務(wù)時(shí)所需要的資源；優(yōu)先級(jí)：用于標(biāo)識(shí)一個(gè)任務(wù)得到處理的輕重緩急。實(shí)時(shí)調(diào)度：在實(shí)時(shí)操作系統(tǒng)中，實(shí)現(xiàn)實(shí)時(shí)進(jìn)程或任務(wù)的調(diào)度。實(shí)時(shí)調(diào)度強(qiáng)調(diào)對(duì)實(shí)時(shí)進(jìn)程或任務(wù)處理（響應(yīng)）的及時(shí)性和緊迫性。2.系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，通常都有多個(gè)實(shí)時(shí)任務(wù)（進(jìn)程）等待計(jì)算機(jī)及時(shí)處理。處理機(jī)能力必須滿足：假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間分別Ci，周期時(shí)間分別為Pi，則在單處理機(jī)情況下，其處理能力必須滿足條件：處理機(jī)滿足此條件時(shí)，才是可調(diào)度的；否則，調(diào)度不過來。多處理機(jī)情況下，需要滿足條件為：（N為處理機(jī)個(gè)數(shù)）3、采用搶占式調(diào)度機(jī)制當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)停止，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。4、具有快速切換機(jī)制對(duì)外部中斷的快速響應(yīng)能力：外部任務(wù)來到時(shí)能快速響應(yīng)；快速的任務(wù)分派能力：在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。3.3.2實(shí)時(shí)調(diào)度算法的分類1.非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法：控制多個(gè)相同對(duì)象；每對(duì)象一個(gè)實(shí)時(shí)進(jìn)程；建立一個(gè)FIFO進(jìn)程就緒隊(duì)列，按照FCFS輪轉(zhuǎn)調(diào)度。調(diào)度性能：實(shí)現(xiàn)數(shù)秒至數(shù)十秒響應(yīng)時(shí)間，適應(yīng)不嚴(yán)格的實(shí)時(shí)控制。非搶占式優(yōu)先調(diào)度算法：就緒隊(duì)列按優(yōu)先級(jí)進(jìn)隊(duì)排序，調(diào)度始終先調(diào)度隊(duì)首進(jìn)程。調(diào)度性能：可能獲得數(shù)秒至數(shù)百毫秒的響應(yīng)時(shí)間，適應(yīng)有一定要求的實(shí)時(shí)控制系統(tǒng)實(shí)時(shí)調(diào)度算法的分類方式較多：如按照任務(wù)性質(zhì)分為硬實(shí)時(shí)調(diào)度和軟實(shí)時(shí)調(diào)度；按照調(diào)度方式分為搶占方式和非搶占方式調(diào)度等2.搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法：如果有比當(dāng)前進(jìn)程優(yōu)先級(jí)更高的進(jìn)程到來，需等到時(shí)鐘中斷到來時(shí)搶占CPU。調(diào)度性能：響應(yīng)達(dá)到幾十毫秒至幾毫秒，適應(yīng)大多數(shù)控制系統(tǒng)。立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法：如果有比當(dāng)前進(jìn)程優(yōu)先級(jí)更高的進(jìn)程到來，若當(dāng)前進(jìn)程不處在臨界區(qū)，則立即搶占CPU。調(diào)度性能：調(diào)度延遲為幾毫秒至100微秒。非搶占實(shí)時(shí)進(jìn)程調(diào)度示意圖(a)非搶占輪轉(zhuǎn)調(diào)度調(diào)度時(shí)間進(jìn)程

1進(jìn)程

2實(shí)時(shí)進(jìn)程要求調(diào)度進(jìn)程

n實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行(b)非搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間搶占實(shí)時(shí)進(jìn)程調(diào)度示意圖當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度實(shí)時(shí)進(jìn)程槍占當(dāng)前進(jìn)程，并立即執(zhí)行(d)立即搶占的優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程