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

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

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

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

异构机群系统中并行任务的分层调度算法

研究在异构机群系统中,使并行任务执行完成时间最短的调度算法．有许多启发式的任务调度算法在同构的分布式计算系统中是很有效的,但在异构机群系统中,由于每个任务在每个处理机上的执行时间不同而失去意义．本文以任务集内任务的拓扑次序为基础,将任务集分层,提出了分层调度算法．它是一个简单而且实用的算法,在某些情况下能达到局部最优,时间复杂度为Ｏ（ｎｍ）,其中ｎ为任务数,ｍ为处理机数．     

可负载均衡的实时虚拟机VCPU调度算法

针对多核环境下的现有实时虚拟机VCPU(virtual CPU)调度算法不能在保证任务可调度的基础上高效地使用CPU资源的问题,提出一种改进的实时虚拟机VCPU调度算法LBP-EDF(基于独立队列的可负载均衡的最早截止时间优先调度算法).该算法采用了独立队列的方式,以避免共享队列带来的竞争开销.同时算法能够识别紧急任务,并通过负载均衡的机制及时地将紧急任务迁移到负载较轻的CPU上执行,在保证任务可调度的基础上,同时达到充分使用CPU资源的目的.实验结果表明:在保证任务可调度的基础上,LBPEDF较其他算法有更高的CPU利用率.     

异构系统中带可用性约束的性能优化调度算法

针对可用性约束以及任务响应时间不同给异构系统中实时任务调度分配带来的处理机节点难选取的问题,提出了一种带可用性约束的性能优化调度算法(PO-SSAC)。该算法将异构系统内处理机节点、实时任务以及带可用性约束的实时任务调度过程进行数学建模,通过考虑可用性成本与任务平均响应时间的折中,引入系统综合开销的概念,根据实时任务的可用性需求为其分配系统综合开销最少的处理机节点调度执行,达到系统调度资源合理利用的目的。实验结果表明,在实时任务调度可用性方面,与SSAC算法相比,PO-SSAC算法提升了3.4%,与MinMin算法相比,提升了76.9%,与Sufferage算法相比,提升了76.5%;与Sufferage算法相比,PO-SSAC算法的系统综合开销减少了约30%,优化了异构系统的实时任务调度性能。     

多DAG任务调度算法

多DAG任务调度问题是当前研究的热点,为了提高任务调度的效率以及资源利用率,各个DAG的调度顺序以及每个DAG内部任务之间的调度顺序成为研究任务调度问题的关键。提出了一种基于分布式异构计算环境的多DAG任务调度模型和多DAG任务调度算法MDTS(multi-dags task scheduling algorithm)算法。算法首先对多个DAG任务进行合并,通过增加一个入口任务节点和出口任务节点的方法将多个DAG合并为一个DAG;然后根据每个任务节点的计算代价的方差以及平均通信开销对任务进行排序;最后基于HEFT算法降序对各个任务进行处理机调度。实验证明,MDTS算法在任务调度跨度、任务调度平均等待时间以及平均Slack方面均优于Sequential、Interleave算法。     

考虑释放时间和调度顺序的可分任务调度模型

针对处理机具有任意释放时间的异构并行与分布式系统,通过寻找最优的处理机调度顺序和任务分配方案,使得任务的完成时间达到最短.首先,在给定处理机调度顺序的情况下,分析了处理机释放时间对任务完成时间的影响,得到了任务分配方案关于处理机调度顺序和时序约束条件的解析解;然后,以调度顺序和时序约束条件为变量,以任务的最短完成时间为目标,建立了一种新的可分任务调度模型;最后,设计了高效的全局优化遗传算法求解该模型.仿真结果表明所提算法比已有算法完成任务的时间更短.     

基于重复异构最早完成时间的云计算任务调度算法

针对云计算任务调度算法时间成本消耗大的问题,提出了一种新的算法,即重复异构最早完成时间(Duplication based Heterogeneous Earliest Finish Time,DHEFT)任务调度方法.该方法结合异构最早完成时间算法和任务重复算法,可以大大减少任务最早开始时间和最早完成时间.由于任务优先级对于相关任务调度算法的重要性,该算法中提出了乐观成本表的方法来计算任务优先级,根据优先级调度任务,并复制父任务以降低通信成本并获得最佳调度解决方案.实验结果表明,该文提出的DHEFT在调度长度比和完成时间性能方面优于其他算法,说明该文方法的可行性与有效性.     

一种可调节动态任务调度算法

提出了适于异构环境独立任务调度的可调节动态调度算法(AS算法)。该算法以任务与处理机的执行时间和完成时间作为参数共同构造任务调度顺序的衡量值,其中二者所占的比重能进行适当调整。AS算法克服了Min-min算法单纯追求局部最优的局限性,更适合异构环境。实验结果表明AS算法可以有效地降低调度跨度,其性能比Min-min算法有所提高。     

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

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

有通信冲突的异构系统上的任务调度

在新的系统模型上，提出了一个任务调度算法．该系统模型考虑了通信冲突，即在任何时刻，一个处理器只能接收一条消息，发送一条消息．新的算法包括异构系统中任务优先级的高效排序和基于任务复制的处理器分配两部分．随机产生的任务图和一个具体应用的任务图进行调度试验的结果表明，该算法比已有调度算法的性能有了显著的提高．     

