03第三章 中断与处理机调度1.ppt

《03第三章 中断与处理机调度1.ppt》由会员分享，可在线阅读，更多相关《03第三章 中断与处理机调度1.ppt（94页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三章第三章 中断与处理机调度中断与处理机调度n3.1 中断与中断系统中断与中断系统n3.2 处理机调度处理机调度n3.3 调度级别与多级调度调度级别与多级调度n3.4 实时调度实时调度n3.5 多处理机调度多处理机调度n3.6 系统举例系统举例 操作系统是中断驱动的！操作系统是中断驱动的！Interrupt driven3.1 中断与中断系统中断与中断系统n3.1.1 中断的概念中断的概念n3.1.2 中断装置中断装置n3.1.3 中断处理程序中断处理程序3.1.1 中断的概念中断的概念n处理机在运行过程中，出现了某一事件，处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理

2、这必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，个事件，然后再返回原来运行的程序，这一过程称为中断。这一过程称为中断。n中断系统：中断系统：n中断装置中断装置(硬件硬件)n中断处理程序中断处理程序(软件软件)3.1.2 中断装置中断装置n发现并响应中断的硬件机构发现并响应中断的硬件机构n识别中断源，当有多个中断源时，按紧迫程识别中断源，当有多个中断源时，按紧迫程度排队；度排队；n保存现场；保存现场；n引出中断处理程序引出中断处理程序。中断响应和处理的过程中断响应和处理的过程正正运运行行程程序序 1 6处处理理程程序序 4PSW，PCPC:PSW,PC系统桟系统桟psw,p

3、c.253HALOS中断3.1.2.1 中断源与中断字中断源与中断字n中断源中断源n引起中断的事件。引起中断的事件。n中断寄存器中断寄存器n保存与中断事件相关信息的寄存器。保存与中断事件相关信息的寄存器。n中断字中断字n中断寄存器的内容。中断寄存器的内容。n例：例：IO中断：设备状态寄存器。中断：设备状态寄存器。3.1.2.2 中断类型与中断向量中断类型与中断向量n强迫性中断强迫性中断n运行程序不期望的运行程序不期望的n时钟中断时钟中断nIO中断中断n控制台中断控制台中断n硬件故障中断硬件故障中断npower failuren内存校验错内存校验错n程序性中断程序性中断n越界，越权越界，越权n缺

4、页缺页n溢出，除溢出，除0n非法指令非法指令n自愿性中断自愿性中断n运行程序期望的运行程序期望的n系统调用系统调用n访管指令访管指令n系统调用系统调用nfd=open(fname,mode)n访管指令访管指令n准备参数准备参数nsvc nn取返回值取返回值3.1.2.2 中断类型与中断向量中断类型与中断向量中断装置中断装置 中断处中断处 理程序理程序运行程序运行程序访管指令访管指令运行程序运行程序中断装置中断装置 中断处中断处 理程序理程序clockIOconsolePowerfailuremalfunction强迫中断强迫中断：自愿中断自愿中断：SVC ntrap n3.1.2.2 中断类型

5、与中断向量中断类型与中断向量n中断向量：中断处理程序的运行环境与中断向量：中断处理程序的运行环境与入口地址入口地址（PSW，PC）n每类中断事件有一个中断向量每类中断事件有一个中断向量,n中断向量的存放位置是由硬件规定的中断向量的存放位置是由硬件规定的,n中断向量的内容是中断向量的内容是OS在系统初始化时设置在系统初始化时设置好的。好的。中断向量中断向量mode应为系统态应为系统态3.1.2.2 中断类型与中断向量中断类型与中断向量PSW1,PC1 时钟中断向量时钟中断向量PSW2,PC2 I/O中断向量中断向量PSW3,PC3 console中断向量中断向量PSW4,PC4 硬件故障硬件故障

