面向系统负载的分段式实时调度算法及其实现

实时调度算法是实时系统中的关键技术,实时任务能否在规定的时限内完成主要依赖于调度算法的优劣.本文提出了一种分段式实时调度算法SS(Sectional Scheduling),此算法根据系统负载强度的不同将系统负载划分为三种情况:正常负载,超载和严重超载,每一种情况采用不同的调度算法.模拟实验表明,在所有负载条件下该算法相对于典型的EDF(Earliest Deadline First)算法,HVF(Highest Value First)算法与HVDF(Highest Value Density First)算法都有很大的性能改进.     

多处理器EPDFPfair算法的可调度性判定

针对多处理器实时调度中的最早伪时限优先(EPDF)Pfair算法,分析了EPDF算法在M个处理器平台上的可调度利用率约束,根据基于利用率的充分可调度性判定,提出了一种改进的可调度性判定方法。这种方法可以得到更多的可调度任务集,从而使得满足判定的强实时系统和使用tie-breaking规则困难的动态任务系统的调度有较小的开销。实验结果表明,改进的可调度性判定方法增加了判为可调度的任务集数量,具有较好的性能。     

基于EDF的分布式控制系统容错调度算法

现有的分布式实时系统的容错调度算法要求系统中所有任务的周期相同且等于其时限,而实际中任务的周期常常是互不相同的.根据控制系统中任务的特点,结合任务分配算法与处理器的调度算法,提出了基于基版本/副版本技术和EDF算法的容错调度算法.该算法不要求任务的周期都相同,并通过设置基版本/副版本任务时限控制它们的执行时间不重叠,给出了基版本/副版本任务时限的设置方法,并对任务集的可调度性进行了分析.当任务集可调度时,给出其最大利用率和最小处理器个数的约束条件.最后给出一个仿真实例,结果表明了算法的有效性.     

基于时间需求迭代和排队模型的开放式实时系统可调度性分析算法研究

基于RM调度策略和可延期服务器调度的开放式实时系统,以往的可调度性分析算法造成较低资源利用率.结合时间需求分析和服务台休假M/M/1/K排队模型,考虑带宽保留服务器,提出一种高资源利用率的可调度性分析算法,对系统中所有周期任务进行可调度性分析测试.给出其在临界点的响应时间;根据非周期事件到来率和接收缓冲定量分析非周期事件的平均响应时间和事件丢失率.实验表明,提出的可调度性分析方法通过估计任务的响应时间范围,能够在较高资源利用率下,验证多任务系统的可调度性.     

基于资源权重最大资源利用率的动态资源调度算法

对于在云环境下虚拟机放置问题,资源调度管理是其中一项关键技术,因而提出了一种基于最大综合利用率为标准的动态资源调度算法。首先,在云系统调度中心缓存用户的资源请求,将此请求当做一个任务,然后利用负载均衡调度算法,调度中心针对不同任务来分配适当的物理机,最后在物理机上建立虚拟等待队列,充分考虑云系统中计算资源权重比,利用基于权重最大资源利用率的算法进行虚拟机配置。仿真实验结果证明,该算法可以实现有效负载均衡,并在保证一定的QoS的情况下,能有效提高系统的综合利用率。     

异构分布式实时系统的容错优化调度算法

针对分布式实时系统,在分析了单处理调度算法的基础上,结合版本复制技术和首次适应方法,给出了一种容错调度算法。分析了算法的可调度性,给出任务的可调度性条件。在满足任务容错可调度的情况下,以提高处理器的利用率为目标,对基版本时限进行了优化,给出了基版本优化时限的求取算法。仿真结果表明,本文算法将可以得到比FTEDFFF和FTRMFF更高的处理器利用率。     

适用于偶发实时系统的过载控制策略

针对偶发实时系统中过载处理资源消耗大的问题,提出一种基于最小可推迟时间和非精确计算的过载控制策略。结合最早截止期优先调度算法,利用最大挪用时间与最小可推迟时间动态判断系统负载状态,根据系统负载状态舍弃部分非重要任务,解决系统过载问题。实验结果表明,该策略可缩短过载处理时间,提高系统资源利用率。     

异构集群系统中具有QoS 需求的实时任务容错调度

