操作系統(tǒng),處理機(jī)調(diào)度與死鎖教案

Page12023/2/6第三章處理機(jī)調(diào)度與死鎖操作系統(tǒng)Page22023/2/6第三章處理機(jī)調(diào)度與死鎖重點(diǎn)掌握進(jìn)程調(diào)度算法，各適用于何種情況

理解常用的幾種實(shí)時(shí)調(diào)度算法

理解產(chǎn)生死鎖的原因

掌握銀行家算法避免死鎖難點(diǎn)多道程序設(shè)計(jì)中的各種調(diào)度算法

響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過(guò)程

銀行家算法

Page32023/2/6第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)處理機(jī)調(diào)度及調(diào)度算法多處理機(jī)環(huán)境下的進(jìn)程（線(xiàn)程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測(cè)與解除銀行家算法Page42023/2/6第三章處理機(jī)調(diào)度與死鎖處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源在多道程序環(huán)境下，進(jìn)程數(shù)目通常多于處理機(jī)的數(shù)目系統(tǒng)必須按一定方法動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程處理機(jī)利用率和系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間）在很大程度上取決于處理機(jī)調(diào)度分配處理機(jī)的任務(wù)是由處理機(jī)調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。WHAT：按什么原則分配CPU—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU—進(jìn)程調(diào)度的時(shí)機(jī)

HOW：如何分配CPU—CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）Page52023/2/6第三章處理機(jī)調(diào)度與死鎖

處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)作業(yè)與作業(yè)調(diào)度進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測(cè)與解除Page62023/2/6處理機(jī)調(diào)度的基本概念作業(yè)是用戶(hù)在一次解題或一個(gè)事務(wù)處理過(guò)程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合，包括用戶(hù)程序、所需的數(shù)據(jù)及命令等作業(yè)的狀態(tài)：一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè)階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)后備狀態(tài)運(yùn)行狀態(tài)完成狀態(tài)Page72023/2/6運(yùn)行狀態(tài)處理機(jī)調(diào)度的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請(qǐng)求時(shí)間片完作業(yè)注冊(cè)作業(yè)調(diào)度進(jìn)程調(diào)度終止作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換Page82023/2/63.1.1處理機(jī)調(diào)度的層次1.高級(jí)調(diào)度(HighScheduling)2.低級(jí)調(diào)度(LowLevelScheduling)3.中級(jí)調(diào)度(Intermediate-LevelScheduling)處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

Page92023/2/6高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)調(diào)度(HighScheduling)

作業(yè)調(diào)度或長(zhǎng)程調(diào)度（Long-TermScheduling）主要任務(wù)是按一定的原則對(duì)外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，放入就緒隊(duì)列，以使該作業(yè)的進(jìn)程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利也稱(chēng)為接納調(diào)度（AdmissionScheduling）高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天Page102023/2/6高級(jí)、中級(jí)和低級(jí)調(diào)度在每次作業(yè)調(diào)度時(shí)，須決定：接納多少個(gè)作業(yè)即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多道程序度（DegreeofMultiprogramming）作業(yè)太多服務(wù)質(zhì)量下降作業(yè)太少資源利用率低接納哪些作業(yè)

取決于作業(yè)調(diào)度算法先來(lái)先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度→周轉(zhuǎn)時(shí)間太長(zhǎng)→系統(tǒng)吞吐量太低

適當(dāng)?shù)恼壑远嗟莱绦蚨龋杭丛试S多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。周轉(zhuǎn)時(shí)間：從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔。吞吐量：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。Page112023/2/6高級(jí)、中級(jí)和低級(jí)調(diào)度低級(jí)調(diào)度

進(jìn)程調(diào)度或短程調(diào)度（Short-TermScheduling）主要任務(wù)是按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程，將處理機(jī)分配給它常見(jiàn)的低級(jí)調(diào)度有非搶占式和搶占式兩種低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效Page122023/2/6進(jìn)程調(diào)度的任務(wù)

進(jìn)程調(diào)度的任務(wù)是控制、協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng),即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程Page132023/2/6進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)搶占方式(PreemptiveMode)Page142023/2/6進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)

當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，該進(jìn)程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進(jìn)入完成或阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程引起進(jìn)程調(diào)度的因素正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作，如wait、Block、Wakeup原語(yǔ)優(yōu)點(diǎn)：算法簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小缺點(diǎn)：緊急任務(wù)不能及時(shí)響應(yīng)；短進(jìn)程到達(dá)要等待長(zhǎng)進(jìn)程運(yùn)行結(jié)束Page152023/2/6進(jìn)程調(diào)度方式搶占方式(PreemptiveMode)

當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則允許高優(yōu)先權(quán)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)短作業(yè)(進(jìn)程)優(yōu)先原則允許執(zhí)行時(shí)間短的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)時(shí)間片原則時(shí)間片用完后停止執(zhí)行，重新進(jìn)行調(diào)度，適用于分時(shí)系統(tǒng)