6、PSW5,PC5 程序错误程序错误 PSWn,PCn 访管访管中断向量中断向量00000008001600240030 0090时钟中断时钟中断处理程序处理程序PC1:I/O中断中断处理程序处理程序PC2:访管中断访管中断处理程序处理程序PCn:系统空间系统空间3.1.2.3 中断嵌套与系统栈中断嵌套与系统栈n一般原则：一般原则：n高优先级别中断可以嵌入低优先级中断高优先级别中断可以嵌入低优先级中断n实现方法：实现方法：n中断响应后立即屏蔽不高于当前中断优先级中断响应后立即屏蔽不高于当前中断优先级的中断源。的中断源。3.1.2.3 中断嵌套与系统栈中断嵌套与系统栈中断响应后一般需要进一步保存现

7、场中断响应后一般需要进一步保存现场中断响应后一般需要进一步保存现场中断响应后一般需要进一步保存现场 关中断关中断（屏蔽所有中断）（屏蔽所有中断）进一步保存现场（通用寄存器等）进一步保存现场（通用寄存器等）开中断开中断（或开放高优先级中断）（或开放高优先级中断）.中断处理中断处理 .关中断关中断（屏蔽所有中断）（屏蔽所有中断）恢复现场恢复现场 开中断开中断（或开放高优先级中断）（或开放高优先级中断）中断返回中断返回3.1.2.3 中断嵌套与系统栈中断嵌套与系统栈(Cont.)目态目态PSW1:PC1管态管态PSW2:PC2管态管态PSWn:PCn中断嵌套中断嵌套:3.1.2.3 中断嵌套与系统栈

8、中断嵌套与系统栈(Cont.)PSWn-1 PCn-1PSW2 PC2PSW1 PC1栈顶指针栈顶指针:系统栈系统栈:3.1.2.4 中断优先级与中断屏蔽中断优先级与中断屏蔽n中断优先级：中断优先级：n硬件规定的中断响应次序，依据硬件规定的中断响应次序，依据:n紧迫程度；紧迫程度；n处理时间。处理时间。n中断屏蔽：中断屏蔽：n高优先级中断事件处理不受低优先级中断打高优先级中断事件处理不受低优先级中断打扰；扰；n程序调整中断响应次序。程序调整中断响应次序。3.1.3 中断处理程序中断处理程序强迫性中断强迫性中断自愿性中断自愿性中断保存现场信息保存现场信息取中断字取中断字分析中断原因分析中断原因保

9、存现场信息保存现场信息取调用号取调用号分析何种系统调用分析何种系统调用 中断处理中断处理（如等待转（如等待转dispatcher)继续处理继续处理 嵌套中断嵌套中断系统栈恢复现场系统栈恢复现场返回上层中断返回上层中断需要切换进程需要切换进程系统栈恢复现场系统栈恢复现场返回目态程序返回目态程序转转dispatcherTFFT3.1.3.1 IO中断处理中断处理n正常结束正常结束n继续传输；继续传输；n唤醒相关进程。唤醒相关进程。n传输错误传输错误n复执（复执（eg.3次次)；n报告系统操作员。报告系统操作员。3.1.3.2 时钟中断处理时钟中断处理nHousekeepingn进程管理进程管理n重

10、新计算进程调度参数重新计算进程调度参数(eg.动态优先数动态优先数)n实现软时钟，启动定时程序实现软时钟，启动定时程序n硬时钟硬时钟5ms发生一次中断，软时钟发生一次中断，软时钟50msn考虑进程切换考虑进程切换3.1.3.3 控制台中断处理控制台中断处理n一个控制按钮，一个中断向量，一个中一个控制按钮，一个中断向量，一个中断处理程序。断处理程序。3.1.3.4 硬件故障处理硬件故障处理n电源故障处理电源故障处理n掉电：掉电：n内存，寄存器内存，寄存器外存外存n停止设备停止设备n停止处理机停止处理机n恢复：恢复：n启动处理机启动处理机n启动设备启动设备n外存外存内存，寄存器内存，寄存器 Use

11、 UPS for criticalapplications3.1.3.4 硬件故障处理硬件故障处理(cont.)n内存故障处理内存故障处理n海明校验，奇偶校验错误海明校验，奇偶校验错误n下雨检查下雨检查n划出系统划出系统n报告操作员报告操作员3.1.3.5 程序性中断的处理程序性中断的处理n只能由操作系统处理的中断只能由操作系统处理的中断n影响系统或其它进程影响系统或其它进程n越界，非法指令，（处理：终止进程、调试）越界，非法指令，（处理：终止进程、调试）n需要系统管理或协助需要系统管理或协助n页故障，缺段，（处理：动态调入）页故障，缺段，（处理：动态调入）n可以由用户自己处理的中断可以由用户

