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