【正文】 時間 帶權周 轉時間 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 第三章 處理機調度與死鎖 從表上可以看出，其中短作業(yè) C的帶權周轉時間競高達100，這是不能容忍的；而長作業(yè) D的帶權周轉時間僅為 。 第三章 處理機調度與死鎖 FCFS算法比較有利于長作業(yè) (進程 )，而不利于短作業(yè)(進程 )。在進程調度中采用 FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。 ? 大多數系統(tǒng)都根據用戶的需要而采用兼顧某些目標的簡單調度算法 調 度 算 法 第三章 處理機調度與死鎖 調 度 算 法 先來先服務和短作業(yè) (進程 )優(yōu)先調度算法 1． 先來先服務調度算法 先來先服務 (FCFS First e first served )調度算法是一種最簡單的調度算法，該算法既可用于作業(yè)調度，也可用于進程調度。 ??? 系統(tǒng)資源的均衡使用。但對于微型機和某些實時系統(tǒng)而言，準則(2)(3)并不重要。 在大、中型系統(tǒng)中，不僅要使處理機的利用率高，而且還應能有效地利用其它各類資源，如內存、外存和 I/O設備等。 第三章 處理機調度與死鎖 (2) 處理機利用率好。 ? 與批處理作業(yè)的平均長度具有密切關系 。 這是用于評價 批處理系統(tǒng)性能 的另一個重要指標 ， 因而是選擇批處理作業(yè)調度的重要準則 。在要求較嚴格的場合，往往還須選擇搶占式調度方式，才能保證緊急作業(yè)得到及時處理。 (4) 優(yōu)先權準則。 這是評價 實時系統(tǒng) 性能的重要指標 ， 因而是選擇實時調度算法的重要準則 。 ?包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的響應信息回送到終端顯示器的時間。 常把響應時間的長短用來評價 分時系統(tǒng) 的性能，這是選擇分時系統(tǒng)中進程調度算法的重要準則之一。 ? 平均周轉時間 ?帶權周轉時間：作業(yè)的周轉時間 T與系統(tǒng)為它提供服務的時間 Ts之比 ， 即 W = T/Ts ??????? ??niiTnT11第三章 處理機調度與死鎖 ?平均帶權周轉時間： ??????? ??niiTTnW1 s1 一般，總是 T或 W小的作業(yè)被選中，因為這樣資源利用率較高，用戶也滿意。 評價 批處理系統(tǒng) 的性能 、 選擇作業(yè)調度方式與算法的重要準則之一 。圖 33示出了具有三級調度的調度隊列模型。類似地，也可把阻塞狀態(tài)進一步分成 內存阻塞 和 外存阻塞 兩種狀態(tài)。中級調度的運行頻率基本上 介于 上述兩種調度之間，因此把它稱為中程調度。 作業(yè)調度往往是發(fā)生在一個 (批 )作業(yè)運行完畢，退出系統(tǒng)，而需要重新調入一個 (批 )作業(yè)進入內存時，故作業(yè)調度的周期較長，大約 幾分鐘（幾小時 ）一次，因此把它稱為長程調度。 ? 原則： （ 1） 優(yōu)先權 （ 2） 短作業(yè) （ 進程 ） 優(yōu)先 （ 3）時間片 ?選擇性剝奪調度 第三章 處理機調度與死鎖 在上述三種調度中，進程調度的運行頻率最高，在分時系統(tǒng)中通常是 10～ 100 ms便進行一次進程調度，因此把它稱為短程調度。 ? 優(yōu)點：公平，能滿足對響應時間有著較嚴格要求的實時任務的需求。 ? 優(yōu)點：實現簡單，開銷小，適用于大多數的批處理系統(tǒng)環(huán)境。 ??? 在可剝奪調度方式中，一個具有更高優(yōu)先數的進程進入就緒隊列。 ??? 運行中的進程提出 I/O 請求。在第一對上下文切換時，操作系統(tǒng)將保存當前進程的上下文，而裝入分派程序的上下文，以便分派程序運行；在第二對上下文切換時，將移出分派程序，而把新選進程的 CPU現場信息裝入到處理機的各個相應寄存器中。 (3) 上下文切換機制 。 就緒進程按照一定的方式排成一個或多個隊列 (2) 分派器 (分派程序 )。 (3) 把處理器分配給進程。 第三章 處理機調度與死鎖 低級調度的主要功能如下： (1) 保存處理機的現場信息 。 進程調度是最基本的一種調度 ， 在多道批處理 、 分時和實時三種類型的 OS中 ， 都必須配置這級調度 。在每次執(zhí)行作業(yè)調度時，都須做出以下兩個決定。 第三章 處理機調度與死鎖 提交 后備 運行 就緒 等待 完成 作業(yè)調度 作業(yè)調度 作業(yè)錄入 作業(yè)的狀態(tài)及轉換 第三章 處理機調度與死鎖 3．作業(yè)調度算法的選擇 用戶：周轉時間少最好 系統(tǒng)：作業(yè)的平均周轉時間盡可能少，有利于提高 CPU 的利用率和系統(tǒng)的吞吐量。 ③ 運行狀態(tài) ：作業(yè)被調度程序選中而被送入主存中投入運行。 第三章 處理機調度與死鎖 JCB主要信息 第三章 處理機調度與死鎖 作業(yè)的狀態(tài)及其轉換 ① 提交狀態(tài) ：一個作業(yè)被提交給機房后或用戶通過終端設備向計算機中輸入其作業(yè)時所處的狀況。 ?通常應包含的內容有：作業(yè)標識、用戶名稱、用戶帳戶、作業(yè)類型 (CPU 繁忙型、 I/O 繁忙型、批量型、終端型 )、作業(yè)狀態(tài)、調度信息 (優(yōu)先級、作業(yè)已運行時間 )、資源需求 (預計運行時間、要求內存大小、要求 I/O設備的類型和數量等 )、進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。 若干個作業(yè)進入系統(tǒng)后 ， 被依次存放在外存上 ， 形成輸入的作業(yè)流；在操作系統(tǒng)的控制下 ， 逐個作業(yè)進行處理 ， 形成處理作業(yè)流 。 通常 ， 在作業(yè)運行期間 ， 每個作業(yè)都必須經過若干個相對獨立 ， 又相互關聯(lián)的順序加工步驟才能得到結果 ， 我們把其中的每一個加工步驟稱為一個作業(yè)步 ， 各作業(yè)步之間存在著相互聯(lián)系 ， 往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入 。在批處理系統(tǒng)中，以作業(yè)為基本單位從外存調入內存的。 目的：提高內存的利用率和系統(tǒng)吞吐量。因此，有時也把作業(yè)調度稱為接納調度 (Admission Scheduling)。第三章 處理機調度與死鎖 第三章 處理機調度與死鎖 處理機調度的層次 調度隊列模型和調度準則 調度算法 實時調度 產生死鎖的原因和必要條件 預防死鎖的方法 死鎖的檢測與解除 第三章 處理機調度與死鎖 ?處理機是計算機系統(tǒng)中的重要資源 ?處理機調度算法對整個計算機系統(tǒng)的綜合性能指標有重要影響 ?不同的 OS，處理機管理的策略不同 ?可把處理機調度分成三個層次： ? 高級調度 ? 中級調度 ? 低級調度 處理機調度的層次 第三章 處理機調度與死鎖 處理機調度的層次 ?高級調度（ 宏觀調度、作業(yè)調度、長程調度 ） 主要功能：根據作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調入內存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。 第三章 處理機調度與死鎖 ?低 級調度 （ 微觀調度、進程調度、短程調度 ） 功能：決 定就緒隊列中的哪個進程 (或內核級線程 )應獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作 . ?中 級調度 （中程調度、交換調度） 按照給定的原則和策略，將處于外存交換區(qū)中的就緒狀態(tài)或等待狀態(tài)的進程調入內存，或把處于內存就緒狀態(tài)或內存等待狀態(tài)的進程交換到外存交換區(qū)中。 處理機調度的層次 第三章 處理機調度與死鎖 處理機調度的層次 高級調度（只針對批處理系統(tǒng)） 1． 作業(yè)和作業(yè)步 (1) 作業(yè) (Job)=程序 +數據 +作業(yè)說明書 系統(tǒng)根據說明書來對程序的運行進行控制。 第三章 處理機調度與死鎖 (2) 作業(yè)步 (Job Step)。 ① 編譯 ② 連結裝配 ③ 運行 (3) 作業(yè)流 。 第三章 處理機調度與死鎖 2． 作業(yè)控制塊 JCB(Job Control Block) ?是作業(yè)在系統(tǒng)中存在的標志 ?保存了系統(tǒng)對作業(yè)進行管理和調度所需的全部信息。 ?作業(yè)的狀態(tài) 作業(yè)從輸入到完成要經歷 提交，收容，執(zhí)行，完成 四個階段。 ② 后備狀態(tài) ：作業(yè)的全部信息都已輸入，并存放在磁盤中等待運行。 ④ 完成狀態(tài) ：作業(yè)完成其全部運行，釋放其所占用的全部資源，準備退出系統(tǒng)。 既應考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。 1) 決定接納多少個作業(yè)：多道程序度的確定應根據系統(tǒng)的規(guī)模和運行速度等情況做適當的 折衷 2) 決定接納哪些作業(yè)：作業(yè)調度算法 第三章 處理機調度與死鎖 低級調度 調度的對象是進程 (或內核級線程 )。 1． 低級調度的功能 低級調度用于決定就緒隊列中的哪個進程 (或內核級線程 )應獲得處理機 ， 然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作 。 (2) 按某種算法選取進程 。 第三章 處理機調度與死鎖 2． 進程調度中的三個基本機制 為了實現進程調度 ， 應具有如下三個基本機制： (1) 排隊器 。從就緒隊列中取出選中進程，然后進行上下文切換，分配處理機。 當對處理機進行切換時，會發(fā)生 兩對 上下文切換 操作。 耗時？怎么辦？ P86 第三章 處理機調度與死鎖 ? 進程調度時機 ??? 正在執(zhí)行的進程執(zhí)行完畢。 ??? 執(zhí)行某原語操作。 ??? 在分時系統(tǒng)中，分配給該進程的時間片已用完 第三章 處理機調度與死鎖 3． 進程調度方式 （ 兩種 ） 1) 非搶占方式 (Nonpreemptive Mode) ? 分派程序一旦把處理機分配給某進程后便讓它一直運行下去，直到進程完成或發(fā)生某事件而阻塞時，才把處理機分配給另一個進程。 ? 缺點：難以滿足緊急任務的要求 —— 立即執(zhí)行 第三章 處理機調度與死鎖 2) 搶占 方式 (Preemptive Mode) ? 當一個進程正在運行時，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程。 ? 缺點：開銷較大 。為避免進程調度占用太多的 CPU時間，進程調度算法不宜太復雜。由于其運行頻率較低，故允許作業(yè)調度算法花費較多的時間。 第三章 處理機調度與死鎖 調度隊列模型和調度準則 調度隊列模型 1． 僅有進程調度的調度隊列模型 （ 分時 、 實時 OS） 就 緒 隊 列阻 塞 隊 列進程調度C P U進程完成等待事件交互用戶事件出現時間片完第三章 處理機調度與死鎖 2． 具有高級和低級調度的調度隊列模型 （ 批處理 ） 就 緒 隊 列進程調度C P U進程完成等待事件 1作業(yè)調度事件 1 出現時間片完等待事件 2事件 2 出現??等待事件 n事件 n 出現后 備 隊 列? ?第三章 處理機調度與死鎖 3． 同時具有三級調度的調度隊列模型 當在 OS中引入中級調度后，人們可把進程的就緒狀態(tài)分為 內存就緒 (表示進程在內存中就緒 )和 外存就緒 (進程在外存中就緒 )。在調出操作的作用下，可使進程狀態(tài)由內存就緒轉為外存就緒，由內存阻塞轉為外存阻塞；在中級調度的作用下，又可使外存就緒轉為內存就緒。 第三章 處理機調度與死鎖 圖 33 具有三級調度時的調度隊列模型 就緒隊列進程調度C P U就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現事件出現第三章 處理機調度與死鎖 選擇調度方式和調度算法的若干準則 1． 面向用戶的準則 (1) 周轉時間短 。 ? 周轉時間 ：從作業(yè)被提交給系統(tǒng)開始 ， 到作業(yè)完成為止的這段時間間隔 。 第三章 處理機調度與死鎖 (2) 響應時間快。 ?響應時間 ：從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產生響應為止的時間，或者說，直到屏幕上顯示出結果為止的一段時間間隔。 第三章 處理機調度與死鎖 (3) 截止時間的保證 。 截止時間 ：是指某任務必須開始執(zhí)行的最遲時間 ， 或必須完成的最遲時間 。 在批處理、分