【正文】 JF (b) 帶權(quán)周轉(zhuǎn)時間 1 2. 67 3. 1 1. 5 2. 25 2. 1 第三章 處理機調(diào)度與死鎖 2．短作業(yè) (進程 )優(yōu)先調(diào)度算法 短作業(yè) (進程 )優(yōu)先調(diào)度算法 SJ(P)F（ Shortest job first ） ，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。 進程名 到達時間 服務(wù)時間 開始執(zhí)行時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周 轉(zhuǎn)時間 A 0 1 0 1 1 1 B 1 100 1 101 100 1 C 2 1 101 102 100 100 D 3 100 102 202 199 1. 99 第三章 處理機調(diào)度與死鎖 從表上可以看出，其中短作業(yè) C的帶權(quán)周轉(zhuǎn)時間競高達100，這是不能容忍的；而長作業(yè) D的帶權(quán)周轉(zhuǎn)時間僅為 。在進程調(diào)度中采用 FCFS算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。 ??? 系統(tǒng)資源的均衡使用。 在大、中型系統(tǒng)中，不僅要使處理機的利用率高，而且還應(yīng)能有效地利用其它各類資源，如內(nèi)存、外存和 I/O設(shè)備等。 ? 與批處理作業(yè)的平均長度具有密切關(guān)系 。在要求較嚴(yán)格的場合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時處理。 這是評價 實時系統(tǒng) 性能的重要指標(biāo) ， 因而是選擇實時調(diào)度算法的重要準(zhǔn)則 。 常把響應(yīng)時間的長短用來評價 分時系統(tǒng) 的性能，這是選擇分時系統(tǒng)中進程調(diào)度算法的重要準(zhǔn)則之一。 評價 批處理系統(tǒng) 的性能 、 選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一 。類似地，也可把阻塞狀態(tài)進一步分成 內(nèi)存阻塞 和 外存阻塞 兩種狀態(tài)。 作業(yè)調(diào)度往往是發(fā)生在一個 (批 )作業(yè)運行完畢，退出系統(tǒng)，而需要重新調(diào)入一個 (批 )作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約 幾分鐘（幾小時 ）一次，因此把它稱為長程調(diào)度。 ? 優(yōu)點：公平，能滿足對響應(yīng)時間有著較嚴(yán)格要求的實時任務(wù)的需求。 ??? 在可剝奪調(diào)度方式中，一個具有更高優(yōu)先數(shù)的進程進入就緒隊列。在第一對上下文切換時，操作系統(tǒng)將保存當(dāng)前進程的上下文，而裝入分派程序的上下文，以便分派程序運行；在第二對上下文切換時，將移出分派程序，而把新選進程的 CPU現(xiàn)場信息裝入到處理機的各個相應(yīng)寄存器中。 就緒進程按照一定的方式排成一個或多個隊列 (2) 分派器 (分派程序 )。 第三章 處理機調(diào)度與死鎖 低級調(diào)度的主要功能如下： (1) 保存處理機的現(xiàn)場信息 。在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。 ③ 運行狀態(tài) ：作業(yè)被調(diào)度程序選中而被送入主存中投入運行。 ?通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識、用戶名稱、用戶帳戶、作業(yè)類型 (CPU 繁忙型、 I/O 繁忙型、批量型、終端型 )、作業(yè)狀態(tài)、調(diào)度信息 (優(yōu)先級、作業(yè)已運行時間 )、資源需求 (預(yù)計運行時間、要求內(nèi)存大小、要求 I/O設(shè)備的類型和數(shù)量等 )、進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。 通常 ， 在作業(yè)運行期間 ， 每個作業(yè)都必須經(jīng)過若干個相對獨立 ， 又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果 ， 我們把其中的每一個加工步驟稱為一個作業(yè)步 ， 各作業(yè)步之間存在著相互聯(lián)系 ， 往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入 。 目的：提高內(nèi)存的利用率和系統(tǒng)吞吐量。第三章 處理機調(diào)度與死鎖 第三章 處理機調(diào)度與死鎖 處理機調(diào)度的層次 調(diào)度隊列模型和調(diào)度準(zhǔn)則 調(diào)度算法 實時調(diào)度 產(chǎn)生死鎖的原因和必要條件 預(yù)防死鎖的方法 死鎖的檢測與解除 第三章 處理機調(diào)度與死鎖 ?處理機是計算機系統(tǒng)中的重要資源 ?處理機調(diào)度算法對整個計算機系統(tǒng)的綜合性能指標(biāo)有重要影響 ?不同的 OS，處理機管理的策略不同 ?可把處理機調(diào)度分成三個層次： ? 高級調(diào)度 ? 中級調(diào)度 ? 低級調(diào)度 處理機調(diào)度的層次 第三章 處理機調(diào)度與死鎖 處理機調(diào)度的層次 ?高級調(diào)度（ 宏觀調(diào)度、作業(yè)調(diào)度、長程調(diào)度 ） 主要功能：根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。 第三章 處理機調(diào)度與死鎖 ?低 級調(diào)度 （ 微觀調(diào)度、進程調(diào)度、短程調(diào)度 ） 功能：決 定就緒隊列中的哪個進程 (或內(nèi)核級線程 )應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作 . ?中 級調(diào)度 （中程調(diào)度、交換調(diào)度） 按照給定的原則和策略，將處于外存交換區(qū)中的就緒狀態(tài)或等待狀態(tài)的進程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進程交換到外存交換區(qū)中。 第三章 處理機調(diào)度與死鎖 (2) 作業(yè)步 (Job Step)。 第三章 處理機調(diào)度與死鎖 2． 作業(yè)控制塊 JCB(Job Control Block) ?是作業(yè)在系統(tǒng)中存在的標(biāo)志 ?保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。 ② 后備狀態(tài) ：作業(yè)的全部信息都已輸入，并存放在磁盤中等待運行。 既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。 1． 低級調(diào)度的功能 低級調(diào)度用于決定就緒隊列中的哪個進程 (或內(nèi)核級線程 )應(yīng)獲得處理機 ， 然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作 。 第三章 處理機調(diào)度與死鎖 2． 進程調(diào)度中的三個基本機制 為了實現(xiàn)進程調(diào)度 ， 應(yīng)具有如下三個基本機制： (1) 排隊器 。 當(dāng)對處理機進行切換時，會發(fā)生 兩對 上下文切換 操作。 ??? 執(zhí)行某原語操作。 ? 缺點：難以滿足緊急任務(wù)的要求 —— 立即執(zhí)行 第三章 處理機調(diào)度與死鎖 2) 搶占 方式 (Preemptive Mode) ? 當(dāng)一個進程正在運行時，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程。為避免進程調(diào)度占用太多的 CPU時間，進程調(diào)度算法不宜太復(fù)雜。 第三章 處理機調(diào)度與死鎖 調(diào)度隊列模型和調(diào)度準(zhǔn)則 調(diào)度隊列模型 1． 僅有進程調(diào)度的調(diào)度隊列模型 （ 分時 、 實時 OS） 就 緒 隊 列阻 塞 隊 列進程調(diào)度C P U進程完成等待事件交互用戶事件出現(xiàn)時間片完第三章 處理機調(diào)度與死鎖 2． 具有高級和低級調(diào)度的調(diào)度隊列模型 （ 批處理 ） 就 緒 隊 列進程調(diào)度C P U進程完成等待事件 1作業(yè)調(diào)度事件 1 出現(xiàn)時間片完等待事件 2事件 2 出現(xiàn)??等待事件 n事件 n 出現(xiàn)后 備 隊 列? ?第三章 處理機調(diào)度與死鎖 3． 同時具有三級調(diào)度的調(diào)度隊列模型 當(dāng)在 OS中引入中級調(diào)度后，人們可把進程的就緒狀態(tài)分為 內(nèi)存就緒 (表示進程在內(nèi)存中就緒 )和 外存就緒 (進程在外存中就緒 )。 第三章 處理機調(diào)度與死鎖 圖 33 具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進程調(diào)度C P U就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章 處理機調(diào)度與死鎖 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1． 面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時間短 。 第三章 處理機調(diào)度與死鎖 (2) 響應(yīng)時間快。 第三章 處理機調(diào)度與死鎖 (3) 截止時間的保證 。 在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法時，都可遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能得到及時處理。 ? 吞吐量 ：指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù) 。 (3) 各類資源的平衡利用。 第三章 處理機調(diào)度與死鎖 ??? 設(shè)計調(diào)度算法時考慮的因素 ??? 應(yīng)與系統(tǒng)的整個設(shè)計目標(biāo)一致。 當(dāng)在作業(yè)調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。下表列出了 A、 B、 C、 D四個作業(yè)分別到達系統(tǒng)的時間、要求服務(wù)的時間、開始執(zhí)行的時間及各自的完成時間，并計算出各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。從每個進程的完成時間中減去其到達時間，即得到其周轉(zhuǎn)時間，進而可以算出每個進程的帶權(quán)周轉(zhuǎn)時間。而短進程優(yōu)先 (SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調(diào)度。 ? 作為作業(yè)調(diào)度算法（ 批處理 ） ? 作為進程調(diào)度算法（ 分時、實時 ） ? 用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。 第三章 處理機調(diào)度與死鎖 2) 搶占式優(yōu)先權(quán)調(diào)度算法 系統(tǒng)把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。 ? 進程對資源的要求 ? 用戶要求 ? 將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進程的優(yōu)先級。 ? 非線形改變優(yōu)先級規(guī)則 第三章 處理機調(diào)度與死鎖 3． 高響應(yīng)比優(yōu)先調(diào)度算法 （ HRN） 先來先服務(wù)和短作業(yè)優(yōu)先算法都有其片面性 ， 先來先服務(wù)調(diào)度算法只考慮作業(yè)的等待時間 ， 而忽視了作業(yè)的運行時間 ， 短作業(yè)優(yōu)先算法則相反 ， 只考慮了作業(yè)的運行時間 ， 而忽視了作業(yè)的等待時間 。 第三章 處理機調(diào)度與死鎖 由上式可以看出： (1) 如果作業(yè)的等待時間相同 ， 則要求服務(wù)的時間愈短 ，其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) 。 第三章 處理機調(diào)度與死鎖 ?這樣算法從 理論 上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶的估計的運行時間，并要作浮點運算（這是系統(tǒng)程序最忌諱的）浪費大量的計算時間，這是系統(tǒng)程序所不允許的。 若取時間片略大于一次典型的交互所需要的時間 ， 這樣可使大多數(shù)進程在一個時間片內(nèi)完成 。 第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。 第三章 處理機調(diào)度與死鎖 圖 37 多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至C P U至C P U至C P U至C P U( 時間片： S1＜ S2＜ S3)第三章 處理機調(diào)度與死鎖 ?? 多級反饋輪轉(zhuǎn)法 ?設(shè)置多個就緒隊列 ,每個隊列賦予不同地優(yōu)先級。 ?僅當(dāng)?shù)?i隊列空閑時，才調(diào)度第 i+1隊列。 第三章 處理機調(diào)度與死鎖 思考：如下調(diào)度用的進程狀態(tài)變遷圖，調(diào)度算法和調(diào)度效果如何？ 運行 低優(yōu)先就緒 高優(yōu)先就緒 等待 首先選擇100ms 其次選擇500ms 請求 I/O I/O完成 超時間片 第三章 處理機調(diào)度與死鎖 隊列結(jié)構(gòu) ? I/O等待隊列 —— 一個進程如果請求 I/O，則進入 I/O等待隊列。 第三章 處理機調(diào)度與死鎖 運行 低優(yōu)先就緒 高優(yōu)先就緒 因盤或帶I/O而等待 進程調(diào)度500ms 請求盤或帶 I/O I/O完成 超時間片 中優(yōu)先就緒 因終端I/O而等待 因頁面I/O而等待 進程調(diào)度100ms 進程調(diào)度100ms I/O完成 I/O完成 請求終端 I/O 缺頁中斷 調(diào)度算法、效果？ 第三章 處理機調(diào)度與死鎖 思考 ?若在操作系統(tǒng)的就緒進程隊列中等待運行的共有三個進程 P P P3，已知它們各自的運行時間為 a、 b、 c，且滿足關(guān)系 a b c。 (3) 處理時間。 2) 非搶占式優(yōu)先調(diào)度算法 獲得僅 為數(shù)秒至數(shù)百毫秒級的響應(yīng)時間 ， 因而可用于有一定要求的實時控制系統(tǒng)中 。該例中具有四個非周期任務(wù)，它們先后到達。 第三章 處理機調(diào)度與死鎖 圖 39 EDF算法用于非搶占調(diào)度的調(diào)度方式 1 3 4 2開始截止時間任務(wù)執(zhí)行任務(wù)到達1 2 3 41 3 4 2t到達 到達 到達 第三章 處理機調(diào)度與死鎖 2) 搶占式調(diào)度方式用于周期實時任務(wù) 圖 310示出了將最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例。 第三章 處理機調(diào)度與死鎖 圖 310 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例 A1 B1 A2 B1 A3 B