操作系統(tǒng)課件：03第三章 中斷與處理機(jī)調(diào)度2

1、3.2 處理機(jī)調(diào)度3.2.1 處理機(jī)調(diào)度算法按什么原則分配3.2.2 處理機(jī)調(diào)度時(shí)機(jī)何時(shí)重新分配3.2.3 處理機(jī)調(diào)度過程如何完成分配scheduling3.2.1 處理機(jī)調(diào)度算法考慮因素（scheduling criteria）CPU利用率 ; (max)吞吐量 ; (max)周轉(zhuǎn)時(shí)間 ; (min)響應(yīng)時(shí)間 ; (min)系統(tǒng)開銷 ; (min)調(diào)度參數(shù)周轉(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)程(線程)使用CP

2、U計(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ù)(01)控制tn和n在公式中起的作用：當(dāng)=0時(shí)，n+1=n；當(dāng)=1時(shí)，n+1=tn。通常取0.5。剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(

3、preemptive)就緒進(jìn)程可以從運(yùn)行進(jìn)程手中搶占CPU。進(jìn)程運(yùn)行,直到結(jié)束、等待或被搶先非剝奪式(non-preemptive)就緒進(jìn)程不可從運(yùn)行進(jìn)程手中搶占CPU。進(jìn)程運(yùn)行,直到結(jié)束或等待3.2.1.1 先到先服務(wù)算法FCFS（First Come First Serve)按進(jìn)程申請CPU（就緒）的次序。Process Arrival time Burst timeP1 0 27P2 1 3P3 2 5CPU調(diào)度狀況可用Gantt 圖表示0 27 30 35P1P2P33.2.1.1 先到先服務(wù)算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P102702727

4、1P2132730299.67P3253035336.6平均周轉(zhuǎn)時(shí)間 =(27+29+33)/3=29.67 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P33.2.1.1 先到先服務(wù)算法(Cont.)優(yōu)點(diǎn)：“公平”；缺點(diǎn):短作業(yè)等待時(shí)間長。3.2.1.2 短作業(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 3Gantt Chart0 3 8 15 27P1P2P3P43.2.1.2 短作業(yè)優(yōu)先0 3 8

5、15 27P1P2P3P4進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P10121527272.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時(shí)間 =(27+8+15+3)/4=13.25 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(2.25+1.6+2.14+1)/4=1.753.2.1.2 短作業(yè)優(yōu)先特點(diǎn)：假定所有任務(wù)同時(shí)到達(dá)，平均等待時(shí)間最短。長作業(yè)可能被餓死。3.2.1.3 最短剩余時(shí)間優(yōu)先算法(SRTN) Shortest Remaining Time Next 可剝奪SJFProcess Arrival time Burst time P1 0 12 P2 1 9

6、 P3 3 6 P4 5 3Gantt圖P1P2P3P4P3P2P10 1 3 5 8 12 19 303.2.1.3 最短剩余時(shí)間優(yōu)先算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1012030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時(shí)間=(30+18+9+3)/4=15平均帶權(quán)周轉(zhuǎn)時(shí)間=(2.5+2+1.5+1)/4=1.75 平均等待時(shí)間(18+9+3+0)/ 4 7.5(ms)P1P2P3P4P3P2P10 1 3 5 8 12 19 303.2.1.4最高響應(yīng)比優(yōu)先(HRN)Highest Response Ratio

7、 NextRR=(BT+WT)/BT=1+WT/BT其中:BT=burst timeWT=wait time優(yōu)點(diǎn):同時(shí)到達(dá)任務(wù), 短者優(yōu)先長作業(yè)隨等待時(shí)間增加響應(yīng)比增加3.2.1.5 最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(static)優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。響應(yīng)速度慢，開銷小。適合批處理進(jìn)程動態(tài)優(yōu)先數(shù)(dynamic)進(jìn)程創(chuàng)建時(shí)繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。響應(yīng)速度快，開銷大。適用于實(shí)時(shí)系統(tǒng)3.2.1.5 最高優(yōu)先數(shù)算法(Cont.)非剝奪式優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待剝奪式優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待出現(xiàn)高優(yōu)先級的進(jìn)程3.2.1.5 最高優(yōu)先數(shù)算法(Co

8、nt.)可搶占CPUProcess Arrival time Priority Burst timeP1 0 0 8P2 2 1 5P3 4 3 7P4 0 2 3P5 5 7 2Gantt Chart0 3 4 5 7 13 17 25P1P4P2P2P3P3P53.2.1.5 最高優(yōu)先數(shù)算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉(zhuǎn)時(shí)間 =(25+15+9+3+2)/5=38.8 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(3.13+3+1.29+1+1)/

9、5=1.88 0 3 4 5 7 13 17 25P1P4P2P2P3P3P53.2.1.5 最高優(yōu)先數(shù)算法(Cont.)例子UNIX：preemptive+dynamic priority（可搶占CPU動態(tài)優(yōu)先數(shù)）。計(jì)算公式：p_pri=min127, USER+p_cpu/16+p_nice定義USER=100；p_cpu: 運(yùn)行進(jìn)程每20ms加1（優(yōu)先級降低），其它進(jìn)程每1200ms減10（優(yōu)先級提高）；p_nice: 可以通過系統(tǒng)調(diào)用nice()修改的量：規(guī)定用戶進(jìn)程020之間（低），系統(tǒng)進(jìn)程-20+20之間（高）。調(diào)度時(shí)取p_pri最小的。3.2.1.6 循環(huán)輪轉(zhuǎn)算法(RR)Roun

10、d Robin(RR)基本輪轉(zhuǎn)時(shí)間片(quantum,time slice)長度固定，不變；所有進(jìn)程等速向前推進(jìn)。改進(jìn)輪轉(zhuǎn)時(shí)間片長度不定，可變。適用于分時(shí)系統(tǒng)3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)時(shí)間片長度： 幾十毫秒幾百毫秒(eg. 50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時(shí)3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.) RR可搶占CPU調(diào)度：time slice=4msProcess Arriveral time Burst timeP1 0 17P2 0 10 P3 0 3 Gantt ChartP1P2P3P1P2P1P2P1P10 4 8 1

