1、第三章處理機(jī)調(diào)度與死鎖 第三章處理機(jī)調(diào)度與死鎖 3.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.3 調(diào)度算法調(diào)度算法3.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法3.7 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除 第三章處理機(jī)調(diào)度與死鎖 3.1處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度3.1.1高級(jí)調(diào)度高級(jí)調(diào)度High Level Scheduling)作業(yè)調(diào)度或長(zhǎng)程調(diào)度作業(yè)調(diào)度或長(zhǎng)程調(diào)度LongTerm Scheduling）1作業(yè)和作業(yè)步作業(yè)和作業(yè)步

2、(1) 作業(yè)作業(yè)(Job)。作業(yè)不僅包含了通常的程序和數(shù)據(jù)，而且。作業(yè)不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說(shuō)明書，系統(tǒng)根據(jù)該說(shuō)明書來(lái)對(duì)程序的運(yùn)還應(yīng)配有一份作業(yè)說(shuō)明書，系統(tǒng)根據(jù)該說(shuō)明書來(lái)對(duì)程序的運(yùn)行進(jìn)行控制。行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。 第三章處理機(jī)調(diào)度與死鎖 (2) 作業(yè)步(Job Step)。作業(yè)的每一個(gè)順序加工步驟稱為一個(gè)作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步的輸入。例如，一個(gè)典型的作業(yè)可分成三個(gè)作業(yè)步： “編譯作業(yè)步，通過(guò)執(zhí)行編譯程序?qū)υ闯绦蜻M(jìn)行編譯

3、，產(chǎn)生若干個(gè)目標(biāo)程序段； “連結(jié)裝配作業(yè)步，將“編譯作業(yè)步所產(chǎn)生的若干個(gè)目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序； “運(yùn)轉(zhuǎn)作業(yè)步，將可執(zhí)行的目標(biāo)程序讀入內(nèi)存并控制其運(yùn)行。(3) 作業(yè)流。若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)行處理，于是便形成了處理作業(yè)流。 第三章處理機(jī)調(diào)度與死鎖 2 2作業(yè)控制塊作業(yè)控制塊JCB(Job Control Block)JCB(Job Control Block)作業(yè)控制塊是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系作業(yè)控制塊是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)

4、度所需的全部信息。在在JCBJCB中通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳中通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型戶、作業(yè)類型(CPU (CPU 繁忙型、繁忙型、I/O I/O 繁忙型、批量型、終端型繁忙型、批量型、終端型) )、作業(yè)狀態(tài)、調(diào)度信息作業(yè)狀態(tài)、調(diào)度信息( (優(yōu)先級(jí)、作業(yè)已運(yùn)行時(shí)間優(yōu)先級(jí)、作業(yè)已運(yùn)行時(shí)間) )、資源需求、資源需求( (預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小、要求預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小、要求I/OI/O設(shè)備的類型和數(shù)量設(shè)備的類型和數(shù)量等等) )、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間

5、、資源使用情況等。出時(shí)間、資源使用情況等。 作業(yè)進(jìn)入系統(tǒng)建立作業(yè)進(jìn)入系統(tǒng)建立JCBJCB，插入相應(yīng)的隊(duì)列。作業(yè)調(diào)，插入相應(yīng)的隊(duì)列。作業(yè)調(diào)度程序調(diào)度作業(yè)裝入內(nèi)存。在作業(yè)運(yùn)行期間，按照度程序調(diào)度作業(yè)裝入內(nèi)存。在作業(yè)運(yùn)行期間，按照J(rèn)CBJCB中的信中的信息對(duì)作業(yè)進(jìn)行控制。作業(yè)執(zhí)行結(jié)束時(shí)，系統(tǒng)負(fù)責(zé)回收分配給息對(duì)作業(yè)進(jìn)行控制。作業(yè)執(zhí)行結(jié)束時(shí)，系統(tǒng)負(fù)責(zé)回收分配給它的資源，撤消它的作業(yè)控制塊。它的資源，撤消它的作業(yè)控制塊。 第三章處理機(jī)調(diào)度與死鎖 3作業(yè)調(diào)度作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建

6、進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。因此，有時(shí)也把作業(yè)調(diào)度稱為接納調(diào)度(Admission Scheduling)。 第三章處理機(jī)調(diào)度與死鎖 在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。 1) 決定接納多少個(gè)作業(yè)取決于多道程序度(Degree of Multiprogramming)，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。 當(dāng)內(nèi)存中同時(shí)運(yùn)行的作業(yè)數(shù)目太多時(shí)，可能會(huì)影響到系統(tǒng)的服務(wù)質(zhì)量，比如，使周轉(zhuǎn)時(shí)間太長(zhǎng)。但如果在內(nèi)存中同時(shí)運(yùn)行作業(yè)的數(shù)量太少時(shí)，又會(huì)導(dǎo)致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低。 多道程序度的確定應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度等情況做適當(dāng)?shù)恼壑浴?2) 決定接納哪

7、些作業(yè) 取決于所采用的調(diào)度算法。第三章處理機(jī)調(diào)度與死鎖 在批處理系統(tǒng)中，需要有作業(yè)調(diào)度的過(guò)程，以便將它們?cè)谂幚硐到y(tǒng)中，需要有作業(yè)調(diào)度的過(guò)程，以便將它們分批地裝入內(nèi)存。分批地裝入內(nèi)存。分時(shí)系統(tǒng)中無(wú)需配置作業(yè)調(diào)度機(jī)制，但需要有某些限制分時(shí)系統(tǒng)中無(wú)需配置作業(yè)調(diào)度機(jī)制，但需要有某些限制性措施來(lái)限制進(jìn)入系統(tǒng)的用戶數(shù)。即，如果系統(tǒng)尚未飽和，性措施來(lái)限制進(jìn)入系統(tǒng)的用戶數(shù)。即，如果系統(tǒng)尚未飽和，將接納所有授權(quán)用戶，否則，將拒絕接納。將接納所有授權(quán)用戶，否則，將拒絕接納。在實(shí)時(shí)系統(tǒng)中通常也不需要作業(yè)調(diào)度。在實(shí)時(shí)系統(tǒng)中通常也不需要作業(yè)調(diào)度。 第三章處理機(jī)調(diào)度與死鎖 3.1.2 3.1.2 低級(jí)調(diào)度低級(jí)調(diào)度Low

