調(diào)度算法-四川大學(xué)

1、操作系統(tǒng)原理Operating System Principles,四川大學(xué)計(jì)算機(jī)學(xué)院段 磊leiduan@scu.edu.cn2014 Spring,第3章 處理器調(diào)度,處理器調(diào)度指在多道程序環(huán)境下將處理器分配給各進(jìn)程。 在處理器調(diào)度中，合理的調(diào)度算法能夠提高處理器的處理能力和系統(tǒng)性能，滿足用戶需求。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,3/98,本章目錄,3.1 處理器調(diào)度的層次3.2 評(píng)價(jià)調(diào)度

2、算法的準(zhǔn)則3.3 調(diào)度算法 3.4 線程調(diào)度3.5 實(shí)時(shí)調(diào)度3.6 多處理器調(diào)度3.7 Windows 2000/XP系統(tǒng)的處理器調(diào)度,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,4/98,3.1 處理器調(diào)度的層次,內(nèi)容高級(jí)調(diào)度-作業(yè)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度-進(jìn)程調(diào)度要點(diǎn)調(diào)度的本質(zhì)進(jìn)程調(diào)度的概念,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,5/98,3.1 處理器調(diào)度的層次,內(nèi)容高級(jí)調(diào)度-作業(yè)

3、調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度-進(jìn)程調(diào)度要點(diǎn)調(diào)度的本質(zhì)進(jìn)程調(diào)度的概念,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,6/98,調(diào)度的概念與本質(zhì),調(diào)度：系統(tǒng)將計(jì)算機(jī)資源分配給進(jìn)程。單道程序環(huán)境與多道程序環(huán)境處理器調(diào)度：多道程序環(huán)境下將處理器分配給各進(jìn)程,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,7/98,,調(diào)度要解決的問題：WHAT：按什么原則分配CPU調(diào)度算法WHEN：何時(shí)分配CPU調(diào)度的時(shí)機(jī)HOW： 如何分

4、配CPU調(diào)度過程,調(diào)度的概念與本質(zhì),2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,8/98,處理器調(diào)度的層次,處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源處理機(jī)調(diào)度算法對整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響處理機(jī)調(diào)度的三個(gè)層次：高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度,高級(jí)調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天,中級(jí)調(diào)度涉及進(jìn)程在內(nèi)外存間的交換從存儲(chǔ)器資源管理的角度來看，把進(jìn)程的部分或全部換出到外存上，可為當(dāng)前運(yùn)行進(jìn)程

5、的執(zhí)行提供所需內(nèi)存空間，將當(dāng)前進(jìn)程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問,低級(jí)調(diào)度也稱微觀調(diào)度從處理機(jī)資源分配的角度來看，處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運(yùn)行狀態(tài)，低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,9/98,高級(jí)調(diào)度-作業(yè)的概念與分類,概念：作業(yè)由一組統(tǒng)一管理和操作的進(jìn)程集合構(gòu)成，是用戶要求計(jì)算機(jī)系統(tǒng)完成

6、的一項(xiàng)相對獨(dú)立的工作。作業(yè)可以是完成了編譯、鏈接之后的一個(gè)用戶程序，也可以是用各種命令構(gòu)成的一個(gè)腳本。分類：根據(jù)需要處理工作的類型，分為計(jì)算型作業(yè)和I/O型作業(yè)。按照作業(yè)提交方式，分為批處理作業(yè)和終端型作業(yè)。一個(gè)系統(tǒng)能夠同時(shí)接納作業(yè)的個(gè)數(shù)稱為系統(tǒng)的多道程序度。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,10/98,作業(yè)的狀態(tài)：提交狀態(tài)后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài),高級(jí)調(diào)度-作業(yè)的概念與分類,作業(yè)被調(diào)度到內(nèi)存，為作業(yè)分

7、配資源并為其創(chuàng)建與之對應(yīng)的進(jìn)程，進(jìn)程獲得CPU，開始運(yùn)行。,從作業(yè)的第一個(gè)進(jìn)程完成開始，直到作業(yè)所有的進(jìn)程完成，釋放作業(yè)所占用的資源，退出系統(tǒng)的整個(gè)進(jìn)程。,系統(tǒng)接收輸入的用戶作業(yè)，并將其放入計(jì)算機(jī)磁盤。作業(yè)在磁盤上以后備隊(duì)列形式進(jìn)行組織，等待作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)度到內(nèi)存。,用戶將作業(yè)提交給操作系統(tǒng)，等待輸入程序和數(shù)據(jù)到磁盤。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,11/98,高級(jí)調(diào)度-概念與模型,作業(yè)調(diào)度概念：按照操作系統(tǒng)預(yù)

8、先規(guī)定的策略，從磁盤的作業(yè)后備隊(duì)列中選擇作業(yè)調(diào)入內(nèi)存，為作業(yè)分配所需要的資源并建立與作業(yè)相對應(yīng)的進(jìn)程。當(dāng)作業(yè)運(yùn)行的準(zhǔn)備工作完成后，作業(yè)調(diào)度啟動(dòng)作業(yè)運(yùn)行。在作業(yè)運(yùn)行結(jié)束后，作業(yè)調(diào)度歸還并釋放作業(yè)占用的資源，結(jié)束作業(yè)。模型：,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,12/98,高級(jí)調(diào)度-策略與因素,接納多少個(gè)作業(yè)作業(yè)數(shù)目太多時(shí)，可能會(huì)影響到系統(tǒng)的服務(wù)質(zhì)量;作業(yè)的數(shù)量太少時(shí)，又會(huì)導(dǎo)致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低接納哪

9、些作業(yè)先來先服務(wù)調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法基于作業(yè)優(yōu)先級(jí)的調(diào)度算法響應(yīng)比高者優(yōu)先的調(diào)度算法,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,13/98,高級(jí)調(diào)度-OS任務(wù),作業(yè)調(diào)度中操作系統(tǒng)需要完成如下主要工作：確定作業(yè)的數(shù)據(jù)結(jié)構(gòu)確定作業(yè)的調(diào)度算法為作業(yè)分配資源回收作業(yè)資源,操作系統(tǒng)為每個(gè)進(jìn)入系統(tǒng)的作業(yè)分配一個(gè)與進(jìn)程控制塊（PCB）類似的作業(yè)控制塊（JCB） JCB是作業(yè)的標(biāo)志，OS根據(jù)JCB中的信息對作業(yè)進(jìn)行調(diào)

