17-05-2013, 03:24 PM
RASA A NEW GRID TASK SCHEDULING Algorithm
A NEW GRID.pptx (Size: 166.43 KB / Downloads: 18)
Abstract
A new task scheduling algorithm called RASA is built through a comprehensive study and analysis of two well known task scheduling algorithms, Min-min and Max-min.
RASA takes advantages of the both algorithms and avoids their drawbacks. RASA firstly estimates the completion time of the tasks on each of the available grid resources, and then applies the Max-min and Min-min algorithms, alternatively.
RASA uses the Min-min strategy to execute small tasks before the large ones, and applies the Max-min strategy to avoid delays in the execution of the large tasks.
Applying RASA on scheduling independent tasks within grid environments RASA has comparatively lower make span.
Introduction
Computational grid is defined as a hardware and software infrastructure which provides dependable, consistent, pervasive and inexpensive access to computational resources existing on the network.
There are relatively a large number of task scheduling algorithms to minimize the total completion time of the tasks in distributed systems. These algorithms try to minimize the overall completion time of the tasks by finding the most suitable resources to be allocated to the tasks. Two well known examples of such algorithms are Max-min and Min-min. These two algorithms estimate the execution and completion times of each of the tasks on each of the grid resources.
Existing System
Opportunistic load balancing (OLB) algorithm is one of the earlier scheduling algorithms which do not use the execution or completion time of the tasks, and schedules the tasks in the arbitrary order. The insight behind OLB is to keep all resources as busy as possible.
One advantage of OLB is its simplicity, but because OLB does not consider expected task execution times, the mappings it finds can result in very poor make spans.
In OLB algorithm, if multiple resources become ready at the same time, then one resource is arbitrarily chosen.
Proposed System
RASA is Resource Aware Scheduling Algorithm.
The proposed grid scheduling algorithm is RASA. This algorithm builds a matrix C where Cij represents the completion time of the task Ti on the resource Rj.
If the number of available resources is odd, the Min-min strategy is applied to assign the first task, otherwise the Max-min strategy is applied.
The remaining tasks are assigned to their appropriate resources by one of the two strategies, alternatively.
For instance, if the first task is assigned to a resource by the Min-min strategy, the next task will be assigned by the Max-min strategy.
Conclusion
The make spans returned by RASA are smaller than the other algorithms in almost all different conditions.
RASA uses the advantages of Max-min and Min-min algorithms and covers their disadvantages.
The results obtained by applying RASA within the GridSim simulator, shows that RASA outperforms the existing scheduling algorithms in large scale distributed systems.