星载计算机系统高优先级恢复容错调度算法

为了在星载异构容错计算机上调度星载任务，在给出了星载计算机系统的容错调度模型的基础上，提出了一种星载计算机系统高优先级恢复容错调度算法（OHFSA），该算法通过引进可靠性代价量化了容错系统在维护容错调度时所需要的开销，并在调度过程中充分考虑了容错调度的实时性和低可靠性代价．同时，采用高优先级恢复机制可及时响应紧急时限下的恢复任务，从而提高了星载任务的整体实时性能．实验验证表明，OHFSA随着计算时间的增加，其所需的可靠性代价也相应增大．仿真结果表明，在任务负载不断增加的情况下，OHFSA的执行时间比目前算法减少20%～30%，特别是在恢复任务优先级比其主任务提高1个级别时，响应时间可减少近8．7%．     

基于非精确计算的保证计算质量的容错调度

针对单处理器系统的周期性实时任务集,基于非精确计算,提出FT／FA（Fault Tolerance／Frequency Assurance）调度方法．该方法对任务的强制部分进行容错,保证出错时仍能满足任务的时限要求;采用对可选部分的执行频率进行保证,保证任务的计算质量．此外。给出了FT／FA方法的可调度条件,并分析了该调度方法的性能．     

分布式系统的实时容错任务调度算法设计

提出一种分布式实时容错调度算法,并研究了该算法的时间复杂度．这种容错调度算法称为“副版本后调度（ＢＫＣＬ）算法”,该实时容错调度算法可以同时调度具有容错需求的实时任务和无容错需求的实时任务,所产生的调度可保证在分布式系统中一个节点机失效的情况下,具有容错需求的实时任务仍然可在截止时限内完成．     

支持优先级约束任务的容错调度算法

为了解决异构分布式系统中可靠调度问题,提出一种考虑处理机链路通信竞争的,支持优先级约束任务的容错调度(FSPCT)算法。该算法使用通信竞争模型描述处理机之间通信,在备份成本最小化和备份任务最早完成之间寻求平衡点。对主副版本任务的最早开始时间进行分析,并限定了所执行的处理机,在处理机出现故障后任务可以顺利执行。实验结果表明FSPCT算法的综合性能优于现有一些算法。     

分布式系统的实时容错任务调度算法设计

提出一种分布式实时容错调度算法,并研究了该算法的时间复杂度,这种容错调度算法称为“副版本后调度（ＢＫＣＬ）算法”,该实时容错调度算法可以同时调度具有容错需求的实时任务和无容错需求的实时任务,所产生的调度可保证在分布式系统中一个节点机失效的情况下,具有容错需求的实时任务仍然可在截止时限内完成。     

分布式系统中一种基于EDF的实时容错调度算法及其分析

将任务分配算法与处理器调度算法相结合，提出了分布式系统调度的一般方法。给出当处理器调度算法为EDF，且容错采用主／副版本技术时任务集所需最小处理器个数的计算公式。给出满足以上条件的任务分配算法（针对任务集动态产生的情况）和任务集所需最小处理器个数算法。模拟结果显示：算法是有效的，且表明任务集所需处理器数与任务资源利用率有关。     

基于副版本零调整策略的实时任务主副版本容错调度

为了降低硬实时周期性任务主副版本容错调度的副版本调整开销,提出了一种BEDFNENF容错调度算法.采用反向最早截止期优先(BEDF)策略为副版本预分配处理器时间,运行时则采用零调整最早通知时间优先(NENF)策略调度主版本.结果表明,BEDF-NENF算法能够按照最后机会策略调度副版本.当主版本错误概率不大于0.05时,BEDF-NENF算法的副版本调整平均比较次数和副版本调整时间比率均为0,与BEDF-RM算法、BEDF-EDF算法、BEDF-ENF算法的主版本完成率之差约为1%.BEDF-NENF算法不仅能够取得与同类调度算法接近的主版本完成率,而且能够通过省略副版本重新调整操作来降低调度的复杂性,节省调度时间.     

多处理机系统的高效实时容错调度算法

在容错调度算法副版本后调度算法（ＢＫＣＬ）的基础上,提出一种高效实时容错调度算法（ＥＢＫＣＬ）．对于具有容错需求的实时任务而言,由实时容错调度算法所产生的调度可保证在多处理机实时系统中一个处理机失效时,实时任务仍然可在截止时限内完成．在ＥＢＫＣＬ算法中,如果两个实时任务的基版本分配在不同的处理机Ｐｉ和Ｐｊ上,且这两个实时任务的副版本被调度到同一个处理机Ｐ上,则两个副版本之间允许有时间上的重叠．模拟实验证明,使用多个实时任务副版本之间的时间重叠技术,ＥＢＫＣＬ大大提高了调度的性能     

多处理机系统的高效实时容错调度算法

在容错调度算法副版本后调度算法的基础上,提出一种高效实时容错调度算法。对于具有容错需求的实时任务而言,由实进容错调度算法所产生的调度可保证在多处理机实时系统中一个处理机失效时,实时任务仍然可在截止时限内完成。在ＥＢＫＣＬ算法中,如何两个实时任务的基版本分配在不同的处理机Ｐｉ和Ｐｊ上,且这两个实时任务的副版本被调度到同一个处理机Ｐ’上,则两个副版本之间允许有时间上的重叠。     

面向飞行控制系统应用的容错计算机系统设计

在设计飞控计算机时采用了冗余技术(4余度容错计算机)，保证系统实现人以两次故障工作，三次故障安全(fo／fo／fs)．采用完善的余度管理技术和余度表决监控算法，进行故障的隔离定位和屏蔽，飞控计算机采用多速率任务调度策略，保证了系统的实时性．作者详细地描述了该容错计算机的软件／硬件设计结构、系统调度策略和余度管理算法，     