優(yōu)點(diǎn)：適于時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)缺點(diǎn)：調(diào)度算法復(fù)雜，系統(tǒng)開(kāi)銷(xiāo)大Page162023/2/6高級(jí)、中級(jí)和低級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-LevelScheduling)又稱(chēng)為內(nèi)存調(diào)度引入目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待主要任務(wù)是按照給定的原則和策略，將處于外存對(duì)換區(qū)中的重又具備運(yùn)行條件的就緒進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存對(duì)換區(qū)Page172023/2/63.1.2處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的共同目標(biāo)資源利用率為提高系統(tǒng)的資源利用率，應(yīng)使系統(tǒng)中的處理機(jī)和其它所有資源盡可能地保持忙碌狀態(tài)。CPU的利用率=CPU有效工作時(shí)間/（CPU有效工作時(shí)間+CPU空閑等待時(shí)間）公平性。指應(yīng)使諸進(jìn)程都獲得合理的CPU時(shí)間，不會(huì)發(fā)生進(jìn)程饑餓現(xiàn)象。對(duì)相同類(lèi)型的進(jìn)程應(yīng)獲得相同的服務(wù)，對(duì)于不同類(lèi)型的進(jìn)程，由于其緊急程度或重要性的不同，則應(yīng)提供不同的服務(wù)。平衡性。盡可能保持系統(tǒng)資源使用的平衡性，使內(nèi)存、外存和I/O設(shè)備的利用率高策略強(qiáng)制執(zhí)行。對(duì)所制訂的策略其中包括安全策略，只要需要，必須予以準(zhǔn)確地執(zhí)行，即使會(huì)造成某些工作的延遲也要執(zhí)行。Page182023/2/6(1)平均周轉(zhuǎn)時(shí)間短。

(2)系統(tǒng)吞吐量高。(3)處理機(jī)利用率高。3.1.2處理機(jī)調(diào)度算法的目標(biāo)批處理系統(tǒng)的目標(biāo)Page192023/2/6周轉(zhuǎn)時(shí)間是指從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔。由四部分組成：作業(yè)在外存后備隊(duì)列上等待（作業(yè)）調(diào)度的時(shí)間進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間進(jìn)程在CPU上執(zhí)行的時(shí)間進(jìn)程等待I/O操作完成的時(shí)間。后3項(xiàng)是在一個(gè)作業(yè)的整個(gè)處理過(guò)程中，可能發(fā)生多次。3.1.2處理機(jī)調(diào)度算法的目標(biāo)周轉(zhuǎn)時(shí)間Page202023/2/6周轉(zhuǎn)時(shí)間短平均周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：進(jìn)程（或作業(yè)）的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS。而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:3.1.2處理機(jī)調(diào)度算法的目標(biāo)Page212023/2/6系統(tǒng)吞吐量高吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較大影響處理機(jī)利用率高

對(duì)于大、中型計(jì)算機(jī)，CPU價(jià)格十分昂貴，致使處理機(jī)的利用率成為衡量系統(tǒng)性能的十分重要的指標(biāo)。而調(diào)度方式和算法對(duì)處理機(jī)的利用率起著十分重要的作用。如果單純是為使處理機(jī)利用率高，應(yīng)盡量多的選擇計(jì)算量大的作業(yè)運(yùn)行。這些要求之間存在一定的矛盾。3.1.2處理機(jī)調(diào)度算法的目標(biāo)Page222023/2/63.1.2處理機(jī)調(diào)度算法的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)響應(yīng)時(shí)間快響應(yīng)時(shí)間是指從用戶(hù)通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時(shí)間包括三部分時(shí)間：一是請(qǐng)求信息從鍵盤(pán)輸入開(kāi)始，直到將其傳送到處理機(jī)的時(shí)間；二是處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間；三是將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。均衡性用戶(hù)對(duì)響應(yīng)時(shí)間的要求并非完全相同。對(duì)較復(fù)雜任務(wù)的響應(yīng)時(shí)間允許較長(zhǎng)，而對(duì)簡(jiǎn)單任務(wù)的響應(yīng)時(shí)間要短。均衡性是指系統(tǒng)響應(yīng)時(shí)間的快慢應(yīng)與用戶(hù)所請(qǐng)求服務(wù)的復(fù)雜性相適應(yīng)。Page232023/2/6實(shí)時(shí)系統(tǒng)的目標(biāo)截止時(shí)間保證截止時(shí)間是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間截止時(shí)間是實(shí)時(shí)系統(tǒng)中的重要指標(biāo)可預(yù)測(cè)性。在實(shí)時(shí)系統(tǒng)中，可預(yù)測(cè)性顯得非常重要。3.1.2處理機(jī)調(diào)度算法的目標(biāo)Page242023/2/6選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則各種系統(tǒng)主要目標(biāo)周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間保證批處理系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)等待時(shí)間短優(yōu)先權(quán)Page252023/2/6選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則等待時(shí)間短等待時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時(shí)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)的時(shí)間優(yōu)先權(quán)準(zhǔn)則在批處理、實(shí)時(shí)和分時(shí)系統(tǒng)中都可以選擇優(yōu)先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理有時(shí)還選擇搶占式調(diào)度方式Page262023/2/6第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

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

進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測(cè)與解除Page272023/2/6作業(yè)與作業(yè)調(diào)度在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法問(wèn)題提出如何制定分配策略：對(duì)不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)先，時(shí)間片輪轉(zhuǎn)等有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn)程調(diào)度，有些兩者皆可3.2.1批處理系統(tǒng)中的作業(yè)1.作業(yè)和作業(yè)步

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

⑵作業(yè)步：在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過(guò)若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果。我們把其中的每一個(gè)加工步驟稱(chēng)一個(gè)作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是上一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步的輸入。

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

在多道批處理系統(tǒng)中，為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊JCB，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。在作業(yè)運(yùn)行期間，系統(tǒng)就按照J(rèn)CB中的信息，和作業(yè)說(shuō)明書(shū)對(duì)作業(yè)進(jìn)行控制。3.作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，通常需要經(jīng)歷收容、運(yùn)行和完成三個(gè)階段。相應(yīng)的作業(yè)也就有“后備狀態(tài)”、“運(yùn)行狀態(tài)”和“完成狀態(tài)”。

