【正文】 策略 死鎖避免與銀行家算法 9 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 就緒隊(duì)列 阻塞隊(duì)列 交互作業(yè) 進(jìn)程調(diào)度 CPU 進(jìn)程完成 等待事件 時(shí)間片完 事件出現(xiàn) 10 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 具有高級和低級調(diào)度的調(diào)度隊(duì)列模型 就緒隊(duì)列 阻塞隊(duì)列 1 作業(yè)調(diào)度 進(jìn)程調(diào)度 CPU 進(jìn)程完成 等待事件 1 時(shí)間片完 事件 1出現(xiàn) 后備隊(duì)列 阻塞隊(duì)列 2 等待事件 2 事件 2出現(xiàn) 阻塞隊(duì)列 n 等待事件 n 事件 n出現(xiàn) … … 批量作業(yè) 交互 作業(yè) 11 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型 就緒隊(duì)列 就緒掛起隊(duì)列 作業(yè)調(diào)度 進(jìn)程調(diào)度 CPU 進(jìn)程完成 事件出現(xiàn) 時(shí)間片完 中級調(diào)度 后備隊(duì)列 阻塞掛起隊(duì)列 掛起 阻塞隊(duì)列 等待事件 事件出現(xiàn) 批量作業(yè) 交互作業(yè) 掛起 12 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 第三章 處理機(jī)調(diào)度與死鎖 高級、中級與低級調(diào)度 調(diào)度隊(duì)列模型 調(diào)度方式與算法選擇準(zhǔn)則 調(diào)度算法 死鎖產(chǎn)生及處理策略 死鎖避免與銀行家算法 13 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 選擇調(diào)度方式和算法的若干準(zhǔn)則 ? 面向用戶的準(zhǔn)則（與操作系統(tǒng)類型有關(guān)） ? 周轉(zhuǎn)時(shí)間 短（ 平均周轉(zhuǎn) /帶權(quán)周轉(zhuǎn) 時(shí)間 ） ? 響應(yīng)時(shí)間 快 ? 截至?xí)r間 的保證 ? 優(yōu)先權(quán)準(zhǔn)則 ? 面向系統(tǒng)的準(zhǔn)則 ? 系統(tǒng) 吞吐量 高 ? 處理機(jī)利用率好 ? 各類資源的平衡利用 ??????? ??niiTnT11????????? ??ni SiiTTnW1114 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 第三章 處理機(jī)調(diào)度與死鎖 高級、中級與低級調(diào)度 調(diào)度隊(duì)列模型 調(diào)度方式與算法選擇準(zhǔn)則 調(diào)度算法 死鎖產(chǎn)生及處理策略 死鎖避免與銀行家算法 15 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 調(diào)度算法（資源分配算法） 先來先服務(wù)調(diào)度算法 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 高響應(yīng)比優(yōu)先調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法 多級隊(duì)列調(diào)度算法 多級反饋隊(duì)列調(diào)度算法 16 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 先來先服務(wù)調(diào)度算法 FCFS ? 基本思想 ? 先來先服務(wù)作業(yè)調(diào)度算法 ? 先來先服務(wù)進(jìn)程調(diào)度算法 ? 算法特點(diǎn) ? 有利于長作業(yè)（進(jìn)程）而不利于短作業(yè)（進(jìn)程） ? 有利于 CPU繁忙型作業(yè)（進(jìn)程）而不利于I/O繁忙型作業(yè)（進(jìn)程） 17 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 先來先服務(wù)調(diào)度算法舉例分析 進(jìn)程名 到達(dá)時(shí)間 服務(wù)時(shí)間 開始執(zhí)行 時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn) 時(shí)間 A B C D 0 1 2 3 1 100 1 100 0 1 101 102 1 101 102 202 1 100 100 199 1 1 100 18 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 調(diào)度算法（資源分配算法） 先來先服務(wù)調(diào)度算法 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 高響應(yīng)比優(yōu)先調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法 多級隊(duì)列調(diào)度算法 多級反饋隊(duì)列調(diào)度算法 19 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 短進(jìn)程優(yōu)先調(diào)度算法舉例分析 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 服務(wù)時(shí)間 4 3 5 2 4 完成時(shí)間 4 7 12 14 18 周轉(zhuǎn)時(shí)間 4 6 10 11 14 9 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2 完成時(shí)間 4 9 18 6 13 周轉(zhuǎn)時(shí)間 4 8 16 3 9 8 帶權(quán)周轉(zhuǎn)時(shí)間 1 作業(yè)情況 先來先服務(wù) 短進(jìn)程優(yōu)先 20 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 短作業(yè) (進(jìn)程 )優(yōu)先調(diào)度算法 SJ(P)F ? 基本思想 ? 短作業(yè)優(yōu)先調(diào)度算法 ? 短進(jìn)程優(yōu)先調(diào)度算法 ? 算法特點(diǎn) ? 能有效降低作業(yè)（進(jìn)程）平均等待時(shí)間和提高系統(tǒng)吞吐量 ? 不利于長作業(yè)（進(jìn)程） ? 完全未考慮作業(yè)（進(jìn)程）的緊迫程度 ? 作業(yè)（進(jìn)程）執(zhí)行時(shí)間估計(jì)的不準(zhǔn)確性 21 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 調(diào)度算法（資源分配算法） 先來先服務(wù)調(diào)度算法 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 高響應(yīng)比優(yōu)先調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法 多級隊(duì)列調(diào)度算法 多級反饋隊(duì)列調(diào)度算法 22 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 FPF ? 基本思想 ? 照顧緊迫型作業(yè)（進(jìn)程） ? 算法分類 ? 非搶占式優(yōu)先權(quán)算法 ? 搶占式優(yōu)先權(quán)調(diào)度算法 ? 優(yōu)先權(quán)類型 ? 靜態(tài)優(yōu)先權(quán) ? 動態(tài)優(yōu)先權(quán) 進(jìn)程優(yōu)先權(quán)確定依據(jù)：進(jìn)程類型、資源需求及用戶要求 23 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 調(diào)度算法（資源分配算法） 先來先服務(wù)調(diào)度算法 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 高響應(yīng)比優(yōu)先調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法 多級隊(duì)列調(diào)度算法 多級反饋隊(duì)列調(diào)度算法 24 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 高響應(yīng)比優(yōu)先調(diào)度算法 ? 基本思想 ? 短作業(yè)優(yōu)先調(diào)度算法 +動態(tài)優(yōu)先權(quán)機(jī)制 ? 優(yōu)先權(quán)（響應(yīng)比 RP） ? （等待時(shí)間 +要求服務(wù)時(shí)間） /要求服務(wù)時(shí)間 ? 算法特點(diǎn) ? 短作業(yè)與先后次序的兼顧，且不會使長作業(yè)長期得不到服務(wù) ? 響應(yīng)比計(jì)算系統(tǒng)開銷 25 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 調(diào)度算法（資源分配算法） 先來先服務(wù)調(diào)度算法 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 高響應(yīng)比優(yōu)先調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法 多級隊(duì)列調(diào)度算法 多級反饋隊(duì)列調(diào)度算法 26 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 時(shí)間片輪轉(zhuǎn)調(diào)度算法 ? 基本思想 ? 按先來先服務(wù)原則排隊(duì) ? 時(shí)間片及時(shí)鐘中斷 ? 時(shí)間片大小的確定 ? 系統(tǒng)對響應(yīng)時(shí)間的要求 ? 就緒隊(duì)列中進(jìn)程的數(shù)目 ? 系統(tǒng)的處理能力 27 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 時(shí)間片輪轉(zhuǎn)調(diào)度算法舉例分析 待續(xù) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 A B C D E A B C D E A B C E A C E t A B C D E q=1 q=4 28 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 時(shí)間片輪轉(zhuǎn)調(diào)度算法舉例分析 續(xù)完 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 服務(wù)時(shí)間 4 3 4 2 4 完成時(shí)間 15 12 16 9 17 周轉(zhuǎn)時(shí)間 15 11 14 6 13 帶權(quán)周轉(zhuǎn)時(shí)間 3 完成時(shí)間 4 7 11 13 17 周轉(zhuǎn)時(shí)間 4 6 9 10 13 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 5 q=4 q=1 作業(yè)情況 29 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 調(diào)度算法（資源分配算法） 先來