一种基于混合任务集的高能效调度算法

动态电源与频率调整技术能够帮助实时系统显著减少能耗,之前的研究大多聚焦于基于周期性任务的线程调度算法,却很少考虑周期性与非周期性任务混合的模型。同时,尽管基于CPU利用率的DVS算法可以从系统级上减少能耗,但不能保证实时性。本文提出一种新的算法,它结合减慢因子的DVFS调度算法与系统级的DVS技术,融合PID控制器与自适应的权衡策略为软实时系统提供更好的能耗减少方法。该算法的能耗在服务器利用率低于25%的情况下比加州大学提出的算法下降了14.2%²5.9%,周期性任务超过时限率低于3%。     

1553B总线上消息的实时调度

为了优化1553B总线传输性能,降低总线上消息传输的延迟时间,讨论了周期消息和非周期消息混合传输情况下总线上的消息调度策略。首先,借鉴周期任务的调度模型对周期消息进行建模,提出了改进的速率单调消息调度算法。然后,利用排队论建立非周期消息的M/M/1排队模型,定量分析了1553B总线的平均响应时间和总线利用率等时间性能参数,并对非周期消息的延迟时间进行优化,推导出总线最优服务率和最小平均延迟时间的计算公式,给出了非周期消息的调度算法。最后,对上述算法在消息混合传输下的可调度性进行了验证。实验结果表明,在总线利用率达96%时,混合消息的平均响应时间为0.713ms。在消息混合传输的情况下,非周期消息的平均响应时间和M/M/1排队模型下理想的非周期响应时间偏差不超过10%。上述算法时间响应特性良好,能够保证周期消息和非周期消息的实时调度。     

Optimal Checkpoint Placement on Real-Time Tasks with Harmonic Periods

This paper presents an optimal checkpoint strategy for fault-tolerance in real-time systems where transient faults occur in Poisson distribution. In our environment, multiple real-time tasks with different deadlines and harmonic periods are scheduled in the system by rate-monotonic algorithm, and checkpoints are inserted at a constant interval in each task. When a fault is detected, the system carries out rollback to the latest checkpoint and re-executes tasks. The maximum number of re-executable checkpoints and an equation to check schedulability are derived, and the optimal number of checkpoints is selected to maximize the probability of completing all the tasks within their deadlines.     

两种经典实时调度算法的研究与实现

速率单调（RM）调度和最早截止期限优先（EDF）调度在实时调度领域占有重要低位。基于一个x86体系结构的小系统上设计实现RM和EDF调度算法，并在不同的工作负载下，以任务截止期错失率作为衡量不同任务调度算法性能优劣的指标，对两种算法进行了性能分析和比较。在通常情况下，RM和EDF都可以保证任务成功调度，EDF算法可承受较多的工作负载。但是随着负载的增加，EDF算法性能急剧下降，到一定过载程度，EDF算法性能低于RM算法。     

基于混合搜索的含逻辑“与”“或”的RM优化算法

相对于标准约束优化问题,广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS）,将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.     

基于多核ARM的数控系统实时性研究

随着数控系统的不断发展,数控系统对精度和速度有了更高的要求,这都对当前普遍采用的单核处理器平台提出了严峻的挑战.基于同构的四核ARM处理器平台,在添加了实时补丁的Linux系统环境下,根据数控系统中硬实时任务、软实时任务、非实时任务并存的特点,把数控系统任务合理的分配到多核ARM上运行,并采用改进的RM算法进行调度,最后对新的任务调度算法进行实时性能测试.本调度模型能够解决了数控系统混合任务调度的问题,并能满足数控系统对实时性的要求.     

基于树状线性规划搜索的单调速率优化设计

改善单调速率(rate monotonic,简称RM)可调度性判定算法的效率,是过去40年计算机实时系统设计的重要问题.最近,研究人员把可调度性判定问题扩展到了更一般的优化设计问题,即,如何调节在区间可选择情况下的任务运行时间,使得:(1)系统RM可调度;(2)系统的某个性能(如CPU利用率)达到最优.在已有的求解实时系统RM优化设计问题的方法中,都是先把原问题建模成广义约束优化问题,然后再对广义约束优化问题进行求解.但现有方法的求解速度较慢,任务数较多时不再适用.提出一种求解优化问题的方法——基于树状的线性规划搜索(linearprogramming search,简称LPS)方法.该方法先将实时系统RM优化设计问题建模成广义约束优化问题,再将其分拆成若干线性规划子问题,然后构造线性规划搜索树,利用剪枝搜索算法求解部分线性规划子问题,最后得到优化解.实验结果表明:LPS方法相比于已有的方法能够节省20%~70%的求解时间,任务数越多,节省时间越多.该研究成果可以与计算机可满足性模定理(satisfiability modulo theories,简称SMT)领域的多个研究热点问题联系起来,并可望改善SMT问题的求解效率.     

基于双曲线边界的多处理器实时任务可调度性判定

Lopez等学者求解出基于单调速率算法和首次适应分派策略的多处理器实时任务可调度性判定边界.该边界在所有O(m)复杂度的判定边界中是最优的.基于Bini等学者针对单处理器提出的双曲线可调度性判定方法,给出了一种多处理器实时任务可调度性判定边界.新边界在相当数量的利用率分布下明显优于已有边界.新边界与已有边界具有相容性,所以虽然新边界无法在所有情况下超越已有边界,但在实际应用中可联合两种边界进行判定,在不增加计算复杂度的同时全面提高可调度任务集的数量.     

一种增强任务关键无线网络可信性的消息调度策略

任务关键无线网络面临实时和安全等可信因素的挑战,而已有的消息调度算法忽略了安全因素。提出一种安全感知的实时调度算法(SAMS)。在不违背关键消息的实时约束和安全约束的前提下,该算法能最大化提升系统的安全服务质量。仿真结果显示SAMS的有效性和健壮性。     

Research on run-time overhead of RM and improvement

The rate-monotonic (RM) algorithm is a classic fixed priority real-time scheduling algorithm. However, in most embedded real-time systems where the workload is composed of many tasks of high frequency and short execution time, the overheads from preemptions of the real-time operating system will lead to a low resource utilization rate if the RM algorithm is directly used. By studying the preemption relationship of the tasks scheduled by RM algorithm, a model of preemption overheads is established with task attributes, based on which the run-time preemption overheads of RM algorithm are reduced by optimizing the start time of the tasks in embedded real-time systems. Finally, the experimental results show the validity of the proposed strategy. __________ Translated from Journal on Communications, 2008, 29(2): 79–86 [译自: 通信学报]