【文章內容簡介】 終止 ? 等待 ? 剝奪式動 (靜 )態(tài)優(yōu)先數 ? 獲得處理機的進程運行，直至 ? 終止 ? 等待 ? 出現高優(yōu)先級的進程 最高優(yōu)先數算法 (Cont.) ? 可搶占 CPU ? Process Arrival time Priority Burst time ? P1 0 0 8 ? P2 2 1 5 ? P3 4 3 7 ? P4 0 2 3 ? P5 5 7 2 ? Gantt Chart 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 最高優(yōu)先數算法 (Cont.) TW進程 到達時間 運行時間 優(yōu)先級 開始時間 完成時間 周轉時間 帶權周轉時間 P1 0 8 0 17 25 25 P2 2 5 1 3 17 15 3 P3 4 7 3 4 13 9 P4 0 3 2 0 3 3 1 P5 5 2 7 5 7 2 1 平均周轉時間 =(25+15+9+3+2)/5= 平均帶權周轉時間 =(+3++1+1)/5= 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 最高優(yōu)先數算法 (Cont.) ? 例子 UNIX： preemptive+dynamic priority（可搶占 CPU動態(tài)優(yōu)先數）。 ? 計算公式： p_pri=min{127, USER+p_cpu/16+p_nice} ? 定義 USER=100； ? p_cpu: 運行進程每 20ms加 1（優(yōu)先級降低） ，其它進程每 1200ms減 10（優(yōu)先級提高）； ? p_nice: 可以通過系統(tǒng)調用 nice(… )修改的量：規(guī)定用戶進程 0~20之間（低），系統(tǒng)進程 20~+20之間（高）。 ? 調度時取 p_pri最小的。 循環(huán)輪轉算法 (RR) ? Round Robin(RR) ? 基本輪轉 ? 時間片 (quantum,time slice)長度固定，不變； ? 所有進程等速向前推進。 ? 改進輪轉 ? 時間片長度不定，可變。 循環(huán)輪轉算法 (Cont.) ? 時間片長度： 幾十毫秒 ?幾百毫秒 (eg. 50ms) ? 過長：響應速度慢； ? 過短：系統(tǒng)開銷 (overhead)大。 ? 適應系統(tǒng)： ? 分時 多級隊列算法 (MLQ) ? 多級隊列 ? 多個就緒隊列，進程所屬的隊列固定。 ? 例如：通用系統(tǒng)中： ? 隊列 1：實時進程就緒隊列（ HPF） ? 隊列 2：分時進程就緒隊列 （ RR） ? 隊列 3：批處理進程就緒隊列 （ HPF） 最短剩余時間優(yōu)先 (SRTN) ? Shortest Remaining Time Next ? 可剝奪 SJF ? Process Arrival time Burst time ? P1 0 12 ? P2 1 5 ? P3 3 7 ? P4 5 3 ? Gantt圖 0 1 6 9 16 27 P1 P2 P3 P1 P4 最短剩余時間優(yōu)先 (SRTN) TW進程 到達時間 運行時間 開始時間 完成時間 周轉時間 帶權周轉時間 P1 0 12 0 27 27 P2 1 5 1 6 5 1 P3 3 7 9 16 13 P4 5 3 6 9 4 平均周轉時 =(27+5+13+4)/4= 平均帶權周轉時間 =(+1++)= T0 1 6 9 16 27 P1 P2 P3 P1 P4 3. 反饋排隊算法 (FB) ? FeedBack: ? 多個就緒隊列，進程所屬隊列可變。 Q1（ RR,HPF） Q2（ RR,HPF） Qn（ RR,HPF） 運行 s1時間片 運行 s2時間片 …. 創(chuàng)建喚醒 優(yōu)先級 時間片 運行 sn時間片 反饋排隊算法 (Cont.) ? 調度效果： ? 資源利用率高 ? P1等待 P2占有的資源 R, P2釋放 R, 分給 P1, P1被喚醒 , 進入最高級隊列 , 可盡早投入運行 , 使用資源 R； ? 響應速度快 ? 交互式進程經常進入等待狀態(tài) (等待用戶輸入 ),一旦被喚醒(輸入完成 ),進入最高級隊列 ,可盡快被調度選中 ,投入運行 ,反應及時； ? 系統(tǒng)開銷小 ? 計算量大的進程用完前面 n1級時間片 ,沒有處理完 ,落入底層隊列 ,調度頻率下降 ,但每次獲得較長的時間片。 處理機調度時機 ? 運行進程結束； ? 運行進程等待； ? 處理機被剝奪。 目態(tài)（ Pi運行） 目態(tài)（ Pj運行） 管態(tài) 管態(tài) …... 中斷 中斷 中斷 返回 返回 返回 Pi=Pj: 未發(fā)生進程切換； PiPj: 發(fā)生了進程切換。 處理機調度時機 (Cont.) ? 必然引起進程切換的中斷 – 進程自愿結束 , exit() – 進程被強行終止； ? 非法指令，越界， kill – 進程等待 ? 可能引起進程切換的中斷 – 時鐘 – 系統(tǒng)調用 處理機調度過程 ? dispatcher ? 保存下降進程的現場 – 寄存器 (PSW,PC,SP,通用寄存器 ,地址寄存器 )?PCB ? 選擇上升進程 – 按處理機調度算法 ? 恢復上升進程的現場 – PCB ?寄存器 – 先恢復通用寄存器和地址寄存器 ,最后恢復 PSW,PC – PSW和 PC必須用一條指令恢復 調度級別與多級調度 ? 交換與中級調度 ? Swapping and midlevel scheduling ? 作業(yè)與高級調度 ? Job and highlevel scheduling 處理機調度為低級調度 CPU scheduling = low level scheduling 交換與中級調度 ? 術語 ? 交換 (swapping) ? 中級調度 (midlevel scheduling) ? 并發(fā)度 (degree of multiprogramming) ? 目標：控制并發(fā)度 ? 并發(fā)度過高