8、 Level Scheduling)Low Level Scheduling)進(jìn)程調(diào)度、短程調(diào)度進(jìn)程調(diào)度、短程調(diào)度(ShortTerm Scheduling)(ShortTerm Scheduling)調(diào)度的對(duì)象是進(jìn)程調(diào)度的對(duì)象是進(jìn)程( (或內(nèi)核級(jí)線程或內(nèi)核級(jí)線程) )1 1低級(jí)調(diào)度的功能低級(jí)調(diào)度的功能調(diào)度用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程調(diào)度用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程( (或內(nèi)核級(jí)線程，為敘或內(nèi)核級(jí)線程，為敘述方便，以后只寫進(jìn)程述方便，以后只寫進(jìn)程) )應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。行把處理機(jī)分配給該進(jìn)程的具體操作。低級(jí)調(diào)度程序

9、是操作系統(tǒng)最為核心的部分，低級(jí)調(diào)度策略低級(jí)調(diào)度程序是操作系統(tǒng)最為核心的部分，低級(jí)調(diào)度策略的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能第三章處理機(jī)調(diào)度與死鎖 低級(jí)調(diào)度的過(guò)程如下： (1) 保存處理機(jī)的現(xiàn)場(chǎng)信息。如程序計(jì)數(shù)器、多個(gè)通用寄存器中的內(nèi)容等，將它們送入該進(jìn)程的進(jìn)程控制塊(PCB)中的相應(yīng)單元。(2) 按某種算法選取進(jìn)程。低級(jí)調(diào)度程序按某種算法，從就緒隊(duì)列中選取一個(gè)進(jìn)程，把它的狀態(tài)改為運(yùn)行狀態(tài)，并準(zhǔn)備把處理機(jī)分配給它。 (3) 把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。此時(shí)需為選中的進(jìn)程恢復(fù)處理機(jī)現(xiàn)場(chǎng)，即把選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場(chǎng)

10、的信息裝入處理器相應(yīng)的各個(gè)寄存器中，把處理器的控制權(quán)交給該進(jìn)程，讓它從取出的斷點(diǎn)處開始繼續(xù)運(yùn)行。 第三章處理機(jī)調(diào)度與死鎖 2 2進(jìn)程調(diào)度中的三個(gè)基本機(jī)制進(jìn)程調(diào)度中的三個(gè)基本機(jī)制（1 1） 排隊(duì)器。排隊(duì)器。（2 2） 分派器分派器( (分派程序分派程序) )。（3 3上下文切換機(jī)制。當(dāng)對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)發(fā)生上下文切換機(jī)制。當(dāng)對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)發(fā)生兩對(duì)上下文切換操作。在第一對(duì)上下文切換時(shí)，操作系統(tǒng)將兩對(duì)上下文切換操作。在第一對(duì)上下文切換時(shí)，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二對(duì)上下文切換時(shí)，將移

11、出分派程序，而派程序運(yùn)行；在第二對(duì)上下文切換時(shí)，將移出分派程序，而把新選進(jìn)程的把新選進(jìn)程的CPUCPU現(xiàn)場(chǎng)信息裝入到處理機(jī)的各個(gè)相應(yīng)寄存器中?，F(xiàn)場(chǎng)信息裝入到處理機(jī)的各個(gè)相應(yīng)寄存器中。 應(yīng)當(dāng)指出，上下文切換將花去不少的處理機(jī)時(shí)間，即使應(yīng)當(dāng)指出，上下文切換將花去不少的處理機(jī)時(shí)間，即使是現(xiàn)代計(jì)算機(jī)，每一次上下文切換大約需要花費(fèi)幾毫秒的時(shí)是現(xiàn)代計(jì)算機(jī)，每一次上下文切換大約需要花費(fèi)幾毫秒的時(shí)間，該時(shí)間大約可執(zhí)行上千條指令。間，該時(shí)間大約可執(zhí)行上千條指令。第三章處理機(jī)調(diào)度與死鎖 3 3進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式進(jìn)程調(diào)度可采用下述兩種調(diào)度方式。進(jìn)程調(diào)度可采用下述兩種調(diào)度方式。1) 1) 非搶占方式非搶占方式(

12、Nonpreemptive Mode)(Nonpreemptive Mode)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長(zhǎng)時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)椴还芩\(yùn)行多長(zhǎng)時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其時(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他

13、進(jìn)程。給其他進(jìn)程。 第三章處理機(jī)調(diào)度與死鎖 在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為如下幾個(gè)：(1) 正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；(2) 執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；(3) 在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作，如P操作(wait操作)、Block原語(yǔ)等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。 第三章處理機(jī)調(diào)度與死鎖 2) 搶占方式(Preemptive Mode)這種調(diào)度方式允許調(diào)度

14、程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。 搶占方式的優(yōu)點(diǎn)是，可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。第三章處理機(jī)調(diào)度與死鎖 搶占調(diào)度方式是基于一定原則的，主要有如下幾條：搶占調(diào)度方式是基于一定原則的，主要有如下幾條： (1) 優(yōu)先權(quán)原則。就緒的優(yōu)先權(quán)高的進(jìn)程有權(quán)搶占低優(yōu)先權(quán)優(yōu)先權(quán)原則。就緒的優(yōu)先權(quán)高的進(jìn)程有權(quán)搶占低優(yōu)先權(quán)進(jìn)程的處理機(jī)。進(jìn)程的處理機(jī)。(2) 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先原則。就緒的短作業(yè)優(yōu)先原則。就緒的短作業(yè)

15、(進(jìn)程進(jìn)程)可以搶占可以搶占當(dāng)前較長(zhǎng)作業(yè)當(dāng)前較長(zhǎng)作業(yè)(進(jìn)程進(jìn)程)的處理機(jī)。的處理機(jī)。(3) 時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行，當(dāng)一個(gè)時(shí)間片時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。 第三章處理機(jī)調(diào)度與死鎖 3.1.3 3.1.3 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate Level Scheduling)(Intermediate Level Scheduling)又

16、稱中程調(diào)度又稱中程調(diào)度(Medium-Term Scheduling)(Medium-Term Scheduling)。引入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)引入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。吞吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí)，由當(dāng)這些進(jìn)程重又具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來(lái)決定把外存上的那些又具

