共查询到18条相似文献,搜索用时 484 毫秒
1.
2.
一种改进的RM可调度性判定算法 总被引:6,自引:1,他引:5
固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高. 相似文献
3.
针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。 相似文献
4.
5.
6.
7.
基于抢占阈值调度的任务响应时间分析方法是一种新型实时系统任务可调度性判定技术。然而已有的研究工作,有时对以前的任务请求检查过少,可能导致对响应时间估计过低。同时对任务响应时间的分析忽略了任务释放抖动和时钟嘀嗒调度对任务响应时间的影响,造成任务错过期限的现象,系统任务可调度性判定存在潜在的不精确因素。针对上述缺点不足,本文提出改进的基于抢占阈值调度的任务响应时间分析方法,在修正已有方法缺陷的同时,考虑任务释放抖动和时钟嘀嗒调度的影响,引入额外的时间需求,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。 相似文献
8.
针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。 相似文献
9.
在通信、雷达、导航以及各种消费类电子产品等民用和军事领域,嵌入式实时调度已逐渐成为电子电气系统的控制核心。针对同优先级任务使用FIFO调度的静态优先级系统,使用反例指出给定同优先级任务初始执行顺序的前提下,Katcher可调度判定条件的必要性不成立,提出并解析证明了FP可调度的充要条件。随机实验表明,对于高利用率下任务间执行时间差异较大的情况,约有15%的可调度任务集会被Katcher条件错判为不可调度。进一步的仿真和实例分析表明,Liu、Lehoczky、Bini等提出的条件不能判定相同优先级的情况,Katcher条件的必要性不成立,论文提到的条件能够正确判定任务集的可调度性。提出方法为实时系统调度的顶层设计提供了快速离线工具。 相似文献
10.
11.
实时任务调度算法之间很难进行比较,而且缺少比较标准。提出具体环境下实时极限的思想,为任务调度的比较研究提供了一个尺度。并可在此基础之上进行算法自身消耗的测量。还可扩展可通行判定理论的应用范围。 相似文献
12.
静态优先级调度在实时系统中得到了广泛应用.然而,静态优先级调度受到系统支持的优先级个数的限制.当任务的个数大于优先级个数时,需要将多个任务映射到同一个优先级.针对优先级个数有限的情况,给出了在截止期限大于周期时任务可调度的充分必要条件,并提出了基于有限优先级的静态优先级分配算法(AGP).AGP算法对于基本任务集合是最优的静态优先级分配算法.其最优性表现在,所需的优先级个数最小,并且若采用AGP算法不可调度某个任务集,则采用其他静态优先级分配算法也不可调度该任务集.模拟结果表明,AGP算法的可调度性要远远大于常量法.AGP算法对于解决在嵌入式实时系统中任务的优先级分配问题具有重要意义. 相似文献
13.
不可抢占式EDF调度算法的可调度性分析 总被引:4,自引:1,他引:4
沈卓炜 《计算机工程与应用》2006,42(9):10-12,29
现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。 相似文献
14.
15.
16.
17.
近年来,随着实时调度研究的快速发展,可调度性实验的复杂性随之增加,然而,由于缺乏标准化、模块化的可调度性实验工具,研究者往往需要耗费大量时间进行实验;此外,由于实验源码不能公开获得,使得实验结果难以验证,实验代码难以重用与扩展。针对可调度性实验重复工作量大、难以验证的问题,提出一种可调度性实验基础框架。该框架通过随机分布产生任务系统集合,并测试其可调度性,基于该框架设计并实现了一个新的可调度性实验开源平台——SET-MRTS。该平台采用模块化架构设计了任务模块、处理器模块、共享资源模块、算法库、配置解析模块以及输出模块。实验结果表明,SET-MRTS支持单/多处理器实时调度算法和实时同步协议分析,能够正确地进行可调度性对比实验,输出直观的实验结果,并且支持算法库的扩充,与算法库中已实现的算法进行对比实验,具有良好的兼容性与可扩展性。SET-MRTS是第一个支持完整实验流程,包括算法实现、参数配置、结果统计、图表绘制等的可调度性实验开源平台。 相似文献
18.
Romulo Silva de Oliveira Andreu Carminati Renan Augusto Starke 《Journal of Parallel and Distributed Computing》2014
Schedulability analysis of real-time multiprocessor systems is usually based on sufficient but not necessary tests that produce pessimistic results. One difficulty in evaluating the effectiveness of sufficient schedulability tests has been distinguishing the cause of a task set failing the test, i.e., finding out whether the task set is in fact not schedulable or it is actually schedulable but the test itself is too pessimistic. Necessary schedulability tests help to distinguish between these two situations, since if a task set fails in the test then it is guaranteed to be unschedulable. An adversary simulator is a scheduling simulator that uses the non-determinism of the task model to generate scenarios that will stress a specific scheduling algorithm, improving the odds of a deadline miss. In this paper we describe a new adversary simulator algorithm for sporadic task sets executed on multiprocessors scheduled by Global Earliest Deadline First (G-EDF). It is shown that this new adversary simulator is more effective as a necessary test than existing approaches. We also estimate the uncertainty regarding G-EDF by applying to the same task sets a well-known sufficient schedulability test from the literature and the necessary schedulability test based on the adversary simulator. 相似文献