Hybrid Task and Message Scheduling in Hard Real Time Distributed Systems over FlexRay Bus

FlexRay is a vehicular communication protocol designed to meet growing requirements in hard real time automotive systems and to support time triggered as well as event triggered paradigms. Thus, there has been a lot of recent interest in timing analysis techniques in order to provide bounds for the message communication times on FlexRay. In this paper, we present an approach to compute the WCRT （worst case response time） for periodic and sporadic tasks, within a FlexRay node, responsible for sending messages on the FlexRay SS （static segment） and DS （dynamic segment）. On the other hand, we propose a scheduling table for messages transmitted over the FlexRay SS. An interesting innovation would be the use of a scheduling algorithm performed on a FlexRay node to guarantee the arrival of the right data on the right time and to ensure that every task meets its deadline. As application, we will use the extended SAE （society of automotive engineers） benchmark for the FlexRay network to identify the static and dynamic tasks, and calculate the response time, based on a hybrid scheduling model to further prove that the deadline of the SAE benchmark applications is insured.

基于启发式算法降低比例公平调度开销策略

在多处理器系统中已经证明了比例公平(proportion fair,Pfair)算法是调度周期任务最优的全局调度算法。然而在该算法的最坏执行情况下,任务在每个调度时刻均产生切换或迁移,导致系统开销过大。针对这一问题,对Pfair算法进行深入研究后发现,任务的分配过程是一个重要原因。基于此,提出基于启发式算法的模拟退火比例公平(simulated annealing-proportion fair,SA-Pfair)调度算法,即在Pfair算法做出调度决策后,用启发式算法将任务分配给处理器,以弥补原算法的不足。最后,采用LITMUS-RT平台对SA-Pfair算法和以此为基础设计的调度器进行仿真。结果表明,新算法在一定程度上减少了任务的切换次数以及50%以上的任务迁移总量,且能够有效地降低调度过程中的系统开销。

一类非抢占式非严格周期任务单通道调度问题研究

针对一种特殊的非抢占式非严格周期任务集的单通道调度问题,提出一种启发式搜索的方法,全局遍历来搜索所有的可行解。同时对于某些需要快速反应的应用场景,提出一种快速求解法,其算法复杂度要远低于全局搜索,能在更快的时间内求得可行方案,但可能会忽略大部分的可行解。实验结果表明两算法在任务集调度方面都有其各自的优缺点,可适用于不同的应用场景。

具有依赖关系的周期任务实时调度方法

随着多核技术在嵌入式领域的快速发展,越来越多的功能被集成在同一个平台上,任务之间的关系越来越复杂.而当前大多数的实时周期任务的调度模型都是不考虑任务之间关系的相互独立的任务模型.文中则针对具有依赖关系的周期任务,提出了一种基于ST(Simple-Tree)的实时周期任务调度模型,通过该模型来维护任务之间的依赖关系.此外,为了有效地提高系统利用率以及降低死限丢失率,文中还提出了可延迟时间越短越优先的调度方法并和RM算法、EDF算法进行仿真实验比较,结果表明该方法具有较高的核利用率和较低的死限丢失率.

容错多处理机中一种高效的实时调度算法(英文)

针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3个不相交的子集进行调度,从而使TPFTRM调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM算法的高效性.

实时操作系统实时性能测试技术研究

实时性能是表征实时操作系统的最重要的性能指标。现代实时操作系统的多任务调度、内存管理、中断处理等机制对系统的实时性能带来了很大的影响。为了对实时操作系统的性能进行详尽的测试,需要对实时操作系统的实现机制进行深入的分析,确定系统的实时时钟精度,选择有代表性的实时性能指标,并制定各实时性能指标的性能测试方法。中断响应延迟是表征操作系统本身最基本的实时性能指标,影响着系统其它方面的实时性能。周期任务调度延迟与应用直接相关,是实时操作系统应用的最直接性能指标。根据中断响应延迟和周期任务调度延迟的产生机理,可以设计并完成实时操作系统的性能测试。

周期性任务调度的装箱算法

