《计算机操作系统教程》(第3版)-03第三章-中断与处理机调度1课件

第三章中断与处理机调度3.1中断与中断系统3.2处理机调度3.3调度级别与多级调度3.4实时调度3.5多处理机调度3.6系统举例操作系统是中断驱动的！Interruptdriven第三章中断与处理机调度3.1中断与中断系统操作13.1中断与中断系统3.1.1中断的概念3.1.2中断装置3.1.3中断处理程序3.1中断与中断系统3.1.1中断的概念23.1.1中断的概念处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，这一过程称为中断。中断系统：中断装置(硬件)中断处理程序(软件)3.1.1中断的概念处理机在运行过程中，出现了某一事件，必33.1.2中断装置发现并响应中断的硬件机构识别中断源，当有多个中断源时，按紧迫程度排队；保存现场；引出中断处理程序。3.1.2中断装置发现并响应中断的硬件机构4中断响应和处理的过程正运行程序16处理程序4PSW’，PC’PC’:PSW,PC系统桟psw,pc……...253HALOS中断中断响应和处理的过程正运行程序处理程序PSW’，PC’PC’53.1.2.1中断源与中断字中断源引起中断的事件。中断寄存器保存与中断事件相关信息的寄存器。中断字中断寄存器的内容。例：IO中断：设备状态寄存器。3.1.2.1中断源与中断字中断源63.1.2.2中断类型与中断向量强迫性中断运行程序不期望的时钟中断IO中断控制台中断硬件故障中断powerfailure内存校验错程序性中断越界，越权缺页溢出，除0非法指令自愿性中断运行程序期望的系统调用访管指令系统调用fd=open(fname,mode)访管指令准备参数svcn取返回值3.1.2.2中断类型与中断向量强迫性中断自愿性中断73.1.2.2中断类型与中断向量中断装置中断处理程序运行程序访管指令运行程序中断装置中断处理程序clockIOconsolePowerfailuremalfunction强迫中断：自愿中断：SVCntrapn3.1.2.2中断类型与中断向量中断装置中断处运行程序83.1.2.2中断类型与中断向量中断向量：中断处理程序的运行环境与入口地址（PSW，PC）每类中断事件有一个中断向量,中断向量的存放位置是由硬件规定的,中断向量的内容是OS在系统初始化时设置好的。中断向量mode应为系统态3.1.2.2中断类型与中断向量中断向量：中断处理程序的运93.1.2.2中断类型与中断向量PSW1,PC1时钟中断向量PSW2,PC2I/O中断向量PSW3,PC3console中断向量PSW4,PC4硬件故障PSW5,PC5程序错误……PSWn,PCn访管中断向量00000008001600240030

…0090时钟中断处理程序PC1:I/O中断处理程序PC2:访管中断处理程序PCn:…系统空间3.1.2.2中断类型与中断向量PSW1,PC1103.1.2.3中断嵌套与系统栈一般原则：高优先级别中断可以嵌入低优先级中断实现方法：中断响应后立即屏蔽不高于当前中断优先级的中断源。3.1.2.3中断嵌套与系统栈一般原则：113.1.2.3中断嵌套与系统栈中断响应后一般需要进一步保存现场

关中断（屏蔽所有中断）进一步保存现场（通用寄存器等）

