操作系統(tǒng)第9講new

1、第三章 處理機(jī)調(diào)度與死鎖第九講第九講處理機(jī)調(diào)度的層次、模型和處理機(jī)調(diào)度的層次、模型和準(zhǔn)則準(zhǔn)則2022年3月15日0時(shí)54分第三章 處理機(jī)調(diào)度與死鎖本次課程主要內(nèi)容本次課程主要內(nèi)容處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次高級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度中級(jí)調(diào)度中級(jí)調(diào)度調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則調(diào)度算法調(diào)度算法先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法2022年3月15日0時(shí)54分2第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分3job1job1job2job

2、2job3job3.外存內(nèi)存Process1Process1Process2Process2Process3Process3.處理機(jī)調(diào)度：處理機(jī)調(diào)度：Pro1Pro1Pro2Pro3.作業(yè)掛起進(jìn)程第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次2022年3月15日0時(shí)54分.1高級(jí)調(diào)度高級(jí)調(diào)度1 1作業(yè)和作業(yè)步作業(yè)和作業(yè)步（1 1）作業(yè)（）作業(yè)（JobJob）：程序、數(shù)據(jù)、作業(yè)說(shuō)明書）：程序、數(shù)據(jù)、作業(yè)說(shuō)明書（2 2）作業(yè)步（）作業(yè)步（Job StepJob Step）：）： “編譯編譯”作業(yè)步作業(yè)步 “連結(jié)裝配連結(jié)裝配”作業(yè)步作業(yè)步 “運(yùn)行運(yùn)行”作業(yè)步作業(yè)步

3、 (3) (3) 作業(yè)流。輸入的作業(yè)流；處理作業(yè)流。作業(yè)流。輸入的作業(yè)流；處理作業(yè)流。 作業(yè)說(shuō)明書主要包含三方面內(nèi)容：作業(yè)基本描述：包括用戶名、作業(yè)名、使用的編程語(yǔ)言名、允許的最大處理時(shí)間等。作業(yè)控制描述：包括作業(yè)在執(zhí)行過(guò)程中的控制方式。資源要求描述：包括要求內(nèi)存大小、外設(shè)種類和臺(tái)數(shù)、處理機(jī)優(yōu)先級(jí)、所需處理時(shí)間、所需庫(kù)函數(shù)或?qū)嵱贸绦虻?。第三?處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分52 2作業(yè)控制塊作業(yè)控制塊JCB(Job Control Block)JCB(Job Control Block) 在在JCBJCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含

4、的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型(CPU (CPU 繁忙型、繁忙型、I/O I/O 繁忙型、批量型、終端型繁忙型、批量型、終端型) )、作業(yè)狀、作業(yè)狀態(tài)、調(diào)度信息態(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í)間、開(kāi)始處理時(shí)間、作業(yè)完成時(shí)、進(jìn)入系統(tǒng)時(shí)間、開(kāi)始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。間、作業(yè)退出時(shí)間、資源使用情況等。第三章 處理機(jī)調(diào)

5、度與死鎖2022年3月15日0時(shí)54分63. 3. 作業(yè)調(diào)度作業(yè)調(diào)度 作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。因此，有時(shí)新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。因此，有時(shí)也把作業(yè)調(diào)度稱為接納調(diào)度也把作業(yè)調(diào)度稱為接納調(diào)度(Admission Sc

6、heduling)(Admission Scheduling)。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分7存在的矛盾：存在的矛盾：用戶希望自己作業(yè)的周轉(zhuǎn)用戶希望自己作業(yè)的周轉(zhuǎn)時(shí)間短時(shí)間短系統(tǒng)希望平均周轉(zhuǎn)時(shí)間短系統(tǒng)希望平均周轉(zhuǎn)時(shí)間短要做的決定：要做的決定：接納多少個(gè)作業(yè)接納多少個(gè)作業(yè)決定接納哪些作業(yè)決定接納哪些作業(yè)job1job1job2job2job3job3.外存內(nèi)存Process1Process1Process2Process2Process3Process3.作業(yè)作業(yè)調(diào)度第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分8三種基本操作操作系統(tǒng)是否需要作業(yè)調(diào)度？三種基本操