针对基于时间触发的CAN控制系统,给出了确定周期性任务表中的基本周期的两种策略,提出了构造周期性任务调度表的下次适应、降序下次适应、最佳适应和降序最佳适应四种算法,分析了这四种不同算法的时间复杂度和最坏渐近性能比,最后对不同规模下的四种算法进行了仿真比较,结果表明文中给出的四种算法效果均优于经典的一维装箱算法。

基于RMS调度周期、非周期混合任务集的一种新方法

提出了一种利用速率单调(RMS)算法确定计算机实时系统中整个任务集优先级的新方法。该方法利用数理统计的规律克服了普通RMS算法只能对系统中周期任务进行有效调度而不能对系统中的非周期任务进行有效调度的局限,扩大了RMS算法的适用范围,简化了非周期任务的处理过程,减小了系统开销。利用该方法在先进飞机电气综合控制与管理系统中进行了整个任务集的可调度性测试、验证,并给出了任务集的实际调度的验证实例。

基于平均空闲时间分配的低功耗调度算法

针对周期任务,考虑通用的功耗模型,结合动态电压缩放技术和动态功耗管理技术,提出了基于平均空闲时间分配的低功耗调度算法.该算法是两阶段的调度算法,离线阶段计算静态运行速度,回收静态空闲时间;在线阶段回收动态空闲时间,调节处理器的运行速度,并适时地利用动态功耗管理技术关闭处理器,以降低处理器能耗.仿真实验表明所提的算法比使用基于贪婪空闲时间分配的DRA算法平均节约大约6.55%的能耗.

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务，又包含软非周期任务，引入一种改进软非周期实时任务响应时间的算法．已有的解决混合任务调度问题的方法都是基于速率单调（ＲａｔｅＭｏｎｏｔｏｎｉｃ）策略的，其中从周期任务“挪用时间”的算法被证明优于其他所有算法．但是，速率单调算法限制了处理器的使用率，从而使周期任务的可“挪用”时间受到限制．最后期限驱动（ＤｅａｄｌｉｎｅＤｒｉｖｅｎ）策略ＤＤ可使潜在的处理器利用率达到１００％．新算法正是在周期任务的调度中适当加入了ＤＤ策略，从而使非周期任务的响应时间得以缩短．仿真实验的结果表明，这种算法的性能优于已有的所有算法，而由它所带来的额外开销却不算很高．

面向多处理器的实时周期任务容错调度算法研究

主副版本策略是多处理器系统实时任务调度中处理容错问题的一种重要方式.根据分布式控制系统的特点,本文提出一种改进的FTRMBF算法—PR-FTRMBF,以提高系统周期任务的可调度性.在FTRMBF等已有的调度算法中,当没有处理器分配给当前副版本时,将为副版本分配新的处理器;本文提出的改进算法则以回溯的方式重新分配主版本.在保证系统实时性能和容错能力的前提下,节省了处理器数目.仿真实验表明,与FTRMBF算法相比,改进算法显著提高了系统任务的可调度性.

异构分布式系统混合型实时容错调度算法

基/副版本技术是实现实时分布式系统容错的一个重要手段。提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务。在此基础上给出3种容错调度算法:以可调度性为目的SSA算法、以可靠性为目的RSA算法、以负载均衡性为目的BSA算法。算法能够在异构系统中同时调度具有周期和非周期容错需求的实时任务,且能够保证在异构系统中某节点机失效情况下,实时任务仍然能在截止时间内完成。最后从可调度性、可靠性代价、负载均衡性、周期与非周期任务数及任务周期与粒度5个方面对算法进行了分析。模拟实验结果显示算法各有优缺点,所以在选择调度算法时应该根据异构系统的特点来选择。

VxWorks在飞行器管理系统中的应用研究

提出了一种操作系统分级调度模型,该模型能够将多个传统子系统综合到一个应用平台中,并能保证各子系统在时间上相互独立。结合实时操作系统VxWorks,论述了该模型的最佳实践方法辅助时钟法,并对VxWorks的启动、存储管理、中断与异常管理等进行了详细论述。采用该模型在飞行器管理系统中将飞行控制系统、导航系统、数传模块以及任务管理系统等传统的子系统进行了综合,并给出了在某系统中的具体应用和性能评估,实验结果表明了该系统具有高性能、增量开发与部署的能力。