17、備運(yùn)行條件的就緒進(jìn)程中級(jí)調(diào)度來(lái)決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能。 第三章處理機(jī)調(diào)度與死鎖 在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10100 ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時(shí)間，進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(gè)(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)(批)作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周

18、期較長(zhǎng)，大約幾分鐘一次，因此把它稱為長(zhǎng)程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。中級(jí)調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。 運(yùn)行頻率：高級(jí)調(diào)度中級(jí)調(diào)度PjPiPj，則立即停止，則立即停止PjPj的執(zhí)行，的執(zhí)行，做進(jìn)程切換，使做進(jìn)程切換，使i i進(jìn)程投入執(zhí)行。進(jìn)程投入執(zhí)行。搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。高的批處理和分時(shí)系統(tǒng)中。第三章處理機(jī)調(diào)度與死鎖 2 2

19、優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型對(duì)于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用對(duì)于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)，還是用動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先靜態(tài)優(yōu)先權(quán)，還是用動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。權(quán)。1) 1) 靜態(tài)優(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)靜態(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)表示的，一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如，例如，0 07 7或或0 0255255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)，中的某一整數(shù)，又把該整數(shù)稱

20、為優(yōu)先數(shù)，只是具體用法各異：有的系統(tǒng)用只是具體用法各異：有的系統(tǒng)用“0 0表示最高優(yōu)先權(quán)，當(dāng)數(shù)表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。 第三章處理機(jī)調(diào)度與死鎖 確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：(1) 進(jìn)程類型。(2) 進(jìn)程對(duì)資源的需求(3) 用戶要求。靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進(jìn)程)長(zhǎng)期沒有被調(diào)度的情況。因此，僅在要求不高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。 第三章處理機(jī)調(diào)度與死鎖 2) 動(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)或隨其等待時(shí)間的增加而改變的，

21、以便獲得更好的調(diào)度性能。例：就緒隊(duì)列中有三個(gè)進(jìn)程P1、P2和P3，隨其等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)以速率a增加。 若三個(gè)進(jìn)程具有相同的優(yōu)先權(quán)初值，則最先進(jìn)入就緒隊(duì)列的進(jìn)程如P1最先獲得處理機(jī)，此即FCFS算法； 若所有進(jìn)程具有不相同的優(yōu)先權(quán)初值如P1P2P3），則優(yōu)先權(quán)低的進(jìn)程P1在等待足夠長(zhǎng)的時(shí)間后，其優(yōu)先權(quán)便可升至最高從而獲得處理機(jī)執(zhí)行。 此外，若采用可搶占調(diào)度方式時(shí)，再令正在執(zhí)行的進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期占用處理機(jī)。第三章處理機(jī)調(diào)度與死鎖 3高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法HRRF） 響應(yīng)比響應(yīng)比Rp定義如下：定義如下： Rp=作業(yè)響應(yīng)時(shí)間作業(yè)響應(yīng)時(shí)間tR /

22、要求服務(wù)的時(shí)間要求服務(wù)的時(shí)間 作業(yè)響應(yīng)時(shí)間作業(yè)響應(yīng)時(shí)間tR=等待時(shí)間等待時(shí)間+要求服務(wù)的時(shí)間要求服務(wù)的時(shí)間 Rp=1+(等待時(shí)間等待時(shí)間tW /要求服務(wù)的時(shí)間要求服務(wù)的時(shí)間)高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法HRRF原理：就是在每調(diào)原理：就是在每調(diào)度一個(gè)作業(yè)投入運(yùn)行時(shí)，先計(jì)算后備作業(yè)隊(duì)列中每個(gè)作業(yè)度一個(gè)作業(yè)投入運(yùn)行時(shí)，先計(jì)算后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比，然后挑選響應(yīng)比最高者投入運(yùn)行。的響應(yīng)比，然后挑選響應(yīng)比最高者投入運(yùn)行。第三章處理機(jī)調(diào)度與死鎖 由上式可以看出：(1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作

23、業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。 (3) 對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)。 優(yōu)點(diǎn)：該算法既照顧了短作業(yè)用戶，同時(shí)也避免優(yōu)點(diǎn)：該算法既照顧了短作業(yè)用戶，同時(shí)也避免了長(zhǎng)作業(yè)用戶無(wú)限期的等待，是了長(zhǎng)作業(yè)用戶無(wú)限期的等待，是 FCFS 和和 SJ(P)F 兩種兩種算法的較好折衷方案。算法的較好折衷方案。 缺陷：算法較為復(fù)雜，且增加了系統(tǒng)開銷缺陷：算法較為復(fù)雜，且增加了系統(tǒng)開銷(計(jì)算響計(jì)算響應(yīng)比應(yīng)比)。第三章處理機(jī)調(diào)度與死鎖 作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶

24、權(quán)周轉(zhuǎn)時(shí)間ts(時(shí))tR(時(shí))tB(時(shí))tC(時(shí))ti(時(shí))Wi(Z)12348.008.509.009.502.000.500.100.20H H算法實(shí)例算法實(shí)例8.0010.1010.0010.6010.0010.6010.1010.802.002.101.101.306.501.004.2011.006.5022.70平均周轉(zhuǎn)時(shí)間 T=6.50/4=1.625(小時(shí))平均帶權(quán)時(shí)間 W=22.7/4=5.675第三章處理機(jī)調(diào)度與死鎖 3.3.33.3.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1 1時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法(Round Robin,RR)(Round Robin,R

25、R)輪轉(zhuǎn)法是最簡(jiǎn)單又最公平的進(jìn)程調(diào)度算法。主要用于分時(shí)輪轉(zhuǎn)法是最簡(jiǎn)單又最公平的進(jìn)程調(diào)度算法。主要用于分時(shí)系統(tǒng)中。屬于可搶占策略。系統(tǒng)中。屬于可搶占策略。1) 1) 基本原理基本原理輪轉(zhuǎn)法分配給每一進(jìn)程在輪轉(zhuǎn)法分配給每一進(jìn)程在CPUCPU上運(yùn)行的時(shí)間長(zhǎng)度，稱上運(yùn)行的時(shí)間長(zhǎng)度，稱之為時(shí)間片。之為時(shí)間片?；驹恚褐T進(jìn)程以此時(shí)間片為限制，輪流使用基本原理：諸進(jìn)程以此時(shí)間片為限制，輪流使用CPUCPU。如。如果時(shí)間片到期時(shí)，進(jìn)程尚未完成運(yùn)行，調(diào)度程序?qū)儕Z它正在果時(shí)間片到期時(shí)，進(jìn)程尚未完成運(yùn)行，調(diào)度程序?qū)儕Z它正在使用的使用的CPUCPU，轉(zhuǎn)讓給另一進(jìn)程使用；如果進(jìn)程在使用完它的某，轉(zhuǎn)讓給另一進(jìn)程使用