12、自己处理的中断n不影响系统和其它进程不影响系统和其它进程n除除0，溢出，（处理：用户处理，或，溢出，（处理：用户处理，或OS处理）处理）应用程序自己处理中断应用程序自己处理中断调试语句：调试语句：on 例如：例如：on goto LA;除除0中断时转中断时转LA处理处理除除0中断时转中断时转LB处理处理 on goto LB除除0中中断续元断续元除除0中中断续元断续元LA:LB:相同中断发生在不同位置相同中断发生在不同位置可采用不同处理方法可采用不同处理方法应用程序自行处理中断应用程序自行处理中断(Cont.)编译时：生成中断续元表：编译时：生成中断续元表：中断续元入口中断续元入口0中断续元入

13、口中断续元入口1中断续元入口中断续元入口n中断事件中断事件0:中断事件中断事件1:中断事件中断事件n:.运行时：执行调试语句，填写中断续元表。运行时：执行调试语句，填写中断续元表。中断时：根据中断原因查中断续元表，中断时：根据中断原因查中断续元表，为为0，用户未规定中断续元，由，用户未规定中断续元，由OS标准处理；标准处理；非非0，用户已规定中断续元，由用户处理。，用户已规定中断续元，由用户处理。初始时均为初始时均为0图图3-9（P47）n步骤：步骤：n（1）发生溢出中断）发生溢出中断n（2）保存旧）保存旧PSW和和PCn（3）取中断向量取中断向量n（4）转到中断处理程序）转到中断处理程序n（

14、5）访问中断续元表（假定非）访问中断续元表（假定非0）n（6）系统栈中现场转移到用户栈）系统栈中现场转移到用户栈n（7）中断续元入口送寄存器（）中断续元入口送寄存器（OS中断处理完成）中断处理完成）n（8）执行中断续元）执行中断续元n（9）用户栈）用户栈PSW和和PC送寄存器送寄存器n（10）返回中断断点）返回中断断点3.1.3.6 自愿性中断的处理自愿性中断的处理访管指令访管指令（SuperVisor Call)形式：形式：准备参数准备参数SVC n取返回值取返回值系统调用系统调用（system call)形式：形式：返回值返回值=系统调用名称（实参系统调用名称（实参1,实参实参n)参数和返

15、回值和存放位置是由参数和返回值和存放位置是由OS规定的。规定的。3.1.3.6 自愿性中断的处理自愿性中断的处理系统调用驱动表：系统调用驱动表：(table driven)服务程序入口服务程序入口addr0addrm-1访管号：访管号：0.m-1Eg.UNIX3.2 处理机调度处理机调度n3.2.1 处理机调度算法处理机调度算法n按什么原则分配按什么原则分配n3.2.2 处理机调度时机处理机调度时机n何时重新分配何时重新分配n3.2.3 处理机调度过程处理机调度过程n如何完成分配如何完成分配3.2.1 处理机调度算法处理机调度算法n考虑因素（考虑因素（scheduling criteria）n

16、CPU利用率利用率;(max)n吞吐量吞吐量;(max)n周转时间周转时间;(min)n响应时间响应时间;(min)n系统开销系统开销;(min)调度参数周转时间：完成时间周转时间：完成时间-进入时间进入时间平均周转时间：周转时间的平均值平均周转时间：周转时间的平均值带权周转时间：周转时间带权周转时间：周转时间/运行时间运行时间平均带权周转时间：带权周转时间的平均值平均带权周转时间：带权周转时间的平均值CPU burst vs.I/O burst n阵发期阵发期:nCPU burst cycle:进程进程(线程线程)使用使用CPU计算；计算；nI/O burst cycle:进程进程(线程线程

17、)使用设备使用设备I/O。n进程运行行为：进程运行行为：nCPU burst,I/O burst,CPU burst,I/O burst,nCPU调度：考虑处于调度：考虑处于CPU burst进程集合进程集合n CPU burst时间根据以前行为推定。时间根据以前行为推定。CPU burst vs.I/O burstn下一个下一个CPU burst的长度估算的长度估算n令令n是估计的第是估计的第n个个CPU阵发期的长度，阵发期的长度，tn的值是进程最近一次的值是进程最近一次CPU阵发期长度，则有阵发期长度，则有如下估算公式：如下估算公式：nn+1=tn+(1-)nn参数参数(01)控制控制tn

