Research On Online Scheduling Of Multiple Workflows In CloudEnvironments

With the development of the society,the scale of workflows that need to be computed and stored in different areas is increasing.Besides,the computation process is increasingly complicated.There is a general trend in IT that moves computation and data storage away from desktop and portable PCs into large scale data centers for better efficiency.Cloud computing as an increasingly popular computing paradigm,typically adopts the pay-as-you-go mechanism,and rely on the QoS(Quality of Service)to meet users' requirement.Typical examples of QoS include application deadline constraints etc.Therefore,in this thesis,we focus on such scheduling problems that consider real-time workflows,which consists of interdependent relationships between subtasks,with deadline constraints.Scheduling is critical to exploit the efficiency of cloud computing,it is the dominant key to affect whether computing resources can be efficient used.Majority of scheduling algorithms in the context of cloud computing focus on user-oriented metrics,e.g.,minimization of response time etc,other than system-oriented metrics,such as maximizing resource utilization,which is usually a concern of cloud service provider.In this thesis,the scheduling objectives of concern are task completion rate and cloud resources utilization,instead of the traditional overall processing time.To deal with the difficulties in real-time workflow scheduling studies in real cloud computing environments,such as "difficult to reach","limited size",and "lack of effective performance benchmark",we designed a real-time Workflow Simulator named RTWSim,which can aid to the theoretical research of workflow online scheduling problem.The simulator can generate a set of test workflow,which contains a certain number of tasks with interdependencies.Besides,each task has a deadline constraint.The most important feature of the constructed testset is that it guarantees that there always exists a schedule for the submitted workflows where the resource utilization rate reaches 100%and the deadlines can all be satisfied.Namely,we can always know one of the optimal schedules in advance.We expect this simulator can facilitates to the development of online workflow scheduling algorithms for clouds.To test and verify the correctness and availability of RTWSim,we evaluate four classic single processor scheduling algorithms for real-time workflows by using the RTWSim simulator.Furthermore,with the aid of RTWSim,we propose two new online scheduling algorithms for real-time workflows in cloud computing environments:Earliest Level-Deadline First Algorithm(ELDF)and Level Relaxing and Elastic Backfilling Algorithm(LREB).ELDF is derived from the classical EDF,which is not suitable for real-time workflow in clouds.In contrast,LREB employs Elastic Backfilling and Level Relaxing mechanismto improve the task success rate and effective resource utilization rate.