[計(jì)算機(jī)軟件及應(yīng)用]cpu-資料下載頁(yè)
2025-01-15 06:57本頁(yè)面
【正文】 或至少需要估計(jì)每個(gè)進(jìn)程所需要的處理時(shí)間。通常一進(jìn)程沒(méi)有這方面的信息，只能估計(jì)。 ? 評(píng)價(jià)： ? 有利于短進(jìn)程?？梢宰C明： SJF算法平均等待時(shí)間最小 ? 長(zhǎng)進(jìn)程就可能被餓死：只要有持續(xù)不斷的短進(jìn)程存在 。 ? 缺少剝奪機(jī)制，不適用于對(duì)分時(shí)系統(tǒng)或事務(wù)處理環(huán)境 最短剩余時(shí)間調(diào)度 SRT（ shortest remaining Timer， SRT） ? 原理： ? 對(duì) SJF增加了剝奪機(jī)制，將 SJF算法用于分時(shí)環(huán)境。從就緒隊(duì)列中選擇進(jìn)程運(yùn)行到完成時(shí)所需時(shí)間最短的進(jìn)程優(yōu)先得到處理。它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時(shí)間，只要滿足條件的新進(jìn)程就緒，調(diào)度程序就進(jìn)行剝奪。 ? 優(yōu)點(diǎn)： ? 既不偏愛(ài)長(zhǎng)進(jìn)程，也不像 RR算法那樣會(huì)產(chǎn)生額外的中斷，從而減少了開(kāi)銷(xiāo)。 ? 周轉(zhuǎn)時(shí)間方面， SRT比 SJF性能要好，短作業(yè)可以立即被選擇執(zhí)行。 ? SRT問(wèn)題： ? 需要知道或至少需要估計(jì)每個(gè)進(jìn)程所需要的處理時(shí)間。 ? 只要有持續(xù)不斷的短進(jìn)程存在，長(zhǎng)進(jìn)程就可能被餓死 ? 它必須記錄過(guò)去的服務(wù)時(shí)間，從而增加了開(kāi)銷(xiāo)。 優(yōu)先級(jí)調(diào)度 ? 優(yōu)先級(jí) ? 每個(gè)進(jìn)程都有一個(gè)優(yōu)先級(jí)，調(diào)度程序總是選擇具有較高優(yōu)先級(jí)的進(jìn)程。 ? 靜態(tài)優(yōu)先級(jí) (static) ? 優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。 ? 響應(yīng)速度慢，開(kāi)銷(xiāo)小。 ? 適合批處理進(jìn)程 ? 動(dòng)態(tài)優(yōu)先級(jí) (dynamic) ? 進(jìn)程創(chuàng)建時(shí)繼承優(yōu)先級(jí)，生存期內(nèi)可以修改。 ? 響應(yīng)速度快，開(kāi)銷(xiāo)大。 ? 問(wèn)題 ? 低優(yōu)先級(jí)的進(jìn)程可能會(huì)餓死 (無(wú)窮阻塞） 。 如果一直有高優(yōu)先級(jí)的就緒進(jìn)程的話。 ? 改進(jìn) ? 一個(gè)進(jìn)程的優(yōu)先級(jí)隨著它的時(shí)間或執(zhí)行歷史而變化－老化策略 (aging)。 輪轉(zhuǎn)調(diào)度 RR （ Round Robin） ? 輪轉(zhuǎn)調(diào)度（或稱(chēng)時(shí)間片調(diào)度（ time slicing） ：其就緒隊(duì)列按進(jìn)程達(dá)到的時(shí)間來(lái)排序。以一定的時(shí)間間隔周期性產(chǎn)生一個(gè)時(shí)鐘中斷，當(dāng)中斷發(fā)生時(shí)，按照 FCFS原則，進(jìn)程調(diào)度程序總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程，如果進(jìn)程使用完處理機(jī)一個(gè)時(shí)間片后，進(jìn)程還未完成，它也必須釋放處理機(jī)給下一個(gè)就緒的進(jìn)程，并返回到就緒隊(duì)列的末尾重新排隊(duì)，等候再次運(yùn)行。專(zhuān)門(mén)為分時(shí)系統(tǒng)設(shè)計(jì)。 ? 執(zhí)行過(guò)程： ? 將系統(tǒng)中所有的就緒進(jìn)程按照 FCFS原則，排成一個(gè)隊(duì)列。 ? 每次調(diào)度時(shí)將 CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長(zhǎng)度從幾個(gè) ms到幾百 ms。 ? 在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。 ? 調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。 ? 進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓 CPU（ 如阻塞）。 輪轉(zhuǎn)調(diào)度 RR （ Round Robin） 圖示 A B C D … F CPU 完成 超時(shí) 阻塞 ? 時(shí)間片長(zhǎng)度變化的影響 ? 過(guò)長(zhǎng)－ 響應(yīng)時(shí)間長(zhǎng)。退化為 FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完， ? 過(guò)短－ 響應(yīng)時(shí)間長(zhǎng)。用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加。 ? 因?yàn)樘幚頃r(shí)鐘中斷、執(zhí)行調(diào)度和分派函數(shù)都需要處理器開(kāi)銷(xiāo) ? 策略：時(shí)間段最好略大于一次典型的交互所需要的時(shí)間，否則使響應(yīng)時(shí)間延長(zhǎng)（使用兩個(gè)時(shí)間片）。 ? 評(píng)價(jià)： ? 在分時(shí)系統(tǒng)或事務(wù)處理器系統(tǒng)中特別有效 ? 缺點(diǎn)：偏向于 CPU型的進(jìn)程。 最高響應(yīng)比調(diào)度 算法 （ HRRN） ? 原理： ? 當(dāng)前進(jìn)程完成或被阻塞時(shí)，選擇響應(yīng)比最大的就緒進(jìn)程運(yùn)行。非搶占的調(diào)度策略。 ? 響應(yīng)比 R定義： R＝ (w＋ S)/S (R:響應(yīng)比 ,W＝ 等待時(shí)間 ,S＝ 運(yùn)行時(shí)間 ) 響應(yīng)比 R= 周轉(zhuǎn)時(shí)間 / 運(yùn)行時(shí)間 =（運(yùn)行時(shí)間 + 等待時(shí)間） / 運(yùn)行時(shí)間 = 1 +（等待時(shí)間 / 運(yùn)行時(shí)間） ? 評(píng)價(jià)： ? 該算法是 FCFS和 SJF的結(jié)合，克服了兩種算法的缺點(diǎn) ? 公平，吞吐率大 ? 需要估計(jì)期待的服務(wù)時(shí)間，增加了計(jì)算，增加了開(kāi)銷(xiāo)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1