⑴收容階段：操作員把用戶(hù)提交的作業(yè)，通過(guò)某種輸入方式或SPOOLing系統(tǒng)，輸入到硬盤(pán)上，再為該作業(yè)建立JCB，并把它放入作業(yè)后備隊(duì)列中，相應(yīng)的，此時(shí)作業(yè)的狀態(tài)為“后備狀態(tài)”。

⑵運(yùn)行階段：當(dāng)作業(yè)被作業(yè)調(diào)度選中后，便為它分配必要的資源和建立進(jìn)程，并將它放入就緒隊(duì)列。一個(gè)作業(yè)從第一次進(jìn)入就緒狀態(tài)開(kāi)始，直到它運(yùn)行結(jié)束前，在此期間都處于“運(yùn)行狀態(tài)”。⑶完成階段：當(dāng)作業(yè)運(yùn)行完成、或發(fā)生異常情況而提前結(jié)束時(shí)，作業(yè)便進(jìn)入完成階段，相應(yīng)的作業(yè)狀態(tài)為“完成狀態(tài)”。此時(shí)系統(tǒng)中的“終止作業(yè)”程序，將會(huì)回收已分配給該作業(yè)的作業(yè)控制塊和所有資源，并將作業(yè)運(yùn)行結(jié)果信息形成輸出文件后輸出。3.2.1批處理系統(tǒng)中的作業(yè)Page302023/2/63.2.1批處理系統(tǒng)中的作業(yè)SPOOLing（即外部設(shè)備聯(lián)機(jī)并行操作），它是關(guān)于慢速字符設(shè)備如何與計(jì)算機(jī)主機(jī)交換信息的一種技術(shù)，通常稱(chēng)為“假脫機(jī)技術(shù)”。spooling系統(tǒng)的三大組成部分：<1>.輸入井和輸出井<2>.輸入緩沖和輸出緩沖<3>.輸入進(jìn)程SPi和輸出進(jìn)程Spo例如：若有進(jìn)程要求對(duì)它打印輸出時(shí)，SPOOLing系統(tǒng)并不是將這臺(tái)打印機(jī)直接分配給SPOOLING進(jìn)程，而是在共享設(shè)備（磁盤(pán)）上的輸出SPOOLing存儲(chǔ)區(qū)中為其分配一塊存儲(chǔ)空間，進(jìn)程的輸出數(shù)據(jù)以文件形式存放于此。各進(jìn)程的數(shù)據(jù)輸出文件形成了一個(gè)輸出隊(duì)列，由輸出SPOOLing系統(tǒng)控制這臺(tái)打印機(jī)進(jìn)程，依次將隊(duì)列中的輸出文件實(shí)際打印輸出。在SPOOLing系統(tǒng)中，實(shí)際上并沒(méi)有為任何進(jìn)程分配，而只是在輸入井和輸出井中，為進(jìn)程分配一存儲(chǔ)區(qū)和建立一張I/O請(qǐng)求表。這樣，便把獨(dú)占設(shè)備改造為共享設(shè)備。

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

也稱(chēng)為接納調(diào)度，根據(jù)JCB中的信息，檢查系統(tǒng)中的資源，能否滿(mǎn)足作業(yè)對(duì)資源的需求，以及按照一定的調(diào)度算法，從外存的后備隊(duì)列中，選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程，排在就緒隊(duì)列上等待調(diào)度。因此，也把作業(yè)調(diào)度（AdmissionScheduling）。

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

①接納多少個(gè)作業(yè)取決于多道程序度，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。

②接納哪些作業(yè)取決于所采用的調(diào)度算法。3.2.2作業(yè)調(diào)度的主要任務(wù)Page322023/2/6先來(lái)先服務(wù)(FCFS)/先進(jìn)先出(FIFO)調(diào)度算法按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長(zhǎng)的作業(yè)/進(jìn)程是一種最簡(jiǎn)單的調(diào)度算法，即可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度幾個(gè)術(shù)語(yǔ)到達(dá)時(shí)間、服務(wù)時(shí)間、開(kāi)始時(shí)間完成時(shí)間、等待時(shí)間周轉(zhuǎn)時(shí)間：完成時(shí)間-到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間①3.2.3先來(lái)先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法

Page332023/2/6先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E044476先來(lái)先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518tPage342023/2/6先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法

先來(lái)先服務(wù)（先進(jìn)先出）優(yōu)缺點(diǎn)

比較有利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）有利于CPU繁忙型作業(yè)（進(jìn)程），而不利于I/O繁忙型作業(yè)（進(jìn)程）用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)Page352023/2/6先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，以要求運(yùn)行時(shí)間長(zhǎng)短進(jìn)行調(diào)度，即啟動(dòng)要求運(yùn)行時(shí)間最短的作業(yè)可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行；而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度②Page362023/2/6先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E0441短作業(yè)/短進(jìn)程優(yōu)先（SJF/SPF）：4633/26988/391399/413181616/540/52.1AAAABBBCCCCCDDEEEE05101518tPage372023/2/6FCFS/SJF調(diào)度算法的性能先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法SJF能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量

作業(yè)調(diào)度情況算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524FCFS完成時(shí)間47121418周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJF完成時(shí)間4918613周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間12.673.11.52.252.1SJF平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間明顯改善Page382023/2/6先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)對(duì)長(zhǎng)作業(yè)不利。嚴(yán)重的是，若一長(zhǎng)作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來(lái)的)短作業(yè)(進(jìn)程)，將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度——饑餓完全未考慮作業(yè)(進(jìn)程)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶(hù)所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶(hù)又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。2023/2/6391、在單道批處理系統(tǒng)中，有五個(gè)作業(yè)進(jìn)入輸入井的時(shí)間及需要執(zhí)行的時(shí)間如下表所示，并約定當(dāng)這五個(gè)作業(yè)全部進(jìn)入輸入井后立即進(jìn)行調(diào)度，忽略調(diào)度的時(shí)間開(kāi)銷(xiāo)。要求：寫(xiě)出分別采用先來(lái)先服務(wù)和最短執(zhí)行時(shí)間優(yōu)先調(diào)度算法時(shí)的調(diào)度次序和作業(yè)平均周轉(zhuǎn)時(shí)間。課堂練習(xí)作業(yè)號(hào)進(jìn)入輸入井時(shí)間需執(zhí)行時(shí)間（分鐘）開(kāi)始執(zhí)行時(shí)間結(jié)束執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/640(1)先來(lái)先服務(wù)調(diào)度算法(FCFS)作業(yè)號(hào)進(jìn)入輸入井時(shí)間需執(zhí)行時(shí)間（分鐘）開(kāi)始執(zhí)行時(shí)間結(jié)束執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/641(1)先來(lái)先服務(wù)調(diào)度算法(FCFS)作業(yè)號(hào)進(jìn)入輸入井時(shí)間需執(zhí)行時(shí)間（分鐘）開(kāi)始執(zhí)行時(shí)間結(jié)束執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間（分鐘）110∶004010:40

11:2080

210∶1030

11:2011:50

100

310∶2020

11:5012:10

110

410∶3025

12:1012:35

125

510∶4010

12:3512:45

125

調(diào)度次序：1-2-3-4-5平均周轉(zhuǎn)時(shí)間為（80+100+110+125+125)/5=108分鐘2023/2/642(2)短作業(yè)優(yōu)先調(diào)度算法(SJF)作業(yè)號(hào)進(jìn)入輸入井時(shí)間需執(zhí)行時(shí)間（分鐘）開(kāi)始執(zhí)行時(shí)間結(jié)束執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/643(2)短作業(yè)優(yōu)先調(diào)度算法(SJF)作業(yè)號(hào)進(jìn)入輸入井時(shí)間需執(zhí)行時(shí)間（分鐘）開(kāi)始執(zhí)行時(shí)間結(jié)束執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間（分鐘）110∶0040

12:0512:45

165

210∶1030

11:3512:05

115

310∶2020

10:5011:10

50

410∶3025

11:1011:35

65

510∶401010:40

10:50

10調(diào)度次序：5-3-4-2-1平均周轉(zhuǎn)時(shí)間為（165+115+50+65+10)/5=81分鐘3.2.4優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法1.優(yōu)先級(jí)調(diào)度算法(priority-schedulingalgorithm)

基于作業(yè)的緊迫程度，由外部賦予作業(yè)相應(yīng)的優(yōu)先級(jí)，調(diào)度算法是根據(jù)該優(yōu)先級(jí)進(jìn)行調(diào)度的。這樣就可以保證緊迫性作業(yè)優(yōu)先運(yùn)行。

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

高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時(shí)間，又考慮作業(yè)運(yùn)行時(shí)間的調(diào)度算法，因此既照顧了短作業(yè)，又不致使長(zhǎng)作業(yè)的等待時(shí)間過(guò)長(zhǎng)，從而改善了處理機(jī)調(diào)度的性能。

★高響應(yīng)比優(yōu)先算法的實(shí)現(xiàn)優(yōu)先級(jí)的變化規(guī)律可描述為：由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先級(jí)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：Page452023/2/6優(yōu)先權(quán)調(diào)度算法的類(lèi)型非搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法③3.2.4優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法Page462023/2/6高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFirst）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類(lèi)型（P92）非搶占式優(yōu)先權(quán)調(diào)度算法特點(diǎn)：系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成，或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)才將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程主要用于批處理系統(tǒng)中，也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中Page472023/2/6高優(yōu)先權(quán)優(yōu)先（HPF—HighestPriorityFirst）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類(lèi)型搶占式優(yōu)先權(quán)調(diào)度算法把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行期間，只要出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，并將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程注意：只要系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程，就進(jìn)行優(yōu)先權(quán)比較該調(diào)度算法，能更好地滿(mǎn)足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中Page482023/2/6高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類(lèi)型（P94）靜態(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ù)來(lái)表示的，例如，07或0255，又把該整數(shù)稱(chēng)為優(yōu)先數(shù)確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)進(jìn)程類(lèi)型:系統(tǒng)進(jìn)程，用戶(hù)進(jìn)程進(jìn)程對(duì)資源的需求用戶(hù)要求靜態(tài)優(yōu)先權(quán)特點(diǎn)系統(tǒng)開(kāi)銷(xiāo)小、不夠精確、一般用在要求不高的系統(tǒng)中問(wèn)題：用戶(hù)將優(yōu)先權(quán)設(shè)的較高，對(duì)其他進(jìn)程不利??！短進(jìn)程優(yōu)先對(duì)長(zhǎng)進(jìn)程不利?。age492023/2/6高優(yōu)先權(quán)優(yōu)先調(diào)度算法動(dòng)態(tài)優(yōu)先權(quán)隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變，以獲得更好的調(diào)度性能可規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)以速率a提高具有相同優(yōu)先權(quán)初值的進(jìn)程，則最先進(jìn)入就緒隊(duì)列，其將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期地壟斷處理機(jī)Page502023/2/6進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先權(quán)開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均靜態(tài)優(yōu)先權(quán)，非搶占式（1為高優(yōu)先權(quán)）高優(yōu)先權(quán)優(yōu)先調(diào)度算法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下?lián)屨际剑闆r如何？Page512023/2/6進(jìn)程調(diào)度算法—優(yōu)先權(quán)、搶占式其中，RQ為就緒隊(duì)列指針，EP為運(yùn)行隊(duì)列指針。Page522023/2/6進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先權(quán)開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均高優(yōu)先權(quán)優(yōu)先調(diào)度算法04A413B225C332D544E1016164484114318131111/516181515/29.83.14靜態(tài)優(yōu)先權(quán)，搶占式（1為高優(yōu)先權(quán)）ABBBEEEECCCCCAAADD05101518tBAACDEACD練習(xí)作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級(jí)A082B141C264（高）Page532023/2/6假定在單CPU條件下有下列要執(zhí)行的作業(yè)：（1）用一個(gè)執(zhí)行時(shí)間圖描述在采用非搶占優(yōu)先級(jí)算法時(shí)執(zhí)行這些作業(yè)的情況；