10、度和管理。,作業(yè)運(yùn)行需要各種資源，包括硬件資源和軟件資源。硬件資源有內(nèi)存、處理器和各種輸入輸出設(shè)備。軟件資源有各種共享變量等。 作業(yè)的資源分配策略主要考慮的是作業(yè)所包含的進(jìn)程所需要的資源，在一般情況下，資源按照進(jìn)程需求進(jìn)行分配。資源分配中需要避免由進(jìn)程之間的資源競爭而造成的死鎖等現(xiàn)象。,作業(yè)完成后，作業(yè)調(diào)度程序除了要輸出相關(guān)的作業(yè)信息之外，還要回收作業(yè)所占用的全部資源，撤銷與作業(yè)相關(guān)的進(jìn)程和作業(yè)控制塊。 在作業(yè)調(diào)度工作中

11、，大多數(shù)工作由作業(yè)的調(diào)度程序完成。 內(nèi)存和輸入輸出設(shè)備的分配和釋放不是由作業(yè)調(diào)度程序完成，而是由存儲(chǔ)器管理和設(shè)備管理程序完成的。 作業(yè)調(diào)度程序只是將作業(yè)對內(nèi)存的要求和對設(shè)備的要求轉(zhuǎn)交給相應(yīng)的內(nèi)存管理程序和設(shè)備管理程序，由內(nèi)存管理程序和設(shè)備管理程序完成內(nèi)存和設(shè)備的分配與回收。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,14/98,高級(jí)調(diào)度-作業(yè)狀態(tài)轉(zhuǎn)換,作業(yè)調(diào)度將作業(yè)從后備狀態(tài)轉(zhuǎn)換到內(nèi)存執(zhí)行狀態(tài)作業(yè)執(zhí)行狀態(tài)包含作業(yè)

12、所對應(yīng)進(jìn)程的就緒、運(yùn)行和阻塞狀態(tài),,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,15/98,3.1 處理器調(diào)度的層次,內(nèi)容高級(jí)調(diào)度-作業(yè)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度-進(jìn)程調(diào)度要點(diǎn)調(diào)度的本質(zhì)進(jìn)程調(diào)度的概念,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,16/98,中級(jí)調(diào)度-概念與功能,又稱為中程調(diào)度，是為了提高內(nèi)存利用率和平衡系統(tǒng)負(fù)載而采取的一種利用外存補(bǔ)充內(nèi)存的措施。多進(jìn)程環(huán)境下，內(nèi)存中存在多個(gè)進(jìn)程，其中有些進(jìn)程可能需要掛

13、起，這些進(jìn)程暫時(shí)不參與對處理器的競爭。為了充分利用內(nèi)存資源，系統(tǒng)會(huì)采用進(jìn)程對換的方法將進(jìn)程換出到外存，將這些進(jìn)程占用的內(nèi)存空間釋放，讓內(nèi)存能夠接納新的進(jìn)程或使得內(nèi)存中的進(jìn)程能夠更快推進(jìn)。當(dāng)被換出到外存中的進(jìn)程掛起時(shí)間到時(shí)，又需要將這些進(jìn)程換入到內(nèi)存。中級(jí)調(diào)度是在換出內(nèi)存的進(jìn)程中確定需要進(jìn)入內(nèi)存的進(jìn)程的一種調(diào)度操作。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,17/98,3.1 處理器調(diào)度的層次,內(nèi)容高級(jí)調(diào)度-作業(yè)調(diào)度中級(jí)

14、調(diào)度低級(jí)調(diào)度-進(jìn)程調(diào)度要點(diǎn)調(diào)度的本質(zhì)進(jìn)程調(diào)度的概念,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,18/98,低級(jí)調(diào)度-概念與功能,又稱為進(jìn)程調(diào)度、短程調(diào)度按照一定的調(diào)度算法從內(nèi)存的就緒進(jìn)程隊(duì)列中選擇進(jìn)程，為進(jìn)程分配處理器，避免進(jìn)程對處理器競爭的方法。與作業(yè)調(diào)度和中級(jí)調(diào)度比較，進(jìn)程調(diào)度發(fā)生的頻率最高，作業(yè)調(diào)度發(fā)生的頻率最低，中級(jí)調(diào)度主要用于內(nèi)存管理，特別是虛擬存儲(chǔ)器管理。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,1

15、9/98,3.1.2 進(jìn)程調(diào)度模型,只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型,,低級(jí)調(diào)度-模型,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,20/98,3.1.2 進(jìn)程調(diào)度模型,具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型,,低級(jí)調(diào)度-模型,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,21/98,具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型,3.1.2 進(jìn)程調(diào)度模型,低級(jí)調(diào)度-模型,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,22/98,低級(jí)調(diào)度-原因與機(jī)制,

16、引起進(jìn)程調(diào)度的主要原因如下：處理器執(zhí)行的進(jìn)程完成任務(wù)，處理器空閑處理器執(zhí)行的進(jìn)程轉(zhuǎn)入阻塞狀態(tài)，此時(shí)處理器空閑處理器執(zhí)行的進(jìn)程被其它進(jìn)程搶占處理器執(zhí)行的進(jìn)程被掛起機(jī)制：排隊(duì)器分派器上下文切換機(jī)制,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,23/98,低級(jí)調(diào)度-調(diào)度方式,非搶占方式：簡單，實(shí)時(shí)性差搶占方式時(shí)間片原則優(yōu)先權(quán)原則短作業(yè)優(yōu)先原則,如果執(zhí)行進(jìn)程正好在執(zhí)行一個(gè)沒有資源的無限循環(huán)，則執(zhí)行進(jìn)程不會(huì)放棄處理器

17、，所有的就緒進(jìn)程會(huì)永久等待，系統(tǒng)進(jìn)入了一種僵持的狀態(tài)。,指一個(gè)進(jìn)程正在處理器中運(yùn)行時(shí)，操作系統(tǒng)可以根據(jù)規(guī)定的搶占原則，將已經(jīng)分配給進(jìn)程的處理器從進(jìn)程剝奪，并分配給其他的進(jìn)程。,在系統(tǒng)允許搶占調(diào)度，并滿足搶占條件的情況下，系統(tǒng)才可以采用搶占調(diào)度方式。,滿足搶占條件的進(jìn)程能夠搶占當(dāng)前正在執(zhí)行進(jìn)程的處理器。被搶占的進(jìn)程狀態(tài)從執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)，其進(jìn)程控制塊進(jìn)入到進(jìn)程就緒隊(duì)列。,思考：“搶占”可能帶來的問題及原因？,2024/3/1,《計(jì)算機(jī)

18、操作系統(tǒng)》- 第3章,24/98,本章目錄,3.1 處理器調(diào)度的層次3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則3.3 調(diào)度算法 3.4 線程調(diào)度3.5 實(shí)時(shí)調(diào)度3.6 多處理器調(diào)度3.7 Windows 2000/XP系統(tǒng)的處理器調(diào)度,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,25/98,3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則,內(nèi)容準(zhǔn)則評(píng)價(jià)指標(biāo)要點(diǎn)指標(biāo)含義計(jì)算方式,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,26/