26、；如果進(jìn)程在使用完它的某一時(shí)間片之前已經(jīng)完成運(yùn)行或已阻塞，一時(shí)間片之前已經(jīng)完成運(yùn)行或已阻塞，CPUCPU也立即轉(zhuǎn)讓給另一也立即轉(zhuǎn)讓給另一進(jìn)程使用。進(jìn)程使用。第三章處理機(jī)調(diào)度與死鎖 輪轉(zhuǎn)法在實(shí)現(xiàn)上也很容易，調(diào)度程序只要維護(hù)一個(gè)先進(jìn)先出的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，將就緒進(jìn)程排隊(duì)，每當(dāng)一個(gè)進(jìn)程的時(shí)間片運(yùn)行完后，便把它從原來(lái)的隊(duì)頭位置移到隊(duì)尾，然后把現(xiàn)在處于隊(duì)頭位置的進(jìn)程調(diào)度到CPU上運(yùn)行。時(shí)間片的計(jì)數(shù)則可通過(guò)定時(shí)中斷實(shí)現(xiàn)。100ms交互用戶交互用戶 進(jìn)程調(diào)度進(jìn)程調(diào)度 endend 事件出現(xiàn)事件出現(xiàn)就緒隊(duì)列I/O阻塞隊(duì)列阻塞隊(duì)列I/OCPU等待事件等待事件時(shí)間片完時(shí)間片完第三章處理機(jī)調(diào)度與死鎖 2) 時(shí)間片大小的

27、確定時(shí)間片大小的確定輪轉(zhuǎn)法的性能取決于時(shí)間片大小的選擇。輪轉(zhuǎn)法的性能取決于時(shí)間片大小的選擇。 例：若一次切換時(shí)間為例：若一次切換時(shí)間為5毫秒，時(shí)間片長(zhǎng)度選擇毫秒，時(shí)間片長(zhǎng)度選擇為為20毫秒，則毫秒，則20的的CPU時(shí)間花費(fèi)于進(jìn)程調(diào)度程序。時(shí)間花費(fèi)于進(jìn)程調(diào)度程序。為了改善為了改善CPU的利用率，可以增大時(shí)間片，比如說(shuō)為的利用率，可以增大時(shí)間片，比如說(shuō)為500毫秒，此時(shí)毫秒，此時(shí)CPU利用率達(dá)利用率達(dá)99之多，但每一進(jìn)程之多，但每一進(jìn)程的響應(yīng)時(shí)間也因之增大。若就緒隊(duì)列中共有的響應(yīng)時(shí)間也因之增大。若就緒隊(duì)列中共有10個(gè)進(jìn)程，個(gè)進(jìn)程，則每一進(jìn)程需要等待則每一進(jìn)程需要等待5秒鐘，才能在秒鐘，才能在CPU

28、上服務(wù)一次。上服務(wù)一次。 第三章處理機(jī)調(diào)度與死鎖 選擇很小的時(shí)間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，選擇很小的時(shí)間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，但會(huì)頻繁地發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開但會(huì)頻繁地發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開銷；銷；選擇太長(zhǎng)的時(shí)間片，使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完選擇太長(zhǎng)的時(shí)間片，使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，時(shí)間片輪轉(zhuǎn)算法便退化為成，時(shí)間片輪轉(zhuǎn)算法便退化為FCFSFCFS算法，無(wú)法滿足交互式用戶算法，無(wú)法滿足交互式用戶的需求。的需求。一個(gè)較為可取的大小是，時(shí)間片略大于一次典型的交互所一個(gè)較為可取的大小是，時(shí)間片略大于一次典型的交互

29、所需要的時(shí)間。這樣可使大多數(shù)進(jìn)程在一個(gè)時(shí)間片內(nèi)完成。需要的時(shí)間。這樣可使大多數(shù)進(jìn)程在一個(gè)時(shí)間片內(nèi)完成。與時(shí)間片大小有關(guān)的因素有：系統(tǒng)響應(yīng)時(shí)間、就緒進(jìn)程個(gè)數(shù)和與時(shí)間片大小有關(guān)的因素有：系統(tǒng)響應(yīng)時(shí)間、就緒進(jìn)程個(gè)數(shù)和CPU處處理能力三個(gè)。理能力三個(gè)。 第三章處理機(jī)調(diào)度與死鎖 圖3-5 q=1和q=4時(shí)的進(jìn)程運(yùn)行情況 ABCDEABCDEABCEACE(a) q1(b) q412345678910 11 12 13 14 15 16 17t第三章處理機(jī)調(diào)度與死鎖 圖3-6 q=1和q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 作業(yè) 情況 時(shí) 間 片 服務(wù)時(shí)間

30、4 3 4 2 4 完成時(shí)間 15 12 16 9 17 周轉(zhuǎn)時(shí)間 15 11 14 6 13 11.8 RR q=1 帶權(quán)周轉(zhuǎn)時(shí)間 3.75 3.67 3.5 3 3.33 3.46 完成時(shí)間 4 7 11 13 17 周轉(zhuǎn)時(shí)間 4 6 9 10 13 8.4 RR q=4 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2.25 5 3.33 2.5 第三章處理機(jī)調(diào)度與死鎖 2 2多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列優(yōu)先級(jí)不首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列優(yōu)先級(jí)不同，第一個(gè)隊(duì)列優(yōu)先級(jí)最高。同，第一個(gè)隊(duì)列優(yōu)先級(jí)最高。每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的第一每個(gè)就緒隊(duì)列分