11、1 15 19 23 25 29 303.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1017030301.76P2010425252.5P303811113.67平均周轉(zhuǎn)時(shí)間 (30+25+11)/3=22 平均帶權(quán)周轉(zhuǎn)時(shí)間(1.76+2.5+3.67)/3=2.64平均等待時(shí)間(13+15+8)/ 3 12(ms)P1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29 303.2.1.7 多級隊(duì)列算法(MLQ)多級隊(duì)列多個(gè)就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。例如：通用系統(tǒng)中： 隊(duì)列1：實(shí)時(shí)進(jìn)程就緒隊(duì)列（HPF） 隊(duì)

12、列2：分時(shí)進(jìn)程就緒隊(duì)列 （RR） 隊(duì)列3：批處理進(jìn)程就緒隊(duì)列 （HPF）3. 2.1.8 反饋排隊(duì)算法(FB)Feed-Back:多個(gè)就緒隊(duì)列，進(jìn)程所屬隊(duì)列可變。運(yùn)行s1時(shí)間片運(yùn)行s2時(shí)間片.創(chuàng)建喚醒優(yōu)先級 時(shí)間片運(yùn)行sn時(shí)間片Q1 ( RR, HPF1 ) Q2 ( RR, HPF2 ) Qn ( RR, HPFn ) 3.2.1.8 反饋排隊(duì)算法 (Cont.)調(diào)度效果： 資源利用率高P1等待P2占有的資源R, P2釋放R, 分給P1, P1被喚醒, 進(jìn)入最高級隊(duì)列, 可盡早投入運(yùn)行, 使用資源R； 響應(yīng)速度快交互式進(jìn)程經(jīng)常進(jìn)入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進(jìn)入最高級隊(duì)

13、列,可盡快被調(diào)度選中,投入運(yùn)行,反應(yīng)及時(shí)； 系統(tǒng)開銷小計(jì)算量大的進(jìn)程用完前面n-1級時(shí)間片,沒有處理完,落入底層隊(duì)列,調(diào)度頻率下降,但每次獲得較長的時(shí)間片。Feed Back3.2.2 處理機(jī)調(diào)度時(shí)機(jī)運(yùn)行進(jìn)程結(jié)束；運(yùn)行進(jìn)程等待；核心級現(xiàn)場=PCB處理機(jī)被剝奪。用戶級現(xiàn)場=PCB中斷與處理機(jī)切換的關(guān)系中斷是處理機(jī)切換的必要條件，但不是充分條件必然引起進(jìn)程切換的中斷進(jìn)程自愿結(jié)束, exit()進(jìn)程被強(qiáng)行終止；非法指令，越界，kill可能引起進(jìn)程切換的中斷時(shí)鐘系統(tǒng)調(diào)用3.2.3 處理機(jī)調(diào)度過程dispatcher保存下降進(jìn)程的現(xiàn)場寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB選擇上升進(jìn)程

14、按處理機(jī)調(diào)度算法恢復(fù)上升進(jìn)程的現(xiàn)場PCB 寄存器先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PCPSW和PC必須用一條指令恢復(fù)3.3 調(diào)度級別與多級調(diào)度3.3.1 交換與中級調(diào)度Swapping and mid-level scheduling3.3.2 作業(yè)與高級調(diào)度Job and high-level scheduling處理機(jī)調(diào)度為低級調(diào)度CPU scheduling = low level scheduling3.3.1 交換與中級調(diào)度術(shù)語交換(swapping)中級調(diào)度(mid-level scheduling)并發(fā)度(degree of multi-programming)目標(biāo)：

