計(jì)算機(jī)操作系統(tǒng)第四章

第4章調(diào)度與死鎖主講：王斯鋒2023/2/51大學(xué)課件本章主要目錄4.1調(diào)度的類型和模型4.2調(diào)度的算法4.3實(shí)時(shí)系統(tǒng)中的調(diào)度4.4多處理機(jī)調(diào)度4.6死鎖的基本概念4.7死鎖的預(yù)防和避免4.8死鎖的檢測(cè)和解除本章基礎(chǔ)要點(diǎn)作業(yè)課后練習(xí)題及參考答案實(shí)戰(zhàn)練習(xí)2023/2/52大學(xué)課件4.1調(diào)度的類型和模型4.1.1調(diào)度的類型一、高級(jí)調(diào)度二、低級(jí)調(diào)度三、中級(jí)調(diào)度4.1.2調(diào)度隊(duì)列模型一、僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型二、具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型三、同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型4.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則一、面向用戶的準(zhǔn)則二、面向系統(tǒng)的準(zhǔn)則4.1.4進(jìn)程調(diào)度的進(jìn)一步理解4.1.5進(jìn)程調(diào)度的功能2023/2/53大學(xué)課件多道程序環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭(zhēng)用處理機(jī)，這就要求系統(tǒng)能按某種算法動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行進(jìn)程。在多道程序系統(tǒng)中，一個(gè)作業(yè)從提交到執(zhí)行，一般都經(jīng)歷多級(jí)調(diào)度。2023/2/54大學(xué)課件作業(yè)與作業(yè)管理1、作業(yè)與作業(yè)步作業(yè)：是用戶要求計(jì)算機(jī)系統(tǒng)所做的一個(gè)計(jì)算問題或一次事務(wù)處理的完整過(guò)程。任何一個(gè)作業(yè)都要經(jīng)過(guò)若干個(gè)步驟之后，才能得到結(jié)果，稱每一個(gè)加工步驟為一個(gè)“作業(yè)步”。一個(gè)作業(yè)的各個(gè)作業(yè)步之間是有聯(lián)系的，上一個(gè)作業(yè)步的輸出是下一下作業(yè)步的輸入。2、作業(yè)控制塊創(chuàng)建一個(gè)進(jìn)程時(shí)，要開辟一個(gè)進(jìn)程控制塊PCB，隨時(shí)記錄進(jìn)程的信息。把一個(gè)作業(yè)提交給系統(tǒng)時(shí)，也要開辟一個(gè)作業(yè)控制塊JCB，隨時(shí)記錄作業(yè)的信息。2023/2/55大學(xué)課件作業(yè)控制塊的內(nèi)容用戶名作業(yè)名作業(yè)類別作業(yè)現(xiàn)行狀態(tài)內(nèi)存需求量作業(yè)優(yōu)先數(shù)外設(shè)類型與需求數(shù)量作業(yè)提交時(shí)間作業(yè)運(yùn)行時(shí)間(估計(jì))作業(yè)控制塊JCB指針其他2023/2/56大學(xué)課件作業(yè)從提交給系統(tǒng)直到它完成后離開系統(tǒng)前的整個(gè)活動(dòng)常劃分為若干個(gè)階段。作業(yè)在每一階段中所處的狀況稱為作業(yè)的狀態(tài)。系統(tǒng)中的作業(yè)通常分為四種狀態(tài)：2023/2/57大學(xué)課件(1)提交狀態(tài)：進(jìn)入外存，作業(yè)的一個(gè)暫時(shí)性的狀態(tài)，其信息還沒有全部進(jìn)入系統(tǒng)，也沒有建立JCB，感知不到它的存在。(2)后備狀態(tài)(收容狀態(tài))：系統(tǒng)收到其全部信息，為其建立JCB，形成后備作業(yè)隊(duì)列，系統(tǒng)能感知到它的存在。2023/2/58大學(xué)課件(3)運(yùn)行狀態(tài)：由作業(yè)調(diào)度進(jìn)入了進(jìn)程調(diào)度階段。(4)完成狀態(tài)：作業(yè)運(yùn)行結(jié)束后的一個(gè)狀態(tài)，是一個(gè)暫時(shí)性狀態(tài)。2023/2/59大學(xué)課件Windows2000/XP中的作業(yè)是共享一組配額限度和安全性限制的進(jìn)程集合；進(jìn)程是內(nèi)存資源分配和打開文件個(gè)數(shù)的基本單位；線程是操作系統(tǒng)調(diào)度處理器的執(zhí)行單位。一個(gè)作業(yè)可以包含一個(gè)或多個(gè)進(jìn)程，一個(gè)進(jìn)程可以包含一個(gè)或多個(gè)線程。一個(gè)進(jìn)程只能屬于一個(gè)作業(yè)，一個(gè)線程只能屬于一個(gè)進(jìn)程。2023/2/510大學(xué)課件系統(tǒng)的運(yùn)行性能，如：吞吐量的大小、周轉(zhuǎn)時(shí)間的長(zhǎng)短、響應(yīng)的及時(shí)性等，很大程度上都取決于調(diào)度。調(diào)度成為多道系統(tǒng)的關(guān)鍵。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序Scheduler完成的。2023/2/511大學(xué)課件4.1調(diào)度的類型和模型從不同的角度進(jìn)行分類，常用分類方法是按調(diào)度的層次，把調(diào)度分為高級(jí)、中級(jí)和低級(jí)調(diào)度；另一種分類是按OS的類型分類，調(diào)度分為批處理調(diào)度、分時(shí)調(diào)度和實(shí)時(shí)調(diào)度及多處理機(jī)調(diào)度。4.1.1調(diào)度類型作業(yè)從進(jìn)入系統(tǒng)并駐留在外存的后備隊(duì)列上開始，直至作業(yè)運(yùn)行完畢，要經(jīng)歷下述三級(jí)調(diào)度。2023/2/512大學(xué)課件一、高級(jí)調(diào)度，又稱作業(yè)調(diào)度或長(zhǎng)程調(diào)度或宏觀調(diào)度。常用于批處理系統(tǒng)，分時(shí)和實(shí)時(shí)都沒有作業(yè)：是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。進(jìn)程：是計(jì)算機(jī)為了完成任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位。一個(gè)作業(yè)總是由一個(gè)以上的多個(gè)進(jìn)程組成的。2023/2/513大學(xué)課件執(zhí)行作業(yè)調(diào)度時(shí)，需解決兩個(gè)問題：1、接納多少個(gè)作業(yè)作業(yè)調(diào)度接納多少個(gè)作業(yè)進(jìn)入內(nèi)存，取決于多道程序度，即允許有多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。2023/2/514大學(xué)課件2、接納哪些作業(yè)2023/2/515大學(xué)課件二、低級(jí)調(diào)度，又稱進(jìn)程調(diào)度、短程調(diào)度、微觀調(diào)度。最基本的調(diào)度，三種類型的操作系統(tǒng)中必須都配置。2023/2/516大學(xué)課件后備隊(duì)列就緒隊(duì)列I/O阻塞隊(duì)列高級(jí)調(diào)度CPU低級(jí)調(diào)度I/Oend2023/2/517大學(xué)課件1、非搶占方式(非剝奪方式)nonpreemptive2、搶占方式(剝奪方式)preemptive,又稱搶奪、搶用、強(qiáng)搶、搶先、剝奪。2023/2/518大學(xué)課件(1)時(shí)間片原則。(2)優(yōu)先權(quán)原則。(3)短作業(yè)(進(jìn)程)優(yōu)先原則。3、完全可搶先f(wàn)ullypreemptive是指任何時(shí)間，不管進(jìn)程處于用戶態(tài)還是核心態(tài)，都可以隨時(shí)被更高優(yōu)先級(jí)的進(jìn)程搶用CPU。2023/2/519大學(xué)課件(1)完全不可搶先或用戶態(tài)不可搶先：當(dāng)前進(jìn)程不論在用戶態(tài)或核心態(tài)時(shí)，都不可以被搶用CPU，這種操作系統(tǒng)稱為不可搶先式的操作系統(tǒng)。如：windows98和windows95(2)內(nèi)核完全不可搶先：當(dāng)前進(jìn)程在用戶態(tài)時(shí)可以被搶占，但當(dāng)在核心態(tài)時(shí)不可被搶占。如：傳統(tǒng)的UNIX3或4.3BSDUNIX、windowsNT2023/2/520大學(xué)課件(3)內(nèi)核的部分可搶先：用戶態(tài)時(shí)可被搶占，核心態(tài)時(shí)大部分時(shí)間不可搶占，而只在某些時(shí)刻點(diǎn)(可搶先點(diǎn)，preemptionpoint)時(shí)可被搶占。UNIXSVR4(4)完全可搶先或內(nèi)核完全可搶先：無(wú)論任何狀態(tài)都可以被搶占。如SUN公司的Solaris2023/2/521大學(xué)課件三、中級(jí)調(diào)度，又稱中程調(diào)度、交換調(diào)度。分時(shí)系統(tǒng)中常用，主要任務(wù)是將內(nèi)存處于阻塞狀態(tài)的某些進(jìn)程調(diào)到外存。

