Monotone Additive Schwarz Algorithms for Solving Two-Side Obstacle Problems

Additive Schwarz algorithms for solving the discrete problems of twrvside obstacle problems are proposed. The monotone convergence of the algorithms is established for M-matrix and the h-independent convergence rate is proved for S-matrix. The so-called finite step convergence for coincident components is discussed for nondegenerate discreted problems.

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.

TT-RMS:时间触发网络通信表生成算法

针对时间触发网络依据全局时间进行触发数据通信的特点,提出了一种基于单调速率调度(RMS)调度机制的通信表生成算法时间触发单调速率调度(TT-RMS),来生成时间触发网络的通信表.TT-RMS算法在安排消息时间槽过程中,首先根据消息周期,计算出各个链路的总负载,再根据链路的消息周期和总负载,通过RMS机制进行消息排序,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度,优化了消息的调度过程.所提算法的计算时间复杂度为O(n2),空间复杂度为O(n).目前广泛研究和应用的可满足性理论(SMT)通信表生成方法,其计算时间复杂度通常是多项式级,有时计算时间不收敛.实验结果显示,TT-RMS调度的网络单个链路负载最大可接近100%,计算时间在1 ms左右,平均可调度网络负载是SMT方法可调度网络负载的两倍.TT-RMS通信表生成算法具有计算时间短,可调度消息负载多等优点,可以更好地满足航空航天复杂系统中上千条实时消息流的调度需要.

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

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

改进的TT-RMS调度表生成算法

基于时间触发以太网的网络模型与消息模型,改进了时间触发单调速率调度(TT-RMS)通信表生成算法,用于生成时间触发以太网的调度表。改进后的TT-RMS算法,首先根据消息的周期属性,计算出消息调度的集群周期长度,其次根据消息的周期及经过的路径长度,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度。实验结果显示,改进后的TT-RMS算法,可以在多跳网络环境下,基于不同长度和周期的消息,生成时间触发消息调度表,同时生成的调度表能够满足消息的时延需求。

一种基于非抢占RM算法的可行性判决算法及应用

为中断服务例程建立了任务模型,在该模型的基础上给出了中断服务例程集使用非抢占RM调度的可行性的充分必要条件,并且基于该条件提出了一种新的非抢占RM算法的可行性判决算法。进一步地,给出了如何改进不可调度例程集的方法,并且将该方法应用到一个具体工程项目中,取得较好的效果。

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

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

单调比率(RM)调度算法及应用

介绍了任务死线不大于其周期的任务集调度条件分析及算法实现。这种约束条件放松, 有利于周期与非周期任务混合模型调度。同时,分析了以往调度算法中单调比率调度算法约束条件, 并指明了计算时间复杂度的缺点。因而,在RM算法基础之上提出一种实时系统调度算法及实现流 程图,并对提出的现场级实时调度算法进行了对比测试。

基于RM调度的任务抢占次数最多分析

传统的实时系统可调度性分析方法往往忽略任务抢占的时间开销,然而在重负载情况下,如果任务抢占次数很多,则由此带来的时间开销将不可忽略。该文分析基于单调速率调度算法的系统中任务抢占次数最多需要满足的条件,提出通过修改任务参数来减少抢占次数的方法,减少了系统在最坏情况下的任务响应时间。

基于改进RMS算法的多核嵌入式系统总线周期调度表优化设计

远程指挥控制决策系统是军事作战体系的“神经中枢”,有效、高速、可靠地获取战场信息一直是制约战场态势感知的一个瓶颈。针对这个问题,讨论一种同构的多核嵌入式系统,该系统能够通过控制多条总线增加信息获取源,并通过信息源的备份增加信息的可靠性和稳定性。针对该系统的总线周期表优化问题,给出了系统任务模型,对RMS算法改进策略,并进行改进RMS算法可调度性分析。实验结果表明该算法解决了RMS算法适用于多核嵌入式系统的瓶颈问题,能够在多个处理器中同步进行总线资源调度,并且可以满足总线动态负载平衡,提高总线传输效率和系统的可靠性。

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

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

经典RM调度算法在无人机发动机试车台软件开发中的应用