18、和和n在公式中起的作用：在公式中起的作用：当当=0时，时，n+1=n；当；当=1时，时，n+1=tn。通常通常取取0.5。剥夺式调度与非剥夺式调度剥夺式调度与非剥夺式调度n剥夺式剥夺式(preemptive)n就绪进程就绪进程可以可以从运行进程手中从运行进程手中抢占抢占CPU。n进程运行进程运行,直到结束、等待或被抢先直到结束、等待或被抢先n非剥夺式非剥夺式(non-preemptive)n就绪进程就绪进程不可不可从运行进程手中从运行进程手中抢占抢占CPU。n进程运行进程运行,直到结束或等待直到结束或等待3.2.1.1 先到先服务算法先到先服务算法nFCFS（First Come First

19、Serve)n按进程申请按进程申请CPU（就绪）的次序。（就绪）的次序。nProcess Arrival time Burst timenP1 0 27nP2 1 3nP3 2 5nCPU调度状况可用调度状况可用Gantt 图表示图表示0 27 30 35P1P2P33.2.1.1 先到先服务算法先到先服务算法(Cont.)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P1027027271P2132730299.67P3253035336.6平均周转时间平均周转时间 =(27+29+33)/3=29.67 平均带权周转时间平均

20、带权周转时间 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P33.2.1.1 先到先服务算法先到先服务算法(Cont.)n优点：优点：n“公平公平”；n缺点缺点:n短作业等待时间长。短作业等待时间长。3.2.1.2 短作业优先短作业优先nSJF（Shortest Job First)n按按CPU burst长度长度nProcess Arrival time Burst timen P1 0 12n P2 0 5n P3 0 7n P4 0 3nGantt Chart0 3 8 15 27P1P2P3P43.2.1.2 短作业优先短作业优先0 3 8 15 27P1P2

21、P3P4进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P10121527272.25P2053881.6P307815152.14P4030331平均周转时间平均周转时间 =(27+8+15+3)/4=13.25 平均带权周转时间平均带权周转时间 =(2.25+1.6+2.14+1)/4=1.753.2.1.2 短作业优先短作业优先n特点：特点：n假定所有任务同时到达，平均等待假定所有任务同时到达，平均等待时间最短。时间最短。n长作业可能被饿死。长作业可能被饿死。3.2.1.3最高响应比优先最高响应比优先(HRN)nHighes

22、t Response Ratio NextnRR=(BT+WT)/BT=1+WT/BTn其中其中:nBT=burst timenWT=wait timen优点优点:n同时到达任务同时到达任务,短者优先短者优先n长作业随等待时间增加响应比增加长作业随等待时间增加响应比增加3.2.1.4 最高优先数算法最高优先数算法(HPF)n静态优先数静态优先数(static)n优先数在进程创建时分配，生存期内不变。优先数在进程创建时分配，生存期内不变。n响应速度慢，开销小。响应速度慢，开销小。n适合批处理进程适合批处理进程n动态优先数动态优先数(dynamic)n进程创建时继承优先数，生存期内可以修改。进程创

23、建时继承优先数，生存期内可以修改。n响应速度快，开销大。响应速度快，开销大。3.2.1.4 最高优先数算法最高优先数算法(Cont.)n非剥夺式静态优先数非剥夺式静态优先数n获得处理机的进程运行，直至获得处理机的进程运行，直至n终止终止n等待等待n剥夺式动剥夺式动(静静)态优先数态优先数n获得处理机的进程运行，直至获得处理机的进程运行，直至n终止终止n等待等待n出现高优先级的进程出现高优先级的进程3.2.1.4 最高优先数算法最高优先数算法(Cont.)n可抢占CPUnProcess Arrival time Priority Burst timenP1 0 0 8nP2 2 1 5nP3 4

