EDI中心的实时任务调度算法研究

本文首先综述单处理器系统中基于截止时间优先任务调度的几种算法以及涉及问题的基本解决方法，然后提出在满足每个任务截止时间的前提下，基于最早开始执行时间优先动态调度算法。     

基于RMS任务调度算法的弱实时上下位监控系统

上下位监控系统在工业及其他领域中得到越来越广泛的应用,实时的实现及其可靠性是系统的关键。文章讨论了基于RMS的实时任务调度算法及其在弱实时上下位监控系统中的应用,并给出了具体的应用实例。     

多核系统的实时任务调度算法研究

为更好地解决多核系统实时任务调度问题,针对基本蚁群算法求解最短路径过程中容易陷入局部最优的情况,对基本蚁群算法进行了改进。改进算法根据系统的实际情况对概率选择公式做出调整,同时根据相应策略对信息素进行调整,有效地缩小了信息素之间的差距,有利于跳出局部最优状态。实验结果表明,该算法与基本蚁群算法相比在收敛速度和计算最优解方面都有了提高。     

一个市场驱动的QoS网格工作流任务调度算法

网格调度关系到整个网格任务运行的效率,因此在网格的研究过程中,已经提出了很多调度算法.但这些算法大部分是对元任务(Meta-task)进行调度,很少是针对关联任务的.在考虑用户QoS(Quality of Service)需求的情况下,提出了一个市场驱动的QoS网格工作流任务调度算法.仿真实验结果表明了该算法的合理性和有效性.     

车辆移动云可靠性任务调度

车辆移动性使得移动车辆云中的任务调度可靠性问题变得尤为复杂。针对这一问题,提出一种基于混合整数线性规化最优化方法的云任务调度算法。借助于MapReduce构建车辆云任务的调度模型,并设计一种复杂度更低的启发式调度方法,在有效降低任务执行延时的同时,确保了任务调度的可靠性。通过在网络仿真器NS3中运行城市道路环境下的MapReduce应用,对算法的调度结果进行性能评估。结果表明,与同类的车辆云中的调度方法相比,该算法在作业平均执行时间、作业调度成功率、系统吞吐量及任务执行开销等性能指标上均优于对比算法。     

一种动态可重构系统的实时任务调度算法

硬件任务的软实时调度是影响动态可重构系统性能的关键因素之一。本文提出了一种基于顶点链表的硬件任务间最小空间调度算法MSSA,该算法将硬件任务按照长、宽及调度时间构成一个三维资源模型,以到达任务与已放置任务在三维空间的邻接度来构建代价函数,获取具有最大代价函数值的放置位置和启动时间,可使任务安排得更紧凑,减小对系统资源的浪费,提高并行度。仿真实验表明,与MSG-4V和Stuffing算法相比,本文算法具有更高的芯片利用率和任务接受率。     

RMS任务调度算法在弱实时上下位监控系统中的应用

上下位监控系统在工业及其他领域中得到越来越广泛的应用，实时的实现及其可靠性是系统的关键。文章讨论了基于RMS的实时任务调度算法及其在弱实时上下位监控系统中的应用，并给出了具体的应用实例。     

电网自动化中的高可靠分布式任务调度算法

电网自动化系统实现了电网变电站的现代化管理，是确保电力系统安全、稳定、可靠运行的重要手段，本文提出了针对电网自动化调度监控中心的分布式结构模型，并在此基础上设计和实现了两种高可靠的分布式任务调度算法－－ADS算法和LFS算法，对系统性能的测试结果表明，采用本文的分布式结构和算法可保证电网自动化系统的实时性和高可靠性。     

一种基于多处理机的容错实时任务调度算法

容错是实时系统的重要要求,在实时系统中,若一个实时任务没在规定的时间期限内完成,则认为系统出现错误,针对多处理机实时系统提出了一种容错调度算法．算法采用了任务的主从备份技术和Ｆｉｒｓｔ－ｆｉｔ启发式方法,通过为可能因处理机故障而执行失败的实时任务预留重新运行的时间来实现容错功能;并通过对预留时间段的重叠利用和无错时预留时间的回收分配,来提高处理机的利用率和系统对任务的接收率．模拟结果表明算法是有效     

ORB中实时任务调度的实现