容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段.目前已有很多集群系统中实时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS需求问题.提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ(fault-tolerant QoS-based scheduling).该算法采用主版本/副版本(primary/backup,简称PB)技术,综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调度性和资源的利用率.对系统的可靠性进行了定量分析,并将其引入到容错调度算法中,提高了系统的可靠性.同时,在调度过程中尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者使任务主版本和副版本的重叠部分尽量少,提高了资源的利用率.此外,采用了副版本重叠技术,并分析了副版本的最晚开始时间及其约束条件,提高了任务的调度成功率.通过大量的模拟实验,对FTQ,NOFTQ和DYFARS算法进行了比较.实验结果表明,FTQ算法的性能优于其他方法,具有更好的调度质量.     

一种基于混合任务集的高能效调度算法

动态电源与频率调整技术能够帮助实时系统显著减少能耗,之前的研究大多聚焦于基于周期性任务的线程调度算法,却很少考虑周期性与非周期性任务混合的模型。同时,尽管基于CPU利用率的DVS算法可以从系统级上减少能耗,但不能保证实时性。本文提出一种新的算法,它结合减慢因子的DVFS调度算法与系统级的DVS技术,融合PID控制器与自适应的权衡策略为软实时系统提供更好的能耗减少方法。该算法的能耗在服务器利用率低于25%的情况下比加州大学提出的算法下降了14.2%²5.9%,周期性任务超过时限率低于3%。     

一种新的异构实时分布式系统的容错调度算法

一般来说,异构分布式实时系统中任务的周期并不完全相同且任务的时限不等于它们的周期,同时系统中还有一些无容错需求的任务.因此现有的任务调度算法一般不能满足这些要求.针对这类系统,在结合基版本/副版本技术和EDF算法的基础上,给出了一种新的容错调度算法.该算法由两部分组成：任务分配调度算法和单处理器调度算法.对于单处理器调度算法,本文采用了EDF算法;在此基础上,给出一种启发式静态任务分配算法.分析了系统的可调度性,给出了任务可调度条件和基版本/副版本时限的设置方法.仿真结果表明,这种算法是有效的.     

基于EDF算法的可行性判定及实现

实时调度算法是实时系统中的关键技术。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。在介绍实时系统中常用的各种实时调度算法,包括固定优先级调度算法和动态优先级调度算法基础上,详细分析了动态优先级调度算法EDF算法的运算过程和使用条件。提出了该算法在实际应用中存在的问题。针对该硬实时调度算法,提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。为实际应用中实现该实时调度算法确定了依据。     

Combined task and message scheduling in distributed real-timesystems

