基于概率性分析的混合关键级系统节能调度算法

针对混合关键级系统中的固定优先级任务节能问题,文中提出了基于概率性分析的混合关键级系统节能调度算法。混合关键级系统的实时性要求使得系统建模和分析偏向于较坏的情况。该类系统中出现任务超限的情况相对较少,易存在资源配置过度问题。通过DVFS(Dynamic Voltage Frequency Scaling)技术和混合关键级系统调度算法相结合的方式挖掘空闲时间,从而在保证系统实时性的前提下降低系统的能耗。利用MCSIMU仿真软件对所提算法进行了仿真验证,实验结果表明,对于固定优先级任务与未使用节能调度算法相比,固定优先级节能调度算法的节能率可达45%。

FPNS中控制器局域网报文响应时间的最差假设

在控制器局域网(CAN)消息集固定优先级非抢占式调度(FPNS)的研究中,现有的CAN报文的最差响应时间(WCRT)分析方法会对某些消息集的可调度性做出错误判断。为此,本文根据CAN消息FPNS的报文忙期的定义重新分析了报文首次与其余各次进入相关节点的发送队列的情况,修正了其响应时间的最差假设。根据该最差假设所计算的WCRT修正了传统的WCRT分析方法的过优估计,消除了修正的WCRT分析方法引入的过差估计。

基于避让阻塞的优先级天花板协议

为了提高空间飞行器计算机的CPU利用率,新一代空间飞行器操作系统使用了一种同时包含固定时间点启动任务和偶发任务的混合调度算法.其中固定时间点启动任务往往是安全攸关任务,需要在固定时间点启动,且执行期间不能被阻塞.在固定时间点启动任务和偶发任务共存的条件下,现有的实时锁协议无法保证固定时间点启动任务的阻塞时间为零,因此在经典的优先级天花板协议的基础上,提出基于避让思想的实时锁协议,通过提前预判和设置虚拟启动点的方式,确保偶发任务对共享资源的访问不会影响到固定时间点启动任务的执行.同时暂时提升部分共享资源的访问优先级,降低了任务抢占所带来的运行开销.给出上述锁协议的最坏阻塞时间,并通过可调度率实验分析其性能,实验表明,在临界区较短的情况下,本协议可将因访问共享资源而导致的可调度性损失控制在27%以内.

CAN总线固定优先级调度算法的应用

分析了CAN总线的最差消息传输模型,提出了一种固定优先级调度算法;针对系统控制实时性的要求及特点,对6自由度平台系统的消息进行调度。实际使用证明,该方法改善了6自由度平台的整体控制性能,提高了网络利用率,消息的截止期得到满足。

一个基于多线程的优先级继承协议锁的算法研究

实时线程库对构造实时中间件和开发具有良好可移植性、有实时要求的分布式应用具有重要意义 .防止优先级翻转的线程互斥和同步机制是实现实时线程库的核心 ,目前多数的线程库都缺乏这种机制 .基于优先级继承协议 ,提出了一个防止优先级反转的互斥算法 .算法能够保证操作的原子性 ,可以避免发生死锁 ,且能够有效地防优先级翻转 .在 Windows和 Solaris平台上对性能进行了分析 ,并将算法应用到了实时

面向多级中断系统的任务最差响应时间分析

针对航天嵌入式系统中存在多级中断情况下的时间分析问题,提出了中断与任务混合的响应时间计算模型。该模型中断与任务使用统一的优先级定义,将多级中断嵌套的响应时间分析与任务嵌套的响应时间分析相结合,推导出了混合模型下响应时间计算公式。并进一步比较了中断与任务的异同,阐述了公式中关键参数的含义与计算方法。最后利用开源的LEON3平台和Modelsim软件对所述方法进行了仿真验证,结果表明,任务最差响应时间过估小于5%,可以得到准确的分析结果,有较高的工程应用价值。

CAN总线可调度分析及在导弹控制系统中的应用

针对CAN总线固定优先级调度设计中存在的问题,在给出了任务模型和相关定义的基础上,首先推导了任务的最坏响应时间,得出了系统可调度的方法;然后,给出了设计固定优先级调度算法的步骤;最后,以某型导弹控制系统为例进行了可调度分析和优先级设计,并用Truetime工具箱进行了仿真,结果显示了该方法的有效性。

实时控制系统中固定优先级调度的延迟与抖动控制

在基于固定优先级调度实时控制系统中,任务的延迟与抖动是影响系统稳定性的重要因素.提出一种基于可抢占时间阈值的延迟与抖动控制策略,给出一种保证系统可调度的最优阈值分配算法,并通过对任务延迟和抖动的分析量化出阈值分配后的最大可能IO延迟及抖动.最后通过仿真实验验证了该策略的有效性.

抢占阈值调度的功耗优化

DVS(Dynamic Voltage Scaling)技术的应用使得任务执行时间延长进而使得处理器的静态功耗(由CMOS电路的泄露电流引起)迅速增加.延迟调度(Procrastination Scheduling)算法是近年提出用于减少静态功耗的有效方法,它通过推迟任务的正常执行来尽可能长时间地让处理器处于睡眠或关闭状态,从而避免过多的静态功耗泄露.文中针对可变电压处理器上运用抢占阈值调度策略的周期性任务集合,将节能调度和延迟调度结合起来,提出一种两阶段节能调度算法,先使用离线算法来计算每个任务的最优处理器执行速度,而后使用在线模拟调度算法来计算每个任务的延迟时间,从而动态判定处理器开启/关闭时刻.实例研究和仿真实验表明,作者的方法能够进一步降低抢占阈值任务调度算法的功耗.

优先级受限系统中可调度判定方法