19、98,調(diào)度算法的評(píng)價(jià)準(zhǔn)則,基本原則：具有公平性資源利用率高（特別是CPU利用率）在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好）在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量,面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；處理機(jī)利用率好；各類資源的平衡利用,面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短；響應(yīng)時(shí)間快；截止時(shí)間的保證；優(yōu)先權(quán)準(zhǔn)則,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,27/98,處理器利用率CPU utilization響應(yīng)時(shí)間resp

20、onse time周轉(zhuǎn)時(shí)間turnaround time系統(tǒng)吞吐量throughput,處理器利用率為CPU有效工作時(shí)間與CPU總的運(yùn)行時(shí)間之比，即：CPU利用率 = CPU有效工作時(shí)間/CPU總的運(yùn)行時(shí)間CPU總的運(yùn)行時(shí)間 = CPU的有效工作時(shí)間 + CPU的空閑時(shí)間,響應(yīng)時(shí)間是交互環(huán)境下用戶從鍵盤提交第1個(gè)請求開始，到系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者是屏幕上顯

21、示出結(jié)果為止的時(shí)間。響應(yīng)時(shí)間 = 從終端鍵盤輸入的請求信息傳送到處理機(jī)的時(shí)間 + 處理機(jī)對請求信息的處理時(shí)間 + 生成的響應(yīng)信息回送到終端顯示器的時(shí)間,周轉(zhuǎn)時(shí)間指用戶作業(yè)提交給操作系統(tǒng)開始到作業(yè)完成為止的時(shí)間。周轉(zhuǎn)時(shí)間通常是評(píng)價(jià)批處理系統(tǒng)性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一。周轉(zhuǎn)時(shí)間Ti = 作業(yè)在后備隊(duì)列中的等待調(diào)度時(shí)間+進(jìn)程在就緒隊(duì)列上等待調(diào)度

22、的時(shí)間+進(jìn)程在CPU上的運(yùn)行時(shí)間 + 進(jìn)程等待I/O或其他事件發(fā)生的時(shí)間作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間Tf  = 作業(yè)的周轉(zhuǎn)時(shí)間Ti/系統(tǒng)為作業(yè)提供的服務(wù)時(shí)間Tsi,單位時(shí)間內(nèi)處理的進(jìn)程數(shù)目為CPU的工作成效，單位時(shí)間內(nèi)完成的進(jìn)程數(shù)目為系統(tǒng)的吞吐量。,在選擇處理器的調(diào)度算法時(shí)，用戶希望CPU利用率和系統(tǒng)吞吐量越大越好，響應(yīng)時(shí)間和周轉(zhuǎn)時(shí)間越小越好。 但是，通常情況下，系統(tǒng)希望的是能夠合理利用

23、處理器和各類資源，使作業(yè)的平均周轉(zhuǎn)時(shí)間或帶權(quán)周轉(zhuǎn)時(shí)間小的調(diào)度算法。 對于實(shí)時(shí)系統(tǒng)，作業(yè)調(diào)度的關(guān)鍵在于能否滿足作業(yè)的實(shí)時(shí)要求，對周轉(zhuǎn)時(shí)間等指標(biāo)并不特別著重。,調(diào)度算法的評(píng)價(jià)指標(biāo),2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,28/98,本章目錄,3.1 處理器調(diào)度的層次3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則3.3 調(diào)度算法 3.4 線程調(diào)度3.5 實(shí)時(shí)調(diào)度3.6 多處理器調(diào)度3.7 Windows 2000/XP系

24、統(tǒng)的處理器調(diào)度,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,29/98,3.3 調(diào)度算法,內(nèi)容作業(yè)調(diào)度算法進(jìn)程調(diào)度算法要點(diǎn)算法思想指標(biāo)計(jì)算,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,30/98,3.3 調(diào)度算法,內(nèi)容作業(yè)調(diào)度算法進(jìn)程調(diào)度算法要點(diǎn)算法思想指標(biāo)計(jì)算,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,31/98,作業(yè)調(diào)度算法,概念回顧作業(yè)調(diào)度是在資源滿足的條件下，將處于后備狀態(tài)的作業(yè)調(diào)入內(nèi)存

25、，同時(shí)生成與作業(yè)相對應(yīng)的進(jìn)程，并為這些進(jìn)程提供所需要的資源。作業(yè)調(diào)度程序只保證被調(diào)度的作業(yè)有獲得處理器的資格，而處理器的分配則需要進(jìn)程調(diào)度才能完成。主要算法FCFS：先來先服務(wù)（First-Come First-Served)SJF：短作業(yè)優(yōu)先（Shortest-Job-First）HRRF：響應(yīng)比高者優(yōu)先HPF：優(yōu)先權(quán)高者優(yōu)先（ Highest-Priority-First)分類調(diào)度,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》

26、- 第3章,32/98,FCFS：先來先服務(wù),基本思想遵循先進(jìn)入后備隊(duì)列的作業(yè)，先進(jìn)行調(diào)度的原則。非搶占式算法簡單，易于編碼實(shí)現(xiàn)優(yōu)先考慮作業(yè)的等待時(shí)間，沒有考慮作業(yè)的執(zhí)行時(shí)間長短、作業(yè)的運(yùn)行特性和作業(yè)對資源的要求算法評(píng)價(jià)有利于長作業(yè)，不利于短作業(yè)有利于CPU繁忙的作業(yè)，不利于I/O繁忙的作業(yè)舉例？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,33/98,FCFS：先來先服務(wù)-例1,作業(yè)J1、J2、J3、J4依次到達(dá)作

27、業(yè)后備隊(duì)列，需要處理時(shí)間分別如下：J1為15ms，J2為5ms，J3為10ms，J4為3ms。請給出作業(yè)執(zhí)行的圖示（橫軸為時(shí)間，縱軸為作業(yè)）請計(jì)算每個(gè)作業(yè)的等待時(shí)間和周轉(zhuǎn)時(shí)間請計(jì)算上述作業(yè)的平均等待時(shí)間和平均周轉(zhuǎn)時(shí)間,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,34/98,FCFS：先來先服務(wù)-例2,如果4個(gè)作業(yè)A、B、C、D到達(dá)系統(tǒng)磁盤后備隊(duì)列的順序和需要執(zhí)行的時(shí)間如下表所示。,請給出作業(yè)執(zhí)行的圖示（橫軸為時(shí)間，縱軸為作業(yè)

