基于时限单调算法的混合任务实时调度算法的研究与设计

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向。针对现代嵌入式实时系统的任务特性,和经典实时调度算法只调度周期任务的特点,提出一种新的静态优先级调度算法——混合任务时限单调算法(Periodic and Aperiodic Deadline Monotonic,PADM)。该方法结合时限单调(DM)算法和先来先服务(FCFS)算法,将非周期任务量化为周期任务,且非周期任务在其裕度为零时优先级最高。通过理论分析和具体实验比较,在任务集轻载情况下,PADM算法尽可能地保证周期任务的完成率和非周期任务的时限,同时所带来的额外开销小,计算复杂度低,实现方便,是一种有效的混合任务调度算法。     

一种新的多处理器系统实时容错算法

实时多处理器容错算法是实时系统研究领域的一个重要课题.提出了一个动态处理非周期实时任务的容错算法.提出了对待实时任务的基、副版本采用不同的处理器分配策略.对于基版本,尽量提前任务的开始时间;对于副版本,尽量延迟任务的开始时间.通过实验模拟研究了算法的性能.实验表明,算法调度的成功率跟处理器个数、任务数以及任务计算时间有关.与采用单一处理器分配策略相比,具有较高的调度成功率.     

一种面向多处理器系统的在线低功耗调度算法

针对当前多处理器系统中的散热瓶颈问题,基于处理器动态速度调节技术,提出了一种在线低功耗调度算法(PEQUI).PEQUI以动态均衡算法(EQUI)为基础,公平地分配处理器资源,依据处理器功耗与运行速度间存在非线性关系,以正比于系统任务数的方式调节处理器运行速度.与传统低功耗调度算法相比,PEQUI仅基于当前待调度任务的信息进行决策,决策参数少.以能量消耗与任务执行流时间为评价算法性能的指标,利用在线竞争分析方法证明了PEQUI算法与最优离线算法相比可达到常数竞争比(10).模拟结果表明,PEQUI比最近到达处理器共享算法(LAPS)和恒速EQUI算法能更好地优化系统整体性能和能量消耗.在相同负载情况下,与LAPS相比,PEQUI在降低功耗的同时系统平均运行时间也降低了近7%.     

多核平台下一种新的实时调度模型

针对当前嵌入式多核平台下的实时调度模型没有考虑实时周期任务之间的制约关系这一不足,提出了一种能够描述实时周期任务之间存在简单制约关系的任务时序图(TTOG)模型,该模型不仅能体现任务实时性需求,还能反映周期任务之间的依赖关系.根据该模型,提出了一种剩余执行时间越短越优先(RETSF)的调度方法.该方法将根据某个周期任务距离时限的剩余执行时间动态地调整调度方案,与先来先服务(FCFS)算法相比较,在提高系统利用率,以及降低时限丢失率方面有很大改善.     

实时CORBA技术综述

实时CORBA系统是一类重要的服务应用，实时CORBA技术不仅具有通用实时系统的特征，而且是基于网络通信的分布计算，有着区别于其它实时系统的特征。本文针对OMG组织制订的实时CORBA规范、固定优先级驱动的RM和DM调度算法、动态优先级驱动的EDF和LST调度算法、混合优先级驱动的MUF调度算法、多处理器和分布系统中的优先级驱动调度方法MPCP、资源访问与控制协议PCP和CPP、端到端实时CORBA系统调度模型、实时CORBA应用系统TAO系统和NraD/URI CORBA系统以及相关支撑技术，包括实时操作系统和实时通信技术等方面，对实时CORBA技术进行分类、比较、分析和综述。     

周期实时任务在多处理器下的可调度条件

研究硬实时周期任务在并行等同多处理器下的可调度问题．在任务/处理器静态绑定和周期任务静态优先权配置策略下，依据单处理器情形下的最优配置RM策略作为一项任务在单个处理器上的可配置条件，给出了以实时任务集合的任务数、利用率和与利用率递减排序为特点的在多处理器环境下的可调度新判据．新判据拓宽了基于阈值判据的可判定范围．最后通过实例分析说明新判据的有效性．     

具有自适应特性的反射式动态弹性调度模型

针对负载可以弹性变化的实时系统,提出了一种两层结构的动态调度模型,实现具有自适应性的反射式弹性动态调度.上层调度采用弹性调度算法动态地调整实时任务的作业周期,底层调度采用MUF调度算法,保证实时任务的优先级次序.通过反馈控制,弹性调度器对实时系统的性能进行动态优化.在保证实时任务服务质量(Quality of Service QOS)要求的前提下,通过改变实时任务的运行周期,接纳尽量多的服务请求,以达到提高实时系统吞吐率的目的.模拟测试表明本模型适用于实时任务负载可以动态变化的实时系统中.     

混合实时任务的两级调度策略

面向混合实时任务应用,提出一种两级结构调度策略:对周期性实时任务采用时间触发,非周期性实时任务则采用事件触发.先建立任务模型并定义相关概念,然后给出调度策略的架构,并对调度算法、可调度性、抖动、时标间隔及调度策略优化等进行研究.结合windows CE.NET进行的调度策略实验验证结果表明,该方法能提高混合实时任务的确定性,减小抖动.文中最后讨论了时标间隔对处理器利用率和周期分辨率的影响.     

