一种混合实时任务系统的公平调度算法

Baruah提出的PFair公平调度理论是周期任务在多处理器系统上的最佳实时调度理论,而在实际实时系统中,实时任务往往是由周期任务和非周期任务组成的混合任务系统．在研究PFair公平调度理论和算法的基础上,提出了基于服务器思想的公平调度方案,使得PFair调度理论适用于多处理器系统中混合任务的实时调度,并提出了对非周期任务进行实时调度的3种策略,给出软实时性非周期任务在不同调度策略下的最坏响应时间计算公式,并且证明了计算公式．     

基于回卷恢复的数控系统实时容错调度策略

针对数控系统对时间确定性和可靠性的要求,建立混合关联任务集描述模型,提出了基于回卷恢复机制和最佳优先（BF）算法的容错调度策略.该策略对数控系统关键任务的执行过程进行周期性分段验证,通过保存正确的检查点状态,使得出现瞬时故障时任务可以从检查点开始继续执行,从而以较低的计算损失达到容错的效果.与传统的实时容错调度算法相比,基于回卷恢复机制的容错调度策略能很好地适用于数控系统多类型任务并存和任务间相互约束的特点,同时,通过降低错误恢复所需的时间开销,有效地提高了系统的资源利用率.该算法应用于数控系统的有效性在实例分析和算法模拟研究中得到验证.     

热工过程工业以太网中混合调度算法的研究

为提高工业以太网通信的实时性、确定性以及可靠性,分析了现有工业以太网的通信机理,提出了一种新的实时通信机制;并针对热工过程中随机负载的特点,提出混合调度算法．机理分析和仿真结果表明,该算法对具有随机负载的热工过程有很好的实时性．     

基于多核处理器平台的公平调度算法

为了减少多核处理器系统全局调度算法中共享L2cache抖动,在Pfair调度算法基础上提出一种新的Cache感知的软实时公平调度算法.通过对WSS(work set size)、子任务截止时间和任务负载建立多因素优先级模型,并将此优先级模型应用到改进后的Pfair算法中,该算法的调度决策在系统负载较重的系统中对WSS具有自适应性.模拟实验结果显示:在对称4核和8核处理器系统中,该算法任务丢失率低,且在系统负载重时能够减少共享L2cache抖动,其整体调度性能优于传统的G-EDF(global-earliest deadline first)调度算法和Pfair调度算法.     

μC/OS-Ⅱ混合调度算法的硬件实现

针对μC/OS-Ⅱ过于单一的调度算法引起的应用局限性,提出一种混合调度算法.在原有的基于优先级的抢占式调度算法基础上,扩展了同级调度.对于具有同一优先级的多任务的任务组,按照用户设定的优先级阈值进行划分,优先级高于该阈值为实时任务组,否则为非实时任务组.同级实时任务组采用较公平的时间片轮转算法,同级非实时任务组采用开销较少的先来先服务算法.算法基于FPGA实现,由VHDL描述,通过ISE 10.1仿真,仿真结果表明,硬件任务调度器保证了调度的正确性,提高了系统的实时性.     

基于启发搜索策略的飞行仿真系统实时调度算法

针对飞行仿真系统中多种类型任务并发执行及任务具有严格定时限制和时序约束的特点,探讨了飞行仿真系统混合任务集的实时调度问题.通过建立混合任务集调度模型,把飞行仿真系统实时调度描述成一种受约束的在状态空间上的路径寻优问题.基于对启发式估价函数的设计,利用启发式搜索策略在所有符合约束的状态节点中搜索使启发式估价函数值最小的节点,经节点扩展得到了使混合任务集延迟时间最小的可行调度.建立飞行仿真系统混合任务集实时调度构架对调度算法进行试验验证,结果表明,该算法有效解决了飞行仿真系统中多种类型任务集成调度问题,并能以较低的时间开销满足飞行仿真系统对响应时间的一致性要求.     

基于Linux的多媒体任务调度算法

