【正文】 0時(shí)， A3又到達(dá)，但 B1的截止時(shí)間要比 A3早，仍應(yīng)該讓 B1繼續(xù)執(zhí)行直到完成（ t=45），然后再調(diào)度 A3執(zhí)行； 在 t=55時(shí)， A3完成，又調(diào)度 B2執(zhí)行。處理機(jī)調(diào)度與死鎖 Operating System 2 2022/2/16 教學(xué)重點(diǎn) ? 處理機(jī)調(diào)度的基本概念 ? 調(diào)度算法 ? 多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度方式 ? 死鎖產(chǎn)生的原因、預(yù)防辦法及檢測與解決方法 ? 深入理解銀行家算法，掌握其用法 3 2022/2/16 處理機(jī)調(diào)度的基本概念 處理機(jī)調(diào)度層次 1 調(diào)度隊(duì)列模型 2 選擇調(diào)度算法的準(zhǔn)則 3 4 2022/2/16 處理機(jī)調(diào)度的基本概念 ? 不同 OS中的各類型作業(yè)都會經(jīng)歷 進(jìn)程調(diào)度（低級調(diào)度）過程，某些系統(tǒng)中還有 中級調(diào)度 和 作業(yè)調(diào)度 （高級調(diào)度）過程，每個(gè)級別的調(diào)度過程都可以根據(jù)具體需求選擇不同的調(diào)度算法 5 2022/2/16 作業(yè) ? 定義 ? 除通常的程序和數(shù)據(jù)外，還配有作業(yè)說明書，以便系統(tǒng)根據(jù)該說明書控制程序運(yùn)行。 ? 作業(yè)步 ? 作業(yè)中相對獨(dú)立又相互關(guān)聯(lián)的順序加工步驟，前一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步的輸入 ? 編譯 連接 運(yùn)行 ? 作業(yè)流：排隊(duì)的作業(yè)形成 6 2022/2/16 作業(yè) ? 作業(yè)控制塊 JCB ? 系統(tǒng)感知作業(yè)的標(biāo)志，包含作業(yè) 描述信息和控制信息 ? 作業(yè)進(jìn)入系統(tǒng)時(shí)由系統(tǒng)為其建立 JCB，并插入相應(yīng)類型后備隊(duì)列 作業(yè)調(diào)度程序依照特定算法調(diào)度作業(yè)進(jìn)入內(nèi)存 作業(yè)運(yùn)行期間系統(tǒng)按照 JCB控制作業(yè) 作業(yè)執(zhí)行結(jié)束進(jìn)入完成狀態(tài)，系統(tǒng)回收資源和撤銷 JCB 7 2022/2/16 調(diào)度類型 ? 一個(gè)批處理作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行完成可能經(jīng)歷的調(diào)度過程有： ? 高級調(diào)度 ? 低級調(diào)度 ? 中級調(diào)度 8 2022/2/16 高級調(diào)度 ? 又稱為作業(yè)調(diào)度、長程調(diào)度或接納調(diào)度 用于決定把外存上后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為其建立進(jìn)程、分配必要資源，然后將新創(chuàng)建的進(jìn)程加入就緒隊(duì)列等待執(zhí)行 ? 在響應(yīng)速度要求較高的實(shí)時(shí)系統(tǒng)和分時(shí)系統(tǒng)中，不需要 使用高級調(diào)度 ? 執(zhí)行作業(yè)調(diào)度時(shí)需要考慮的問題 ? 接納 多少個(gè) 作業(yè)：根據(jù)系統(tǒng)規(guī)模和運(yùn)行速度等情況決定多道程序度 ? 接納 哪些 作業(yè)：根據(jù)采用的調(diào)度算法不同選擇合適的作業(yè)進(jìn)入內(nèi)存 9 2022/2/16 低級調(diào)度 ? 又稱進(jìn)程調(diào)度或短程調(diào)度 用于從就緒隊(duì)列中選擇進(jìn)程（或內(nèi)核級線程）使之 獲得處理機(jī) ，接著由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作 在批處理 OS、分時(shí) OS和實(shí)時(shí) OS中都必須配備進(jìn)程調(diào)度，是 最基本 的調(diào)度層次 10 2022/2/16 低級調(diào)度 ? 進(jìn)程調(diào)度功能 ? 保存處理機(jī)現(xiàn)場信息 ? 依照調(diào)度算法選擇進(jìn)程 ? 把處理器分配給進(jìn)程 ? 進(jìn)程調(diào)度的保障機(jī)制 ? 排隊(duì)器 ? 分派器 ? 上下文切換機(jī)制：發(fā)生在當(dāng)前進(jìn)程與分派器、分派器與新進(jìn)程間的兩次切換，需要大量的處理機(jī)時(shí)間 ? 改進(jìn)方法：使用硬件寄存器保存系統(tǒng)態(tài)和用戶態(tài)的不同現(xiàn)場值，切換時(shí) 只需修改指針 指向當(dāng)前寄存器組 11 2022/2/16 低級調(diào)度方式 ? 非搶占 方式 一旦某進(jìn)程獲得處理機(jī)后將一直執(zhí)行，直至進(jìn)程完成或因某事件阻塞時(shí)，才把處理機(jī)分配給其他進(jìn)程， 決不允許進(jìn)程搶占他人已獲得的處理機(jī) 可能引起進(jìn)程調(diào)度的因素：當(dāng)前進(jìn)程任務(wù)完成或因某事件阻塞、當(dāng)前進(jìn)程提出 I/O請求、進(jìn)程同步或通信時(shí)執(zhí)行了某種原語操作 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單、系統(tǒng)開銷小、適用于大多數(shù) 批處理 系統(tǒng) 缺點(diǎn)：難以立即執(zhí)行，不適合在實(shí)時(shí)性要求高的系統(tǒng)中使用 12 2022/2/16 低級調(diào)度分類 ? 搶占方式 ? 調(diào)度程序根據(jù)某種原則暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程 ? 這種方式可以提供更公平服務(wù)，但 系統(tǒng)開銷大 ? 搶占原則 ? 優(yōu)先權(quán) 原則：優(yōu)先權(quán)高的新到進(jìn)程可以搶占當(dāng)前進(jìn)程的處理機(jī) ? 短作業(yè)（進(jìn)程） 優(yōu)先原則：短作業(yè)（進(jìn)程）可以搶占當(dāng)前較長作業(yè)（進(jìn)程）的處理機(jī) ? 時(shí)間片 原則：各進(jìn)程一次只運(yùn)行一個(gè)時(shí)間片，用完后即停止執(zhí)行重新等待調(diào)度 13 2022/2/16 中級調(diào)度 ? 又稱中程調(diào)度，目的是提高內(nèi)存利用率和系統(tǒng)吞吐量 暫時(shí)不能運(yùn)行的進(jìn)程不再占用內(nèi)存， 調(diào)出 到外存對換區(qū) 等待，此時(shí)即為掛起狀態(tài)；當(dāng)重新運(yùn)行的條件具備 且 內(nèi)存有足夠空閑 時(shí)，中級調(diào)度選擇處于掛起狀態(tài)的進(jìn)程重入內(nèi)存并修改狀態(tài)為活動的，然后將其插入正確的隊(duì)列中 14 2022/2/16 調(diào)度隊(duì)列模型 ? 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 ? 具有高級和低級調(diào)度的調(diào)度隊(duì)列模型 ? 具有三種調(diào)度的調(diào)度隊(duì)列模型 15 2022/2/16 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 ? 常用于分時(shí) OS和實(shí)時(shí) OS，用戶的命令和數(shù)據(jù)直送內(nèi)存，各進(jìn)程由 命令解釋程序 創(chuàng)建 CPU 進(jìn)程完成 時(shí)間片完 進(jìn)程調(diào)度 等待事件 交互用戶 事件出現(xiàn) 就 緒 隊(duì) 列 阻 塞 隊(duì) 列 16 2022/2/16 具有高低級調(diào)度的調(diào)度隊(duì)列模型 ? 常用于多道批處理系統(tǒng)，就緒隊(duì)列按優(yōu)先級高低順序排列，阻塞隊(duì)列按阻塞原因分類 時(shí)間片完 CPU 進(jìn)程完成 進(jìn)程調(diào)度 等待事件 1 作業(yè)調(diào)度 事件 1出現(xiàn) 就 緒 隊(duì) 列 等待事件 2 等待事件 3 事件 2出現(xiàn) 事件 3出現(xiàn) 后 備 隊(duì) 列 17 2022/2/16 具有三種調(diào)度的調(diào)度隊(duì)列模型 ? 引入中級調(diào)度后，就緒分為內(nèi)存就緒和外存就緒，阻塞也分為內(nèi)存阻塞和外存阻塞，用于通用 OS CPU 進(jìn)程完成 時(shí)間片完 進(jìn)程調(diào)度 事件出現(xiàn) 作業(yè)調(diào)度 事件出現(xiàn) 就 緒 隊(duì) 列 掛起