2023/2/522大學(xué)課件引入中級(jí)調(diào)度的目的是，為提高內(nèi)存的利用率和系統(tǒng)吞吐量。中級(jí)調(diào)度實(shí)質(zhì)上是存儲(chǔ)器管理中的對(duì)換功能。2023/2/523大學(xué)課件三種調(diào)度，進(jìn)程調(diào)度的運(yùn)行頻率最高，其調(diào)度算法不能太復(fù)雜，以免占用太多的CPU時(shí)間。作業(yè)調(diào)度發(fā)生在一個(gè)作業(yè)運(yùn)行完畢，退出系統(tǒng)時(shí)又要重新調(diào)入一個(gè)作業(yè)進(jìn)入內(nèi)存時(shí)，調(diào)度的周期長(zhǎng)，其調(diào)度算法花費(fèi)較多的時(shí)間。中級(jí)調(diào)度的運(yùn)行頻率介于兩種之間。2023/2/524大學(xué)課件***4.1.2調(diào)度隊(duì)列模型在上述的三種調(diào)度中，都涉及進(jìn)程隊(duì)列，形成了三種類型的調(diào)度隊(duì)列模型。一、僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型分時(shí)系統(tǒng)中僅有進(jìn)程調(diào)度。用戶的命令直接送入內(nèi)存，OS對(duì)每個(gè)命令命令建立一個(gè)進(jìn)程，按時(shí)間片輪轉(zhuǎn)運(yùn)行。2023/2/525大學(xué)課件每個(gè)進(jìn)程執(zhí)行時(shí)，可能出現(xiàn)三種情況：(1)該任務(wù)在該時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程釋放處理機(jī)后進(jìn)入完成狀態(tài)。(2)任務(wù)在本次其對(duì)應(yīng)的時(shí)間片內(nèi)尚未完成，OS將該任務(wù)放在就緒隊(duì)列的后面。(3)在執(zhí)行期間，進(jìn)程因某事件而被阻塞后，OS將它放入阻塞隊(duì)列。其調(diào)度隊(duì)列模型如圖：2023/2/526大學(xué)課件列隊(duì)緒就列隊(duì)塞阻CPU等待事件進(jìn)程調(diào)度進(jìn)程完成交互用戶時(shí)間片完事件出現(xiàn)內(nèi)存2023/2/527大學(xué)課件二、具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型如圖示：具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型，它與上一模型的區(qū)別：(1)OS中既引入了進(jìn)程調(diào)度，又引入了作業(yè)調(diào)度。后者從外存的后備隊(duì)列選擇一批作業(yè)調(diào)入內(nèi)存，并創(chuàng)建進(jìn)程，然后，送入就緒隊(duì)列。(2)OS中設(shè)置多個(gè)阻塞隊(duì)列。每個(gè)隊(duì)列對(duì)應(yīng)一種引起進(jìn)程阻塞的事件。2023/2/528大學(xué)課件列隊(duì)緒就CPU等待事件1等待事件n等待事件2進(jìn)程調(diào)度時(shí)間片完事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)作業(yè)調(diào)度后備隊(duì)列2023/2/529大學(xué)課件三、同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型

OS引入中級(jí)調(diào)度后，可把進(jìn)程的就緒狀態(tài)分為內(nèi)存就緒狀態(tài)(表示進(jìn)程在內(nèi)存中就緒即活動(dòng)就緒)、外存就緒狀態(tài)(進(jìn)程在外存中就緒即靜止就緒)。也可把阻塞狀態(tài)分成內(nèi)存阻塞(活動(dòng)阻塞)和外存阻塞(靜止阻塞)。

2023/2/530大學(xué)課件三級(jí)調(diào)度的調(diào)度隊(duì)列模型如圖示：2023/2/531大學(xué)課件CPU阻塞隊(duì)列阻塞，掛起隊(duì)列就緒，掛起隊(duì)列就緒隊(duì)列時(shí)間片完后備隊(duì)列作業(yè)調(diào)度批量作業(yè)交互型作業(yè)中級(jí)調(diào)度事件出現(xiàn)掛起等待事件進(jìn)程完成進(jìn)程調(diào)度事件出現(xiàn)2023/2/532大學(xué)課件4.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則(面向用戶和面向系統(tǒng))選擇調(diào)度方式和算法，取決于OS的類型和目標(biāo)，選擇調(diào)度方式和算法的準(zhǔn)則，有的是面向用戶的，有的是面向系統(tǒng)的。2023/2/533大學(xué)課件一、面向用戶的準(zhǔn)則1、周轉(zhuǎn)時(shí)間短，批處理系統(tǒng)中。所謂周轉(zhuǎn)時(shí)間，指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時(shí)間間隔，又稱作業(yè)周轉(zhuǎn)時(shí)間。包括：2023/2/534大學(xué)課件(1)作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時(shí)間(2)進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間。(3)進(jìn)程在CPU上執(zhí)行的時(shí)間。(4)等待I/O操作完成的時(shí)間。