The paper presents an algorithm for offline scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real time systems. Tasks are assumed to communicate via message passing based on a time bounded communication paradigm, such as the real time channel (D.D. Kandlur et al., 1994). The algorithm uses a branch-and-bound (B & B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain     

A measurement-based model to predict the performance impact ofsystem modifications: a case study

The paper presents a performance case study of parallel jobs executing in real multi user workloads. The study is based on a measurement based model capable of predicting the completion time distribution of the jobs executing under real workloads. The model constructed is also capable of predicting the effects of system design changes on application performance. The model is a finite state, discrete time Markov model with rewards and costs associated with each state. The Markov states are defined from real measurements and represent system/workload states in which the machine has operated. The paper places special emphasis on choosing the correct number of states to represent the workload measured. Specifically, the performance of computationally bound, parallel applications executing in real workloads on an Alliant FX/80 is evaluated. The constructed model is used to evaluate scheduling policies, the performance effects of multiprogramming overhead, and the scalability of the Alliant FX/8O in real workloads. The model identifies a number of available scheduling policies which would improve the response time of parallel jobs. In addition, the model predicts that doubling the number of processors in the current configuration would only improve response time for a typical parallel application by 25%. The model recommends a different processor configuration to more fully utilize extra processors. The paper also presents empirical results which validate the model created     

多回路网络化控制系统中采样周期的优化算法研究

研究了具有多个控制回路的网络化控制系统中采样周期的优化确定算法．采用将基本周期划分为时间段的方法，取各控制回路的采样周期为基本周期的2的阶次方倍且不大于相应回路的最大允许网络时延．通过对系统的可调度性进行分析，能够优化确定出各控制回路的采样周期，并且保证实时性周期数据和实时性非周期数据的实时传输以及非实时数据的最小利用率．基于CAN总线控制网络的仿真结果表明了本算法的有效性．     

An Energy-Aware Heuristic Scheduling for Data-Intensive Workflows in Virtualized Datacenters

With the development of cloud computing, more and more data-intensive workflows have been deployed on virtualized datacenters. As a result, the energy spent on massive data accessing grows rapidly. In this paper, an energy-aware scheduling algorithm is proposed, which introduces a novel heuristic called Minimal Data-Accessing Energy Path for scheduling data-intensive workflows aiming to reduce the energy consumption of intensive data accessing. Extensive experiments based on both synthetical and real workloads are conducted to investigate the effectiveness and performance of the proposed scheduling approach. The experimental results show that the proposed heuristic scheduling can significantly reduce the energy consumption of storing/retrieving intermediate data generated during the execution of data-intensive workflow. In addition, it exhibits better robustness than existing algorithms when cloud systems are in presence of I/O- intensive workloads.     

磁带库系统的随机I/O调度算法

由于磁带库随机存取的性能很差,需要研究有效的随机I/O调度策略和算法以改善其在线存取的效率.对已有调度算法进行了分类、提炼和总结,利用仿真实验对静态调度、动态调度和基于复制的调度算法进行了深入研究,讨论了影响各种算法有效性的因素.针对已有算法在较重的负载条件下使系统性能急剧恶化的问题,还提出并研究了一种基于效益-代价均衡的调度算法.该算法引入效益-代价加权的概念,通过调节不同负载下的效益-代价加权比,极大地改善了已有算法在重负载下的有效性.该项研究为设计海量存储系统中的自适应调度算法提供了重要依据.     

On-line hierarchical job scheduling on grids with admissible allocation

In this paper, we address non-preemptive online scheduling of parallel jobs on a Grid. Our Grid consists of a large number of identical processors that are divided into several machines. We consider a Grid scheduling model with two stages. At the first stage, jobs are allocated to a suitable machine, while at the second stage, local scheduling is independently applied to each machine. We discuss strategies based on various combinations of allocation strategies and local scheduling algorithms. Finally, we propose and analyze a scheme named adaptive admissible allocation. This includes a competitive analysis for different parameters and constraints. We show that the algorithm is beneficial under certain conditions and allows for an efficient implementation in real systems. Furthermore, a dynamic and adaptive approach is presented which can cope with different workloads and Grid properties.     

异构集群系统的可分负载多轮调度算法

针对更实际的异构集群计算环境,充分考虑处理机具有不同的计算速度、通信能力和存储容量的特性,通过允许计算和通信操作重叠执行,采取多次并行分配计算任务的方法,设计一种可分负载多轮调度算法。实验结果表明,该算法不但能获得与均匀多轮调度(UMR)算法相当的渐近最优调度时间长度,并且能够处理更大规模的应用负载,实用性更强。     

FAIRIO: A Throughput-oriented Algorithm for Differentiated I/O Performance

Providing differentiated service in a consolidated storage environment is a challenging task. To address this problem, we introduce FAIRIO, a cycle-based I/O scheduling algorithm that provides differentiated service to workloads concurrently accessing a consolidated RAID storage system. FAIRIO enforces proportional sharing of I/O service through fair scheduling of disk time. During each cycle of the algorithm, I/O requests are scheduled according to workload weights and disk-time utilization history. Experiments, which were driven by the I/O request streams of real and synthetic I/O benchmarks and run on a modified version of DiskSim, provide evidence of FAIRIO’s effectiveness and demonstrate that fair scheduling of disk time is key to achieving differentiated service in a RAID storage system. In particular, the experimental results show that, for a broad range of workload request types, sizes, and access characteristics, the algorithm provides differentiated storage throughput that is within 10% of being perfectly proportional to workload weights; and, it achieves this with little or no degradation of aggregate throughput. The core design concepts of FAIRIO, including service-time allocation and history-driven compensation, potentially can be used to design I/O scheduling algorithms that provide workloads with differentiated service in storage systems comprised of RAIDs, multiple RAIDs, SANs, and hypervisors for Clouds.     

实时系统中的非定期任务调度算法综述

非定期任务调度是实时系统中的一个重要研究内容，综述了实时系统中非定期任务调度算法的研究与进展，按照这些算法的特征分为基于服务器的算法与基于空闲时间的算法两大类别，并着重对每个类别中的不同算法的特征与性能进行了分析，通过对这些算法的比较与分析，希望为实时系统的研究与开发者提供有意义的参考，最后还给出了非定期任务调度进一步研究的思路与建议。