现代无人机发动机测试项目多、实时性要求高，早期的基于非实时的片上系统不能很好地满足测试要求。本文以某型无人机发动机试车台软件系统实际开发为例，在软件开发中引入了经典RM调度算法，分析了经典RM算法的可调度性判定法则，描述了片上系统任务集设计过程，进行了RM可调度性理论判定。通过对任务集的实际可调度性测试表明：硬件利用率最大可达到93．8％，达到设计指标要求；系统运行稳定可靠，并取得预期效果。

基于CAN总线实时应用的可靠调度性研究

CAN总线是一种高级的串行通信协议,适用于各种分布式控制系统。在实时应用中,标准的CAN协议使用静态优先级算法,对传输信道的利用率比较低。对基于CAN总线通信的动态优先级调度算法进行研究后,提出了一种基于指数分配方式的MTS算法,在保证强实时性消息的同时兼顾了低优先级消息的公平性。

基于逻辑“或”约束优化的实时系统设计

标准约束优化问题的等式或不等式约束之间是逻辑“与”关系,目前已经有很多高效、收敛的优化算法.但是,在实际应用中有很多更一般的约束优化问题,其等式或不等式约束之间不仅包含逻辑“与”关系,而且还包含逻辑“或”关系,现有的针对标准约束优化问题的各种算法不再适用.给出一种新的数学变换方法,把具有逻辑“或”关系的不等式约束转换为一组具有逻辑“与”关系的不等式,并应用到实时单调速率调度算法的可调度性判定充要条件中,把实时系统设计表示成混合布尔型整数规划问题,利用经典的分支定界法求解.实验部分指出了各种方法的优缺点.

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

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

网络化运动控制系统的经典调度算法应用研究

网络化运动控制系统作为一类特殊的实时系统,其系统的性能与资源(处理器、网络)的调度密切相关,将实时调度理论应用于网络化运动控制系统非常必要。在对用于单处理器的经典实时调度算法(RM和EDF)以及网络调度的研究现状进行综述的基础上,对网络调度和任务调度的异同点及网络调度的实现方法和应用技术进行了研究。最后,对RM和EDF两类调度算法在网络化运动控制系统中的应用及调度优化问题进行了仿真研究。

多功能车辆总线周期扫描表优化设计

针对参与通信的各周期信息特点设计优化的多功能车辆总线周期扫描表对提高列车通信网络的实时性能具有重要作用;标准推荐的周期轮询算法存在周期信息分布不均匀,带宽利用率相差较大的问题,在对周期扫描表的优化设计方法进行深入研究后,提出基于模拟退火算法的优化方案。建立了周期信息通信模型,详细阐述了通信抖动的概念并对其进行了定义。给出了优化目标函数并采用模拟退火算法进行求解,对算法的几个关键步骤进行了设计,并采用改进策略提高了模拟退火算法效率。通过实例仿真证明该算法实现了周期信息在整个宏周期范围内的均匀分布,优化了周期扫描表的构造。

一种新型的实时调度算法

在嵌入式系统中,系统的实时性很大程度上取决于任务调度策略。对如何提高系统实时性的研究已经成为该领域的一大热点。文中针对传统的忽略了作业所能承受的等待时间的能力仅以等待时间的长短而来衡量优先级的先来先服务(FCFS)算法,和仅以任务的周期长短来设置优先级而导致那些周期长但急需要执行的任务无法被调度的速率单调(RM)算法的缺陷,提出一种新的动态设置优先级的方法—剩余时间法。该方法以任务的等待时间和周期共同来决定优先级。通过分析和实验表明该方法兼具RM和FCFS的优点。它不仅考虑到短周期任务应优先执行,而且同时也把任务等待时间作为评价优先级的重要因素,实验结果证实了该方法能更有效地提高实时任务的完成率和CPU的利用率。

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

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

实时调度算法研究

对实时调度进行了讨论：研究了单处理器下的经典调度算法：单调速率调度、最早死线调度和最短空闲时间优先调度；分析了多处理器系统中的典型调度算法：对分布式系统中的两种调度算法：广义单调速率调度和分布式风车调度做了简要论述；指出实时调度研究策略方向。