1、1 在多道程序系統(tǒng)中，進(jìn)程數(shù)目往往多在多道程序系統(tǒng)中，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目。要求系統(tǒng)能按某種算法，于處理機(jī)數(shù)目。要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的進(jìn)程，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的進(jìn)程，使之執(zhí)行。而系統(tǒng)的運(yùn)行性能，如吞吐量使之執(zhí)行。而系統(tǒng)的運(yùn)行性能，如吞吐量地大小、周轉(zhuǎn)時(shí)間的長(zhǎng)短、響應(yīng)的及時(shí)性地大小、周轉(zhuǎn)時(shí)間的長(zhǎng)短、響應(yīng)的及時(shí)性等，在很大程度上都取決于處理機(jī)調(diào)度。等，在很大程度上都取決于處理機(jī)調(diào)度。23處理器調(diào)度的三級(jí)模型如圖處理器調(diào)度的三級(jí)模型如圖3.33.3所示。所示。圖圖3.3 3.3 處理器三級(jí)調(diào)度模型處理器三級(jí)調(diào)度模型進(jìn)程掛起就緒隊(duì)列進(jìn)程掛起就緒隊(duì)列進(jìn)

2、程 阻 塞進(jìn) 程 阻 塞隊(duì)列隊(duì)列進(jìn)程掛起阻塞隊(duì)列進(jìn)程掛起阻塞隊(duì)列進(jìn)程就緒隊(duì)列進(jìn)程就緒隊(duì)列完成完成中 級(jí)中 級(jí)調(diào)度調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度處理器處理器高級(jí)調(diào)度高級(jí)調(diào)度作業(yè)后備隊(duì)列作業(yè)后備隊(duì)列交互式用戶交互式用戶提交提交用戶作業(yè)用戶作業(yè)5 3.1.1 3.1.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次1 1 高級(jí)調(diào)度高級(jí)調(diào)度 又稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度又稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度(long-term (long-term scheduling),scheduling),用于決定把外存上處于后備隊(duì)列中的用于決定把外存上處于后備隊(duì)列中的作業(yè)調(diào)入內(nèi)存，并為他們創(chuàng)建進(jìn)程、分配必要的資作業(yè)調(diào)入內(nèi)存，并為他們創(chuàng)建進(jìn)程、分配必

3、要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。備執(zhí)行。 作業(yè)作業(yè): :用戶提交給系統(tǒng)處理的一個(gè)任務(wù)用戶提交給系統(tǒng)處理的一個(gè)任務(wù). .包括用包括用戶程序戶程序數(shù)據(jù)數(shù)據(jù)對(duì)程序運(yùn)行進(jìn)行控制和處理有關(guān)的對(duì)程序運(yùn)行進(jìn)行控制和處理有關(guān)的信息信息. .分為批處理作業(yè)和終端型作業(yè)分為批處理作業(yè)和終端型作業(yè). . 分時(shí)和實(shí)時(shí)系統(tǒng)中不設(shè)置高級(jí)調(diào)度。？分時(shí)和實(shí)時(shí)系統(tǒng)中不設(shè)置高級(jí)調(diào)度。？6 每次執(zhí)行作業(yè)調(diào)度時(shí)，都需作出以下兩每次執(zhí)行作業(yè)調(diào)度時(shí)，都需作出以下兩個(gè)決定：個(gè)決定： 接納多個(gè)作業(yè)接納多個(gè)作業(yè): :取決于系統(tǒng)的多道程序度取決于系統(tǒng)的多道程序度. . 接納哪

4、些作業(yè)接納哪些作業(yè): :取決于系統(tǒng)調(diào)度算法：先取決于系統(tǒng)調(diào)度算法：先來(lái)先服務(wù)來(lái)先服務(wù), ,優(yōu)先級(jí)優(yōu)先級(jí), ,響應(yīng)比等響應(yīng)比等. .72 2 低級(jí)調(diào)度（低級(jí)調(diào)度（low level Schedulinglow level Scheduling） 又稱為進(jìn)程調(diào)度或短程調(diào)度又稱為進(jìn)程調(diào)度或短程調(diào)度. .它決定就緒隊(duì)列它決定就緒隊(duì)列中的哪個(gè)進(jìn)程將獲得處理機(jī)，然后分派程序執(zhí)行把中的哪個(gè)進(jìn)程將獲得處理機(jī)，然后分派程序執(zhí)行把處理機(jī)分派給該進(jìn)程的操作?？煞譃閮煞N方式：處理機(jī)分派給該進(jìn)程的操作?？煞譃閮煞N方式：非搶占方式（非搶占方式（Non-preemaptive ModeNon-preemaptive Mod

5、e）: : 一旦把處理機(jī)分配給進(jìn)程后便讓該進(jìn)程一直執(zhí)一旦把處理機(jī)分配給進(jìn)程后便讓該進(jìn)程一直執(zhí)行行, ,直至完成或發(fā)生事件而被阻塞時(shí)直至完成或發(fā)生事件而被阻塞時(shí), ,才再把處理機(jī)才再把處理機(jī)分配給其它進(jìn)程分配給其它進(jìn)程, ,不允許某進(jìn)程搶占已經(jīng)分配出去不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)的處理機(jī). . 優(yōu)點(diǎn)優(yōu)點(diǎn): :簡(jiǎn)單簡(jiǎn)單, ,系統(tǒng)開(kāi)銷小系統(tǒng)開(kāi)銷小, ,適合在批處理系統(tǒng)環(huán)境適合在批處理系統(tǒng)環(huán)境. . 缺點(diǎn)缺點(diǎn): :實(shí)時(shí)性差實(shí)時(shí)性差. .8搶占方式（搶占方式（Preemptive ModePreemptive Mode）: : 允許調(diào)度程序根據(jù)某種原則去停止某個(gè)正允許調(diào)度程序根據(jù)某種原則去停止某

6、個(gè)正在執(zhí)行的進(jìn)程，將已分配的處理機(jī)重新分配給在執(zhí)行的進(jìn)程，將已分配的處理機(jī)重新分配給另一進(jìn)程另一進(jìn)程. . 搶占原則搶占原則: : a. a.優(yōu)先權(quán)原則優(yōu)先權(quán)原則. . b.b.短作業(yè)（進(jìn)程）優(yōu)先原則短作業(yè)（進(jìn)程）優(yōu)先原則. . c.c.時(shí)間片原則時(shí)間片原則. .9 3 3 中級(jí)調(diào)度（中級(jí)調(diào)度（Intermediate-Level Scheduling Intermediate-Level Scheduling ） 又稱為中程調(diào)度。目的是提高內(nèi)存的利用率又稱為中程調(diào)度。目的是提高內(nèi)存的利用率和系統(tǒng)吞吐量。和系統(tǒng)吞吐量。 操作是將暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存中調(diào)到操作是將暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存中調(diào)

7、到外存上去，該進(jìn)程為外存就緒或外存掛起狀態(tài)。外存上去，該進(jìn)程為外存就緒或外存掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又有空閑當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又有空閑時(shí)，時(shí)，由中級(jí)調(diào)度來(lái)決定將外存上具備運(yùn)行的就緒由中級(jí)調(diào)度來(lái)決定將外存上具備運(yùn)行的就緒進(jìn)程重新從外存調(diào)入到內(nèi)存，修改狀態(tài)為就緒，進(jìn)程重新從外存調(diào)入到內(nèi)存，修改狀態(tài)為就緒，等待進(jìn)程調(diào)度。等待進(jìn)程調(diào)度。 10在這三種調(diào)度方式中：在這三種調(diào)度方式中：進(jìn)程調(diào)度的運(yùn)行頻率最高：分時(shí)系統(tǒng)中進(jìn)程調(diào)度的運(yùn)行頻率最高：分時(shí)系統(tǒng)中10-10010-100msms進(jìn)行一次進(jìn)程調(diào)度，所以進(jìn)程調(diào)度算法不能太復(fù)進(jìn)行一次進(jìn)程調(diào)度，所以進(jìn)程調(diào)度算法不能太復(fù)雜，

