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

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

一种Hadoop中基于作业类别和截止时间的调度算法

Hadoop是一种开源可靠的分布式计算框架,而MapReduce是处理超大规模数据集的编程模型.鉴于Ha-doop内置的调度器不能很好地处理类别不同且有截止时间的作业的调度,提出了一种基于作业类别和截止时间的作业调度算法.作业分为CPU密集型和I/O密集型,并根据截止时间设置优先级来实现作业的调度.实验结果表明,该算法在充分利用集群的CPU和磁盘I/O的同时,能满足作业的截止期需求,当同一时间段内截止时间相近时算法达到最优,当某一队列中作业截止时间均比另一种队列短时,算法效率最低.     

面向信息服务的网格资源管理器的设计

设计一个面向信息服务的网格资源管理器的架构，该架构分为全局和局部管理器。介绍一个新的作业调度算法，该算法的特点是根据历史作业执行时间来预测当前作业的执行时间，在调度时考虑作业执行时间和截止时间2个要素。试验证明该算法比目前常用的Max-Min和Min-Min算法具有更好的性能。     

一种快速的网格任务调度算法的设计

网格任务的执行环境具有动态性、分布性等特征,为了能顺利完成任务并使其具有较好的执行效率,需要一种有效的策略来进行任务的调度.结合信息处理的特点,提出一种快速有效的网格任务调度算法.该算法采用历史信息预测任务的执行时间,根据任务的截止时间要求对子任务进行合理分组.最后,给出了该算法在网格模拟器上的测试结果,并与一些算法进行了比较.结果表明,本算法对大作业以及截止期限紧急的作业具有较好的调度效果.     

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

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

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。     

基于排队网络的多优先级MapReduce作业调度算法

MapReduce是一个能够对大规模数据进行分布式处理的框架,目前被各个领域广泛应用。在提供MapReduce服务的集群中,如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战。针对这一问题,提出了一个基于排队网络的多优先级作业调度算法（MPSA）。首先分析和归纳了基于MapReduce模型的算法,提出了三种常见模式,采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求;随后使用AR(1)模型进行预测,使算法可以动态地适应不同的用户访问量;利用二分查找算法,分步计算出不同优先级在map阶段和reduce阶段分配的槽位数;最后实现了在MapReduce模型中应用的实时调度算法。实验结果表明,与传统的FIFO和公平调度算法相比,本文提出的算法在用户到达率和任务规模变化的情况下,可以更加有效地满足不同优先级用户的截止时间限定。     

移动环境中请求多数据项的广播调度算法

提出移动环境中请求多数据项的广播调度算法——基于权重的调度算法(BWS)和权重比截止时间算法(WID)。BWS算法根据数据项对客户的满足情况确定权重,并以数据项的总权重作为调度的依据,同时考虑数据项的使用频率和数据项对于客户的满足情况。WID算法以总权重与截止时间的比值作为调度依据,同时考虑广播效率和紧急性的要求。在数据广播调度方面这2种算法比传统的算法具有更好的性能。     

基于截止时间满意度的网格工作流调度算法

动态网格环境中用户截止时间保障是工作流调度问题的一个挑战.利用随机服务模型来描述网格资源的动态处理能力及其动态负载压力,提出了截止时间满意度的概念和工作流截止时间满意度的计算方法.将以DAG图形式表示的任务执行关系转换为以数值表示的任务执行优先级,并根据最大截止时间满意度优先的思想,确定执行工作流子任务的候选资源;将工作流全局截止时间划分问题描述为一个约束下的非线性规划问题并通过已有方法求解该问题,提出了一种截止时间满意度增强的工作流调度算法(DSESAW).仿真实验采用实际网格应用和系统数据来验证所提出算法的性能表现,实验结果表明新算法在网格环境的自适应性和用户截止时间保障方面优于其他两种实际网格系统中的调度算法.     

多处理器系统可靠性约束下的节能调度算法

