【正文】 第三章 處理機(jī)調(diào)度與 死鎖 主要內(nèi)容： ● 處理機(jī)的兩級調(diào)度 ● 作業(yè)調(diào)度 ● 進(jìn)程調(diào)度 ● 死鎖 ● 什么是死鎖 ● 預(yù)防死鎖。 ● 避免死鎖。 ● 檢測死鎖。 第一部分 處理機(jī)調(diào)度 主要內(nèi)容：兩級調(diào)度：作業(yè)調(diào)度和進(jìn)程調(diào)度的調(diào)度算法。 作業(yè)調(diào)度：從磁盤的眾多的作業(yè)中選擇作業(yè)進(jìn)入 內(nèi)存。 進(jìn)程調(diào)度：進(jìn)入系統(tǒng)中若干進(jìn)程如何爭奪 cpu的控制權(quán)。 167。 1. cpu的調(diào)度層級 作業(yè)調(diào)度：宏觀調(diào)度（用戶的觀點） 進(jìn)程調(diào)度：微觀調(diào)度（系統(tǒng)的觀點） 一，作業(yè)調(diào)度和進(jìn)程調(diào)度的任務(wù) (1) 從磁盤的后備作業(yè)中按一定的算法選擇作業(yè)進(jìn)入內(nèi)存 。 (2) 建立相應(yīng)的進(jìn)程于就緒狀態(tài) ,使它們有資格獲得 cpu的 控制權(quán) 。 (3) 當(dāng)作業(yè)執(zhí)行完成后 ,作善后處理工作 ,如 :撤銷 JCB,回收資源等。 （ 1）按一定的算法將 CPU分配某一就緒狀態(tài)的進(jìn)程，規(guī)定占用 CPU的時間，或測試優(yōu)先級； （ 2）當(dāng) CPU被進(jìn)程占用時，建立相應(yīng)的運(yùn)行環(huán)境，如：保護(hù)現(xiàn)場等。 二，兩級調(diào)度的關(guān)系 執(zhí)行 運(yùn)行 就緒 等待 后備 提交 完成 作業(yè)錄入：sploonig系統(tǒng) 作業(yè)調(diào)度 作業(yè)調(diào)度 進(jìn)程調(diào)度 注意： 作業(yè)的執(zhí)行狀態(tài)就是進(jìn)程處于運(yùn)行 ,就緒 ,等待等狀態(tài)之中。 167。 2 作業(yè)調(diào)度 一 . 作業(yè)的狀態(tài)及其轉(zhuǎn)換 4種狀態(tài) ①提交狀態(tài)：一個作業(yè)被提交給機(jī)房后或用戶通過終端設(shè)備向計算機(jī)中輸入其作業(yè)時所處的狀況。 ②后備狀態(tài)：作業(yè)的全部信息都已輸入，并存放在磁盤中等待運(yùn)行。 ③運(yùn)行狀態(tài)：作業(yè)被調(diào)度程序選中而被送入主存中投入運(yùn)行。 ④完成狀態(tài)：作業(yè)完成其全部任務(wù)，釋放其所占用的全部資源，準(zhǔn)備退出系統(tǒng)。 提交狀態(tài) → 后備狀態(tài) → 運(yùn)行狀態(tài) → 完成狀態(tài) 二 . 作業(yè)調(diào)度的功能 ①記錄進(jìn)入系統(tǒng)的各作業(yè)的情況。 建立作業(yè)控制塊 jcb (job control block)。作業(yè)控制塊記錄了每個作業(yè)類型、狀態(tài)、資源請求及分配情況 。 ②按調(diào)度算法從后備作業(yè)中挑選出若干作業(yè)投入運(yùn)行。 ③為選中的作業(yè)分配主存和外設(shè)資源。 為選中的作業(yè)分配所需要的系統(tǒng)資源。 ④作業(yè)結(jié)束后作善后處理工作。 收回該作業(yè)所占用的全部資源，撤消作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進(jìn)程。 三. 作業(yè)控制塊 (JCB) 每個作業(yè)進(jìn)入系統(tǒng)時由系統(tǒng)為其建立一個作業(yè)控制塊JCB （ Job Control Block)， 它是存放作業(yè)控制和管理信息的數(shù)據(jù)結(jié)構(gòu) ， 主要信息見右圖 。 四. 調(diào)度性能的衡量 1. 調(diào)度算法設(shè)計時考慮的因素 ①與整體目標(biāo)一致 ● 批量系統(tǒng) :盡量增加系統(tǒng)作業(yè)的平均吞吐量 ,提高系統(tǒng)的效率 . ● 分時系統(tǒng) :保證用戶能忍受時間 . ● 實時系統(tǒng) :保證及時響應(yīng)和處理 . 資源負(fù)載均勻 ,作業(yè)應(yīng)能運(yùn)行 ,特殊要求等。 ② 考慮的調(diào)度原則 ● 公平性 :對用戶要公平和滿意 ,不能無故地拖延作業(yè)的運(yùn)行 . ● 平衡 資源 的使用 :將 I/O繁忙的作業(yè)和 CPU繁忙的作業(yè)搭配起來 ,盡量使資源都處于忙碌 . ● 較大的流量 :單位時間內(nèi) ,盡可多的為多個作業(yè)服務(wù) .保證系統(tǒng)的吞吐能力 . 2. 調(diào)度性能的衡量 通常采用 平均周轉(zhuǎn)時間 和 平均帶權(quán)周轉(zhuǎn)時間 衡量 . (1)周轉(zhuǎn)時間和平均周轉(zhuǎn)時間 作業(yè)的周轉(zhuǎn)時間 ti：一個作業(yè)在系統(tǒng)中停留的時間 . ti = tcitsi tci:作業(yè)完成時間 tsi:作業(yè)進(jìn)入輸入井時間 n個作業(yè)的 平均周轉(zhuǎn)時間 t: t越小調(diào)度性能越好 。 系統(tǒng) 吞吐量大 , 資源利用率越高 . (2)帶權(quán)周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間 帶權(quán) 周轉(zhuǎn)時間 wi:周轉(zhuǎn)時間 /運(yùn)行時間 作業(yè)在系統(tǒng)中相對等待時間 注： 平均周轉(zhuǎn)時間：用來衡量不同的調(diào)度算法對同一作業(yè)流的調(diào)度性能。 平均帶權(quán)周轉(zhuǎn)時間：用來衡量某種調(diào)度算法對不同作業(yè)流的調(diào)度性能。 五 . 作業(yè)調(diào)度算法 ●先來先服務(wù)調(diào)度算法 ●短作業(yè)優(yōu)先調(diào)度算法 ●響應(yīng)比高者優(yōu)先調(diào)度算法 ●優(yōu)先數(shù)調(diào)度算法 ●均衡調(diào)度算法 （ FCFS） 按作業(yè)到達(dá)輸入井的先后次序，且滿足資源要求挑選作業(yè)進(jìn)行的調(diào)度。 例子 在一個多道程序系統(tǒng)中，有作業(yè) A,B,C,D,E；用戶使用的空間100KB。各作業(yè)進(jìn)入輸入井的時間和要求運(yùn)行的時間如下表： 根據(jù)達(dá)到輸入井的先后次序和滿足資源要求條件 ,4個作業(yè)的調(diào)度次序： A→B →D →C →E 作業(yè) 進(jìn)入輸入井的 時間（小時） 要求運(yùn)行時間（分鐘） 主存量要求 A 42 15k B 30 60k C 24 50k D 24 10k E 12 20k 先來先服務(wù)算法（ ＝ 6分鐘） 作業(yè) 進(jìn)入輸 入井時間 (小時 ) 執(zhí)行時間 （分鐘） 開始時間(小時 ) 完成時間 (小時 ) 周轉(zhuǎn)時間 (小時 ) 帶權(quán)周轉(zhuǎn)時間 (小時 ) A 42（ ） 1 B 30（ ） 1 2 C 24（ ） 4 D 24（ ） E 12（ ） 8 平均周轉(zhuǎn)時間 t = (+1+++)/5=(小時 ) 平均帶權(quán)周轉(zhuǎn)時間 w = (1+2+4++8)/5=(小時 ) 算法的優(yōu)缺點： 優(yōu)點：實現(xiàn)簡單；算法具有一定的公平性。 缺點：當(dāng)計算時間長的作業(yè)先達(dá)到而被選中時，可能使計算時間短的作業(yè)長期等待， 則周轉(zhuǎn)時間長，平均周轉(zhuǎn)時間增大，降低了系統(tǒng)的 吞吐能力。 入內(nèi)存時間（小時） 每次總是選擇滿足資源要求的作業(yè)優(yōu)先調(diào)入內(nèi)存，然后挑選要求運(yùn)行時間最短的作業(yè)投入運(yùn)行。 上例：短作業(yè)優(yōu)先調(diào)度的次序： A→B →D →E →C 作業(yè) 入主存時間 (小時 ) 執(zhí)行時間 （分鐘） 開始時間(小時 ) 完成時間(小時 ) 周轉(zhuǎn)時間 (小時 ) 帶權(quán)周轉(zhuǎn)時間 (小時 ) A 42（ ） 1 B 30（ ） 1 2 C 24（ ） D 24（ ） E 12（ ） 6 入輸入井時間 (小時 ) 平均周轉(zhuǎn)時間 t = (+1+++)/5=(小時 ) 平均帶權(quán)周轉(zhuǎn)時間 w = (1+2+++6)/5=(小時 )