LLF算法2.0.ppt

实时任务的类型： 按任务执行时是否呈现周期性来划分： 周期性实时任务：每隔一段固定的时间发生 非周期性实时任务：在不可预测的时间发生。 根据对截止时间的要求来划分： 硬实时任务(HRT)：系统必须在用户给定的时限内完成。 软实时任务(SRT):可以容忍偶尔超过时间限制。 实时调度的概念及实现实时调度的基本条件 EDF算法的缺点 EDF算法虽然能对调度负载有所优化，但是它不能解决过载问题。发生过载时，EDF算法性能就会急剧退化。 EDF算法只考虑了截止期，没有考虑任务执行时间，当一个任务由于截止期的临近被调度，然而此时任务执行所需要的时间已超出了截止期，即任务就算被调度也来不及在截止期前完成，那么该任务的执行已没有意义，不仅导致任务夭折，有浪费了CPU资源。 LLF算法的提出可以弥补EDF算法的不足。 最低松弛度LLF算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。 松弛度：即各个进程的富裕时间。 例如，一个任在200ms时必须完成，它本身所需的运行时间有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。 最低松弛度LLF算法——算法要求 1、系统中有一个按松弛度排序的实时任务就绪队列。 2、松弛度最低的任务排在队列最前面。 3、调度程序总是选择就绪队列中的队首任务执行。 最低松弛度LLF算法——特点 （1）动态调度算法。（即任务的优先级则在运行过程中确定，并可能不断地发生变化） （2）若是周期性任务，周期内任务只执行一次。即当进程在当前周期截止时间前完成了任务，则在该进程进入下个周期前，无需计算它的松弛度。 （3）松弛度为0时发生抢占（主要用于可抢占调度方式中） 最低松弛度LLF算法——算法实例 该假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20ms执行一次，执行时间为10ms；任务B只要求每50 ms执行一次，执行时间位25ms。由此可知，任务A和任务B每次必须完成的时间分别为：A1、 A2、 A3、…和B1、 B1、 B1、 B1…，如图中所示： 执行过程 最低松弛度LLF算法——不足 当多个任务松弛度值接近时，会造成任务之间的频繁切换或颠簸现象较为严重，增大了系统内因调度造成的开销，限制了算法的实际应用。 * 最低松弛度调度算法-----LLF算法 组员：李欢，纪宏伟，李国栋 实时调度 实时调度的概念：实时调度是为了完成实时处理任务而分配处理器的调度方法 实现实时调度的基本条件： 提供必要的信息(就绪时间、截止时间（开始和完成）、处理时间、资源要求、资源优先级) 系统处理能力要足够强: 单处理机情况下：设有m个周期性事件，事件i的周期为Pi，其中每个事件需要Ci秒的CPU时间来处理，可调度的的实时系统必须满足： C1/P1 + C2/P2 + … + Cm/Pm ≤ 1 多处理机情况下： C1/P1 + C2/P2 + … + Cm/Pm ≤ N（N处理机的个数） 采用抢占式调度机制 具有快速切换机制 实时调度算法的分类 1)非抢占式调度算法 : 非抢占式轮转调度算法(实时要求不太严格，s) 非抢占式优先调度算法(要求比较严格,数百ms) 2)抢占式调度算法: 基于时钟中断的抢占优先调度算法(要求比较严格,数10ms) 立即抢占优先权调度算法(紧迫任务,几ms甚至百微秒) 最低松弛度调度算法-----LLF算法 松弛度=必须完成时间 – 本身运行时间 – 当前时间 松弛度=必须完成时间 – 本身运行时间 – 当前时间