Hadoop平台下基于截止时间限制的动态调度算法的研究

为了满足有截止时间限制的MapReduce作业的需求,提出一种基于截止时间限制的动态调度算法（DCDS）。该算法实时监控作业运行状况,并对作业运行时间进行动态估算,从而确定作业优先级;对于时间紧迫的作业,可通过抢占策略来保证在用户要求的截止时间内完成。实验结果表明,与Hadoop平台现有的调度算法相比,该算法不仅能满足作业截止时间的要求,也提高了系统资源的利用率和吞吐量。     

结合价值密度和截止期的网格实时作业调度

在商业网格和云计算环境中,作业有到达时间、计算量、预算、截止期等参数,其中,预算是时间的函数。准确区分作业的重要性和紧迫性是作业调度系统的一个关键问题。综合利用这四个参数来定义作业的优先级,并提出基于价值密度和相对截止期的网格作业调度算法。分别对弱实时和强实时网格作业的调度进行仿真。仿真结果显示,所提出的调度算法的性能在两种情况下都优于所有对比算法的性能,且在强实时作业情况下优势更明显。     

Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines.     

基于组合优先级的自适应实时调度算法研究

在嵌入式实时操作系统中,由单个特征参数作为实时任务优先级的调度依据,并不能较好地描述系统中任务的关键性和紧迫性.提出一种基于组合优先级的自适应实时调度算法(SREDF),综合任务的截止期和CPU运行期设计任务的优先级,使截止期越早且CPU运行期越短的任务拥有最高优先级.处理器能有效地调度相同截止期的实时任务,并提前分析和预测任务能否完成.实验表明,该算法降低了任务调度的截止期错失率(MDP),并提高了任务调度的速度和效率.     

Dynamic priority ceilings: A concurrency control protocol for real-time systems

Real-time systems have stringent deadline requirements for their tasks. To meet the requirements, a real-time system must use scheduling algorithms that ensure a predictable response even in the face of mutually exclusive accesses to critical sections. We present a concurrency control protocol for systems using the earliest deadline first scheduling algorithm. The protocol specifies a dynamic priority ceiling for each critical section which is the earliest deadline of jobs which are currently in or will enter the critical section. Jobs trying to enter a critical section will be blocked if they do not have a priority higher than the priority ceiling of any critical section which is in use. We show that the protocol prevents both deadlock and chained blocking. The schedulability condition and implementation issues of the protocol are also discussed.     

数据流QoS自适应框架调度算法的研究与实现

在数据流QoS自适应框架中,针对如何为具有截止期和重要性两个特征参数的流数据分派优先级,在讨论了了当前调度算法优缺点的基础上,提出了称为截止期-重要性优先DIF（deadline-importance first）的实时调度算法,并利用链表给出了算法的实现.实验结果表明,在所有负载条件下DIF算法相对于EDF（earliest deadline first）算法、HVF（highest value first）算法和CDF（criticalness-deadline first）算法,在性能方面具有明显改善,特别在系统过载的情况下,能够优雅地降级.     

基于优先级表的实时调度算法及其实现

讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliest deadline value)与VED(value earliest deadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliest deadline first)算法与HVF(highest value first)算法都有很大的性能改进.     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

双头镜像磁盘的实时调度算法及性能评价

本文对双头镜像磁盘系统模型进行实时扩展,并提出了三种实时调度算法：最早截止期优先算法（ＥＤＦ）,可满足的最早截止期优先算法（Ｆ－ＥＤＦ）和忽视超时限请求算法（ＩＧＭ－ＥＤＦ）．这三种算法充分考虑了Ｉ／Ｏ请求的截止期限,使双头镜像磁盘系统能更好地满足实时需求．在进行了性能模拟后,发现实时调度算法比非实时算法能更好地满足实时Ｉ／Ｏ请求的时限要求．三种实时调度算法中,适用于硬实时应用的ＩＧＭ－ＥＤＦ的性能最好,Ｆ－ＥＤＦ算法的性能次之,它适用于软实时环境．     

队头阻塞优化的EDF可重构任务调度算法

针对最早截止时刻优先(earliest deadline first,EDF)调度算法队头阻塞任务导致资源利用率和配置端口复用率低下的问题,提出一种队头阻塞优化的EDF实时调度算法.通过定义无效阻塞任务并引入无效阻塞任务丢弃策略,提前判定和丢弃无法调度成功的任务,以利于后续任务调度;通过定义队头阻塞任务最早布局成功时刻...     

一种用于无线网络中实时业务的跨层调度算法

就同时包含了有线链路和无线链路的异构网络上的实时应用,提出了一种满足其端到端服务质量(QoS)需求的无线网络MAC(media access control)层调度算法(real-time cross-layer scheduling algorithm for real-time application,简称RTCLA).该算法采用跨层的思想,结合了自适应调制编码(adaptive modulation and coding,简称AMC)技术和选择性自动请求重传(selective repeat-automatic repeat request,简称SR-ARQ)技术,在满足应用的系统误包率(packet error rate,简称PER)要求、尽可能减少基站中等待超时分组数目的前提下,提高系统吞吐性能和频谱利用率.通过仿真来验证算法分组超时率、平均系统有效吞吐率和公平性3个方面的性能,并与改进的比例公平算法(modifiedpro portional fair,简称MPF)、最早到期优先(earliest deadline first,简称EDF)和改进的最大加权延时优先(modified largest weighted delay first,简称M-LWDF)等3种广泛使用的算法进行了比较.仿真结果还表明,综合考虑实时应用的严格时延要求和无线网络资源稀缺以及信道的时变特性,RTCLA更适合于对时延敏感的实时应用,尤其是分组超时率性能方面表现突出.此外,仿真结果还表明,RTCLA在稳定性方面的表现与其他3种算法基本相同.     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