7、作操作系統(tǒng)是否需要作業(yè)調(diào)度？批處理系統(tǒng)：批處理系統(tǒng)：作業(yè)進(jìn)入系統(tǒng)后，總是先駐留在外存的后備隊(duì)列上，因此需要需要有作業(yè)調(diào)度的過(guò)程，以便將它們分批地裝入內(nèi)存。分時(shí)系統(tǒng)：分時(shí)系統(tǒng)：為了做到及時(shí)響應(yīng)，用戶通過(guò)鍵盤輸入的命令或數(shù)據(jù)等都是被直接送入內(nèi)存的，因而無(wú)需無(wú)需再配置上述的作業(yè)調(diào)度機(jī)制。實(shí)時(shí)系統(tǒng)：實(shí)時(shí)系統(tǒng)：通常也不需要不需要作業(yè)調(diào)度第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分93.1.2 低級(jí)調(diào)度低級(jí)調(diào)度通常也把低級(jí)調(diào)度通常也把低級(jí)調(diào)度(Low Level Scheduling)稱為稱為進(jìn)程調(diào)度或短程調(diào)度進(jìn)程調(diào)度或短程調(diào)度(ShortTerm Scheduling)，它所，它所調(diào)度的對(duì)象是

8、進(jìn)程調(diào)度的對(duì)象是進(jìn)程(或內(nèi)核級(jí)線程或內(nèi)核級(jí)線程)。進(jìn)程調(diào)度是最。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時(shí)和實(shí)時(shí)三種基本的一種調(diào)度，在多道批處理、分時(shí)和實(shí)時(shí)三種類型的類型的OS中，都必須配置這級(jí)調(diào)度。中，都必須配置這級(jí)調(diào)度。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分10低級(jí)調(diào)度的主要功能如下：低級(jí)調(diào)度的主要功能如下：（1 1）保存處理機(jī)的現(xiàn)場(chǎng)信息。）保存處理機(jī)的現(xiàn)場(chǎng)信息。 程序計(jì)數(shù)器、多個(gè)通用寄存器中的內(nèi)容等，寫入進(jìn)程控制塊(PCB)中的相應(yīng)單元。（2 2）按某種算法選取進(jìn)程。）按某種算法選取進(jìn)程。 優(yōu)先數(shù)算法、輪轉(zhuǎn)法等（3 3）把處理器分配給進(jìn)程）把處理器分配給進(jìn)程。內(nèi)存Pr

9、ocess1Process1Process2Process2Process3Process3.進(jìn)程調(diào)度第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分11排隊(duì)器：為了提高進(jìn)程調(diào)度的效率，應(yīng)事排隊(duì)器：為了提高進(jìn)程調(diào)度的效率，應(yīng)事先將系統(tǒng)中所有的就緒進(jìn)程按照一定的先將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程方式排成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程序能最快地找到它。序能最快地找到它。內(nèi)存Process1Process1Process2Process2Process3Process3.進(jìn)程調(diào)度排隊(duì)器排隊(duì)器分配器分配器上下文上下文切換器切換器分派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，分

10、派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，從就緒隊(duì)列中取出該進(jìn)程，然后進(jìn)行上從就緒隊(duì)列中取出該進(jìn)程，然后進(jìn)行上下文切換，將處理機(jī)分配給它下文切換，將處理機(jī)分配給它 。上下文切換機(jī)制。當(dāng)對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)上下文切換機(jī)制。當(dāng)對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)發(fā)生兩對(duì)上下文切換操作。在第一對(duì)上下文發(fā)生兩對(duì)上下文切換操作。在第一對(duì)上下文切換時(shí)，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，切換時(shí)，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二對(duì)上下文切換時(shí)，將移出分派程行；在第二對(duì)上下文切換時(shí)，將移出分派程序，而把新選進(jìn)程的序，而把新選進(jìn)程的CPUCPU現(xiàn)場(chǎng)信