31、配給不同時(shí)間片，優(yōu)先級(jí)高的第一級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別的降低，時(shí)間片級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別的降低，時(shí)間片加大加大 各個(gè)隊(duì)列按照按時(shí)間片輪轉(zhuǎn)的先來(lái)先服務(wù)出調(diào)度各個(gè)隊(duì)列按照按時(shí)間片輪轉(zhuǎn)的先來(lái)先服務(wù)出調(diào)度算法算法一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列進(jìn)程。由于等待一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列進(jìn)程。由于等待而放棄而放棄CPUCPU后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列則回到原來(lái)的就緒隊(duì)列 第三章處理機(jī)調(diào)度與死鎖 當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占CPUCPU，被搶，被搶占進(jìn)程回到原來(lái)一級(jí)

32、就緒隊(duì)列末尾占進(jìn)程回到原來(lái)一級(jí)就緒隊(duì)列末尾 當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如此類推，當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如此類推，在第在第n n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。 當(dāng)時(shí)間片到后，進(jìn)程放棄當(dāng)時(shí)間片到后，進(jìn)程放棄CPUCPU，回到下一級(jí)隊(duì)列，回到下一級(jí)隊(duì)列第三章處理機(jī)調(diào)度與死鎖 處理機(jī)調(diào)度第三章處理機(jī)調(diào)度與死鎖 3多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。(1) 終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)(進(jìn)程)在第一隊(duì)列所規(guī)

33、定的時(shí)間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。 第三章處理機(jī)調(diào)度與死鎖 (2) 短批處理作業(yè)用戶。對(duì)于很短的批處理型作業(yè)，開始時(shí)像終端型作業(yè)一樣，如果僅在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間。對(duì)于稍長(zhǎng)的作業(yè)，通常也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即可完成，其周轉(zhuǎn)時(shí)間仍然較短。(3) 長(zhǎng)批處理作業(yè)用戶。對(duì)于長(zhǎng)作業(yè)，它將依次在第1，2，n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長(zhǎng)期得不到處理。 第三章處理機(jī)調(diào)度與死鎖 3.4實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度 3.4.13.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1 1提供必要的信息提供必要的

34、信息為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述一些信息：下述一些信息：(1) (1) 就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間，就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間，在周期任務(wù)的情況下，它就是事先預(yù)知的一串時(shí)間序列；而在周期任務(wù)的情況下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)的情況下，它也可能是預(yù)知的。在非周期任務(wù)的情況下，它也可能是預(yù)知的。 第三章處理機(jī)調(diào)度與死鎖 (2) 開始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用，只須知道開始截止時(shí)間，或者知道完成截止時(shí)間。(3) 處理時(shí)間。這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)

35、間。在某些情況下，該時(shí)間也是系統(tǒng)提供的。(4) 資源要求。這是指任務(wù)執(zhí)行時(shí)所需的一組資源。(5) 優(yōu)先級(jí)。如果某任務(wù)的開始截止時(shí)間已經(jīng)錯(cuò)過(guò)，就會(huì)引起故障，則應(yīng)為該任務(wù)賦予“絕對(duì)優(yōu)先級(jí)；如果開始截止時(shí)間的推遲對(duì)任務(wù)的繼續(xù)運(yùn)行無(wú)重大影響，則可為該任務(wù)賦予“相對(duì)優(yōu)先級(jí)，供調(diào)度程序參考。 第三章處理機(jī)調(diào)度與死鎖 2系統(tǒng)處理能力強(qiáng)假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件： 11miiiPC系統(tǒng)才是可調(diào)度的。系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是 50

36、 ms，而每次的處理時(shí)間為而每次的處理時(shí)間為 10 ms，則不難算出，此時(shí)是不能滿足，則不難算出，此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。上式的，因而系統(tǒng)是不可調(diào)度的。第三章處理機(jī)調(diào)度與死鎖 解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為： NPCmiii1第三章處理機(jī)調(diào)度與死鎖 3采用搶占式調(diào)度機(jī)制在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可

37、滿足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。第三章處理機(jī)調(diào)度與死鎖 4具有快速切換機(jī)制為保證要求較高的硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在實(shí)時(shí)系統(tǒng)中還應(yīng)具有快速切換機(jī)制，以保證能進(jìn)行任務(wù)的快速切換。該機(jī)制應(yīng)具有如下兩方面的能力：(1) 對(duì)外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。(2) 快速的任務(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í)間開銷。 第三章處理機(jī)調(diào)度與死鎖 3.4

38、.23.4.2實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類1 1非搶占式調(diào)度算法非搶占式調(diào)度算法1) 1) 非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺(tái)計(jì)算機(jī)控制該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的若干個(gè)相同的( (或類似的或類似的) )對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)中的第一個(gè)任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行

39、，而調(diào)度程序再選擇下一個(gè)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，而調(diào)度程序再選擇下一個(gè)( (隊(duì)首隊(duì)首) )任務(wù)運(yùn)行。任務(wù)運(yùn)行。這是一種常用于分時(shí)系統(tǒng)的調(diào)度算法，這種調(diào)度算法可獲得數(shù)這是一種常用于分時(shí)系統(tǒng)的調(diào)度算法，這種調(diào)度算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)秒至數(shù)十秒的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中或?qū)崟r(shí)信息處理系統(tǒng)。中或?qū)崟r(shí)信息處理系統(tǒng)。 第三章處理機(jī)調(diào)度與死鎖 2) 非搶占式優(yōu)先級(jí)調(diào)度算法如果在實(shí)時(shí)系統(tǒng)中存在著要求較為嚴(yán)格(響應(yīng)時(shí)間為數(shù)百毫秒)的任務(wù)，可為這些任務(wù)賦予較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行

40、完成后才能被調(diào)度執(zhí)行。常用于多道批處理系統(tǒng)的調(diào)度算法，這種調(diào)度算法可能獲得僅為數(shù)秒至數(shù)百毫秒級(jí)的響應(yīng)時(shí)間，因而可用于有一定要求的實(shí)時(shí)控制系統(tǒng)中。 第三章處理機(jī)調(diào)度與死鎖 2 2搶占式調(diào)度算法搶占式調(diào)度算法在要求較嚴(yán)格的在要求較嚴(yán)格的( (響應(yīng)時(shí)間為數(shù)十毫秒以下響應(yīng)時(shí)間為數(shù)十毫秒以下) )的實(shí)時(shí)系統(tǒng)中，的實(shí)時(shí)系統(tǒng)中，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法?？筛鶕?jù)搶占發(fā)生時(shí)間的不同而應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法?？筛鶕?jù)搶占發(fā)生時(shí)間的不同而進(jìn)一步分成以下兩種調(diào)度算法。進(jìn)一步分成以下兩種調(diào)度算法。1) 1) 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實(shí)時(shí)任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高

