Open Access Open Access  Restricted Access Subscription or Fee Access

RAA: Task Scheduling Algorithm in Grid Computing Environment

J. Abuthahir, S. Vaaheedha Kfatheen, Dr. M. Nazreen Banu

Abstract


The purpose of grid computing is to produce a virtual supercomputer by using free resources available through widespread networks such as the Internet. Resource management and scheduling plays a crucial role in achieving high utilization of resources in grid computing environments. Due to heterogeneity of resources, scheduling an application is significantly complicated and challenging task in grid system. Most of the researches in this area are mainly focused to improve the performance of the grid system. In this paper, a new task scheduling algorithm called Resource Allocation Algorithm (RAA), is proposed to the resource allocation model with multiple load originating processors as an economic model.RAA first estimates the neighbour node details and most recently used resources to schedule a task. Linear programming approach is used to execute the Task Monitor which it avoids delay in the execution of large tasks and supports concurrency in the execution of large and small tasks. Experimental results proved that the proposed Algorithm (RAA) on scheduling independent tasks within grid environments achieves comparatively lower makespan and better solution in terms of cost and time.

Keywords


Gird Workflows, Workload Distribution, Economic Model, Cost Optimization, RAA Algorithm

Full Text:

PDF

References


Feo T. A. and Resende M. G. C. (1995): Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6:109-133, 1995.

Maheswaran. M, Ali. Sh, Jay Siegel. H, Hensgen. D, and Freund.R.F, "Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems, Journal of Parallel and Distributed Computing, Vol. 59, pp. 107-131, 1999.

Maheswaran M., Ali S., Siegel H. J, Hensgen D. and Freund R. F.(1999): Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J. Parallel Distributed Computing, 59, 2: 107-131, 1999.

Braun, T.D., Siegel, H.J., Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., et al. “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems”, Journal of Parallel and Distributed Computing, Vol. 61, No. 6, pp.810–837, 2001.

Ranganathan, K. and Foster, I., “Decoupling Computation and Data Scheduling in Distributed Data Intensive Applications”, Proceedings of the 11th IEEE Symposium on High Performance Distributed Computing (HPDC-11), Edinburgh, Scotland, July 2002.

Topcuoglu H., Hariri S.. and Wu M. Y.(2002): Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Transactions on Parallel and Distributed Systems, 13, 3: 260-274, 2002.

Tannenbaum T., Wright D., Miller K., and Livny M. (2002): Condor . A Distributed Job Scheduler. Computing with Linux, The MIT Press, MA, USA, 2002.

He. X, X-He Sun, and Laszewski. G.V, "QoS Guided Minmin Heuristic for Grid Task Scheduling," Journal of Computer Science and Technology, Vol. 18, pp. 442-451, 2003.

Young L., McGough S., Newhouse S. and Darlington J.(2003): Scheduling Architecture and Algorithms within the ICENI Grid Middleware. UK e-Science All Hands Meeting, IOP Publishing Ltd, Bristol,UK, Nottingham, UK, Sep. 2003; 5-12.

Menasc D. A. and Casalicchio E. (2004): A Framework for Resource Allocation in Grid Computing. Proc. of the 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, 2004; pp. 259-267.

Yu J., Buyya R. and Tham C. K. (2005): A Cost-based Scheduling of Scientific Workflow Applications on Utility Grids. Proc. of the First IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia, Dec. 2005, pp. 140-147.

Sakellariou R., Zhao H., Tsiakkouri E. and Dikaiakos M. D.(2005): Scheduling Workflows with Budget Constraints. Proc. of the CoreGRID Workshop on Integrated Research in Grid Computing, Gorlatch S. and Danelutto M. (Eds.), Tech. Rep. TR-05-22, University of Pisa, Dipartimento Di Informatica, Pisa, Italy, Nov. 2005, pp. 347-357.

Fahringer T., Jugravu A., Pllana S., Prodan R., Slovis C. Jr, and Truong H. L.(2005): ASKALON: A Tool Set for Cluster and Grid Computing. Concurrency and Computation: Practice and Experience, 17:143-169, 2005.

Wieczorek M., Prodan R. and Fahringer T. (2005): Scheduling of Scientific Workflows in the ASKALON Grid Environment. Special Issues on scientific workflows, ACM SIDMOD Record, 34, 3:56-62, 2005.

Blythe J.; Jain S.; Deelman E.; Gil Y.; Vahi K.; Mandal A.and Kennedy K.(2005): Task scheduling strategies for workflow-based applications in grids. Proc. of IEEE International Symposium on Cluster Computing and the Grid, vol. 2, pp. 759-767, May 2005.

Dong. F, Luo. J, Gao. L and Ge. L, "A Grid Task Scheduling Algorithm Based on QoS Priority Grouping," In the Proceedings of the Fifth International Conference on Grid and Cooperative Computing (GCC’06), IEEE, 2006.

Ludcher B., Altintas I., Berkley C., Higgins D., Jaeger-Frank E., Jones M., Lee E., Tao J. and Zhao Y.(2006): Scientific Workflow Management and the Kepler System. Concurrency and Computation: Practice and Experience, 18, 10: 1039-1065, 2006.

Etminani .K, and Naghibzadeh. M, "A Min-min Max-min Selective Algorithm for Grid Task Scheduling," The Third IEEE/IFIP International Conference on Internet, Uzbekistan, 2007.

Ullah Munir. E, Li. J, and Shi. Sh, 2007. QoS Sufferage Heuristic for Independent Task Scheduling in Grid. Information Technology Journal, 6 (8): 1166-1170.

Yu J. and Buyya R. (2007): Workflow Scheduling Algorithms for Grid Computing. Tech. Rep. GRIDS-TR-2007-10, Grid Computing and Distributed Systems Laboratory, The University of Melbourne, Australia, May 31, 2007.

Yagoubi. B, and Slimani. Y, "Task Load Balancing Strategy for Grid Computing," Journal of Computer Science, Vol. 3, No. 3, pp. 186-194, 2007.

Singh. M and Suri. P.K, QPS A QoS Based Predictive Max-Min, Min-Min Switcher Algorithm for Job Scheduling in a Grid, Information Technology Journal, Year: 2008, Volume: 7, Issue: 8, Page No.: 1176-1181.

Saeed Parsa, Reza Entezari-Maleki RASA: A New Grid Task Scheduling Algorithm , International Journal of Digital Content Technology and its Applications Volume 3, Number 4, December 2009.

Sameer Singh Chauhan,R. Joshi. C, QoS Guided Heuristic Algorithms for Grid Task Scheduling, International Journal of Computer Applications (0975 – 8887), pp 24-31, Volume 2, No.9, June 2010.

Murugesan.G, An Economic-based Resource Management and Scheduling for Grid Computing Applications, IJCSI International Journal of Computer Science Issues, VOL.7 No.5, March 2010.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.