为了在Linux系统中实现对多媒体任务灵活有效的调度支持，作者引进并实现了多媒体任务模型ARB．与周期任务模型、零星任务模型等传统实时任务模型相比，对ARB任务模型做了如下几方面的改进：（1）不需要预先知道任务的计算资源需求量或最坏情况执行时间，以满足多媒体任务对资源需求动态多变的特点；（2）任务相邻两次执行之间需要满足一定的时间距离约束，以确保多媒体任务的执行延迟和抖动，使执行结果更为流畅；（3）多媒体任务以指定的速率执行，且该速率在任务执行过程中可以动态调整，以适应用户需求和系统可用资源的动态变化，在具体的内核调度算法实现中支持执行速率、截止期限、周期等重要实时任务属性的定义．实验结果表明，基于ARB，Linux内核可以为多媒体任务提供如下调度支持：（1）保证任务以指定的速率执行，且速率在任务执行过程中动态可调；（2）通过任务执行时的时间距离约束，保证任务的执行延迟和抖动；（3）通过准入控制和自适应QoS协商机制，实现资源的动态请求．因此，基于ARB任务模型，Linux内核不仅可以实现对多媒体任务灵活有效的调度支持，而且使得这些任务具有较好的可控性．这一点对实时任务很重要，有助于提高实时任务的可确定性，此外对于系统资源的合理分配以及充分利用具有重要意义．     

面向分布式实时系统的新型可信任务调度算法

目前许多面向关键领域的应用对实时系统提出了可信要求,研究可信的实时调度算法成为当前的研究热点。文章分析了当前公开文献中各种实时调度算法的缺陷,针对现有算法的不足,提出了一种适用于分布式实时系统的启发式可信调度算法,该算法以提高系统的可靠性和安全性为目标,一方面采用改进的主动副本复制技术,在多个处理机上有效分配实时周期任务,并支持对硬件失效和软件瞬时失效的处理,另一方面利用处理机对每个运行之前的任务进行安全性检查,有效防止了非法任务进入并破坏系统。仿真实验的结果表明,文中提出的算法DTSA相对于其它算法而言,在仅增加较少硬件成本的前提下,能够有效提高运行任务的可靠性和安全性。     

码域发送参考脉冲超宽带系统的多路并行传输方法

网络多媒体业务的不断发展迫使网络核心节点能够支持组播交换技术。分析了现有组播交换调度算法的优缺点,基于带缓存交叉开关交换结构探讨了组播调度的公平性问题,提出了一种能够为组播业务提供公平服务的分层混合调度算法—MSHF(Multicast Stratified and Hybrid Fair Scheduling)。MSHF采用分层和混合化的公平调度机制,通过输入调度和交叉节点调度确保组播业务的公平性问题。其算法复杂度为O(1),具有良好的可扩展性;同时依据组播业务流的权重进行分组和分级调度,减少了时延抖动,具有良好的公平性,能够适应实时业务的性能需求。理论分析和仿真结果表明:该算法具有良好的时延、吞吐量和公平性能。     

基于有限优先级的动态调度算法

实时任务调度是实时系统中的关键问题,实时动态调度是实时调度的主要方面。当实时调度应用于实际的任务系统时,仅能使用有限的优先级数量。实时调度在理论分析时,都假设系统能够识别任意多的优先级。该文提出了在优先级数量有限的条件下的动态调度算法,给出了一个任务系统动态调度所需的最小优先级的数量的算法,并对算法的复杂性进行了分析。     

基于TinyOS的非抢占双环周期协同调度策略

针对TinyOS系统 FCFS任务调度机制对吞吐量和短任务实时响应的不足,提出了基于非抢占任务的实时周期监测调度策略。把任务抽象为周期和非周期2种存在形式,在2个任务队列中实现并行协调调度,使短任务单独组队、长任务进行优化调度处理。实验结果表明,在不影响原系统性能的前提下,此方法提高了系统吞吐量,改善了短任务响应性能。     

高利用率集合Sporadic实时任务调度方法研究