2023/2/535大學(xué)課件作業(yè)周轉(zhuǎn)時(shí)間與系統(tǒng)為它提供的實(shí)際服務(wù)時(shí)間Ts之比，稱為帶權(quán)周轉(zhuǎn)時(shí)間。W=T/Ts，平均帶權(quán)時(shí)間表示為：2、響應(yīng)時(shí)間快，分時(shí)系統(tǒng)中。用于評(píng)價(jià)分時(shí)系統(tǒng)的性能，是選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則。2023/2/536大學(xué)課件響應(yīng)時(shí)間，是從用戶通過(guò)鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或說(shuō)直到在屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。包括：2023/2/537大學(xué)課件(1)從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間。(2)處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間。(3)將所形成的響應(yīng)回送到終端顯示器的時(shí)間。2023/2/538大學(xué)課件3、截止時(shí)間的保證，實(shí)時(shí)系統(tǒng)中。所謂截止時(shí)間，是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間（截止開始），或必須完成的最遲時(shí)間（截止結(jié)束）。2023/2/539大學(xué)課件4、優(yōu)先權(quán)準(zhǔn)則批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中，都可引用優(yōu)先權(quán)準(zhǔn)則，讓某些緊急的作業(yè)，得到及時(shí)的處理。嚴(yán)格的場(chǎng)合，還可選擇搶占調(diào)度方式。二、面向系統(tǒng)的準(zhǔn)則2023/2/540大學(xué)課件1、系統(tǒng)吞吐量高用于評(píng)價(jià)批處理系統(tǒng)性能的重要指標(biāo)。吞吐量是指在單位時(shí)間內(nèi)所完成的作業(yè)數(shù)。它與作業(yè)的平均長(zhǎng)度有密切關(guān)系。作業(yè)的調(diào)度方式和算法，對(duì)吞吐量的大小也產(chǎn)生影響。2023/2/541大學(xué)課件2、處理機(jī)利用率好實(shí)際系統(tǒng)中，CPU的利用率在40%到90%之間。對(duì)大、中型多用戶系統(tǒng)，處理機(jī)的利用率成為衡量性能的重要指標(biāo)。2023/2/542大學(xué)課件3、各類資源的平衡利用選擇適當(dāng)?shù)恼{(diào)度方式和算法，能保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。如：內(nèi)存、外存、I/O設(shè)備等。2023/2/543大學(xué)課件進(jìn)程調(diào)度的進(jìn)一步理解作業(yè)調(diào)度程序在挑選作業(yè)進(jìn)入主存運(yùn)行時(shí)，要為該作業(yè)建立相應(yīng)的進(jìn)程。在作業(yè)完成后要撤消該作業(yè)的全部進(jìn)程。因此作業(yè)調(diào)度程序要調(diào)用操作系統(tǒng)內(nèi)核所提供的有關(guān)的進(jìn)程管理原語(yǔ)，如“建立進(jìn)程”原語(yǔ)和“撤消進(jìn)程”等原語(yǔ)2023/2/544大學(xué)課件由于進(jìn)程只能由其父進(jìn)程建立，所以在一般系統(tǒng)中，作業(yè)調(diào)度程序都以進(jìn)程的形式在系統(tǒng)中存在和活動(dòng)，稱為作業(yè)調(diào)度進(jìn)程。作業(yè)調(diào)度進(jìn)程可以說(shuō)是系統(tǒng)中的祖先進(jìn)程，由它完成作業(yè)調(diào)度的諸功能。2023/2/545大學(xué)課件進(jìn)程調(diào)度的功能是從就緒隊(duì)列中挑選一個(gè)進(jìn)程到處理機(jī)上運(yùn)行。負(fù)責(zé)進(jìn)程調(diào)度功能的內(nèi)核程序稱為進(jìn)程調(diào)度程序。2023/2/546大學(xué)課件讀者往往不易分清作業(yè)調(diào)度程序挑選作業(yè)進(jìn)入主存運(yùn)行和進(jìn)程調(diào)度程序挑選一個(gè)進(jìn)程到處理機(jī)上運(yùn)行，這兩種運(yùn)行之間有何區(qū)別。2023/2/547大學(xué)課件所謂作業(yè)調(diào)度程序挑選作業(yè)進(jìn)主存運(yùn)行是個(gè)宏觀的概念，實(shí)際上被選進(jìn)主存運(yùn)行的作業(yè)只是具有了競(jìng)爭(zhēng)處理機(jī)的機(jī)會(huì)(將來(lái)真正在處理機(jī)上運(yùn)行的是該作業(yè)的一個(gè)進(jìn)程)。而進(jìn)程調(diào)度程序才是真正讓某個(gè)就緒進(jìn)程到處理機(jī)上運(yùn)行。2023/2/548大學(xué)課件由于進(jìn)程調(diào)度程序負(fù)責(zé)在就緒進(jìn)程間轉(zhuǎn)接對(duì)處理機(jī)的控制，所以對(duì)它的調(diào)用相當(dāng)頻繁，每秒要執(zhí)行很多次。它是操作系統(tǒng)核心(常稱為內(nèi)核)的重要組成部分。進(jìn)程調(diào)度程序在系統(tǒng)中以原語(yǔ)形式存在，它是為進(jìn)程在系統(tǒng)內(nèi)的活動(dòng)提供支持。2023/2/549大學(xué)課件進(jìn)程調(diào)度的功能進(jìn)程調(diào)度程序的具體功能如下：1、記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況及狀態(tài)特征。為了實(shí)現(xiàn)進(jìn)程調(diào)度，進(jìn)程管理模塊必須將系統(tǒng)中各進(jìn)程的執(zhí)行情況和狀態(tài)特征記錄在各進(jìn)程的PCB中，同時(shí)還應(yīng)根據(jù)各進(jìn)程的狀態(tài)特征和資源需求等信息將進(jìn)程的PCB組織成相應(yīng)的隊(duì)列，并依據(jù)運(yùn)行情況將進(jìn)程的PCB在不同狀態(tài)隊(duì)列之間轉(zhuǎn)換。進(jìn)程調(diào)度模塊通過(guò)PCB的變化來(lái)掌握系統(tǒng)中所有進(jìn)程的執(zhí)行情況和狀態(tài)特征。2023/2/550大學(xué)課件2、選擇獲得處理機(jī)的進(jìn)程按照一定的策略選擇一個(gè)處于就緒狀態(tài)的進(jìn)程，使其獲得處理機(jī)執(zhí)行。根據(jù)不同的系統(tǒng)設(shè)計(jì)目標(biāo)，有各種各樣的選擇策略。例如先來(lái)先服務(wù)調(diào)度算法、時(shí)間片輪轉(zhuǎn)調(diào)度算法等。這些選擇策略決定了調(diào)度算法的性能。2023/2/551大學(xué)課件3、處理機(jī)分配當(dāng)正在運(yùn)行進(jìn)程由于某種原因要放棄處理機(jī)時(shí)，進(jìn)程調(diào)度程序應(yīng)保護(hù)當(dāng)前運(yùn)行進(jìn)程的CPU現(xiàn)場(chǎng)，將其狀態(tài)由運(yùn)行變成就緒或阻塞，并插入到相應(yīng)隊(duì)列中去，同時(shí)調(diào)度程序還應(yīng)根據(jù)一定原則從就緒隊(duì)列中挑選出一個(gè)進(jìn)程，把該進(jìn)程從就緒隊(duì)列中移出，恢復(fù)其CPU現(xiàn)場(chǎng)，并將其狀態(tài)改變?yōu)檫\(yùn)行。2023/2/552大學(xué)課件引起進(jìn)程調(diào)度的原因有以下幾種：(1)當(dāng)前運(yùn)行進(jìn)程運(yùn)行結(jié)束。因任務(wù)完成而正常結(jié)束，或者因出現(xiàn)錯(cuò)誤而異常結(jié)束。(2)當(dāng)前運(yùn)行進(jìn)程因某種原因，比如I/O請(qǐng)求，從運(yùn)行狀態(tài)進(jìn)入阻塞狀態(tài)。(3)當(dāng)前運(yùn)行進(jìn)程執(zhí)行某種原語(yǔ)操作，如P操作、阻塞原語(yǔ)等，進(jìn)入阻塞狀態(tài)。2023/2/553大學(xué)課件(4)執(zhí)行完系統(tǒng)調(diào)用等系統(tǒng)程序后返回用戶進(jìn)程，這時(shí)可以看作系統(tǒng)進(jìn)程執(zhí)行完畢，從而可以調(diào)度一個(gè)新的用戶進(jìn)程。(5)在采用剝奪調(diào)度方式的系統(tǒng)中，一個(gè)具有更高優(yōu)先級(jí)的進(jìn)程要求使用處理機(jī)，則使當(dāng)前運(yùn)行進(jìn)程進(jìn)入就緒隊(duì)列(這與調(diào)度方式有關(guān))。(6)在分時(shí)系統(tǒng)中，分配給該進(jìn)程的時(shí)間片已用完(這與系統(tǒng)類型有關(guān)，多用于分時(shí)系統(tǒng)中)。2023/2/554大學(xué)課件選擇調(diào)度算法時(shí)應(yīng)考慮的問題在設(shè)計(jì)系統(tǒng)的調(diào)度程序時(shí)，首先要決定選擇何種調(diào)度算法，依據(jù)此算法來(lái)編制相應(yīng)的調(diào)度程序。而調(diào)度算法實(shí)際上就是系統(tǒng)所采取的調(diào)度策略，選擇時(shí)所要考慮的因素很多。如：系統(tǒng)各類資源的均衡使用，對(duì)用戶公平并使用戶滿意，用戶作業(yè)到達(dá)系統(tǒng)的時(shí)間，作業(yè)的優(yōu)先數(shù)，對(duì)主存和外設(shè)的要求，以及整個(gè)系統(tǒng)的效率等。2023/2/555大學(xué)課件但這些因素之間往往相互矛盾，很難兼顧。所以設(shè)計(jì)時(shí)應(yīng)將那些對(duì)系統(tǒng)運(yùn)行影響較大的關(guān)鍵因素作為調(diào)度算法考慮的主要依據(jù)。通常應(yīng)考慮以下因素：2023/2/556大學(xué)課件(1)設(shè)計(jì)目標(biāo)：系統(tǒng)的設(shè)計(jì)目標(biāo)是選擇算法的主要依據(jù)，目標(biāo)不同，系統(tǒng)的設(shè)計(jì)要求自然不同。2023/2/557大學(xué)課件如：批處理系統(tǒng)所追求的是充分發(fā)揮和提高計(jì)算機(jī)的效率；實(shí)時(shí)系統(tǒng)所關(guān)心的是不要丟失實(shí)時(shí)信息并及時(shí)給以處理；分時(shí)系統(tǒng)則側(cè)重于保證用戶的請(qǐng)求及時(shí)給予響應(yīng)，計(jì)算中心要求系統(tǒng)吞吐量要大等等。2023/2/558大學(xué)課件(2)資源利用率：這是評(píng)價(jià)系統(tǒng)性能優(yōu)劣的重要指標(biāo)。因此在確定算法時(shí)，在考慮設(shè)計(jì)目標(biāo)的前提下應(yīng)充分發(fā)揮各種資源的效能，最大限度地使它們忙碌。2023/2/559大學(xué)課件如：將科學(xué)計(jì)算型(CPU型)作業(yè)和數(shù)據(jù)處理型(輸入輸出型)作業(yè)搭配運(yùn)行就是一種方法。為了充分提高資源利用率還應(yīng)注意照顧正在使用關(guān)鍵資源的進(jìn)程，使之優(yōu)先運(yùn)行。2023/2/560大學(xué)課件(3)均衡地處理系統(tǒng)和用戶的要求：由于系統(tǒng)和用戶的要求往往是矛盾的，確定算法時(shí)也要設(shè)法給予緩和。2023/2/561大學(xué)課件一般說(shuō)來(lái)，用戶本能地希望盡快獲得運(yùn)行結(jié)果。但系統(tǒng)有時(shí)卻不能立即滿足用戶要求。如：個(gè)別用戶可能要求使用系統(tǒng)中的幾乎全部外設(shè)，卻只要求很少的主存。系統(tǒng)若滿足這類用戶的愿望，勢(shì)必影響主存利用率，從而降低系統(tǒng)效率，所以一般都不得不推遲這種作業(yè)的運(yùn)行時(shí)間，等到有要求內(nèi)存多而外設(shè)少的作業(yè)與之搭配運(yùn)行。2023/2/562大學(xué)課件但是我們選擇的算法也不應(yīng)使一個(gè)作業(yè)的運(yùn)行被無(wú)限制地推遲。這是用戶無(wú)法忍受的。解決的辦法是使進(jìn)程優(yōu)先數(shù)隨等待時(shí)間而增加。2023/2/563大學(xué)課件(4)在使用優(yōu)先級(jí)的系統(tǒng)中，每個(gè)進(jìn)程都有一個(gè)優(yōu)先數(shù)(或優(yōu)先級(jí))，調(diào)度算法應(yīng)優(yōu)先運(yùn)行高優(yōu)先級(jí)進(jìn)程。2023/2/564大學(xué)課件(5)在使用優(yōu)先數(shù)的系統(tǒng)中，調(diào)度策略還分為“可搶占”和“不可搶占”兩種方式。所謂“不可搶占”是指一旦某個(gè)進(jìn)程分得處理機(jī)后，除非它因等待某事件發(fā)生或已完成其任務(wù)而主動(dòng)讓出處理機(jī)外，不得將處理機(jī)從該進(jìn)程搶走給其它進(jìn)程使用。2023/2/565大學(xué)課件所謂“可搶占”是指可以將處理機(jī)從該進(jìn)程搶占給其它進(jìn)程使用，即使該進(jìn)程仍然需要處理機(jī)。搶占策略通常適用于需要迅速響應(yīng)高優(yōu)先級(jí)進(jìn)程的系統(tǒng)中。但搶占策略要增加系統(tǒng)兩個(gè)方面的開銷：2023/2/566大學(xué)課件首先是增加了處理機(jī)在進(jìn)程間轉(zhuǎn)接的次數(shù)，消耗處理機(jī)機(jī)時(shí)。其次系統(tǒng)為提高搶占工作的效率，在主存中要存放多個(gè)作業(yè)(進(jìn)程)，以保證搶占后，該進(jìn)程可立即投入運(yùn)行，這又增加了不運(yùn)行進(jìn)程占用主存的開銷。2023/2/567大學(xué)課件4.2調(diào)度算法4.2.1先來(lái)先服務(wù)調(diào)度算法一、調(diào)度算法

二、FCFS實(shí)例4.2.2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法4.2.3時(shí)間片輪轉(zhuǎn)調(diào)度算法一、基本原理

二、時(shí)間片大小的確定4.2.4優(yōu)先權(quán)調(diào)度算法一、優(yōu)先權(quán)調(diào)度算法的類型二、優(yōu)先權(quán)的類型2023/2/568大學(xué)課件4.2.5高響應(yīng)比優(yōu)先調(diào)度算法4.2.6最短剩余時(shí)間優(yōu)先調(diào)度算法練習(xí)4.2.7多級(jí)隊(duì)列調(diào)度4.2.8多級(jí)反饋隊(duì)列調(diào)度算法一、調(diào)度算法二、多級(jí)反饋隊(duì)列算法的性能4.2.9彩票調(diào)度算法LotteryScheduling4.2.10進(jìn)程調(diào)度的實(shí)現(xiàn)2023/2/569大學(xué)課件

OS調(diào)度實(shí)質(zhì)是一種資源分配。調(diào)度算法是指，根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。系統(tǒng)采用一種調(diào)度算法，意味著作業(yè)的運(yùn)行對(duì)應(yīng)著一種調(diào)度順序。了解每一種算法的思想、特點(diǎn)和適應(yīng)范圍。2023/2/570大學(xué)課件4.2.1先來(lái)先服務(wù)調(diào)度算法FCFS或FIFO(先進(jìn)先出)(非剝奪式)

一、調(diào)度算法基本思想是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)分配處理機(jī)。非剝奪的調(diào)度方式。2023/2/571大學(xué)課件從表面上看，先來(lái)先服務(wù)算法對(duì)于所有作業(yè)是公平的，即按照它們到來(lái)的先后次序進(jìn)行服務(wù)。但：短作業(yè)在系統(tǒng)中的駐留平均時(shí)間與長(zhǎng)作業(yè)的駐留平均時(shí)間相同。2023/2/572大學(xué)課件很少被用作主要調(diào)度策略，常作為一種輔助調(diào)度算法使用。如例表：2023/2/573大學(xué)課件111001.991100100199110110220201101102110011000123ABCD帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間完成時(shí)間開始執(zhí)行時(shí)間服務(wù)時(shí)間到達(dá)時(shí)間進(jìn)程名2023/2/574大學(xué)課件從表知：短作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間(周轉(zhuǎn)時(shí)間(完成時(shí)間-到達(dá)時(shí)間)/應(yīng)服務(wù)時(shí)間)高達(dá)100，是不可容忍的。長(zhǎng)作業(yè)D的帶權(quán)時(shí)間為1.992023/2/575大學(xué)課件FCFS有利于CPU繁忙型（科學(xué)計(jì)算型）的作業(yè)，不利于I/O繁忙型（數(shù)據(jù)處理型）的作業(yè)(進(jìn)程)。

