网格计算中任务调度算法的研究和改进

任务调度一直是网格计算中的热点问题,任务调度的目的是最优地分配任务,实现最佳的调度策略,以高效地完成计算任务。在网格环境中,资源的合理有效利用是实现任务调度的关键问题之一。本文首先论述静态任务调度算法和动态任务算法的原理和优缺点等,然后结合Min-min、Max-min算法的优点设计一种新的调度算法SA-MM,根据资源的使用情况自适应调度相应算法进行任务到资源的映射。最后,用GridSim模拟工具对网格计算中Min-min、Max-min和SA-MM任务调度算法进行仿真实验,分析和比较它们的调度长度(MakeSpan)和资源负载情况等影响任务调度效率的指标。     

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.     

To Schedule or to Execute: Decision Support and Performance Implications

This paper addresses a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The time allocated to scheduling must be controlled explicitly, in order to obtain good-quality schedules in reasonable times. As task constraints are relaxed, the algorithms proposed in this paper increase scheduling complexity to optimize longer and obtain high-quality schedules. When task constraints are tightened, the algorithms adjust scheduling complexity to reduce the adverse effect of long scheduling times on the schedule quality. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled tasks. We investigate the performance of our algorithms in two scheduling models: one that allows idle-time intervals to exist in the schedule and another that does not. The model with idle-time intervals has important implications for dynamic scheduling which are discussed in the paper. Experimental evaluation of the proposed algorithms shows that our algorithms outperform other candidate algorithms in several parameter configurations.     

A New Strategy for Improving the Effectiveness of Resource Reclaiming Algorithms in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted the attention of many researchers in the recent past. Tasks in such systems have deadlines to be met, and most real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. Several resource reclaiming algorithms such as Basic, Early Start, and RV algorithms have been proposed in the recent past. But these pay very little attention to the strategy by which the scheduler can better utilize the benefits of reclaimed resources. In this paper, we propose an esti- mation strategy which can be used along with a particular class of resource reclaiming algorithms (such as Early Start and RV algorithms) by which the scheduler can estimate the minimum time by which any scheduled but unexecuted task will start or finish early, based solely on the start and finish times of tasks that have started or finished execution. We then propose an approach by which dynamic scheduling strategies, which append or reschedule new tasks into the schedules, can use this estimation strategy to achieve better schedulability. Extensive simulation studies are carried out to investigate the effectiveness of this estimation strategy versus its cost.     

一种基于神经网络的网格实时调度算法*

提出一种在指定的最终期限内,利用队列技术来模拟调度动态资源,构建一个数学神经模型调度应用的子任务,使用GridSim 工具测试的调度算法,通过大约90%的模拟实验说明了模型调度任务是成功和高效的。     

Aperiodic servers in a deadline scheduling environment

A real-time system may have tasks with soft deadlines, as well as hard deadlines. While earliest-deadline-first scheduling is effective for hard-deadline tasks, applying it to soft-deadline tasks may waste schedulable processor capacity or sacrifice average response time. Better average response time may be obtained, while still guaranteeing hard deadlines, with an aperiodic server. Three scheduling algorithms for aperiodic servers are described, and schedulability tests are derived for them. A simulation provides performance data for these three algorithms on random aperiodic tasks. The performances of the deadline aperiodic servers are compared with those of several alternatives, including background service, a deadline polling server, and rate-monotonic servers, and with estimates based on the M/M/1 queueing model. This adds to the evidence in support of deadline scheduling,versus fixed priority scheduling.     

Generating short-term observation schedules for space mission projects

In this paper, we propose a new dispatching rule and a set of local search algorithms based on the filtered beam search, GRASP and simulated annealing methodologies to construct short-term observation schedules of space mission projects, mainly for NASA's Hubble Space Telescope (HST). The main features of generating short-term observations of HST are state dependent set up times, user specified deadlines, visibility windows of the targets and the priorities assigned to the observations. The objective of HST scheduling is to maximize the scientific return. We have tested the relative performances of the proposed algorithms including the nearest neighbor rule both in objective function value and computational time aspects by utilizing a full-factorial experimental design.     

Multi-objective scheduling of many tasks in cloud platforms

The scheduling of a many-task workflow in a distributed computing platform is a well known NP-hard problem. The problem is even more complex and challenging when the virtualized clusters are used to execute a large number of tasks in a cloud computing platform. The difficulty lies in satisfying multiple objectives that may be of conflicting nature. For instance, it is difficult to minimize the makespan of many tasks, while reducing the resource cost and preserving the fault tolerance and/or the quality of service (QoS) at the same time. These conflicting requirements and goals are difficult to optimize due to the unknown runtime conditions, such as the availability of the resources and random workload distributions. Instead of taking a very long time to generate an optimal schedule, we propose a new method to generate suboptimal or sufficiently good schedules for smooth multitask workflows on cloud platforms.Our new multi-objective scheduling (MOS) scheme is specially tailored for clouds and based on the ordinal optimization (OO) method that was originally developed by the automation community for the design optimization of very complex dynamic systems. We extend the OO scheme to meet the special demands from cloud platforms that apply to virtual clusters of servers from multiple data centers. We prove the suboptimality through mathematical analysis. The major advantage of our MOS method lies in the significantly reduced scheduling overhead time and yet a close to optimal performance. Extensive experiments were carried out on virtual clusters with 16 to 128 virtual machines. The multitasking workflow is obtained from a real scientific LIGO workload for earth gravitational wave analysis. The experimental results show that our proposed algorithm rapidly and effectively generates a small set of semi-optimal scheduling solutions. On a 128-node virtual cluster, the method results in a thousand times of reduction in the search time for semi-optimal workflow schedules compared with the use of the Monte Carlo and the Blind Pick methods for the same purpose.     