24、 3 7nP4 0 2 3nP5 5 7 2nGantt Chart0 0 3 3 4 4 5 5 7 7 13 13 17 17 2525P1P4P2P2P3P3P53.2.1.4 最高优先数算法最高优先数算法(Cont.)进进程程到达到达时间时间运行运行时间时间优优先先级级开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P10801725253.13P2251317153P347341391.29P40320331P55275721平均周转时间平均周转时间 =(25+15+9+3+2)/5=38.8 平均带权周转时间平均带权周转时间 =(3.13+3+1.29+1+

25、1)/5=1.88 0 0 3 3 4 4 5 5 7 7 13 13 17 17 2525P1P4P2P2P3P3P53.2.1.4 最高优先数算法最高优先数算法(Cont.)n例子例子UNIX：preemptive+dynamic priority（可抢占可抢占CPU动态优先数）。动态优先数）。n计算公式：计算公式：p_pri=min127,USER+p_cpu/16+p_nicen定义定义USER=100；np_cpu:运行进程每运行进程每20ms加加1（优先级降低）优先级降低），其，其它进程每它进程每1200ms减减10（优先级提高）；（优先级提高）；np_nice:可以通过系统调用可

26、以通过系统调用nice()修改的量：规修改的量：规定用户进程定用户进程020之间（低），系统进程之间（低），系统进程-20+20之间（高）。之间（高）。n调度时取调度时取p_pri最小的。最小的。3.2.1.5 循环轮转算法循环轮转算法(RR)nRound Robin(RR)n基本轮转基本轮转n时间片时间片(quantum,time slice)长度固定，不长度固定，不变；变；n所有进程等速向前推进。所有进程等速向前推进。n改进轮转改进轮转n时间片长度不定，可变。时间片长度不定，可变。3.2.1.5 循环轮转算法循环轮转算法(Cont.)n时间片长度：时间片长度：几十毫秒几十毫秒 几百毫秒几百

27、毫秒(eg.50ms)n过长：响应速度慢；过长：响应速度慢；n过短：系统开销过短：系统开销(overhead)大。大。n适应系统：适应系统：n分时分时3.2.1.6 多级队列算法多级队列算法(MLQ)n多级队列多级队列n多个就绪队列，进程所属的队列固定。多个就绪队列，进程所属的队列固定。n例如：通用系统中：例如：通用系统中：n 队列队列1：实时进程就绪队列（：实时进程就绪队列（HPF）n 队列队列2：分时进程就绪队列：分时进程就绪队列（RR）n 队列队列3：批处理进程就绪队列：批处理进程就绪队列（HPF）3.2.1.7 最短剩余时间优先最短剩余时间优先(SRTN)nShortest Remai

28、ning Time Nextn可剥夺可剥夺SJFnProcess Arrival time Burst timen P1 0 12n P2 1 5n P3 3 7n P4 5 3nGantt图0 1 6 9 16 27P1P2P3P1P43.2.1.7 最短剩余时间优先最短剩余时间优先(SRTN)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P1012027272.25P2151651P337916131.86P4536941.33平均周转时平均周转时 =(27+5+13+4)/4=12.25平均带权周转时间平均带权周转时间 =

29、(2.25+1+1.86+1.33)=1.61 0 1 6 9 16 27P1P2P3P1P43.2.1.8 反馈排队算法反馈排队算法(FB)nFeed-Back:n多个就绪队列，进程所属队列可变。多个就绪队列，进程所属队列可变。Q1（RR,HPF）Q2（RR,HPF）Qn（RR,HPF）运行运行s1时间片时间片运行运行s2时间片时间片.创建创建唤醒唤醒优优先先级级 时时间间片片运行运行sn时间片时间片3.2.1.8 反馈排队算法反馈排队算法(Cont.)n调度效果：调度效果：n 资源利用率高资源利用率高nP1等待等待P2占有的资源占有的资源R,P2释放释放R,分给分给P1,P1被唤醒被唤醒,