容错模式下TTCAN系统矩阵的实时调度

TTCAN协议是一种CAN总线高层协议,在现行CAN协议的基础上引入了时间触发机制.由于消息组中的消息具有多样性,各个消息的周期可能相差很大.针对这一问题,采用最大公约数(GCD)方法来加以解决;利用遗传算法对调度表进行优化,提高了网络利用率,并且提高了事件触发任务的实时性能.对调度表的容错性能进行了分析,并提出了基于后面优先原则的仲裁窗方法.实验结果表明,该算法优化系统网络调度,保证了传输的实时性.     

并行防火墙系统的容错加权散列调度算法

提出一种用于并行防火墙系统的容错加权散列调度算法,该算法在散列调度的基础上增加了加权处理和容错机制．加权处理根据防火墙组件的不同处理能力调度访问请求,保证处理能力强的防火墙组件处理更多的访问流量,提高了系统的整体效率;容错机制在防火墙组件失效或恢复正常时利用基于连接调度的过渡散列表记录不稳定连接,避免已有连接因算法参数改变而失效．算法性能分析表明：该算法综合了散列调度的高效性、低内存开销以及连接调度的稳定性等优点,为并行防火墙系统提供高效可靠的调度服务．     

An Efficient Real-Time Fault-Tolerant Scheduling Algorithm Based on Multiprocessor Systems

In the context of real-time fault-tolerant scheduling in multiprocessor systems, Primary-backup scheme plays an important role. A backup copy is always preferred to be executed as passive backup copy whenever possible because it can take the advantages of backup copy de-allocation technique and overloading technique to improve schedulability. In this paper, we propose a novel efficient fault-tolerant ratemonotonic best-fit algorithm efficient fault-tolerant rate-monotonic best-fit （ERMBF） based on multiprocessors systems to enhance the schedulability. Unlike existing scheduling algorithms that start scheduling tasks with only one processor. ERMBF pre-allocates a certain amount of processors before starting scheduling tasks, which enlarge the searching spaces for tasks. Besides, when a new processor is allocated, we reassign the task copies that have already been assigned to the existing processors in order to find a superior tasks assignment configuration. These two strategies are all aiming at making as many backup copies as possible to be executed as passive status. As a result, ERMBF can use fewer processors to schedule a set of tasks without losing real-time and fault-tolerant capabilities of the system. Simulation results reveal that ERMBF significantly improves the schedulability over existing, comparable algorithms in literature.     

改进的最低松弛度优先周期任务调度算法

最小松弛度优先LLF(Least Laxity First)调度算法结合任务执行的缓急程度来给任务分配优先级,任务的松弛度越小,越需要尽快执行.然而,当多个任务松弛度值接近时,算法造成任务之间的频繁切换或颠簸现象,增大了系统因调度引起的开销,限制了调度算法的实际应用.寻找合理的任务执行时间片,对最低松弛度优先调度算法进行改进,一直是研究的热点.该文在深入研究周期任务特点的基础上,给出了最少切换次数的最低松弛度优先调度算法.仿真实验表明,算法是有效的.     

基于双优先级队列的异构分布式控制系统容错调度算法

在对分布式控制系统进行分析的基础上,给出了任务模型和处理器模型.为了调度多种实时性的任务,提出了双优先级队列调度算法,用于调度每个处理器上的任务.该算法设置2个优先级队列,其中高优先级队列用于调度实时任务,低优先级队列用于调度非实时任务,高优先级队列中的任务可抢占低优先级队列中的任务.在此基础上,采用版本复制技术使系统具有容错能力,并分析了任务的容错可调度条件.基于此,采用首次适应的启发式任务分配策略,将任务分配到各个处理器上,在确保任务容错可调度的条件下使处理器负载均衡.仿真结果表明所提出的算法是有效的.     

基于EDF的实时数据库动态容错调度算法

实时数据库系统的事务调度过程中,对于即将完成的事务的抢占会造成CPU时间的浪费,降低系统的性能.针对实时数据库中的周期性实时事务提出了一种PEA(preemptive estimate algorithm)软件容错调度算法,算法基于EDF(earliest deadline first)进行事务调度,并结合负载优化算法进行适当调整,采用抢占评估策略来确定是否允许事务抢占,以最大化系统的资源利用率.通过实验测试,证明其具有良好的性能,能有效提高事务的成功率.     

基于簇的可动态调整的分层负载均衡算法

为了提高分布式系统的性能,设计了能根据节点当前任务负载强度和调度能力,动态地改变集群的逻辑控制结构的2层负载均衡算法.算法把系统中的节点分成多个簇,每个簇有1个调度节点和若干个工作节点,簇内工作节点形成算法的第1层,执行用户提交的任务;簇间的调度节点形成算法的第2层,调度节点间通过相互协作,均衡簇间的负载.算法可以通过分裂簇增加调度节点的方式来提高系统的调度能力;通过合并簇增加工作节点的方式来提高系统的执行能力.对于不同类型任务,算法能根据任务到达流的速度调整逻辑控制结构,从而提高CPU利用率.测试结果表明,该算法不仅能提高系统性能,而且经过调整后的系统会进入稳定状态.     

A Novel Processor Scheduling Schema in Programmable Router Based on Queue Length Thresholds

Programmable router may execute computing tasks except for forwarding IP packets. How to schedule the CPU in the programmable router is an important issue that needs to be solved. In this paper, the authors establish general software architecture of programmable router firstly. Based on this architecture, authors present a novel CPU scheduling algorithm based on queue length thresholds. We model this algorithm using stochastic Petri nets. The analytic results show that this scheduling algorithm can guarantee the requirements of computing of best-effort flows and QoS flows in prograrmmable router at the same time.     

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

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