常用的几种实时调度算法
最早截止时间优先即EDF(Earliest Deadline First)算法
最低松弛度优先即LLF(Least Laxity First)算法
该算法是根据任务紧急(或松弛)的程度来确定任务的优先级任务的紧急程度愈高为该任务所赋予的优先级就愈高 以使之优先执行例如一个任务在ms时必须完成而它本身所需的运行时间就有ms因此调度程序必须在ms之前调度执行该任务的紧急程度(松弛程度)为ms又如另一任务在ms时必须完成它本身需要运行ms则其松弛程度为ms在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列松弛度最低的任务排在队列最前面调度程序总是选择就绪队列中的队首任务执行该算法主要用于可抢占调度方式中假如在一个实时系统中有两个周期性实时任务A和B任务A要求每 ms执行一次执行时间为ms任务B只要求每ms执行一次执行时间为ms
在刚开始时(t=)A必须在ms时完成而它本身运行又需ms可算出A的松弛度为msB必须在ms时完成 而它本身运行就需ms可算出B的松弛度为ms故调度程序应先调度A执行在t=ms时A的松弛度可按下式算出
A的松弛度=必须完成时间其本身的运行时间当前时间
=msmsms=ms
类似地可算出B的松弛度为ms故调度程序应选择B运行在t=ms时A的松弛度已减为(即)而B的松弛度为ms(即)于是调度程序应抢占B的处理机而调度A运行在t=ms时A的松弛度为ms(即)而B的松弛度仅为ms(即)故又应重新调度B执行在t=ms时B执行完成而此时A的松弛度已减为ms(即)而B的松弛度为ms(即)于是又应调度A执行在t=ms时任务A尚未进入第周期而任务B已进入第周期故再调度B执行在t=ms时A的松弛度已减至ms(即)而B的松弛度为ms(即)故此时调度又应抢占B的处理机而调度A执行
——返回教材目录
了解更多计算机相关基础课程视频