8、不能占用太多雜，不能占用太多CPUCPU時(shí)間。時(shí)間。作業(yè)調(diào)度往往發(fā)生在一個(gè)批處理作業(yè)運(yùn)行完畢，作業(yè)調(diào)度往往發(fā)生在一個(gè)批處理作業(yè)運(yùn)行完畢，作業(yè)調(diào)度的周期較長(zhǎng)，大約幾分鐘。作業(yè)調(diào)度的周期較長(zhǎng)，大約幾分鐘。中級(jí)調(diào)度介于以上兩者之間。中級(jí)調(diào)度介于以上兩者之間。11 3.1.23.1.2處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo) 1 1 處理機(jī)調(diào)度算法的共同目標(biāo)處理機(jī)調(diào)度算法的共同目標(biāo)（1）資源利用率；（2）公平性；（3）平衡性；（4）策略強(qiáng)制執(zhí)行。 CPU的利用率:CPU的有效工作時(shí)間/(CPU的有效工作時(shí)間+CPU的等待時(shí)間）122 2 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)（1）平均周轉(zhuǎn)時(shí)間短；（2）系統(tǒng)

9、吞吐量高；（3）處理機(jī)利用率高。周轉(zhuǎn)時(shí)間：提交給系統(tǒng)開(kāi)始到完成結(jié)束。133 3 分時(shí)系統(tǒng)的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)（1）響應(yīng)時(shí)間快；（2）均衡性。4 4 實(shí)時(shí)系統(tǒng)的目標(biāo)實(shí)時(shí)系統(tǒng)的目標(biāo)（1）截止時(shí)間的保證；（2）可預(yù)測(cè)性。14選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則可分為面向用戶和面向系統(tǒng)的準(zhǔn)則：可分為面向用戶和面向系統(tǒng)的準(zhǔn)則： 1 1 面向用戶準(zhǔn)則：面向用戶準(zhǔn)則： （1 1）周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短( (周轉(zhuǎn)時(shí)間與平均周轉(zhuǎn)時(shí)間概念周轉(zhuǎn)時(shí)間與平均周轉(zhuǎn)時(shí)間概念).). 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間: :作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)為它實(shí)作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)為它實(shí)際服務(wù)時(shí)間之比際服務(wù)時(shí)間之比.(.(大于等

10、于大于等于1,1,越小越好越小越好) ) （2 2）響應(yīng)時(shí)間快）響應(yīng)時(shí)間快( (響應(yīng)時(shí)間概念響應(yīng)時(shí)間概念).). （3 3）截止時(shí)間的保證）截止時(shí)間的保證( (截止時(shí)間概念截止時(shí)間概念).). （4 4）優(yōu)先權(quán)準(zhǔn)則）優(yōu)先權(quán)準(zhǔn)則. .15 2 2 面向系統(tǒng)準(zhǔn)則：面向系統(tǒng)準(zhǔn)則： (1) (1)系統(tǒng)吞吐量系統(tǒng)吞吐量. . (2) (2)處理機(jī)利用率好處理機(jī)利用率好. . (3) (3)各類資源的平衡利用各類資源的平衡利用. . 16 1 1 作業(yè)和作業(yè)步作業(yè)和作業(yè)步 作業(yè)：作業(yè)： 它不僅包含了通常的程序和數(shù)據(jù)，而且還它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說(shuō)明書，系統(tǒng)根據(jù)該說(shuō)明書來(lái)對(duì)程應(yīng)配

11、有一份作業(yè)說(shuō)明書，系統(tǒng)根據(jù)該說(shuō)明書來(lái)對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中是以作業(yè)為基序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。本單位從外存調(diào)入內(nèi)存的。 作業(yè)步（作業(yè)步（JobJob stepstep）：）：各作業(yè)步之間存在著相互聯(lián)各作業(yè)步之間存在著相互聯(lián)系，往往是上一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步系，往往是上一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步的輸入。的輸入。17 2 2 作業(yè)控制塊作業(yè)控制塊 在多道批處理系統(tǒng)中，為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制在多道批處理系統(tǒng)中，為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊塊JCBJCB，以管理和調(diào)度作業(yè)。它是作業(yè)在系統(tǒng)中存在的標(biāo)志。，以管理和調(diào)度作業(yè)。

12、它是作業(yè)在系統(tǒng)中存在的標(biāo)志。 通常在通常在JCBJCB中包含的內(nèi)容有：中包含的內(nèi)容有： 作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬號(hào)、作業(yè)類型、作業(yè)狀況、作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬號(hào)、作業(yè)類型、作業(yè)狀況、調(diào)度信息、資源需求、資源使用情況等。調(diào)度信息、資源需求、資源使用情況等。18 3 3作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài) 作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，通常需要經(jīng)歷收容、運(yùn)行作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，通常需要經(jīng)歷收容、運(yùn)行和完成三個(gè)階段。相應(yīng)的作業(yè)也就有和完成三個(gè)階段。相應(yīng)的作業(yè)也就有“后備狀態(tài)后備狀態(tài)”、“運(yùn)運(yùn)行狀態(tài)行狀態(tài)”、“完成狀態(tài)完成狀態(tài)”。 （1 1）收容階段；）收容階段； （2 2

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

14、業(yè)調(diào)度時(shí)，都需要做出以下兩個(gè)決定： 1 1、接納多少個(gè)作業(yè)；、接納多少個(gè)作業(yè)； 2 2、接納哪些作業(yè)。、接納哪些作業(yè)。20 1 1 先來(lái)先服務(wù)（先來(lái)先服務(wù)（FCFS)FCFS)調(diào)度算法調(diào)度算法 作業(yè)調(diào)度：作業(yè)調(diào)度： 每次調(diào)度是從后備作業(yè)隊(duì)列中，選擇每次調(diào)度是從后備作業(yè)隊(duì)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，并分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。存，并分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。 進(jìn)程調(diào)度：進(jìn)程調(diào)度：每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使之投先進(jìn)入該隊(duì)

15、列的進(jìn)程，把處理機(jī)分配給它，使之投入運(yùn)行。入運(yùn)行。 21進(jìn)程進(jìn)程名名到達(dá)到達(dá)時(shí)間時(shí)間服務(wù)服務(wù)時(shí)間時(shí)間開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.99 FCFSFCFS算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），而算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。在應(yīng)用中也就是利于不利于短作業(yè)（進(jìn)程）。在應(yīng)用中也就是利于CPUCPU繁忙型作業(yè)（進(jìn)程），而不利于繁忙型作業(yè)（進(jìn)程），而不利于I/OI/O繁忙型繁忙型作業(yè)（進(jìn)程）。作業(yè)（進(jìn)程）。22SJ(P)FSJ(P)F是指

