多处理器EPDFPfair算法的可调度性判定

针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。     

实时调度EDZL算法的可调度性判定

针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。     

多处理器全局单调比率的可调度性分析

针对全局单调比率(RM)调度的多处理器系统中最高优先级任务数量少于处理器数量时,Bertogna等给出的最坏情况计算任务受到的干涉过于悲观,证明了任务受到最高优先级任务的干涉不会出现最坏情况,它受到非最高优先级任务干涉仍可能出现最坏情况。分析得出了任务受到最高优先级任务干涉的最大可能值,由此得到了一个更紧的可调度性判断条件。实验结果表明,提出的方法提高了判为可调度的任务集数量。     

强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。     

基于单调速率的可调度性判定改进算法

在单调速率调度策略的基础上,提出一种改进的任务集可调度性判定算法。该算法通过设定时钟变量模拟调度过程中的系统时钟,在时钟变量值增长过程中,根据任务优先级从高到低的顺序,分析各个任务的截止时间限的满足情况,判定任务的可调度性,从而确定任务集的可调度性。通过实例分析及与现有判定方法的比较,验证了该算法的正确性和高效性。     

全局EDZL实时调度算法的可调度性判定

可调度性判定就是离线验证实时系统中所有任务是否可调度。通过可调度性判定,能够更好地保证实时系统的可靠性。有多种分析方法可用于可调度性判定,得到的结果有所不同。通过分析在多处理器实时系统中全局EDZL算法的任务需求,考虑带入作业和带出作业对处理器资源的需求。引入最大连续忙区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。实验结果说明了这种方法提高了通过可调度性判定的任务数量,是一种更紧密的可调度性判断方法。     

一种有限优先级的静态优先级分配算法

静态优先级调度在实时系统中得到了广泛应用.然而,静态优先级调度受到系统支持的优先级个数的限制.当任务的个数大于优先级个数时,需要将多个任务映射到同一个优先级.针对优先级个数有限的情况,给出了在截止期限大于周期时任务可调度的充分必要条件,并提出了基于有限优先级的静态优先级分配算法(AGP).AGP算法对于基本任务集合是最优的静态优先级分配算法.其最优性表现在,所需的优先级个数最小,并且若采用AGP算法不可调度某个任务集,则采用其他静态优先级分配算法也不可调度该任务集.模拟结果表明,AGP算法的可调度性要远远大于常量法.AGP算法对于解决在嵌入式实时系统中任务的优先级分配问题具有重要意义.     

SET-MRTS：一种多处理器实时系统可调度性实验平台

近年来,随着实时调度研究的快速发展,可调度性实验的复杂性随之增加,然而,由于缺乏标准化、模块化的可调度性实验工具,研究者往往需要耗费大量时间进行实验;此外,由于实验源码不能公开获得,使得实验结果难以验证,实验代码难以重用与扩展。针对可调度性实验重复工作量大、难以验证的问题,提出一种可调度性实验基础框架。该框架通过随机分布产生任务系统集合,并测试其可调度性,基于该框架设计并实现了一个新的可调度性实验开源平台——SET-MRTS。该平台采用模块化架构设计了任务模块、处理器模块、共享资源模块、算法库、配置解析模块以及输出模块。实验结果表明,SET-MRTS支持单/多处理器实时调度算法和实时同步协议分析,能够正确地进行可调度性对比实验,输出直观的实验结果,并且支持算法库的扩充,与算法库中已实现的算法进行对比实验,具有良好的兼容性与可扩展性。SET-MRTS是第一个支持完整实验流程,包括算法实现、参数配置、结果统计、图表绘制等的可调度性实验开源平台。     

一种静态最少优先级分配算法

