1、操作系統(tǒng) Chapter3 處理器調(diào)度與死鎖,主要內(nèi)容,處理器調(diào)度的層次,評價調(diào)度算法的準則,處理器調(diào)度算法,線程調(diào)度,實時調(diào)度,多處理器調(diào)度,高級調(diào)度-作業(yè)調(diào)度 中級調(diào)度 低級調(diào)度-進程調(diào)度,調(diào)度的本質(zhì) 進程調(diào)度的概念,內(nèi)容,要點,Windows 2000/XP系統(tǒng)的處理器調(diào)度,調(diào)度的概念與本質(zhì),調(diào)度： 系統(tǒng)將計算機資源分配給進程。 單道程序環(huán)境與多道程序環(huán)境 處理器調(diào)度： 多道程序環(huán)境下將處理器分配給各進程,調(diào)度要解決的問題： WHAT：按什么原則分配CPU 調(diào)度算法 WHEN：何時分配CPU 調(diào)度的時機 HOW： 如何分配CPU 調(diào)度過程,處理器調(diào)度的層次,處理機是計算機系統(tǒng)中的重要資源

2、 處理機調(diào)度算法對整個計算機系統(tǒng)的綜合性能指標有重要影響 處理機調(diào)度的三個層次： 高級調(diào)度 中級調(diào)度 低級調(diào)度,高級調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度 高級調(diào)度的時間尺度通常是分鐘、小時或天,中級調(diào)度涉及進程在內(nèi)外存間的交換 從存儲器資源管理的角度來看，把進程的部分或全部換出到外存上，可為當前運行進程的執(zhí)行提供所需內(nèi)存空間，將當前進程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機直接訪問,低級調(diào)度也稱微觀調(diào)度 從處理機資源分配的角度來看，處理機需要經(jīng)常選擇就緒進程或線程進入運行狀態(tài)，低級調(diào)度的時間尺度通常是毫秒級的。 由于低級調(diào)度算法的頻繁使用，要求在實現(xiàn)時做到高效。,高級調(diào)度-作業(yè)的概念與

3、分類,概念： 作業(yè)由一組統(tǒng)一管理和操作的進程集合構(gòu)成，是用戶要求計算機系統(tǒng)完成的一項相對獨立的工作。 作業(yè)可以是完成了編譯、鏈接之后的一個用戶程序，也可以是用各種命令構(gòu)成的一個腳本。 分類： 根據(jù)需要處理工作的類型，分為計算型作業(yè)和I/O型作業(yè)。 按照作業(yè)提交方式，分為批處理作業(yè)和終端型作業(yè)。 一個系統(tǒng)能夠接納作業(yè)的個數(shù)稱為系統(tǒng)的多道程序度。,作業(yè)被調(diào)度到內(nèi)存，為作業(yè)分配資源并為其創(chuàng)建與之對應的進程，進程獲得CPU，開始運行。,從作業(yè)的第一個進程完成開始，直到作業(yè)所有的進程完成，釋放作業(yè)做占用的資源，退出系統(tǒng)的整個進程。,系統(tǒng)接收輸入的用戶作業(yè)，并將其放入計算機磁盤。作業(yè)在磁盤上以后備隊列形式

4、進行組織，等待作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)度到內(nèi)存。,用戶將作業(yè)提交給操作系統(tǒng)，等待輸入程序和數(shù)據(jù)到磁盤。,高級調(diào)度-策略與因素,接納多少個作業(yè) 作業(yè)數(shù)目太多時，可能會影響到系統(tǒng)的服務質(zhì)量; 作業(yè)的數(shù)量太少時，又會導致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低 接納哪些作業(yè) 先來先服務調(diào)度算法 短作業(yè)優(yōu)先調(diào)度算法 基于作業(yè)優(yōu)先級的調(diào)度算法 響應比高者優(yōu)先”的調(diào)度算法,主要內(nèi)容,處理器調(diào)度的層次,評價調(diào)度算法的準則,處理器調(diào)度算法,線程調(diào)度,實時調(diào)度,多處理器調(diào)度,高級調(diào)度-作業(yè)調(diào)度 中級調(diào)度 低級調(diào)度-進程調(diào)度,調(diào)度的本質(zhì) 進程調(diào)度的概念,內(nèi)容,要點,Windows 2000/XP系統(tǒng)的處理器調(diào)度,中級調(diào)度-概