16、對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。 短作業(yè)短作業(yè)( (SJF)SJF)的調(diào)度算法可以照顧實(shí)際上占很的調(diào)度算法可以照顧實(shí)際上占很大比例的短作業(yè)大比例的短作業(yè), ,使其能比長(zhǎng)作業(yè)優(yōu)先執(zhí)行使其能比長(zhǎng)作業(yè)優(yōu)先執(zhí)行. .從作從作業(yè)的后備隊(duì)列中選則一個(gè)或若干個(gè)短作業(yè)到內(nèi)存業(yè)的后備隊(duì)列中選則一個(gè)或若干個(gè)短作業(yè)到內(nèi)存就緒隊(duì)列就緒隊(duì)列. . 短進(jìn)程短進(jìn)程( (SPF)SPF)的調(diào)度算法從內(nèi)存就緒隊(duì)列中選的調(diào)度算法從內(nèi)存就緒隊(duì)列中選則一個(gè)運(yùn)行時(shí)間最短的進(jìn)程到處理機(jī)中執(zhí)行則一個(gè)運(yùn)行時(shí)間最短的進(jìn)程到處理機(jī)中執(zhí)行. .23 作業(yè)情況調(diào)度算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間

17、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.124SJ(P)FSJ(P)F調(diào)度算法存在的問(wèn)題調(diào)度算法存在的問(wèn)題: :該算法對(duì)長(zhǎng)作業(yè)非常不利該算法對(duì)長(zhǎng)作業(yè)非常不利. .可能長(zhǎng)期得不到調(diào)可能長(zhǎng)期得不到調(diào)度度. .該算法完全未考慮作業(yè)的緊迫程度該算法完全未考慮作業(yè)的緊迫程度, ,不能保證不能保證緊迫性作業(yè)或進(jìn)程會(huì)得到及時(shí)處理緊迫性作業(yè)或進(jìn)程會(huì)得到及時(shí)處理. .由于作業(yè)由于作業(yè)( (進(jìn)程進(jìn)程) )的長(zhǎng)短只是根據(jù)用戶所提供的的長(zhǎng)短只是根據(jù)用戶所提供的

18、估計(jì)執(zhí)行時(shí)間而定估計(jì)執(zhí)行時(shí)間而定, ,而用戶又可能估計(jì)不準(zhǔn)而用戶又可能估計(jì)不準(zhǔn), ,致致使該算法不一定能真正作到短作業(yè)使該算法不一定能真正作到短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先優(yōu)先調(diào)度調(diào)度. .25Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04SJF (non-preemptive非搶占非搶占)Average waiting time = (0 + 6 + 3 + 7)/4 = 4P1P3P273160P481226Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.0

19、4SJF (preemptive搶占搶占)Average waiting time = (9 + 1 + 0 +2)/4 =3P1P3P242110P457P2P11627 此調(diào)度的算法是：當(dāng)進(jìn)程調(diào)度時(shí)，把處理機(jī)此調(diào)度的算法是：當(dāng)進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。 1 1 優(yōu)先權(quán)調(diào)度算法類型優(yōu)先權(quán)調(diào)度算法類型 a.a.非強(qiáng)占式非強(qiáng)占式: : 系統(tǒng)按照優(yōu)先權(quán)的高低進(jìn)行調(diào)度系統(tǒng)按照優(yōu)先權(quán)的高低進(jìn)行調(diào)度, ,進(jìn)程調(diào)度時(shí)進(jìn)程調(diào)度時(shí)把處理機(jī)分配給具有高優(yōu)先權(quán)的進(jìn)程把處理機(jī)分配給具有高優(yōu)先權(quán)的進(jìn)程, ,直到該進(jìn)程直到該進(jìn)程完成后才放棄處理機(jī)完成后才放棄

20、處理機(jī). . 適用于實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中適用于實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中. . b. b.強(qiáng)占式強(qiáng)占式: : 在處理機(jī)分配上優(yōu)先權(quán)高的進(jìn)程會(huì)停止優(yōu)先在處理機(jī)分配上優(yōu)先權(quán)高的進(jìn)程會(huì)停止優(yōu)先權(quán)低的進(jìn)程的執(zhí)行而得到處理機(jī)權(quán)低的進(jìn)程的執(zhí)行而得到處理機(jī). .282.2.優(yōu)先權(quán)的類型：優(yōu)先權(quán)的類型： （1 1）靜態(tài)優(yōu)先權(quán)）靜態(tài)優(yōu)先權(quán), ,進(jìn)程創(chuàng)建時(shí)確定，用一固定進(jìn)程創(chuàng)建時(shí)確定，用一固定數(shù)值表示數(shù)值表示, ,在進(jìn)程的整個(gè)執(zhí)行期間保持不變?cè)谶M(jìn)程的整個(gè)執(zhí)行期間保持不變. . 確定進(jìn)程優(yōu)先權(quán)的依據(jù)確定進(jìn)程優(yōu)先權(quán)的依據(jù): :w進(jìn)程類型進(jìn)程類型: :系統(tǒng)進(jìn)程高于用戶進(jìn)程系統(tǒng)進(jìn)程高于用戶進(jìn)程. .w進(jìn)程對(duì)資源的要

21、求進(jìn)程對(duì)資源的要求: :運(yùn)行時(shí)間短的進(jìn)程優(yōu)先權(quán)高運(yùn)行時(shí)間短的進(jìn)程優(yōu)先權(quán)高. .w根據(jù)用戶要求根據(jù)用戶要求: :用戶緊迫程度及用戶付費(fèi)情況用戶緊迫程度及用戶付費(fèi)情況. . （2 2）動(dòng)態(tài)優(yōu)先權(quán)，優(yōu)先權(quán)隨進(jìn)程的推進(jìn)而改）動(dòng)態(tài)優(yōu)先權(quán)，優(yōu)先權(quán)隨進(jìn)程的推進(jìn)而改變變: :優(yōu)先權(quán)初值相同的進(jìn)程最先進(jìn)入的進(jìn)程會(huì)先得優(yōu)先權(quán)初值相同的進(jìn)程最先進(jìn)入的進(jìn)程會(huì)先得到處理機(jī)到處理機(jī). .29 在批處理系統(tǒng)中在批處理系統(tǒng)中, ,作業(yè)調(diào)度的短作業(yè)優(yōu)先作業(yè)調(diào)度的短作業(yè)優(yōu)先算法是一個(gè)比較好的算法算法是一個(gè)比較好的算法, ,對(duì)長(zhǎng)作業(yè)如果引入對(duì)長(zhǎng)作業(yè)如果引入動(dòng)態(tài)優(yōu)先權(quán)機(jī)制動(dòng)態(tài)優(yōu)先權(quán)機(jī)制, ,則長(zhǎng)作業(yè)在等待一定的時(shí)間則長(zhǎng)作業(yè)在等待一定

22、的時(shí)間后后, ,必然有機(jī)會(huì)分配到處理機(jī)必然有機(jī)會(huì)分配到處理機(jī). . 優(yōu)先權(quán)的變化可描述為：優(yōu)先權(quán)的變化可描述為： 30響應(yīng)比響應(yīng)比RpRp可表示為：可表示為：w該算法有利于短作業(yè)該算法有利于短作業(yè): :等待時(shí)間相同等待時(shí)間相同, ,要求服務(wù)要求服務(wù)越短越短, ,其優(yōu)先權(quán)越高其優(yōu)先權(quán)越高. .w實(shí)現(xiàn)了先來(lái)先服務(wù)實(shí)現(xiàn)了先來(lái)先服務(wù): :要求服務(wù)時(shí)間相同時(shí)要求服務(wù)時(shí)間相同時(shí), ,作業(yè)作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間的優(yōu)先權(quán)決定于其等待時(shí)間. .w長(zhǎng)作業(yè)當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)長(zhǎng)作業(yè)當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí), ,優(yōu)先權(quán)便可以優(yōu)先權(quán)便可以升高升高, ,也可獲得處理機(jī)也可獲得處理機(jī). .313.3.3.3.1 1 進(jìn)程

