Study On Scheduling Problem Of Instance-intensive Worklfows Under Cloud Environment

Instance-intensive workflow is an important and increasingly widely used commercial application. Online shopping with millions of transactions each day, which is still growing at a rapid rate, is just an example of the instance-intensive workflow applications. While traditional distributed computing, parallel computing and grid computing can hardly handle the fast growing instance-intensive workflow applications with a huge number of data. Cloud computing, however, can process massive data and solve that problem well by creating "cloud". Thus, instance-intensive workflow applications will gradually transfer to cloud environment, and resource scheduling is one of the key issues. The scheduling algorithms for instance-intensive workflows so far under cloud environment have mainly focused on QoS(cost and time) factors, while the reliability factor is not paid enough attention, which leads to a higher risk of task execution-interruption resulting from resources’failure, and then adds extra task execution cost, delays task completion time, and may even results in rescheduling.In view of the above problems, this thesis introduces trust mechanism, which assesses the reliability of resources by establishing trust model. In this mechanism, the direct trust value is determined by both the historical experience of the resource itself, including service time, the frequency of service success, service failure and service delay, and the time attenuation factor a, resulting from the recent-biased technology based on time series; the indirect trust value is decided mainly by the failure law of the task node executing the task. Further more, regarding the characteristics of the unreliability of cloud resources and the fierce competition for resources of the instance-intensive workflow, this thesis designs the Trust-drive Minimize Cost Within Deadline algorithm, namely, TD-MCWD algorithm. On the one hand, the TD-MCWD algorithm stagger deadlines of the large number of concurrent instances of the same nature, expecting to get cheaper and more intensively competitive resources, since the later sub-deadline tasks may have the chance to use cheaper resources released by earlier sub-deadline tasks. On the other hand, it will predict success and failure probability of task when executed in resource nodes on the basis of resource reliability estimated by trust model. Then, with a comprehensive consideration of execution cost and time in successful task implementation, risk cost and time in task execution-interruption, the TD-MCWD algorithm will calculate the total task execution time and cost, then choose the lowest total cost resource to execute the task, in condition that the resource meets the constraints of the task’s sub-deadline. In the end, this thesis extends the CloudSim tool, realizing TD-MCWD algorithm and comparing it with other algorithms in simulation. The result of the comparison shows that TD-MCWD can reduce the rate of delayed instance completion and the average execution cost of successful instance completion. Besides, TD-MCWD has a better load balancing and shows a better performance.