CPU約束的CPU-bound:編譯程序、科技計(jì)算程序、算法程序等。I/O約束的I/O-bound：編輯排版程序、游戲程序等。2023/2/576大學(xué)課件二、FCFS實(shí)例如圖示：有五個(gè)進(jìn)程A、B、C、D和E。2023/2/577大學(xué)課件調(diào)度算法作業(yè)情況2.12.251.53.22.671帶權(quán)周轉(zhuǎn)時(shí)間8931684周轉(zhuǎn)時(shí)間1361894完成時(shí)間2.83.55.5221帶權(quán)周轉(zhuǎn)時(shí)間914111064周轉(zhuǎn)時(shí)間18141274完成時(shí)間42534服務(wù)時(shí)間43210到達(dá)時(shí)間平均EDCBA進(jìn)程名FCFS(a)SJF(b)2023/2/578大學(xué)課件4.2.2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，又稱最短CPU運(yùn)行期優(yōu)先SCBF（shortestCPUburstfirst）

從就緒隊(duì)列中選出下一個(gè)“CPU執(zhí)行期”最短的進(jìn)程。主要用于作業(yè)調(diào)度。非搶占式的策略。2023/2/579大學(xué)課件SJF算法用于作業(yè)調(diào)度。

SPF算法進(jìn)程調(diào)度。2023/2/580大學(xué)課件和FCFS算法相比較，平均周轉(zhuǎn)時(shí)間及平均帶權(quán)周轉(zhuǎn)時(shí)間有明顯的改善，尤其對(duì)短作業(yè)，所以，SJF能有效地降低作業(yè)的平均等待時(shí)間和提高系統(tǒng)的吞吐量。2023/2/581大學(xué)課件其缺點(diǎn)：(1)該算法對(duì)長(zhǎng)作業(yè)非常不利。嚴(yán)重的會(huì)導(dǎo)致長(zhǎng)作業(yè)得不到調(diào)度。所以不適合于分時(shí)系統(tǒng)。它不能保證對(duì)用戶及時(shí)響應(yīng)。饑餓或餓死現(xiàn)象。2023/2/582大學(xué)課件(2)該算法完全未考慮作業(yè)的緊迫程度，不能保證緊迫性作業(yè)(進(jìn)程)會(huì)得到及時(shí)處理。(3)作業(yè)(進(jìn)程)的長(zhǎng)短是根據(jù)用戶提供的估計(jì)執(zhí)行時(shí)間而定的，不一定能真正做到短作業(yè)優(yōu)先調(diào)度。2023/2/583大學(xué)課件練習(xí)：若在后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)1、2、3，已知它們各自的運(yùn)行時(shí)間為a,b,c，且滿足關(guān)系a<b<c，試證明采用短作業(yè)優(yōu)先算法能獲得最小平均周轉(zhuǎn)時(shí)間。2023/2/584大學(xué)課件解：由于短作業(yè)優(yōu)先調(diào)度算法總是在后備作業(yè)隊(duì)列中選擇運(yùn)行時(shí)間最短的作業(yè)作為調(diào)度對(duì)象，所以，對(duì)短作業(yè)優(yōu)先調(diào)度算法而言，這三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為：T1＝a+(a+b)+(a+b+c)=3a+2b+c(一)若不按短作業(yè)優(yōu)先調(diào)度算法來(lái)調(diào)度這三個(gè)作業(yè)，不失一般性，假定調(diào)度順序?yàn)?、1、3，則其總周轉(zhuǎn)時(shí)間為：T2＝b+(b+a)+(b+a+c)=3b+2a+c(二)由（二）-（一）得：T2－T1＝b-a>0由此可見：短作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時(shí)間2023/2/585大學(xué)課件反例：考慮5個(gè)作業(yè)，從A到E，運(yùn)行時(shí)間分別是2,4,1,1和1。它們的到達(dá)時(shí)間是0,0,3,3和3。開始只能選擇A或B，因?yàn)槠渌淖鳂I(yè)還沒有到達(dá)。使用最短作業(yè)優(yōu)先，將按照A，B，C，D，E的順序運(yùn)行作業(yè)，其平均等待時(shí)間是4.6。但是，按照B，C，D，E，A的順序運(yùn)行作業(yè)，其平均等待的時(shí)間是4.4。2023/2/586大學(xué)課件4.2.3時(shí)間片輪轉(zhuǎn)調(diào)度算法，分時(shí)系統(tǒng)中采用，用于進(jìn)程調(diào)度。搶占式策略。一、基本原理RR或TRR（RoundRobin）

基本思想：讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待時(shí)間與享受服務(wù)的時(shí)間成比例。2023/2/587大學(xué)課件將CPU的處理時(shí)間分成固定大小的時(shí)間片。時(shí)間片的大小從幾ms到幾百ms，早期默認(rèn)100ms，現(xiàn)在一般在50ms或25ms。2023/2/588大學(xué)課件保證了就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。2023/2/589大學(xué)課件就緒隊(duì)列I/O阻塞隊(duì)列I/O時(shí)間片用完進(jìn)程結(jié)束高級(jí)調(diào)度因I/O請(qǐng)求而阻塞CPU簡(jiǎn)單輪轉(zhuǎn)法的調(diào)度模型2023/2/590大學(xué)課件二、時(shí)間片大小的確定時(shí)間片的大小對(duì)系統(tǒng)的性能有很大影響。太大時(shí)，則成了FCFS。太小時(shí)，切換過(guò)于頻繁，影響響應(yīng)時(shí)間。所以，時(shí)間片要適當(dāng)。2023/2/591大學(xué)課件時(shí)間片長(zhǎng)度的選擇是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求R和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)N。

q=R/N2023/2/592大學(xué)課件如圖示：各進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。2023/2/593大學(xué)課件時(shí)間片作業(yè)情況2.53.3352.2521帶權(quán)周轉(zhuǎn)時(shí)間8.41310964周轉(zhuǎn)時(shí)間17131174完成時(shí)間3.463.3333.53.673.75帶權(quán)周轉(zhuǎn)時(shí)間11.8136141115周轉(zhuǎn)時(shí)間179161215完成時(shí)間42434服務(wù)時(shí)間43210到達(dá)時(shí)間平均EDCBA進(jìn)程名RRq=1RRq=42023/2/594大學(xué)課件＊＊一、進(jìn)程調(diào)度算法計(jì)算題（華師大2002年試題）＊＊假定有進(jìn)程，它們的提交時(shí)間、運(yùn)行時(shí)間如下：作業(yè)號(hào)到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間結(jié)束時(shí)間103224342464要求：1、采用先來(lái)先服務(wù)算法，分別計(jì)算這批進(jìn)程的平均輪轉(zhuǎn)時(shí)間、平均帶權(quán)輪轉(zhuǎn)時(shí)間2、采用時(shí)間片輪轉(zhuǎn)算法（時(shí)間片Q=2），分別計(jì)算這批進(jìn)程的平均輪轉(zhuǎn)時(shí)間、平均帶權(quán)輪轉(zhuǎn)時(shí)間。2023/2/595大學(xué)課件練習(xí)有5個(gè)批任務(wù)幾乎同時(shí)到達(dá)，其預(yù)計(jì)的運(yùn)行時(shí)間A,B,C,D,E分別為6，10，2，8，4分，計(jì)算其在時(shí)間片輪轉(zhuǎn)算法下的平均進(jìn)程周轉(zhuǎn)時(shí)間。（進(jìn)程切換開銷可以忽略）2023/2/596大學(xué)課件這里并沒有明確地給出時(shí)間片的大小，在這種情況下，一般默認(rèn)時(shí)間片很小（操作系統(tǒng)中一般時(shí)間片為0.1秒）。

然后，在本題中，顯然任務(wù)C先執(zhí)行完，在任務(wù)C執(zhí)行完的時(shí)候，任務(wù)D,E只跟C相差很小的時(shí)間，可以近似的認(rèn)為A,B,C,D,E都執(zhí)行了2分鐘。那么，C的周轉(zhuǎn)時(shí)間就是10分鐘。接著，A,B,D,E再都執(zhí)行2分鐘，E任務(wù)結(jié)束，所以，E的周轉(zhuǎn)時(shí)間是18分鐘。

依次類推，A的周轉(zhuǎn)時(shí)間為24分鐘，D的周轉(zhuǎn)時(shí)間為28分鐘，B為30分鐘。2023/2/597大學(xué)課件多級(jí)反饋輪轉(zhuǎn)法輪轉(zhuǎn)法中有三種進(jìn)程：（1）時(shí)間片用完，但未結(jié)束。（2）運(yùn)行期間被阻塞。（3）新進(jìn)程。不同進(jìn)程給予不同的優(yōu)先級(jí)和時(shí)間片。2023/2/598大學(xué)課件4.2.4最高優(yōu)先權(quán)優(yōu)先調(diào)度算法（FPF）最常用的一種算法。一、最高優(yōu)先權(quán)調(diào)度算法的類型“急事先辦，要事先辦”。作業(yè)調(diào)度和進(jìn)程調(diào)度。2023/2/599大學(xué)課件1、非搶占式優(yōu)先權(quán)算法