41、于當(dāng)前任務(wù)在某實(shí)時(shí)任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來(lái)時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分鐘中斷到來(lái)時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。配給新到的高優(yōu)先權(quán)任務(wù)。這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。 第三章處理機(jī)調(diào)度與死鎖 2) 立即搶占(Immediate P

42、reemption)的優(yōu)先權(quán)調(diào)度算法在這種調(diào)度策略中，一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。這種算法能獲得非常快的響應(yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。圖3-8中的(a)、(b)、(c)、(d)分別示出了采用非搶占式輪轉(zhuǎn)調(diào)度算法、非搶占式優(yōu)先權(quán)調(diào)度算法、基于時(shí)鐘中斷搶占的優(yōu)先權(quán)調(diào)度算法和立即搶占的優(yōu)先權(quán)調(diào)度算法四種情況的調(diào)度時(shí)間。 第三章處理機(jī)調(diào)度與死鎖 圖3-8 實(shí)時(shí)進(jìn)程調(diào)度 (a) 非搶占式輪轉(zhuǎ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)度調(diào)度時(shí)間進(jìn)程 1進(jìn)程

43、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í)間當(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)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程第三章處理機(jī)調(diào)度與死鎖 3.4.33.4.3常用的幾種實(shí)時(shí)調(diào)度算法常用的幾種實(shí)時(shí)調(diào)度算法1 1最早截止時(shí)間優(yōu)先即最早截止時(shí)間優(yōu)先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法該算法是根據(jù)任務(wù)的開始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)。該算法是根據(jù)任務(wù)的開始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早

44、，其優(yōu)先級(jí)愈高。截止時(shí)間愈早，其優(yōu)先級(jí)愈高。在系統(tǒng)中就緒隊(duì)列按各任務(wù)截止時(shí)間的早晚排序，具有最在系統(tǒng)中就緒隊(duì)列按各任務(wù)截止時(shí)間的早晚排序，具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序選擇就緒隊(duì)列早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。最早截止時(shí)間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非最早截止時(shí)間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。搶占式調(diào)度方式中。 第三章處理機(jī)調(diào)度與死鎖 1) 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)1342開始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)12 341342

45、t圖 3-9EDF算法用于非搶占調(diào)度的調(diào)度方式第三章處理機(jī)調(diào)度與死鎖 2) 2) 搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)圖圖3-103-10示出了將最早截止時(shí)間優(yōu)先算法用于搶占調(diào)度方示出了將最早截止時(shí)間優(yōu)先算法用于搶占調(diào)度方式之例。式之例。在該例中有兩個(gè)周期性任務(wù)，任務(wù)在該例中有兩個(gè)周期性任務(wù)，任務(wù)A A的周期時(shí)間為的周期時(shí)間為20 ms20 ms，每個(gè)周期的處理時(shí)間為每個(gè)周期的處理時(shí)間為10 ms10 ms；任務(wù)；任務(wù)B B的周期時(shí)間為的周期時(shí)間為50 ms50 ms，每個(gè)周期的處理時(shí)間為每個(gè)周期的處理時(shí)間為25 ms25 ms。圖中的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最

46、后期限和圖中的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最后期限和執(zhí)行時(shí)間圖。其中任務(wù)執(zhí)行時(shí)間圖。其中任務(wù)A A的到達(dá)時(shí)間為的到達(dá)時(shí)間為0 0、2020、4040、；任務(wù)；任務(wù)A A的最后期限為的最后期限為2020、4040、6060、；任務(wù)；任務(wù)B B的到達(dá)時(shí)間為的到達(dá)時(shí)間為0 0、5050、100100、；任務(wù)；任務(wù)B B的最后期限為的最后期限為5050、100100、150150、(注：?jiǎn)挝蛔ⅲ簡(jiǎn)挝唤詾榻詾閙s)ms)。 第三章處理機(jī)調(diào)度與死鎖 圖3-10 最早截止時(shí)間優(yōu)先算法用于搶占調(diào)度方式之例 A1B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3B2A4B2A5

47、 B2A1A2B2A3A4A5B1最 后 期 限B2最 后 期 限A1最 后 期 限A2最 后 期 限A3最 后 期 限A4最 后 期 限A5最 后 期 限到 達(dá) 時(shí) 間 、 執(zhí) 行 時(shí) 間和 最 后 期 限A1固 定 優(yōu) 先 級(jí) 調(diào) 度固 定 優(yōu) 先 級(jí) 調(diào) 度A2B1A3A4A5， B2A5， B2A4A1(錯(cuò) 過(guò) )A2B1A3(錯(cuò) 過(guò) )A1A2B1(錯(cuò) 過(guò) )A3A4A5， B20102030405060708090100時(shí) 間t/ms使 用 完 成 最 后 期 限最 早 和 最 后 期 限 調(diào) 度(A有 較 高 優(yōu) 先 級(jí) )(B有 較 高 優(yōu) 先 級(jí) )第三章處理機(jī)調(diào)度與死鎖 2

48、 2最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。以使之優(yōu)先執(zhí)行。例如，一個(gè)任務(wù)在例如，一個(gè)任務(wù)在200 ms200 ms時(shí)必須完成，而它本身所需的時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有運(yùn)行時(shí)間就有100 ms100 ms，因此，調(diào)度程序必須在，因此，調(diào)度程序必須在100 ms100 ms之前調(diào)之前調(diào)度執(zhí)行，該任務(wù)的緊急程度度執(zhí)行，該任務(wù)的緊急程度( (松弛程度松弛程度) )為為100 ms10

49、0 ms。又如，另。又如，另一任務(wù)在一任務(wù)在400 ms400 ms時(shí)必須完成，它本身需要運(yùn)行時(shí)必須完成，它本身需要運(yùn)行 150 ms150 ms，則其，則其松弛程度為松弛程度為 250 ms250 ms。就緒隊(duì)列按松弛度排序，松弛度最低的任務(wù)排在隊(duì)列最就緒隊(duì)列按松弛度排序，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。 第三章處理機(jī)調(diào)度與死鎖 該算法主要用于可搶占調(diào)度方式中。該算法主要用于可搶占調(diào)度方式中。假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A A和和B B：任務(wù)任務(wù)A

