03操作系统优秀PPT.ppt
第三章 中断与处理机调度l3.1 中断与中断系统l3.2 处理机调度l3.3 调度级别与多级调度l3.4 实时调度l3.5 多处理机调度l3.6 系统举例 操作系统是中断驱动的！Interrupt driven3.1 中断与中断系统l3.1.1 中断的概念l3.1.2 中断装置l3.1.3 中断处理程序3.1.1 中断的概念l处理机在运行过程中，出现了某一事务，必需中止正在运行的程序，转去处理这个事务，然后再返回原来运行的程序，这一过程称为中断。l中断系统：l中断装置(硬件)l中断处理程序(软件)3.1.2 中断装置l发觉并响应中断的硬件机构l识别中断源，当有多个中断源时，按紧迫程度排队；l保存现场；l引出中断处理程序。中断响应和处理的过程正运行程序 1 6处理程序 4PSW，PCPC:PSW,PC系统桟psw,pc.253HALOS3.1.2.1 中断源与中断字l中断源l引起中断的事务。l中断寄存器l保存与中断事务相关信息的寄存器。l中断字l中断寄存器的内容。l例：IO中断：设备状态寄存器。3.1.2.2 中断类型与中断向量l强迫性中断l运行程序不期望的l时钟中断lIO中断l限制台中断l硬件故障中断lpower failurel内存校验错l程序性中断l越界，越权，缺页l溢出，除0l非法指令l自愿性中断l运行程序期望的l系统调用l访管指令l系统调用lfd=open(fname,mode)l访管指令l准备参数lsvc nl取返回值3.1.2.2 中断类型与中断向量中断装置 中断处 理程序运行程序访管指令运行程序中断装置 中断处 理程序clockIOconsolepower failuremalfunction强迫中断：自愿中断：SVC ntrap n3.1.2.2 中断类型与中断向量l中断向量：中断处理程序的运行环境与入口地址（PSW，PC）l每类中断事务有一个中断向量,l中断向量的存放位置是由硬件规定的,l中断向量的内容是OS在系统初始化时设置好的。中断向量mode应为系统态3.1.2.2 中断类型与中断向量PSW1,PC1 时钟中断向量PSW2,PC2 I/O中断向量PSW3,PC3 console中断向量PSW4,PC4 硬件故障PSW5,PC5 程序错误 PSWn,PCn 访管中断向量00000008001600240030 0090时钟中断处理程序PC1:I/O中断处理程序PC2:访管中断处理程序PCn:系统空间3.1.2.3 中断嵌套与系统栈l一般原则：l高优先级别中断可以嵌入低优先级中断l实现方法：l中断响应后立刻屏蔽不高于当前中断优先级的中断源。3.1.2.3 中断嵌套与系统栈进入中断后一般须要进一步保存现场进入中断后一般须要进一步保存现场进入中断后一般须要进一步保存现场进入中断后一般须要进一步保存现场 关中断（屏蔽全部中断）关中断（屏蔽全部中断）关中断（屏蔽全部中断）关中断（屏蔽全部中断）进一步保存现场（地址寄存器，通用寄存器等）进一步保存现场（地址寄存器，通用寄存器等）进一步保存现场（地址寄存器，通用寄存器等）进一步保存现场（地址寄存器，通用寄存器等）开中断（或开放高优先级中断）开中断（或开放高优先级中断）开中断（或开放高优先级中断）开中断（或开放高优先级中断）.中断处理中断处理中断处理中断处理 .复原现场复原现场复原现场复原现场 中断返回中断返回中断返回中断返回3.1.2.3 中断嵌套与系统栈(Cont.)目态PSW1:PC1管态PSW2:PC2管态PSWn:PCn中断嵌套:3.1.2.3 中断嵌套与系统栈(Cont.)PSWn-1 PCn-1PSW2 PC2PSW1 PC1栈顶指针:系统栈:3.1.2.4 中断优先级与中断屏蔽l中断优先级：l硬件规定的中断响应次序，依据:l紧迫程度；l处理时间。l中断屏蔽：l高优先级中断事务处理不受低优先级中断打搅；l程序调整中断响应次序。3.1.3 中断处理程序强迫性中断：自愿性中断：转中断处理程序 是否嵌套中断由系统栈复原现场 须要切换进程 返回上层中断 由系统栈复原现场 转CPU分派 返回目态程序 （dispatcher）保存现场信息取中断字分析中断缘由保存现场信息取访管号分析调用功能TFFT3.1.3.1 IO中断处理l正常结束l接着传输；l唤醒相关进程。l传输错误l复执（eg.3次)；l报告系统操作员。3.1.3.2 时钟中断处理lHousekeeping进程管理l重新计算进程调度参数(eg.动态优先数)实现软时钟，启动定时程序l硬时钟5ms发生一次中断，软时钟50ms考虑进程切换3.1.3.3 限制台中断处理l一个限制按钮，一个中断向量，一个中断处理程序。3.1.3.4 硬件故障处理l电源故障处理l掉电：l内存，寄存器外存l停止设备l停止处理机l复原：l启动处理机l启动设备l外存内存，寄存器 Use UPS for criticalapplications3.1.3.4 硬件故障处理(cont.)l内存故障处理海明校验，奇偶校验错误l下雨检查l划出系统l报告操作员3.1.3.5 程序性中断的处理l只能由操作系统处理的中断l影响系统或其它进程l越界，非法指令，（处理：终止进程、调试）l须要系统管理或帮助l页故障，缺段，（处理：动态调入）l可以由用户自己处理的中断l不影响系统和其它进程l除0，溢出，（处理：用户处理，或OS处理）应用程序自己处理中断调试语句：on 例如：on goto LA;除0中断时转LA处理除0中断时转LB处理 on goto LB除0中断续元除0中断续元LA:LB:相同中断发生在不同位置可接受不同处理方法应用程序自行处理中断(Cont.)编译时：生成中断续元表：中断续元入口0中断续元入口1中断续元入口n中断事务0:中断事务1:中断事务n:.运行时：执行调试语句，填写中断续元表。中断时：依据中断缘由查中断续元表，为0，用户未规定中断续元，由OS标准处理；非0，用户已规定中断续元，由用户处理。初始时均为0图3-9（P44）l步骤：（1）发生溢出中断（2）保存旧PSW和PC（3）取中断向量（4）转到中断处理程序（5）访问中断续元表（假定非0）（6）系统栈中现场转移到用户栈（7）中断续元入口送寄存器（OS中断处理完成）（8）执行中断续元（9）用户栈PSW和PC送寄存器（10）返回中断断点3.1.3.6 自愿性中断的处理访管指令（SuperVisor Call)形式：准备参数SVC n取返回值系统调用（system call)形式：返回值=系统调用名称（实参1,实参n)参数和返回值的存放位置是由OS规定的。3.1.3.6 自愿性中断的处理系统调用驱动表：(table driven)服务程序入口addr1addrn访管号：0.mEg.UNIX3.2 处理机调度l3.2.1 处理机调度算法l按什么原则支配l3.2.2 处理机调度时机l何时重新支配l3.2.3 处理机调度过程l如何完成支配3.2.1 处理机调度算法l考虑因素（scheduling criteria）CPU利用率;(max)吞吐量;(max)周转时间;(min)响应时间;(min)系统开销;(min)CPU burst vs.I/O burst l阵发期:lCPU burst cycle:进程(线程)运用CPU计算；lI/O burst cycle:进程(线程)运用设备I/O。l进程运行行为：lCPU burst,I/O burst,CPU burst,I/O burst,lCPU调度：考虑处于CPU burst进程集合l CPU burst时间依据以前行为推定。剥夺式调度与非剥夺式调度l剥夺式(preemptive)l就绪进程可以从运行进程手中抢占CPU。l非剥夺式(non-preemptive)l就绪进程不行从运行进程手中抢占CPU。3.2.1.1 先到先服务算法lFCFS（First Come First Serve)按进程申请CPU（就绪）的次序。Gantt图（到达次序：P1，P2，P3）processBurst timeP127P23P35P1P2 P30 27 30 353.2.1.1 先到先服务算法(Cont.)平均等待时间：（0+27+30）/3=19（ms)Gantt图（到达次序：P2，P3，P1）平均等待时间l（0+3+8）/3=3.67P1P2 P30 3 8 353.2.1.1 先到先服务算法(Cont.)l优点：l“公允”；l短作业等待时间长。3.2.1.2 短作业优先lSJF（Shortest Job First)按CPU burst长度Gant chart:ProcessBurst timeP112P25P37P43P1P3P2P40 3 8 15 273.2.1.2 短作业优先(SJF)平均等待时间：（0+3+8+15）/4=6.5（ms)特点：假定全部任务同时到达，平均等待时间最短。长作业可能被饿死。3.2.1.3 最高优先数算法(HPF)l静态优先数(static)l优先数在进程创建时支配，生存期内不变。l响应速度慢，开销小。l适合批处理进程l动态优先数(dynamic)l进程创建时继承优先数，生存期内可以修改。l响应速度快，开销大。3.2.1.3 最高优先数算法(Cont.)l非剥夺式静态优先数获得处理机的进程运行，直至l终止l等待l剥夺式动(静)态优先数获得处理机的进程运行，直至l终止l等待l出现高优先级的进程3.2.1.3 最高优先数算法(Cont.)l例子UNIX：preemptive+dynamic priority（可抢占CPU动态优先数）。计算公式：p_pri=min127,USER+p_cpu/16+p_nice定义USER=100；p_cpu:运行进程每20ms加1（优先级降低），其它进程每1200ms减10（优先级提高）；p_nice:可以通过系统调用nice()修改的量：规定用户进程020之间（低），系统进程-20+20之间（高）。3.2.1.4 循环轮转算法(RR)lRound Robin(RR)l基本轮转l时间片(quantum,time slice)长度固定，不变；l全部进程等速向前推动。l改进轮转l时间片长度不定，可变。3.2.1.4 循环轮转算法(Cont.)l时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。l适应系统：分时3.2.1.5 多级队列算法(MLQ)l多级队列多个就绪队列，进程所属的队列固定。l例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）3.2.1.6 最短剩余时间(SRTN)lShortest Remaining Time Nextl可剥夺SJF3.2.1.7 反馈排队算法(FB)lFeed-Back:多个就绪队列，进程所属队列可变。Q1（RR，HPF）Q2（RR，HPF）Qn（RR，HPF）运行s1时间片运行s2时间片.创建唤醒优先级 时间片运行sn时间片3.2.1.7 反馈排队算法(Cont.)l调度效果：l 资源利用率高l被唤醒的进程尽早投入运行；l 响应速度快l交互式进程反应刚好；l 系统开销小l计算量大的进程落入底层队列。3.2.2 处理机调度时机l中断处理完毕，没有嵌套中断，即将返回目态。目态（Pi运行）目态（Pj运行）管态管态.中断中断中断返回返回返回Pi=Pj:未发生进程切换；PiPj:发生了进程切换。3.2.2 处理机调度时机(Cont.)l必定引起进程切换的中断l进程自愿结束,exit()l进程被强行终止；l非法指令，越界，killl进程等待l可能引起进程切换的中断l时钟l系统调用3.2.3 处理机调度过程l保存下降进程的现场l系统栈PCBl选择上升进程l按处理机调度算法l复原上升进程的现场lPCB 寄存器3.3 调度级别与多级调度l3.3.1 交换与中级调度Swapping and mid-level schedulingl3.3.2 作业与高级调度Job and high-level scheduling处理机调度为低级调度CPU scheduling=low level scheduling3.3.1 交换与中级调度l术语l交换(swapping)l中级调度(mid-level scheduling)l并发度(degree of multi-programming)l目标：限制并发度l并发度过高l系统开销大l响应速度慢l内存等资源惊惶l进程(线程)频繁进入等待状态lMore deadlocks3.3.1 交换与中级调度剥夺就绪等待运行 选中等待事务事务发生就绪挂起等待挂起无终止创建创建结束换出换出换入换入事务发生UNIX的中级调度（sched#0)l移入SRUN状态进程l如内存不够，移出SWAIT和SSTOP状态进程；如还不够，移出SSLEEP和SRUN状态进程；l条件：待移入进程在外存时间=3秒；待移出进程在内存时间=2秒。3.3.2 作业与高级调度l作业状态:提交:输入机向输入井传送后备:在输入井,尚未进入内存执行:分解为进程,在内存处理完成:处理完毕,结果在输出井退出:由输出井向打印机传送3.3.2 作业与高级调度l状态转换:提交后备:由SPOOLing输入进程完成Simultaneous Peripheral Operation On-Line后备执行:由作业调度(1)(高级调度)完成高级调度:系统进程执行完成:由作业调度(2)完成完成退出:由SOOPLing输出进程完成提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出3.4 实时调度(real-time scheduling)l实时任务：l具有明确时间约束的计算任务。lEg.l某时刻前必需起先处理l某时刻前必需处理完毕l实时调度：l合理支配就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。实时任务分类l硬实时 与 软实时 l硬实时:必需满足任务截止期要求.l软实时:期望满足截止期要求.l周期性与随机性 l周期性:每隔固定时间发生一次 l随机性:由随机事务触发，其发生时刻不确定 术语说明lReady time:就绪时间lStarting deadline:起先截止期lProcessing time:处理时间lCompletion deadline:完成截止期lOccurring frequency:发生频率周期性实时事务l周期性实时事务:令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,Pm可调度的必要条件为：周期性实时事务l例：P1=100,P2=200,P3=500(ms)C1=50,C2=30,C3=100(ms)C1/P1+C2/P2+C3/P3=0.5+0.15+0.2=0.850)goodness=quantum+priorityLinux 进程调度l调度发生时刻：运行进程的quantum减至0；运行进程执行系统调用exit;运行进程因等待I/O、信号灯而被封锁;原来具有高goodness的进程被解除封锁.l调度效果:实时优先于分时 交互和I/O进程优先于CPU进程 Linux 对称多处理lLinux2.0是支持对称多处理硬件的第一个Linux核心;l进程或线程可以同时运行在多个处理机上.l为保持核心非剥夺同步要求，SMP通过一个唯一的核心自旋锁(spin-lock)来保证任何时刻最多只有一个处理机执行核心代码,l支持真正意义上的SMP：将一个自旋锁分解为若干个相互独立的自旋锁，分别用于疼惜核心代码不相交的子集.3.6.2 Windows 2000/XP线程调度lMain Features：Thread level scheduling;Real time+foreground+background;lreal time:no deadline scheduling;lforeground:GUI windowlbackground:non-interactivePreemptive+dynamic priority +RR+Feed back;Symmetric Multi-Processor(SMP)support;优先级别l16个实时优先级（16-31）l一些内核线程l应用程序提升为实时优先级须要有权限l不是真正意义上的实时调度l15个可变线程优先级（1-15）l基本优先级 vs.当前优先级l可动态提升l运行完一个quantum之后自动下降l1个系统线程优先级（0）优先级提升l优先级提升lIO操作完成l事务等待结束l前台进程中的线程完成一个等待操作l由于窗口活动而唤醒GUI线程l就绪超过确定时限，未获得处理机l优先级提升不会超过15抢占CPUl抢先情形l被唤醒线程优先级高于运行线程优先级；l某线程的优先级动态变更l被抢先线程l回到相应就绪队列l时间配额l实时线程：重新支配完整时间配额l其它线程：保持剩余配额时间配额(quantum)l配额长度：6-36l时钟中断（15ms发生一次）减3，2-12次时钟中断（30ms-180ms）配额用完l配额用完后进入就绪队列，优先级下降SMP上的线程调度l线程与CPU的亲合关系l每个进程有一个处理器亲合掩码，缺省为全部处理器的集合l线程继承其进程的亲合掩码l亲合掩码可以修改lSetProcessAffinityMask,lSetThreadAffinityMask;SMP上的线程调度l线程的志向处理器（Ideal processor）l首选处理器：l其次处理器：（在内核线程限制块中）l志向处理器确定l线程创建时随机确定，l分散各个线程与处理机对应关系。l线程可修改SetThreadIdealProcessor就绪线程的处理器选择l有空闲处理器l首选处理器l其次处理器l当前执行处理器（正执行调度代码）l由高到低依次找空闲的处理器l无空闲处理器，考虑抢先l首选处理器l其次处理器l可运行编号最大处理器l不能抢先进入相应的就绪队列处理器对就绪线程的选择处理器对就绪线程的选择l空闲处理器调度空闲处理器调度l线程上次在此线程上次在此CPU上运行（二级缓冲利上运行（二级缓冲利用）用）l线程的志向处理器是该线程的志向处理器是该CPUl处于就绪状态时间超过处于就绪状态时间超过2个个quantuml优先级别大于等于优先级别大于等于24
