操作系统最低松弛性算法

该算法根据任务紧急(或松弛)的程度，确定任务优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。主要用于可抢占调度方式。与任务的完成截止时间密切相关。任务的松弛度=必须完成时间-其本身的运行时间-当前时间系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在最前面，调度程序总是选择就绪队列中的队首任务执行。图3-7A和B任务每次必须完成的时间A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0图3-8利用LLF算法进行调度的情况t1A1(10)10203040506080t0t1＝0B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)t1=0，A1须在20ms完成，运行10ms，松弛度为10ms；B1须在50ms完成，运行25ms，松弛度为25ms，调度A1。t2=10，A2的松弛度=必须完成时间-其本身的运行时间-当前时间=40ms-10ms-10ms=20ms；类似求出B1松弛度为15ms，调度B1。t3＝30时，A2松弛度减为0，B1的松弛度为15ms（即50-5-30），A2抢占B1处理机t4=40，A3松弛度为10（即60-10-40），B1松弛度为5（即50-5-40），重新调度B1执行。t5＝45，B1完成，A3松弛度减为5（即60-10-45），B2松弛度为30（即100-25-45），调度A3执行。t6＝55，任务A未进入第4周期，B已进入第2周期，故再调度B2执行。t7＝70，A4松弛度减至0（80-10-70），B2松弛度为20（100-10-70），A4抢占B2处理机执行。任务A每20ms执行一次，执行时间为10ms；任务B每50ms执行一次，执行时间为25ms。例：假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25msA1A2A3A4A5A6A7A820406080100120140160B1B2B3t0图3-8A和B任务每次必须完成的时间t1A1(10)10203040506080t0t1＝0B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)图3-9利用ELLF算法进行调度的情况End！