首先讨论了现行的CORBA中实时性应用的缺陷。为了解决这些缺陷,必须对CORBA进行改进,主要讨论对ORB中的任务调度进行改进。在比较了几种静态调度策略（基于速率的策略RMT）和动态调度策略（最早期限策略EDF,最少松弛度策略MLF）的优缺点的基础上,提出了一种动、静态相结合的策略;最重要的优先策略（MIF）。最后用IDL语言定义了ORB中任务调度服务对象与应用的接口,并给出了执行过程。     

An efficient weighted bi-objective scheduling algorithm for heterogeneous systems

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability.     

Reliability-aware scheduling strategy for heterogeneous distributed computing systems

Heterogeneous computing systems are promising computing platforms, since single parallel architecture based systems may not be sufficient to exploit the available parallelism with the running applications. In some cases, heterogeneous distributed computing (HDC) systems can achieve higher performance with lower cost than single-machine supersystems. However, in HDC systems, processors and networks are not failure free and any kind of failure may be critical to the running applications. One way of dealing with such failures is to employ a reliable scheduling algorithm. Unfortunately, most existing scheduling algorithms for precedence constrained tasks in HDC systems do not adequately consider reliability requirements of inter-dependent tasks. In this paper, we design a reliability-driven scheduling architecture that can effectively measure system reliability, based on an optimal reliability communication path search algorithm, and then we introduce reliability priority rank (RRank) to estimate the task’s priority by considering reliability overheads. Furthermore, based on directed acyclic graph (DAG) we propose a reliability-aware scheduling algorithm for precedence constrained tasks, which can achieve high quality of reliability for applications. The comparison studies, based on both randomly generated graphs and the graphs of some real applications, show that our scheduling algorithm outperforms the existing scheduling algorithms in terms of makespan, scheduling length ratio, and reliability. At the same time, the improvement gained by our algorithm increases as the data communication among tasks increases.     

异构机群下最小化非实时任务平均响应时间的调度策略

机群作为高性能计算机平台有着广阔的应用前景。由于很多情况下单一机群已经无法满足应用需求,因此分离的机群通常相互连接来建立一个多机群计算结构。分布式系统中根据系统处理任务性质的不同可分为实时任务和非实时任务两类。它们继而又可以分为有数据关联任务和无数据关联任务。本文关注的是异构机群下非实时任务流的调度,采用最小化任务平均响应时间作为目标函数。已有的策略要么不适用于异构多机群,要么没有考虑到任务传递的通信耗费,或者两者都欠缺。本文提出的任务调度策略解决了这两个问题,并且通过试验证明了MMRT虽然充分考虑了通信耗费,却没有明显增大系统的额外开销。     

一种可行的DMS可调度性分析

固定优先级任务的可调度性判定是实时系统调度理论研究的核心问题之一。提出了一种可行的DMS(Deadline Monotonic Scheduling,简称DMS)可调度性判定方法—确切性判定方法(precised schedulability test algorithm简称PSTA),利用DMS调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的。首先给出了DMS调度模型,介绍了可调度性判定的基本思想,然后通过实验提出并验证了PSTA相关的结论。     

Predictability of Fixed-Job Priority schedulers on heterogeneous multiprocessor real-time systems

The multiprocessor Fixed-Job Priority (FJP) scheduling of real-time systems is studied. An important property for the schedulability analysis, the predictability (regardless to the execution times), is studied for heterogeneous multiprocessor platforms. Our main contribution is to show that any FJP schedulers are predictable on unrelated platforms. A convenient consequence is the fact that any FJP schedulers are predictable on uniform multiprocessors.     

T–L plane-based real-time scheduling for homogeneous multiprocessors

We consider optimal real-time scheduling of periodic tasks on multiprocessors—i.e., satisfying all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. We introduce a novel abstraction for reasoning about task execution behavior on multiprocessors, called T–L plane and present T–L plane-based real-time scheduling algorithms. We show that scheduling for multiprocessors can be viewed as scheduling on repeatedly occurring T–L planes, and feasibly scheduling on a single T–L plane results in an optimal schedule. Within a single T–L plane, we analytically show a sufficient condition to provide a feasible schedule. Based on these, we provide two examples of T–L plane-based real-time scheduling algorithms, including non-work-conserving and work-conserving approaches. Further, we establish that the algorithms have bounded overhead. Our simulation results validate our analysis of the algorithm overhead. In addition, we experimentally show that our approaches have a reduced number of task migrations among processors when compared with a previous algorithm.