优先级周期性互换的实时调度算法

针对实时多任务调度时低优先级任务的延迟问题,提出了一种优先级周期性互换的静态优先级调度算法。该方法以固定的时间片为周期,对多任务系统中的某两个不同优先级的独立性任务,周期性地互换它们的优先级级别,在保证较高优先级任务的执行时间的前提下,使得较低优先级的任务有机会尽快执行,以缩短其执行过程中的延迟时间。所提方法能有效解决低优先级任务的实时性问题,从而提高实时多任务系统的整体控制性能。

PLUFS:一种开销敏感的周期任务在线多处理器节能实时调度算法

现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果，但仍不能保证最优可调度性。针对嵌入式实时系统中不可忽视的状态切换开销，提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合，在每个TL面的初始时刻、任务结束执行时刻实现节能调度，在不违反周期任务集最优可调度性的前提下，达到实时约束与能耗节余的合理折中。经过理论证明和模拟实验，结果表明：PLUFS算法不仅保证了周期任务集的最优可调度性，而且节能效果整体优于现有算法，能耗节余比现有算法提高约10％-20％。

一种新的嵌入式Linux实时调度算法

针对现有实时调度算法在实时性能上的不足,提出了一种新的实时任务分类调度算法,根据实时任务的到达情况进行分类,划分为周期任务和非周期任务,并对不同类型的实时任务使用不同的改进的实时调度算法.通过实验,证明此算法与现有实时调度算法相比,综合实时性能有了很大程度的提高.

周期多帧任务模型的响应时间分析

在一些实时系统应用中,经常需要计算周期任务每次请求的响应时间。针对周期性多帧任务模型,我们给出周期多帧任务请求的响应时间计算公式。模拟结果表明,该公式具有表达简单、计算量小的优点。

单层树型网格下独立任务的周期性调度

提出单层树型网格下单位独立任务的周期性调度方法,单位独立任务是大小相等的独立任务.首先,为单层树型网格下的单位独立任务调度建立线性规划模型,通过分析整数线性规划求解过程,发现一个单层树型网格平台在节点构成不同时,分别具有非饱和态、临界态或冗余态特征;并且,随着网格节点上任务数的增多,线性规划最优解呈线性增长,任务调度具有周期性特性.据此给出非饱和态、临界态或冗余态网格的定义、性质和判定方法,推导出单位独立任务调度的周期长度.最后,分析了周期性调度的时间复杂性,提出一种周期性调度算法Periodic-Sched.实验结果表明,周期性调度是有效的.单位独立任务的周期性调度将大规模的任务调度问题简化为一个周期内的任务调度,降低了调度问题的复杂度.该调度方法适用于对Hadoop平台的Map任务进行调度.

嵌入式实时操作系统任务调度算法的改进与应用

在嵌入式系统中,任务调度器的好坏很大程度上决定了系统的性能。针对经典的速率单调(RM)调度算法以任务的周期作为优先级的评测标准,容易导致某些周期长且重要的任务错过截止期限,而当任务数量趋于无穷时,CPU的利用率仅为69%的特点,提出一种新的静态调度算法—NSRL。该算法在任务控制块(TCB)中增加两个域,分别为任务的重要度和裕度为零的时刻。在高优先级任务优先执行的前提下,重要度较高且未执行的任务当且仅当裕度为零时,具有较高的优先权可以抢占当前任务运行。通过理论分析和具体实验,该方法降低了任务截止期错失率,提高了CPU利用率,可以更有效地调度实时任务,在无线宽带移动计算中得到了较好应用。

单处理器平台下的严格周期任务可调度性判定

针对系统调度理论研究中的严格周期任务可调度性判定问题,从研究实时系统中严格周期任务之间的相互干涉关系出发,提出一种基于特征任务的可调度性判定方法。分析严格周期任务在单一处理器平台下无冲突运行的时间约束,计算任务所能使用的全部空余时间,进而界定连续空余时间是否满足任务执行的需要,得到一个可调度性判定的充要条件。实验结果表明,与特征映射任务分配方法相比,该方法能够减少判定时间,提高判定成功率,具有更优的可调度判定性能。