操作系統(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)度時機(jī)何時重新分配3.2.3 處理機(jī)調(diào)度過程如何完成分配scheduling3.2.1 處理機(jī)調(diào)度算法考慮因素（scheduling criteria）CPU利用率 ; (max)吞吐量 ; (max)周轉(zhuǎn)時間 ; (min)響應(yīng)時間 ; (min)系統(tǒng)開銷 ; (min)調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進(jìn)入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/運(yùn)行時間平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間的平均值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時間根據(jù)以前行為推定。CPU burst vs. I/O burst下一個CPU burst的長度估算令n是估計(jì)的第n個CPU陣發(fā)期的長度， tn的值是進(jìn)程最近一次CPU陣發(fā)期長度，則有如下估算公式：n+1=tn + (1-)n參數(shù)(01)控制tn和n在公式中起的作用：當(dāng)=0時，n+1=n；當(dāng)=1時，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á)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P102702727

4、1P2132730299.67P3253035336.6平均周轉(zhuǎn)時間 =(27+29+33)/3=29.67 平均帶權(quán)周轉(zhuǎn)時間 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P33.2.1.1 先到先服務(wù)算法(Cont.)優(yōu)點(diǎn)：“公平”；缺點(diǎn):短作業(yè)等待時間長。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á)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10121527272.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時間 =(27+8+15+3)/4=13.25 平均帶權(quán)周轉(zhuǎn)時間 =(2.25+1.6+2.14+1)/4=1.753.2.1.2 短作業(yè)優(yōu)先特點(diǎn)：假定所有任務(wù)同時到達(dá)，平均等待時間最短。長作業(yè)可能被餓死。3.2.1.3 最短剩余時間優(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 最短剩余時間優(yōu)先算法(Cont.)進(jìn)程到達(dá)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1012030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時間=(30+18+9+3)/4=15平均帶權(quán)周轉(zhuǎn)時間=(2.5+2+1.5+1)/4=1.75 平均等待時間(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):同時到達(dá)任務(wù), 短者優(yōu)先長作業(yè)隨等待時間增加響應(yīng)比增加3.2.1.5 最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(static)優(yōu)先數(shù)在進(jìn)程創(chuàng)建時分配，生存期內(nèi)不變。響應(yīng)速度慢，開銷小。適合批處理進(jìn)程動態(tài)優(yōu)先數(shù)(dynamic)進(jìn)程創(chuàng)建時繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。響應(yīng)速度快，開銷大。適用于實(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á)時間運(yùn)行時間優(yōu)先級開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉(zhuǎn)時間 =(25+15+9+3+2)/5=38.8 平均帶權(quán)周轉(zhuǎn)時間 =(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)度時取p_pri最小的。3.2.1.6 循環(huán)輪轉(zhuǎn)算法(RR)Roun

10、d Robin(RR)基本輪轉(zhuǎn)時間片(quantum,time slice)長度固定，不變；所有進(jìn)程等速向前推進(jìn)。改進(jìn)輪轉(zhuǎn)時間片長度不定，可變。適用于分時系統(tǒng)3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)時間片長度： 幾十毫秒幾百毫秒(eg. 50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時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á)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1017030301.76P2010425252.5P303811113.67平均周轉(zhuǎn)時間 (30+25+11)/3=22 平均帶權(quán)周轉(zhuǎn)時間(1.76+2.5+3.67)/3=2.64平均等待時間(13+15+8)/ 3 12(ms)P1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29 303.2.1.7 多級隊(duì)列算法(MLQ)多級隊(duì)列多個就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。例如：通用系統(tǒng)中： 隊(duì)列1：實(shí)時進(jìn)程就緒隊(duì)列（HPF） 隊(duì)

12、列2：分時進(jìn)程就緒隊(duì)列 （RR） 隊(duì)列3：批處理進(jìn)程就緒隊(duì)列 （HPF）3. 2.1.8 反饋排隊(duì)算法(FB)Feed-Back:多個就緒隊(duì)列，進(jìn)程所屬隊(duì)列可變。運(yùn)行s1時間片運(yùn)行s2時間片.創(chuàng)建喚醒優(yōu)先級 時間片運(yùn)行sn時間片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)及時； 系統(tǒng)開銷小計(jì)算量大的進(jìn)程用完前面n-1級時間片,沒有處理完,落入底層隊(duì)列,調(diào)度頻率下降,但每次獲得較長的時間片。Feed Back3.2.2 處理機(jī)調(diào)度時機(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)程切換的中斷時鐘系統(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)程在外存時間=3秒；待移出進(jìn)程在內(nèi)存時間=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)入時間處理時間

17、完成時間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)度的算法時間片輪轉(zhuǎn)算法(RR)最短剩余時間優(yōu)先(SRTN)反饋排隊(duì)算法(FB)3.4 實(shí)時調(diào)度(real-time scheduling)實(shí)時任務(wù)：具有明確時間約束的計(jì)算任務(wù)。Eg.某時刻前必須開始處理某時刻前必須處理完畢實(shí)時調(diào)度：合理安排就緒實(shí)時任務(wù)的執(zhí)行次序，滿足每個實(shí)時任務(wù)時間約束條件

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

20、P1,Pm可調(diào)度的必要條件為： 周期性實(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ā)生時刻： 運(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í)時優(yōu)先于分時 交互和I/O進(jìn)程優(yōu)先于CPU進(jìn)程 Linux 對稱多處理Linux2.0是支持對稱多處理硬件的第一個Lin

21、ux核心 ; 進(jìn)程或線程可以同時運(yùn)行在多個處理機(jī)上 .為保持核心非剝奪同步要求，SMP通過一個唯一的核心自旋鎖(spin-lock)來保證任何時刻最多只有一個處理機(jī)執(zhí)行核心代碼, 支持真正意義上的SMP：將一個自旋鎖分解為若干個相互獨(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個實(shí)時優(yōu)先級（16-31）一些內(nèi)核線程應(yīng)用程序提升為實(shí)時優(yōu)先級需要有權(quán)限不是真正意義上的實(shí)時調(diào)度15個可變線程優(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)行完一個quantum之后自動下降, 不低于基本優(yōu)先級1個系統(tǒng)線程優(yōu)先級（0）Windows優(yōu)先級3128241916158210實(shí)時(系統(tǒng))線程可變(用戶)線程頁面清0守護(hù)線程當(dāng)前優(yōu)先級基本優(yōu)先級(繼承得到,上下浮動2,最低為1)(下浮)(上浮)優(yōu)先級提升優(yōu)先級提升IO操作完成事件等待結(jié)束前臺進(jìn)程中的線程完成一個等待操作由于窗口活動而喚醒GUI線程就緒超過一定時限，未獲得