开中断（或开放高优先级中断）…...中断处理…...关中断（屏蔽所有中断）恢复现场开中断（或开放高优先级中断）中断返回3.1.2.3中断嵌套与系统栈中断响应后一般需要进一步保存123.1.2.3中断嵌套与系统栈(Cont.)……目态PSW1:PC1……管态PSW2:PC2……管态PSWn:PCn…中断嵌套:……3.1.2.3中断嵌套与系统栈(Cont.)…目态PSW1133.1.2.3中断嵌套与系统栈(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1栈顶指针:系统栈:3.1.2.3中断嵌套与系统栈(Cont.)栈顶指针:系统143.1.2.4中断优先级与中断屏蔽中断优先级：硬件规定的中断响应次序，依据:紧迫程度；处理时间。中断屏蔽：高优先级中断事件处理不受低优先级中断打扰；程序调整中断响应次序。3.1.2.4中断优先级与中断屏蔽中断优先级：153.1.3中断处理程序强迫性中断自愿性中断保存现场信息取中断字分析中断原因保存现场信息取调用号分析何种系统调用

中断处理（如等待转dispatcher)继续处理嵌套中断系统栈恢复现场返回上层中断需要切换进程系统栈恢复现场返回目态程序转dispatcherTFFT3.1.3中断处理程序强迫性中断自愿性中断保存现场信息保存163.1.3.1IO中断处理正常结束继续传输；唤醒相关进程。传输错误复执（eg.3次)；报告系统操作员。3.1.3.1IO中断处理正常结束173.1.3.2时钟中断处理Housekeeping进程管理重新计算进程调度参数(eg.动态优先数)实现软时钟，启动定时程序硬时钟5ms发生一次中断，软时钟50ms考虑进程切换3.1.3.2时钟中断处理Housekeeping183.1.3.3控制台中断处理一个控制按钮，一个中断向量，一个中断处理程序。3.1.3.3控制台中断处理一个控制按钮，一个中断向量，一193.1.3.4硬件故障处理电源故障处理掉电：内存，寄存器外存停止设备停止处理机恢复：启动处理机启动设备外存内存，寄存器UseUPSforcriticalapplications3.1.3.4硬件故障处理电源故障处理UseUPS203.1.3.4硬件故障处理(cont.)内存故障处理海明校验，奇偶校验错误下雨检查划出系统报告操作员3.1.3.4硬件故障处理(cont.)内存故障处理213.1.3.5程序性中断的处理只能由操作系统处理的中断影响系统或其它进程越界，非法指令，（处理：终止进程、调试）需要系统管理或协助页故障，缺段，（处理：动态调入）可以由用户自己处理的中断不影响系统和其它进程除0，溢出，（处理：用户处理，或OS处理）3.1.3.5程序性中断的处理只能由操作系统处理的中断22应用程序自己处理中断调试语句：on<中断条件><中断续元入口>例如：on<divide_zero>gotoLA;除0中断时转LA处理除0中断时转LB处理on<divide_zero>gotoLB除0中断续元除0中断续元LA:LB:相同中断发生在不同位置可采用不同处理方法应用程序自己处理中断调试语句：on<中断条件><中断续元23应用程序自行处理中断(Cont.)编译时：生成中断续元表：中断续元入口0中断续元入口1……中断续元入口n中断事件0:中断事件1:中断事件n:…...运行时：执行调试语句，填写中断续元表。中断时：根据中断原因查中断续元表，为0，用户未规定中断续元，由OS标准处理；非0，用户已规定中断续元，由用户处理。初始时均为0应用程序自行处理中断(Cont.)编译时：生成中断续元表：中24图3-9（P47）步骤：（1）发生溢出中断（2）保存旧PSW和PC（3）取中断向量（4）转到中断处理程序（5）访问中断续元表（假定非0）（6）系统栈中现场转移到用户栈（7）中断续元入口送寄存器（OS中断处理完成）（8）执行中断续元（9）用户栈PSW和PC送寄存器（10）返回中断断点图3-9（P47）步骤：253.1.3.6自愿性中断的处理访管指令（SuperVisorCall)形式：准备参数SVCn取返回值系统调用（systemcall)形式：返回值=系统调用名称（实参1,…,实参n)参数和返回值和存放位置是由OS规定的。3.1.3.6自愿性中断的处理访管指令（SuperViso263.1.3.6自愿性中断的处理系统调用驱动表：(tabledriven)服务程序入口addr0…………addrm-1访管号：0……...m-1Eg.UNIX3.1.3.6自愿性中断的处理系统调用驱动表：(table273.2处理机调度3.2.1处理机调度算法按什么原则分配3.2.2处理机调度时机何时重新分配3.2.3处理机调度过程如何完成分配scheduling3.2处理机调度3.2.1处理机调度算法scheduli283.2.1处理机调度算法考虑因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周转时间;(min)响应时间;(min)系统开销;(min)3.2.1处理机调度算法考虑因素（schedulingc29调度参数周转时间：完成时间-进入时间平均周转时间：周转时间的平均值带权周转时间：周转时间/运行时间平均带权周转时间：带权周转时间的平均值调度参数周转时间：完成时间-进入时间平均周转时间：周转时间的30CPUburstvs.I/Oburst阵发期:CPUburstcycle:进程(线程)使用CPU计算；I/Oburstcycle:进程(线程)使用设备I/O。进程运行行为：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU调度：考虑处于CPUburst进程集合CPUburst时间根据以前行为推定。CPUburstvs.I/Oburst阵发期:31CPUburstvs.I/Oburst下一个CPUburst的长度估算令τn是估计的第n个CPU阵发期的长度，tn的值是进程最近一次CPU阵发期长度，则有如下估算公式：τn+1=αtn+(1-α)τn参数α(0≤α≤1)控制tn和τn在公式中起的作用：当α=0时，τn+1=τn；当α=1时，τn+1=tn。通常α取。CPUburstvs.I/Oburst下一个CPU32剥夺式调度与非剥夺式调度剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。进程运行,直到结束或等待剥夺式调度与非剥夺式调度剥夺式(preemptive)333.2.1.1先到先服务算法FCFS（FirstComeFirstServe)按进程申请CPU（就绪）的次序。Process

Arrivaltime

BursttimeP1027P213P325CPU调度状况可用Gantt图表示．0273035P1P2P33.2.1.1先到先服务算法FCFS（FirstCome343.2.1.1先到先服务算法(Cont.)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1027027271P2132730299.67P3253035336.6平均周转时间=(27+29+33)/3=29.67平均带权周转时间=(1+9.67+6.6)/3=5.760273035P1P2P33.2.1.1先到先服务算法(Cont.)进程到达时间运行353.2.1.1先到先服务算法(Cont.)优点：“公平”；缺点:短作业等待时间长。3.2.1.1先到先服务算法(Cont.)优点：363.2.1.2短作业优先SJF（ShortestJobFirst)按CPUburst长度Process

Arrivaltime

BursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作业优先SJF（ShortestJob373.2.1.2短作业优先0381527P1P2P3P4进程到达时间运行时间开始时间完成时间周转时间带权周转时间P10121527272.25P2053881.6P307815152.14P4030331平均周转时间=(27+8+15+3)/4=13.25