28、）請計(jì)算每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間請計(jì)算上述作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,35/98,SJF：短作業(yè)優(yōu)先,基本思想根據(jù)作業(yè)控制塊中作業(yè)申請時(shí)指出的執(zhí)行時(shí)間，選取執(zhí)行時(shí)間最短的作業(yè)優(yōu)先調(diào)度。搶占調(diào)度方式：只要就緒隊(duì)列中出現(xiàn)了需要執(zhí)行時(shí)間比當(dāng)前正在運(yùn)行作業(yè)的剩余處理時(shí)間更短的作業(yè)，則該作業(yè)會(huì)搶占當(dāng)前正在運(yùn)行的作業(yè)。算法評(píng)價(jià)克服FCFS調(diào)度算法對短作業(yè)不利的缺點(diǎn)，效率高

29、，易于編程實(shí)現(xiàn)不利于長作業(yè)預(yù)先估計(jì)作業(yè)的執(zhí)行時(shí)間舉例？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,36/98,SJF：短作業(yè)優(yōu)先-例3,作業(yè)A、B、C、D需要處理的時(shí)間分別為20ms、15ms、10ms、5ms。如果這4個(gè)作業(yè)同時(shí)到達(dá)作業(yè)后備隊(duì)列請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示請計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間,如果這4個(gè)作業(yè)不是同時(shí)到達(dá)，A作業(yè)在0時(shí)間到達(dá)，B作業(yè)在A作業(yè)之后5ms達(dá)到，C作業(yè)在A作業(yè)之后

30、10ms達(dá)到，D作業(yè)在A作業(yè)之后15ms達(dá)到請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示請計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間,如果A作業(yè)到達(dá)的時(shí)間為0，B、C、D作業(yè)達(dá)到系統(tǒng)的時(shí)間分別改為1ms、2ms、3ms請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示請計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,37/98,HRRF：響應(yīng)比高者優(yōu)先,初衷FCFS調(diào)度算法只片面地考慮了作業(yè)的進(jìn)入時(shí)間，短作業(yè)

31、優(yōu)先調(diào)度算法考慮了作業(yè)的運(yùn)行時(shí)間而忽略了作業(yè)的等待時(shí)間。響應(yīng)比高者優(yōu)先調(diào)度算法為這兩種算法的折中。響應(yīng)比計(jì)算作業(yè)的響應(yīng)時(shí)間與作業(yè)需要處理的時(shí)間之比。作業(yè)的響應(yīng)時(shí)間為作業(yè)進(jìn)入系統(tǒng)后的等待時(shí)間與作業(yè)要求處理器處理的時(shí)間之和。搶占調(diào)度方式,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,38/98,HRRF：響應(yīng)比高者優(yōu)先,分析與評(píng)價(jià)響應(yīng)比高，可能是因?yàn)樽鳂I(yè)等待時(shí)間長，也可能是因?yàn)樽鳂I(yè)需要處理時(shí)間短。響應(yīng)比高優(yōu)先調(diào)度算法不僅體現(xiàn)

32、了等待時(shí)間長的作業(yè)會(huì)優(yōu)先調(diào)度，而且還體現(xiàn)了處理時(shí)間短的作業(yè)也會(huì)優(yōu)先調(diào)度。該算法能夠客觀地對待長作業(yè)和短作業(yè)。舉例？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,39/98,HRRF：響應(yīng)比高者優(yōu)先-例4,如果4個(gè)作業(yè)A、B、C、D到達(dá)系統(tǒng)磁盤后備隊(duì)列的順序和需要執(zhí)行的時(shí)間如下表所示。,計(jì)算各時(shí)間點(diǎn)的響應(yīng)比及調(diào)度情況。請給出作業(yè)執(zhí)行的圖示（橫軸為時(shí)間，縱軸為作業(yè)）請計(jì)算上述作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間,2024/3/1

33、,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,40/98,FCFS、SJF、HRRF：比較,思考：對上述比較結(jié)果進(jìn)行分析和評(píng)價(jià)。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,41/98,HPF：優(yōu)先權(quán)高者優(yōu)先,基本思想根據(jù)作業(yè)的優(yōu)先權(quán)進(jìn)行作業(yè)調(diào)度，每次總是選取優(yōu)先權(quán)高的作業(yè)調(diào)度。作業(yè)的優(yōu)先數(shù)可由系統(tǒng)或用戶給定。評(píng)價(jià)綜合考慮了作業(yè)的執(zhí)行時(shí)間和等待時(shí)間的長短、作業(yè)的緩急程度、作業(yè)對外部設(shè)備的使用情況等因素根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)和運(yùn)行環(huán)境而給定各作

34、業(yè)的優(yōu)先權(quán)，決定作業(yè)調(diào)度的先后順序。舉例？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,42/98,HPF：優(yōu)先權(quán)高者優(yōu)先-例5,作業(yè)A、B、C、D一起達(dá)到，需要處理的時(shí)間分別為25ms、5ms、10ms、3ms，優(yōu)先數(shù)分別為154、139、149、130，優(yōu)先數(shù)越大、優(yōu)先級(jí)越低。請給出采用優(yōu)先權(quán)高者優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示請計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間靜態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán),思考：動(dòng)態(tài)優(yōu)先權(quán)的“動(dòng)態(tài)性”體現(xiàn)？,20

35、24/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,43/98,綜合：分類調(diào)度算法,目的：均衡使用系統(tǒng)資源兼顧不同大小的作業(yè)基本思想按照使用系統(tǒng)資源或作業(yè)的大小的不同首先分別對作業(yè)進(jìn)行分類然后再根據(jù)作業(yè)的類型進(jìn)行調(diào)度還可以進(jìn)一步將同一類別的作業(yè)再按照優(yōu)先級(jí)進(jìn)行排隊(duì),2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,44/98,3.3 調(diào)度算法,內(nèi)容作業(yè)調(diào)度算法進(jìn)程調(diào)度算法要點(diǎn)算法思想指標(biāo)計(jì)算,2024/3/1,《計(jì)算機(jī)操

36、作系統(tǒng)》- 第3章,45/98,進(jìn)度調(diào)度算法,概念回顧進(jìn)程調(diào)度算法是低級(jí)調(diào)度算法。在傳統(tǒng)操作系統(tǒng)中，進(jìn)程為資源分配和調(diào)度的基本單位，是操作系統(tǒng)中發(fā)生頻率最高的調(diào)度。主要算法FCFS：先來先服務(wù)（略）TRR：時(shí)間片輪轉(zhuǎn)調(diào)度算法優(yōu)先級(jí)調(diào)度算法MQ：多級(jí)隊(duì)列調(diào)度算法MFQ：多級(jí)反饋隊(duì)列調(diào)度算法,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,46/98,TRR：時(shí)間片輪轉(zhuǎn)調(diào)度算法,基本思想分時(shí)思想首先將處理器的處理時(shí)間劃分

