A New Heuristic Metatask Scheduling Algorithm Based on Choosing QoS Policy Mechanism

More and more applications of grid have been achieved. How to support Quality of Service (QoS) to meet different users' demand has raised an outstanding challenge. Currently, several QoS policies of resource have been widely used in Grid. Thus, how to use them freely and efficiently is a serious problem. In this study, we illustrated three QoS policies of resources: best effort, real time, and competing, and explain their mechanisms. Following this, we proposed a new QoS policy, namely Free QoS policy, to help the user who is not very familiar with QoS polices. The first step is that we can get the matrix of QoS parameters of each resource from the Policy Pool in which all the information about QoS policies of resources in “virtual organizations†could be obtained. Second, we will calculate every resource's P adjugment value by a comparison algorithm. Finally, the QoS policy matching the maximum value of P adjugment value is the user's decision. After choosing a suitable resource with a clear QoS policy, the next question is how to achieve an optimum quality under the given policy, which is the problem of scheduling. Min_Min algorithm has been widely used as a higher efficiency and simple algorithm. However, it has a serious problem: load unbalance. In order to solve the problem, we propose a novel task scheduling algorithm, called the Heuristic task scheduling algorithm based on Min-Min and Max-Min (H-MM) in the best effort of the QoS policy, which is merged with the high efficiency of the traditional Min-Min scheduling algorithm and the load balance of the traditional Max-Min scheduling algorithm. Through plenty of experiments, we know that the performance of Max-Min is better than that of Min-Min in the condition that the values of ETC are not uniform, and the performance of Min-Min is a priority to Max-Min when there are many tasks in which the value of ETC are uniform. In this paper, we take the relative standard deviation value of ETC matrix's Min_Time as the criterion to judge whether the set of tasks is uniform or not. Finally, the scheduler selects the Max-Min or Min-Min to assign tasks. The experiments have shown that the H-MM algorithm overweighs traditional algorithms a lot in the makespan and the scalability of the scheduling algorithm.