平均带权周转时间=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作业优先038383.2.1.2短作业优先特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。3.2.1.2短作业优先特点：39最高响应比优先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime优点:同时到达任务,短者优先长作业随等待时间增加响应比增加最高响应比优先(HRN)HighestResponseR403.2.1.4最高优先数算法(HPF)静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以修改。响应速度快，开销大。适用于实时系统3.2.1.4最高优先数算法(HPF)静态优先数(stat413.2.1.4最高优先数算法(Cont.)非剥夺式静态优先数获得处理机的进程运行，直至终止等待剥夺式动(静)态优先数获得处理机的进程运行，直至终止等待出现高优先级的进程3.2.1.4最高优先数算法(Cont.)非剥夺式静态优先423.2.1.4最高优先数算法(Cont.)可抢占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高优先数算法(Cont.)可抢占CPU0433.2.1.4最高优先数算法(Cont.)进程到达时间运行时间优先级开始时间完成时间周转时间带权周转时间P10801725253.13P2251317153P347341391.29P40320331P55275721平均周转时间=(25+15+9+3+2)/5=38.8

平均带权周转时间=(3.13+3+1.29+1+1)/5=1.88

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高优先数算法(Cont.)进程到达时间运行443.2.1.4最高优先数算法(Cont.)例子UNIX：preemptive+dynamicpriority（可抢占CPU动态优先数）。计算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定义USER=100；p_cpu:运行进程每20ms加1（优先级降低），其它进程每1200ms减10（优先级提高）；p_nice:可以通过系统调用nice(…)修改的量：规定用户进程0~20之间（低），系统进程-20~+20之间（高）。调度时取p_pri最小的。3.2.1.4最高优先数算法(Cont.)例子UNIX：p453.2.1.5循环轮转算法(RR)RoundRobin(RR)基本轮转时间片(quantum,timeslice)长度固定，不变；所有进程等速向前推进。改进轮转时间片长度不定，可变。适用于分时系统3.2.1.5循环轮转算法(RR)RoundRobin(463.2.1.5循环轮转算法(Cont.)时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。适应系统：分时3.2.1.5循环轮转算法(Cont.)时间片长度：473.2.1.6多级队列算法(MLQ)多级队列多个就绪队列，进程所属的队列固定。例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）3.2.1.6多级队列算法(MLQ)多级队列483.2.1.7最短剩余时间优先(SRTN)ShortestRemainingTimeNext可剥夺SJFProcess

Arrivaltime

BursttimeP1012P215P337P453Gantt图01691627P1P2P3P1P43.2.1.7最短剩余时间优先(SRTN)Shortest493.2.1.7最短剩余时间优先(SRTN)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1012027272.25P2151651P337916131.86P4536941.33平均周转时=(27+5+13+4)/4=12.25平均带权周转时间=(2.25+1+1.86+1.33)=1.61

01691627P1P2P3P1P43.2.1.7最短剩余时间优先(SRTN)进程到达时间运行503.2.1.8反馈排队算法(FB)Feed-Back:多个就绪队列，进程所属队列可变。Q1（RR,HPF）Q2（RR,HPF）Qn（RR,HPF）运行s1时间片运行s2时间片….创建唤醒优先级时间片运行sn时间片3.2.1.8反馈排队算法(FB)Feed-Back:Q513.2.1.8反馈排队算法(Cont.)调度效果：资源利用率高P1等待P2占有的资源R,P2释放R,分给P1,P1被唤醒,进入最高级队列,可尽早投入运行,使用资源R；响应速度快交互式进程经常进入等待状态(等待用户输入),一旦被唤醒(输入完成),进入最高级队列,可尽快被调度选中,投入运行,反应及时；系统开销小计算量大的进程用完前面n-1级时间片,没有处理完,落入底层队列,调度频率下降,但每次获得较长的时间片。FeedBack3.2.1.8反馈排队算法(Cont.)调度效果：Fee523.2.2处理机调度时机运行进程结束；运行进程等待；处理机被剥夺。目态（Pi运行）目态（Pj运行）管态管态…...中断中断中断返回返回返回Pi=Pj:未发生进程切换；Pi<>Pj:发生了进程切换。3.2.2处理机调度时机运行进程结束；目态（Pi运行）管态533.2.2处理机调度时机(Cont.)必然引起进程切换的中断进程自愿结束,exit()进程被强行终止；非法指令，越界，kill进程等待可能引起进程切换的中断时钟系统调用3.2.2处理机调度时机(Cont.)必然引起进程切换的中543.2.3处理机调度过程dispatcher保存下降进程的现场寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB选择上升进程按处理机调度算法恢复上升进程的现场PCB寄存器先恢复通用寄存器和地址寄存器,最后恢复PSW,PCPSW和PC必须用一条指令恢复3.2.3处理机调度过程dispatcher553.3调度级别与多级调度3.3.1交换与中级调度Swappingandmid-levelscheduling3.3.2作业与高级调度Jobandhigh-levelscheduling处理机调度为低级调度CPUscheduling=lowlevelscheduling3.3调度级别与多级调度3.3.1交换与中级调度处理机调563.3.1交换与中级调度术语交换(swapping)中级调度(mid-levelscheduling)并发度(degreeofmulti-programming)目标：控制并发度并发度过高系统开销大响应速度慢内存等资源紧张进程(线程)频繁进入等待状态Moredeadlocks3.3.1交换与中级调度术语573.3.1交换与中级调度剥夺就绪等待运行选中等待事件事件发生就绪挂起等待挂起无终止创建创建结束换出换出换入换入事件发生3.3.1交换与中级调度剥夺就绪等待运行58UNIX的中级调度（sched#0)移入SRUN状态进程如内存不够，移出SWAIT和SSTOP状态进程；如还不够，移出SSLEEP和SRUN状态进程；条件：待移入进程在外存时间>=3秒；待移出进程在内存时间>=2秒。UNIX的中级调度（sched#0)移入SRUN状态进程593.3.2作业与高级调度作业状态:提交:输入机向输入井传送后备:在输入井,尚未进入内存执行:分解为进程,在内存处理完成:处理完毕,结果在输出井退出:由输出井向打印机传送3.3.2作业与高级调度作业状态:603.3.2作业与高级调度状态转换:提交后备:由SPOOLing输入进程完成SimultaneousPeripheralOperationOn-Line后备执行:由作业调度(1)(高级调度)完成高级调度:系统进程执行完成:由作业调度(2)完成完成退出:由SPOOLing输出进程完成提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出3.3.2作业与高级调度状态转换:提交后备执行完成退出SP61作业调度算法适合批作业调度的算法先到先服务算法(FCFS)优先数调度算法(HPF)短作业优先调度算法(SJF)最高响应比优先调度算法(HRN)不适合批作业调度的算法时间片轮转算法(RR)最短剩余时间优先(SRTN)反馈排队算法(FB)作业调度算法适合批作业调度的算法623.4实时调度(real-timescheduling)实时任务：具有明确时间约束的计算任务。Eg.某时刻前必须开始处理某时刻前必须处理完毕实时调度：合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。3.4实时调度(real-timescheduling)63实时任务分类硬实时vs.软实时

硬实时(hardreal-time):必须满足任务截止期要求.软实时(softreal-time):期望满足截止期要求.周期性vs.随机性

周期性:每隔固定时间发生一次随机性:由随机事件触发，其发生时刻不确定实时任务分类硬实时vs.软实时64术语解释Readytime:就绪时间Startingdeadline:开始截止期Processingtime:处理时间Completiondeadline:完成截止期Occurringfrequency:发生频率术语解释Readytime:就绪时间65周期性实时事务周期性实时事务:令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,…,Pm可调度的必要条件为：

周期性实时事务周期性实时事务:66周期性实时事务例：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.85<1满足可调度的必要条件周期性实时事务例：67周期性实时事务进程就绪时间处理时间完成截止期发生周期A0102020B025505010/20+25/50=1,可调度(不考虑开销)周期性实时事务进程就绪时间处理时间完成截止期发生周期A01068例子ProcessArrivaltimeExecutiontimecompletiondeadlineA(1)A(2)A(3)A(4)A(5)…...B(1)B(2)020406080…...0501010101010……252520406080100…...50100例子ProcessArrivaltime693.4.1最早截止期调度EDF（EarliestDeadlineFirst)优先选择截止期最早的实时任务可抢先可以证明：对EDF来说，可调度充分条件是：在不可调度的条件下，可使错过截止期任务最小化3.4.1最早截止期调度EDF（EarliestDead70例子:EarliestDeadlineFirst0102030405060708090100TimeA2A2dlA3A3dlA4A4dlB1A1A1dlB1dlB2B2dlA5A5dlA1B1A2B1A3B2A5B2A4A1A2B1A3A4A5B2例子:EarliestDeadlineFirst0713.4.2速率单调调度RMS（RateMonotonicScheduling）提出于1973年面向周期性实时事务，非剥夺式优先调度发生周期最短（频度最高）的实时任务可调度条件：3.4.2速率单调调度RMS（RateMonotonic72RMS的上限值n123456┇1.00.8280.7790.7560.7430.734┇ln20.693RMSvs.EDFRMS可调度条件强于EDFRMS调度较EDF实现简单RMS的上限值n11.0RMSvs.EDF73RMS例子：进程ＴiCiA10020B15040C350100可调度，具体调度结果：A1B1C1A2B2A3A4B3C202060160180220240300320360460RMS例子：进程ＴiCiA10020B15040C35010743.5多处理机调度问题：Mprocesses(threads)NprocessorsSMP：symmetricmulti-processorsallprocessorsareidentical(homogeneous)目标：load-sharingseparatereadyqueueforeachprocessor,notreallybalanced;commonreadyqueueQforallprocessorseachprocessoraccessesQonitsown,master/slaveassignment.3.5多处理机调度问题：753.5.1自调度(selfscheduling)均衡调度(balancedscheduling)一个就绪队列(多处理机访问互斥)优点不需要专门的处理机从事任务分派工作任务分配均衡缺点当CPU较多时,就绪队列成为瓶颈线程两次调度可能处于不同处理机不能保证同组线程同时调度3.5.1自调度(selfscheduling)均衡调度76自调度(selfscheduling)就绪队列进程(线程)进程(线程)进程(线程)CPUCPUCPU自调度(selfscheduling)就绪队列进程(线程)77自调度(selfscheduling)例子:Mach,改进的自调度全局队列:系统一个局部队列:每个CPU一个调度时首先考虑局部队列然后考虑全局队列自调度(selfscheduling)例子:783.5.2组调度(gangscheduling)将一组相关(合作)的线程同时分派到多个处理机上运行避免合作线程之间的相互等待降低开销,提高运行效率例子:Cm*Taskforce(一组相关的计算)3.5.2组调度(gangscheduling)将一组相793.6系统举例Linux进程调度Windows2000/XP线程调度UNIX进程调度（见第12章）3.6系统举例Linux进程调度80三种特征进程Real-timeFIFOReal-timeRoundRobinTimesharingGoodness-basedschedulingpriority0-40,(缺省值20),可通过nice系统调用调整，nice(value)中value的取值范围为(-20,20)之间,取priority=20-value.counter进程尚可运行的剩余时间3.6.1Linux进程调度三种特征进程3.6.1Linux进程调度81Linux进程调度counter对于运行进程来说，每个时钟间隔(10ms，称为一个jiffy)，将counter减1当所有就绪进程的counter配额下降到0时，重新计算所有进程(包括等待进程)的counter值

counter=(counter/2)+prioritygoodnessif(Real-time)goodness=1000+priorityif(Timesharing&&counter=0)goodness=0if(Timesharing&&counter>0)goodness=counter+priorityLinux进程调度counter82Linux进程调度调度发生时刻：

运行进程的counter减至0；

运行进程执行系统调用exit;运行进程因等待I/O、信号灯而被封锁;原来具有高goodness的进程被解除封锁.调度效果:实时优先于分时

交互和I/O进程优先于CPU进程

Linux进程调度调度发生时刻：83Linux对称多处理是支持对称多处理硬件的第一个Linux核心;进程或线程可以同时运行在多个处理机上.为保持核心非剥夺同步要求，SMP通过一个唯一的核心自旋锁(spin-lock)来保证任何时刻最多只有一个处理机执行核心代码,支持真正意义上的SMP：将一个自旋锁分解为若干个相互独立的自旋锁，分别用于保护核心代码不相交的子集.Linux对称多处理是支持对称多处理硬件的第一个Linux843.6.2Windows2000/XP线程调度MainFeatures：Threadlevelscheduling;Realtime+foreground+background;realtime:nodeadlinescheduling;foreground:GUIwindowbackground:non-interactivePreemptive+dynamicpriority+RR+Feedback;SymmetricMulti-Processor(SMP)support;3.6.2Windows2000/XP线程调度Main85优先级别16个实时优先级（16-31）一些内核线程应用程序提升为实时优先级需要有权限不是真正意义上的实时调度15个可变线程优先级（1-15）基本优先级vs.当前优先级线程基本优先级继承进程基本优先级,可上下浮动2如:进程基本优先级4,其线程基本优先级2—6,当前优先级在2—15范围内变动.可动态提升运行完一个quantum之后自动下降,不低于基本优先级1个系统线程优先级（0）优先级别16个实时优先级（16-31）86优先级提升优先级提升IO操作完成事件等待结束前台进程中的线程完成一个等待操作由于窗口活动而唤醒GUI线程就绪超过一定时限，未获得处理机优先级提升不会超过15优先级提升优先级提升87抢占CPU抢先情形被唤醒线程优先级高于运行线程优先级；某线程的优先级动态变化被抢先线程回到相应就绪队列时间配额实时线程：重新分配完整时间配额其它线程：保持剩余配额抢占CPU抢先情形88时间配额(quantum)配额长度：6--36时钟中断（15ms发生一次）减3，2--12次时钟中断（30ms--180ms）配额用完配额用完后进入就绪队列，优先级下降时间配额(quantum)配额长度：6--3689SMP上的线程调度线程与CPU的亲合关系每个进程有一个处理器亲合掩码，缺省为所有处理器的集合线程继承其进程的亲合掩码亲合掩码可以修改SetProcessAffinityMask,SetThreadAffinityMask;SMP上的线程调度线程与CPU的亲合关系90SMP上的线程调度线程的理想处理器（Idealprocessor）首选处理器：第二处理器：（在内核线程控制块中）理想处理器确定线程创建时随机确定，分散各个线程与处理机对应关系。线程可修改SetThreadIdealProcessorSMP上的线程调度线程的理想处理器（Idealproces91就绪线程对处理器的选择有空闲处理器首选处理器第二处理器当前执行处理器（正执行调度代码）由高到低顺序找空闲的处理器无空闲处理器，考虑抢先首选处理器第二处理器可运行编号最大处理器不能抢先进入相应的就绪队列就绪线程对处理器的选择有空闲处理器92处理器对就绪线程的选择空闲处理器调度线程上次在此CPU上运行（二级缓冲利用）线程的理想处理器是该CPU处于就绪状态时间超过2个quantum优先级别大于等于24处理器对就绪线程的选择空闲处理器调度93作业#1进程切换时需要保存哪些现场信息？请尽量考虑完全。由核心返回目态程序时，进程的PSW和PC为何必须用一条机器指令同时恢复？对如下三个实时任务:T1=100,C1=50;T2=200,C2=30;T3=500,C3=100.采用EDF算法和RMS算法是否可调度?如是画出对应的Gantt图,否则说明原因。作业#1进程切换时需要保存哪些现场信息？请尽量考虑完全。94第三章中断与处理机调度3.1中断与中断系统3.2处理机调度3.3调度级别与多级调度3.4实时调度3.5多处理机调度3.6系统举例操作系统是中断驱动的！Interruptdriven第三章中断与处理机调度3.1中断与中断系统操作953.1中断与中断系统3.1.1中断的概念3.1.2中断装置3.1.3中断处理程序3.1中断与中断系统3.1.1中断的概念963.1.1中断的概念处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，这一过程称为中断。中断系统：中断装置(硬件)中断处理程序(软件)3.1.1中断的概念处理机在运行过程中，出现了某一事件，必973.1.2中断装置发现并响应中断的硬件机构识别中断源，当有多个中断源时，按紧迫程度排队；保存现场；引出中断处理程序。3.1.2中断装置发现并响应中断的硬件机构98中断响应和处理的过程正运行程序16处理程序4PSW’，PC’PC’:PSW,PC系统桟psw,pc……...253HALOS中断中断响应和处理的过程正运行程序处理程序PSW’，PC’PC’993.1.2.1中断源与中断字中断源引起中断的事件。中断寄存器保存与中断事件相关信息的寄存器。中断字中断寄存器的内容。例：IO中断：设备状态寄存器。3.1.2.1中断源与中断字中断源1003.1.2.2中断类型与中断向量强迫性中断运行程序不期望的时钟中断IO中断控制台中断硬件故障中断powerfailure内存校验错程序性中断越界，越权缺页溢出，除0非法指令自愿性中断运行程序期望的系统调用访管指令系统调用fd=open(fname,mode)访管指令准备参数svcn取返回值3.1.2.2中断类型与中断向量强迫性中断自愿性中断1013.1.2.2中断类型与中断向量中断装置中断处理程序运行程序访管指令运行程序中断装置中断处理程序clockIOconsolePowerfailuremalfunction强迫中断：自愿中断：SVCntrapn3.1.2.2中断类型与中断向量中断装置中断处运行程序1023.1.2.2中断类型与中断向量中断向量：中断处理程序的运行环境与入口地址（PSW，PC）每类中断事件有一个中断向量,中断向量的存放位置是由硬件规定的,中断向量的内容是OS在系统初始化时设置好的。中断向量mode应为系统态3.1.2.2中断类型与中断向量中断向量：中断处理程序的运1033.1.2.2中断类型与中断向量PSW1,PC1时钟中断向量PSW2,PC2I/O中断向量PSW3,PC3console中断向量PSW4,PC4硬件故障PSW5,PC5程序错误……PSWn,PCn访管中断向量00000008001600240030

…0090时钟中断处理程序PC1:I/O中断处理程序PC2:访管中断处理程序PCn:…系统空间3.1.2.2中断类型与中断向量PSW1,PC11043.1.2.3中断嵌套与系统栈一般原则：高优先级别中断可以嵌入低优先级中断实现方法：中断响应后立即屏蔽不高于当前中断优先级的中断源。3.1.2.3中断嵌套与系统栈一般原则：1053.1.2.3中断嵌套与系统栈中断响应后一般需要进一步保存现场

关中断（屏蔽所有中断）进一步保存现场（通用寄存器等）

开中断（或开放高优先级中断）…...中断处理…...关中断（屏蔽所有中断）恢复现场开中断（或开放高优先级中断）中断返回3.1.2.3中断嵌套与系统栈中断响应后一般需要进一步保存1063.1.2.3中断嵌套与系统栈(Cont.)……目态PSW1:PC1……管态PSW2:PC2……管态PSWn:PCn…中断嵌套:……3.1.2.3中断嵌套与系统栈(Cont.)…目态PSW11073.1.2.3中断嵌套与系统栈(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1栈顶指针:系统栈:3.1.2.3中断嵌套与系统栈(Cont.)栈顶指针:系统1083.1.2.4中断优先级与中断屏蔽中断优先级：硬件规定的中断响应次序，依据:紧迫程度；处理时间。中断屏蔽：高优先级中断事件处理不受低优先级中断打扰；程序调整中断响应次序。3.1.2.4中断优先级与中断屏蔽中断优先级：1093.1.3中断处理程序强迫性中断自愿性中断保存现场信息取中断字分析中断原因保存现场信息取调用号分析何种系统调用

中断处理（如等待转dispatcher)继续处理嵌套中断系统栈恢复现场返回上层中断需要切换进程系统栈恢复现场返回目态程序转dispatcherTFFT3.1.3中断处理程序强迫性中断自愿性中断保存现场信息保存1103.1.3.1IO中断处理正常结束继续传输；唤醒相关进程。传输错误复执（eg.3次)；报告系统操作员。3.1.3.1IO中断处理正常结束1113.1.3.2时钟中断处理Housekeeping进程管理重新计算进程调度参数(eg.动态优先数)实现软时钟，启动定时程序硬时钟5ms发生一次中断，软时钟50ms考虑进程切换3.1.3.2时钟中断处理Housekeeping1123.1.3.3控制台中断处理一个控制按钮，一个中断向量，一个中断处理程序。3.1.3.3控制台中断处理一个控制按钮，一个中断向量，一1133.1.3.4硬件故障处理电源故障处理掉电：内存，寄存器外存停止设备停止处理机恢复：启动处理机启动设备外存内存，寄存器UseUPSforcriticalapplications3.1.3.4硬件故障处理电源故障处理UseUPS1143.1.3.4硬件故障处理(cont.)内存故障处理海明校验，奇偶校验错误下雨检查划出系统报告操作员3.1.3.4硬件故障处理(cont.)内存故障处理1153.1.3.5程序性中断的处理只能由操作系统处理的中断影响系统或其它进程越界，非法指令，（处理：终止进程、调试）需要系统管理或协助页故障，缺段，（处理：动态调入）可以由用户自己处理的中断不影响系统和其它进程除0，溢出，（处理：用户处理，或OS处理）3.1.3.5程序性中断的处理只能由操作系统处理的中断116应用程序自己处理中断调试语句：on<中断条件><中断续元入口>例如：on<divide_zero>gotoLA;除0中断时转LA处理除0中断时转LB处理on<divide_zero>gotoLB除0中断续元除0中断续元LA:LB:相同中断发生在不同位置可采用不同处理方法应用程序自己处理中断调试语句：on<中断条件><中断续元117应用程序自行处理中断(Cont.)编译时：生成中断续元表：中断续元入口0中断续元入口1……中断续元入口n中断事件0:中断事件1:中断事件n:…...运行时：执行调试语句，填写中断续元表。中断时：根据中断原因查中断续元表，为0，用户未规定中断续元，由OS标准处理；非0，用户已规定中断续元，由用户处理。初始时均为0应用程序自行处理中断(Cont.)编译时：生成中断续元表：中118图3-9（P47）步骤：（1）发生溢出中断（2）保存旧PSW和PC（3）取中断向量（4）转到中断处理程序（5）访问中断续元表（假定非0）（6）系统栈中现场转移到用户栈（7）中断续元入口送寄存器（OS中断处理完成）（8）执行中断续元（9）用户栈PSW和PC送寄存器（10）返回中断断点图3-9（P47）步骤：1193.1.3.6自愿性中断的处理访管指令（SuperVisorCall)形式：准备参数SVCn取返回值系统调用（systemcall)形式：返回值=系统调用名称（实参1,…,实参n)参数和返回值和存放位置是由OS规定的。3.1.3.6自愿性中断的处理访管指令（SuperViso1203.1.3.6自愿性中断的处理系统调用驱动表：(tabledriven)服务程序入口addr0…………addrm-1访管号：0……...m-1Eg.UNIX3.1.3.6自愿性中断的处理系统调用驱动表：(table1213.2处理机调度3.2.1处理机调度算法按什么原则分配3.2.2处理机调度时机何时重新分配3.2.3处理机调度过程如何完成分配scheduling3.2处理机调度3.2.1处理机调度算法scheduli1223.2.1处理机调度算法考虑因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周转时间;(min)响应时间;(min)系统开销;(min)3.2.1处理机调度算法考虑因素（schedulingc123调度参数周转时间：完成时间-进入时间平均周转时间：周转时间的平均值带权周转时间：周转时间/运行时间平均带权周转时间：带权周转时间的平均值调度参数周转时间：完成时间-进入时间平均周转时间：周转时间的124CPUburstvs.I/Oburst阵发期:CPUburstcycle:进程(线程)使用CPU计算；I/Oburstcycle:进程(线程)使用设备I/O。进程运行行为：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU调度：考虑处于CPUburst进程集合CPUburst时间根据以前行为推定。CPUburstvs.I/Oburst阵发期:125CPUburstvs.I/Oburst下一个CPUburst的长度估算令τn是估计的第n个CPU阵发期的长度，tn的值是进程最近一次CPU阵发期长度，则有如下估算公式：τn+1=αtn+(1-α)τn参数α(0≤α≤1)控制tn和τn在公式中起的作用：当α=0时，τn+1=τn；当α=1时，τn+1=tn。通常α取。CPUburstvs.I/Oburst下一个CPU126剥夺式调度与非剥夺式调度剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。进程运行,直到结束或等待剥夺式调度与非剥夺式调度剥夺式(preemptive)1273.2.1.1先到先服务算法FCFS（FirstComeFirstServe)按进程申请CPU（就绪）的次序。Process