主要用于批處理系統(tǒng)中，也可用于對(duì)實(shí)時(shí)性要求不高的實(shí)時(shí)系統(tǒng)中。2023/2/5100大學(xué)課件2、搶占式優(yōu)先權(quán)調(diào)度算法任一時(shí)刻運(yùn)行的是優(yōu)先級(jí)最高的進(jìn)程。2023/2/5101大學(xué)課件該算法更好地滿足了緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求高的批處理和分時(shí)系統(tǒng)中。該算法的關(guān)鍵是如何確定進(jìn)程的優(yōu)先權(quán)，方法如下兩種：2023/2/5102大學(xué)課件二、優(yōu)先權(quán)的類型1、靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般利用某一范圍內(nèi)一個(gè)整數(shù)表示，該整數(shù)稱為優(yōu)先數(shù)。如：0~7或0~255。2023/2/5103大學(xué)課件確定進(jìn)程優(yōu)先權(quán)的依據(jù)：(1)進(jìn)程類型。系統(tǒng)進(jìn)程高于用戶進(jìn)程,聯(lián)機(jī)用戶于脫機(jī)用戶進(jìn)程的優(yōu)先權(quán)。(2)進(jìn)程對(duì)資源的要求。執(zhí)行時(shí)間及內(nèi)存需要量少的進(jìn)程，有較高的優(yōu)先權(quán)。2023/2/5104大學(xué)課件(3)根據(jù)用戶要求。由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來(lái)確定進(jìn)程的優(yōu)先權(quán)。2023/2/5105大學(xué)課件2、動(dòng)態(tài)優(yōu)先權(quán)，是基于某種原則，使進(jìn)程的優(yōu)先權(quán)隨時(shí)間而改變。是指在創(chuàng)建進(jìn)程時(shí)，根據(jù)系統(tǒng)資源的使用情況和進(jìn)程的當(dāng)前特點(diǎn)所賦予的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)而改變，以獲得更好的調(diào)度性能。2023/2/5106大學(xué)課件具有相同的優(yōu)先權(quán)初值，最先進(jìn)入就緒隊(duì)列的進(jìn)程，將先獲得處理機(jī)。即FCFS。具有互不相同的優(yōu)先權(quán)初值，優(yōu)先權(quán)初值低的進(jìn)程，等待足夠時(shí)間后，其優(yōu)先權(quán)會(huì)升為最高，從而獲得處理機(jī)執(zhí)行。練習(xí)2023/2/5107大學(xué)課件4.2.5高響應(yīng)比優(yōu)先調(diào)度算法（HighestResponse_ratio

Next）HRN(Hansen)

是對(duì)FCFS和SJF的綜合平衡。FCFS只考慮等待時(shí)間而未考慮執(zhí)行時(shí)間的長(zhǎng)短。SJF只考慮執(zhí)行時(shí)間未考慮等待時(shí)間的長(zhǎng)短。2023/2/5108大學(xué)課件為每個(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)機(jī)制，并使之以速率a增加，則長(zhǎng)作業(yè)等待一定的時(shí)間后，會(huì)有機(jī)會(huì)分配到處理機(jī)。優(yōu)先權(quán)的變化：優(yōu)先權(quán)＝(等待時(shí)間＋要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間2023/2/5109大學(xué)課件等待時(shí)間加上要求服務(wù)時(shí)間，即該作業(yè)的響應(yīng)時(shí)間。所以，優(yōu)先權(quán)又稱為響應(yīng)比Rp:

Rp=優(yōu)先權(quán)＝響應(yīng)時(shí)間/要求服務(wù)時(shí)間由此看出：（1）若作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，優(yōu)先權(quán)愈高，則該算法有利于短作業(yè)。2023/2/5110大學(xué)課件（2）若要求服務(wù)的時(shí)間相同，作業(yè)的優(yōu)先權(quán)取決其等待時(shí)間，實(shí)現(xiàn)了先來(lái)先服務(wù)。（3）對(duì)長(zhǎng)作業(yè)，其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)會(huì)升到很高，從而可獲得處理機(jī)。2023/2/5111大學(xué)課件所以，該算法既有利于短作業(yè)，又考慮了作業(yè)到達(dá)的先后順序，使長(zhǎng)作業(yè)也能得到服務(wù)。不過(guò)，利用該算法時(shí)，在調(diào)度前，要先進(jìn)行響應(yīng)比的計(jì)算，有一定的開銷。練習(xí)2023/2/5112大學(xué)課件4.2.6最短剩余時(shí)間優(yōu)先調(diào)度算法(SRTF,ShortestRemainingTimeFirst)最短剩余時(shí)間優(yōu)先調(diào)度算法是把最短作業(yè)優(yōu)先算法使用于分時(shí)環(huán)境中的變型。其基本思想是讓運(yùn)行到作業(yè)完成時(shí)所需的運(yùn)行時(shí)間最短的進(jìn)程優(yōu)先得到處理，其中包括新進(jìn)入系統(tǒng)的進(jìn)程。2023/2/5113大學(xué)課件在最短作業(yè)優(yōu)先策略中，一個(gè)作業(yè)一旦得到處理機(jī)就一直運(yùn)行到完成(或等待事件)而不能被搶占(除非主動(dòng)讓出處理機(jī))。而最短剩余時(shí)間優(yōu)先策略是可以被一個(gè)新進(jìn)入系統(tǒng)，并且其運(yùn)行時(shí)間少于當(dāng)前運(yùn)行進(jìn)程的剩余運(yùn)行時(shí)間的進(jìn)程所搶占。2023/2/5114大學(xué)課件本策略的優(yōu)點(diǎn)是可以用于分時(shí)系統(tǒng)，保證及時(shí)響應(yīng)用戶要求。缺點(diǎn)是系統(tǒng)開銷增加，首先要保存進(jìn)程的運(yùn)行情況記錄，以比較其剩余時(shí)間大小。其次，搶占本身也要消耗處理機(jī)時(shí)間。毫無(wú)疑問，這個(gè)策略使短作業(yè)一進(jìn)入系統(tǒng)就能立即得到服務(wù)，從而降低作業(yè)的平均等待時(shí)間。2023/2/5115大學(xué)課件假設(shè)有一個(gè)系統(tǒng)中有5個(gè)進(jìn)程，它們的到達(dá)時(shí)間和服務(wù)時(shí)間如表所示，忽略I/O以及其他開銷時(shí)間，若分別按高響應(yīng)比優(yōu)先、非搶占及搶占的短進(jìn)程優(yōu)先調(diào)度算法進(jìn)行CPU調(diào)度，請(qǐng)給出各進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間2023/2/5116大學(xué)課件進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A03B26C44D65E822023/2/5117大學(xué)課件線性優(yōu)先級(jí)調(diào)度策略

(SRR)selfishroundrobin新創(chuàng)建的進(jìn)程按FCFS排成就緒隊(duì)列A，而其他已得到過(guò)時(shí)間片服務(wù)的進(jìn)程也按FCFS排成另一個(gè)就緒隊(duì)列或稱享受服務(wù)隊(duì)列B。

對(duì)兩個(gè)不同隊(duì)列中的進(jìn)程，設(shè)置不同的優(yōu)先級(jí)P。A中的優(yōu)先級(jí)以a的速率增加：

P＝a*t(a>0)B中的優(yōu)先級(jí)以b的速率增加：

P＝b*t(a>b>0)2023/2/5118大學(xué)課件所以，某一進(jìn)程在t1被創(chuàng)建，在t時(shí)刻,該進(jìn)程的優(yōu)先級(jí)為

P(t)=a*(t-t1)若該進(jìn)程在t2時(shí)刻轉(zhuǎn)入B隊(duì)列中，則在時(shí)刻t，該進(jìn)程的優(yōu)先級(jí)為

P(t)=a*(t2-t1)+b*(t-t2)2023/2/5119大學(xué)課件當(dāng)A隊(duì)列中的第一個(gè)進(jìn)程優(yōu)先級(jí)和B隊(duì)列中最后一個(gè)進(jìn)程的優(yōu)先級(jí)相等時(shí)，A中的第一個(gè)進(jìn)程可以轉(zhuǎn)入B隊(duì)列?；虍?dāng)B隊(duì)列為空時(shí)，A中的第一個(gè)進(jìn)程可轉(zhuǎn)入B隊(duì)列。2023/2/5120大學(xué)課件顯然，a>b>0的條件是必要的。若b>a>0時(shí)，兩個(gè)隊(duì)列中優(yōu)先級(jí)永遠(yuǎn)不會(huì)相等，B中永遠(yuǎn)只有一個(gè)進(jìn)程，轉(zhuǎn)化成了FCFS算法。若a>b=0時(shí)，則轉(zhuǎn)化為RR法。2023/2/5121大學(xué)課件練習(xí)一、設(shè)有四道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如下：

作業(yè)號(hào)提交時(shí)間執(zhí)行時(shí)間123410.010.210.410.52.01.00.50.32023/2/5122大學(xué)課件試計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法進(jìn)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出它們的調(diào)度順序。（時(shí)間單位：小時(shí)，以十進(jìn)制進(jìn)行計(jì)算）2023/2/5123大學(xué)課件練習(xí)解：采用先來(lái)先服務(wù)調(diào)度算法，則其調(diào)度順序?yàn)?、2、3、4。作業(yè)號(hào)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間123410.010.210.410.52.01.00.50.310.012.013.013.512.013.013.513.82.02.83.13.31.02.86.211.02023/2/5124大學(xué)課件平均周轉(zhuǎn)時(shí)間：T=(2.0+2.8+3.1+3.3)/4=2.8平均帶權(quán)周轉(zhuǎn)時(shí)間：W=(1+2.8+6.2+11)/4=5.25采用短作業(yè)優(yōu)先調(diào)度算法自己練習(xí)T=2.45,W=3.85。2023/2/5125大學(xué)課件二、下表給出作業(yè)1、2、3的到達(dá)時(shí)間和運(yùn)行時(shí)間。采用短作業(yè)優(yōu)先調(diào)度算法和先來(lái)先服務(wù)調(diào)度算法，試問平均周轉(zhuǎn)時(shí)間各為多少？是否還有更好的調(diào)度策略存在？（時(shí)間單位：小時(shí)，以十進(jìn)制進(jìn)行計(jì)算）。練習(xí)2023/2/5126大學(xué)課件作業(yè)號(hào)到達(dá)時(shí)間運(yùn)行時(shí)間1230.00.41.08.04.01.02023/2/5127大學(xué)課件練習(xí)采用先來(lái)先服務(wù)調(diào)度算法：平均周轉(zhuǎn)時(shí)間T=10.53采用短作業(yè)優(yōu)先調(diào)度策略，順序：1、3、2平均周轉(zhuǎn)時(shí)間T=9.53存在縮短平均周轉(zhuǎn)時(shí)間的策略，即還有兩個(gè)短作業(yè)，等所有作業(yè)都到達(dá)后，再按短作業(yè)優(yōu)先調(diào)度算法調(diào)度，順序：3、2、1，平均周轉(zhuǎn)時(shí)間T=6.872023/2/5128大學(xué)課件練習(xí)三、假設(shè)有四個(gè)作業(yè)，它們的提交、執(zhí)行時(shí)間如下表所示。若采用響應(yīng)比高者優(yōu)先調(diào)度算法，試問平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間為多少？作業(yè)號(hào)到達(dá)時(shí)間運(yùn)行時(shí)間12348.08.38.59.02.00.50.10.4返回2023/2/5129大學(xué)課件練習(xí)解：調(diào)度順序：1、3、2、4。T=1.975W=6.658點(diǎn)鐘時(shí)，只有作業(yè)1到達(dá)，系統(tǒng)先1投入運(yùn)行，運(yùn)行2小時(shí)后即10點(diǎn)鐘完成。剩下三個(gè)作業(yè)的響應(yīng)比為：r2=1+(10.3-8.3)/0.5=4.4r3=1+(10.0-8.5)/0.1=16r4=1+(10.0-9.0)/0.4=3.5返回2023/2/5130大學(xué)課件所以，作業(yè)2的響應(yīng)比最高，先讓3運(yùn)行，運(yùn)行0.1小時(shí)完成，此時(shí)，2和4的響應(yīng)比為：