30、进进入最高级队列入最高级队列,可尽早投入运行可尽早投入运行,使用资源使用资源R；n 响应速度快响应速度快n交互式进程经常进入等待状态交互式进程经常进入等待状态(等待用户输入等待用户输入),一旦被唤醒一旦被唤醒(输入完成输入完成),进入最高级队列进入最高级队列,可尽快被调度选中可尽快被调度选中,投入运行投入运行,反应及时；反应及时；n 系统开销小系统开销小n计算量大的进程用完前面计算量大的进程用完前面n-1级时间片级时间片,没有处理完没有处理完,落入底落入底层队列层队列,调度频率下降调度频率下降,但每次获得较长的时间片。但每次获得较长的时间片。3.2.2 处理机调度时机处理机调度时机l运行进程结

31、束；运行进程结束；l运行进程等待；运行进程等待；l处理机被剥夺。处理机被剥夺。目态（目态（Pi运行）运行）目态（目态（Pj运行）运行）管态管态管态管态.中断中断中断中断中断中断返回返回返回返回返回返回Pi=Pj:未发生进程切换；未发生进程切换；PiPj:发生了进程切换。发生了进程切换。3.2.2 处理机调度时机处理机调度时机(Cont.)l必然引起进程切换的中断必然引起进程切换的中断进程自愿结束进程自愿结束,exit()进程进程被强行终止；被强行终止；l非法非法指令，越界，指令，越界，kill进程等待进程等待l可能引起进程切换的中断可能引起进程切换的中断时钟时钟系统调用系统调用3.2.3 处理

32、机调度过程处理机调度过程ldispatcherl保存下降进程的现场保存下降进程的现场寄存器寄存器(PSW,PC,SP,通用寄存器通用寄存器,地址寄存器地址寄存器)PCBl选择上升进程选择上升进程按处理机调度算法按处理机调度算法l恢复上升进程的现场恢复上升进程的现场PCB 寄存器寄存器先恢复通用寄存器和地址寄存器先恢复通用寄存器和地址寄存器,最后恢复最后恢复PSW,PCPSW和和PC必须用一条指令恢复必须用一条指令恢复3.3 调度级别与多级调度调度级别与多级调度n3.3.1 交换与中级调度交换与中级调度nSwapping and mid-level schedulingn3.3.2 作业与高级调

33、度作业与高级调度nJob and high-level scheduling处理机调度为低级调处理机调度为低级调度度CPU scheduling=low level scheduling3.3.1 交换与中级调度交换与中级调度n术语术语n交换交换(swapping)n中中级调度级调度(mid-level scheduling)n并发度并发度(degree of multi-programming)n目标：控制并发度目标：控制并发度n并发度过高并发度过高n系统开销大系统开销大n响应速度慢响应速度慢n内存等资源紧张内存等资源紧张n进程进程(线程线程)频繁进入等待状态频繁进入等待状态nMore de

34、adlocks3.3.1 交换与中级调度交换与中级调度剥夺剥夺就绪就绪等待等待运行运行 选中选中等待事件等待事件事件发生事件发生就绪就绪挂起挂起等待等待挂起挂起无无终止终止创建创建创建创建结束结束换出换出换出换出换入换入换入换入事件发生事件发生UNIX的的中级调度（中级调度（sched#0)n移入移入SRUN状态进程状态进程n如内存不够，如内存不够，n移出移出SWAIT和和SSTOP状态进程；状态进程；n如还不够，移出如还不够，移出SSLEEP和和SRUN状态进程；状态进程；n条件：条件：n待移入进程在外存时间待移入进程在外存时间=3秒；秒；n待移出进程在内存时间待移出进程在内存时间=2秒。秒

35、。3.3.2 作业与高级调度作业与高级调度n作业状态作业状态:n提交提交:输入机向输入井传送输入机向输入井传送n后备后备:在输入井在输入井,尚未进入内存尚未进入内存n执行执行:分解为进程分解为进程,在内存处理在内存处理n完成完成:处理完毕处理完毕,结果在输出井结果在输出井n退出退出:由输出井向打印机传送由输出井向打印机传送3.3.2 作业与高级调度作业与高级调度l状态转换状态转换:提交提交后备后备:由由SPOOLing输入进程完成输入进程完成Simultaneous Peripheral Operation On-Line后备后备执行执行:由作业调度由作业调度(1)(高级调度高级调度)完成完成

