中断与处理器调度课件.ppt
94页
第三章第三章 中断与处理机调度中断与处理机调度n3.1 中断与中断系统中断与中断系统n3.2 处理机调度处理机调度n3.3 调度级别与多级调度调度级别与多级调度n3.4 实时调度实时调度n3.5 多处理机调度多处理机调度n3.6 系统举例系统举例 操作系统是中断驱动的！操作系统是中断驱动的！Interrupt driven中断与处理器调度 3.1 中断与中断系统中断与中断系统n3.1.1 中断的概念中断的概念n3.1.2 中断装置中断装置n3.1.3 中断处理程序中断处理程序中断与处理器调度 3.1.1 中断的概念中断的概念n处理机在运行过程中，出现了某一事件，处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，个事件，然后再返回原来运行的程序，这一过程称为中断这一过程称为中断n中断系统：中断系统：n中断装置中断装置(硬件硬件)n中断处理程序中断处理程序(软件软件)中断与处理器调度 3.1.2 中断装置中断装置n发现并响应中断的硬件机构发现并响应中断的硬件机构n识别中断源，当有多个中断源时，按紧迫程识别中断源，当有多个中断源时，按紧迫程度排队；度排队；n保存现场；保存现场；n引出中断处理程序。
引出中断处理程序中断与处理器调度 中断响应和处理的过程中断响应和处理的过程正正运运行行程程序序 1 6处处理理程程序序 4PSW’，，PC’PC’:PSW, PC系统桟系统桟psw, pc……...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缺页缺页n溢出，除溢出，除0n非法指令非法指令n自愿性中断自愿性中断n运行程序期望的运行程序期望的n系统调用系统调用n访管指令访管指令n系统调用系统调用nfd=open(fname,mode)n访管指令访管指令n准备参数准备参数nsvc nn取返回值取返回值中断与处理器调度 3.1.2.2 中断类型与中断向量中断类型与中断向量中断装置中断装置 中断处中断处 理程序理程序运行程序运行程序访管指令访管指令运行程序运行程序中断装置中断装置 中断处中断处 理程序理程序clockIOconsolePowerfailuremalfunction强迫中断强迫中断：：自愿中断自愿中断：：SVC ntrap n中断与处理器调度 3.1.2.2 中断类型与中断向量中断类型与中断向量n中断向量：中断处理程序的运行环境与中断向量：中断处理程序的运行环境与入口地址（入口地址（PSW，，PC））n每类中断事件有一个中断向量每类中断事件有一个中断向量,n中断向量的存放位置是由硬件规定的中断向量的存放位置是由硬件规定的,n中断向量的内容是中断向量的内容是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 中断嵌套与系统栈中断嵌套与系统栈n一般原则：一般原则：n高优先级别中断可以嵌入低优先级中断高优先级别中断可以嵌入低优先级中断n实现方法：实现方法：n中断响应后立即屏蔽不高于当前中断优先级中断响应后立即屏蔽不高于当前中断优先级的中断源的中断源中断与处理器调度 3.1.2.3 中断嵌套与系统栈中断嵌套与系统栈中断响应后一般需要进一步保存现场中断响应后一般需要进一步保存现场中断响应后一般需要进一步保存现场中断响应后一般需要进一步保存现场 关中断关中断（屏蔽所有中断）（屏蔽所有中断） 进一步保存现场（通用寄存器等）进一步保存现场（通用寄存器等） 开中断开中断（或开放高优先级中断）（或开放高优先级中断） …... 中断处理中断处理 …... 关中断关中断（屏蔽所有中断）（屏蔽所有中断） 恢复现场恢复现场 开中断开中断（或开放高优先级中断）（或开放高优先级中断） 中断返回中断返回中断与处理器调度 3.1.2.3 中断嵌套与系统栈中断嵌套与系统栈(Cont.)……目态目态PSW1: PC1……管态管态PSW2: PC2……管态管态PSWn: PCn…中断嵌套中断嵌套:……中断与处理器调度 3.1.2.3 中断嵌套与系统栈中断嵌套与系统栈(Cont.)……PSWn-1 PCn-1……PSW2 PC2PSW1 PC1栈顶指针栈顶指针:系统栈系统栈:中断与处理器调度 3.1.2.4 中断优先级与中断屏蔽中断优先级与中断屏蔽n中断优先级：中断优先级：n硬件规定的中断响应次序，依据硬件规定的中断响应次序，依据:n紧迫程度；紧迫程度；n处理时间。
处理时间n中断屏蔽：中断屏蔽：n高优先级中断事件处理不受低优先级中断打高优先级中断事件处理不受低优先级中断打扰；扰；n程序调整中断响应次序程序调整中断响应次序中断与处理器调度 3.1.3 中断处理程序中断处理程序强迫性中断强迫性中断自愿性中断自愿性中断保存现场信息保存现场信息取中断字取中断字分析中断原因分析中断原因保存现场信息保存现场信息取调用号取调用号分析何种系统调用分析何种系统调用 中断处理中断处理（如等待转（如等待转dispatcher) 继续处理继续处理 嵌套中断嵌套中断系统栈恢复现场系统栈恢复现场返回上层中断返回上层中断需要切换进程需要切换进程系统栈恢复现场系统栈恢复现场返回目态程序返回目态程序转转dispatcherTFFT中断与处理器调度 3.1.3.1 IO中断处理中断处理n正常结束正常结束n继续传输；继续传输；n唤醒相关进程唤醒相关进程n传输错误传输错误n复执（复执（eg. 3次次)；；n报告系统操作员报告系统操作员中断与处理器调度 3.1.3.2 时钟中断处理时钟中断处理nHousekeepingn进程管理进程管理n重新计算进程调度参数重新计算进程调度参数(eg. 动态优先数动态优先数)n实现软时钟，启动定时程序实现软时钟，启动定时程序n硬时钟硬时钟5ms发生一次中断，软时钟发生一次中断，软时钟50msn考虑进程切换考虑进程切换中断与处理器调度 3.1.3.3 控制台中断处理控制台中断处理n一个控制按钮，一个中断向量，一个中一个控制按钮，一个中断向量，一个中断处理程序。
断处理程序中断与处理器调度 3.1.3.4 硬件故障处理硬件故障处理n电源故障处理电源故障处理n掉电：掉电：n内存，寄存器内存，寄存器外存外存n停止设备停止设备n停止处理机停止处理机n恢复：恢复：n启动处理机启动处理机n启动设备启动设备n外存外存内存，寄存器内存，寄存器 Use UPS for criticalapplications中断与处理器调度 3.1.3.4 硬件故障处理硬件故障处理(cont.)n内存故障处理内存故障处理n海明校验，奇偶校验错误海明校验，奇偶校验错误n划出系统划出系统n报告操作员报告操作员中断与处理器调度 3.1.3.5 程序性中断的处理程序性中断的处理n只能由操作系统处理的中断只能由操作系统处理的中断n影响系统或其它进程影响系统或其它进程n越界，非法指令，（处理：终止进程、调试）越界，非法指令，（处理：终止进程、调试）n需要系统管理或协助需要系统管理或协助n页故障，缺段，（处理：动态调入）页故障，缺段，（处理：动态调入）n可以由用户自己处理的中断可以由用户自己处理的中断n不影响系统和其它进程不影响系统和其它进程n除除0，溢出，（处理：用户处理，或，溢出，（处理：用户处理，或OS处理）处理）中断与处理器调度 应用程序自己处理中断应用程序自己处理中断调试语句：调试语句：on <中断条件中断条件> <中断续元入口中断续元入口>例如：例如：on
运行时：执行调试语句，填写中断续元表中断时：根据中断原因查中断续元表，中断时：根据中断原因查中断续元表， 为为0，用户未规定中断续元，由，用户未规定中断续元，由OS标准处理；标准处理； 非非0，用户已规定中断续元，由用户处理用户已规定中断续元，由用户处理初始时均为初始时均为0中断与处理器调度 n步骤：步骤：n（（1）发生溢出中断）发生溢出中断n（（2）保存旧）保存旧PSW和和PCn（（3）取中断向量）取中断向量n（（4）转到中断处理程序）转到中断处理程序n（（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) 参数和返回值和存放位置是由参数和返回值和存放位置是由OS规定的。
规定的中断与处理器调度 3.1.3.6 自愿性中断的处理自愿性中断的处理系统调用驱动表：系统调用驱动表：(table driven)服务程序入口服务程序入口addr0…………addrm-1访管号：访管号：0……...m-1Eg. UNIX中断与处理器调度 3.2 处理机调度处理机调度n3.2.1 处理机调度算法处理机调度算法n按什么原则分配按什么原则分配n3.2.2 处理机调度时机处理机调度时机n何时重新分配何时重新分配n3.2.3 处理机调度过程处理机调度过程n如何完成分配如何完成分配中断与处理器调度 3.2.1 处理机调度算法处理机调度算法n考虑因素（考虑因素（scheduling criteria））nCPU利用率利用率 ; (max)n吞吐量吞吐量 ; (max)n周转时间周转时间 ; (min)n响应时间响应时间 ; (min)n系统开销系统开销 ; (min)中断与处理器调度 调度参数周转时间：完成时间周转时间：完成时间-进入时间进入时间平均周转时间：周转时间的平均值平均周转时间：周转时间的平均值带权周转时间：周转时间带权周转时间：周转时间/运行时间运行时间平均带权周转时间：带权周转时间的平均值平均带权周转时间：带权周转时间的平均值中断与处理器调度 CPU burst vs. I/O burst n阵发期阵发期 :nCPU burst cycle: 进程进程(线程线程)使用使用CPU计算；计算；nI/O burst cycle: 进程进程(线程线程)使用设备使用设备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阵发期长度，则有阵发期长度，则有如下估算公式：如下估算公式：nτn+1=αtn + (1-α)τnn参数参数α(0≤α≤1)控制控制tn和和τn在公式中起的作用：在公式中起的作用：当当α=0时，时，τn+1=τn；当；当α=1时，时，τn+1=tn通常通常α取取0.5中断与处理器调度 剥夺式调度与非剥夺式调度剥夺式调度与非剥夺式调度n剥夺式剥夺式(preemptive)n就绪进程就绪进程可以可以从运行进程手中从运行进程手中抢占抢占CPUn进程运行进程运行,直到结束、等待或被抢先直到结束、等待或被抢先n非剥夺式非剥夺式(non-preemptive)n就绪进程就绪进程不可不可从运行进程手中从运行进程手中抢占抢占CPU。
n进程运行进程运行,直到结束或等待直到结束或等待中断与处理器调度 3.2.1.1 先到先服务算法先到先服务算法nFCFS（（First Come First Serve)n按进程申请按进程申请CPU（就绪）的次序就绪）的次序nProcess Arrival time Burst timenP1 0 27nP2 1 3nP3 2 5nCPU调度状况可用调度状况可用Gantt 图表示图表示．0 27 30 35P1P2P3中断与处理器调度 3.2.1.1 先到先服务算法先到先服务算法(Cont.)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P1027027271P2132730299.67P3253035336.6平均周转时间平均周转时间 =(27+29+33)/3=29.67 平均带权周转时间平均带权周转时间 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P3中断与处理器调度 3.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 27P1P2P3P4中断与处理器调度 3.2.1.2 短作业优先短作业优先0 3 8 15 27P1P2P3P4进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P10121527272.25P2053881.6P307815152.14P4030331平均周转时间平均周转时间 =(27+8+15+3)/4=13.25 平均带权周转时间平均带权周转时间 =(2.25+1.6+2.14+1)/4=1.75中断与处理器调度 3.2.1.2 短作业优先短作业优先n特点：特点：n假定所有任务同时到达，平均等待假定所有任务同时到达，平均等待时间最短。
时间最短n长作业可能被饿死长作业可能被饿死中断与处理器调度 3.2.1.3最高响应比优先最高响应比优先(HRN)nHighest 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进程创建时继承优先数，生存期内可以修改进程创建时继承优先数，生存期内可以修改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 3 7nP4 0 2 3nP5 5 7 2nGantt Chart0 0 3 3 4 4 5 5 7 7 13 13 17 17 2525P1P4P2P2P3P3P5中断与处理器调度 3.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 0 3 3 4 4 5 5 7 7 13 13 17 17 2525P1P4P2P2P3P3P5中断与处理器调度 3.2.1.4 最高优先数算法最高优先数算法(Cont.)n例子例子UNIX：：preemptive+dynamic priority（可抢占（可抢占CPU动态优先数）。
动态优先数）n计算公式：计算公式：p_pri=min{127, USER+p_cpu/16+p_nice}n定义定义USER=100；；np_cpu: 运行进程每运行进程每20ms加加1（优先级降低），其（优先级降低），其它进程每它进程每1200ms减减10（优先级提高）；（优先级提高）；np_nice: 可以通过系统调用可以通过系统调用nice(…)修改的量：规修改的量：规定用户进程定用户进程0~20之间（低），系统进程之间（低），系统进程-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时间片长度：时间片长度： 几十毫秒几十毫秒 几百毫秒几百毫秒(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 Remaining Time Nextn可剥夺可剥夺SJFnProcess Arrival time Burst timen P1 0 12n P2 1 5n P3 3 7n P4 5 3nGantt图0 1 6 9 16 27P1P2P3P1P4中断与处理器调度 3.2.1.7 最短剩余时间优先最短剩余时间优先(SRTN)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P1012027272.25P2151651P337916131.86P4536941.33平均周转时平均周转时 =(27+5+13+4)/4=12.25平均带权周转时间平均带权周转时间 =(2.25+1+1.86+1.33)=1.61 0 1 6 9 16 27P1P2P3P1P4中断与处理器调度 3. 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被唤醒被唤醒, 进进入最高级队列入最高级队列, 可尽早投入运行可尽早投入运行, 使用资源使用资源R；；n 响应速度快响应速度快n交互式进程经常进入等待状态交互式进程经常进入等待状态(等待用户输入等待用户输入),一旦被唤醒一旦被唤醒(输入完成输入完成),进入最高级队列进入最高级队列,可尽快被调度选中可尽快被调度选中,投入运行投入运行,反应及时；反应及时；n 系统开销小系统开销小n计算量大的进程用完前面计算量大的进程用完前面n-1级时间片级时间片,没有处理完没有处理完,落入底落入底层队列层队列,调度频率下降调度频率下降,但每次获得较长的时间片但每次获得较长的时间片。
中断与处理器调度 3.2.2 处理机调度时机处理机调度时机l运行进程结束；运行进程结束；l运行进程等待；运行进程等待；l处理机被剥夺处理机被剥夺目态（目态（Pi运行）运行）目态（目态（Pj运行）运行）管态管态管态管态…...中断中断中断中断中断中断返回返回返回返回返回返回Pi=Pj: 未发生进程切换；未发生进程切换；Pi<>Pj: 发生了进程切换发生了进程切换中断与处理器调度 3.2.2 处理机调度时机处理机调度时机(Cont.)l必然引起进程切换的中断必然引起进程切换的中断–进程自愿结束进程自愿结束, exit()–进程进程被强行终止；被强行终止；l非法非法指令，越界，指令，越界，kill–进程等待进程等待l可能引起进程切换的中断可能引起进程切换的中断–时钟时钟–系统调用系统调用中断与处理器调度 3.2.3 处理机调度过程处理机调度过程ldispatcherl保存下降进程的现场保存下降进程的现场–寄存器寄存器(PSW,PC,SP,通用寄存器通用寄存器,地址寄存器地址寄存器)PCBl选择上升进程选择上升进程–按处理机调度算法按处理机调度算法l恢复上升进程的现场恢复上升进程的现场–PCB 寄存器寄存器–先恢复通用寄存器和地址寄存器先恢复通用寄存器和地址寄存器,最后恢复最后恢复PSW,PC–PSW和和PC必须用一条指令恢复必须用一条指令恢复中断与处理器调度 3.3 调度级别与多级调度调度级别与多级调度n3.3.1 交换与中级调度交换与中级调度nS and mid-level schedulingn3.3.2 作业与高级调度作业与高级调度nJob and high-level scheduling处理机调度为低级调处理机调度为低级调度度CPU scheduling = low level scheduling中断与处理器调度 3.3.1 交换与中级调度交换与中级调度n术语术语n交换交换(s)n中级调度中级调度(mid-level scheduling)n并发度并发度(degree of multi-programming)n目标：控制并发度目标：控制并发度n并发度过高并发度过高n系统开销大系统开销大n响应速度慢响应速度慢n内存等资源紧张内存等资源紧张n进程进程(线程线程)频繁进入等待状态频繁进入等待状态nMore deadlocks中断与处理器调度 3.3.1 交换与中级调度交换与中级调度剥夺剥夺就绪就绪等待等待运行运行 选中选中等待事件等待事件事件发生事件发生就绪就绪挂起挂起等待等待挂起挂起无无终止终止创建创建创建创建结束结束换出换出换出换出换入换入换入换入事件发生事件发生中断与处理器调度 UNIX的中级调度（的中级调度（sched #0)n移入移入SRUN状态进程状态进程n如内存不够，如内存不够，n移出移出SWAIT和和SSTOP状态进程；状态进程；n如还不够，移出如还不够，移出SSLEEP和和SRUN状态进程；状态进程；n条件：条件：n待移入进程在外存时间待移入进程在外存时间>=3秒；秒；n待移出进程在内存时间待移出进程在内存时间>=2秒。
秒中断与处理器调度 3.3.2 作业与高级调度作业与高级调度n作业状态作业状态:n提交提交: 输入机向输入井传送输入机向输入井传送n后备后备: 在输入井在输入井,尚未进入内存尚未进入内存n执行执行: 分解为进程分解为进程,在内存处理在内存处理n完成完成: 处理完毕处理完毕,结果在输出井结果在输出井n退出退出: 由输出井向打印机传送由输出井向打印机传送中断与处理器调度 3.3.2 作业与高级调度作业与高级调度l状态转换状态转换:–提交提交后备后备: 由由SPOOLing输入进程完成输入进程完成–Simultaneous Peripheral Operation On-Line–后备后备执行执行: 由作业调度由作业调度(1)(高级调度高级调度)完成完成–高级调度高级调度: 系统进程系统进程–执行执行完成完成: 由作业调度由作业调度(2)完成完成–完成完成退出退出: 由由SPOOLing输出进程完成输出进程完成提交提交后备后备执行执行完成完成退出退出SPOOLing输入输入作业调度作业调度1作业调度作业调度2SPOOLing输出输出中断与处理器调度 作业调度算法作业调度算法n适合批作业调度的算法适合批作业调度的算法n先到先服务算法先到先服务算法(FCFS)n优先数调度算法优先数调度算法(HPF)n短作业优先调度算法短作业优先调度算法(SJF)n最高响应比优先调度算法最高响应比优先调度算法(HRN)n不适合批作业调度的算法不适合批作业调度的算法n时间片轮转算法时间片轮转算法(RR)n最短剩余时间优先最短剩余时间优先(SRTN)n反馈排队算法反馈排队算法(FB)中断与处理器调度 3.4 实时调度实时调度(real-time scheduling)n实时任务：实时任务：n具有明确时间约束的计算任务。
具有明确时间约束的计算任务nEg.n某时刻前必须开始处理某时刻前必须开始处理n某时刻前必须处理完毕某时刻前必须处理完毕n实时调度：实时调度：n合理安排就绪实时任务的执行次序，满足每合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度个实时任务时间约束条件的调度中断与处理器调度 实时任务分类实时任务分类n硬实时硬实时 vs. 软实时软实时 n硬实时硬实时(hard real-time): 必须满足任务截必须满足任务截止期要求止期要求 . n软实时软实时(soft real-time): 期望满足截止期期望满足截止期要求要求 . n周期性周期性 vs. 随机性随机性 n周期性周期性: 每隔固定时间发生一次每隔固定时间发生一次 n随机性随机性: 由随机事件触发，其发生时刻不确由随机事件触发，其发生时刻不确定定 中断与处理器调度 术语解释术语解释nReady time: 就绪时间就绪时间nStarting deadline: 开始截止期开始截止期nProcessing time: 处理时间处理时间nCompletion deadline: 完成截止期完成截止期nOccurring frequency: 发生频率发生频率中断与处理器调度 周期性实时事务周期性实时事务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.85<1–满足可调度的必要条件满足可调度的必要条件中断与处理器调度 周期性实时事务周期性实时事务进程进程就绪时间就绪时间处理时间处理时间完成截止期完成截止期发生周期发生周期A0102020B025505010/20 + 25/50 = 1, 可调度可调度(不考虑开销不考虑开销)中断与处理器调度 例子例子Process Arrival time Execution time completion deadline A(1)A(2)A(3)A(4)A(5)…...B(1)B(2)020406080…...0501010101010……252520406080100…...50100中断与处理器调度 3.4.1 最早截止期调度最早截止期调度nEDF（（Earliest Deadline First)n优先选择截止期最早的实时任务优先选择截止期最早的实时任务n可抢先可抢先n可以证明：对可以证明：对EDF来说，可调度充分条件是：来说，可调度充分条件是：n在不可调度的条件下，可使错过截止期任务最在不可调度的条件下，可使错过截止期任务最小化小化中断与处理器调度 例子: Earliest Deadline First0 10 20 30 40 50 60 70 80 90 100 TimeA2A2 dlA3A3 dlA4A4 dlB1A1A1dlB1 dlB2B2 dlA5A5 dlA1B1A2B1A3B2A5B2 A4A1 A2 B1 A3 A4 A5B2中断与处理器调度 3.4.2 速率单调调度速率单调调度nRMS（（Rate Monotonic Scheduling））n提出于提出于1973年年n面向周期性实时事务，非剥夺式面向周期性实时事务，非剥夺式n优先调度发生周期最短（频度最高）的实时任务优先调度发生周期最短（频度最高）的实时任务n可调度条件：可调度条件：中断与处理器调度 RMS的上限值的上限值n1 12 23 34 45 56 6┇┇ 1.01.00.8280.8280.7790.7790.7560.7560.7430.7430.7340.734┇┇ln2 2 0.6930.693RMS vs. EDF1)RMS可调度条件强于可调度条件强于EDF2)RMS调度较调度较EDF实现简实现简单单中断与处理器调度 RMS例子：进程ＴiCiA10020B15040C350100可调度，具体调度结果：A1B1C1A2B2A3A4B3C20 20 60 160 180 220 240 300 320 360 460中断与处理器调度 3.5 多处理机调度多处理机调度n问题：问题：nM processes (threads)nN processorsnSMP：：symmetric multi-processorsnall processors are identical (homogeneous)n目标：目标：load-sharingnseparate ready queue for each processor, nnot really balanced;ncommon ready queue Q for all processorsneach processor accesses Q on its own,nmaster/slave assignment.中断与处理器调度 3.5.1 自调度自调度(self scheduling)n均衡调度均衡调度(balanced scheduling)n一个就绪队列一个就绪队列(多处理机访问互斥多处理机访问互斥)n优点优点n不需要专门的处理机从事任务分派工作不需要专门的处理机从事任务分派工作n任务分配均衡任务分配均衡n缺点缺点n当当CPU较多时较多时,就绪队列成为瓶颈就绪队列成为瓶颈n线程两次调度可能处于不同处理机线程两次调度可能处于不同处理机n不能保证同组线程同时调度不能保证同组线程同时调度中断与处理器调度 自调度自调度(self scheduling)就绪队列就绪队列进程进程(线程线程)进程进程(线程线程)进程进程(线程线程)CPUCPUCPU中断与处理器调度 自调度自调度(self scheduling)n例子例子:nMach, 改进的自调度改进的自调度n全局队列全局队列:系统一个系统一个n局部队列局部队列:每个每个CPU一个一个n调度时调度时n首先考虑局部队列首先考虑局部队列n然后考虑全局队列然后考虑全局队列中断与处理器调度 3.5.2 组调度组调度(gang scheduling)n将一组相关将一组相关(合作合作)的线程的线程同时同时分派到多分派到多个处理机上运行个处理机上运行n避免合作线程之间的相互等待避免合作线程之间的相互等待n降低开销降低开销,提高运行效率提高运行效率n例子例子:nCm*nTask force (一组相关的计算一组相关的计算)中断与处理器调度 3.6 系统举例系统举例nLinux进程调度进程调度nWindows2000/XP线程调度线程调度nUNIX进程调度（见第进程调度（见第12章）章）中断与处理器调度 n三种特征进程三种特征进程 nReal-time FIFOnReal-time Round RobinnTimesharingnGoodness-based schedulingnpriorityn0-40, (缺省值缺省值20 ),可通过可通过nice系统调用调整系统调用调整 ，，nice(value)中中value的取值范围为的取值范围为(-20,20)之间之间 ,取取priority=20-value. ncountern进程尚可运行的剩余时间进程尚可运行的剩余时间 3.6.1 Linux 进程调度进程调度中断与处理器调度 Linux 进程调度进程调度–counterl对于运行进程来说，每个时钟间隔对于运行进程来说，每个时钟间隔( (10ms，，称为一个称为一个jiffy) )，，将将counter减减1 l当所有就绪进程的当所有就绪进程的counter配额下降到配额下降到0时，重新计算时，重新计算所有进程所有进程( (包括等待进程包括等待进程) )的的counter值值 –counter= (counter/2) + priority–goodnesslif(Real-time)goodness=1000+prioritylif(Timesharing && counter=0)goodness=0lif(Timesharing && counter>0)goodness=counter+priority中断与处理器调度 Linux 进程调度进程调度l调度发生时刻：调度发生时刻： –运行进程的运行进程的counter减至减至0 0；； –运行进程执行系统调用运行进程执行系统调用exit ;–运行进程因等待运行进程因等待I/O、、信号灯而被封锁信号灯而被封锁 ;–原来具有高原来具有高goodness的进程被解除封锁的进程被解除封锁 .l调度效果调度效果 :–实时优先于分时实时优先于分时 –交互和交互和I/O进程优先于进程优先于CPU进程进程 中断与处理器调度 Linux 对称多处理对称多处理lLinux2.0是支持对称多处理硬件的第一个是支持对称多处理硬件的第一个Linux核心核心 ; –进程或线程可以同时运行在多个处理机上进程或线程可以同时运行在多个处理机上 .l为保持核心非剥夺同步要求，为保持核心非剥夺同步要求，SMP通过一个唯通过一个唯一的核心自旋锁一的核心自旋锁( (spin-lock) )来保证任何时刻最来保证任何时刻最多只有一个处理机执行核心代码多只有一个处理机执行核心代码, –支持真正意义上的支持真正意义上的SMP：：将一个自旋锁分解为若干将一个自旋锁分解为若干个相互独立的自旋锁，分别用于保护核心代码不相个相互独立的自旋锁，分别用于保护核心代码不相交的子集交的子集 .中断与处理器调度 3.6.2 Windows 2000/XP线程线程调度调度nMain Features：：nThread level scheduling;nReal time + foreground + background;nreal time: no deadline scheduling;nforeground: GUI windownbackground: 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如如: 进程基本优先级进程基本优先级4, 其线程基本优先级其线程基本优先级2—6, n当前优先级在当前优先级在2—15范围内变动范围内变动.n可动态提升可动态提升n运行完一个运行完一个quantum之后自动下降之后自动下降, 不低于基本优先级不低于基本优先级n1个系统线程优先级（个系统线程优先级（0））中断与处理器调度 优先级提升优先级提升n优先级提升优先级提升nIO操作完成操作完成n事件等待结束事件等待结束n前台进程中的线程完成一个等待操作前台进程中的线程完成一个等待操作n由于窗口活动而唤醒由于窗口活动而唤醒GUI线程线程n就绪超过一定时限，未获得处理机就绪超过一定时限，未获得处理机n优先级提升不会超过优先级提升不会超过15中断与处理器调度 抢占抢占CPUn抢先情形抢先情形n被唤醒线程优先级高于运行线程优先级；被唤醒线程优先级高于运行线程优先级；n某线程的优先级动态变化某线程的优先级动态变化n被抢先线程被抢先线程n回到相应就绪队列回到相应就绪队列n时间配额时间配额n实时线程：重新分配完整时间配额实时线程：重新分配完整时间配额n其它线程：保持剩余配额其它线程：保持剩余配额中断与处理器调度 时间配额时间配额(quantum)n配额长度：配额长度：6--36n时钟中断（时钟中断（15ms发生一次）减发生一次）减3，，2--12次时钟中断（次时钟中断（30ms--180ms）配额）配额用完用完n配额用完后进入就绪队列，优先级下降配额用完后进入就绪队列，优先级下降中断与处理器调度 SMP上的线程调度上的线程调度n线程与线程与CPU的亲合关系的亲合关系n每个进程有一个处理器亲合掩码，缺省为所每个进程有一个处理器亲合掩码，缺省为所有处理器的集合有处理器的集合n线程继承其进程的亲合掩码线程继承其进程的亲合掩码n亲合掩码可以修改亲合掩码可以修改nSetProcessAffinityMask, nSetThreadAffinityMask;中断与处理器调度 SMP上的线程调度上的线程调度n线程的理想处理器（线程的理想处理器（Ideal processor））n首选处理器：首选处理器：n第二处理器：（在内核线程控制块中）第二处理器：（在内核线程控制块中）n理想处理器确定理想处理器确定n线程创建时随机确定，线程创建时随机确定，n分散各个线程与处理机对应关系。
分散各个线程与处理机对应关系n线程可修改线程可修改SetThreadIdealProcessor中断与处理器调度 就绪线程对处理器的选择就绪线程对处理器的选择n有空闲处理器有空闲处理器n首选处理器首选处理器n第二处理器第二处理器n当前执行处理器（正执行调度代码）当前执行处理器（正执行调度代码）n由高到低顺序找空闲的处理器由高到低顺序找空闲的处理器n无空闲处理器，考虑抢先无空闲处理器，考虑抢先n首选处理器首选处理器n第二处理器第二处理器n可运行编号最大处理器可运行编号最大处理器n不能抢先进入相应的就绪队列不能抢先进入相应的就绪队列中断与处理器调度 处理器对就绪线程的选择处理器对就绪线程的选择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图图,否则说明原因否则说明原因。