37、為大小相等的時(shí)間片。調(diào)度程序每次從就緒隊(duì)列中選擇隊(duì)首的進(jìn)程，為之分配處理器的一個(gè)時(shí)間片并讓進(jìn)程運(yùn)行。當(dāng)進(jìn)程運(yùn)行的時(shí)間片到時(shí)，強(qiáng)迫進(jìn)程放棄處理器，到就緒隊(duì)列中再次排隊(duì)，并將處理器的下一個(gè)時(shí)間片分配給就緒隊(duì)列中隊(duì)首的進(jìn)程。所有就緒隊(duì)列中的進(jìn)程按照這樣的形式輪轉(zhuǎn)使用處理器時(shí)間片。舉例?,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,47/98,TRR：時(shí)間片輪轉(zhuǎn)調(diào)度算法-例6,進(jìn)程A、B、C、D需要處理的時(shí)間分別為20ms、10ms

38、、15ms、5ms，在0時(shí)間達(dá)到。達(dá)到的先后順序?yàn)锳→B→C→D。請給出不同時(shí)間片下的調(diào)度圖示；請計(jì)算不同時(shí)間片下的平均周轉(zhuǎn)時(shí)間。A：時(shí)間片為1A：時(shí)間片為5A：時(shí)間片為10,思考：時(shí)間片大小與平均周轉(zhuǎn)時(shí)間的關(guān)系？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,48/98,TRR：時(shí)間片輪轉(zhuǎn)調(diào)度算法,分析與評(píng)價(jià)搶占式調(diào)度算法進(jìn)程切換以時(shí)間片為單位，系統(tǒng)的花銷主要體現(xiàn)在進(jìn)程切換上。當(dāng)時(shí)間片很小時(shí)，切換的頻率高，時(shí)間片花銷

39、大。當(dāng)時(shí)間片過大時(shí)，進(jìn)程切換開銷減小，但是進(jìn)程輪轉(zhuǎn)一次需要的等待時(shí)間增加，周轉(zhuǎn)時(shí)間增加。當(dāng)時(shí)間片大到每個(gè)進(jìn)程足以完成時(shí)，時(shí)間片調(diào)度算法便退化為FCFS算法。時(shí)間片大小的取值需要考慮系統(tǒng)中進(jìn)程個(gè)數(shù)、進(jìn)程切換開銷、響應(yīng)時(shí)間、系統(tǒng)效率等多種因素。,思考：固定大小時(shí)間片與可變大小時(shí)間片？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,49/98,優(yōu)先級(jí)調(diào)度算法-例7,同時(shí)達(dá)到的進(jìn)程P1、P2、P3、P4，它們的優(yōu)先數(shù)分別為80、70、7

40、5、65，數(shù)字越大表示進(jìn)程優(yōu)先級(jí)越高，需要處理的時(shí)間分別是20ms、15ms、25ms、30ms。請給出采用優(yōu)先級(jí)算法的調(diào)度圖示；請計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,50/98,MQ：多級(jí)隊(duì)列調(diào)度算法,基本思想根據(jù)進(jìn)程的類型不同，將進(jìn)程就緒隊(duì)列分為若干個(gè)獨(dú)立的就緒隊(duì)列，不同的就緒隊(duì)列采用不同的調(diào)度算法，同一個(gè)就緒隊(duì)列采用同一種進(jìn)程調(diào)度算法。主要用于有多組就緒進(jìn)程的操作系統(tǒng)，如有

41、批處理用戶作業(yè)的進(jìn)程和終端用戶進(jìn)程，批處理用戶作業(yè)的進(jìn)程運(yùn)行在后臺(tái)，終端用戶的進(jìn)程運(yùn)行在前臺(tái)。一個(gè)作業(yè)的進(jìn)程固定劃分到一個(gè)就緒隊(duì)列中。按照用戶作業(yè)的性質(zhì)不同，就緒隊(duì)列進(jìn)行不同組織。,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,51/98,作業(yè)-進(jìn)程調(diào)度,某多道程序設(shè)計(jì)系統(tǒng)中配有一臺(tái)處理器CPU和兩臺(tái)輸入/輸出設(shè)備IO1和IO2。現(xiàn)有優(yōu)先級(jí)由高到低的3個(gè)進(jìn)程P1、P2、P3同時(shí)存在，它們使用資源的先后順序和占用時(shí)間分別是：進(jìn)程

42、P1：進(jìn)程P2：進(jìn)程P3：,IO2(30ms)-CPU(10ms)-IO1(30ms)-CPU(10ms)-IO2(10ms),IO1(20ms)-CPU(20ms)-IO1(40ms),CPU(30ms)-IO2(20ms),若進(jìn)程采用“可搶占的最高優(yōu)先級(jí)”調(diào)度算法，且忽略調(diào)度等所需的時(shí)間，請回答有下列問題：1）進(jìn)程P1、P2、P3從開始到完成所用的時(shí)間分別是多少（要求用坐標(biāo)畫出三個(gè)進(jìn)程的工作過程，其中橫坐標(biāo)表示時(shí)間，縱坐標(biāo)

43、表示CPU和IO設(shè)備）。2）這三個(gè)進(jìn)程從開始到全部完成時(shí)CPU的利用率是多少？IO1和IO2的利用率是多少？,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,52/98,本章目錄,3.1 處理器調(diào)度的層次3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則3.3 調(diào)度算法 3.4 線程調(diào)度3.5 實(shí)時(shí)調(diào)度3.6 多處理器調(diào)度3.7 Windows 2000/XP系統(tǒng)的處理器調(diào)度,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,53/

44、98,線程調(diào)度,現(xiàn)代OS中，進(jìn)程是資源分配的基本單位，線程是調(diào)度的基本單位。因此，低級(jí)調(diào)度為線程調(diào)度。由于線程需要進(jìn)程環(huán)境的支撐，因此，線程調(diào)度與線程和進(jìn)程之間的關(guān)系有關(guān)。線程的實(shí)現(xiàn)方式有:用戶級(jí)線程內(nèi)核級(jí)線程,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,54/98,線程調(diào)度,現(xiàn)代OS中，進(jìn)程是資源分配的基本單位，線程是調(diào)度的基本單位。因此，低級(jí)調(diào)度為線程調(diào)度。由于線程需要進(jìn)程環(huán)境的支撐，因此，線程調(diào)度與線程和進(jìn)程之間的