基于时间触发和事件触发的混合实时任务两级调度策略研究

针对混合实时任务应用, 提出一种两级结构调度策略：对周期性实时任务采用时间触发, 非周期性实时任务则采用事件触发．先建立任务模型并定义相关概念, 然后给出调度策略的架构, 并对调度算法、可调度性、抖动、时标间隔及调度策略优化等进行深入研究．结合Windows CE.NET进行了调度策略实验验证, 结果表明, 该方法能提高混合实时任务的确定性, 减小抖动．最后, 讨论了时标间隔与处理器利用率及时标间隔与周期分辨率的关系．     

合理反馈机制下保证混合业务QoS的调度算法

针对正交频分复用(orthogonal frequency division multiplexing, OFDM)系统多用户中继场景中混合业务对时延的不同需求,提出一种基于合理反馈机制下的降低时延、保证混合业务服务质量的调度算法(mixed services with feedback scheduling , MSFS)。MSFS算法针对用户实时业务及非实时业务的不同需求分别采用不同的调度准则及反馈方式,以达到优化系统性能的目的。针对实时业务,增大其调度优先级以减少等待时延,并在其等待时延接近时延门限时,使其调度优先级迅速增加,以避免丢包;针对非实时业务,加入时延公平因子,使得该类用户业务在时延公平性方面得到改善,同时设置适当的反馈门限,在不影响业务服务质量需求的同时达到降低系统反馈量的目的。仿真结果表明,该算法在保证系统吞吐量和用户公平性的同时,不仅能够有效降低实时用户的时延,而且能够较大程度地减少系统反馈量。     

现场硬实时网络调度算法研究

研究了实时任务死线不大于其周期的任务集调度条件与硬实时网络调度算法约束条件，论证了计算时间复杂度，并将单调死线调度方法直接用于非周期任务调度．最后对调度算法的可调度性进行了严格测试．     

一种新的静态优先级在线节能调度算法

合理运用动态电压调整技术可有效降低嵌入式实时系统能耗.针对静态优先级实时调度,提出了一种能够有效分析松弛时间并尽可能平衡分配松弛时间的在线节能调度算法TPSRM.设计了一种两段式频率执行策略来改变任务执行时间的分配,能充分在线分析各种形式的松弛时间.通过尽可能合理降低高优先级任务的处理器执行频率来实现有效的在线频率调整.实验结果表明TPSRM算法可实现较好的节能效果.     

多处理机实时分类调度算法研究

讨论了在多处理机实时系统中周期任务可调度性的充要条件和非周期任务的分布函数,并进行了任务调度模型设计。通过处理器利用率实现对实时任务的动态分类,并根据这些分类进行处理器分派。仿真结果表明,这种方法能有效提高实时任务的调度成功率;在处理器达到5个时,调度率可达98%以上,基本属于最优调度,平均负载达到最小且趋于平稳。     

多处理机系统中最小平均流调度的模糊控制算法FBRUNO

多处理机系统中，任务调度是一个关键问题，是多机操作系统的重要内容。本文基于模糊集合理论提出了一种最小平均流时间算法的新的实现方案。并对其有效性进行了讨论。最后，通过几个实例对本算法的应用进行了说明。     

考虑缓存预热时间的多核调度系统验证

随着多核架构在实时系统中的应用,多核实时调度已成为研究热点.在多核全局调度中,任务在多核间迁移通常会引起缓存预热.在严格实时调度中,这部分时间可能导致任务错过截止时间.为此基于调度理论的测试方法比较悲观,在作可调度性判定时,引入模型检测.考虑缓存预热时间的抽象模型仅局限在双核,提出一种建模方法,能够在更多核的条件下,验证调度系统的正确性和可调度性.     

基于混合遗传算法的并行多处理器系统的任务调度

针对并行多处理器系统的任务调度问题,提出一个新的混合遗传算法(HGA)．HGA使用拓扑排序表的交叉来保证下代的合法性和搜索空间的全局性,为了提高HGA的收敛速度,根据拉马克进化理论,在交叉算子中使用贪婪策略来提高个体的适应值,模拟结果显示HGA的调度结果和算法的时间复杂性都是令人满意的．     

OFDMA下行链路混合业务调度算法

提出了一种基于正交频分多址接入系统的混合业务分组调度算法.在调度过程中,对信道状况好的实时业务用户的数据包采用推迟发送的策略.先对缓冲区中累积数据包较多的实时业务用户分配资源,随后对非实时业务用户采用正比公平算法分配剩余的资源.仿真结果表明,提出的算法较好地满足了实时业务的延迟需求,并提高了非实时业务的系统吞吐量.     

实时调度问题的形式化描述及分析

使用自动机理论建立了一个用于分析实时调度问题的、可化简归并的形式化方法。通过分析单个任务的状态变化过程来构造实时系统的自动机。对自动机的状态进行化简和归并,大大降低了讨论实时调度问题的复杂度。以优先级上限协议为例构造了确定有穷自动机并使用该自动机证明了优先级上限协议的性质。