[計算機軟件及應用]os-03中斷與處理機調(diào)度(存儲版)
【正文】 8 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A B C D E 最高響應比 (HRRN) 調(diào)度算法例題 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A B C D E 反饋 (隊列有 2個） q = 1 調(diào)度算法例題 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A B C D E 反饋（采用剝奪方式） q = 2i 調(diào)度算法例題 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 ? 在多處理器線程調(diào)度和處理器分配的各種方案中，比較突出的方法是： ? 負載分配 ： 進程不是分配到一個特定的處理器，而是維護一個就緒進程的全局隊列，每個處理器只要空閑就從隊列中選擇一個線程，負載平衡是基于一種比較永久的分配方案配工作的 ? 成組調(diào)度 ： 一組相關(guān)的線程基于一對一的原則，同時調(diào)度到一組處理器上運行 ? 專用處理器分配 ： 這種方法與負載分配的方法相反，它通過把線程指定到處理器來定義隱式的調(diào)度。 – Eg. ? 某時刻前必須開始處理 ? 某時刻前必須處理完畢 ? 實時調(diào)度： – 合理安排就緒實時任務的執(zhí)行次序，滿足每個實時任務時間約束條件的調(diào)度。 ? (3) Feedback——— 比較有利于短作業(yè)，因為其工作方式類似于 RR算法。（ ） ?? ? 作 業(yè) ? 根據(jù)下表中的各進程資料，結(jié)合不同的處理器調(diào)度算法：FCFS先來先服務、 RR輪轉(zhuǎn)、 SPN最短進程、 SRTN最短剩余時間 ， HRRN最高響應比優(yōu)先，多級反饋隊列 FB（共 3個就緒隊列， q＝ 2i，采用剝奪策略），畫出各進程執(zhí)行流程圖 ，并計算 RR調(diào)度算法的平均周轉(zhuǎn)時間。 ? 解： 作業(yè) 執(zhí)行時間 優(yōu)先級 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 作業(yè) FCFS RR SPN Priority 1 0 9 9 6 2 10 1 0 0 3 11 5 2 16 4 13 3 1 18 5 14 9 4 1 平均 例題精選 ?敘述下列調(diào)度算法在支持短作業(yè)方面的差別： (1) FCFS； (2) RR； (3) Feedback (多級反饋調(diào)度 ) ? 解 : (1) FCFS—— 不怎么有利于短作業(yè)，因為在長作業(yè)之后到達的短作業(yè)將會等待較長的時間。但是，優(yōu)先級為 15的線程不能升到16級，也就是說不能升到實時類的任何級中 進程和線程優(yōu)先級 最低 (0) 最高 (15) 最低 (16) 最高 (31) 實時優(yōu) 先級類 可變優(yōu) 先級類 Windows NT 線程調(diào)度優(yōu)先級 ?當 Windows 2022運行在一個處理器上時，優(yōu)先級最高的線程總是活躍的，除非它正在等待一個事件 ?如果有多個線程具有最高的優(yōu)先級，則處理器在這一級的所有線程間被循環(huán)共享 ?在一個具有 N個處理器的多處理器系統(tǒng)中， (N1) 個最高優(yōu)先級的線程總是活躍的，在 (N1) 個處理器上獨占運行。有兩種方案： ? 搶占方式：即當高優(yōu)先級進程到來時，立即搶占處理進程的處理器，被搶占進程回到原來就緒隊列的末尾。其時間片的長短，影響著進程的進展速度 ? 當就緒進程很多時，如果時間片很長，就會影響一些需要“緊急”運行的作業(yè)。 ? 響應比 R，代表了進程的年齡，算法在保證短進程優(yōu)先的同時又兼顧了長進程 —— 折中 調(diào)度算法 ?最高響應比優(yōu)先調(diào)度算法（ HRRN） ? R=(w+s)/s=1+w/s ? 當一系列進程同時進入系統(tǒng)時，由于短作業(yè) s值小， R值就大，因此短作業(yè)得到了優(yōu)先執(zhí)行。 中程調(diào)度 ?從執(zhí)行的頻率看 – 長程調(diào)度程序的執(zhí)行頻率相對低些，并且僅僅是粗略地決定是否接受新進程以及接受哪一個 – 為進行交換決策，中程調(diào)度程序執(zhí)行得略微頻繁一些 – 短程調(diào)度程序，即分派程序執(zhí)行得最頻繁，并且精確地決定下一次執(zhí)行哪一個進程 短程調(diào)度 ?根據(jù)已占有處理機的進程是否可被剝奪這一原則，調(diào)度方式（策略）可分為： ? 非剝奪方式： 一旦某個就緒進程分得處理機之后，只要不是其自身的原因被阻塞 (如要求 I/O操作 ) 而不能繼續(xù)運行時，就一直運行下去，直至運行結(jié)束 ? 缺點：緊急進程無法立即運行，實時性差； 短進程周轉(zhuǎn)時間長，公平性差。 – 帶權(quán)的周轉(zhuǎn)時間 W： 周轉(zhuǎn)時間與執(zhí)行時間的比值 – 響應時間 從提交一個請求到開始處理的時間間隔。 ? 處理器調(diào)度算法 ：按照什么原則和方法分配處理器資源 ? 處理機調(diào)度必須設計成可以滿足多個目標，例如公平、任何進程都不會餓死、有效地使用處理器時間和低開銷等 調(diào)度算法設計指標 ? 面向用戶準則所關(guān)心的性能指標 – 周轉(zhuǎn)時間 T :指一個進程從提交到完成之間的時間間隔，包括實際執(zhí)行時間加上等待時間（等待 +就緒）。典型的調(diào)度類型有：
教學課件相關(guān)推薦
鄂ICP備17016276號-1