45、關(guān)系有關(guān)。線程的實(shí)現(xiàn)方式有:用戶級(jí)線程內(nèi)核級(jí)線程,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,55/98,用戶級(jí)線程,內(nèi)核看不見用戶級(jí)線程，內(nèi)核按照進(jìn)程調(diào)度分配處理器。 用戶級(jí)線程存在于用戶地址空間內(nèi)核在進(jìn)程調(diào)度時(shí)，根據(jù)相應(yīng)的進(jìn)程調(diào)度算法。在每個(gè)進(jìn)程分得的時(shí)間片中，由線程調(diào)度算法決定該進(jìn)程中的線程怎樣共享這個(gè)時(shí)間片，決定哪個(gè)線程首先被處理器運(yùn)行。線程調(diào)度算法與進(jìn)程調(diào)度算法沒有關(guān)系為實(shí)現(xiàn)簡單，線程調(diào)度算法會(huì)選擇FCF

46、S的方式。,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,56/98,用戶級(jí)線程,內(nèi)核看不見用戶級(jí)線程，內(nèi)核按照進(jìn)程調(diào)度分配處理器。 用戶級(jí)線程存在于用戶地址空間內(nèi)核在進(jìn)程調(diào)度時(shí)，根據(jù)相應(yīng)的進(jìn)程調(diào)度算法。在每個(gè)進(jìn)程分得的時(shí)間片中，由線程調(diào)度算法決定該進(jìn)程中的線程怎樣共享這個(gè)時(shí)間片，決定哪個(gè)線程首先被處理器運(yùn)行。線程調(diào)度算法與進(jìn)程調(diào)度算法沒有關(guān)系為實(shí)現(xiàn)簡單，線程調(diào)度算法會(huì)選擇FCFS的方式。,2024/3/1,《計(jì)算機(jī)操作

47、系統(tǒng)》- 第3章,57/98,內(nèi)核級(jí)線程,線程調(diào)度在處理器調(diào)度中起決定作用。內(nèi)核會(huì)根據(jù)線程調(diào)度算法選擇一個(gè)處于就緒狀態(tài)的內(nèi)核級(jí)線程運(yùn)行。在選擇線程時(shí)，內(nèi)核不會(huì)考慮該線程屬于哪一個(gè)進(jìn)程，對所有進(jìn)程的所有線程都公平對待，任何一個(gè)線程都被看作一個(gè)獨(dú)立的線程。線程最大的優(yōu)勢在于應(yīng)用在多處理器環(huán)境下,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,58/98,內(nèi)核級(jí)線程,線程調(diào)度在處理器調(diào)度中起決定作用。內(nèi)核會(huì)根據(jù)線程調(diào)度算法選

48、擇一個(gè)處于就緒狀態(tài)的內(nèi)核級(jí)線程運(yùn)行。在選擇線程時(shí)，內(nèi)核不會(huì)考慮該線程屬于哪一個(gè)進(jìn)程，對所有進(jìn)程的所有線程都公平對待，任何一個(gè)線程都被看作一個(gè)獨(dú)立的線程。線程最大的優(yōu)勢在于應(yīng)用在多處理器環(huán)境下,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,59/98,本章目錄,3.1 處理器調(diào)度的層次3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則3.3 調(diào)度算法 3.4 線程調(diào)度3.5 實(shí)時(shí)調(diào)度3.6 多處理器調(diào)度3.7 Windows

49、2000/XP系統(tǒng)的處理器調(diào)度,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,60/98,實(shí)時(shí)調(diào)度,實(shí)時(shí)操作系統(tǒng)中的處理器調(diào)度為實(shí)時(shí)調(diào)度。實(shí)時(shí)調(diào)度要求能夠控制實(shí)時(shí)進(jìn)程，滿足實(shí)時(shí)任務(wù)的時(shí)間限制。在實(shí)時(shí)系統(tǒng)中，衡量調(diào)度性能的指標(biāo)不是周轉(zhuǎn)時(shí)間和等待時(shí)間，而是能否滿足實(shí)時(shí)任務(wù)的截止時(shí)間要求。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,61/98,3.5.1 實(shí)時(shí)調(diào)度需要滿足的條件,實(shí)時(shí)任務(wù)截止時(shí)間是實(shí)時(shí)調(diào)度的基本指標(biāo)。實(shí)

50、時(shí)調(diào)度需要滿足如下條件：系統(tǒng)向?qū)崟r(shí)調(diào)度提供與實(shí)時(shí)任務(wù)相關(guān)的信息 對系統(tǒng)處理能力的衡量 搶占調(diào)度和快速切換機(jī)制,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,62/98,與實(shí)時(shí)任務(wù)相關(guān)的信息（1）,就緒起始時(shí)間 實(shí)時(shí)任務(wù)對應(yīng)的進(jìn)程被創(chuàng)建并加入到進(jìn)程就緒隊(duì)列如果實(shí)時(shí)任務(wù)是周期任務(wù)，就緒起始時(shí)間是一個(gè)時(shí)間串如果實(shí)時(shí)任務(wù)是非周期任務(wù)，就緒起始時(shí)間是一個(gè)預(yù)知的值截止時(shí)間當(dāng)實(shí)時(shí)系統(tǒng)中的實(shí)時(shí)任務(wù)發(fā)生時(shí)，實(shí)時(shí)系統(tǒng)中的就緒進(jìn)程按照進(jìn)程

51、的截止時(shí)間進(jìn)行排列對于周期性實(shí)時(shí)任務(wù)，截止時(shí)間為下一次任務(wù)發(fā)生的時(shí)間對于非周期性實(shí)時(shí)任務(wù)，任務(wù)的所有者需要提供截止時(shí)間,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,63/98,與實(shí)時(shí)任務(wù)相關(guān)的信息（2）,處理時(shí)間 實(shí)時(shí)任務(wù)從開始到完成所需要的時(shí)間?？捎蓪?shí)時(shí)任務(wù)的所有者提供，也可以由系統(tǒng)提供實(shí)時(shí)任務(wù)的資源需求實(shí)時(shí)任務(wù)執(zhí)行時(shí)所需要的一組資源 實(shí)時(shí)任務(wù)的優(yōu)先級(jí) 用戶或系統(tǒng)需要為每個(gè)實(shí)時(shí)任務(wù)指定優(yōu)先級(jí)，作為調(diào)度的依據(jù),2024

52、/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,64/98,對系統(tǒng)處理能力的衡量,實(shí)時(shí)系統(tǒng)中，可能因?yàn)樘幚砥鞯奶幚砟芰Σ蛔愣绊憣?shí)時(shí)任務(wù)的完成，或?qū)е孪到y(tǒng)產(chǎn)生故障。 單處理器情況下系統(tǒng)對周期性的實(shí)時(shí)任務(wù)的處理，必須滿足下列條件：其中，i表示周期事件，Pi為周期事件i發(fā)生的周期，Ci為需要處理器的處理時(shí)間。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,65/98,對系統(tǒng)處理能力的衡量,當(dāng)系統(tǒng)不能調(diào)度這些周期性實(shí)時(shí)任務(wù)時(shí)，可以通過提高處