Planning virtual infrastructures for time critical applications with multiple deadline constraints

Executing time critical applications within cloud environments while satisfying execution deadlines and response time requirements is challenging due to the difficulty of securing guaranteed performance from the underlying virtual infrastructure. Cost-effective solutions for hosting such applications in the Cloud require careful selection of cloud resources and efficient scheduling of individual tasks. Existing solutions for provisioning infrastructures for time constrained applications are typically based on a single global deadline. Many time critical applications however have multiple internal time constraints when responding to new input. In this paper we propose a cloud infrastructure planning algorithm that accounts for multiple overlapping internal deadlines on sets of tasks within an application workflow. In order to better compare with existing work, we adapted the IC-PCP algorithm and then compared it with our own algorithm using a large set of workflows generated at different scales with different execution profiles and deadlines. Our results show that the proposed algorithm can satisfy all overlapping deadline constraints where possible given the resources available, and do so with consistently lower host cost in comparison with IC-PCP.     

A new real time disk-scheduling method based on GSR algorithm

Disk scheduling has an important role in QOS guarantee of soft real-time environments such as video-on-demand and multimedia servers. Since now, some disk-scheduling algorithms have been proposed to schedule real-time disk requests. One of the most recent algorithms is global seek-optimizing real-time (GSR) that schedules the disk requests with different ready times by a global regrouping scheme. In the present paper, we propose a real-time disk-scheduling algorithm based on GSR that is called IGSR (improved GSR). IGSR creates the scan-groups of the requests and tries to find a good feasible schedule by optimized grouping with considering another chance for tasks that miss their deadlines at initial grouping. With regard to the admission policy of tasks, two different version of proposed method are presented: the first one has been designed for the case that all the disk requests available simultaneously and second one has been designed for the case that requests are admitted dynamically (GSR does not support the second one). It means that in the second case, the request queue may change when a task is running but in the first one it does not change. Simulation results showed IGSR outperformed GSR and some other related works in terms of maximum supportable streams, number of missed deadlines, and disk throughput.     

Multi-QoS constrained and Profit-aware scheduling approach for concurrent workflows on heterogeneous systems

The execution of a workflow application can result in an imbalanced workload among allocated processors, ultimately resulting in a waste of resources and a higher cost to the user. Here, we consider a dynamic resource management system in which processors are reserved not for a job but only to run a task, thus allowing a higher resource usage rate. This paper presents a scheduling algorithm that manages concurrent workflows in a dynamic environment in which jobs are submitted by users at any moment in time, on shared heterogeneous resources, and constrained to a specified budget and deadline for each job. Recent research attempted to propose dynamic strategies for concurrent workflows but only addressed fairness in resource sharing among applications while minimizing the execution time. The Multi-QoS Profit-Aware scheduling algorithm (MQ-PAS) proposed here is able to increase the profit achieved by the provider by considering the budget available for each job to define tasks priorities. We study the scalability of the algorithm with different types of workflows and infrastructures. The experimental results show that our strategy improves provider revenue significantly and obtains comparable successful rates of completed jobs.     

New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted many researchers in the recent past. Tasks in these systems have deadlines to be met, and most of the real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. In this paper, we propose two algorithms to reclaim these resources from real-time tasks that are constrained by precedence relations and resource requirements, in shared memory multiprocessor systems. We introduce a notion called a restriction vector for each task which captures its resource and precedence constraints with other tasks. This will help not only in the efficient implementation of the algorithms, but also in obtaining an improvement in performance over the reclaiming algorithms proposed in earlier work [[2]]. We compare our resource reclaiming algorithms with the earlier algorithms and, by experimental studies, show that they reclaim more resources, thereby increasing the guarantee ratio (the ratio of the number of tasks guaranteed to meet their deadlines to the number of tasks that have arrived), which is the basic requirement of any resource reclaiming algorithm. From our simulation studies, we demonstrate that complex reclaiming algorithms with high reclaiming overheads do not lead to an improvement in the guarantee ratio.     

Power and performance management for parallel computations in clouds and data centers

