评价网 > 科教论文 > 工学毕业论文 > 计算机应用论文 > 正文

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

2015-01-17 01:04 摘 要 实时调度算法是实时系统的关键。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。本文针对硬实时调度算法中的最早时限优先（EDF）调度算法，分别介绍在简单模型上和复杂模型上如何判定实时任务的可行性。 关键词 实时；调度算法；可行性分析；响应时间1 前言 硬实时调度算法，常见的分为速率单调调度法（RM）、 时限调度法（DM）和最早时限优先调度算法（EDF）。 EDF调度总是比固定优先级调度取得更高的利用率。相对于速率单调调度法（RM）和 时限调度法 （DM），EDF的时限是任意的，更适用于实际的实时系统。检查一组或一个具体实时任务是否能采用某种调度算法进行实时调度。这一过程叫调度算法的可行性判定。针对不同的算法，可行性测定有很多种。本文对常见的硬实时调度算法EDF介绍了相应的可行性测定方法。即假定任务同时启动，任务的最坏响应时间（即任务就绪到任务被完成的最长时间段）是否大于其任务时限，若大于，则调度可行，否则任务不可调度。在简单介绍完该方法后，对该方法进行了编程实现。 2 EDF简单实时模型的可行性测定 简单实时模型即各任务都是独立的周期任务，任务之间相互独立,无资源共享。Liu和Layland的论文[2]不仅介绍了针对固定优先级调度的基于利用率的测试，而且也为最早时限优先级算法（EDF）给出了一个基于利用率的测试：只要进程集合（对于简单进程模型）的利用率 小于1，那么所有时限将能被满足。但这种测试方法的缺点是不准确，不适应于更一般的进程模型。3 EDF的基于最坏响应时间的可调度性测试 所谓响应时间是指任务的某次释放到任务完成所花费的时间，而最坏响应时间是指所有响应时间中最长的响应时间。本文中介绍的方法——EDF的基于最坏响应时间的可调度性测试即是首先找出所给任务集的各个任务的最坏响应时间，然后将各个任务的最坏响应时间与相对时限相比较，如果所有任务的最坏响应时间都不大于各自的相对时限，那么该任务集可调度。如果没有通过测试，则该任务集不可调度。对调度的判断采用响应时间测试方法的优点之一是该方法适应于更一般的进程模型，优点之二它们是充分必要条件——如果任务集合通过测试，则可调度，否则，不可调度。可见找出最坏响应时间对于任务的可调度性的判断是非常重要的。下面介绍如何找出任务的最坏响应时间。EDF调度算法的最坏时间响应分析的基本思想： 所求任务i的最坏响应时间一定在处理器的忙碌期找到[3]。可知任务i的最坏响应时间不一定在处理器的第一忙碌期找到，但它能在这样的忙碌期找到：在该忙碌期中，除了任务i外其它任务都在忙碌期的开始同时释放，然后各个任务按各自的周期而再次释放。 因为虽然任务同时释放的情况很特殊，但我们可以把其它任务都移到忙碌期的开始时刻后再同时释放，这种移动不但不会减少任务i的响应时间，相反可能增加其响应时间，而我们就是要求任务I的最坏响应时间，因此这样的移动是合理的。更有利于计算出任务的最坏响应时间。 设忙碌期的始端时刻为t1,结束时刻为t2。除任务i外的任务于忙碌期的开始时刻同时释放，任务i的相对时限为Di，设任务i的某次执行于时刻a释放，因此任务i的绝对时限为d=a Di。在忙碌期内所有任务的绝对时限都小于或等于任务i的绝对时限，因此任务i的完成时刻即是忙碌期的结束时刻t。见图1。 图1为讨论方便，令t1=0,那么任务i的响应时间即是Li(a)-a。现在的问题就变成如何计算忙碌期的长度Li(a)？忙碌期长度即是从时刻t1释放到时刻t2完成的任务的计算时间总和。所以Li(a)＝Cj δi(a,Li(a))Ci [3] （1）（其中，