r2=1+(10.1-8.3)/0.5=4.6r4=1+(10.1-9.0)/0.4=3.75

可知2的響應(yīng)比高，先讓2運(yùn)行。返回2023/2/5131大學(xué)課件練習(xí)四、今有三個(gè)批處理作業(yè)。第一個(gè)作業(yè)10：00到達(dá)，需要執(zhí)行2小時(shí)，第二個(gè)作業(yè)在10：10到達(dá)，需要執(zhí)行1小時(shí)，第三個(gè)作業(yè)在10：25到達(dá)，需要執(zhí)行25分鐘。分別采用如下三種調(diào)度算法：（1）計(jì)算各調(diào)度算法下的作業(yè)平均周轉(zhuǎn)時(shí)間(以小時(shí)為單位)（2）調(diào)度算法1、3分別是什么作業(yè)調(diào)度算法？2023/2/5132大學(xué)課件作業(yè)號(hào)到達(dá)時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間1231010:1010:25101213121313:25調(diào)度算法12023/2/5133大學(xué)課件作業(yè)號(hào)到達(dá)時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間1231010:1010:2511:5010:5010:2513:5011:5010:50調(diào)度算法22023/2/5134大學(xué)課件作業(yè)號(hào)到達(dá)時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間1231010:1010:251012:25121213:2512:25調(diào)度算法32023/2/5135大學(xué)課件練習(xí)五、（北京大學(xué)95年試題）有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。作業(yè)號(hào)到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間（分鐘）優(yōu)先數(shù)ABCD1010:2010:3010:50403050205346返回2023/2/5136大學(xué)課件練習(xí)要求：（1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間（2）計(jì)算平均周轉(zhuǎn)時(shí)間(以分鐘計(jì)算)2023/2/5137大學(xué)課件練習(xí)解：本題中，每個(gè)作業(yè)的運(yùn)行都將經(jīng)歷兩級(jí)調(diào)度：作業(yè)調(diào)度和進(jìn)程調(diào)度。只有當(dāng)作業(yè)調(diào)度程序?qū)⒆鳂I(yè)裝入內(nèi)存后，才能參與進(jìn)程調(diào)度。而系統(tǒng)是兩道作業(yè)系統(tǒng)，每次只能有兩道作業(yè)進(jìn)入內(nèi)存。2023/2/5138大學(xué)課件本題中的作業(yè)和進(jìn)程推進(jìn)順序：10：00，A到達(dá)，作業(yè)調(diào)度程序先將A調(diào)入內(nèi)存并排在就緒隊(duì)列上，進(jìn)程調(diào)度調(diào)度它運(yùn)行。10：20，B到達(dá)，后備隊(duì)列無(wú)其它作業(yè)，作業(yè)調(diào)度程序?qū)調(diào)入內(nèi)存并排在就緒隊(duì)列上，B的優(yōu)先級(jí)高于A，進(jìn)程調(diào)度程序停止A的運(yùn)行，將A放入就緒隊(duì)列，調(diào)度B運(yùn)行，此時(shí)，已有兩道作業(yè)在內(nèi)存中，A已運(yùn)行20分鐘。2023/2/5139大學(xué)課件練習(xí)10：30，C到達(dá)，但只能在后備作業(yè)隊(duì)列中等待作業(yè)調(diào)度，B已運(yùn)行了10分鐘，A已等待10分鐘，還需運(yùn)行20分鐘才能完成。10：50，B運(yùn)行結(jié)束，D到達(dá)，內(nèi)存中只有A，后備隊(duì)列中有C、D，按短作業(yè)優(yōu)先的作業(yè)調(diào)度策略，作業(yè)D被優(yōu)先調(diào)入內(nèi)存，在內(nèi)存中，A的優(yōu)先級(jí)高于D，A運(yùn)行，D在就緒隊(duì)列中等待。此時(shí)，A已運(yùn)行了20分鐘，等待了30分鐘，再運(yùn)行20分鐘，C已在后備隊(duì)列中等待了20分鐘。2023/2/5140大學(xué)課件11：10，A運(yùn)行結(jié)束，內(nèi)存只有D，作業(yè)調(diào)度將C調(diào)入內(nèi)存，由于C優(yōu)先級(jí)高于D，進(jìn)程調(diào)度調(diào)度C運(yùn)行，D繼續(xù)等待。12：00，C結(jié)束運(yùn)行，D調(diào)度運(yùn)行。12：20，D結(jié)束運(yùn)行。2023/2/5141大學(xué)課件4.2.7多級(jí)隊(duì)列調(diào)度多隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型，將就緒隊(duì)列分成多級(jí)獨(dú)立子隊(duì)列，各個(gè)作業(yè)固定的分屬于一個(gè)隊(duì)列。不同的隊(duì)列采用不同的調(diào)度算法，各級(jí)隊(duì)列之間的關(guān)系可采用優(yōu)先權(quán)或按分配CPU的時(shí)間比例進(jìn)行調(diào)度。2023/2/5142大學(xué)課件4.2.8多級(jí)反饋隊(duì)列調(diào)度算法(多重隊(duì)列法.MLFQ,Multi-LevelFeedbackQueue,反饋循環(huán)隊(duì)列)多級(jí)反饋隊(duì)列調(diào)度算法，不必事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，還可以滿足各種類型進(jìn)程的需要，是比較好的一種進(jìn)程調(diào)度算法。UNIX和OS/2中都采用了類似的調(diào)度算法。Solaris和Windows2000/NT也都采用它。2023/2/5143大學(xué)課件一、調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法的實(shí)施過(guò)程：(1)系統(tǒng)中有多個(gè)進(jìn)程就緒隊(duì)列，每個(gè)就緒隊(duì)列對(duì)應(yīng)一個(gè)調(diào)度級(jí)別，各級(jí)具有不同的運(yùn)行優(yōu)先級(jí)。第一級(jí)隊(duì)列的優(yōu)先級(jí)最高，以下各級(jí)隊(duì)列的優(yōu)先級(jí)逐次降低。2023/2/5144大學(xué)課件(2)各級(jí)就緒隊(duì)列中的進(jìn)程具有不同的時(shí)間片。優(yōu)先級(jí)最高的第1級(jí)隊(duì)列中的進(jìn)程的時(shí)間片最小，隨著隊(duì)列的級(jí)別增加其進(jìn)程的優(yōu)先級(jí)降低了，但時(shí)間片卻增加了。一般提高一級(jí)其時(shí)間片增加一倍。2023/2/5145大學(xué)課件(3)各級(jí)隊(duì)列均按先來(lái)先服務(wù)原則排序。(4)調(diào)度方法：當(dāng)一個(gè)新進(jìn)程進(jìn)入系統(tǒng)后，它被放入第1級(jí)就緒隊(duì)列的末尾。該隊(duì)列中的進(jìn)程按先來(lái)先服務(wù)原則分給處理機(jī)，并運(yùn)行一個(gè)相應(yīng)于該隊(duì)列的時(shí)間片。2023/2/5146大學(xué)課件假如進(jìn)程在這個(gè)時(shí)間片中完成了其全部工作或因等待事件或等待輸入輸出而主動(dòng)放棄了處理機(jī)，于是該進(jìn)程或撤離系統(tǒng)(任務(wù)完成)或進(jìn)入相應(yīng)的等待隊(duì)列，從而離開了就緒隊(duì)列。2023/2/5147大學(xué)課件若進(jìn)程使用完了整個(gè)時(shí)間片后，其運(yùn)行任務(wù)并未完成仍然要求運(yùn)行(也沒能產(chǎn)生輸入輸出要求)。于是該進(jìn)程被搶占處理機(jī)，同時(shí)將它放入下一級(jí)就緒隊(duì)列的末尾。2023/2/5148大學(xué)課件(5)當(dāng)?shù)谝患?jí)進(jìn)程就緒隊(duì)列為空后，調(diào)度程序才去調(diào)度第2級(jí)就緒隊(duì)列中的進(jìn)程。其調(diào)度方法同前。當(dāng)?shù)?，第2隊(duì)列皆為空時(shí)才去調(diào)度第3級(jí)隊(duì)列中進(jìn)程……。當(dāng)前面各級(jí)隊(duì)列皆為空時(shí)，才去調(diào)度最后第n級(jí)隊(duì)列中的進(jìn)程。第n級(jí)(最低級(jí))隊(duì)列中的進(jìn)程是采用時(shí)間片輪轉(zhuǎn)方法進(jìn)行調(diào)度。2023/2/5149大學(xué)課件(6)當(dāng)比運(yùn)行進(jìn)程更高級(jí)別的隊(duì)列中到來(lái)一個(gè)新的進(jìn)程時(shí)，它將搶占運(yùn)行進(jìn)程的處理機(jī)，而被搶占的進(jìn)程回到原隊(duì)列的末尾。2023/2/5150大學(xué)課件多級(jí)反饋隊(duì)列的調(diào)度操作已大致描述如上，它是根據(jù)進(jìn)程執(zhí)行情況的反饋信息而對(duì)進(jìn)程隊(duì)列進(jìn)行組織并調(diào)度進(jìn)程，故而得名。2023/2/5151大學(xué)課件二、多級(jí)反饋隊(duì)列調(diào)度算法的性能：能滿足各種類型用戶的需要1、終端型作業(yè)用戶2、短批處理作業(yè)用戶3、長(zhǎng)批處理作業(yè)用戶使用多級(jí)反饋隊(duì)列調(diào)度算法的例子是著名的WindowsNT操作系統(tǒng)的調(diào)度算法。2023/2/5152大學(xué)課件進(jìn)程名ABCD到達(dá)時(shí)間0123服務(wù)時(shí)間10482第一隊(duì)列Q=4完成時(shí)間481214第二隊(duì)列Q=8完成時(shí)間2024第n隊(duì)列完成時(shí)間2023/2/5153大學(xué)課件4.2.9彩票調(diào)度算法LotteryScheduling系統(tǒng)為每種資源發(fā)放不同數(shù)量的彩票給不同的進(jìn)程。調(diào)度程序?qū)δ撤N資源做出調(diào)度決策時(shí)，隨機(jī)選擇一張彩票，彩票的持有者將獲得相應(yīng)的系統(tǒng)資源。協(xié)作進(jìn)程可以交換彩票，客戶進(jìn)程給服務(wù)器進(jìn)程發(fā)送消息后而阻塞，客戶進(jìn)程可以把彩票全部交給服務(wù)器進(jìn)程。服務(wù)器進(jìn)程完成服務(wù)后，又把彩票還給客戶進(jìn)程。2023/2/5154大學(xué)課件10、策略驅(qū)動(dòng)法：11、最晚時(shí)間限調(diào)度deadlinescheduling：保證在每個(gè)進(jìn)程必須完成的最晚時(shí)間限前運(yùn)行完該進(jìn)程。12、二級(jí)調(diào)度法：后備隊(duì)列和就緒隊(duì)列。Linux中CPU調(diào)度算法可由用戶通過(guò)宏定義來(lái)選擇，可選的算法有：先進(jìn)先出、時(shí)間片輪轉(zhuǎn)、動(dòng)態(tài)優(yōu)先級(jí)等2023/2/5155大學(xué)課件總結(jié)作業(yè)調(diào)度的目標(biāo)：盡量做到公平合理，能執(zhí)行盡可能多的作業(yè)，盡快地響應(yīng)時(shí)間以及高的設(shè)備利用率等。調(diào)度算法有：FCFS系統(tǒng)開銷小，且對(duì)每個(gè)作業(yè)按其到達(dá)的順序依次調(diào)度，不利于短作業(yè)。SJF可得到最大的系統(tǒng)吞吐量，但會(huì)使長(zhǎng)作業(yè)可能長(zhǎng)期得不到調(diào)度。HRN介于FCFS和SJF之間。2023/2/5156大學(xué)課件進(jìn)程調(diào)度的主要任務(wù)是選擇一個(gè)合適的進(jìn)程占據(jù)處理機(jī)。調(diào)度算法：RR輪轉(zhuǎn)法，F(xiàn)CFS法,優(yōu)先級(jí)法和SRR線性優(yōu)先級(jí)法RR主要用于分時(shí)系統(tǒng)。有較好的響應(yīng)時(shí)間，對(duì)每個(gè)進(jìn)程有較好的公平性。FCFS不利于執(zhí)行時(shí)間短的進(jìn)程。SRR介于FCFS和RR之間。2023/2/5157大學(xué)課件適用于作業(yè)調(diào)度的算法先來(lái)先服務(wù)算法：計(jì)算時(shí)間短的作業(yè)優(yōu)先算法：

