一种硬实时调度算法的可行性判定及实现

《一种硬实时调度算法的可行性判定及实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种硬实时调度算法的可行性判定及实现摘要实时调度算法是实时系统的关键。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。本文针对硬实时调度算法中的最早时限优先（EDF）调度算法，分别介绍在简单模型上和复杂模型上如何判定实时任务的可行性。关键词实时；调度算法；可行性分析；响应时间1前言硬实时调度算法，常见的分为速率单调调度法（RM）、时限调度法（DM）和最早时限优先调度算法（EDF）。EDF调度总是比固定优先级调度取得更高的利用率。相对于速率单调调度法（RM）和时限调度法（DM），EDF的时限是任意的，更适用于实际的实时系统。检查一组或

2、一个具体实时任务是否能采用某种调度算法进行实时调度。这一过程叫调度算法的可行性判定。针对不同的算法，可行性测定有很多种。本文对常见的硬实时调度算法EDF介绍了相应的可行性测定方法。即假定任务同时启动，任务的最坏响应时间（即任务就绪到任务被完成的最长时间段）是否大于其任务时限，若大于，则调度可行，否则任务不可调度。在简单介绍完该方法后，对该方法进行了编程实现。2EDF简单实时模型的可行性测定简单实时模型即各任务都是独立的周期任务，任务之间相互独立,无资源共享。Liu和Layland的论文[2]不仅介绍了针对固定优先级调度的基于利用率的测试，而且也为最早

3、时限优先级算法（EDF）给出了一个基于利用率的测试：只要进程集合（对于简单进程模型）的利用率小于1，那么所有时限将能被满足。但这种测试方法的缺点是不准确，不适应于更一般的进程模型。3EDF的基于最坏响应时间的可调度性测试所谓响应时间是指任务的某次释放到任务完成所花费的时间，而最坏响应时间是指所有响应时间中最长的响应时间。本文中介绍的方法——EDF的基于最坏响应时间的可调度性测试即是首先找出所给任务集的各个任务的最坏响应时间，然后将各个任务的最坏响应时间与相对时限相比较，如果所有任务的最坏响应时间都不大于各自的相对时限，那么该任务集可调度。如果没有通过

4、测试，则该任务集不可调度。对调度的判断采用响应时间测试方法的优点之一是该方法适应于更一般的进程模型，优点之二它们是充分必要条件——如果任务集合通过测试，则可调度，否则，不可调度。可见找出最坏响应时间对于任务的可调度性的判断是非常重要的。下面介绍如何找出任务的最坏响应时间。EDF调度算法的最坏时间响应分析的基本思想：所求任务i的最坏响应时间一定在处理器的忙碌期找到[3]。可知任务i的最坏响应时间不一定在处理器的第一忙碌期找到，但它能在这样的忙碌期找到：在该忙碌期中，除了任务i外其它任务都在忙碌期的开始同时释放，然后各个任务按各自的周期而再次释放。因为虽

5、然任务同时释放的情况很特殊，但我们可以把其它任务都移到忙碌期的开始时刻后再同时释放，这种移动不但不会减少任务i的响应时间，相反可能增加其响应时间，而我们就是要求任务I的最坏响应时间，因此这样的移动是合理的。更有利于计算出任务的最坏响应时间。设忙碌期的始端时刻为t1,结束时刻为t2。除任务i外的任务于忙碌期的开始时刻同时释放，任务i的相对时限为Di，设任务i的某次执行于时刻a释放，因此任务i的绝对时限为d=a+Di。在忙碌期内所有任务的绝对时限都小于或等于任务i的绝对时限，因此任务i的完成时刻即是忙碌期的结束时刻t。见图1。图1为讨论方便，令t1=0,

6、那么任务i的响应时间即是Li(a)-a。现在的问题就变成如何计算忙碌期的长度Li(a)？忙碌期长度即是从时刻t1释放到时刻t2完成的任务的计算时间总和。所以Li(a)＝Cj+δi(a,Li(a))Ci[3]（1）（其中，任务i的第一次释放时刻为对于等式+δi(a,Li(a))Ci可知，因为Li(a)是未知的（它是正在计算的值），由于高限函数和低限函数，使方程难以求解。可构造一递推关系+δi(a,Lmi(a))Ci若令那么等式（1）变成Li(m+1)(a)=)(a))（2）(其中)经过证明只要利用率，那么递推式（2）就收敛，方程有解。这样当Li(m+1

7、)(a)=Li(m)(a)，方程的解Li(a)就找到，就是Li(m)(a)。求解过程我们可以用时间窗口的概念来总结一下求Li(a)思路：我们可以将Li(a)这段时间称为时间窗口（见图1），。那么在时间窗口内，只能有优先级高于或等于任务i（即绝对时限小于或等于任务I的时限d）的任务能执行，随着更多优先级的任务落入时间窗口，时间窗口的长度不断扩大，当没有更高优先级的任务需要执行时，则时间窗口到达最大，此时的时间窗口的长度即是忙碌期长度Li(a)。知道了Li(a)的表达式后，可以在忙碌期内让a取不同的值，通过不同的a值，计算出任务i不同的Li(a)值，响应

8、时间为ri(a)=max{Ci,Li(a)-a}，从其中找出最大的ri(a),这就是所要求的最坏响应时间ri