50、 A要求每要求每 20 ms20 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 10 ms10 ms；任務(wù)任務(wù)B B只要求每只要求每50 ms50 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 25 ms25 ms。由此可得知任務(wù)由此可得知任務(wù)A A和和B B每次必須完成的時(shí)間分別為：每次必須完成的時(shí)間分別為：A1A1、A2A2、A3A3、和和B1B1、B2B2、B3B3、，見圖，見圖3-113-11。為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。先的搶占調(diào)度策略。 第三章處理機(jī)調(diào)度與死鎖 圖 3-11A和B任務(wù)每次必須完成的

51、時(shí)間 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0t1A1(10)10203040506080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)圖 3-12利用LLF算法進(jìn)行調(diào)度的情況 第三章處理機(jī)調(diào)度與死鎖 先來(lái)先服務(wù)先來(lái)先服務(wù)短作業(yè)優(yōu)先短作業(yè)優(yōu)先高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列能否是可搶占能否是可搶占否否能能能能能能能能能否是不可搶占能否是不可搶占能能能能能能否否不能不能優(yōu)點(diǎn)優(yōu)點(diǎn)公平，實(shí)現(xiàn)簡(jiǎn)公平，實(shí)現(xiàn)簡(jiǎn)單，利于單，利于CPU繁忙型繁忙型平

52、均等待時(shí)間平均等待時(shí)間最少，效率最最少，效率最高高兼顧長(zhǎng)短作業(yè)兼顧長(zhǎng)短作業(yè)兼顧長(zhǎng)短作兼顧長(zhǎng)短作業(yè)業(yè)兼顧長(zhǎng)短作業(yè)，有兼顧長(zhǎng)短作業(yè)，有較好的響應(yīng)時(shí)間，較好的響應(yīng)時(shí)間，利于終端型作業(yè)和利于終端型作業(yè)和短批處理作業(yè)短批處理作業(yè)缺點(diǎn)缺點(diǎn)不利于短作業(yè)，不利于短作業(yè)，不利用不利用I/O繁忙繁忙型型長(zhǎng)作業(yè)會(huì)饑餓，長(zhǎng)作業(yè)會(huì)饑餓，估計(jì)時(shí)間不易估計(jì)時(shí)間不易確定，未考慮確定，未考慮緊迫程度緊迫程度計(jì)算響應(yīng)比的計(jì)算響應(yīng)比的開銷大開銷大平均等待時(shí)平均等待時(shí)間較長(zhǎng)，上間較長(zhǎng)，上下文切換浪下文切換浪費(fèi)時(shí)間費(fèi)時(shí)間尤其適用于尤其適用于作業(yè)調(diào)度，批作業(yè)調(diào)度，批處理系統(tǒng)處理系統(tǒng)分時(shí)系統(tǒng)分時(shí)系統(tǒng)相當(dāng)通用相當(dāng)通用能否用于作業(yè)調(diào)能否用于作

53、業(yè)調(diào)度度能能能能能能否否否否能否用于進(jìn)程調(diào)能否用于進(jìn)程調(diào)度度能能能能能能能能能能表3.1 調(diào)度算法比較第三章處理機(jī)調(diào)度與死鎖 1. 1. 分時(shí)系統(tǒng)中的當(dāng)前運(yùn)行進(jìn)程連續(xù)獲得了兩個(gè)時(shí)間片，原因分時(shí)系統(tǒng)中的當(dāng)前運(yùn)行進(jìn)程連續(xù)獲得了兩個(gè)時(shí)間片，原因可能是（可能是（ ）。）。A A該進(jìn)程的優(yōu)先級(jí)最高該進(jìn)程的優(yōu)先級(jí)最高B B就緒隊(duì)列為空就緒隊(duì)列為空C C該進(jìn)程最早進(jìn)入就緒隊(duì)列該進(jìn)程最早進(jìn)入就緒隊(duì)列D D該進(jìn)程是一個(gè)短進(jìn)程該進(jìn)程是一個(gè)短進(jìn)程2. 2. 若進(jìn)程若進(jìn)程P P一旦被喚醒就能夠投入運(yùn)行，系統(tǒng)可能為（一旦被喚醒就能夠投入運(yùn)行，系統(tǒng)可能為（ ) )。A.A.在分時(shí)系統(tǒng)中，進(jìn)程在分時(shí)系統(tǒng)中，進(jìn)程P P的優(yōu)先

54、級(jí)最高的優(yōu)先級(jí)最高B.B.搶占調(diào)度方式，就緒隊(duì)列上的所有進(jìn)程的優(yōu)先級(jí)皆比搶占調(diào)度方式，就緒隊(duì)列上的所有進(jìn)程的優(yōu)先級(jí)皆比P P的低的低C.C.就緒隊(duì)列為空隊(duì)列就緒隊(duì)列為空隊(duì)列D.D.搶占調(diào)度方式，搶占調(diào)度方式，P P的優(yōu)先級(jí)高于當(dāng)前運(yùn)行的進(jìn)程的優(yōu)先級(jí)高于當(dāng)前運(yùn)行的進(jìn)程第三章處理機(jī)調(diào)度與死鎖 3. 3. 現(xiàn)有現(xiàn)有3 3個(gè)同時(shí)到達(dá)的作業(yè)個(gè)同時(shí)到達(dá)的作業(yè)J1J1、J2J2和和J3J3，它們的執(zhí)行時(shí)間，它們的執(zhí)行時(shí)間分別是分別是T1T1、T2T2和和T3T3，且，且T1T2T3T1T2T3。系統(tǒng)按單道方式運(yùn)行且采。系統(tǒng)按單道方式運(yùn)行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時(shí)間是用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時(shí)間是

55、( () )?！疚麟??！疚麟?20192019】A. T1+T2+T3 A. T1+T2+T3 B. B.（T1+T2+T3T1+T2+T3）/3/3C.C.（3T1+2T2+T33T1+2T2+T3）/3 /3 D. D.（T1+2T2+3T3T1+2T2+3T3）/3/3. . 降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是：降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是：A.A.進(jìn)程的時(shí)間片用完進(jìn)程的時(shí)間片用完進(jìn)程剛完成進(jìn)程剛完成I/OI/O進(jìn)入就緒隊(duì)列進(jìn)入就緒隊(duì)列進(jìn)程長(zhǎng)期處于就緒隊(duì)列中進(jìn)程長(zhǎng)期處于就緒隊(duì)列中進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行態(tài)進(jìn)程從就緒狀態(tài)轉(zhuǎn)為運(yùn)行態(tài)第三章處理機(jī)調(diào)度與死鎖 . . 下列算法中，（下列算法中，（ ）只能采取

