抢占式调度方式用于周期实时任务

抢占式调度方式用于周期实时任务 主讲人：韩成喜 教案制作：李春强课件制作：陈存衡刘永华最早截止时间优先即EDF（EarliestDeadlineFirst）算法： 根据任务的截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。 该算法既可以用于抢占式调度，也可用于非抢占式调度方式中。包括开始截止时间和完成截止时间问题描述 有两个周期性任务，任务A的周期时间为20ms，每个周期处理时间为10ms；任务B的周期时间为50ms，每个周期处理时间为25ms。两个任务的到达时间，最后期限和执行时间如下图：B2最后期限A1A3A5A4A2B1B2A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限0102030405060708090100 时间t/msA1A2A3A4A5B1B1B2B2B2B2最后期限A1A3A5A4A2B1B20102030405060708090100 时间t/msA1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限固定优先级调度（A有较高优先级）A1A2B1(错过)A4A5，B2A3这说明利用通常的固定优先级调度已经失败。t=0ms时，先调度A1执行，在A1完成后才调度B1执行t=20ms时，调度A2执行在t=30ms时，A2完成，又调度B1执行在t=40ms时，调度A3执行在t=50ms时，虽然A3完成，但B1已错过了它的最后期限在t=60ms时，A4到达调度A4执行在t=70ms时，A4完成，又调度B2执行执行在t=80ms时，A5到达，调度A5执行在t=900ms时，A5完成，又调度B2执行B2最后期限A1A3A5A4A2B1B20102030405060708090100 时间t/msA1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限B1A2A3B2A5

固定优先级调度（B有较高的优先级）A1（错过）A2B1A3A4（错过）A5,B2A1A3A5A4A2B1B2A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限B1最后期限A2B1A5A1B1A30102030405060708090100 时间t/msA4B2B2使用完成最后期限最早和最后期限调度A1A2B1A3A4A5,B2在该例中利用最早截止时间优先算法可以满足系统要求。在t=0时，A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行t=10ms时，A1完成，调度B1执行在t=20ms时，A2到达，由于A2的截止时间比B2早，B1被中断而调度A2执行在t=30ms时，A2完成，又重新调度B1执行在t=40ms时，A3又到达，但B1的截止时间比A3早，仍让B1继续执行直到完成（t=45ms时），然后调度A3执行t=55ms时，A3完成，又调度B2执行t=60ms时，A4到达，由于A4的截止时间比B2早，B2被中断而调度A4执行t=70ms时，A4完成，又重新调度B2执行t=80ms时，A5到达，由于A5和B2的截止时间相同，继续执行B2t=90ms时，B2完成，调度A5执行B2最后期限

总结:固定优先级调度（A有较高优先级）时