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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Next）HRN(Hansen)

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

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

(SRR)selfishroundrobin新創(chuàng)建的進程按FCFS排成就緒隊列A，而其他已得到過時間片服務的進程也按FCFS排成另一個就緒隊列或稱享受服務隊列B。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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