15、控制并發(fā)度并發(fā)度過高系統(tǒng)開銷大響應(yīng)速度慢內(nèi)存等資源緊張進(jìn)程(線程)頻繁進(jìn)入等待狀態(tài)More deadlocks3.3.1 交換與中級調(diào)度剝奪就緒等待運(yùn)行 選中等待事件事件發(fā)生就緒掛起等待掛起無終止創(chuàng)建創(chuàng)建結(jié)束換出換出換入換入事件發(fā)生UNIX的中級調(diào)度（sched #0)移入SRUN狀態(tài)進(jìn)程如內(nèi)存不夠，移出SWAIT和SSTOP狀態(tài)進(jìn)程；如還不夠，移出SSLEEP和SRUN狀態(tài)進(jìn)程；條件：待移入進(jìn)程在外存時(shí)間=3秒；待移出進(jìn)程在內(nèi)存時(shí)間=2秒。3.3.2 作業(yè)與高級調(diào)度作業(yè)狀態(tài):提交: 輸入機(jī)向輸入井傳送后備: 在輸入井,尚未進(jìn)入內(nèi)存執(zhí)行: 分解為進(jìn)程,在內(nèi)存處理完成: 處理完畢,結(jié)果在輸出井退

16、出: 由輸出井向打印機(jī)傳送3.3.2 作業(yè)與高級調(diào)度狀態(tài)轉(zhuǎn)換:提交后備: 由SPOOLing輸入進(jìn)程完成Simultaneous Peripheral Operation On-Line后備執(zhí)行: 由作業(yè)調(diào)度(1)(高級調(diào)度)完成高級調(diào)度: 系統(tǒng)進(jìn)程執(zhí)行完成: 由作業(yè)調(diào)度(2)完成完成退出: 由SPOOLing輸出進(jìn)程完成提交后備執(zhí)行完成退出SPOOLing輸入作業(yè)調(diào)度1作業(yè)調(diào)度2SPOOLing輸出作業(yè)控制塊與作業(yè)表JCB（Job Control Block）：作業(yè)存在的數(shù)據(jù)結(jié)構(gòu)，其中保存系統(tǒng)對作業(yè)進(jìn)行管理的全部信息作業(yè)標(biāo)識所屬用戶作業(yè)狀態(tài)調(diào)度參數(shù)輸入井地址輸出井地址資源需求進(jìn)入時(shí)間處理時(shí)間

17、完成時(shí)間SPOOling輸入建立，作業(yè)調(diào)度使用，SPOOling輸出撤銷。JCB1JCB2JCB3JCBk作業(yè)表3.3.2 作業(yè)與高級調(diào)度(Cont.)批處理作業(yè)調(diào)度程序(1)：在后備作業(yè)集合中選擇作業(yè)，并為其建立作業(yè)控制進(jìn)程來處理該作業(yè)。作業(yè)調(diào)度程序(1)內(nèi)存已有n 道作業(yè)等 待T輸入井中有后備作業(yè)等 待F訪問磁盤中JCB表根據(jù)調(diào)度參數(shù)按作業(yè)調(diào)度算法選擇后備作業(yè)作業(yè)狀態(tài)標(biāo)志為“執(zhí)行”為該作業(yè)建立作業(yè)控制進(jìn)程3.3.2 作業(yè)與高級調(diào)度(Cont.)2. 批處理作業(yè)調(diào)度程序(2)對終止的作業(yè)控制進(jìn)程進(jìn)行善后處理。作業(yè)調(diào)度程序(2)有終止的作業(yè)控制進(jìn)程等 待F作業(yè)調(diào)度(1)因內(nèi)存有n道作業(yè)而等待撤

18、銷該作業(yè)控制進(jìn)程，做善后處理取一終止的作業(yè)控制進(jìn)程對應(yīng)作業(yè)狀態(tài)改為“完成”喚醒作業(yè)調(diào)度(1)TSpooling輸出等待作業(yè)完成喚醒Spooling輸出T作業(yè)調(diào)度算法適合批作業(yè)調(diào)度的算法先到先服務(wù)算法(FCFS)優(yōu)先數(shù)調(diào)度算法(HPF)短作業(yè)優(yōu)先調(diào)度算法(SJF)最高響應(yīng)比優(yōu)先調(diào)度算法(HRN)不適合批作業(yè)調(diào)度的算法時(shí)間片輪轉(zhuǎn)算法(RR)最短剩余時(shí)間優(yōu)先(SRTN)反饋排隊(duì)算法(FB)3.4 實(shí)時(shí)調(diào)度(real-time scheduling)實(shí)時(shí)任務(wù)：具有明確時(shí)間約束的計(jì)算任務(wù)。Eg.某時(shí)刻前必須開始處理某時(shí)刻前必須處理完畢實(shí)時(shí)調(diào)度：合理安排就緒實(shí)時(shí)任務(wù)的執(zhí)行次序，滿足每個(gè)實(shí)時(shí)任務(wù)時(shí)間約束條件