（2）對(duì)于上述算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少？平均周轉(zhuǎn)時(shí)間是多少？

（3）對(duì)于上述算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少？

平均帶權(quán)周轉(zhuǎn)時(shí)間是多少Page542023/2/6ACB01281418T任務(wù)執(zhí)行任務(wù)到達(dá)ABC（2）平均周轉(zhuǎn)時(shí)間：（8+12+17）/3＝12.33（3）平均帶權(quán)周轉(zhuǎn)時(shí)間：（8/8+12/6+17/3）/3＝2.22Page552023/2/6高優(yōu)先權(quán)優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法（HRF）是FCFS和SJF的結(jié)合，克服了兩種算法的缺點(diǎn)調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)因等待時(shí)間+服務(wù)時(shí)間=該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為④Page562023/2/6高優(yōu)先權(quán)優(yōu)先調(diào)度算法對(duì)HRF的小結(jié)等待時(shí)間相同的作業(yè)，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，要求服務(wù)的時(shí)間相同的作業(yè)，則等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，長(zhǎng)作業(yè)，優(yōu)先權(quán)隨等待時(shí)間的增加而提高，其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī)是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開(kāi)銷(xiāo)——對(duì)短作業(yè)有利——是先來(lái)先服務(wù)——對(duì)長(zhǎng)作業(yè)有利Page572023/2/6進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間響應(yīng)比開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均高優(yōu)先權(quán)優(yōu)先調(diào)度算法04A13B25C32D44E044114181414/447629141212/579638.42.38高響應(yīng)比優(yōu)先，非搶占式21.41.51231.752.42.25=當(dāng)前時(shí)間-到達(dá)時(shí)間服務(wù)時(shí)間+服務(wù)時(shí)間練習(xí)Page582023/2/6假定在單CPU條件下有下列要執(zhí)行的作業(yè)：（1）用一個(gè)執(zhí)行時(shí)間圖描述在采用響應(yīng)比高者優(yōu)先調(diào)度算法

執(zhí)行這些作業(yè)的情況；（2）計(jì)算各作業(yè)的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間。作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間A08B14C26假設(shè)有三個(gè)同時(shí)到達(dá)的作業(yè)J1、J2和J3，它們的執(zhí)行時(shí)間分別是T1、T2和T3，且T1<T2<T3。單處理機(jī)系統(tǒng)采用短作業(yè)優(yōu)先算法運(yùn)行，則平均周轉(zhuǎn)時(shí)間是（

）。Page592023/2/6Page602023/2/6第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

作業(yè)與作業(yè)調(diào)度進(jìn)程調(diào)度實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測(cè)與解除3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式

1.進(jìn)程調(diào)度任務(wù)

①保存處理機(jī)的現(xiàn)場(chǎng)信息：在進(jìn)行調(diào)度時(shí)首先需要保存當(dāng)前進(jìn)程的處理機(jī)的現(xiàn)場(chǎng)信息，如程序計(jì)數(shù)器、多個(gè)通用寄存器中的內(nèi)容等。

②按某種算法選取進(jìn)程：調(diào)度程序按某種算法，從就緒隊(duì)列中選取一個(gè)進(jìn)程，將其狀態(tài)改為運(yùn)行狀態(tài)，并準(zhǔn)備把處理機(jī)分配給它。

③把處理器分配給進(jìn)程：由分派程序把處理器分配給該進(jìn)程。此時(shí)需要將選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場(chǎng)的信息，裝入處理器相應(yīng)的各個(gè)寄存器中，把處理器的控制權(quán)交予該進(jìn)程，讓它從上次的斷點(diǎn)處恢復(fù)運(yùn)行。3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式

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

⑴排隊(duì)器：事先將系統(tǒng)中的所有就緒進(jìn)程，按照一定的策略，排成一個(gè)或多個(gè)隊(duì)列。以便調(diào)度程序能最快地找到它。以后每當(dāng)有一個(gè)進(jìn)程轉(zhuǎn)變?yōu)榫途w狀態(tài)時(shí)，排隊(duì)器便將它插入到相應(yīng)的就緒隊(duì)列。⑵分派器：依據(jù)進(jìn)程調(diào)度程序所選定的進(jìn)程，將其從就緒隊(duì)列中取出，然后進(jìn)行進(jìn)程間的上下文切換，將處理機(jī)分配給新選出的進(jìn)程。⑶上下文切換器：在對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)發(fā)生：①第一對(duì)上下文切換時(shí)，OS將保存當(dāng)前進(jìn)程的上下文，裝入分派程序的上下文，以便分派程序運(yùn)行；②第二對(duì)上下文切換是移出分派程序的上下文，裝入新選進(jìn)程上下文。3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式

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