36、高级调度高级调度:系统进程系统进程执行执行完成完成:由作业调度由作业调度(2)完成完成完成完成退出退出:由由SPOOLing输出进程完成输出进程完成提交提交后备后备执行执行完成完成退出退出SPOOLing输入输入作业调度作业调度1作业调度作业调度2SPOOLing输出输出作业调度算法作业调度算法n适合批作业调度的算法适合批作业调度的算法n先到先服务算法先到先服务算法(FCFS)n优先数调度算法优先数调度算法(HPF)n短作业优先调度算法短作业优先调度算法(SJF)n最高响应比优先调度算法最高响应比优先调度算法(HRN)n不适合批作业调度的算法不适合批作业调度的算法n时间片轮转算法时间片轮转算法

37、(RR)n最短剩余时间优先最短剩余时间优先(SRTN)n反馈排队算法反馈排队算法(FB)3.4 实时调度实时调度(real-time scheduling)n实时实时任务：任务：n具有明确时间约束的计算任务。具有明确时间约束的计算任务。nEg.n某时刻前必须开始处理某时刻前必须开始处理n某时刻前必须处理完毕某时刻前必须处理完毕n实时调度：实时调度：n合理安排就绪实时任务的执行次序，满足每合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。个实时任务时间约束条件的调度。实时任务分类实时任务分类n硬实时硬实时 vs.软实时软实时 n硬实时硬实时(hard real-time):必须

38、满足任务截必须满足任务截止期要求止期要求.n软实时软实时(soft real-time):期望满足截止期期望满足截止期要求要求.n周期性周期性 vs.随机性随机性 n周期性周期性:每隔固定时间发生一次每隔固定时间发生一次 n随机性随机性:由随机事件触发，其发生时刻不确由随机事件触发，其发生时刻不确定定 术语解释术语解释nReady time:就绪时间就绪时间nStarting deadline:开始截止期开始截止期nProcessing time:处理时间处理时间nCompletion deadline:完成截止期完成截止期nOccurring frequency:发生频率发生频率周期性实时事

39、务周期性实时事务n周期性实时事务周期性实时事务:n令令Ci为任务为任务Pi处理时间，处理时间，Ti为任务为任务Pi的发生的发生周期，则任务周期，则任务P1,Pm可调度的必要条件为：可调度的必要条件为：周期性实时事务周期性实时事务l例：例：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 进程调度进程调度l调度发生时刻：调度发生时刻：运行进程的运行进程的counter减至减至0 0；运行进程执行系统调用运行进程执行系统调

40、用exit;运行进程因等待运行进程因等待I/O、信号灯而被封锁信号灯而被封锁;原来具有高原来具有高goodness的进程被解除封锁的进程被解除封锁.l调度效果调度效果:实时优先于分时实时优先于分时 交互和交互和I/O进程优先于进程优先于CPU进程进程 Linux 对称多处理对称多处理lLinux2.0是支持对称多处理硬件的第一个是支持对称多处理硬件的第一个Linux核心核心;进程或线程可以同时运行在多个处理机上进程或线程可以同时运行在多个处理机上.l为保持核心非剥夺同步要求，为保持核心非剥夺同步要求，SMP通过一个唯通过一个唯一的核心自旋锁一的核心自旋锁(spin-lock)来保证任何时刻最来

41、保证任何时刻最多只有一个处理机执行核心代码多只有一个处理机执行核心代码,支持真正意义上的支持真正意义上的SMP：将一个自旋锁分解为若干将一个自旋锁分解为若干个相互独立的自旋锁，分别用于保护核心代码不相个相互独立的自旋锁，分别用于保护核心代码不相交的子集交的子集.3.6.2 Windows 2000/XP线程线程调度调度nMain Features：nThread level scheduling;nReal time+foreground+background;nreal time:no deadline scheduling;nforeground:GUI windownbackground

42、:non-interactivenPreemptive+dynamic priority +RR+Feed back;nSymmetric Multi-Processor(SMP)support;优先级别优先级别n16个实时优先级（个实时优先级（16-31）n一些内核线程一些内核线程n应用程序提升为实时优先级需要有权限应用程序提升为实时优先级需要有权限n不是真正意义上的实时调度不是真正意义上的实时调度n15个可变线程优先级（个可变线程优先级（1-15）n基本优先级基本优先级 vs.当前优先级当前优先级n线程基本优先级继承进程基本优先级线程基本优先级继承进程基本优先级,可上下浮动可上下浮动2n如