23、調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式 1 1、進(jìn)程調(diào)度的任務(wù)、進(jìn)程調(diào)度的任務(wù) （1）保存處理機(jī)的現(xiàn)場(chǎng)消息；（2）按某種算法提取進(jìn)程；（3）把處理器分配給進(jìn)程。2 2、進(jìn)程調(diào)度機(jī)制、進(jìn)程調(diào)度機(jī)制（1）排隊(duì)器；（2）分派器；（3）上下文切換器。32就緒進(jìn)程進(jìn)程控制塊就緒隊(duì)列排隊(duì)器分派器上下文切換器CPU進(jìn)程調(diào)度機(jī)制來(lái)自其他狀態(tài)移出運(yùn)行進(jìn)程調(diào)度程序333 3、進(jìn)程調(diào)度方式、進(jìn)程調(diào)度方式1）非搶占方式2）搶占方式搶占方式遵循的主要原則有：優(yōu)先權(quán)原則；短進(jìn)程優(yōu)先原則；時(shí)間片原則。非搶占方式存在著很大的局限性，很難滿足交互性作業(yè)和實(shí)時(shí)任務(wù)的需求。341 1、輪轉(zhuǎn)法的基本原理、輪轉(zhuǎn)法的基本原理

24、在輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按FCFS策略排成一個(gè)就緒隊(duì)列。并保證就緒隊(duì)列中的所有進(jìn)程在確定的時(shí)間段內(nèi)，都能獲得一個(gè)時(shí)間片的處理機(jī)時(shí)間。2 2、進(jìn)程切換時(shí)機(jī)、進(jìn)程切換時(shí)機(jī) 1）一個(gè)時(shí)間片尚未用完； 2）一個(gè)時(shí)間片用完時(shí)。353 3、時(shí)間片大小的確定、時(shí)間片大小的確定 時(shí)間分配給進(jìn)程的時(shí)間片交互結(jié)束響應(yīng)時(shí)間 s時(shí)間片 q時(shí)間片大于交互時(shí)間q-s363 3、時(shí)間片大小的確定、時(shí)間片大小的確定 時(shí)間分配給進(jìn)程的時(shí)間片進(jìn)程被搶占時(shí)間片 q時(shí)間片小于交互時(shí)間分配給進(jìn)程的時(shí)間片交互完成其他進(jìn)程運(yùn)行37時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法 在分時(shí)系統(tǒng)中，系統(tǒng)使每個(gè)進(jìn)程依次地按時(shí)在分時(shí)系統(tǒng)中，系統(tǒng)使每個(gè)進(jìn)程依次地按時(shí)

25、間片輪流的方式執(zhí)行，就緒進(jìn)程按先來(lái)先服務(wù)原間片輪流的方式執(zhí)行，就緒進(jìn)程按先來(lái)先服務(wù)原則；當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出則；當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷，將它送就緒隊(duì)列的末尾，等待下一次時(shí)鐘中斷，將它送就緒隊(duì)列的末尾，等待下一次執(zhí)行。執(zhí)行。 時(shí)間片大小的確定因素：時(shí)間片大小的確定因素： a. a.系統(tǒng)對(duì)響應(yīng)時(shí)間的要求；系統(tǒng)對(duì)響應(yīng)時(shí)間的要求； b. b.就緒隊(duì)列中進(jìn)程的數(shù)目；就緒隊(duì)列中進(jìn)程的數(shù)目； c. c.系統(tǒng)的處理能力。系統(tǒng)的處理能力。 380 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 170 01 02 03 0

26、4 05 06 07 08 09 10 11 12 13 14 15 16 17A AB BD DC CE EA AB BD DC CE EA AB BD DC CE EA AC CE EA AB BC CE E時(shí)間片時(shí)間片q=1q=1時(shí)時(shí)時(shí)間片時(shí)間片q=4q=4時(shí)時(shí)39 作業(yè)情況調(diào)度算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43424RR(q=1)完成時(shí)間151216917周轉(zhuǎn)時(shí)8帶權(quán)周轉(zhuǎn)時(shí)間 3.753.673.533.333.46RR(q=4)完成時(shí)間47111317周轉(zhuǎn)時(shí)間46910138.4帶權(quán)周轉(zhuǎn)時(shí)間122.2553.332.540Turnarou

27、nd Time(周轉(zhuǎn)時(shí)間）周轉(zhuǎn)時(shí)間） Varies With The Time Quantum41 1 1. . 優(yōu)先級(jí)調(diào)度算法的類型優(yōu)先級(jí)調(diào)度算法的類型 非搶占式優(yōu)先級(jí)調(diào)度算法； 搶占式優(yōu)先級(jí)調(diào)度算法。2 2. . 優(yōu)先級(jí)的類型優(yōu)先級(jí)的類型 1）靜態(tài)優(yōu)先級(jí) 確定進(jìn)程優(yōu)先級(jí)大小的依據(jù)有：進(jìn)程類型、 進(jìn)程對(duì)資源的需求、用戶要求。 2）動(dòng)態(tài)優(yōu)先級(jí) 42 在實(shí)際的計(jì)算機(jī)系統(tǒng)中在實(shí)際的計(jì)算機(jī)系統(tǒng)中, ,不少都配置了幾種不少都配置了幾種類型的操作系統(tǒng)類型的操作系統(tǒng), ,既有批處理型作業(yè)既有批處理型作業(yè), ,又有處理又有處理交互型作業(yè)的分時(shí)操作系統(tǒng)交互型作業(yè)的分時(shí)操作系統(tǒng), ,前臺(tái)交互型進(jìn)程采前臺(tái)交互型進(jìn)

28、程采用時(shí)間片輪轉(zhuǎn)調(diào)度算法用時(shí)間片輪轉(zhuǎn)調(diào)度算法, ,后臺(tái)批處理型作業(yè)的進(jìn)后臺(tái)批處理型作業(yè)的進(jìn)程會(huì)采用優(yōu)先權(quán)高者優(yōu)先的算法程會(huì)采用優(yōu)先權(quán)高者優(yōu)先的算法. . 根據(jù)作業(yè)的性質(zhì)或類型的不同根據(jù)作業(yè)的性質(zhì)或類型的不同, ,將就緒進(jìn)程將就緒進(jìn)程隊(duì)列再分為若干個(gè)獨(dú)立子隊(duì)列隊(duì)列再分為若干個(gè)獨(dú)立子隊(duì)列, ,每個(gè)隊(duì)列采用一每個(gè)隊(duì)列采用一種算法種算法, ,不同的隊(duì)列采用不同的調(diào)度算法不同的隊(duì)列采用不同的調(diào)度算法. . 43Multilevel Queue Scheduling44 (1) (1)調(diào)度算法調(diào)度算法: :設(shè)置多個(gè)就緒隊(duì)列并為各個(gè)隊(duì)列賦予不同的優(yōu)先權(quán)設(shè)置多個(gè)就緒隊(duì)列并為各個(gè)隊(duì)列賦予不同的優(yōu)先權(quán): :第一個(gè)

29、隊(duì)列的優(yōu)先權(quán)最高第一個(gè)隊(duì)列的優(yōu)先權(quán)最高, ,依次降低依次降低; ;賦予各個(gè)不同隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不賦予各個(gè)不同隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同相同, ,優(yōu)先權(quán)越高的隊(duì)列進(jìn)程執(zhí)行的時(shí)間片越短優(yōu)先權(quán)越高的隊(duì)列進(jìn)程執(zhí)行的時(shí)間片越短. .新進(jìn)程進(jìn)入內(nèi)存后新進(jìn)程進(jìn)入內(nèi)存后, ,首先放到第一隊(duì)列的末尾首先放到第一隊(duì)列的末尾, ,按按FCFSFCFS原則排隊(duì)等待調(diào)度原則排隊(duì)等待調(diào)度. .如果執(zhí)行一個(gè)時(shí)間片不能完如果執(zhí)行一個(gè)時(shí)間片不能完成成, ,則轉(zhuǎn)入第二隊(duì)列的末尾則轉(zhuǎn)入第二隊(duì)列的末尾, ,同樣進(jìn)行同樣進(jìn)行. .僅當(dāng)?shù)谝魂?duì)列空閑時(shí)僅當(dāng)?shù)谝魂?duì)列空閑時(shí), ,調(diào)度程序才調(diào)度第二隊(duì)列中的調(diào)度程序才調(diào)度