11、息裝入到處現(xiàn)場(chǎng)信息裝入到處理機(jī)的各個(gè)相應(yīng)寄存器中。理機(jī)的各個(gè)相應(yīng)寄存器中。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分123 3進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式1) 1) 非搶占方式非搶占方式(Nonpreemptive Mode)(Nonpreemptive Mode)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長(zhǎng)時(shí)間，都一直讓它運(yùn)行下去，程后，不管它要運(yùn)行多長(zhǎng)時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。

12、直機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。 第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分13在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為如下幾個(gè)：可歸結(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

13、原語(yǔ)、Wakeup原語(yǔ)等。思考：有何優(yōu)缺點(diǎn)？思考：有何優(yōu)缺點(diǎn)？第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分142) 2) 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。機(jī)重新分配給另一進(jìn)程。 優(yōu)點(diǎn)是，可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理優(yōu)點(diǎn)是，可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿

14、足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。滿足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開(kāi)銷較大。但搶占方式比非搶占方式調(diào)度所需付出的開(kāi)銷較大。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分15搶占調(diào)度方式基于的原則：搶占調(diào)度方式基于的原則： (1) (1) 優(yōu)先權(quán)原則。優(yōu)先權(quán)原則。允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。(2) (2) 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先原則。優(yōu)先原則。短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長(zhǎng)作業(yè)(進(jìn)程)的處理機(jī)。(3) (3) 時(shí)間片原則。時(shí)間片原則。當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用

15、于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分16又稱中程調(diào)度又稱中程調(diào)度(Medium-Term Scheduling)。引入中。引入中級(jí)調(diào)度的主要目的是為了提級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。高內(nèi)存利用率和系統(tǒng)吞吐量。暫時(shí)不能運(yùn)行的就緒進(jìn)程調(diào)暫時(shí)不能運(yùn)行的就緒進(jìn)程調(diào)至外存上去等待，把此時(shí)的至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為靜止就緒狀態(tài)進(jìn)程狀態(tài)稱為靜止就緒狀態(tài)或掛起狀態(tài)。把靜止就緒進(jìn)或掛起狀態(tài)。把靜止就緒進(jìn)程從外存調(diào)入內(nèi)存活動(dòng)就緒程從外存調(diào)入內(nèi)存活動(dòng)就緒隊(duì)列的調(diào)度即為中程調(diào)度。隊(duì)列的調(diào)度即為中程調(diào)度。外存內(nèi)存P

16、rocess1Process1Process2Process2Process3Process3.Pro1Pro1Pro2Pro3.掛起進(jìn)程3.1.3 中級(jí)調(diào)度中級(jí)調(diào)度第三章 處理機(jī)調(diào)度與死鎖3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則 2022年3月15日0時(shí)54分.1調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型1 1僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 在分時(shí)系統(tǒng)中，通常僅設(shè)置了進(jìn)程調(diào)度，用戶在分時(shí)系統(tǒng)中，通常僅設(shè)置了進(jìn)程調(diào)度，用戶鍵入的命令和數(shù)據(jù)都直接送入內(nèi)存。對(duì)于命令，是鍵入的命令和數(shù)據(jù)都直接送入內(nèi)存。對(duì)于命令，是由由OSOS為之建立一個(gè)進(jìn)程。系統(tǒng)可以把處于就緒狀