We address scheduling independent and precedence constrained parallel tasks on multiple homogeneous processors in a data center with dynamically variable voltage and speed as combinatorial optimization problems. We consider the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on multiple processors. Our approach is to use level-by-level scheduling algorithms to deal with precedence constraints. We use a simple system partitioning and processor allocation scheme, which always schedules as many parallel tasks as possible for simultaneous execution. We use two heuristic algorithms for scheduling independent parallel tasks in the same level, i.e., SIMPLE and GREEDY. We adopt a two-level energy/time/power allocation scheme, namely, optimal energy/time allocation among levels of tasks and equal power supply to tasks in the same level. Our approach results in significant performance improvement compared with previous algorithms in scheduling independent and precedence constrained parallel tasks.     

云计算环境下带安全约束的工作流调度问题的研究

资源调度问题一直是云计算环境下的热点研究问题,然而当前的大部分研究都集中在满足用户的时间或成本需求上,很少考虑用户在调度过程中对安全的需求。针对这一问题,在对常见的云环境下工作流任务的资源调度问题进行建模的基础上,提出了一个安全约束模型,并使用变近邻粒子群算法对该问题进行了求解。最后在CloudSim仿真平台上,用最大 最小蚁群算法和遗传算法与该算法进行了对比,实验结果表明,该算法具有很好的可用性和寻优能力。关键词：     

An optimal boundary fair scheduling algorithm for multiprocessor real-time systems

With the emergence of multicore processors, the research on multiprocessor real-time scheduling has caught more researchers’ attention recently. Although the topic has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks with quantum-based computation requirements and implicit deadlines, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which can achieve full system utilization as the well-known Pfair scheduling algorithms. However, different from Pfair algorithms that make scheduling decisions and enforce proportional progress (i.e., fairness) for all tasks at each and every time unit, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries (i.e., deadlines of periodic tasks). The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved and its performance is evaluated through extensive simulations. The results show that, compared to that of Pfair algorithms, Bfair can significantly reduce the number of scheduling points (by up to 94%) and the overhead of Bfair at each scheduling point is comparable to that of the most efficient Pfair algorithm (i.e., PD²). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule can dramatically reduce the number of required context switches and task migrations (as much as 82% and 85%, respectively) when compared to those of Pfair schedules, which in turn reduces the run-time overhead of the system.     

On Task Scheduling Accuracy: Evaluation Methodology and Results

Many heuristics based on the directed acyclic graph (DAG) have been proposed for the static scheduling problem. Most of these algorithms apply a simple model of the target system that assumes fully connected processors, a dedicated communication sub-system and no contention for the communication resources. Only a few algorithms consider the network topology and the contention for the communication resources. This article evaluates the accuracy of task scheduling algorithms and thus the appropriateness of the applied models. An evaluation methodology is proposed and applied to a representative set of scheduling algorithms. The obtained results show a significant inaccuracy of the produced schedules. Analyzing these results is important for the development of more appropriate models and more accurate scheduling algorithms.     

Migration-aware adaptive MPSoC static schedules with dynamic reconfigurability

Technology scalings in semiconductors have enabled the integration of dozens of processing elements (PEs) onto a single chip (MPSoC). Scheduling application tasks onto the target MPSoC has been widely reported in the literature. Both technology scalings and resource competitions among applications have led to the variations of availability resources at runtime. While adaptive static schedules with predictable responses to runtime resource variations have consequently been proposed, a large number of task migrations upon PE failures in this reconfigurable schedule scheme will lead to excessive migration cost among processors and performance degradation. In this paper, we present an algorithm to reduce the number of task migrations while retaining the benefits of the fore techniques. Through embedding several soft constraints into the baseline heuristic scheduling algorithm, the proposed algorithm can decrease the number of task migrations significantly on the basis of holding the advantages of the initial dynamic reconfigurable schedule scheme. The performance evaluation of the proposed technique is carried out by incorporation into a well known heuristic scheduling algorithm. The simulation results confirm its effectiveness in minimizing the number of task migrations during dynamic reconfiguration.     

Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign the resources to tasks (match) and order the execution of tasks on each resource (schedule) to exploit the heterogeneity of the resources and tasks. Dynamic mapping (defined as matching and scheduling) is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no inter-task communication), and tasks have priorities and multiple soft deadlines. The value of a task is calculated based on the priority of the task and the completion time of the task with respect to its deadlines. The goal of a dynamic mapping heuristic in this research is to maximize the value accrued of completed tasks in a given interval of time. This research proposes, evaluates, and compares eight dynamic mapping heuristics. Two static mapping schemes (all arrival information of tasks are known) are designed also for comparison. The performance of the best heuristics is 84% of a calculated upper bound for the scenarios considered.     

适用于实例密集型云工作流的调度算法

工作流调度算法仅适用于单个复杂工作流实例,而不适用于实例密集型云工作流实例,为此,提出了基于实例密集型的云工作流调度算法(MCUD)。MCUD算法先对待处理的一组工作流实例进行分类,再对分类后的同类工作流实例采用一种新的分配方法将用户指定的总最后期限分配到各任务;同时,在调度的过程中动态地调整后续任务的子最后期限。MCUD算法对同类工作流实例中的任务分配不同子最后期限,减小了资源竞争,提高了资源的利用率。仿真实验表明,MCUD相比于其他算法,在满足总的最后期限的前提下更进一步地降低了执行成本和执行时间。     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.