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