5、念與功能,又稱為中程調(diào)度，是為了提高內(nèi)存利用率和平衡系統(tǒng)負載而采取的一種利用外存補充內(nèi)存的措施。 多進程環(huán)境下，內(nèi)存中存在多個進程，其中有些進程可能需要掛起，這些進程暫時不參與對處理器的競爭。 為了充分利用內(nèi)存資源，系統(tǒng)會采用進程對換的方法將進程換出到外存，將這些進程占用的內(nèi)存空間釋放，讓內(nèi)存能夠接納新的進程或使得內(nèi)存中的進程能夠更快推進。當被換出到外存中的進程掛起時間到時，又需要將這些進程換入到內(nèi)存。 中級調(diào)度是在換出內(nèi)存的進程中確定需要進入內(nèi)存的進程的一種調(diào)度操作。,主要內(nèi)容,處理器調(diào)度的層次,評價調(diào)度算法的準則,處理器調(diào)度算法,線程調(diào)度,實時調(diào)度,多處理器調(diào)度,高級調(diào)度-作業(yè)調(diào)度 中級調(diào)

6、度 低級調(diào)度-進程調(diào)度,調(diào)度的本質(zhì) 進程調(diào)度的概念,內(nèi)容,要點,Windows 2000/XP系統(tǒng)的處理器調(diào)度,低級調(diào)度-概念與功能,又稱為進程調(diào)度、短程調(diào)度 按照一定的調(diào)度算法從內(nèi)存的就緒進程隊列中選擇進程，為進程分配處理器，避免進程對處理器競爭的方法。 與作業(yè)調(diào)度和中級調(diào)度比較，進程調(diào)度發(fā)生的頻率最高，作業(yè)調(diào)度發(fā)生的頻率最低，中級調(diào)度主要用于內(nèi)存管理，特別是虛擬存儲器管理。,3.1.2 進程調(diào)度模型,只有進程調(diào)度的調(diào)度隊列模型,低級調(diào)度-模型,3.1.2 進程調(diào)度模型,具有高、低兩級調(diào)度的調(diào)度隊列模型,低級調(diào)度-模型,具有三級調(diào)度時的調(diào)度隊列模型,3.1.2 進程調(diào)度模型,低級調(diào)度-模型,

7、低級調(diào)度-原因與機制,引起進程調(diào)度的主要原因如下： 處理器執(zhí)行的進程完成任務，處理器空閑 處理器執(zhí)行的進程轉(zhuǎn)入阻塞狀態(tài)，此時處理器空閑 處理器執(zhí)行的進程被其它進程搶占 處理器執(zhí)行的進程被掛起 機制： 排隊器 分派器 上下文切換機制,低級調(diào)度-調(diào)度方式,非搶占方式： 簡單，實時性差 搶占方式 時間片原則 優(yōu)先權(quán)原則 短作業(yè)優(yōu)先原則。,如果執(zhí)行進程正好在執(zhí)行一個沒有資源的無限循環(huán)，則執(zhí)行進程不會放棄處理器，所有的就緒進程會永久等待，系統(tǒng)進入了一種僵持的狀態(tài)。,指一個進程正在處理器中運行時，操作系統(tǒng)可以根據(jù)規(guī)定的搶占原則，將已經(jīng)分配給進程的處理器從進程剝奪，并分配給其他的進程。,在系統(tǒng)允許搶占調(diào)度，

8、并滿足搶占條件的情況下，系統(tǒng)才可以采用搶占調(diào)度方式。,滿足搶占條件的進程能夠搶占當前正在執(zhí)行進程的處理器。被搶占的進程狀態(tài)從執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)，其進程控制塊進入到進程就緒隊列。,思考：“搶占”可能帶來的問題及原因？,主要內(nèi)容,處理器調(diào)度的層次,評價調(diào)度算法的準則,處理器調(diào)度算法,線程調(diào)度,實時調(diào)度,多處理器調(diào)度,準則 評價指標,內(nèi)容,Windows 2000/XP系統(tǒng)的處理器調(diào)度,指標含義 計算方式,要點,調(diào)度算法的評價準則,基本原則： 具有公平性 資源利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應時間（越短越好） 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量,面向系統(tǒng)的準則： 系統(tǒng)吞吐