53、理器的處理能力的方法減少每個(gè)周期任務(wù)的處理時(shí)間；或者采用多處理器系統(tǒng)，提高處理能力。如果采用的處理器數(shù)目為N，則處理?xiàng)l件變?yōu)椋?2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,66/98,搶占調(diào)度和快速切換機(jī)制,在要求嚴(yán)格的實(shí)時(shí)系統(tǒng)中，允許一個(gè)優(yōu)先權(quán)高的實(shí)時(shí)任務(wù)搶占優(yōu)先權(quán)低的實(shí)時(shí)任務(wù)在實(shí)際應(yīng)用中，判斷能否滿足截止時(shí)間要求不是一件容易的事 快速切換機(jī)制可以實(shí)現(xiàn)對實(shí)時(shí)任務(wù)的快速切換快速切換機(jī)制用硬件裝置實(shí)現(xiàn)快速中斷機(jī)構(gòu)，做到盡量

54、不漏掉實(shí)時(shí)任務(wù)的中斷，禁止中斷的時(shí)間越短越好在軟件實(shí)現(xiàn)上，也可以通過提高分派程序?qū)θ蝿?wù)切換的速度，以提高系統(tǒng)的性能。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,67/98,3.5.2 實(shí)時(shí)調(diào)度算法,實(shí)時(shí)調(diào)度算法分為:動(dòng)態(tài)實(shí)時(shí)調(diào)度算法在實(shí)時(shí)任務(wù)運(yùn)行時(shí)作出調(diào)度決策。靜態(tài)實(shí)時(shí)調(diào)度算法在系統(tǒng)啟動(dòng)實(shí)時(shí)任務(wù)之前作出調(diào)度決策。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,68/98,常用的實(shí)時(shí)調(diào)度算法 -- 搶占式調(diào)度算法,常

55、用于要求嚴(yán)格的實(shí)時(shí)系統(tǒng)中基于時(shí)鐘中斷的優(yōu)先權(quán)搶占調(diào)度算法如果某實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于正在運(yùn)行的任務(wù)，該實(shí)時(shí)任務(wù)并不立刻搶占，而是等到時(shí)鐘中斷到來時(shí)，才搶占。立即搶占調(diào)度算法一旦出現(xiàn)外部中斷，只要系統(tǒng)不處于臨界區(qū)，系統(tǒng)立即剝奪當(dāng)前執(zhí)行的任務(wù)，把處理器分配給當(dāng)前緊急的任務(wù)。單比率調(diào)度算法事先為每個(gè)實(shí)時(shí)任務(wù)分配一個(gè)與任務(wù)發(fā)生頻率成正比的優(yōu)先級(jí)，運(yùn)行頻率越高的任務(wù)，其優(yōu)先級(jí)越高。運(yùn)行時(shí)優(yōu)先級(jí)高的任務(wù)可以搶占優(yōu)先級(jí)低的任務(wù)。,2024/

56、3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,69/98,常用的實(shí)時(shí)調(diào)度算法 -- 非搶占式調(diào)度算法,實(shí)時(shí)調(diào)度中，對于實(shí)時(shí)要求不太嚴(yán)格的系統(tǒng)，可以采用非搶占式調(diào)度 非搶占式輪轉(zhuǎn)調(diào)度算法運(yùn)行完一個(gè)對象的實(shí)時(shí)任務(wù)（將其掛在隊(duì)列尾，等待下次運(yùn)行），再運(yùn)行另一個(gè)對象的實(shí)時(shí)任務(wù)。所有實(shí)時(shí)任務(wù)輪轉(zhuǎn)。非搶占式優(yōu)先級(jí)調(diào)度算法系統(tǒng)按照優(yōu)先級(jí)進(jìn)行非搶占調(diào)度。要求緊迫的實(shí)時(shí)任務(wù)賦予高的優(yōu)先級(jí)，排在就緒隊(duì)列隊(duì)首，先進(jìn)行調(diào)度。期限調(diào)度算法根據(jù)實(shí)時(shí)任務(wù)的截止期

57、限進(jìn)行就緒隊(duì)列的排隊(duì)，截至期限短的實(shí)時(shí)任務(wù)排在隊(duì)首，首先進(jìn)行調(diào)度。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,70/98,常用的實(shí)時(shí)調(diào)度算法舉例,實(shí)時(shí)系統(tǒng)中有一組實(shí)時(shí)任務(wù)A、B、C、D、E，CPU處理時(shí)間分別為325ms、225ms、160ms、95ms、420ms，截止時(shí)間分別為690ms、675ms、無期限、135ms、1 100ms。如果采用最小截止期限優(yōu)先調(diào)度算法，這些進(jìn)程調(diào)度的順序?yàn)椋?2024/3/1,《

58、計(jì)算機(jī)操作系統(tǒng)》- 第3章,71/98,常用的實(shí)時(shí)調(diào)度算法舉例,實(shí)時(shí)系統(tǒng)中有一組實(shí)時(shí)任務(wù)A、B、C、D、E，CPU處理時(shí)間分別為325ms、225ms、160ms、95ms、420ms，截止時(shí)間分別為690ms、675ms、無期限、135ms、1 100ms。采用最小截止期限優(yōu)先調(diào)度算法，進(jìn)程調(diào)度的順序?yàn)椋篋→B→A→E→C,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,72/98,本章目錄,3.1 處理器調(diào)度的層次3

59、.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則3.3 調(diào)度算法 3.4 線程調(diào)度3.5 實(shí)時(shí)調(diào)度3.6 多處理器調(diào)度3.7 Windows 2000/XP系統(tǒng)的處理器調(diào)度,,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,73/98,多處理器調(diào)度,計(jì)算機(jī)系統(tǒng)有多個(gè)處理器，多個(gè)處理器的調(diào)度稱為多處理器調(diào)度。多處理器調(diào)度與多處理器系統(tǒng)的結(jié)構(gòu)形式有關(guān)：松耦合多處理器系統(tǒng)每個(gè)處理器相對獨(dú)立，擁有自己的內(nèi)存和I/O通道。多處理器調(diào)度對系統(tǒng)中的

60、每個(gè)處理器，采取與單處理器調(diào)度相同的方法。緊耦合多處理器系統(tǒng)多個(gè)處理器共享內(nèi)存和外圍設(shè)備，處理器的相對獨(dú)立性差。在這種多處理器系統(tǒng)中，處理器調(diào)度方法比較復(fù)雜。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,74/98,多核處理器,多核處理器是在一個(gè)處理器中封裝多個(gè)處理核（單元），每個(gè)核都具有處理能力。多核處理器相當(dāng)于共用內(nèi)存和外圍設(shè)備的多處理器，在原理上多核處理器屬于緊耦合多處理器系統(tǒng)。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》-

