中断与处理器调度.ppt

3.3.2作业与高级调度状态转换:提交?后备:由SPOOLing输入进程完成SimultaneousPeripheralOperationOn-Line后备?执行:由作业调度(1)(高级调度)完成高级调度:系统进程执行?完成:由作业调度(2)完成完成?退出:由SPOOLing输出进程完成提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出适合批作业调度的算法01先到先服务算法(FCFS)02优先数调度算法(HPF)03短作业优先调度算法(SJF)04最高响应比优先调度算法(HRN)05不适合批作业调度的算法06时间片轮转算法(RR)07最短剩余时间优先(SRTN)08反馈排队算法(FB)09作业调度算法3.4实时调度(real-timescheduling)实时任务：1具有明确时间约束的计算任务。2Eg.3某时刻前必须开始处理4某时刻前必须处理完毕5实时调度：6合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。71硬实时vs.软实时2硬实时(hardreal-time):必须满足任务截止期要求.3软实时(softreal-time):期望满足截止期要求.6随机性:由随机事件触发，其发生时刻不确定5周期性:每隔固定时间发生一次4周期性vs.随机性实时任务分类Completiondeadline:完成截止期04Occurringfrequency:发生频率05Processingtime:处理时间03Startingdeadline:开始截止期02Readytime:就绪时间01术语解释周期性实时事务周期性实时事务:令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,…,Pm可调度的必要条件为：T1=100,T2=200,T3=500(ms)01C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.85103C1=50,C2=30,C3=100(ms)02满足可调度的必要条件04例：周期性实时事务吞吐量;(max)系统开销;(min)考虑因素（schedulingcriteria）CPU利用率;(max)响应时间;(min)周转时间;(min)0203040506013.2.1处理机调度算法周转时间：完成时间-进入时间带权周转时间：周转时间/运行时间平均周转时间：周转时间的平均值平均带权周转时间：带权周转时间的平均值调度参数CPUburstvs.I/Oburst阵发期:CPUburstcycle:进程(线程)使用CPU计算；I/Oburstcycle:进程(线程)使用设备I/O。进程运行行为：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU调度：考虑处于CPUburst进程集合CPUburst时间根据以前行为推定。CPUburstvs.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。通常α取0.5。剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。进程运行,直到结束或等待剥夺式调度与非剥夺式调度3.2.1.1先到先服务算法FCFS（FirstComeFirstServe)按进程申请CPU（就绪）的次序。ProcessArrivaltimeBursttimeP1027P213P325CPU调度状况可用Gantt图表示．0273035P1P2P33.2.1.1