響應(yīng)比高者優(yōu)先算法優(yōu)先數(shù)調(diào)度算法均衡調(diào)度算法僅適用于作業(yè)調(diào)度的算法：響應(yīng)比高者優(yōu)先算法僅適用于進(jìn)程調(diào)度的算法：時(shí)間片輪轉(zhuǎn)2023/2/5158大學(xué)課件進(jìn)程調(diào)度的實(shí)現(xiàn)在設(shè)計(jì)進(jìn)程調(diào)度程序時(shí)，應(yīng)考慮這樣三個(gè)問題：（1）確定引起進(jìn)程調(diào)度的因素（2）調(diào)度算法的選擇和設(shè)計(jì)（3）就緒隊(duì)列的組織一、確定引起進(jìn)程調(diào)度的因素歸納起來(lái)，大致可有：（1）進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能繼續(xù)執(zhí)行2023/2/5159大學(xué)課件（2）因提出I/O請(qǐng)求而暫停（3）執(zhí)行了某種原語(yǔ)操作，如：p操作或block原語(yǔ)等。（4）在可剝奪式調(diào)度中，有一個(gè)比當(dāng)前進(jìn)程優(yōu)先級(jí)更高的進(jìn)程進(jìn)入就緒隊(duì)列（5）在時(shí)間片輪轉(zhuǎn)法，時(shí)間片用完。二、就緒隊(duì)列的組織2023/2/5160大學(xué)課件進(jìn)程調(diào)度的實(shí)現(xiàn)系統(tǒng)可以把就緒隊(duì)列組織成棧、或隊(duì)列的形式，采用哪種形式與調(diào)度算法有關(guān)。如：輪轉(zhuǎn)法中，就緒進(jìn)程常組織成FIFO隊(duì)列形式在最高優(yōu)先權(quán)優(yōu)先調(diào)度算法中，常采用優(yōu)先級(jí)隊(duì)列形式，進(jìn)程在進(jìn)入就緒隊(duì)列時(shí)，按其優(yōu)先級(jí)的高低，插入到相應(yīng)的位置上。2023/2/5161大學(xué)課件調(diào)度程序總把CPU分配給隊(duì)首進(jìn)程。最高優(yōu)先級(jí)優(yōu)先調(diào)度算法中，也可采用無(wú)序鏈表方式，即每當(dāng)進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，總是被放在末尾，而調(diào)度程序每次調(diào)度時(shí)，依次比較隊(duì)列中每個(gè)進(jìn)程的優(yōu)先級(jí)，從中找出最高的，把CPU分配給它。2023/2/5162大學(xué)課件三、分派程序分派程序首先將正在執(zhí)行進(jìn)程的CPU狀態(tài)保存到該進(jìn)程PCB的保留區(qū)中，再?gòu)谋徽{(diào)度程序選中的進(jìn)程PCB的處理機(jī)狀態(tài)字保留區(qū)中，取出CPU狀態(tài)信息來(lái)重新布置CPU現(xiàn)場(chǎng)。CPU狀態(tài)信息包括：程序狀態(tài)寄存器，若干個(gè)通用寄存器及程序計(jì)數(shù)器的內(nèi)容。

這樣，被調(diào)度到的進(jìn)程可繼續(xù)執(zhí)行。2023/2/5163大學(xué)課件進(jìn)程調(diào)度的實(shí)現(xiàn)分派程序在將處理機(jī)分配給進(jìn)程時(shí)的具體操作，可描述如下：我們假定就緒隊(duì)列中的諸進(jìn)程，已經(jīng)按其優(yōu)先級(jí)的大小排隊(duì)，并允許剝奪調(diào)度，當(dāng)就緒隊(duì)列的隊(duì)首出現(xiàn)優(yōu)先權(quán)比當(dāng)前正在執(zhí)行進(jìn)程j的優(yōu)先級(jí)最高的進(jìn)程時(shí)，應(yīng)立即停止j的執(zhí)行，并將它按其優(yōu)先級(jí)的大小，插入到就緒隊(duì)列的適當(dāng)位置上，然后用進(jìn)程i的PCB中保留的CPU現(xiàn)場(chǎng)信息去恢復(fù)CPU現(xiàn)場(chǎng)。2023/2/5164大學(xué)課件進(jìn)程調(diào)度的實(shí)現(xiàn)采用最高優(yōu)先級(jí)優(yōu)先的調(diào)度算法可描述如下：

proceduredispatcherbeginifRQ=0thenifEP=0thenidlerelsecontinue;remove(RQ,i);ifEQ=0thengotoL;j:=EP;2023/2/5165大學(xué)課件ifi.priority>j.prioritythenbeginstop(j);

save(j.CPUstatus);j.status:=ready;j.data:=RQ;

insertp(RQ,j);2023/2/5166大學(xué)課件L:I.status:=“executing”;EP:=i;

restore(I.CPUstatus);endelsecontinue;end.2023/2/5167大學(xué)課件4.3實(shí)時(shí)系統(tǒng)中的調(diào)度4.3.1對(duì)實(shí)時(shí)系統(tǒng)的要求4.3.2實(shí)時(shí)調(diào)度算法4.3.3實(shí)時(shí)調(diào)度實(shí)例一、具有開始截止時(shí)間的非周期實(shí)時(shí)任務(wù)的調(diào)度二、具有完成截止時(shí)間的周期性實(shí)時(shí)任務(wù)的調(diào)度2023/2/5168大學(xué)課件實(shí)時(shí)系統(tǒng)中，都存在著若干個(gè)實(shí)時(shí)進(jìn)程或任務(wù)，用來(lái)反應(yīng)或控制某個(gè)（些）外部事件，帶有某種程度的緊迫性。所以實(shí)時(shí)系統(tǒng)的調(diào)度有一定特殊性，前述調(diào)度算法，不能滿足實(shí)時(shí)系統(tǒng)的需要。4.3.1對(duì)實(shí)時(shí)系統(tǒng)的要求2023/2/5169大學(xué)課件1、提供必要的調(diào)度信息由于實(shí)時(shí)系統(tǒng)中，無(wú)論是硬實(shí)時(shí)任務(wù)，還是軟實(shí)時(shí)任務(wù)，都聯(lián)系著一個(gè)截止時(shí)間，要保證系統(tǒng)的正常運(yùn)行，實(shí)時(shí)調(diào)度必須能滿足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。實(shí)時(shí)調(diào)度算法大多根據(jù)任務(wù)的截止時(shí)間進(jìn)行調(diào)度的，系統(tǒng)向調(diào)度程序提供有關(guān)任務(wù)的一些信息：2023/2/5170大學(xué)課件（1）就緒時(shí)間。是該任務(wù)成為就緒任務(wù)狀態(tài)的起始時(shí)間，周期任務(wù)情況中，它是事先預(yù)知的一串時(shí)間序列，非周期任務(wù)情況中，也可預(yù)知。（2）開始截止時(shí)間和完成截止時(shí)間。典型的實(shí)時(shí)應(yīng)用只需知道開始截止時(shí)間，或完成截止時(shí)間。2023/2/5171大學(xué)課件（3）處理時(shí)間。是指一個(gè)任務(wù)從開始執(zhí)行到完成所需的時(shí)間，某些情況下，可由系統(tǒng)提供。（4）資源要求。任務(wù)執(zhí)行時(shí)所需的一組資源。2023/2/5172大學(xué)課件（5）優(yōu)先級(jí)。若任務(wù)對(duì)開始截止時(shí)間要求嚴(yán)格（硬任務(wù)）時(shí)，賦予“絕對(duì)”優(yōu)先級(jí)，若對(duì)時(shí)間不甚嚴(yán)格，可賦予“相對(duì)”優(yōu)先級(jí)。2023/2/5173大學(xué)課件2、調(diào)度方式一般對(duì)要求嚴(yán)格的實(shí)時(shí)系統(tǒng)，采用搶占調(diào)度方式，既具有較大的靈活性，又有極小的調(diào)度延遲，但這種方式比較復(fù)雜。2023/2/5174大學(xué)課件在小的實(shí)時(shí)系統(tǒng)中，能預(yù)知任務(wù)的開始截止時(shí)間，實(shí)時(shí)任務(wù)的調(diào)度采用非剝奪調(diào)度方式，簡(jiǎn)化調(diào)度程序和任務(wù)調(diào)度所花費(fèi)的開銷。3、具有快速響應(yīng)外部中斷的能力當(dāng)緊迫的外部事件請(qǐng)求中斷時(shí)，系統(tǒng)能及時(shí)響應(yīng)。要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，使禁止中斷的時(shí)間間隔盡量短。2023/2/5175大學(xué)課件4、快速任務(wù)分派完成任務(wù)調(diào)度后，立即進(jìn)行任務(wù)切換，系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)匦?，減少任務(wù)切換的時(shí)間開銷。2023/2/5176大學(xué)課件4.3.2實(shí)時(shí)調(diào)度算法1、時(shí)間片輪轉(zhuǎn)調(diào)度算法，常用于分時(shí)系統(tǒng)中。當(dāng)一個(gè)實(shí)時(shí)任務(wù)到達(dá)時(shí)，被掛在輪轉(zhuǎn)隊(duì)列的末尾，等待屬于自己的時(shí)間片。這種調(diào)度算法僅能獲得秒級(jí)的響應(yīng)時(shí)間，只適于一般實(shí)時(shí)信息處理系統(tǒng)，不能用于要求嚴(yán)格的實(shí)時(shí)控制系統(tǒng)。2023/2/5177大學(xué)課件2、非搶占優(yōu)先權(quán)調(diào)度算法，常用于多道批處理系統(tǒng)中。當(dāng)一個(gè)優(yōu)先級(jí)高的實(shí)時(shí)任務(wù)到達(dá)時(shí)，被安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行。這種算法可獲得數(shù)秒至數(shù)百毫秒級(jí)的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)。2023/2/5178大學(xué)課件3、基于時(shí)鐘中斷搶占的優(yōu)先權(quán)調(diào)度算法。若某實(shí)時(shí)任務(wù)到達(dá)時(shí)，若該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，在時(shí)鐘中斷到來(lái)時(shí)，調(diào)度程序剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給高優(yōu)先權(quán)任務(wù)，這種算法能獲得幾十毫秒至幾毫秒的調(diào)度延遲。這種算法用于大多數(shù)實(shí)時(shí)系統(tǒng)。2023/2/5179大學(xué)課件4、立即搶占的優(yōu)先權(quán)調(diào)度要求系統(tǒng)具有快速響應(yīng)外部事件中斷的能力，一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。其延遲時(shí)間可到幾毫秒至100微秒，甚至更低。如圖示：P111。2023/2/5180大學(xué)課件4.3.3實(shí)時(shí)調(diào)度實(shí)例******一、具有開始截止時(shí)間的非周期實(shí)時(shí)任務(wù)的調(diào)度事先知道各實(shí)時(shí)任務(wù)的開始截止時(shí)間，且對(duì)調(diào)度延遲要求不嚴(yán)格的情況下，可采用最早截止時(shí)間優(yōu)先的非剝奪調(diào)度策略。例：四個(gè)具有開始截止時(shí)間的非周期任務(wù)的調(diào)度情況。2023/2/5181大學(xué)課件系統(tǒng)首先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、3先后到達(dá)。由于任務(wù)3的開始截止時(shí)間早于任務(wù)2，所以系統(tǒng)在1后將調(diào)度3執(zhí)行，在此期間又來(lái)了4，其開始截止時(shí)間也早于2，所以執(zhí)行完3后，系統(tǒng)又調(diào)度執(zhí)行4，最后才調(diào)度執(zhí)行2。2023/2/5182大學(xué)課件二、具有完成截止時(shí)間的周期性實(shí)時(shí)任務(wù)的調(diào)度基有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，A每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms，B每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。