30、第二隊(duì)列中的進(jìn)程運(yùn)行進(jìn)程運(yùn)行, ,依次類推依次類推. .4546(2)(2)調(diào)度性能調(diào)度性能: : 能夠滿足各種類型用戶的需要能夠滿足各種類型用戶的需要: :終端型作業(yè)終端型作業(yè): :交互作業(yè)交互作業(yè), ,作業(yè)通常較短小作業(yè)通常較短小, ,系統(tǒng)只系統(tǒng)只要能估計(jì)適合的時(shí)間片大小使作業(yè)要能估計(jì)適合的時(shí)間片大小使作業(yè)( (進(jìn)程進(jìn)程) )在第一在第一隊(duì)列所規(guī)定的時(shí)間片完成隊(duì)列所規(guī)定的時(shí)間片完成, ,便能滿足用戶便能滿足用戶. .短批處理作業(yè)用戶短批處理作業(yè)用戶: :通常會(huì)在第一或第二隊(duì)列完通常會(huì)在第一或第二隊(duì)列完成成, ,其周轉(zhuǎn)時(shí)間仍然較短其周轉(zhuǎn)時(shí)間仍然較短. .長(zhǎng)批處理作業(yè)長(zhǎng)批處理作業(yè): :依次按不

31、同的隊(duì)列和不同的時(shí)間依次按不同的隊(duì)列和不同的時(shí)間片直到完成片直到完成, ,用戶不必?fù)?dān)心其作業(yè)得不到處理用戶不必?fù)?dān)心其作業(yè)得不到處理. .47 UNIXUNIX和和OS/2OS/2操作系統(tǒng)采用了該調(diào)度算法操作系統(tǒng)采用了該調(diào)度算法. .該調(diào)度算法是目前公認(rèn)得較好的一種調(diào)度算該調(diào)度算法是目前公認(rèn)得較好的一種調(diào)度算法法. .48 1 1 保證調(diào)度算法保證調(diào)度算法: : 保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出的保證并不是優(yōu)先運(yùn)行，而是明確的性能保證，該算法可以做到調(diào)度的公平性。 2 2 公平公享調(diào)度算法公平公享調(diào)度算法: : 分配給每個(gè)進(jìn)程相同的處理機(jī)時(shí)間。 49 1 1 提供必要的調(diào)度信

32、息提供必要的調(diào)度信息: :w就緒時(shí)間就緒時(shí)間; ;w開(kāi)始截止時(shí)間和完成截止時(shí)間開(kāi)始截止時(shí)間和完成截止時(shí)間; ;w處理時(shí)間處理時(shí)間; ;w資源要求資源要求; ;w優(yōu)先級(jí)優(yōu)先級(jí). . 502 2 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 在實(shí)時(shí)系統(tǒng)中，通常有多個(gè)實(shí)時(shí)任務(wù)，如果處在實(shí)時(shí)系統(tǒng)中，通常有多個(gè)實(shí)時(shí)任務(wù)，如果處理機(jī)處理能力不強(qiáng)，則因處理機(jī)忙不過(guò)來(lái)而使得理機(jī)處理能力不強(qiáng)，則因處理機(jī)忙不過(guò)來(lái)而使得某些實(shí)時(shí)任務(wù)得不到及時(shí)處理。某些實(shí)時(shí)任務(wù)得不到及時(shí)處理。假定系統(tǒng)中有假定系統(tǒng)中有m m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為理時(shí)間可表示為Ci,Ci,周期時(shí)間可表示為周期時(shí)間可表

33、示為Pi,Pi,則在單則在單處理機(jī)情況下，必須滿足下面的限制條件系統(tǒng)才處理機(jī)情況下，必須滿足下面的限制條件系統(tǒng)才是可調(diào)度的是可調(diào)度的: :11miiiPC51 如果系統(tǒng)中有如果系統(tǒng)中有6 6個(gè)硬實(shí)時(shí)任務(wù)個(gè)硬實(shí)時(shí)任務(wù), ,它們的周期它們的周期時(shí)間都是時(shí)間都是5050ms,ms,而每次的處理時(shí)間為而每次的處理時(shí)間為1010ms,ms,則不則不能滿足限制條件能滿足限制條件, ,系統(tǒng)是不可調(diào)度的系統(tǒng)是不可調(diào)度的. . 解決的方法是提高系統(tǒng)的處理能力解決的方法是提高系統(tǒng)的處理能力: :w采用單處理機(jī)系統(tǒng)增強(qiáng)處理能力采用單處理機(jī)系統(tǒng)增強(qiáng)處理能力, ,減少每一任減少每一任務(wù)的處理時(shí)間務(wù)的處理時(shí)間; ;w采用

34、多處理機(jī)系統(tǒng)采用多處理機(jī)系統(tǒng): :多處理機(jī)數(shù)目為多處理機(jī)數(shù)目為N,N,則限制則限制條件改為條件改為: :NPCmiii1523.3.采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制: : 在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中, ,廣泛采用搶廣泛采用搶占機(jī)制。當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許占機(jī)制。當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行。這樣便可以滿足硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間入運(yùn)行。這樣便可以滿足硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。的要求。 小的實(shí)時(shí)系統(tǒng)，如果可以預(yù)知任務(wù)的開(kāi)始截止小的實(shí)時(shí)系統(tǒng)，如果可以預(yù)知任務(wù)的

35、開(kāi)始截止時(shí)間則實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度方式時(shí)間則實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度方式. .但但在設(shè)計(jì)調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較在設(shè)計(jì)調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，并在執(zhí)行關(guān)鍵性程序和臨界區(qū)后，能及時(shí)阻小，并在執(zhí)行關(guān)鍵性程序和臨界區(qū)后，能及時(shí)阻塞，釋放出處理機(jī)，使得其它程序的截止時(shí)間要塞，釋放出處理機(jī)，使得其它程序的截止時(shí)間要求能夠滿足。求能夠滿足。534 4 具有快速切換機(jī)制具有快速切換機(jī)制為了保證要求較高的硬實(shí)時(shí)任務(wù)能夠及時(shí)運(yùn)行，為了保證要求較高的硬實(shí)時(shí)任務(wù)能夠及時(shí)運(yùn)行，在實(shí)時(shí)系統(tǒng)中還應(yīng)該具有快速切換機(jī)制。該機(jī)在實(shí)時(shí)系統(tǒng)中還應(yīng)該具有快速切換機(jī)制。該機(jī)制具有如下能力：制

36、具有如下能力：（1 1）快速響應(yīng)外部中斷的能力）快速響應(yīng)外部中斷的能力. . (2) (2) 快速任務(wù)分派能力快速任務(wù)分派能力. .54 1. 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法(1)(1)非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法: :只適用于實(shí)時(shí)信息只適用于實(shí)時(shí)信息處理處理, ,群控系統(tǒng)，不適用于實(shí)時(shí)控制系統(tǒng)群控系統(tǒng)，不適用于實(shí)時(shí)控制系統(tǒng). .(2)(2)非搶占優(yōu)先權(quán)調(diào)度算法非搶占優(yōu)先權(quán)調(diào)度算法: :調(diào)度要求嚴(yán)格的實(shí)調(diào)度要求嚴(yán)格的實(shí)時(shí)任務(wù)，為之分配高的優(yōu)先權(quán)，使得其能夠時(shí)任務(wù)，為之分配高的優(yōu)先權(quán)，使得其能夠處于調(diào)度隊(duì)列之首。適用于一定要求的實(shí)時(shí)處于調(diào)度隊(duì)列之首。適用于一定要求的實(shí)時(shí)控制系