基于多Agent的分布式多目标任务调度机制研究

针对分布式计算中任务调度的复杂性、动态性和实时性等特点,构建了一个基于多Agent的分布式多目标任务调度模型．此模型中,设计了一种分布武调度机制,使每个节点都具有独立的调度决策能力,增强了系统的可扩展性．同时为了解决分布式调度所产生的节点间任务通信问题,引入任务与节点相关性等概念,有效地降低了节点间的通信代价．模型对多个评价指标进行了综合衡量,如任务调度开销、任务最早执行时间、负载均衡及节点问的通信量等,并根据任务和系统运行的状态特征,实现多目标任务调度,提高了系统的整体性能．     

一种基于贪心策略的启发式云计算任务调度算法

提出了一种基于贪心策略的启发式任务调度算法,用于优化云计算环境下任务调度中执行时间。首先,给出了云计算环境下任务调度问题的形式化描述及其最早完成时间的启发式优先分配原则;接着,基于最早完成时间的优先分配原则,采用贪心策略难易交错地分配任务求得任务调度的初始解;进而,引入了任务对交换的收益值概念,采用贪心策略选择收益值大的任务对交换优化任务调度初始解的执行时间;最后,在Cloud Sim云计算仿真实验平台下进行了顺序调度算法、Min-Min算法、Max-Min算法和本文算法的对比实验,实验数据对比充分验证了本文算法既能减少任务执行时间,又能使资源负载相对平衡。     

嵌入式系统动态策略任务调度算法

针对嵌入式实时系统任务调度问题,讨论综合截止期和关键度两种特征参数的任务调度策略。引入动态策略的概念,采用任务分组优先级分段的方式,通过判断函数的判断动态选择调度策略,利用可达截止期优先降低任务错失率,关键保证重要任务的调度成功率,提出一种动态截止期-关键度调度算法。理论分析和仿真实验表明,在非过载的情况下该算法可以达到与可达截止期优先相当的调度性能;在过载的情况下,相比截止期优先和固定优先级算法具有更好的调度性能,能够有效地保证关键实时任务的成功调度。     

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.     

基于模糊最早价值时间优先的动态调度算法

实时控制系统调度中,最早截止时间优先（EDF）算法在超载时会造成系统控制性能急剧下降且严重影响了系统的稳定性,限制了其应用。为此,本文提出了模糊最早价值时间优先（FEVF）的调度方法。该算法基于模糊思想,构造了任务截止期的模糊隶属度函数,并根据任务的在线执行情况对任务进行价值度评价,从而动态地获得任务的价值时间,价值时间越早,任务的优先级越高。仿真结果表明,FEVF算法调度下系统的稳定性能在一定重载下保持较好的状态,可实现大范围负载内的优雅降级,使系统不致突然出现失效或崩溃。     

WebitOS中动态优先级调度机制及EDF算法的实现

在实时系统中,相对于静态优先级调度机制而言,动态优先级调度机制因其可以为每个任务的各个作业设置不同的绝对时限而更好地反映了实时系统对于所调度的各个任务的时限要求.基于最早时限优先(earliest-deadline-first EDF)算法的高可调度利用率,在WebitOS实时操作系统中设计并实现了动态优先级调度机制,并且提出了一种早期丢弃规则.实验结果表明,该规则提高了EDF算法在超载情况下的整体调度性能.     

An optimizing algorithm of static task scheduling problem based on hybrid genetic algorithm

To reduce resources consumption of parallel computation system,a static task scheduling optimization method based on hybrid genetic algorithm is proposed and validated,which can shorten the scheduling length of parallel tasks with precedence constraints.Firstly,the global optimal model and constraints are created to demonstrate the static task scheduling problem in heterogeneous distributed computing systems(HeDCSs).Secondly,the genetic population is coded with matrix and used to search the total available time span of the processors,and then the simulated annealing algorithm is introduced to improve the convergence speed and overcome the problem of easily falling into local minimum point,which exists in the traditional genetic algorithm.Finally,compared to other existed scheduling algorithms such as dynamic level scheduling(DLS),heterogeneous earliest finish time(HEFT),and longest dynamic critical path(LDCP),the proposed approach does not merely decrease tasks schedule length,but also achieves the maximal resource utilization of parallel computation system by extensive experiments.     

支持缓存划分的全局EDF实时系统调度策略

由于多核处理器争用共享缓存导致的不确定性为实时系统带来极大的挑战.为解决这个问题,现代处理器引入了缓存划分技术,通过隔离处理器核对缓存的访问从而提高了时间可预测性.但是,这种隔离技术可能导致实时任务因缓存分区的数量不足而被阻塞,而传统的实时调度算法与分析方法无法有效应对这种情况.因此,提出了支持缓存划分的可抢占全局最早截止期优先(EDF)实时调度算法gEDFca,并结合最新的缓存敏感调度理论针对这种调度算法进行了可调度性分析,提出了一种基于线性规划的可调度性判定条件.还提出了一种具有线性时间复杂度的优化算法,进一步提高了分析方法的性能.随机生成任务的仿真实验表明,提出的可调度性判定方法具有较高的效率.同时,优化算法提高了算法可调度性.