⑴非搶占方式一旦把處理機(jī)分配給某進(jìn)程后，就一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷，或任何其它原因，去搶占該正在運(yùn)行進(jìn)程的處理機(jī)，直至該進(jìn)程完成，或發(fā)生某事件而被阻塞時(shí)，才把處理機(jī)分配給其它進(jìn)程。采用這種方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為：①正在執(zhí)行的進(jìn)程運(yùn)行完畢，或因發(fā)生某事件而使其無(wú)法再繼續(xù)運(yùn)行；②正在執(zhí)行中的進(jìn)程，因提出I/O請(qǐng)求而暫停執(zhí)行；③在進(jìn)程通信或同步過(guò)程中，執(zhí)行了某種原語(yǔ)操作，如Block原語(yǔ)。

優(yōu)點(diǎn)：是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小，適用于大多數(shù)的批處理系統(tǒng)。

缺點(diǎn)：但它不能用于分時(shí)系統(tǒng)和大多數(shù)實(shí)時(shí)系統(tǒng)。3.進(jìn)程調(diào)度方式⑵搶占方式允許調(diào)度程序根據(jù)某種原則，去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。搶占方式能滿(mǎn)足實(shí)時(shí)任務(wù)的需求。但搶占方式比較復(fù)雜，所需付出統(tǒng)開(kāi)銷(xiāo)也較大。

★“搶占”必須遵循的原則①優(yōu)先權(quán)原則：允許優(yōu)先級(jí)高的新到進(jìn)程，搶占當(dāng)前進(jìn)程的處理機(jī)；②短進(jìn)程優(yōu)先原則：許新到的短進(jìn)程，可以搶占當(dāng)前長(zhǎng)進(jìn)程的處理機(jī)；③時(shí)間片原則：各進(jìn)程按時(shí)間片輪轉(zhuǎn)運(yùn)行時(shí)，當(dāng)正在執(zhí)行的進(jìn)程的一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。3.3.2輪轉(zhuǎn)調(diào)度算法1.輪轉(zhuǎn)法的基本原理

系統(tǒng)將所有的就緒進(jìn)程按FCFS策略，排成一個(gè)就緒隊(duì)列。系統(tǒng)可設(shè)置每隔一定時(shí)間（如30ms），便產(chǎn)生一次中斷，去激活進(jìn)程調(diào)度程序進(jìn)行調(diào)度，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)它運(yùn)行完后，又把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，也讓它執(zhí)行一個(gè)時(shí)間片。

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

①若一個(gè)時(shí)間片尚未用完，正在運(yùn)行的進(jìn)程便已經(jīng)完成，就立即激活調(diào)度程序，將它從就緒隊(duì)列中刪除，再調(diào)度就緒隊(duì)列中隊(duì)首進(jìn)程運(yùn)行，并啟動(dòng)一個(gè)新的時(shí)間片。②在一個(gè)時(shí)間片用完時(shí)，此時(shí)計(jì)時(shí)器中斷處理程序被激活。如果進(jìn)程尚未運(yùn)行完畢，調(diào)度程序把它送往就緒隊(duì)列的末尾。

Page662023/2/6基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法(RR—RoundRobin)系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首時(shí)間片的大小從幾ms到幾百ms優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時(shí)間片+優(yōu)先權(quán)⑤Page672023/2/6基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到達(dá)時(shí)間為0、1、2、3、4，又如何？Page682023/2/6基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABACBDAECBDAECECEC05101518t04A13B25C32D44E013571110121718123931616/5841313/411.63.293.3.2輪轉(zhuǎn)調(diào)度算法3.時(shí)間片大小的確定在輪轉(zhuǎn)算法中，時(shí)間片的大小，對(duì)系統(tǒng)性能有很大的影響。若選擇很小的時(shí)間片，將有利于短作業(yè)，因?yàn)樗茉谠摃r(shí)間片內(nèi)完成。但時(shí)間片小，意味著會(huì)頻繁地執(zhí)行進(jìn)程調(diào)度，和進(jìn)程上下文的切換，這無(wú)疑會(huì)增加系統(tǒng)的開(kāi)銷(xiāo)。若時(shí)間片選擇得太長(zhǎng)，且為使每個(gè)進(jìn)程，都能在一個(gè)時(shí)間片內(nèi)完成，RR算法便退化為FCFS算法，無(wú)法滿(mǎn)足短作業(yè)和交互式用戶(hù)的需求。一個(gè)較為可取的時(shí)間片大小是，略大于一次典型的交互所需要的時(shí)間，使大多數(shù)交互式進(jìn)程，能在一個(gè)時(shí)間片內(nèi)完成，從而可以獲得很小的響應(yīng)時(shí)間。3.時(shí)間片大小的確定3.時(shí)間片大小的確定下左圖示出了時(shí)間片大小對(duì)響應(yīng)時(shí)間的影響，其中圖a是時(shí)間片略大于典型交互的時(shí)間，其中圖b是時(shí)間片小于典型交互的時(shí)間。下右圖示出了時(shí)間片分別為q=1和q=4時(shí)對(duì)平均周轉(zhuǎn)時(shí)間的影響。Page712023/2/6基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇問(wèn)題固定時(shí)間片可變時(shí)間片時(shí)間片大小與時(shí)間片大小有關(guān)的因素系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)CPU能力

