2022年最低松弛度优先宣贯 .pdf

最低松弛度优先（LLF ）算法是根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，使之优先执行。 在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，被优先调度。松弛度的计算方法如下：任务的松弛度 =必须完成的时间-其本身的运行时间-当前时间其中其本身运行的时间指任务运行结束还需多少时间，如果任务已经运行了一部分，则：任务松弛度 =任务的处理时间-任务已经运行的时间 当前时间几个注意点：1. 该算法主要用于可抢占调度方式中，当一任务的最低松弛度减为0时，它必须立即抢占CPU ，以保证按截止时间的要求完成任务。2. 计算关键时间点的各进程周期的松弛度，当进程在当前周期截止时间前完成了任务，则在该进程进入下个周期前，无需计算它的松弛度。3. 当出现多个进程松弛度相同且为最小时，按照“最近最久未调度”的原则进行进程调度。1、结构体描述进程定义及其意义如下：typedef struct process /进程 char pname5; /进程名int deadtime; /周期int servetime; /执行时间/周期进程某一次执行到停止的剩余需执行时间（考虑到抢占），初始为 deadtime int lefttime; int cycle; /执行到的周期数/进程最近一次的最迟开始执行时间，- currenttime 即为松弛度int latestarttime; /进程下一次最早开始时间int arivetime; intk; /k=1 ，表示进程正在运行，否则为0，表示进程不在执行期间/* 若存在最小松弛度进程个数多于1个，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 则采用最近最久未使用算法采用一计数器LRU_t */ intLRU_t; process; 2、循环队列存储进程定义及其意义如下：typedef struct sqqueue /循环队列 process *dataqueuesize; int front,rear; sqqueue; 重难点分析1、实时系统可调度条件当实时系统中有M 个硬实时任务，它们的处理时间可表示为Ci ，周期时间表示为Pi，则在采用 N 个处理机的系统中，必须满足限制条件：=N 系统才是可调度的。现在单处理机下，即=1 ，否则认为不满足实时系统调度条件。2、进程的结构体描述typedefstruct process /进程 char pname5; int deadtime; int servetime; int lefttime; int cycle; int latestarttime; int arivetime; intk; intLRU_t; process; 进程首先包括进程名pname 、周期时间deadtime 、执行时间servetime ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 为控制周期进程的执行周期数，应有一个进程计数cycle ，初始化为 1；因为是实时系统中的进程，该有一个进程执行最早开始时间arivetime和最晚开始时间latestarttime ；考虑到进程抢占，所以有一个进程某一次执行中断后的剩余执行时间，需用于计算松弛度。还可以有一个进程运行状态位k，1即表示正在运行，0则表示没有运行。当出现多个进程松弛度相同且为最小时，按照“最近最久未调度”的原则进行进程调度。所以有一个计数器LRU_t 计算每一个进程在调度时，调度与被调度的情况。初始均为0，调度某一进程时，则该进程以外的其他进程均要在计数器上加1。松弛度相同时，选择计数器LRU_t 值最大的。补充说明：最开始时，我们没有考虑进程运行状态位k，后来是为了输出进程的执行开始和结束时间而加的，可以根据进程的运行状态位，进行输出进程的执行时间段。对于出现多个进程松弛度相同且为最小时，最开始选择的是每次都采用最接近队尾的进程，这样虽然满足对于题目所给的实例，但是实际上是还是不符要求的，最后选择最近最久未使用算法的思想得以解决。3、循环队列的属性及遍历队列中的进程以数组的形式进程存储；队列的队首为front ，队尾为 rear ，遍历时要考虑队空否，或者输入进程时，要考虑进程是否填满了队列。循环队列，队空为：front = rear 队满为： (rear+1)%queuesize = front 4、松弛度的计算松弛度= 任务必须完成的时间 任务本身的运行时间 当前时间；即松弛度= 周期 *需执行的次数（上一次）执行的剩余时间当前时间即松弛度 = deadtime cycle lefttime currenttime 而（可能被中断过）进程最迟开始执行时间arivetime = deadtime cycle lefttime 所以 arivetime currenttime =0 ，即为松弛度为0，抢占当前正在运行进程。5、最小松弛度的进程采用遍历队列中当前时间下可以开始运行的进程，即最早开始时间arivetime=deadtime*( cycle-1) 小于当前时间， 比较各进程松弛度， 得出最小松弛度的进程。6、进程的抢占由上可知进程的松弛度的计算方法，依旧采用遍历队列的方式，循环寻找松弛度为0 的进程：如果存在就让其跳出循环，返回该进程；否则，队首指针向下，直至队尾，如果遍历完都不存在松弛度为0的进程，则返回当前进程即可。但未考虑松弛度同时为0的进程存在多名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 个的情况。7、时钟由于是实时系统，我们采用时钟计时法。即在每1ms 的时间变化时，都要进行LLF 进程的选择。即在当前时间currenttime下， currenttime初始为 0，循环 +，直至到达执行总时间MAXTIME 。8、最低松弛度相同的若干进程调度对于出现多个进程松弛度相同且为最小时，选择的原则是， 刚刚执行过的进程，此时应不再执行，让给其他具有同样最低松弛度的进程。最开始选择的是每次都采用最接近队尾的进程。在遍历的过程中， 将当前队列赋给一临时队列，对临时队列进行遍历，所以并不改变原队列的队首队尾指针。在每次选择最低松弛度的进程时，我们都是选择离队尾最近的进程，但这样存在着问题，例如：A：50ms （周期），10（执行时间） ，B：20ms （周期），10（执行时间）， C： 50ms （周期）， 15（执行时间），在第 80ms 时还是在执行完B4后，执行 B5，而非 A2 。这样虽然满足对于题目所给的实例，但是实际上是还是不符要求的。最后选择最近最久未使用（ LRU ）算法的思想得以解决。即给每一个进程设置一个计数器。9、currenttime 在边界值时的情况在 currenttime = MAXTIME时，可能存在进程正好要开始执行，例如题目所给的例子：100ms 时，A 进程要开始执行，但是我们不应让其开始执行，所以应该临界处理；同理，可能也存在进程正在执行当中，此时应该输出该进程在没有完成其周期执行时间的下的运行时间段。10、当前时间没有进程运行的情况假若只有一个进程，周期时间是20ms ，执行时间是 10ms ，那么在 10 20ms 、3040ms 、5060ms , 时，是没有进程运行的情况，即此时最低松弛度的进程为空。/最低松弛度调度算法LLF 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -