中斷與處理機(jī)調(diào)度ppt課件(已修改)
2025-05-24 05:46 本頁面
【正文】 處理機(jī)調(diào)度 ? 處理機(jī)調(diào)度算法 ? 按什么原則分配 ? 處理機(jī)調(diào)度時(shí)機(jī) ? 何時(shí)重新分配 ? 處理機(jī)調(diào)度過程 ? 如何完成分配 處理機(jī)調(diào)度算法 ? 考慮因素（ scheduling criteria） ? CPU利用率 。 (max) ? 吞吐量 。 (max) ? 周轉(zhuǎn)時(shí)間 。 (min) ? 響應(yīng)時(shí)間 。 (min) ? 系統(tǒng)開銷 。 (min) 調(diào)度參數(shù) ?? ?? ?? ni iini i RTnWnW 11 )(1)(1??? ni iTnT 1 )(1RTW ?sf ttT ??周轉(zhuǎn)時(shí)間：完成時(shí)間 進(jìn)入時(shí)間 平均周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間的平均值 帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間 /運(yùn)行時(shí)間 平均帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間的平均值 CPU burst vs. I/O burst ? 陣發(fā)期 : ? CPU burst cycle: 進(jìn)程 (線程 )使用 CPU計(jì)算； ? I/O burst cycle: 進(jìn)程 (線程 )使用設(shè)備 I/O。 ? 進(jìn)程運(yùn)行行為： ? CPU burst, I/O burst, CPU burst, I/O burst, …… ? CPU調(diào)度：考慮處于 CPU burst進(jìn)程集合 ? CPU burst時(shí)間根據(jù)以前行為推定。 CPU burst vs. I/O burst ? 下一個(gè) CPU burst的長度估算 ? 令 τn是估計(jì)的第 n個(gè) CPU陣發(fā)期的長度， tn的值是進(jìn)程最近一次 CPU陣發(fā)期長度，則有如下估算公式： ? τn+1=αtn + (1α)τn ? 參數(shù) α(0≤α≤1)控制 tn和 τn在公式中起的作用：當(dāng) α=0時(shí)， τn+1=τn；當(dāng) α=1時(shí)， τn+1=tn。通常 α取 。 剝奪式調(diào)度與非剝奪式調(diào)度 ? 剝奪式 (preemptive) ? 就緒進(jìn)程 可以 從運(yùn)行進(jìn)程手中 搶占 CPU。 ? 進(jìn)程運(yùn)行 ,直到結(jié)束、等待或被搶先 ? 非剝奪式 (nonpreemptive) ? 就緒進(jìn)程 不可 從運(yùn)行進(jìn)程手中 搶占 CPU。 ? 進(jìn)程運(yùn)行 ,直到結(jié)束或等待 先到先服務(wù)算法 ? FCFS（ First Come First Serve) ? 按進(jìn)程申請 CPU（就緒）的次序。 ? Process Arrival time Burst time ? P1 0 27 ? P2 1 3 ? P3 2 5 ? CPU調(diào)度狀況可用 Gantt 圖表示 ． 0 27 30 35 P1 P2 P3 先到先服務(wù)算法 (Cont.) 進(jìn)程 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 P1 0 27 0 27 27 1 P2 1 3 27 30 29 P3 2 5 30 35 33 平均周轉(zhuǎn)時(shí)間 =(27+29+33)/3= 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(1++)/3= T W0 27 30 35 P1 P2 P3 先到先服務(wù)算法 (Cont.) ? 優(yōu)點(diǎn)： ? “ 公平 ” ； ? 缺點(diǎn) : ? 短作業(yè)等待時(shí)間長。 短作業(yè)優(yōu)先 ? SJF（ Shortest Job First) ? 按 CPU burst長度 ? Process Arrival time Burst time ? P1 0 12 ? P2 0 5 ? P3 0 7 ? P4 0 3 ? Gantt Chart 0 3 8 15 27 P1 P2 P3 P4 短作業(yè)優(yōu)先 0 3 8 15 27 P1 P2 P3 P4 TW進(jìn)程 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 P1 0 12 15 27 27 P2 0 5 3 8 8 P3 0 7 8 15 15 P4 0 3 0 3 3 1 平均周轉(zhuǎn)時(shí)間 =(27+8+15+3)/4= 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(+++1)/4= 短作業(yè)優(yōu)先 ? 特點(diǎn)： ? 假定所有任務(wù)同時(shí)到達(dá)，平均等待時(shí)間最短。 ? 長作業(yè)可能被餓死。 最短剩余時(shí)間優(yōu)先算法 (SRTN) ? Shortest Remaining Time Next ? 可剝奪 SJF ? Process Arrival time Burst time ? P1 0 12 ? P2 1 9 ? P3 3 6 ? P4 5 3 ? Gantt圖 P1 P2 P3 P4 P3 P2 P1 0 1 3 5 8 12 19 30 最短剩余時(shí)間優(yōu)先算法 (Cont.) 進(jìn)程 到達(dá)時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 P1 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1