3.3.3優(yōu)先級(jí)調(diào)度算法

1.優(yōu)先級(jí)調(diào)度算法的類(lèi)型把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程。

⑴非搶占式優(yōu)先級(jí)調(diào)度算法：一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去直至完成，或者因該進(jìn)程發(fā)生某事件而放棄處理機(jī)時(shí)，系統(tǒng)方可將處理機(jī)重新分配給另一優(yōu)先級(jí)最高的進(jìn)程。

⑵搶占式優(yōu)先級(jí)調(diào)度算法：把處理機(jī)分配給優(yōu)先級(jí)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要出現(xiàn)了另一個(gè)其優(yōu)先級(jí)更高的進(jìn)程，調(diào)度程序就將處理機(jī)分配給新到的優(yōu)先級(jí)最高的進(jìn)程。

2.優(yōu)先級(jí)的類(lèi)型

⑴靜態(tài)優(yōu)先級(jí)：靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。優(yōu)先級(jí)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如0～255中的某一整數(shù)，又把該整數(shù)稱(chēng)為優(yōu)先數(shù)。確定進(jìn)程優(yōu)先級(jí)大小的依據(jù)有如下三個(gè)：進(jìn)程類(lèi)型、進(jìn)程對(duì)資源的需求、用戶(hù)要求。

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

★算法思想

將系統(tǒng)中的進(jìn)程就緒隊(duì)列從一個(gè)拆分為若干個(gè)，將不同類(lèi)型或性質(zhì)的進(jìn)程固定分配在不同的就緒隊(duì)列，不同的就緒隊(duì)列采用不同的調(diào)度算法，一個(gè)就緒隊(duì)列中的進(jìn)程可以設(shè)置不同的優(yōu)先級(jí)，不同的就緒隊(duì)列本身也可以設(shè)置不同的優(yōu)先級(jí)。3.3.5多級(jí)反饋隊(duì)列調(diào)度算法

★算法思想將就緒隊(duì)列分為N級(jí)，每個(gè)就緒隊(duì)列分配給不同的時(shí)間片，隊(duì)列級(jí)別越高，時(shí)間越長(zhǎng)，級(jí)別越小，時(shí)間片越小，最后一級(jí)采用時(shí)間片輪轉(zhuǎn)，其他隊(duì)列采用先進(jìn)先出；系統(tǒng)從第一級(jí)調(diào)度，當(dāng)?shù)谝患?jí)為空時(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列，當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片，放棄CPU時(shí)，進(jìn)入下一級(jí)隊(duì)列；等待進(jìn)程被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時(shí)，進(jìn)入第一級(jí)隊(duì)列。

★算法要點(diǎn)

*首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列；*每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的為第一級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別的降低，時(shí)間片加大；*各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法；*一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列；*進(jìn)程由于等待而放棄CPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列；*當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占CPU，被搶占進(jìn)程回到原來(lái)一級(jí)就緒隊(duì)列末尾；*當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如此類(lèi)推；*當(dāng)時(shí)間片到后，進(jìn)程放棄CPU，回到下一級(jí)隊(duì)列。Page752023/2/6就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1＜S2＜S3)調(diào)度方式高低優(yōu)先級(jí)時(shí)間片小大Sn按FIFO原則排隊(duì)等待調(diào)度尚未完成轉(zhuǎn)入第二隊(duì)列的末尾，按FIFO原則等待調(diào)度采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行因等待而放棄CPU后，進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列3.3.5多級(jí)反饋隊(duì)列調(diào)度算法Page762023/2/6多級(jí)反饋隊(duì)列調(diào)度算法的性能終端型作業(yè)用戶(hù)終端型作業(yè)用戶(hù)所提交的作業(yè)多屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成即可短批處理作業(yè)用戶(hù)若在第1隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間如在第一個(gè)隊(duì)列中不能完成，只需在第2、3隊(duì)列中各執(zhí)行一個(gè)時(shí)間片長(zhǎng)批處理作業(yè)用戶(hù)長(zhǎng)作業(yè)將依次在第1，2，3…，n隊(duì)列中執(zhí)行，最終按輪轉(zhuǎn)方式運(yùn)行3.3.5多級(jí)反饋隊(duì)列調(diào)度算法3.3.6基于公平原則的調(diào)度算法

1.保證調(diào)度算法保證調(diào)度算法向用戶(hù)所做出的是明確的性能保證，該算法可以做到調(diào)度的公平性，如處理機(jī)分配的公平性。在實(shí)施公平調(diào)度算法時(shí)系統(tǒng)中必須具有這樣一些功能：（1）跟蹤計(jì)算每個(gè)進(jìn)程自創(chuàng)建以來(lái)已經(jīng)執(zhí)行的處理時(shí)間；（2）計(jì)算每個(gè)進(jìn)程應(yīng)獲得的處理機(jī)時(shí)間，即自創(chuàng)建以來(lái)的時(shí)間除以n。（3）計(jì)算進(jìn)程獲得處理機(jī)時(shí)間的比率。（4）比較各進(jìn)程獲得處理機(jī)時(shí)間的比率。（5）調(diào)度程序應(yīng)選擇比率最小的進(jìn)程，將處理機(jī)分配給它，并讓該進(jìn)程一直運(yùn)行，直到超過(guò)最接近它的進(jìn)程比率為止。