17、態(tài)為之建立一個(gè)進(jìn)程。系統(tǒng)可以把處于就緒狀態(tài)的進(jìn)程組織成的進(jìn)程組織成FIFOFIFO隊(duì)列形式。每當(dāng)隊(duì)列形式。每當(dāng)OSOS創(chuàng)建一個(gè)新進(jìn)創(chuàng)建一個(gè)新進(jìn)程時(shí)，便將它掛在就緒隊(duì)列的末尾，然后按時(shí)間片程時(shí)，便將它掛在就緒隊(duì)列的末尾，然后按時(shí)間片輪轉(zhuǎn)方式運(yùn)行。輪轉(zhuǎn)方式運(yùn)行。 第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分18(1) (1) 任務(wù)在給定的時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程便在釋放處理任務(wù)在給定的時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；機(jī)后進(jìn)入完成狀態(tài)；(2) (2) 任務(wù)在本次分得的時(shí)間片內(nèi)尚未完成，任務(wù)在本次分得的時(shí)間片內(nèi)尚未完成，OSOS便將該任務(wù)再便將該任務(wù)再放入就緒隊(duì)列的末尾

18、；放入就緒隊(duì)列的末尾；(3) (3) 在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞螅辉趫?zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，被OSOS放入阻放入阻塞隊(duì)列。塞隊(duì)列。就 緒 隊(duì) 列阻 塞 隊(duì) 列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分192 2具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還需有作業(yè)調(diào)度，作業(yè)調(diào)度按一定的作業(yè)調(diào)度算法，需有作業(yè)調(diào)度，作業(yè)調(diào)度按一定的作業(yè)調(diào)度算法，從外存的后備隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，并為從外存的后備隊(duì)列中選擇一

19、批作業(yè)調(diào)入內(nèi)存，并為它們建立進(jìn)程，送入就緒隊(duì)列，然后才由進(jìn)程調(diào)度它們建立進(jìn)程，送入就緒隊(duì)列，然后才由進(jìn)程調(diào)度按照一定的進(jìn)程調(diào)度算法選擇一個(gè)進(jìn)程，把處理機(jī)按照一定的進(jìn)程調(diào)度算法選擇一個(gè)進(jìn)程，把處理機(jī)分配給該進(jìn)程。分配給該進(jìn)程。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分20該模型與上一模型的主要區(qū)別在于如下兩個(gè)方面：該模型與上一模型的主要區(qū)別在于如下兩個(gè)方面：(1) (1) 就緒隊(duì)列的形式。就緒隊(duì)列的形式。(2) (2) 設(shè)置多個(gè)阻塞隊(duì)列。設(shè)置多個(gè)阻塞隊(duì)列。就 緒 隊(duì) 列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時(shí)間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后 備 隊(duì) 列第三