43、如:进程基本优先级进程基本优先级4,其线程基本优先级其线程基本优先级26,n当前优先级在当前优先级在215范围内变动范围内变动.n可动态提升可动态提升n运行完一个运行完一个quantum之后自动下降之后自动下降,不低于基本优先级不低于基本优先级n1个系统线程优先级（个系统线程优先级（0）优先级提升优先级提升n优先级提升优先级提升nIO操作完成操作完成n事件等待结束事件等待结束n前台进程中的线程完成一个等待操作前台进程中的线程完成一个等待操作n由于窗口活动而唤醒由于窗口活动而唤醒GUI线程线程n就绪超过一定时限，未获得处理机就绪超过一定时限，未获得处理机n优先级提升不会超过优先级提升不会超过15

44、抢占抢占CPUn抢先情形抢先情形n被唤醒线程优先级高于运行线程优先级；被唤醒线程优先级高于运行线程优先级；n某线程的优先级动态变化某线程的优先级动态变化n被抢先线程被抢先线程n回到相应就绪队列回到相应就绪队列n时间配额时间配额n实时线程：重新分配完整时间配额实时线程：重新分配完整时间配额n其它线程：保持剩余配额其它线程：保持剩余配额时间配额时间配额(quantum)n配额长度：配额长度：6-36n时钟中断（时钟中断（15ms发生一次）减发生一次）减3，2-12次时钟中断（次时钟中断（30ms-180ms）配额配额用完用完n配额用完后进入就绪队列，优先级下降配额用完后进入就绪队列，优先级下降SM

45、P上的线程调度上的线程调度n线程与线程与CPU的亲合关系的亲合关系n每个进程有一个处理器亲合掩码，缺省为所每个进程有一个处理器亲合掩码，缺省为所有处理器的集合有处理器的集合n线程继承其进程的亲合掩码线程继承其进程的亲合掩码n亲合掩码可以修改亲合掩码可以修改nSetProcessAffinityMask,nSetThreadAffinityMask;SMP上的线程调度上的线程调度n线程的理想处理器（线程的理想处理器（Ideal processor）n首选处理器：首选处理器：n第二处理器：（在内核线程控制块中）第二处理器：（在内核线程控制块中）n理想处理器确定理想处理器确定n线程创建时随机确定，线

46、程创建时随机确定，n分散各个线程与处理机对应关系分散各个线程与处理机对应关系。n线程可修改线程可修改SetThreadIdealProcessor就绪线程对处理器的选择就绪线程对处理器的选择n有空闲处理器有空闲处理器n首选处理器首选处理器n第二处理器第二处理器n当前执行处理器（正执行调度代码）当前执行处理器（正执行调度代码）n由高到低顺序找空闲的处理器由高到低顺序找空闲的处理器n无空闲处理器，考虑抢先无空闲处理器，考虑抢先n首选处理器首选处理器n第二处理器第二处理器n可运行编号最大处理器可运行编号最大处理器n不能抢先进入相应的就绪队列不能抢先进入相应的就绪队列处理器对就绪线程的选择处理器对就绪

47、线程的选择n空闲处理器调度空闲处理器调度n线程上次在此线程上次在此CPU上运行（二级缓冲利用）上运行（二级缓冲利用）n线程的理想处理器是该线程的理想处理器是该CPUn处于就绪状态时间超过处于就绪状态时间超过2个个quantumn优先级别大于等于优先级别大于等于24作业作业#11.进程切换时需要保存哪些现场信息？请尽量考虑进程切换时需要保存哪些现场信息？请尽量考虑完全。完全。2.由核心返回目态程序时，进程的由核心返回目态程序时，进程的PSW和和PC为何必为何必须用一条机器指令同时恢复？须用一条机器指令同时恢复？3.对如下三个实时任务对如下三个实时任务:T1=100,C1=50;T2=200,C2=30;T3=500,C3=100.采用采用EDF算法和算法和RMS算法是否可调度算法是否可调度?如是画出对如是画出对应的应的Gantt图图,否则说明原因否则说明原因。