所以，A和B每次的開始截止時(shí)間為：A1,A2,A3,…和B1,B2,B3,…。

為保證不遺漏一次截止時(shí)間，采用最早截止時(shí)間優(yōu)先的剝奪調(diào)度策略。如圖示：243113421234t開始截止時(shí)間執(zhí)行任務(wù)任務(wù)到達(dá)2023/2/5183大學(xué)課件2023/2/5184大學(xué)課件又例：在時(shí)間為0ms時(shí)，A1離截止時(shí)間只有10ms，B1離截止時(shí)間有25ms,所以，調(diào)度程序?qū)⒄{(diào)度A1執(zhí)行。在10ms時(shí)，A2離截止時(shí)間有20ms，B1離截止時(shí)間還有15ms，此時(shí)調(diào)度B1執(zhí)行。在30ms時(shí)，A2到了開始截止時(shí)間，B1離開始截止時(shí)間還有15ms，此時(shí)要?jiǎng)儕ZB1的運(yùn)行，而調(diào)度A2。

2023/2/5185大學(xué)課件在40ms時(shí)，A3離開始截止時(shí)間有10ms，B1還有5ms，又重新調(diào)度B1執(zhí)行。在45ms時(shí)，B1完成，而A3離開始截止時(shí)間有5ms，而B是30ms，先調(diào)度A3執(zhí)行。在55ms時(shí)，A尚未進(jìn)入第4周期，而B進(jìn)入了第2周期，所以調(diào)度B2執(zhí)行。2023/2/5186大學(xué)課件10A1(10)B1(25)A1210A2(20)B1(15)B1330A2(0)B1(15)A2440A3(10)B1(5)B1545A3(5)B2(30)A3655A4(15)B2(20)B2770A4(0)B2(20)A4...............時(shí)間(ms)A截止時(shí)間B截止時(shí)間調(diào)度對(duì)象2023/2/5187大學(xué)課件4.4多處理機(jī)調(diào)度4.4.1進(jìn)程調(diào)度一、同構(gòu)型多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度二、異構(gòu)型多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度4.4.2自調(diào)度4.4.3成組調(diào)度4.4.4專用處理機(jī)分配前面所述的是單處理機(jī)環(huán)境下的進(jìn)程調(diào)度，當(dāng)有多臺(tái)處理機(jī)時(shí)，要保持多臺(tái)處理機(jī)盡量處于忙狀態(tài)，涉及到多處理機(jī)的調(diào)度，由于，系統(tǒng)中引入線程后，調(diào)度的基本單位已是線程，目前大多數(shù)OS都采用線程機(jī)制，所以本節(jié)主要介紹對(duì)線程的調(diào)度問題2023/2/5188大學(xué)課件4.4.1進(jìn)程調(diào)度多處理機(jī)系統(tǒng)中，進(jìn)程調(diào)度與系統(tǒng)結(jié)構(gòu)有關(guān)。同構(gòu)型中，對(duì)某一進(jìn)程，可將其分配到任一處理機(jī)上運(yùn)行。異構(gòu)型中，對(duì)某一進(jìn)程只能將其分配到適合于他運(yùn)行的處理機(jī)上執(zhí)行。多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度，還與OS的工作模式有關(guān)。2023/2/5189大學(xué)課件一、同構(gòu)型多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度1、靜態(tài)分配(staticassignment)

指一個(gè)進(jìn)程從開始執(zhí)行直至完成，被固定地分配到一臺(tái)處理機(jī)上去執(zhí)行。此時(shí)，要為每一臺(tái)處理機(jī)設(shè)置一專用的就緒進(jìn)程隊(duì)列，該隊(duì)列中的諸進(jìn)程被先后分配到該臺(tái)處理機(jī)上執(zhí)行。2023/2/5190大學(xué)課件進(jìn)程被阻塞后，再次就緒時(shí)，仍被掛在原來(lái)這個(gè)就緒隊(duì)列中，下次仍然在此處理機(jī)上執(zhí)行。該方式與單處理機(jī)環(huán)境的進(jìn)程調(diào)度一樣，優(yōu)點(diǎn)：調(diào)度開銷小，缺點(diǎn)：各處理機(jī)的忙、閑不均。2023/2/5191大學(xué)課件2、動(dòng)態(tài)分配(dynamicassignment)

系統(tǒng)中設(shè)置一個(gè)公共的就緒隊(duì)列，所有的就緒進(jìn)程都被放在該隊(duì)列中。分配處理機(jī)時(shí)，對(duì)某一進(jìn)程，可分配到任意一臺(tái)處理機(jī)。對(duì)一個(gè)進(jìn)程的整個(gè)運(yùn)行過(guò)程，在每次被調(diào)度執(zhí)行時(shí)，是隨機(jī)被分配到一臺(tái)空閑的處理機(jī)上去執(zhí)行。2023/2/5192大學(xué)課件其優(yōu)點(diǎn)：消除了處理機(jī)忙閑不均的現(xiàn)象，但調(diào)度的開銷大。3、自調(diào)度(self-scheduling)

系統(tǒng)只設(shè)置一個(gè)公共就緒隊(duì)列，所有的就緒進(jìn)程都被掛在該隊(duì)列上。2023/2/5193大學(xué)課件自調(diào)度是指由每個(gè)處理機(jī)自己去查看公共就緒隊(duì)列，從中選擇一個(gè)進(jìn)程令其執(zhí)行。要求系統(tǒng)中設(shè)置同步機(jī)制，用于保證諸處理機(jī)互斥地訪問就緒隊(duì)列，避免多個(gè)處理機(jī)同時(shí)選擇一個(gè)進(jìn)程，也不會(huì)出現(xiàn)某個(gè)進(jìn)程從就緒隊(duì)列中丟失。2023/2/5194大學(xué)課件二、異構(gòu)型多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度異構(gòu)型多處理系統(tǒng)，大多采用主-從式OS，即OS的核心部分駐留在主機(jī)上，從機(jī)只執(zhí)行用戶程序，進(jìn)程調(diào)度由主機(jī)執(zhí)行。當(dāng)從機(jī)空閑時(shí)，向主機(jī)發(fā)送一要求進(jìn)程的信號(hào)，然后，等待主機(jī)為之分配進(jìn)程。