61、 第3章,75/98,3.6.1 多處理器中同步的粒度,在多處理器系統(tǒng)中，不但存在多處理器的并行，還存在單處理器的并發(fā)。多處理器中同步的粒度指系統(tǒng)中的多個(gè)進(jìn)程或線程之間同步的頻率，是描述多處理器系統(tǒng)特征和進(jìn)程并發(fā)度的重要指標(biāo)。根據(jù)進(jìn)程或線程之間同步的周期劃分為5個(gè)層次：細(xì)粒度并行、中粒度并行、粗粒度并行、超粗粒度并行、獨(dú)立并行。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,76/98,同步的周期,細(xì)粒度并行同步周期小于20條

62、指令，非常復(fù)雜的并行操作，屬于超高并行度應(yīng)用中粒度并行同步周期為20～200條指令。此類應(yīng)用適合于多線程技術(shù)實(shí)現(xiàn)，多線程并發(fā)執(zhí)行，降低OS在進(jìn)程切換上的開銷。粗粒度并行同步周期為200～2 000條指令，此類應(yīng)用適用于多進(jìn)程并發(fā)實(shí)現(xiàn)。超粗粒度并行同步周期為2 000條指令以上，進(jìn)程之間的交互頻率非常小。獨(dú)立并行進(jìn)程之間沒有明顯的同步，每個(gè)進(jìn)程都代表獨(dú)立的應(yīng)用或作業(yè)。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)

63、》- 第3章,77/98,同步的周期,一個(gè)具有細(xì)粒度和中粒度并行的線程應(yīng)用，由于線程之間的交互非常頻繁，線程的調(diào)度策略對整個(gè)系統(tǒng)的性能有很大影響。對具有獨(dú)立并行的進(jìn)程、具有粗粒度并行的進(jìn)程和超粗粒度并行的進(jìn)程，進(jìn)程的調(diào)度策略與多道程序系統(tǒng)相似。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,78/98,3.6.2 多處理器調(diào)度的設(shè)計(jì)要點(diǎn),多處理器調(diào)度策略的設(shè)計(jì)比單處理器復(fù)雜，其設(shè)計(jì)要點(diǎn)包括：多處理器分配策略如何在每個(gè)處理器上

64、支持多道線程 如何從就緒隊(duì)列中指派進(jìn)程,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,79/98,多處理器分配策略,（1）結(jié)構(gòu)上多個(gè)處理器地位相同多處理器對內(nèi)存和I/O設(shè)備的訪問方式相同，地位相當(dāng)所有處理器放在一個(gè)處理器池中靜態(tài)分配策略在進(jìn)程創(chuàng)建時(shí)系統(tǒng)把所創(chuàng)建的進(jìn)程永久分配給一個(gè)處理器，每個(gè)處理器對應(yīng)一個(gè)進(jìn)程調(diào)度隊(duì)列。動(dòng)態(tài)分配策略所有處理器共用一個(gè)進(jìn)程就緒隊(duì)列，當(dāng)某個(gè)處理器空閑時(shí)，系統(tǒng)從進(jìn)程就緒隊(duì)列中調(diào)度一個(gè)進(jìn)程運(yùn)行。,

65、,優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，調(diào)度代價(jià)低缺點(diǎn)：容易造成處理器之間工作負(fù)荷不均勻,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,80/98,多處理器分配策略,（1）結(jié)構(gòu)上多個(gè)處理器地位相同多處理器對內(nèi)存和I/O設(shè)備的訪問方式相同，地位相當(dāng)所有處理器放在一個(gè)處理器池中靜態(tài)分配策略在進(jìn)程創(chuàng)建時(shí)系統(tǒng)把所創(chuàng)建的進(jìn)程永久分配給一個(gè)處理器，每個(gè)處理器對應(yīng)一個(gè)進(jìn)程調(diào)度隊(duì)列。動(dòng)態(tài)分配策略所有處理器共用一個(gè)進(jìn)程就緒隊(duì)列，當(dāng)某個(gè)處理器空閑時(shí)，系統(tǒng)從進(jìn)程就

66、緒隊(duì)列中調(diào)度一個(gè)進(jìn)程運(yùn)行。,,優(yōu)點(diǎn): 簡單、方便，利于提高系統(tǒng)效率缺點(diǎn): 進(jìn)程在不同處理器之間切換，系統(tǒng)調(diào)度進(jìn)程開銷大,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,81/98,多處理器分配策略,（2）結(jié)構(gòu)上多個(gè)處理器地位不同 如果各處理器之間對內(nèi)存和I/O設(shè)備的地位和訪問方式不相同，則系統(tǒng)可將多個(gè)處理器分為主處理器和從處理器，主處理器管理從處理器。OS核心運(yùn)行在主處理器上，所有的調(diào)度策略由主處理器上的OS核心決定，多處理器調(diào)度

67、需要考慮每個(gè)處理器的工作負(fù)荷。優(yōu)點(diǎn): 處理器調(diào)度效率非常高，甚至比單處理器下的多道程序系統(tǒng)還高。缺點(diǎn): 整個(gè)系統(tǒng)過分依賴主處理器上運(yùn)行的OS核心，如果OS核心出現(xiàn)問題或主處理器出現(xiàn)問題，多處理器系統(tǒng)會(huì)全面崩潰。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,82/98,多處理器分配策略,多處理器系統(tǒng)如果不采用主從方式，可以采用分布式管理結(jié)構(gòu)。在分布式管理結(jié)構(gòu)下，OS可以在所有處理器上執(zhí)行，每個(gè)處理器都可以自我調(diào)度，系統(tǒng)的可靠性更

68、高。缺點(diǎn)：實(shí)現(xiàn)非常復(fù)雜，在操作系統(tǒng)之間很難保持同步。,2024/3/1,《計(jì)算機(jī)操作系統(tǒng)》- 第3章,83/98,多處理器分配策略,綜合主從式系統(tǒng)和分布式系統(tǒng)的優(yōu)點(diǎn)，CMU的Mach操作系統(tǒng)就是一個(gè)典范。支持線程的操作系統(tǒng)建立二級(jí)線程隊(duì)列，實(shí)現(xiàn)多處理器下線程調(diào)度第1級(jí)為一個(gè)全局共享的就緒線程隊(duì)列第2級(jí)為每一個(gè)處理器的局部就緒線程隊(duì)列第2級(jí)隊(duì)列中所有線程都已調(diào)度完，系統(tǒng)才到全局就緒線程隊(duì)列中按照動(dòng)態(tài)調(diào)度策略分配線程,2024/