37、統(tǒng)控制系統(tǒng). .552 2 搶占式調(diào)度算法搶占式調(diào)度算法（1 1）基于時(shí)鐘中斷的搶占式優(yōu)先調(diào)度算法）基于時(shí)鐘中斷的搶占式優(yōu)先調(diào)度算法實(shí)時(shí)任務(wù)到達(dá)后，并不立即搶占處理機(jī)，優(yōu)先級(jí)高實(shí)時(shí)任務(wù)到達(dá)后，并不立即搶占處理機(jī)，優(yōu)先級(jí)高的任務(wù)在時(shí)鐘中斷到來(lái)時(shí)搶占處理機(jī)。一旦出現(xiàn)外的任務(wù)在時(shí)鐘中斷到來(lái)時(shí)搶占處理機(jī)。一旦出現(xiàn)外部中斷部中斷, ,只要當(dāng)前任務(wù)未處于臨界區(qū)只要當(dāng)前任務(wù)未處于臨界區(qū), ,便能立即剝奪便能立即剝奪當(dāng)前任務(wù)的執(zhí)行當(dāng)前任務(wù)的執(zhí)行, ,把處理機(jī)分配給請(qǐng)求中斷的緊迫把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)任務(wù). (3). (3)基于時(shí)鐘中斷搶占的優(yōu)先級(jí)調(diào)度算法基于時(shí)鐘中斷搶占的優(yōu)先級(jí)調(diào)度算法: :時(shí)時(shí)鐘中

38、斷到來(lái)時(shí)鐘中斷到來(lái)時(shí), ,立即搶占處理機(jī)立即搶占處理機(jī). .563.4.3.4.3 3 最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先EDFEDF算法算法 1 1 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)1342EDF算法用于非搶占調(diào)度方式開(kāi)始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)12341234573.4.3.4.4 4 最低松弛度優(yōu)先最低松弛度優(yōu)先LLFLLF算法算法 該算法在確定任務(wù)的優(yōu)先級(jí)時(shí)，根據(jù)的是任務(wù)的緊急（或松弛）程度。任務(wù)緊急情況愈高，賦予該任務(wù)的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。tt1t2t3t4t5t6t7t801030407080A1(10)A2(10)A3(10)A4(10

39、)B1(20)B1(5)B2(15)B2(10)利用利用ELLFELLF算法進(jìn)行調(diào)度的情況算法進(jìn)行調(diào)度的情況583.4.3.4.5 5 優(yōu)先級(jí)倒置優(yōu)先級(jí)倒置 優(yōu)先級(jí)倒置的形成優(yōu)先級(jí)倒置的形成 高優(yōu)先級(jí)P1因共享著“臨界資源”的低優(yōu)先級(jí)進(jìn)程P3被阻塞了，又因?yàn)榱硪粋€(gè)地優(yōu)先級(jí)進(jìn)程P2的存在而延長(zhǎng)了P1被阻塞的時(shí)間。由此所產(chǎn)生的“優(yōu)先級(jí)倒置”。2.2. 優(yōu)先級(jí)倒置的解決方法優(yōu)先級(jí)倒置的解決方法 一種簡(jiǎn)單的解決方法是規(guī)定：P3在進(jìn)入臨界區(qū)后P3所占用的處理機(jī)就不允許被搶占。 一個(gè)比較實(shí)用的方法是建立在動(dòng)態(tài)優(yōu)先級(jí)繼承基礎(chǔ)上的?！皟?yōu)先級(jí)倒置”即高優(yōu)先級(jí)進(jìn)程（或線程）被低優(yōu)先級(jí)進(jìn)程（或線程）延遲或阻塞。59

40、 調(diào)度部分例題調(diào)度部分例題(1)(1)設(shè)一組作業(yè)，他們的提交時(shí)間及運(yùn)行時(shí)間如下：設(shè)一組作業(yè)，他們的提交時(shí)間及運(yùn)行時(shí)間如下： 作業(yè)名作業(yè)名 提交時(shí)間提交時(shí)間 運(yùn)行時(shí)間（分鐘）運(yùn)行時(shí)間（分鐘） A 8A 8：00 7000 70 B 8B 8：40 3040 30 C 8C 8：50 10 50 10 D 9D 9：10 5 10 5 在單道方式下，采用短作業(yè)優(yōu)先調(diào)度算法，試指在單道方式下，采用短作業(yè)優(yōu)先調(diào)度算法，試指出作業(yè)的執(zhí)行順序和周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間。出作業(yè)的執(zhí)行順序和周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間。60作業(yè)的執(zhí)行順序?yàn)樽鳂I(yè)的執(zhí)行順序?yàn)? :A,D,C,B.A,D,C,B.作業(yè)作業(yè)名名提交時(shí)提交時(shí)

41、間間運(yùn)行運(yùn)行時(shí)間時(shí)間(分鐘分鐘)開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間完成時(shí)完成時(shí)間間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間(分鐘分鐘)帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間(分鐘分鐘)A8:00708:009:10701B8:40309:259:55752.5C8:50109:159:25353.5D9:1059:109:155161 (2) (2) 設(shè)有四道作業(yè)，它們的到提交時(shí)間和執(zhí)行時(shí)設(shè)有四道作業(yè)，它們的到提交時(shí)間和執(zhí)行時(shí)間如下：間如下： 作業(yè)號(hào)作業(yè)號(hào) 提交時(shí)間提交時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 A 9.0 2.0A 9.0 2.0 B 9.2 1.0B 9.2 1.0 C 9.4 0.5 C 9.4 0.5 D 9.5 0.3 D 9.5 0

42、.3 試計(jì)算在單道程序設(shè)計(jì)環(huán)境下，采用先來(lái)先服務(wù)試計(jì)算在單道程序設(shè)計(jì)環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法時(shí)它們的調(diào)度調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法時(shí)它們的調(diào)度序列及平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。序列及平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 62解：若采用先來(lái)先服務(wù)調(diào)度算法，其調(diào)度順序解：若采用先來(lái)先服務(wù)調(diào)度算法，其調(diào)度順序?yàn)闉锳 A，B B，C C，D D。 作業(yè)作業(yè)號(hào)號(hào)提交提交時(shí)間時(shí)間運(yùn)行時(shí)運(yùn)行時(shí)間間開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間完成時(shí)完成時(shí)間間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A9.02.09.011.02.01.0B9.21.011.012.02.82.8C9.40.512.01

43、2.53.16.2D9.50.312.512.83.311.063平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T=T=（2.0+2.8+3.1+3.32.0+2.8+3.1+3.3）/4=2.8/4=2.8平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W=W=（1+2.8+6.2+111+2.8+6.2+11）/4=5.25/4=5.2564若采用短作業(yè)優(yōu)先調(diào)度算法，其調(diào)度順序?yàn)槿舨捎枚套鳂I(yè)優(yōu)先調(diào)度算法，其調(diào)度順序?yàn)锳 A，D D，C C，B B。 作業(yè)作業(yè)號(hào)號(hào)提交時(shí)提交時(shí)間間運(yùn)行運(yùn)行時(shí)間時(shí)間開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間完成時(shí)完成時(shí)間間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A9.02.09.011.02.01.0D9.50.31