Arrivaltime

BursttimeP1027P213P325CPU调度状况可用Gantt图表示．0273035P1P2P33.2.1.1先到先服务算法FCFS（FirstCome1283.2.1.1先到先服务算法(Cont.)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1027027271P2132730299.67P3253035336.6平均周转时间=(27+29+33)/3=29.67平均带权周转时间=(1+9.67+6.6)/3=5.760273035P1P2P33.2.1.1先到先服务算法(Cont.)进程到达时间运行1293.2.1.1先到先服务算法(Cont.)优点：“公平”；缺点:短作业等待时间长。3.2.1.1先到先服务算法(Cont.)优点：1303.2.1.2短作业优先SJF（ShortestJobFirst)按CPUburst长度Process

Arrivaltime

BursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作业优先SJF（ShortestJob1313.2.1.2短作业优先0381527P1P2P3P4进程到达时间运行时间开始时间完成时间周转时间带权周转时间P10121527272.25P2053881.6P307815152.14P4030331平均周转时间=(27+8+15+3)/4=13.25

平均带权周转时间=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作业优先0381323.2.1.2短作业优先特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。3.2.1.2短作业优先特点：133最高响应比优先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime优点:同时到达任务,短者优先长作业随等待时间增加响应比增加最高响应比优先(HRN)HighestResponseR1343.2.1.4最高优先数算法(HPF)静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以修改。响应速度快，开销大。适用于实时系统3.2.1.4最高优先数算法(HPF)静态优先数(stat1353.2.1.4最高优先数算法(Cont.)非剥夺式静态优先数获得处理机的进程运行，直至终止等待剥夺式动(静)态优先数获得处理机的进程运行，直至终止等待出现高优先级的进程3.2.1.4最高优先数算法(Cont.)非剥夺式静态优先1363.2.1.4最高优先数算法(Cont.)可抢占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高优先数算法(Cont.)可抢占CPU01373.2.1.4最高优先数算法(Cont.)进程到达时间运行时间优先级开始时间完成时间周转时间带权周转时间P10801725253.13P2251317153P347341391.29P40320331P55275721平均周转时间=(25+15+9+3+2)/5=38.8

平均带权周转时间=(3.13+3+1.29+1+1)/5=1.88

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高优先数算法(Cont.)进程到达时间运行1383.2.1.4最高优先数算法(Cont.)例子UNIX：preemptive+dynamicpriority（可抢占CPU动态优先数）。计算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定义USER=100；p_cpu:运行进程每20ms加1（优先级降低），其它进程每1200ms减10（优先级提高）；p_nice:可以通过系统调用nice(…)修改的量：规定用户进程0~20之间（低），系统进程-20~+20之间（高）。调度时取p_pri最小的。3.2.1.4最高优先数算法(Cont.)例子UNIX：p1393.2.1.5循环轮转算法(RR)RoundRobin(RR)基本轮转时间片(quantum,timeslice)长度固定，不变；所有进程等速向前推进。改进轮转时间片长度不定，可变。适用于分时系统3.2.1.5循环轮转算法(RR)RoundRobin(1403.2.1.5循环轮转算法(Cont.)时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。适应系统：分时3.2.1.5循环轮转算法(Cont.)时间片长度：1413.2.1.6多级队列算法(MLQ)多级队列多个就绪队列，进程所属的队列固定。例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）3.2.1.6多级队列算法(MLQ)多级队列1423.2.1.7最短剩余时间优先(SRTN)ShortestRemainingTimeNext可剥夺SJFProcess

Arrivaltime

BursttimeP1012P215P337P453Gantt图01691627P1P2P3P1P43.2.1.7最短剩余时间优先(SRTN)Shortest1433.2.1.7最短剩余时间优先(SRTN)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1012027272.25P2151651P337916131.86P4536941.33平均周转时=(27+5+13+4)/4=12.25平均带权周转时间=(2.25+1+1.86+1.33)=1.61

01691627P1P2P3P1P43.2.1.7最短剩余时间优先(SRTN)进程到达时间运行1443.2.1.8反馈排队算法(FB)Feed-Back:多个就绪队列，进程所属队列可变。Q1（RR,HPF）Q2（RR,HPF）Qn（RR,HPF）运行s1时间片运行s2时间片….创建唤醒优先级时间片运行sn时间片3.2.1.8反馈排队算法(FB)Feed-Back:Q1453.2.1.8反馈排队算法(Cont.)调度效果：资源利用率高P1等待P2占有的资源R,P2释放R,分给P1,P1被唤醒,进入最高级队列,可尽早投入运行,使用资源R；响应速度快交互式进程经常进入等待状态(等待用户输入),一旦被唤醒(输入完成),进入最高级队列,可尽快被调度选中,投入运行,反应及时；系统开销小计算量大的进程用完前面n-1级时间片,没有处理完,落入底层队列,调度频率下降,但每次获得较长的时间片。FeedBack3.2.1.8反馈排队算法(Cont.)调度效果：Fee1463.2.2处理机调度时机运行进程结束；运行进程等待；处理机被剥夺。目态（Pi运行）目态（Pj运行）管态管态…...中断中断中断返回返回返回Pi=Pj:未发生进程切换；Pi<>Pj:发生了进程切换。3.2.2处理机调度时机运行进程结束；目态（Pi运行）管态1473.2.2处理机调度时机(Cont.)必然引起进程切换的中断进程自愿结束,exit()进程被强行终止；非法指令，越界，kill进程等待可能引起进程切换的中断时钟系统调用3.2.2处理机调度时机(Cont.)必然引起进程切换的中1483.2.3处理机调度过程dispatcher保存下降进程的现场寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB选择上升进程按处理机调度算法恢复上升进程的现场PCB寄存器先恢复通用寄存器和地址寄存器,最后恢复PSW,PCPSW和PC必须用一条指令恢复3.2.3处理机调度过程dispatcher1493.3调度级别与多级调度3.3.1交换与中级调度Swappingandmid-levelscheduling3.3.2作业与高级调度Jobandhigh-levelscheduling处理机调度为低级调度CPUsch