20、章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分213 3同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型當(dāng)在當(dāng)在OSOS中引入中級(jí)調(diào)度后，人們可把進(jìn)程的就緒中引入中級(jí)調(diào)度后，人們可把進(jìn)程的就緒狀態(tài)分為內(nèi)存就緒狀態(tài)分為內(nèi)存就緒( (表示進(jìn)程在內(nèi)存中就緒表示進(jìn)程在內(nèi)存中就緒) )和外存就和外存就緒緒( (進(jìn)程在外存中就緒進(jìn)程在外存中就緒) )。類似地，也可把阻塞狀態(tài)進(jìn)。類似地，也可把阻塞狀態(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，的作用下，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻

21、塞轉(zhuǎn)為外存阻塞；在中級(jí)調(diào)度的作用下，又由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級(jí)調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒?？墒雇獯婢途w轉(zhuǎn)為內(nèi)存就緒。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分22就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分233.2.2選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時(shí)間短。所謂周轉(zhuǎn)時(shí)間，是指從作業(yè)被周轉(zhuǎn)時(shí)間短。所謂周轉(zhuǎn)時(shí)間，是指從作業(yè)被提交給系統(tǒng)開(kāi)始

22、，到作業(yè)完成為止的這段時(shí)間間隔提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔(稱為作業(yè)周轉(zhuǎn)時(shí)間稱為作業(yè)周轉(zhuǎn)時(shí)間)。它包括四部分時(shí)間：作業(yè)在。它包括四部分時(shí)間：作業(yè)在外存后備隊(duì)列上等待外存后備隊(duì)列上等待(作業(yè)作業(yè))調(diào)度的時(shí)間，進(jìn)程在就調(diào)度的時(shí)間，進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在CPU上執(zhí)行上執(zhí)行的時(shí)間，以及進(jìn)程等待的時(shí)間，以及進(jìn)程等待I/O操作完成的時(shí)間。操作完成的時(shí)間。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分24作為計(jì)算機(jī)系統(tǒng)的管理者，則總是希望能使平均周作為計(jì)算機(jī)系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時(shí)間最短，這不僅會(huì)有效地提高系統(tǒng)資源的

23、利用轉(zhuǎn)時(shí)間最短，這不僅會(huì)有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意?？砂哑骄剩疫€可使大多數(shù)用戶都感到滿意?？砂哑骄苻D(zhuǎn)時(shí)間描述為：周轉(zhuǎn)時(shí)間描述為：niiTnT11思考：周轉(zhuǎn)時(shí)間對(duì)那種系統(tǒng)更重要？思考：周轉(zhuǎn)時(shí)間對(duì)那種系統(tǒng)更重要？第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分25作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間與系統(tǒng)為它提供服務(wù)的時(shí)間Ts之之比，即比，即W = T/Ts，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為：周轉(zhuǎn)時(shí)間則可表示為：niiTTnW1s1第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分26(

24、2) (2) 響應(yīng)時(shí)間快。響應(yīng)時(shí)間快。 所謂響應(yīng)時(shí)間，是從用戶通過(guò)鍵盤提交一個(gè)請(qǐng)所謂響應(yīng)時(shí)間，是從用戶通過(guò)鍵盤提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說(shuō)，直到屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。說(shuō)，直到屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。它包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到它包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間，處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間，處理機(jī)的時(shí)間，處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間，以及將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。以及將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。 思考：響應(yīng)時(shí)間對(duì)那種系統(tǒng)更重要

25、？思考：響應(yīng)時(shí)間對(duì)那種系統(tǒng)更重要？第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分27(3) (3) 截止時(shí)間的保證。截止時(shí)間的保證。 所謂截止時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最所謂截止時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。對(duì)于嚴(yán)格的實(shí)時(shí)遲時(shí)間，或必須完成的最遲時(shí)間。對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn)，系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn)，否則將可能造成難以預(yù)料的后果。否則將可能造成難以預(yù)料的后果。思考：截止時(shí)間對(duì)那種系統(tǒng)更重要？思考：截止時(shí)間對(duì)那種系統(tǒng)更重要？第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分28(4) (4) 優(yōu)先

26、權(quán)準(zhǔn)則。在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選優(yōu)先權(quán)準(zhǔn)則。在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選擇調(diào)度算法時(shí)，都可遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些擇調(diào)度算法時(shí)，都可遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能得到及時(shí)處理。在要求較嚴(yán)格的場(chǎng)合，緊急的作業(yè)能得到及時(shí)處理。在要求較嚴(yán)格的場(chǎng)合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時(shí)處理。得到及時(shí)處理。 第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分292 2面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則(1) 系統(tǒng)吞吐量高。(2) 處理機(jī)利用率好。(3) 各類資源的平衡利用。第三章 處理機(jī)調(diào)度與死鎖3.3調(diào)度算法調(diào)度算法 2022年3

27、月15日0時(shí)54分303.2.1先來(lái)先服務(wù)和短作業(yè)先來(lái)先服務(wù)和短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法1先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法 當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。進(jìn)程，然后放入就緒隊(duì)列。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分31在進(jìn)程調(diào)度中采用在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。成或發(fā)生某事件而阻塞后才放棄處理機(jī)。第三章 處理機(jī)調(diào)度與死鎖2022年3月15日0時(shí)54分32下表列出了下表列出了A A、B B、C C、D D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開(kāi)始執(zhí)行的時(shí)間及各自的完間、要求服務(wù)的時(shí)間、開(kāi)始執(zhí)行的時(shí)間及各自的完成時(shí)間，并計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。