操作系统最低松弛度优先算法(倪健聪)

最低松弛度优先即LLF(LeastLaxityFirst)算法小组成员：倪建聪、杨贤蹬、阴晓具体分工：教案：阴晓课件制作：倪建聪课程讲解：杨贤蹬学习目标•松弛度的定义•最低松弛度优先即LLF算法的定义•实现条件•特点•实例讲解•不足松弛度松弛度就是一种优先级，它反应的是任务的紧急程度。公式：松弛度=必须完成时间-其本身运行时间-当前时间例如，此时t=0ms,一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的松弛度为200-100-0=100ms又如，此时t=100ms，一个任务在400ms时必须完成，它本身需要运行150ms，则其松弛度为400-150-100=150ms定义最低松弛度优先算法算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。条件在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。特点①主要用于抢占式调度方式。②抢占时机：松弛度为零时③实用于周期性任务的调度。实例讲解假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0A和B任务每次必须完成的时间t1t2t3t5t4t8t7t601020305040607080时刻就绪队列必须完成时间运行时间松弛度t1=0A1B1201010502525A1(10)t2=10A2B1202515401020B1(20)t3=30A2B14010050515A2(10)t4=40B1A35055601010B1(5)t1t2t3t5t4t8t7t601020305040607080A1(10)A2(10)时刻就绪队列必须完成时间运行时间松弛度B1(20)B1(5)t5=45A3B2601051002530A3(10)t6=55B21002520B2(15)t7=70A4B2801001001020A4(10)t8=80B21001010B2(10)A51001010不足当多个任务松弛度值接近时，算法造成任务之间的频繁切换或颠簸现象，增大了系统因调度引起的开销，限制了调度算法的实际应用。须寻找合理的任务执行时间片谢谢(*^__^*)