【文章內(nèi)容簡介】 運(yùn)行 內(nèi)存 二、 處理機(jī)調(diào)度的分層 運(yùn)行 就緒 等待 外存 就緒態(tài)的進(jìn)程有多個， CPU分配 給誰？ ？ ★ ？ 53 因此， 處理機(jī)的調(diào)度可分為二層 (或三層 ) (1) 宏觀調(diào)度 對象為作業(yè)，故又稱為 作業(yè)調(diào)度 任務(wù)： 在已進(jìn)入系統(tǒng)的作業(yè)中，按某種原則 挑選一個、或一批作業(yè)到內(nèi)存執(zhí)行 完成的工作： ? 為選中 作業(yè)的執(zhí)行程序 建立進(jìn)程 ? 為其分配內(nèi)存 ? 分配其他需 靜態(tài)分配 的資源 ★ 54 (2) 微觀調(diào)度 對象為進(jìn)程，故又稱為 進(jìn)程調(diào)度 任務(wù)： 確定 哪個進(jìn)程、在什么時候 獲得處理機(jī)，以及 使用多長時間 完成的工作： ? 選擇一個 在內(nèi)存就緒 的進(jìn)程 將其狀態(tài)改為運(yùn)行 ? 若分時，給出運(yùn)行的時間片 ? 恢復(fù)該進(jìn)程的現(xiàn)場 ★ 55 （ 3）中級調(diào)度 用于某些分時系統(tǒng) (如 Unix)中 對象為進(jìn)程 任務(wù)： 確定哪些進(jìn)程被允許 參與 處理機(jī)的競爭 短期內(nèi) (如進(jìn)程太多時 )調(diào)整系統(tǒng)內(nèi)存的負(fù)荷 完成的工作： ★ 56 ? 換出： 在內(nèi)存中最不可能得到 CPU的進(jìn)程 首先 : 等待態(tài) 的就緒進(jìn)程 其次： 優(yōu)先級低 且 駐 留內(nèi)存時間長 的就緒進(jìn)程 ?換入： 在進(jìn)程調(diào)度程序挑選運(yùn)行進(jìn)程前 換入在外存 駐 留時間較長 的就緒進(jìn)程 說明： 對處理機(jī)的調(diào)度，不同的操作系統(tǒng) 往往采用不同的實現(xiàn)方式 ★ 57 6. 2 作業(yè)調(diào)度 一個 作業(yè)，是一個用戶的一次上機(jī)過程。因此 (1) 最基本的作業(yè)：執(zhí)行 一個可執(zhí)行程序 (2) 復(fù)雜的作業(yè)：執(zhí)行 一組 可執(zhí)行程序： 如編譯、連接、執(zhí)行等 作業(yè)的表現(xiàn)形式： (1) 批處理：用戶提出的 作業(yè)申請 完成內(nèi)容：在 操作說明書 中所包含的所有 執(zhí)行語句 (2) 分時系統(tǒng)：用戶登錄后的活動 (注銷后結(jié)束 ) 完成內(nèi)容：通過終端輸入的一組命令 (可執(zhí)行的程序 )★ 58 二、 作業(yè)控制塊 操作系統(tǒng)對作業(yè)進(jìn)行管理的數(shù)據(jù)結(jié)構(gòu)，稱為作業(yè)控制塊 (JCB)， 它是一個作業(yè)存在的標(biāo)志。 JCB的主要內(nèi)容包括： ? 作 業(yè) 名 ? 對 資源的要求 估計執(zhí)行時間 最遲完成時間 要求的主存量 要求外設(shè)的類型及臺數(shù) 要求文件量和輸出量 ★ 59 ? 資 源 使 用 情況 進(jìn)入系統(tǒng)的時間 開始執(zhí)行的時間 已執(zhí)行的時間 程序在主存的地址 占有的外部設(shè)備 ? 狀 態(tài) ? 優(yōu) 先 級 ? 作業(yè)類型 (如：多 CPU、多 I\O、或均衡等 ) ? 控制方式 (如脫機(jī)、 聯(lián)機(jī) ) ★ 60 (1)設(shè) 作業(yè) i 的周轉(zhuǎn)時間為 ti ，則 ti = 完成時間－提交時間 = tci – tsi 或： ti = 運(yùn)行時間＋等待時間 ??niti1n1t = ★ 四、 作業(yè)調(diào)度性能的衡量 (2)平均周轉(zhuǎn)時間 1. 周轉(zhuǎn)時間 從作業(yè)提交給系統(tǒng)，到完成所需的時間 意義： 描述了 作業(yè) i 在系統(tǒng)中 停留時間 的長短 61 例： 作業(yè) 運(yùn)行時間 等待時間 周轉(zhuǎn)時間 (分鐘 ) 1 5 25 30 2 20 20 40 調(diào)度算法 對哪個作業(yè)有利呢？ (3) 如何用于評價 對用戶： 周轉(zhuǎn)時間越小越好 (更方便 ) 對系統(tǒng)： 平均周轉(zhuǎn)時間越小越好 (吞吐量大、 利用 率高 ) 原因？ 因為 周轉(zhuǎn)時間 中包含了 運(yùn)行時間 ，使評價出現(xiàn)誤差 平均周轉(zhuǎn)時間 同樣 也有類似的問題 如何衡量更準(zhǔn)確呢？ ★ 10 15 問題： 不夠準(zhǔn)確 62 2. 帶權(quán)周轉(zhuǎn)時間 (1) 帶權(quán)周轉(zhuǎn)時間，指： 一個作業(yè)的 周轉(zhuǎn)時間 與其 運(yùn)行時間 的比值 wi = ？ (2) 平均帶權(quán)周轉(zhuǎn)時間 t = 精確度： 二者都高于周轉(zhuǎn)時間、平均周轉(zhuǎn)時間 ??niwi1n1周轉(zhuǎn)時間 運(yùn)行時間 等待時間 運(yùn)行時間 3. 其他的衡量方法 可用 CPU利用率 、或 系統(tǒng)吞吐量 直接衡量 (無 滿意度 )★ 意義： 說明 作業(yè) i 在系統(tǒng)中的 相對等待時間 = 1 + 63 五、 作業(yè)調(diào)度算法 1. 先來先服務(wù)調(diào)度算法 (FCFS) 特點： 簡單，易實現(xiàn) 1 3 5 1 2 3 4 平均周轉(zhuǎn)時間 t = 0. 95 平均帶權(quán)周轉(zhuǎn)時間 w = 2. 8 ★ 提交 執(zhí)行 開始 完成 周轉(zhuǎn) 帶權(quán)周轉(zhuǎn) 作業(yè) 時間 時間 時間 時間 時間 時間 例：求周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間 (單位： 十進(jìn)制小時 ) (4) 評價： 性能較差。 原因： 當(dāng) 短作業(yè)排在長作業(yè)后面 時，由于 等待時間變長 (而運(yùn)行時間不變 )，造成： 平均 周轉(zhuǎn)時間、 平均 帶權(quán)周轉(zhuǎn)時間變長 短作業(yè)等待時間 長作業(yè)等待 ★ 例： 運(yùn)行時間 周轉(zhuǎn)時間 而且短作業(yè)的 相對等待時間 較長， 不滿意 改進(jìn)： 短作業(yè)排在長作業(yè)前面 2. 短作業(yè)優(yōu)先調(diào)度算法 (1) 策略 按作業(yè) 運(yùn)行的時間 長短進(jìn)行調(diào)度 (2) 優(yōu)點 易實現(xiàn) 系統(tǒng)吞吐量高 (3) 缺點 只照顧短作業(yè) 而沒有考慮長作業(yè)的利益 ★ 66 例：求周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間 提交 執(zhí)行 開始 完成 周轉(zhuǎn) 帶權(quán)周轉(zhuǎn) 作業(yè) 時間 時間 時間 時間 時間 時間 1 問題： 長作業(yè)可能會餓死。如何解決呢？ 希望： ★ 平均周轉(zhuǎn)時間 t =0 . 825 平均帶權(quán)周轉(zhuǎn)時間 w = 2 . 5 5 1 2 3 4 3. 相應(yīng)比高 (帶權(quán)周轉(zhuǎn)時間長 )者優(yōu)先調(diào)度算法 相應(yīng)比 ＝ 等待時間＋運(yùn)行時間 運(yùn)行時間 ＝ 1＋ 等待時間 運(yùn)行時間 調(diào)度策略： 既 短作業(yè)優(yōu)先 ，以提高效率 又適當(dāng)考慮長作業(yè) (一個原則 ) 相應(yīng)比 ＝ 1＋ K＋等待時間 運(yùn)行時間 4. 其他的優(yōu)先數(shù)調(diào)度算法，如： 優(yōu)先數(shù)＝ (等待時間分 )2－執(zhí)行時間 (秒 )－ 16*輸出行 思考： 上述二種策略，用隊列 排序 是否有意義？ ★ 改進(jìn)： 思考： 上述公式中，調(diào)度策略是否得到 完整的實現(xiàn) ？ 其實質(zhì)是 長作業(yè) 優(yōu)先、還是 短作業(yè) 優(yōu)先？ 如第二種調(diào)度策略中，有二個作業(yè) 按優(yōu)先數(shù)當(dāng)前排序如下： （ 42－ 10） （ 52－ 20） 但 1分鐘后，按優(yōu)先數(shù)排序變?yōu)? ： （ 62－ 20） （ 52－ 10） ★ 5. 均衡調(diào)度 目的： 使系統(tǒng)中的所有資源都保持忙碌 以達(dá)到 負(fù)載均衡 ，提高系統(tǒng)的資源利用率 適用范圍： 批處理中的作業(yè)調(diào)度 方法： (1) 將作業(yè)按對 CPU的使用量進(jìn)行分類： 多 CPU的 (計算量大 ) 多 I/O的 (輸入、輸出量大 ) 均衡的 (2) 將各類作業(yè)均衡搭配起來進(jìn)行調(diào)度 ★ 70 6. 3 進(jìn)程調(diào)度 一 . 進(jìn)程 調(diào)度 、及 CPU的 分派 1. 進(jìn)程調(diào)度 按一定的策略，在就緒狀態(tài)的進(jìn)程中 決定處理機(jī)分配的先后次序 (通常是形成一個 有序的就緒隊列 ) ★ 71 二 . 進(jìn)程調(diào)度的功能 1. 記錄進(jìn)程的有關(guān)情況和狀態(tài)特征 (在 PCB中 ) 2. 制定調(diào)度策略 ? 優(yōu)先調(diào)度原則： 就緒隊列按進(jìn)程 優(yōu)先級高低 排序 ? 先來先服務(wù)原則： 就緒隊列按進(jìn)程到來的 先后次序 (或等待時間的長短 )排序 3. 實施處理機(jī)的分配和回收 ★ 72 三 . 進(jìn)程調(diào)度的方式 指處理機(jī) 是否可剝奪 可從 廣義 (如分時 )或 狹義 的角度討論 狹義的 是否可剝奪 是指： 采用 優(yōu)先級 調(diào)度； 一個進(jìn)程正在處理機(jī)上運(yùn)行； 若出現(xiàn) 優(yōu)先級更高 的的就緒進(jìn)程： 系統(tǒng)是否 強(qiáng)行收回 運(yùn)行進(jìn)程的處理機(jī) ★ 73 １ . 非剝奪方式 讓執(zhí)行進(jìn)程繼續(xù)執(zhí)行，直到 放棄 CPU 后 才把處理機(jī) 分配 給優(yōu)先級更高的進(jìn)程 即：只在分配 CPU時，才考慮優(yōu)先級 ２ . 剝奪方式 立即把 CPU分配給優(yōu)先級更高的進(jìn)程 即：總是 優(yōu)先級最高 的進(jìn)程占有 CPU。 問題： 二者都有片面性 解決： 采取 有條件 的剝奪，怎么表述呢？ ★ 74 3. 選擇可搶占策略 每個進(jìn)程給出一對標(biāo)志 (U， V) 根據(jù) 高優(yōu)先就緒進(jìn)程 和 運(yùn)行進(jìn)程 二者的標(biāo)志，決定是否進(jìn)行搶奪： U=1： 表示 可搶奪 運(yùn)行進(jìn)程的 CPU U=0：表示不可搶奪運(yùn)行進(jìn)程的 CPU V=1： 表示 (運(yùn)行進(jìn)程 )允許被其他進(jìn)程搶奪 V=0：表示不允許被其他進(jìn)程搶奪 ★ 75 進(jìn)一步的問題： (1) 一個系統(tǒng)的進(jìn)程 調(diào)度策略 如何來描述？ (2) 與進(jìn)程調(diào)度有關(guān)的各個模塊 在什么條件下 被激活 執(zhí)行？ (3) 這些模塊之間有什么 聯(lián)系 呢？ ★ 76 四 . 調(diào)度用的進(jìn)程狀態(tài)變遷圖 例：某系統(tǒng)的進(jìn)程狀態(tài)變遷圖如下所示 運(yùn)行 500ms 100ms 因 I∕O 而等待 高優(yōu)先 就緒 低優(yōu)先 就緒 進(jìn)程 調(diào)度 進(jìn)程調(diào)度 時間片到 請求 I/O I/O完成 (一 ) 通過進(jìn)程狀態(tài)變遷圖 可反映系統(tǒng) 進(jìn)程調(diào)度 的各種特征 ★ 77 1. 隊列的結(jié)構(gòu)