《《软件教研室》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《软件教研室》PPT课件.ppt（69页珍藏版）》请在三一办公上搜索。
1、第三章 中断与处理机调度,中断与中断系统处理机调度调度级别与多级调度实时调度,3.1 中断与中断系统,3.1.1 中断的概念3.1.2 中断装置3.1.3 中断处理程序,3.1.1 中断的概念,处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，这一过程称为中断。中断系统：中断装置(硬件)中断处理程序(软件),3.1.2 中断装置,发现并响应中断的硬件机构识别中断源，当有多个中断源时，按紧迫程度排队；保存现场；引出中断处理程序。,中断响应和处理的过程,正运行程序 1 6,处理程序 4,PSW，PC,PC:,PSW,PC,系统桟,psw,pc,
2、.,2,5,3,HAL,OS,3.1.2.1 中断源与中断字,中断源引起中断的事件。中断寄存器保存与中断事件相关信息的寄存器。中断字中断寄存器的内容。例：IO中断：设备状态寄存器。,3.1.2.2 中断类型与中断向量,强迫性中断运行程序不期望的时钟中断、IO中断、控制台中断硬件故障中断（power failure、内存校验错）程序性中断（越界，越权、非法指令）自愿性中断运行程序期望的系统调用：fd=open(fname,mode)访管指令：准备参数 svc n 取返回值,3.1.2.2 中断类型与中断向量,3.1.2.2 中断类型与中断向量,中断向量：中断处理程序的运行环境与入口地址（PSW，
3、PC）每类中断事件有一个中断向量,中断向量的存放位置是由硬件规定的,中断向量的内容是OS在系统初始化时设置好的。,3.1.2.2 中断类型与中断向量,系统空间,3.1.2.3 中断嵌套与系统栈,一般原则：高优先级别中断可以嵌入低优先级中断实现方法：中断响应后立即屏蔽不高于当前中断优先级的中断源。,中断嵌套与系统栈,进入中断后一般需要进一步保存现场 关中断（屏蔽所有中断）进一步保存现场（地址寄存器，通用寄存器等）开中断（或开放高优先级中断）.中断处理.恢复现场 中断返回,中断嵌套与系统栈,中断嵌套:,3.1.2.4 中断优先级与中断屏蔽,中断优先级：硬件规定的中断响应次序，依据:紧迫程度；处理时
4、间。中断屏蔽：高优先级中断事件处理不受低优先级中断打扰；程序调整中断响应次序。,3.1.3 中断处理程序,强迫性中断：自愿性中断：转中断处理程序 是否嵌套中断由系统栈恢复现场 需要切换进程 返回上层中断 由系统栈恢复现场 转CPU分派 返回目态程序（dispatcher）,保存现场信息取中断字分析中断原因,保存现场信息取访管号分析调用功能,T,F,F,T,3.2 处理机调度,处理机调度算法按什么原则分配处理机调度时机何时重新分配处理机调度过程如何完成分配,scheduling,3.2.1 处理机调度算法,考虑因素（scheduling criteria）CPU利用率;(max)吞吐量;(max
5、)周转时间;(min)响应时间;(min)系统开销;(min),基本概念,阵发期:CPU burst cycle:进程(线程)使用CPU计算；I/O burst cycle:进程(线程)使用设备I/O。剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。,3.2.1.1 先到先服务算法,FCFS（First Come First Serve)按进程申请CPU（就绪）的次序。Gantt图（到达次序：P1，P2，P3）,3.2.1.1 先到先服务算法,平均等待时间：（0+27+30）/3=19（ms)Ga
6、ntt图（到达次序：P2，P3，P1）平均等待时间（0+3+8）/3=3.67,P1,P2,P3,0 3 8 35,3.2.1.2 短作业优先,SJF（Shortest Job First)按CPU burst长度Gantt chart:,3.2.1.2 短作业优先(SJF),平均等待时间：（0+3+8+15）/4=6.5（ms)特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。,3.2.1.3 最高优先数算法(HPF),静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以
7、修改。响应速度快，开销大。,3.2.1.3 最高优先数算法(Cont.),非剥夺式静态优先数获得处理机的进程运行，直至终止等待剥夺式动(静)态优先数获得处理机的进程运行，直至终止等待出现高优先级的进程,3.2.1.4 循环轮转算法(RR),基本轮转时间片(quantum,time slice)长度固定，不变；所有进程等速向前推进。改进轮转时间片长度不定，可变。,3.2.1.4 循环轮转算法(Cont.),时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。适应系统：分时,3.2.1.5 多级队列算法(MLQ),多级队列多个就绪队列，进程所属的队
8、列固定。例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）,3.2.1.6 最短剩余时间(SRTN),Shortest Remaining Time Next可剥夺SJF,3.2.1.7 反馈排队算法(FB),Feed-Back:多个就绪队列，进程所属队列可变。,3.2.1.7 反馈排队算法(Cont.),调度效果：资源利用率高被唤醒的进程尽早投入运行；响应速度快交互式进程反应及时；系统开销小计算量大的进程落入底层队列。,3.2.2 处理机调度时机,中断处理完毕，没有嵌套中断，即将返回目态。,Pi=Pj:未发生进程切换；Pi
9、Pj:发生了进程切换。,3.2.2 处理机调度时机(Cont.),必然引起进程切换的中断进程自愿结束,exit()进程被强行终止；非法指令，越界，kill进程等待可能引起进程切换的中断时钟系统调用,3.2.3 处理机调度过程,保存下降进程的现场系统栈PCB选择上升进程按处理机调度算法恢复上升进程的现场PCB 寄存器,3.3 调度级别与多级调度,3.3.1 交换与中级调度Swapping and mid-level scheduling3.3.2 作业与高级调度Job and high-level scheduling,3.3.1 交换与中级调度,术语交换(swapping)中级调度(mid-l
10、evel scheduling)并发度(degree of multi-programming)目标：控制并发度并发度过高系统开销大、响应速度慢内存等资源紧张进程(线程)频繁进入等待状态,3.3.1 交换与中级调度,3.3.2 作业与高级调度,作业状态:提交:输入机向输入井传送后备:在输入井,尚未进入内存执行:分解为进程,在内存处理完成:处理完毕,结果在输出井退出:由输出井向打印机传送,3.3.2 作业与高级调度,状态转换:提交后备:由SPOOLing输入进程完成后备执行:由作业调度(1)(高级调度)完成执行完成:由作业调度(2)完成完成退出:由SOOPLing输出进程完成,3.4 实时调度(
11、real-time scheduling),实时任务：具有明确时间约束的计算任务。Eg.某时刻前必须开始处理某时刻前必须处理完毕实时调度：合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。,实时任务分类,硬实时 与 软实时 硬实时:必须满足任务截止期要求.软实时:期望满足截止期要求.周期性与随机性 周期性:每隔固定时间发生一次 随机性:由随机事件触发，其发生时刻不确定,术语解释,Ready time:就绪时间Starting deadline:开始截止期Processing time:处理时间Completion deadline:完成截止期Occurring frequen
12、cy:发生频率,周期性实时事务,周期性实时事务:令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,Pm可调度的必要条件为：,周期性实时事务,例：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.851Schedulable,周期性实时事务,10/20+25/50=1,可调度(不考虑开销),例子,3.4.1 最早截止期调度,EDF（Earliest Deadline First)优先选择截止期最早的实时任务可抢先可以证明：对EDF来说，可调度充分条件是：在不可调度的条件下，可
13、使错过截止期任务最小化,例子:Completion deadline scheduling,3.4.2 速率单调调度,RMS（Rate Monotonic Scheduling）提出于1973年面向周期性实时事务，非剥夺式优先调度发生周期最短（频度最高）的实时任务可调度条件：,RMS的上限值,RMS vs.EDFRMS可调度条件强于EDFRMS调度较EDF实现简单,RMS例子：,可调度，具体调度结果：,0 20 60 160 180 220 240 300 320 360 460,3.5 多处理机调度,问题：M processes(threads)N processorsSMP：all pro
14、cessors are identical(homogeneous)目标：load-sharingseparate ready queue for each processor,not really balanced;common ready queue Q for all processorseach process accesses Q on its own,master/slave assignment.,3.5.1 自调度(self scheduling),均衡调度(balanced scheduling)一个就绪队列(多处理机访问互斥)优点不需要专门的处理机从事任务分派工作任务分配均
15、衡缺点当CPU较多时,就绪队列成为瓶颈线程两次调度可能处于不同处理机不能保证同组线程同时调度,自调度(self scheduling),就绪队列,进程(线程),进程(线程),进程(线程),CPU,CPU,CPU,3.5.2 组调度(gang scheduling),将一组相关(合作)的线程同时分派到多个处理机上运行避免合作线程之间的相互等待降低开销,提高运行效率例子:Cm*Task force(一组相关的计算),3.6 系统举例,Linux进程调度Windows2000/XP线程调度UNIX进程调度（见第12章）,3.6.1 Linux 进程调度,三种特征进程 Real-time FIFORe
16、al-time Round RobinTimesharingGoodness-based schedulingpriority1-40,(缺省值20),可通过nice系统调用调整，nice(value)中value的取值范围为(-20,20)之间,取priority=20-value.quantum进程尚可运行的剩余时间,Linux 进程调度,quantum对于运行进程来说，每个时钟间隔(10ms，称为一个jiffy)，将quantum减1 当所有就绪进程的quantum配额下降到0时，重新计算所有进程(包括等待进程)的quantum值 quantum=(quantum/2)+priority
17、goodnessif(Real-time)goodness=1000+priorityif(Timesharing&quantum=0)goodness=0if(Timesharing&quantum0)goodness=quantum+priority,Linux 进程调度,调度发生时刻：运行进程的quantum减至0；运行进程执行系统调用exit;运行进程因等待I/O、信号灯而被封锁;原来具有高goodness的进程被解除封锁.调度效果:实时优先于分时 交互和I/O进程优先于CPU进程,Linux 对称多处理,Linux2.0是支持对称多处理硬件的第一个Linux核心;进程或线程可以同时运
18、行在多个处理机上.为保持核心非剥夺同步要求，SMP通过一个唯一的核心自旋锁(spin-lock)来保证任何时刻最多只有一个处理机执行核心代码,支持真正意义上的SMP：将一个自旋锁分解为若干个相互独立的自旋锁，分别用于保护核心代码不相交的子集.,3.6.2 Windows 2000/XP线程调度,Main Features：Thread level scheduling;Real time+foreground+background;real time:no deadline scheduling;foreground:GUI windowbackground:non-interactivePr
19、eemptive+dynamic priority+RR+Feed back;Symmetric Multi-Processor(SMP)support;,优先级别,16个实时优先级（16-31）一些内核线程应用程序提升为实时优先级需要有权限不是真正意义上的实时调度15个可变线程优先级（1-15）基本优先级 vs.当前优先级可动态提升运行完一个quantum之后自动下降1个系统线程优先级（0）,优先级提升,优先级提升IO操作完成事件等待结束前台进程中的线程完成一个等待操作由于窗口活动而唤醒GUI线程就绪超过一定时限，未获得处理机优先级提升不会超过15,抢占CPU,抢先情形被唤醒线程优先级高于运
20、行线程优先级；某线程的优先级动态变化被抢先线程回到相应就绪队列时间配额实时线程：重新分配完整时间配额其它线程：保持剩余配额,时间配额(quantum),配额长度：6-36时钟中断（15ms发生一次）减3，2-12次时钟中断（30ms-180ms）配额用完配额用完后进入就绪队列，优先级下降,SMP上的线程调度,线程与CPU的亲合关系每个进程有一个处理器亲合掩码，缺省为所有处理器的集合线程继承其进程的亲合掩码亲合掩码可以修改SetProcessAffinityMask,SetThreadAffinityMask;,SMP上的线程调度,线程的理想处理器（Ideal processor）首选处理器：第二处理器：（在内核线程控制块中）理想处理器确定线程创建时随机确定，分散各个线程与处理机对应关系。线程可修改SetThreadIdealProcessor,就绪线程的处理器选择,有空闲处理器首选处理器第二处理器当前执行处理器（正执行调度代码）由高到低顺序找空闲的处理器无空闲处理器，考虑抢先首选处理器第二处理器可运行编号最大处理器不能抢先进入相应的就绪队列,处理器对就绪线程的选择,空闲处理器调度线程上次在此CPU上运行（二级缓冲利用）线程的理想处理器是该CPU处于就绪状态时间超过2个quantum优先级别大于等于24,