9、量高； 處理機利用率好； 各類資源的平衡利用,面向用戶的準則： 周轉(zhuǎn)時間短； 響應時間快； 截止時間的保證； 優(yōu)先權(quán)準則,處理器利用率 CPU utilization 響應時間 response time 周轉(zhuǎn)時間 turnaround time 系統(tǒng)吞吐量 throughput,處理器利用率為CPU有效工作時間與CPU總的運行時間之比，即： CPU利用率=CPU有效工作時間/CPU總的運行時間 CPU總的運行時間=CPU的有效工作時間+CPU的空閑時間,響應時間是交互環(huán)境下用戶從鍵盤提交第1個請求開始，到系統(tǒng)首次產(chǎn)生響應為止的時間，或者是屏幕上顯示出結(jié)果為止的時間。 響應時間=從終端鍵盤輸入

10、的請求信息傳送到處理機的時間+處理機對請求信息的處理時間+生成的響應信息回送到終端顯示器的時間,周轉(zhuǎn)時間指用戶作業(yè)提交給操作系統(tǒng)開始到作業(yè)完成為止的時間。周轉(zhuǎn)時間通常是評價批處理系統(tǒng)性能、選擇作業(yè)調(diào)度方式與算法的重要準則之一。 周轉(zhuǎn)時間Ti=作業(yè)在后備隊列中的等待調(diào)度時間+進程在就緒隊列上等待調(diào)度的時間+進程在CPU上的運行時間+進程等待I/O或其他事件發(fā)生的時間 作業(yè)的帶權(quán)周轉(zhuǎn)時間Tf=作業(yè)的周轉(zhuǎn)時間Ti/系統(tǒng)為作業(yè)提供的服務時間Tsi,單位時間內(nèi)處理的進程數(shù)目為CPU的工作成效，單位時間內(nèi)完成的進程數(shù)目為系統(tǒng)的吞吐量。,在選擇處理器的調(diào)度算法時，用戶希望CPU利用率和系統(tǒng)吞吐量越大越好，響

11、應時間和周轉(zhuǎn)時間越小越好。 但是，通常情況下，系統(tǒng)希望的是能夠合理利用處理器和各類資源，使作業(yè)的平均周轉(zhuǎn)時間或帶權(quán)周轉(zhuǎn)時間小的調(diào)度算法。 對于實時系統(tǒng)，作業(yè)調(diào)度的關鍵在于能否滿足作業(yè)的實時要求，對周轉(zhuǎn)時間等指標并不特別著重。,調(diào)度算法的評價指標,主要內(nèi)容,處理器調(diào)度的層次,評價調(diào)度算法的準則,處理器調(diào)度算法,線程調(diào)度,實時調(diào)度,多處理器調(diào)度,作業(yè)調(diào)度算法 進程調(diào)度算法,內(nèi)容,Windows 2000/XP系統(tǒng)的處理器調(diào)度,算法思想 指標計算,要點,作業(yè)調(diào)度算法,概念回顧 作業(yè)調(diào)度是在資源滿足的條件下，將處于后備狀態(tài)的作業(yè)調(diào)入內(nèi)存，同時生成與作業(yè)相對應的進程，并為這些進程提供所需要的資源。 作業(yè)

12、調(diào)度程序只保證被調(diào)度的作業(yè)有獲得處理器的資格，而處理器的分配則需要進程調(diào)度才能完成。 主要算法 FCFS：先來先服務（First-Come First-Served) SJF：短作業(yè)優(yōu)先（Shortest-Job-First） HRRF：響應比高者優(yōu)先 HPF：優(yōu)先權(quán)高者優(yōu)先（ Highest-Priority-First) 分類調(diào)度,FCFS：先來先服務,基本思想 遵循先進入后備隊列的作業(yè)，先進行調(diào)度的原則。 非搶占式算法 簡單，易于編碼實現(xiàn) 優(yōu)先考慮作業(yè)的等待時間，沒有考慮作業(yè)的執(zhí)行時間長短、作業(yè)的運行特性和作業(yè)對資源的要求 算法評價 有利于長作業(yè)，不利于短作業(yè) 有利于CPU繁忙的作業(yè)，不