56、非搶占調(diào)度方式，（）只能采取非搶占調(diào)度方式，（ ）只）只能采取搶占調(diào)度方式，而其余的算法既可采取搶占方式，也可能采取搶占調(diào)度方式，而其余的算法既可采取搶占方式，也可采取非搶占方式。采取非搶占方式。A. A. 高優(yōu)先權(quán)優(yōu)先法；高優(yōu)先權(quán)優(yōu)先法； B. B. 時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法C. FCFSC. FCFS調(diào)度算法調(diào)度算法 D. D. 短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法有三個(gè)作業(yè)有三個(gè)作業(yè)A A到達(dá)時(shí)間到達(dá)時(shí)間8:508:50，執(zhí)行時(shí)間，執(zhí)行時(shí)間1.51.5小時(shí)）、小時(shí)）、B B到達(dá)時(shí)間到達(dá)時(shí)間9:009:00，執(zhí)行時(shí)間，執(zhí)行時(shí)間0.40.4小時(shí)）、小時(shí)）、C C到達(dá)時(shí)間到達(dá)時(shí)間9:309:30，執(zhí)，

57、執(zhí)行時(shí)間行時(shí)間1 1小時(shí)）。當(dāng)作業(yè)全部到達(dá)后，單道批處理系統(tǒng)按照響應(yīng)小時(shí)）。當(dāng)作業(yè)全部到達(dá)后，單道批處理系統(tǒng)按照響應(yīng)比高者優(yōu)先算法進(jìn)行調(diào)度，則作業(yè)被選中的次序是（比高者優(yōu)先算法進(jìn)行調(diào)度，則作業(yè)被選中的次序是（ ）。）。A.A.（ABCABC） B.B.（BACBAC）C.C.（BCABCA） D.D.（CBACBA）E.E.（CABCAB） F.F.（ACBACB）第三章處理機(jī)調(diào)度與死鎖 7. 7. 如果為每一個(gè)作業(yè)只建立一個(gè)進(jìn)程，則為了照顧短作如果為每一個(gè)作業(yè)只建立一個(gè)進(jìn)程，則為了照顧短作業(yè)用戶，應(yīng)采用（業(yè)用戶，應(yīng)采用（ ）；為了照顧緊急作業(yè)用戶，應(yīng)采用）；為了照顧緊急作業(yè)用戶，應(yīng)采用（ ）

58、；為能實(shí)現(xiàn)人機(jī)交互作業(yè)，應(yīng)采用（）；為能實(shí)現(xiàn)人機(jī)交互作業(yè)，應(yīng)采用（ ）；為了兼顧）；為了兼顧短作業(yè)和長(zhǎng)時(shí)間等待的作業(yè)，應(yīng)采用（短作業(yè)和長(zhǎng)時(shí)間等待的作業(yè)，應(yīng)采用（ ）；為了使短作業(yè)、）；為了使短作業(yè)、長(zhǎng)作業(yè)及交互作業(yè)用戶都比較滿意，應(yīng)采用（長(zhǎng)作業(yè)及交互作業(yè)用戶都比較滿意，應(yīng)采用（ ）；為了使）；為了使作業(yè)的平均周轉(zhuǎn)時(shí)間最短，應(yīng)采用（作業(yè)的平均周轉(zhuǎn)時(shí)間最短，應(yīng)采用（ ）算法。）算法。A. FCFSA. FCFS調(diào)度算法；調(diào)度算法； B. B. 短作業(yè)優(yōu)先短作業(yè)優(yōu)先C. C. 時(shí)間片輪轉(zhuǎn)；時(shí)間片輪轉(zhuǎn)； D. D. 多級(jí)反饋隊(duì)列調(diào)度算法；多級(jí)反饋隊(duì)列調(diào)度算法；E. E. 基于優(yōu)先權(quán)的剝奪調(diào)度算法基于優(yōu)

59、先權(quán)的剝奪調(diào)度算法 F. F. 高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先第三章處理機(jī)調(diào)度與死鎖 8. 有一個(gè)內(nèi)存中只能裝入兩道作業(yè)的批處理系統(tǒng)，作有一個(gè)內(nèi)存中只能裝入兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。有如表所示的作業(yè)系列，先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。有如表所示的作業(yè)系列，表中所列的優(yōu)先數(shù)是指進(jìn)程調(diào)度的優(yōu)先數(shù)，且優(yōu)先數(shù)越表中所列的優(yōu)先數(shù)是指進(jìn)程調(diào)度的優(yōu)先數(shù)，且優(yōu)先數(shù)越小優(yōu)先級(jí)越高。小優(yōu)先級(jí)越高。列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)刻以及結(jié)束的時(shí)刻列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)刻以及結(jié)束的時(shí)刻計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間計(jì)算

60、作業(yè)的平均周轉(zhuǎn)時(shí)間作業(yè)名到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間優(yōu)先數(shù):分:分:分:分第三章處理機(jī)調(diào)度與死鎖 9. 有有5個(gè)任務(wù)個(gè)任務(wù)A，B，C，D，E，它們幾乎同時(shí)到達(dá)，預(yù)，它們幾乎同時(shí)到達(dá)，預(yù)計(jì)它們的運(yùn)行時(shí)間為計(jì)它們的運(yùn)行時(shí)間為10，6，2，4，8min。其優(yōu)先級(jí)分。其優(yōu)先級(jí)分別為別為3，5，2，1和和4，這里，這里5為最高優(yōu)先級(jí)。對(duì)于下列為最高優(yōu)先級(jí)。對(duì)于下列每一種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間進(jìn)程切每一種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間進(jìn)程切換開銷可不考慮）。換開銷可不考慮）。（1先來(lái)先服務(wù)按先來(lái)先服務(wù)按A，B，C，D，E算法。算法。（2優(yōu)先級(jí)調(diào)度算法。優(yōu)先級(jí)調(diào)度算法。（3時(shí)間片輪轉(zhuǎn)算法時(shí)間片輪轉(zhuǎn)算法q