该文提出一种基于最少迁移度和分割度的任务调度方法。该方法将各个实时周期任务分比例执行在不同处理器核上,并规定任务调度时的优先顺序,然后根据相应的实时调度流程对实时周期任务进行调度。并与已有的高利用率集合调度的准划分调度算法EDF-os、EDF-fm进行对比。结果表明该方法在保证系统利用率的同时,减少了任务分割和迁移的数量和不必要的任务切换开销。     

多处理器实时系统容错ICDM调度算法

目的提出一种针对多处理器实时系统中具有时间、资源和容错需求任务的调度算法来满足硬实时系统实时性及可靠性要求．使硬实时系统在发生故障的情况下，任务也能在其截止期内完成，不致产生灾难性后果．方法将非精确计算模型引入到Distance Myopic算法中，通过非精确计算模型与Distance Myopic算法的有效结合，提出ICDM算法．结果任务分为主副两个版本，每个任务都由两部分组成：强制执行部分和选择执行部分；当任务强制执行部分不能达到截止期时．通过调用MOPT算法减小前序任务选择部分的执行时间，使其满足截止期要求．ICDM算法使任务在保证结果可接受的情况下，在其截止期内完成，提高了任务的可调度性．结论通过引入非精确计算模型，使算法的可调度性增强了，也提高了硬实时系统的实时性及可靠性．     

云数据中心面向实时任务的节能调度算法

针对云计算环境下的独立实时任务的节能调度问题进行了研究,设计了一种基于松弛时间的任务调度算法,该算法由实时任务的分配、虚拟机资源的动态扩展以及虚拟机的动态整合3个部分组成,通过计算任务的松弛时间保证任务在截止期限内完成,保证任务的时效性. 同时提出了一种基于多阈值的虚拟机整合策略,以平衡系统负载并降低系统完成任务集合的能耗. 实验表明,与其他算法相比,该算法在保证了任务能够按时完成的基础上,有效降低了系统的整体能耗.     

异构集群独立任务调度问题的自适应免疫算法

异构集群独立任务调度问题是一个典型的NP难题.面向这一难题,现有的启发式调度算法,如RC、DGA等都没能兼顾实时性与负载均衡能力.人工免疫是一个新的人工智能技术,在解决组合优化难题方面,表现出了较好的性能.文章建立了一个异构集群任务调度模型,基于免疫响应的克隆选择原理和亲和力成熟机制,提出了异构集群独立任务调度问题的自适应免疫算法(AIBA).在AIBA中,通过注入抗体和动态计算负载均衡阈值的方法,将LPT算法的实时性与人工免疫系统的组合优化能力有机地结合了起来.最后,通过模拟实验对算法进行了测试和比较.实验结果显示,与DGA相比,该算法具有自适应调整能力,能动态地兼顾实时性与负载均衡度指标,有很强的实用性.     

实时系统非周期任务的可预测调度研究

提出了一种实时系统任务模型 ,分析了该模型中周期和非周期任务可调度的条件 ,并给出了一种强实时非周期任务的可预测调度算法。该算法按照 RMS算法的原则统一调度系统任务 ,保证系统周期和非周期任务满足各自的时限约束 ,实现了强实时非周期任务的可预测调度     

共享资源约束下多核实时任务分配算法

为了提高多核实时系统任务分配效率,研究分组固定优先级调度策略下的任务分配算法.通过分析核间任务阻塞对任务最坏情况响应时间产生的影响,提出由于任务间共享资源冲突而引发了任务分配故障问题;指出负载非均衡算法,如First-fit算法、Best-fit算法容易引发任务分配故障.为了避免该问题,提出基于分组与负载均衡的任务分配算法.该算法将存在访问共享资源冲突的任务分配到同一核上,以避免核间任务阻塞;当这些任务无法分配到同一核上时,将这些任务依次分配到当前负载最轻的核上以避免任务分配故障.可调度性分析实验表明,采用该算法可以避免任务分配故障,减少分配任务所需的处理器核数(比Worst-fit算法少10%～40%).