13、利于I/O繁忙的作業(yè) 舉例？,FCFS：先來先服務-例1,作業(yè)J1、J2、J3、J4依次到達作業(yè)后備隊列，需要處理時間分別如下：J1為15ms，J2為5ms，J3為10ms，J4為3ms。 請給出作業(yè)執(zhí)行的圖示（橫軸為時間，縱軸為作業(yè)） 請計算每個作業(yè)的等待時間和周轉(zhuǎn)時間 請計算上述作業(yè)的平均等待時間和平均周轉(zhuǎn)時間,FCFS：先來先服務-例2,如果4個作業(yè)A、B、C、D到達系統(tǒng)磁盤后備隊列的順序和需要執(zhí)行的時間如下表所示。,請給出作業(yè)執(zhí)行的圖示（橫軸為時間，縱軸為作業(yè)） 請計算每個作業(yè)的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間 請計算上述作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間,SJF：短作業(yè)優(yōu)先,基本思想 根據(jù)作

14、業(yè)控制塊中作業(yè)申請時指出的執(zhí)行時間，選取執(zhí)行時間最短的作業(yè)優(yōu)先調(diào)度。 搶占調(diào)度方式：只要就緒隊列中出現(xiàn)了需要執(zhí)行時間比當前正在運行作業(yè)的剩余處理時間更短的作業(yè)，則該作業(yè)會搶占當前正在運行的作業(yè)。 算法評價 克服FCFS調(diào)度算法對短作業(yè)不利的缺點，效率高，易于編程實現(xiàn) 不利于長作業(yè) 預先估計作業(yè)的執(zhí)行時間 舉例？,SJF：短作業(yè)優(yōu)先-例3,作業(yè)A、B、C、D需要處理的時間分別為20ms、15ms、10ms、5ms。 如果這4個作業(yè)同時到達作業(yè)后備隊列 請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示 請計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間,如果這4個作業(yè)不是同時到達，A作業(yè)在0時間到達，B作業(yè)在A作業(yè)之

15、后5ms達到，C作業(yè)在A作業(yè)之后10ms達到，D作業(yè)在A作業(yè)之后15ms達到 請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示 請計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間,如果A作業(yè)到達的時間為0，B、C、D作業(yè)達到系統(tǒng)的時間分別改為1ms、2ms、3ms 請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示 請計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間,HRRF：響應比高者優(yōu)先,初衷 FCFS調(diào)度算法只片面地考慮了作業(yè)的進入時間，短作業(yè)優(yōu)先調(diào)度算法考慮了作業(yè)的運行時間而忽略了作業(yè)的等待時間。 響應比高者優(yōu)先調(diào)度算法為這兩種算法的折中。 響應比計算 作業(yè)的響應時間與作業(yè)需要處理的時間之比。 作業(yè)的響應時間為作業(yè)進入系統(tǒng)后的

16、等待時間與作業(yè)要求處理器處理的時間之和。 搶占調(diào)度方式,HRRF：響應比高者優(yōu)先,分析與評價 響應比高，可能是因為作業(yè)等待時間長，也可能是因為作業(yè)需要處理時間短。 響應比高優(yōu)先調(diào)度算法不僅體現(xiàn)了等待時間長的作業(yè)會優(yōu)先調(diào)度，而且還體現(xiàn)了處理時間短的作業(yè)也會優(yōu)先調(diào)度。 該算法能夠客觀地對待長作業(yè)和短作業(yè)。 舉例？,HRRF：響應比高者優(yōu)先-例4,如果4個作業(yè)A、B、C、D到達系統(tǒng)磁盤后備隊列的順序和需要執(zhí)行的時間如下表所示。,計算各時間點的響應比及調(diào)度情況。 請給出作業(yè)執(zhí)行的圖示（橫軸為時間，縱軸為作業(yè)） 請計算上述作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間,FCFS、SJF、HRRF：比較,思考：對上