19、的調(diào)度。實(shí)時(shí)任務(wù)分類硬實(shí)時(shí) vs. 軟實(shí)時(shí) 硬實(shí)時(shí)(hard real-time): 必須滿足任務(wù)截止期要求 . 軟實(shí)時(shí)(soft real-time): 期望滿足截止期要求 . 周期性 vs. 隨機(jī)性 周期性: 每隔固定時(shí)間發(fā)生一次 隨機(jī)性: 由隨機(jī)事件觸發(fā)，其發(fā)生時(shí)刻不確定 術(shù)語解釋Ready time: 就緒時(shí)間Starting deadline: 開始截止期Processing time: 處理時(shí)間Completion deadline: 完成截止期Occurring frequency: 發(fā)生頻率周期性實(shí)時(shí)事務(wù)周期性實(shí)時(shí)事務(wù):令Ci為任務(wù)Pi處理時(shí)間，Ti為任務(wù)Pi的發(fā)生周期，則任務(wù)

20、P1,Pm可調(diào)度的必要條件為： 周期性實(shí)時(shí)事務(wù)例：T1=100, T2=200, T3=500 (ms)C1=50, C2=30, C3=100 (ms)C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.850)goodness=counter+priorityLinux 進(jìn)程調(diào)度調(diào)度發(fā)生時(shí)刻： 運(yùn)行進(jìn)程的counter減至0； 運(yùn)行進(jìn)程執(zhí)行系統(tǒng)調(diào)用exit ;運(yùn)行進(jìn)程因等待I/O、信號燈而被封鎖 ;原來具有高goodness的進(jìn)程被解除封鎖 .調(diào)度效果 :實(shí)時(shí)優(yōu)先于分時(shí) 交互和I/O進(jìn)程優(yōu)先于CPU進(jìn)程 Linux 對稱多處理Linux2.0是支持對稱多處理硬件的第一個(gè)Lin

21、ux核心 ; 進(jìn)程或線程可以同時(shí)運(yùn)行在多個(gè)處理機(jī)上 .為保持核心非剝奪同步要求，SMP通過一個(gè)唯一的核心自旋鎖(spin-lock)來保證任何時(shí)刻最多只有一個(gè)處理機(jī)執(zhí)行核心代碼, 支持真正意義上的SMP：將一個(gè)自旋鎖分解為若干個(gè)相互獨(dú)立的自旋鎖，分別用于保護(hù)核心代碼不相交的子集 .3.6.2 Windows 2000/XP線程調(diào)度Main Features：Thread level scheduling;Real time + foreground + background;real time: no deadline scheduling;foreground: GUI windowback

22、ground: non-interactivePreemptive + dynamic priority + RR + Feed back;Symmetric Multi-Processor(SMP) support;優(yōu)先級別16個(gè)實(shí)時(shí)優(yōu)先級（16-31）一些內(nèi)核線程應(yīng)用程序提升為實(shí)時(shí)優(yōu)先級需要有權(quán)限不是真正意義上的實(shí)時(shí)調(diào)度15個(gè)可變線程優(yōu)先級（1-15）基本優(yōu)先級線程基本優(yōu)先級繼承進(jìn)程基本優(yōu)先級, 可上下浮動2如: 進(jìn)程基本優(yōu)先級4, 其線程基本優(yōu)先級26, 當(dāng)前優(yōu)先級在基本優(yōu)先級與15之間浮動可動態(tài)提升運(yùn)行完一個(gè)quantum之后自動下降, 不低于基本優(yōu)先級1個(gè)系統(tǒng)線程優(yōu)先級（0）Windows優(yōu)先級3128241916158210實(shí)時(shí)(系統(tǒng))線程可變(用戶)線程頁面清0守護(hù)線程當(dāng)前優(yōu)先級基本優(yōu)先級(繼承得到,上下浮動2,最低為1)(下浮)(上浮)優(yōu)先級提升優(yōu)先級提升IO操作完成事件等待結(jié)束前臺進(jìn)程中的線程完成一個(gè)等待操作由于窗口活動而喚醒GUI線程就緒超過一定時(shí)限，未獲得