云环境下周期和非周期混合实时任务双容错调度算法

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

MVB周期信息的实时调度

多功能车辆总线MVB网络对周期信息的通信提出了很高的实时要求,其通信的实时调度主要由MVB总线管理设备利用实时调度表来完成。在分析一般现场总线周期信息实时调度的基础上,结合MVB周期信息的通信特点,提出了采用同步RM调度算法来建立MVB实时调度表的原理与方法;并进一步提出了采用基于任务响应时间的方法对该调度算法进行可调度性分析,给出了一种有效算法,用以实现对调度表的有效性判断;最后通过MVB周期信息实例阐述了所提出的实时调度算法及其可调度性分析方法的具体应用,为实际MVB网络的应用研究提供了理论指导。     

Linux系统中多核实时调度平台的设计

为使各种实时调度算法能够在Linux环境中得到运行和验证,设计一种Linux系统中的公共多核调度平台。该平台由调度模块和跟踪测试模块组成,调度模块实现系统调用、调度处理以及同步功能,跟踪测试模块实现日志和跟踪功能。测试结果表明,该平台可正确显示调度算法的运行结果。     

一种针对依赖性周期任务的实时多核调度算法

针对软实时系统中的一类同时具有依赖性与周期性的任务,提出一种基于单行树矩阵(MST)的动态因子均衡调度算法SMD(schedule on matrix of the single tree and dynamic load factor)。该算法通过对MST矩阵的特性进行分析,将任务划分为若干并行集,再综合考虑已执行时间、任务间的依赖关系及任务最早截止时间几个要素,以动态因子的形式对任务进行实时调度。最后,还以证明的形式给出了可充分调动的任务集的充分条件,并以此为基础随机生成了测试任务集,进行了对比实验。实验表明,与文献中现有经典算法相比,新算法使处理器利用率提升近15%,任务丢失率降低2%。     

一类特殊的非抢占式周期任务的调度方法

现实世界中针对许多任务的资源调度分配和使用具有时效性,对该类任务的调度问题目前的研究还较少。针对此类调度问题,分析其特点,明确其与已有调度模型研究问题的区别,提出新的非抢占式周期任务调度模型,并证明了该类问题为NP完全问题。在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种求解近似解的快速求解算法。相关实验表明,提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。     

VxWorks下周期任务调度和任务周期选择

本文介绍了VxWorks操作系统下任务调度的策略,分析了实际设计应用中,周期任务调度的需求。介绍了一种在Vx鄄Works操作系统下优化周期任务周期的方法。     

周期多帧任务的固定优先级调度算法的调度分析

实时操作系统的核心问题－－实时任务的调度是实时系统研究的重点之一。主要讨论了周期多帧任务的固定优先级调度算法的调度情况,证明了对于周期多帧任务DM算法不是最优的,同时也证明了对于累积单调周期多帧任务的DM算法是最优的。     

面向多处理器的实时周期任务容错调度算法研究

主副版本策略是多处理器系统实时任务调度中处理容错问题的一种重要方式.根据分布式控制系统的特点,本文提出一种改进的FTRMBF算法-PR-FTRMBF,以提高系统周期任务的可调度性.在FTRMBF等已有的调度算法中,当没有处理器分配给当前副版本时,将为副版本分配新的处理器;本文提出的改进算法则以回溯的方式重新分配主版本.在保证系统实时性能和容错能力的前提下,节省了处理器数目.仿真实验表明,与FTRMBF算法相比,改进算法显著提高了系统任务的可调度性.     

反馈控制实时调度中采样周期的研究

以CPU资源调度为典型应用背景，研究并分析了采样周期对反馈控制实时调度和一般数字控制系统性能影响的差异，通过仿真实验得出采样周期的选择对反馈控制实时调度性能影响规律，提出了采样周期的选择方法。对于平均执行时间难以预测的任务集，提出一种可变采样周期的有效解决方案。     

容错多处理机中一种高效的实时调度算法

针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.     

实时分布系统中Out-Tree任务的调度与检查点策略

针对实时分布系统中的Out-Tree任务，提出了一种启发式的调度算（HSA-OT），并开发了一种多处理机上的最优检查点策略。该调度算法能够保证任务的调度长度最小，所需处理器数目尽量少，没有处理机间通信开销。该检查点策略没有检查点全局一致性开销，可保证各处理机的失效率最低。     