可靠的网格作业调度机制

针对网格环境的动态性特征,提出了一种可靠的网格作业调度机制(DGJS)。按照作业完成时间期限,DGJS将作业分为：高QoS级、低QoS级和无QoS级,不同QoS级作业有不同的调度优先权;基于资源可用性预测,DGJS采用基于可靠性代价的作业调度策略,将作业尽可能调度到可靠性高的资源节点;另外,DGJS对不同QoS级作业采用不同的容错策略,在保证故障容错的同时,节省网格资源。实验表明：在动态的网格环境下,较之传统的网格作业调度算法,DGJS提高了作业成功率,减少了作业完成时间。     

Modified rate-monotonic algorithm for scheduling periodic jobs withdeferred deadlines

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, γ-1) periods or more, where γ is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than [1+n(2¹n/-1)]/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity     

一种基于两级DAG模型的MapReduce工作流异构调度算法

MapReduce编程模型被广泛应用于大数据处理平台,而一个有效的任务调度算法对模型的运行效率至关重要。将MapReduce工作流的Map和Reduce阶段分别拆解为若干个有先后序限定关系的作业,每个作业再拆解为多个任务。之后基于计算集群的可用资源和任务异构性,构建面向作业和任务的2级有向无环图(DAG)模型,同时提出基于2级优先级排序的异构调度算法2-MRHS。算法的第1阶段进行优先级排序,即对作业和任务分别进行优先权值计算,再汇总得到任务的调度队列;第2阶段进行任务分配,即基于最快完成时间将每个任务所包含的数据块子任务分配给最适合的计算结点。采用大批量随机生成的DAG模型进行实验,结果表明与其他相关算法相比,本文算法有更短的调度长度(makespan)且更加稳定。     

模糊动态抢占调度算法

针对不确定任务特征,提出应用模糊理论进行动态抢占调度,用语言模糊集来描述任务的不确定特征和不同的优先级等级,利用最大隶属度原理确定任务的优先级等级,采用优先调度高优先级等级任务的调度策略提高重要任务的调度成功率,实现具有不确定任务特征的抢占调度,与传统的EDF和LSF算法相比较,仿真表明,所提算法能够提高重要任务的调度成功率,并降低重要任务的截止期错失率;同时,任务间的平均切换次数大大小于LSF的平均切换次数,而与EDF保持相当,该方法可应用于计算机控制系统的控制任务调度,并借鉴于其它具有不确定任务特征或具有有限优先级等级的实时调度问题研究中。     

一种新的组优先级动态实时调度算法

传统动态调度算法由于对优先级个数没有限制,在实际应用中往往受制约,达不到很好的调度性能.针对此问题,考虑硬实时抢占任务调度需要,提出一种新的组优先级动态实时调度算法.研究作业执行顺序改变对系统可调度性能的影响,给出作业分组可调度性能测试.新算法将满足分组可调度测试公式的作业作为一个任务组,各任务组之间按照最小截止期优先调度,任务组内按照最短作业优先的原则执行作业.仿真结果表明,与最小截止期优先等传统调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高任务调度的成功率,缩短平均响应时间,减少任务切换次数.     

多租户集群中基于服务水平目标的调度机制

针对多租户集群中无法保证作业服务水平目标(SLO)的问题,提出了一种多租户场景下基于SLO的调度机制,其中包括优先调度算法和资源抢占算法。优先调度算法区别考虑超额使用资源的租户和未超额使用资源的租户,赋予后者的作业更高的优先级,在此前提下选择紧急度最高的作业,优先为其分配资源;资源抢占算法在资源受限的情况下,选择紧急度超过阈值的作业实施资源抢占,并根据租户的资源使用情况,在相应的运行作业范围内选择紧急度最低的作业,抢占其资源。实验结果表明,与现有保证公平的多租户调度器Capacity Scheduler相比,该调度机制可以在兼顾作业执行效率和租户间公平的前提下,显著提高作业的截止时间保证率,从而保证业务的服务水平目标。     

一种任务优先级的综合设计方法

提出了一种基于优先级表设计的调度算法.将任务的相对截止期和空闲时间这两个特征参数结合起来,综合设计任务的优先级表,使得截止期越早或空闲时间越短,任务的优先级越高,而且任务的优先级由相对截止期和空闲时间惟一确定.对于任意一个任务,可通过对设计的优先级表进行二元多点插值获得相应任务的惟一优先级.与传统的EDF和LSF算法进行仿真比较,仿真结果表明,通过优先级表设计方法来确定任务的优先级,提高了任务调度的成功率,降低了任务截止期的错失率.该方法可应用于实时系统中实时任务的动态调度中.     

一种作业弹性与截止时间感知的作业调度算法

针对采用MapReduce模型的大数据分析作业的调度问题进行深入研究，并分析现有任务调度算法的缺陷，现有算法没有考虑资源分配对于作业截止时间的影响，也未考虑不同类型作业截止时间的敏感性问题。因作业的完成时间随着分配资源的不同而改变，故称之为弹性作业，截止时间敏感性是指不同类型作业对截止时间要求的严格程度不同。针对以上问题，提出一种截止时间感知的弹性作业调度算法（DA）。该算法将作业依据截止时间敏感程度进行分类，在基于作业整体执行时间预测的基础上，通过调控不同的资源分配策略来改变作业完成时间，同时结合用户对于截止时间的需求及作业预执行的收益来提前规划作业的资源分配及调度次序使得整体收益最大化。将算法在仿真拥有210个物理节点的集群中进行实验，实验表明该算法满足了截止时间的限制并使得作业整体收益值平均提高了2.37倍。