针对多处理器系统中随机到达的任务,设计了可靠性约束下的节能调度算法(ESACR)。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能,在单个处理器上运用最早截止期限优先策略进行调度并尽量使各个任务的执行电压/频率均衡,当新到任务在处理器上不能满足截止期限要求时则逐个调高前面未执行任务的电压/频率。同时,为保证系统的可靠性,ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果表明,与最高电压节能调度(HVEA)、最小能耗最小完成时间调度(ME-MC)、最早完成时间优先调度(EFF)相比,ESACR在保证系统可靠性的前提下节能效果最好。     

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

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

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     

A group priority earliest deadline first scheduling algorithm

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.     

Improving responsiveness of soft aperiodic tasks using proportional slack time

In a real-time system with both hard real-time periodic jobs and soft real-time aperiodic jobs, it is important to guarantee that the deadline of each periodic job is met, as well as to provide a fast response time for each aperiodic job. We propose an algorithm, called Proportional Slack Reserve (PSR), that produces an efficient schedule for such an environment. For every execution unit of a periodic job, the PSR algorithm reserves time which can be used for execution of aperiodic jobs. If reserved time is not available, the algorithm assigns a deadline to an aperiodic job for achieving better responsiveness of aperiodic jobs. The proposed algorithm can fully utilize processing power while meeting all deadlines of periodic jobs. It can also easily reclaim the time unused by the periodic job. We analytically show that for each aperiodic job, the response time in a PSR schedule is no longer than that in a TBS schedule, which is known to be efficient for servicing aperiodic jobs. We also present simulation results in which the response time of PSR is significantly improved over that of TBS, and moreover the performance of PSR compares favorably with TB(N) considering scheduling overhead.     

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

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

Scheduling multiple task graphs in heterogeneous distributed real-time systems by exploiting schedule holes with bin packing techniques

The most crucial aspect of distributed real-time systems is the scheduling algorithm, which must guarantee that every job in the system will meet its deadline. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a heterogeneous distributed real-time system. Each job that arrives in the system is a directed acyclic graph of component tasks and has an end-to-end deadline. For each scheduling policy, we provide alternative versions which allow the insertion of tasks into idle time slots, using various bin packing techniques. The comparison study, based on different workloads and system heterogeneity levels, shows that the alternative versions of the algorithms outperform their respective counterparts.     

Resource availability-aware advance reservation for parallel jobs with deadlines

Advance reservation is important to guarantee the quality of services of jobs by allowing exclusive access to resources over a defined time interval on resources. It is a challenge for the scheduler to organize available resources efficiently and to allocate them for parallel advance reservation jobs with deadline constraint appropriately. This paper provides a slot-based data structure to organize available resources of multiprocessor systems in a way that enables efficient search and update operations and formulates a suite of scheduling policies to allocate resources for dynamically arriving advance reservation requests. The performance of the scheduling algorithms were investigated by simulations with different job sizes and durations, system loads, and scheduling flexibilities. Simulation results show that job sizes and durations, system load and the flexibility of scheduling will impact the performance metrics of all the scheduling algorithms, and the $\textit{PE}\; \textit{Worst Fit}$ algorithm becomes the best algorithm for the scheduler with the highest acceptance rate of advance reservation requests, and the jobs with the $\textit{First Fit}$ algorithm experience the lowest average slowdown. The data structure and scheduling policies can be used to organize and allocate resources for parallel advance reservation jobs with deadline constraint in large-scale computing systems.     

Online deadline scheduling on faster machines

Online deadline scheduling is to determine which jobs are accepted or rejected, where jobs have the deadline by which they must finish their processing and they arrive in the online fashion. The slack of a job is the gap between its arrival time and the last time when it can first be scheduled to meet its deadline. The job instance is given such that the slack of each job is at least κ times its processing time, where κ is called patience. In this paper, online algorithms have faster machines than the adversary. We investigate the speed of machines on which the online algorithms can achieve the optimality and parametrize them by the patience.     

基于价值密度和截止期的网格作业调度算法

对商业网格中的作业调度问题进行研究,采用作业的到达时间、计算量、预算和截止期4个参数定义作业的优先级。在此基础上提出基于价值密度和相对截止期的网格作业调度算法,并对其进行仿真。仿真结果表明,该算法在实现价值率、按时完成作业数和加权作业按时完成率3个性能指标上优于现有算法,兼顾了消费者和服务者的利益。