随着实时系统越来越多地应用于各种快速更新系统,尤其是各种片上系统,如PDA(personal digital assistant),PSP(play station portable)等,性价比已成为系统设计者的主要关注点.实际应用中,实时系统通常仅支持较少的优先级,常出现系统优先级数小于任务数的情况(称为有限优先级),此时,需将多个任务分配到同一系统优先级,RM(rate monotonic),DM(deadline monotonic)等静态优先级分配算法不再适用.为此,静态有限优先级分配是研究在任务集合静态优先级可调度的情况下,可否以及如何用较少或最少的系统优先级保持任务集合可调度.已有静态有限优先级分配可分为两类:固定数目优先级分配和最少优先级分配.给出了任意截止期模型下任务静态有限优先级可调度的充要条件以及不同静态有限优先级分配间转换时的几个重要性质,指出了系统优先级从低到高分配策略的优越性,定义了饱和任务组与饱和分配的概念,证明了在任务集合静态优先级可调度的情况下,最少优先级分配比固定数目优先级分配更具一般性.最后提出一种最少优先级分配算法LNPA(least-number priority assignment).与现有算法相比,LNPA适用范围更广,且复杂度较低.     

不可抢占式EDF调度算法的可调度性分析

现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。     

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

求解多处理机调度问题的蚁群算法

蚁群算法是受自然界中的蚂蚁觅食行为启发而设计的智能优化算法,特别适合处理离散型的组合优化问题。提出一种求解多处理机调度的蚁群算法,利用一个蚂蚁代表一个处理机来选择任务,并通过分析关键路径及每个任务的最早、最迟开始时间来确定每个任务的紧迫程度,让蚂蚁以此来选择任务。实验证明,该算法可比传统算法取得有更好运行效率的调度策略。     

多媒体网络中基于优先级调度的实时QoS研究

使用到达函数和服务函数描述不同优先级实时分组集的到达和处理,基于期望可调度性来刻画不同紧急程度的实时应用对延迟的要求。提出的方法能够实现实时QoS控制下的瞬时特性研究,判定某一时刻不同优先级分组集的可调度性。最后对指数分布服务时间下的不同优先级分组集的期望可调度性进行了研究,基于理论结论的数值结果和基于模型的模拟结果是一致的。     

多处理器调度算法实现及其Petri网建模与仿真

多处理器调度算法在嵌入式实时系统领域中起着关键的作用。根据多处理器的特点,提出一种实时多处理器动态分割并行调度算法SPara。该算法解决了此前多处理器算法,如Myopic、EDPF等仅依据截止期对任务调度产生的问题,实现了增加任务紧迫度限制的调度策略,以及针对执行时间长、截止期紧迫任务的有效调度方法。同时算法结合高级颜色时间Petri网理论进行建模并仿真。测试结果表明,SPara算法在处理器利用率以及调度成功率方面较Myopic等算法有较大提高。     

EDF调度算法可调度性分析方法的改进研究

任务集的可调度性分析是实时系统研究和应用的关键问题。针对抢占式与不可抢占式EDF(earliest deadline first)调度算法, 分别给出了实时任务集新的可调度性测试条件, 针对任务集为可调度时可以实现快速判定。通过与已有的EDF算法的可调度性判定充要条件相结合, 提出了改进的抢占式与不可抢占式EDF算法的可调度性分析方法。仿真实验表明, 相对现有EDF算法的可调度性分析方法, 所提出的方法能有效提高算法性能。     

一种多处理器平台上的传感器事务调度算法

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法,算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束,通过预先计算出全局重复调度序列来降低运行开销,给出了算法的可调度性分析。实验结果表明,该算法具有较高的调度成功率,其产生的更新负载也较低。     

基于差分进化算法多处理机任务调度研究

本文主要基于现代启发式差分算法讨论多处理机调度,多处理机调度是NP组合优化问题,目前多采用启发算法。差分进化算法是最近提出的进化算法,主要根据父代个体之间矢量差构造下一代,是一种全局优化搜索方式。本文考虑采用差分进化矢量优先级模型描述调度顺序进行调度,与模拟退火算法比较得到较好调度结果。