在通信、雷达、导航以及各种消费类电子产品等民用和军事领域,嵌入式实时调度已逐渐成为电子电气系统的控制核心。针对同优先级任务使用FIFO调度的静态优先级系统,使用反例指出给定同优先级任务初始执行顺序的前提下,Katcher可调度判定条件的必要性不成立,提出并解析证明了FP可调度的充要条件。随机实验表明,对于高利用率下任务间执行时间差异较大的情况,约有15%的可调度任务集会被Katcher条件错判为不可调度。进一步的仿真和实例分析表明,Liu、Lehoczky、Bini等提出的条件不能判定相同优先级的情况,Katcher条件的必要性不成立,论文提到的条件能够正确判定任务集的可调度性。提出方法为实时系统调度的顶层设计提供了快速离线工具。

优先级调度在交换式工业以太网中的应用研究

针对交换式以太网用于工业实时通信时不能确保数据按时送达问题,在通信站点和交换机端引入IEEE802.1p优先级服务机制,通过设置实时优先级字段来区分其不同的紧急程度的实时数据帧,并采用非抢占式固定优先级调度算法改善实时数据帧的传输时延.通过将调度分析法和网络演算法相结合,提出了一种混合的实时数据帧传输时延上界计算方法.比较研究表明该方法得到的结果比网络演算法更准确.

基于多分辨率模型的实时调度方法

在实时系统中 ,为了避免任务的计算结果发生时间逻辑错误 ,我们提出一种新的多分辨率模型。在该模型中 ,任务有多个计算时间 ,每个计算时间都对应一定的执行价值。任务的计算时间越长 ,其执行价值越高。接着 ,我们提出了采用计算时间的数学期望值进行任务的优先级分配和可调度分析 ,从而可以利用已有的优先级分配和可调度分析方法 ,并在此基础上提出确定任务计算时间的方法。

固定优先级混合关键偶发任务能耗感知算法

混合关键系统是将不同关键层次的应用或组件集成到同一个共享平台.由于受尺寸、重量与体积的限制,能耗对于混合关键系统而言尤其重要.能耗感知调度算法是解决混合关键系统能耗问题的关键,现有的能耗感知算法主要基于动态优先级策略且空闲时间利用率低.针对固定优先级混合关键系统偶发任务能耗感知问题,提出节能效果更好的固定优先级混合关键调度(fixed priority mixed criticality schedule,FPMCS)算法.首先,提出关键层次单调速率策略(criticality rate monotonic scheme,CRMS)调度混合关键偶发任务,分析该策略的调度可行性,且计算出能耗感知速度.其次,利用高关键层次任务预留的空闲时间,通过事件触发的方法动态更新混合关键偶发任务集的利用率来回收偶发任务到达时间不确定产生的空闲时间.再次,利用混合关键偶发任务集的利用率决定任务的执行速度以达到降低能耗的目的.最后,通过理论分析和实验验证FPMCS算法是可行的;仿真实验表明:所提出的FPMCS算法比现有的方法可以节约大约33.21%的能耗.

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。

基于改进型统一调度算法改善任务集的可调度性

实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。

硬实时环境下固定优先级调度的离线优化

RM调度算法具有简单的实现机制和较低的调度开销,被广泛应用于硬实时调度领域.然而这类算法的固定优先级特征使其在高任务负载环境下具有极高的抢占次数,从而导致了较大的系统开销,因此提出一种方法来减少RM调度的抢占次数.该方法通过离线计算任务集的最优属性来减少基于RM调度的系统在运行时的抢占次数,进而降低系统的抢占开销.仿真结果表明,该方法可以在不付出额外调度开销的前提下有效减少RM调度的抢占次数,降低实时系统的抢占开销.

面向资源优化的周期分配方法和总线访问配置研究

汽车系统的功能多样性和智能化发展,引起车内ECU数量的大量增加,给汽车成本的降低带来巨大压力。ECU节点通过TTP总线构成了以周期性任务触发、基于TDMA技术的消息分发、基于抢占的FPS调度等为特点的分布式体系结构。实时性和资源利用率是上述体系结构需要考虑的两个关键问题,特别是随着汽车系统复杂性的快速增长,对解决上述问题提出了严峻的挑战。本文提出一种利用GP进行周期分配和总线访问配置,并结合FPS进行实时调度分析,在保证系统时限的前提下,最小化系统资源利用率的方法,以减缓ECU数量的增加,降低系统成本。在具备工业实用价值的任务集基础之上进行的仿真实验结果表明了该方法的有效性和可扩展性。

交换式以太网中周期性固定优先级消息的可调度性分析

为使交换式以太网能满足工业数据通信的实时性要求,首先提出了一种基于固定优先级调度(FixPriority Scheduling,FPS)的实时消息调度模型,由源站点和消息接纳控制服务器对消息进行可调度性判定.另外,通过将消息集在交换式以太网上的可调度性判定转化为对在接收链路上具有释放抖动消息集的可调度性分析问题,给出了实时消息在发送和接收链路最坏传输完成时间的计算公式,进而提出了消息可调度性判定方法,并对相关结论进行了理论证明.

一种基于权重与轮询的双层仲裁算法

该文提出一种基于权重与轮询(Round-Robin,RR)的双层仲裁算法,在无冲突和多冲突情况下分别采用改进的固定优先级(Fixed Priority,FP)和RR仲裁轮流工作,并通过彩票项设置权重。在非空非抢占(NonIdling and NonPreemptive,NINP)模型下相比传统FP,RR和Lottery仲裁算法有更好的输出带宽比、带宽占用率和功耗,在速度和面积上有一定优势。该算法适应多种请求环境,逻辑简单,容易实现,可应用于总线结构的片上系统(System-on-Chip,SoC)。

多处理器固定优先级算法的可调度性分析

针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。