2.公平分享調(diào)度算法在該調(diào)度算法中，調(diào)度的公平性主要是針對(duì)用戶(hù)，使所有用戶(hù)能獲得相同的處理機(jī)時(shí)間，或所要求的時(shí)間比例。然而調(diào)度又是以進(jìn)程為基本單位。為此，必須考慮到每一個(gè)用戶(hù)所擁有的進(jìn)程數(shù)目。Page782023/2/6進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢或由于某種錯(cuò)誤而終止運(yùn)行當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/O）分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)阻塞進(jìn)程變成就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作（P操作，阻塞原語(yǔ)，喚醒原語(yǔ)）Page792023/2/6何時(shí)切換進(jìn)程只要OS取得對(duì)CPU的控制，進(jìn)程切換就可能發(fā)生:超級(jí)用戶(hù)調(diào)用來(lái)自程序的顯式請(qǐng)求(如：打開(kāi)文件)，該進(jìn)程通常會(huì)被阻塞陷阱最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退出狀態(tài)中斷外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至IH（中斷處理程序）Page802023/2/6引起進(jìn)程調(diào)度的原因正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作如P操作、阻塞、掛起原語(yǔ)等；在可剝奪式調(diào)度中，有比當(dāng)前進(jìn)程優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列；在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片完。通常系統(tǒng)是按先來(lái)先服務(wù)或優(yōu)先權(quán)形式來(lái)組織調(diào)度隊(duì)列。Page812023/2/6第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)

作業(yè)與作業(yè)調(diào)度進(jìn)程調(diào)度

實(shí)時(shí)調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測(cè)與解除Page822023/2/6實(shí)時(shí)調(diào)度

實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度算法的分類(lèi)常用的幾種實(shí)時(shí)調(diào)度算法Page832023/2/6實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息開(kāi)始截止時(shí)間和完成截止時(shí)間就緒時(shí)間該任務(wù)成為就緒狀態(tài)的起始時(shí)間處理時(shí)間資源要求優(yōu)先級(jí)Page842023/2/6實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿(mǎn)足下面的限制條件例：一個(gè)周期為10ms，執(zhí)行5ms,

一個(gè)周期為15ms,執(zhí)行10ms,

則：(5/10)+(10/15)=35/30Page852023/2/6實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件系統(tǒng)處理能力強(qiáng)若上式不能滿(mǎn)足，則系統(tǒng)是不可調(diào)度的解決的方法是提高系統(tǒng)的處理能力采用單處理機(jī)系統(tǒng)但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間采用多處理機(jī)系統(tǒng)假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為Page862023/2/6實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件采用搶占式調(diào)度機(jī)制當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，以滿(mǎn)足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜小的實(shí)時(shí)系統(tǒng)，若能預(yù)知任務(wù)的開(kāi)始截止時(shí)間，則可采用非搶占調(diào)度機(jī)制，以簡(jiǎn)化調(diào)度程序和對(duì)任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開(kāi)銷(xiāo)注意：設(shè)計(jì)這種調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)地將自己阻塞起來(lái)，以便釋放處理機(jī)，供調(diào)度程序調(diào)度那些開(kāi)始截止時(shí)間即將到達(dá)的任務(wù)Page872023/2/6實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件具有快速切換機(jī)制該機(jī)制應(yīng)具有如下兩方面的能力對(duì)外部中斷的快速響應(yīng)能力為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))快速的任務(wù)分派能力在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開(kāi)銷(xiāo)Page882023/2/6實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度算法的分類(lèi)常用的幾種實(shí)時(shí)調(diào)度算法Page892023/2/6實(shí)時(shí)調(diào)度算法的分類(lèi)非搶占式調(diào)度算法（實(shí)時(shí)任務(wù)小）非搶占式輪轉(zhuǎn)調(diào)度算法

常用于工業(yè)生產(chǎn)的群控系統(tǒng)中調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)運(yùn)行一個(gè)任務(wù)運(yùn)行后排在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度非搶占式優(yōu)先調(diào)度算法為時(shí)間要求嚴(yán)格的任務(wù)分配較高優(yōu)先級(jí)當(dāng)優(yōu)先權(quán)高的實(shí)時(shí)任務(wù)到來(lái)時(shí)，排在就緒隊(duì)列的隊(duì)首等待調(diào)度Page902023/2/6實(shí)時(shí)調(diào)度算法的分類(lèi)搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法某實(shí)時(shí)任務(wù)到達(dá)后，若優(yōu)先級(jí)高于當(dāng)前正在執(zhí)行任務(wù)的優(yōu)先級(jí)，并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來(lái)后調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法一旦有外部中斷，只要當(dāng)前任務(wù)不在臨界區(qū)內(nèi)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，交處理機(jī)分配給要求中斷的緊迫任務(wù)Page912023/2/6實(shí)時(shí)調(diào)度算法的分類(lèi)(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í)間在就緒隊(duì)列尾在就緒隊(duì)列首xs--xxsxs--xxxmsPage922023/2/6實(shí)時(shí)調(diào)度算法的分類(lèi)當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度時(shí)鐘中斷到來(lái)時(shí)調(diào)度時(shí)間(c)基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度實(shí)時(shí)進(jìn)程當(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)度調(diào)度時(shí)間xms--xxsPage932023/2/6實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度算法的分類(lèi)常用的幾種實(shí)時(shí)調(diào)度算法Page942023/2/6常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先EDF(EarliestDeadlineFirst)算法根據(jù)任務(wù)的開(kāi)始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)，截止時(shí)間越早優(yōu)先級(jí)越高既可用于搶占式調(diào)度