44、1.011.31.86.0C9.40.511.311.82.44.8B9.21.011.812.83.63.665平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T=T=（2.0+1.8+2.4+3.62.0+1.8+2.4+3.6）/4=2.45/4=2.45平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W=W=（1+6+4.8+3.61+6+4.8+3.6）/4=3.85/4=3.8566 (3) (3) 設(shè)有五道進(jìn)程設(shè)有五道進(jìn)程A,B,C,D,E,A,B,C,D,E,幾乎同時(shí)提交，它幾乎同時(shí)提交，它們的運(yùn)行時(shí)間及優(yōu)先級(jí)分別為們的運(yùn)行時(shí)間及優(yōu)先級(jí)分別為: : 作業(yè)號(hào)作業(yè)號(hào) 運(yùn)行時(shí)間運(yùn)行時(shí)間( (分鐘分鐘) ) 優(yōu)先級(jí)優(yōu)先級(jí) A

45、 10 24A 10 24 B 6 30B 6 30 C 2 21 C 2 21 D 4 20D 4 20 E 8 28 E 8 28假如數(shù)字越大優(yōu)先級(jí)越高假如數(shù)字越大優(yōu)先級(jí)越高, ,試計(jì)算采用優(yōu)先級(jí)調(diào)度試計(jì)算采用優(yōu)先級(jí)調(diào)度算法和時(shí)間片為算法和時(shí)間片為1 1分鐘的輪轉(zhuǎn)調(diào)度算法的平均周分鐘的輪轉(zhuǎn)調(diào)度算法的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間. .67進(jìn)程進(jìn)程號(hào)號(hào)運(yùn)行運(yùn)行時(shí)間時(shí)間優(yōu)先優(yōu)先級(jí)級(jí)開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A1024024242.4B6300661.0C2210262613D420030307.5E828014143

46、.6優(yōu)先級(jí)調(diào)度算法調(diào)度順序?yàn)閮?yōu)先級(jí)調(diào)度算法調(diào)度順序?yàn)锽 B，E E，A A，C,DC,D。平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間(24+6+26+30+14)/5=20(24+6+26+30+14)/5=20(分鐘分鐘) )68時(shí)間片調(diào)度算法調(diào)度順序?yàn)闀r(shí)間片調(diào)度算法調(diào)度順序?yàn)? :A B C D E A B C D E A B D A B C D E A B C D E A B D 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 E A B D E A B E A B E A EE A B D E A B E A B E A E13 14

47、15 16 17 18 19 20 21 22 23 24 2513 14 15 16 17 18 19 20 21 22 23 24 25A E A AA E A A27 28 29 3027 28 29 3069平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間(30+22+7+16+28)/5=20.6(30+22+7+16+28)/5=20.6(分鐘分鐘) )作業(yè)作業(yè)號(hào)號(hào)運(yùn)行運(yùn)行時(shí)間時(shí)間優(yōu)先優(yōu)先級(jí)級(jí)開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A1024030303.0B630022223.67C2210773.5D420016164.0E828028283.5703.5.13

48、.5.1 資源問(wèn)題資源問(wèn)題 在系統(tǒng)中有許多不同類型的資源，其中可以引起死鎖的主要是，需要采用互斥訪問(wèn)方法的、不可以被搶占的資源。 可重用性資源；可重用性資源； 消耗性資源；消耗性資源； 可搶占性資源；可搶占性資源； 不可搶占性資源。不可搶占性資源。 713.5.23.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖(1)(1)競(jìng)爭(zhēng)資源競(jìng)爭(zhēng)資源 資源分為資源分為: :可剝奪性可剝奪性: :如處理機(jī)如處理機(jī). . 非剝奪性非剝奪性: :如打印機(jī)如打印機(jī). .n競(jìng)爭(zhēng)非剝奪性資源引起死鎖競(jìng)爭(zhēng)非剝奪性資源引起死鎖: : 例例: :兩個(gè)進(jìn)程兩個(gè)進(jìn)程P1,P2,P1,P2,兩個(gè)非剝奪性資源兩個(gè)非剝奪性資源R1,

49、R2;R1,R2; P1: P1: 得到得到R1;R1; P2:P2:得到得到R2;R2; 申請(qǐng)申請(qǐng)R2;R2; 申請(qǐng)申請(qǐng)R1;R1;72共享文件時(shí)的死鎖情況P1P1F1F2P2P2P1Open(f1,w);Open(f2,w);P2Open(f2,w);Open(f1,w);73w競(jìng)爭(zhēng)臨時(shí)性資源引起死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起死鎖: :臨時(shí)性資源臨時(shí)性資源: :一個(gè)進(jìn)程產(chǎn)生一個(gè)進(jìn)程產(chǎn)生, ,另一個(gè)進(jìn)程暫時(shí)使用另一個(gè)進(jìn)程暫時(shí)使用. .例例: :進(jìn)程進(jìn)程P1,P2,P3,P1,P2,P3,臨時(shí)資源臨時(shí)資源S1,S2,S3;S1,S2,S3; P1( P1(產(chǎn)生產(chǎn)生S1,S1,需要需要S3);S3);

50、P2( P2(產(chǎn)生產(chǎn)生S2,S2,需要需要S1);S1); P3( P3(產(chǎn)生產(chǎn)生S3,S3,需要需要S2);S2);74進(jìn)程之間通信時(shí)的死鎖P1P1m3m1P P3 3P1 send(P2,m1); receive(P3,m3);P2 send(P3,m2); receive(P1,m1);P3 send(P1,m3); receive(P2,m2);P2P2m275如果按順序如果按順序: : P1: P1:Release(S1);Request(S3);Release(S1);Request(S3); P2: P2:Release(S2);Request(S1);Release(S2);R

51、equest(S1); P3: P3:Release(S3);Request(S2);Release(S3);Request(S2);不會(huì)發(fā)生死鎖不會(huì)發(fā)生死鎖. .如果按順序如果按順序: : P1: P1:Request(S3);Release(S1);Request(S3);Release(S1); P2: P2:Request(S1);Release(S2);Request(S1);Release(S2); P3: P3:Request(S2);Release(S3);Request(S2);Release(S3);可能會(huì)發(fā)生死鎖可能會(huì)發(fā)生死鎖. .76(2)(2)進(jìn)程推進(jìn)順序非法進(jìn)程推進(jìn)

52、順序非法: :兩個(gè)進(jìn)程兩個(gè)進(jìn)程P1,P2,P1,P2,兩個(gè)資源兩個(gè)資源R1,R2;R1,R2;如果如果: :P1 Request(P1 Request(R1R1); ); P1 P1 Request(R2);Request(R2); P1 Release(R1); P1 Release(R1); P1P1 Release( Release(R2R2) ) P2 Request( P2 Request(R2R2); ); P2 P2 Request(R1);Request(R1); P2 Release(R2); P2 Release(R2); P2P2 Release( Release(R1R

53、1););不會(huì)發(fā)生死鎖不會(huì)發(fā)生死鎖. .77如果如果: :P1 Request(P1 Request(R1R1); ); P2 P2 Request(R2);Request(R2); P1P1 Request( Request(R2R2); ); P2 P2 Request(R1); Request(R1); 則可能會(huì)發(fā)生死鎖則可能會(huì)發(fā)生死鎖. .如果如果: :P2 P2 Request(R2);Request(R2); P1 Request(P1 Request(R1R1); ); P2 P2 Request(R1); Request(R1); P1P1 Request( Request(R

54、2R2); ); 則可能會(huì)發(fā)生死鎖則可能會(huì)發(fā)生死鎖. . 總之總之, ,系統(tǒng)進(jìn)入不安全區(qū)則可能會(huì)發(fā)生死鎖系統(tǒng)進(jìn)入不安全區(qū)則可能會(huì)發(fā)生死鎖. . 78 P P1 1Req(RReq(R1 1) P) P1 1Req(RReq(R2 2) P) P1 1Rel(RRel(R1 1) P) P1 1Rel(RRel(R2 2) ) P P2 2Rel(RRel(R1 1) )P P2 2Rel(RRel(R2 2) ) P P2 2Req(RReq(R1 1) ) P P2 2Req(RReq(R2 2) )1 12 23 34 4不安全區(qū)不安全區(qū)D D79定義：定義： 指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的

