四川大学操作系统原理、操作系统课件 处理器调度（2）.ppt

实时调度算法的分类 常用的实时调度算法-EDF 最早截止时间优先算法：EDF （EDF：Earliest Deadline First) 根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高 可以是抢占式或非抢占式 EDF-用于非抢占式调度 3.3.3 EDF-用于抢占式调度 常用的实时调度算法-LLF 最低松弛度优先LLF算法 松弛度：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90 主要用于可抢占的调度方式中 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级 常用的实时调度算法-LLF 操作系统原理—Chapter4 进程同步与进程通信 zhumin@scu.edu.cn 5 6 D 2 8 E 4 4 C 6 2 B 3 0 A 服务时间 到达时间 进程名 FCFS 5 6 D 2 8 E 4 4 C 6 2 B 3 0 A 服务时间 到达时间 进程名 SJF 5 6 D 2 8 E 4 4 C 6 2 B 3 0 A 服务时间 到达时间 进程名 HRN 四个非周期任务，它们先后到达。 系统先调度任务1执行，在其执行期间，任务2、3又先后到达。 由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。 在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。 有两个周期性任务。 任务A的周期时间为20 ms，每个周期的处理时间为10 ms。 任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。 在t = 0 时， A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行； 在t = 10 时， A1完成，又调度B1执行； 在t = 20 时， A2到达，由于A2的截止时间比B2早，B1被中断而调度A2执行； 在t = 30 时， A2完成，又重新调度B1执行； 在t = 40 时， A3又到达，但B1的截止时间要比A3早，仍应让B1继续执行直到完成(t = 45)，然后再调度A3执行； 在t = 55 时， A3完成，又调度B2执行。 在一个实时系统中，有两个周期性实时任务A和B。 任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。 在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需10ms，可算出A1的松弛度为10ms； B1必须在50ms时完成，而它本身运行就需25ms，可算出B1的松弛度为25ms，故调度程序应先调度A1执行。 在t2=10ms时，A2的松弛度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。 t3=30ms时，A2的松弛度已减为0，B1的松弛度为15 ms，于是调度程序应抢占B1的处理机而调度A2运行…….