17、述比較結(jié)果進行分析和評價。,HPF：優(yōu)先權(quán)高者優(yōu)先,基本思想 根據(jù)作業(yè)的優(yōu)先權(quán)進行作業(yè)調(diào)度，每次總是選取優(yōu)先權(quán)高的作業(yè)調(diào)度。 作業(yè)的優(yōu)先數(shù)可由系統(tǒng)或用戶給定。 評價 綜合考慮了作業(yè)的執(zhí)行時間和等待時間的長短、作業(yè)的緩急程度、作業(yè)對外部設備的使用情況等因素 根據(jù)系統(tǒng)設計目標和運行環(huán)境而給定各作業(yè)的優(yōu)先權(quán)，決定作業(yè)調(diào)度的先后順序。 舉例？,HPF：優(yōu)先權(quán)高者優(yōu)先-例5,作業(yè)A、B、C、D一起達到，需要處理的時間分別為25ms、5ms、10ms、3ms，優(yōu)先數(shù)分別為154、139、149、130，優(yōu)先數(shù)越大、優(yōu)先級越低。 請給出采用短作業(yè)優(yōu)先調(diào)度算法的作業(yè)執(zhí)行圖示 請計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時

18、間 靜態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán),思考：動態(tài)優(yōu)先權(quán)的“動態(tài)性”體現(xiàn)？,綜合：分類調(diào)度算法,目的： 均衡使用系統(tǒng)資源 兼顧不同大小的作業(yè) 基本思想 按照使用系統(tǒng)資源或作業(yè)的大小的不同 首先分別對作業(yè)進行分類 然后再根據(jù)作業(yè)的類型進行調(diào)度 還可以進一步將同一類別的作業(yè)再按照優(yōu)先級進行排隊,主要內(nèi)容,處理器調(diào)度的層次,評價調(diào)度算法的準則,處理器調(diào)度算法,線程調(diào)度,實時調(diào)度,多處理器調(diào)度,作業(yè)調(diào)度算法 進程調(diào)度算法,內(nèi)容,Windows 2000/XP系統(tǒng)的處理器調(diào)度,算法思想 指標計算,要點,進度調(diào)度算法,概念回顧 進程調(diào)度算法是低級調(diào)度算法。 在傳統(tǒng)操作系統(tǒng)中，進程為資源分配和調(diào)度的基本單位，是操作系統(tǒng)

19、中發(fā)生頻率最高的調(diào)度。 主要算法 FCFS：先來先服務（略） TRR：時間片輪轉(zhuǎn)調(diào)度算法 優(yōu)先級調(diào)度算法 MQ：多級隊列調(diào)度算法 MFQ：多級反饋隊列調(diào)度算法,TRR：時間片輪轉(zhuǎn)調(diào)度算法,基本思想 分時思想 首先將處理器的處理時間劃分為大小相等的時間片。 調(diào)度程序每次從就緒隊列中選擇隊首的進程，為之分配處理器的一個時間片并讓進程運行。 當進程運行的時間片到時，強迫進程放棄處理器，到就緒隊列中再次排隊，并將處理器的下一個時間片分配給就緒隊列中隊首的進程。 所有就緒隊列中的進程按照這樣的形式輪轉(zhuǎn)使用處理器時間片。 舉例?,TRR：時間片輪轉(zhuǎn)調(diào)度算法-例6,進程A、B、C、D需要處理的時間分別為20

20、ms、10ms、15ms、5ms，在0時間達到。達到的先后順序為ABCD。 請給出不同時間片下的調(diào)度圖示； 請計算不同時間片下的平均周轉(zhuǎn)時間。 A：時間片為1 A：時間片為5 A：時間片為10,思考：時間片大小與平均周轉(zhuǎn)時間的關系？,TRR：時間片輪轉(zhuǎn)調(diào)度算法,分析與評價 搶占式調(diào)度算法 進程切換以時間片為單位，系統(tǒng)的花銷主要體現(xiàn)在進程切換上。 當時間片很小時，切換的頻率高，時間片花銷大。 當時間片過大時，進程切換開銷減小，但是進程輪轉(zhuǎn)一次需要的等待時間增加，周轉(zhuǎn)時間增加。 當時間片大到每個進程足以完成時，時間片調(diào)度算法便退化為FCFS算法。 時間片大小的取值需要考慮系統(tǒng)中進程個數(shù)、進程切換開銷、響應時間、系統(tǒng)效率等多種因素。,思考：固定大小時間片與可變大小時間片？,優(yōu)先級調(diào)度算法-例7,同時達到的進程P1、P2、P3、P4，它們的優(yōu)先數(shù)分別為80、70、75、65，數(shù)字越大表示進程優(yōu)先級越高，需要處理的時間分別是20ms、15ms、25ms、30ms。 請給出采用優(yōu)先級算法的調(diào)度圖示； 請計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。,MQ：多級隊列調(diào)度算法,基本思想