55、一種僵指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。再向前推進(jìn)。 80產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 同時(shí)具備下列四個(gè)必要條同時(shí)具備下列四個(gè)必要條件則會(huì)產(chǎn)生死鎖件則會(huì)產(chǎn)生死鎖: : (1) (1)互斥條件；互斥條件； (2) (2)請(qǐng)求和保持條件；請(qǐng)求和保持條件； (3) (3)不剝奪條件；不剝奪條件； (4) (4)環(huán)路等待條件；環(huán)路等待條件；81 處理死鎖的基本方法處理死鎖的基本方法(1)(1)預(yù)防死鎖預(yù)防死鎖: :事先破壞死鎖的四個(gè)必要條件事先破壞死鎖的四個(gè)必要條件. .(2)(2)避免死鎖避免死鎖: :資

56、源分配中防止系統(tǒng)進(jìn)入不安全區(qū)資源分配中防止系統(tǒng)進(jìn)入不安全區(qū). .(3)(3)檢測(cè)死鎖檢測(cè)死鎖: :在系統(tǒng)的運(yùn)行過(guò)程中檢測(cè)死鎖的發(fā)在系統(tǒng)的運(yùn)行過(guò)程中檢測(cè)死鎖的發(fā)生生, ,并確定進(jìn)程與有關(guān)的資源并確定進(jìn)程與有關(guān)的資源, ,采取措施清除死鎖采取措施清除死鎖. .(4)(4)解除死鎖解除死鎖: :將進(jìn)程從死鎖轉(zhuǎn)態(tài)解脫出來(lái)將進(jìn)程從死鎖轉(zhuǎn)態(tài)解脫出來(lái). .82基本思想基本思想: : 通過(guò)分析系統(tǒng)產(chǎn)生死鎖的必要條件，通過(guò)分析系統(tǒng)產(chǎn)生死鎖的必要條件，然后使之不成立或破壞條件。然后使之不成立或破壞條件。3.6 3.6 預(yù)防死鎖預(yù)防死鎖833 3.6.1.6.1 破壞破壞“請(qǐng)求和保持請(qǐng)求和保持”條件條件: : 系統(tǒng)

57、要求所有進(jìn)程要一次性的申請(qǐng)?jiān)谡麄€(gè)運(yùn)系統(tǒng)要求所有進(jìn)程要一次性的申請(qǐng)?jiān)谡麄€(gè)運(yùn)行過(guò)程所需要得全部資源行過(guò)程所需要得全部資源, ,在整個(gè)運(yùn)行期間在整個(gè)運(yùn)行期間, ,再不再不會(huì)提出資源要求會(huì)提出資源要求, ,從而摒棄了請(qǐng)求條件從而摒棄了請(qǐng)求條件. . 優(yōu)點(diǎn)優(yōu)點(diǎn): :簡(jiǎn)單簡(jiǎn)單, ,易于實(shí)現(xiàn)易于實(shí)現(xiàn), ,安全安全. . 缺點(diǎn)缺點(diǎn): :資源嚴(yán)重浪費(fèi)資源嚴(yán)重浪費(fèi), ,進(jìn)程延遲運(yùn)行進(jìn)程延遲運(yùn)行. .死鎖的預(yù)防死鎖的預(yù)防843 3.6.2.6.2 破壞破壞“不可搶占不可搶占”條件條件: : 進(jìn)程在需要資源時(shí)才提出請(qǐng)求進(jìn)程在需要資源時(shí)才提出請(qǐng)求, ,一個(gè)已經(jīng)保一個(gè)已經(jīng)保持了某些資源的進(jìn)程當(dāng)它再提出新的資源要求持了某些

58、資源的進(jìn)程當(dāng)它再提出新的資源要求而不能立即得到滿足時(shí)而不能立即得到滿足時(shí), ,必須釋放它已經(jīng)保持的必須釋放它已經(jīng)保持的所有資源待以后需要時(shí)再申請(qǐng)所有資源待以后需要時(shí)再申請(qǐng). .也就是認(rèn)為資源也就是認(rèn)為資源被剝奪了被剝奪了. . 缺點(diǎn)缺點(diǎn): :實(shí)施復(fù)雜實(shí)施復(fù)雜, ,代價(jià)大代價(jià)大. . 反復(fù)申請(qǐng)和釋放資源反復(fù)申請(qǐng)和釋放資源, ,使進(jìn)程的執(zhí)行使進(jìn)程的執(zhí)行 無(wú)限地推遲無(wú)限地推遲, ,延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間, , 增加了系統(tǒng)開(kāi)銷增加了系統(tǒng)開(kāi)銷, ,降低了系統(tǒng)吞吐量降低了系統(tǒng)吞吐量. .853.6.3 3.6.3 破壞破壞“循環(huán)循環(huán)等待等待”條件條件: : 系統(tǒng)將所有資源按類型進(jìn)行線性排

59、隊(duì)系統(tǒng)將所有資源按類型進(jìn)行線性排隊(duì), ,并賦予并賦予不同的序號(hào)不同的序號(hào), ,所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按資所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按資源序號(hào)遞增的次序提出源序號(hào)遞增的次序提出, ,在資源分配圖中不可能再在資源分配圖中不可能再出現(xiàn)環(huán)路出現(xiàn)環(huán)路. . 優(yōu)點(diǎn)優(yōu)點(diǎn): :資源利用率和系統(tǒng)吞吐量提高資源利用率和系統(tǒng)吞吐量提高. . 缺點(diǎn)缺點(diǎn): :資源序號(hào)必須相對(duì)穩(wěn)定資源序號(hào)必須相對(duì)穩(wěn)定, ,新設(shè)備類型增新設(shè)備類型增 加難加難. . 進(jìn)程使用資源的順序與系統(tǒng)規(guī)定的順序進(jìn)程使用資源的順序與系統(tǒng)規(guī)定的順序 不同造成資源浪費(fèi)不同造成資源浪費(fèi). . 限制用戶簡(jiǎn)單限制用戶簡(jiǎn)單, ,自主編程自主編程. . 86

60、 3. 3.7 7. .1 1 系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài)(1)(1)安全狀態(tài)安全狀態(tài): : 只要系統(tǒng)始終處于安全狀態(tài)只要系統(tǒng)始終處于安全狀態(tài), ,便可避免死鎖便可避免死鎖. . 在系統(tǒng)資源分配前在系統(tǒng)資源分配前, ,先計(jì)算系統(tǒng)的安全性先計(jì)算系統(tǒng)的安全性. .若若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài), ,便將資源便將資源分配給進(jìn)程分配給進(jìn)程, ,否則進(jìn)程等待否則進(jìn)程等待. . 3.3.7 7 避免死鎖避免死鎖87安全狀態(tài)定義安全狀態(tài)定義: : 指系統(tǒng)按某種順序指系統(tǒng)按某種順序 Pn，來(lái)為每來(lái)為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)個(gè)進(jìn)程分配其所需資源，