Non-Preemptive Real-Time Scheduling of Multimedia Tasks

Motivated by the special characteristics of multimedia tasks, we consider non-preemptive scheduling of tasks where there exists no (or very limited) information concerning the tasks before they are released. We present impossibility results and analyze algorithms for non-preemptive scheduling in single processor and multiprocessor systems. To evaluate our algorithm we assume that system obtains a value that is proportional to the processing time of the task whenever a task is completed by its deadline. Competitive analysis is used, where the goal is to keep the total value obtained by an on-line algorithm bounded by a function of the total value obtained by an off-line algorithm. In particular, one set of our results considers the competitive ratio of scheduling algorithm when the length of the tasks is not greater than C_max (and not smaller than C_min ). We show that the performance of a scheduling algorithm is improved dramatically when the release time of the tasks is O(C_max) prior to their deadline; achieving a competitive ratio that is close to one.     

End-to-End Utilization Control for Aperiodic Tasks in Distributed Real-Time Systems

An increasing number of DRTS （Distributed model. The key challenges of such DRTS are guaranteeing Real-Time Systems） are employing an end-to-end aperiodic task utilization on multiple processors to achieve overload protection, and meeting the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end utilization control architecture and an IC-EAT （Integration Control for End-to-End Aperiodic Tasks） algorithm, which features a distributed feedback loop that dynamically enforces the desired utilization bound on multiple processors. IC-EAT integrates admission control with feedback control, which is able to dynamically determine the QoS （Quality of Service） of incoming tasks and guarantee the end-to-end deadlines of admitted tasks. Then an LQOCM （Linear Quadratic Optimal Control Model） is presented. Finally, experiments demonstrate that, for the end-to-end DRTS whose control matrix G falls into the stable region, the IC-EAT is convergent and stable. Moreover,it is capable of providing better QoS guarantees for end-to-end aperiodic tasks and improving the system throughput.     

云计算中资源延迟感知的实时任务调度方法

绿色云计算已经成为一个研究焦点,动态整合虚拟机和关闭空闲主机是极具潜力的途径可降低云计算数据中心的能耗.当云平台的负载迅速增加时,系统需要启动更多的主机和创建更多的虚拟机来扩展可用资源.然而,启动主机和创建虚拟机需要一定的时间开销,使得紧急任务难以及时开始,从而延误了截止期.为了解决以上问题,首先提出具有机器启动时间感知的虚拟机扩展策略,以缓解机器启动时间冲击实时任务的时效性要求.基于该策略,设计算法STARS来调度实时任务和资源,以在保障任务时效性与节能2方面进行权横.最后,使用Google的负载数据进行模拟实验,比较算法STARS与其他2个算法的性能.实验结果表明,在保障任务时效性、节能和资源利用率方面,算法STARS优于对比算法.     

控制系统中强实时任务的调度

文章通过对控制系统中强实时任务进行分析,指出系统存在的各类强实时任务。针对控制系统中任务的特点,提出了一种实时任务调度方法。对这种调度算法进行了可调度性分析,指出实时控制系统中任务可调度的条件。     

Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints.Unfortunately,most conventional scheduling algorithms only take one or two dimensions of them into account.Motivated by this fact,this paper investigates the problem of providing multiple performance guarantees including timeliness,QoS,throughput,QoS fairness and load balancing for a set of independent tasks by dynamic ...     

PLUFS: 一种开销敏感的周期任务在线多处理器节能实时调度算法

现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果,但仍不能保证最优可调度性.针对嵌入式实时系统中不可忽视的状态切换开销,提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合,在每个TL面的初始时刻、任务结束执行时刻实现节能调度,在不违反周期任务集最优可调度性的前提下,达到实时约束与能耗节余的合理折中.经过理论证明和模拟实验,结果表明：PLUFS算法不仅保证了周期任务集的最优可调度性,而且节能效果整体优于现有算法,能耗节余比现有算法提高约10%～20%.     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

异构分布式控制系统中实时任务的调度算法

分布式控制系统是一种应用极为广泛的异构分布式实时系统，系统中同时存在有多种实时任务，如何将这些任务分配到各个处理器上并保证它们的时限是系统关键技术之一．在结合启发式任务分配算法和单处理器任务调度算法的基础上，提出了一种分布式控制系统的调度算法．该算法考虑了各个处理器的负载均衡，同时又能满足所有任务的时限．仿真结果表明了算法的有效性．