《中断与处理机调度》PPT课件

《《中断与处理机调度》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2处理机调度3.2.1处理机调度算法按什么原则分配3.2.2处理机调度时机何时重新分配3.2.3处理机调度过程如何完成分配scheduling3.2.1处理机调度算法考虑因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周转时间;(min)响应时间;(min)系统开销;(min)调度参数周转时间：完成时间-进入时间平均周转时间：周转时间的平均值带权周转时间：周转时间/运行时间平均带权周转时间：带权周转时间的平均值CPUburstvs.I/Oburst阵发期:CPUburstcycle:进程(线程)使用CPU计算；I/Oburstcycle

2、:进程(线程)使用设备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)就绪

3、进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。进程运行,直到结束或等待3.2.1.1先到先服务算法FCFS（FirstComeFirstServe)按进程申请CPU（就绪）的次序。ProcessArrivaltimeBursttimeP1027P213P325CPU调度状况可用Gantt图表示．0273035P1P2P33.2.1.1先到先服务算法(Cont.)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1027027271P2132730299.67P3253035

4、336.6平均周转时间=(27+29+33)/3=29.67平均带权周转时间=(1+9.67+6.6)/3=5.760273035P1P2P33.2.1.1先到先服务算法(Cont.)优点：“公平”；缺点:短作业等待时间长。3.2.1.2短作业优先SJF（ShortestJobFirst)按CPUburst长度ProcessArrivaltimeBursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作业优先0381527P1P2P3P4进程到达时间运行时间开始时间完成时间周转时间带权周转时间P10121527272

5、.25P2053881.6P307815152.14P4030331平均周转时间=(27+8+15+3)/4=13.25平均带权周转时间=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作业优先特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。3.2.1.3最短剩余时间优先算法(SRTN)ShortestRemainingTimeNext可剥夺SJFProcessArrivaltimeBursttimeP1012P219P336P453Gantt图P1P2P3P4P3P2P1013581219303.2.1.3最短剩余时间优先算法(Cont.)进程

6、到达时间运行时间开始时间完成时间周转时间带权周转时间P1012030302.5P219119182P33631291.5P4535831平均周转时间=(30+18+9+3)/4=15平均带权周转时间=(2.5+2+1.5+1)/4=1.75平均等待时间＝(18+9+3+0)/4＝7.5(ms)P1P2P3P4P3P2P1013581219303.2.1.4最高响应比优先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime优点:同时到达任务,短者优先长作业随等待时间增加响应比增加3

7、.2.1.5最高优先数算法(HPF)静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以修改。响应速度快，开销大。适用于实时系统3.2.1.5最高优先数算法(Cont.)非剥夺式优先数获得处理机的进程运行，直至终止等待剥夺式优先数获得处理机的进程运行，直至终止等待出现高优先级的进程3.2.1.5最高优先数算法(Cont.)可抢占CPUProcessArrivaltimePriority