計(jì)算機(jī)操作系統(tǒng)(大學(xué)課程)第三章-文庫吧資料
2024-10-24 20:15本頁面
【正文】 8~9:p4p5p2p3 (3) 非剝奪式 SJF調(diào)度算法 ,進(jìn)程的運(yùn)行情況如圖所示 : (4) 剝奪式優(yōu)先級(jí)調(diào)度算法 ,進(jìn)程的運(yùn)行情況如圖所示 : 表 2 進(jìn)程的平均周轉(zhuǎn)時(shí)間 算法 進(jìn)程名 創(chuàng)建時(shí)間 結(jié)束時(shí)間 周轉(zhuǎn)時(shí)間 平均周轉(zhuǎn)時(shí)間 (ms) FCFS P1 0 3 3 (3+7+9+12+12)/5= P2 2 9 7 P3 4 13 9 P4 6 18 12 P5 8 20 12 RR P1 0 4 4 (4+16+13+14+7)/5= P2 2 18 16 P3 4 17 13 P4 6 20 14 P5 8 15 7 非剝奪 式優(yōu)先 級(jí) P1 0 3 3 (3+7+9+12+12)/5= P2 2 9 7 P3 4 13 9 P4 6 18 12 P5 8 20 12 剝奪式 優(yōu)先級(jí) P1 0 3 3 (3+18+4+7+7)/5= P2 2 20 18 P3 4 8 4 P4 6 13 7 P5 8 15 7 ?。 應(yīng)用程序A 應(yīng)用程序 B Cpu1 線程 1 線程 1 Cpu2 線程 2 空閑 Cpu3 線程 3 空閑 Cpu4 線程 4 空閑 時(shí)間 1/2 1/2 浪費(fèi) % 應(yīng)用程序A 應(yīng)用程序 B Cpu1 線程 1 線程 1 Cpu2 線程 2 空閑 Cpu3 線程 3 空閑 Cpu4 線程 4 空閑 時(shí)間 4/5 1/5 浪費(fèi) 15% ?引入：多處理機(jī)系統(tǒng)，每個(gè)處理已不再屬寶貴資源。 （ 2）每次分配一組 CPU，減少了調(diào)度頻率。 ? 快速任務(wù)分派 ?1非搶占式調(diào)度算法 ? 時(shí)間片輪轉(zhuǎn) 秒級(jí) ? 非搶占優(yōu)先權(quán)（協(xié)同） 秒 ~毫秒級(jí) ?2搶占式調(diào)度算法 ? 時(shí)鐘中斷搶占優(yōu)先權(quán) 毫秒級(jí) ? 基于搶占點(diǎn)搶占 ? 立即搶占 immediate preemption 毫秒 ~微秒級(jí) ? 只要不在臨界區(qū)即搶占（中斷引發(fā)） 進(jìn)程 1 進(jìn)程 2 進(jìn)程 n 實(shí)時(shí)進(jìn)程 調(diào)度時(shí)間 實(shí)時(shí)進(jìn)程要求調(diào)度 調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行 a 非搶占輪轉(zhuǎn)調(diào)度 當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程要求調(diào)度 當(dāng)前進(jìn)程運(yùn)行完成 b 非搶占優(yōu)先權(quán)調(diào)度 調(diào)度時(shí)間 c 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度 當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程要求調(diào)度 搶占時(shí)刻（其它中斷） b 立即搶占優(yōu)先權(quán)調(diào)度 當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程要求調(diào)度 時(shí)鐘中斷到達(dá)時(shí) 調(diào)度時(shí)間 調(diào)度時(shí)間 ? EDF（ earliest deadline first)算法 ? 根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級(jí) ? 截止時(shí)間越早，優(yōu)先級(jí)越高 ? 可以是搶占式或非搶占式 最早截止時(shí)間優(yōu)先 EDF例 1 3 4 2 1 3 4 2 1 2 3 4 t 開始截止時(shí)間 任務(wù)到達(dá) 任務(wù)執(zhí)行 圖 3－ 7 EDF算法用于非搶占調(diào)度方式 2. 最低松弛度優(yōu)先 LLF算法 ?松弛度： ? 若 A進(jìn)程需在 200ms時(shí)完成，其本身運(yùn)行需要 100ms，當(dāng)前時(shí)刻是 10ms，則 A的松弛度為： 200－ 100－ 10＝ 90 ? 主要用于可搶占的調(diào)度方式中 ? 例： A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 0 20 40 60 80 100 120 140 160 t 圖 3－ 8 A/B任務(wù)每次必須完成的時(shí)間 最低松弛度優(yōu)先 LLF算法 (2) A1(10) A2(10) A3(10) A4(10) t 0 10 20 30 40 50 60 70 80 t1=0 B1(20) B1(5) B2(15) B2(10) t1 t2 t3 t4 t5 t6 t7 t8 ? MPS和松弛耦合 MPS ? 緊密耦合 ? 共享 RAM和 I/O ? 高速總線和交叉開關(guān)連接 ? 松弛耦合 ? 獨(dú)立 RAM和 I/O ? 通道和通信線路連接 ? ? 處理器是否結(jié)構(gòu)相同 ? ? 靜態(tài)分配 ? 動(dòng)態(tài)分配 ? 可防止系統(tǒng)中多個(gè)處理器忙閑不均 ? SMP中進(jìn)程分配方式 ? 進(jìn)程調(diào)度在主處理器上執(zhí)行 ? 有潛在的不可靠性 （線程）調(diào)度方式 ? ? 各個(gè)處理機(jī)自行在就緒隊(duì)列中取任務(wù)。 就緒隊(duì)列 1 至 CPU S1 就緒隊(duì)列 2 S2 至 CPU 就緒隊(duì)列 3 S3 至 CPU 就緒隊(duì)列 n Sn 至 CPU 時(shí)間片： S1S2S3 圖 3－ 5多級(jí)隊(duì)列反饋調(diào)度算法 ? ? 1．提供必要的調(diào)度信息 ? （ 1）就緒時(shí)間； ? （ 2）開始 /完成截止時(shí)間； ? （ 3）處
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1