Abstract
Recent enthusiasm in grid computing has resulted in a tremendous amount of research in resource scheduling techniques for tasks in a workflow. Most of the work on resource scheduling is aimed at minimizing the total response time for the entire workflow and treats the estimated response time of a task running on a local resource as a constant. In this paper, we propose a probabilistic framework for resource scheduling in grid environment that views the task response time as a probability distribution to take into consideration the uncertain factors. The goal is to dynamically assign resources to tasks so as to maximize the probability of completing the entire workflow within a desired total response time. We propose three algorithms for the dynamic resource scheduling in grid environment. Experimental results using synthetic data derived from a real protein annotation workflow application demonstrate that considering the uncertain factors of task response time in task scheduling does yield better performance, especially in a heterogeneous environment. We also compare the relative performance of the three proposed algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afzal, A., Darlington, J., McGough, A.S.: Stochastic Workflow Scheduling with QoS Guarantees in Grid Computing Environments. In: Proc. of International Conference on Grid and Cooperative Computing, pp. 185–194 (2006)
Blythe, J., Jain, S., Deelman, E., Gil, Y., Vahi, K., Mandal, A., Kennedy, K.: Task scheduling strategies for workflow-based applications in grids. In: Proc. of CCGri 2005, pp. 759–767 (2005)
Cao, J., Spooner, D.P., Jarvis, S.A., Nudd, G.R.: Grid load balancing using intelligent agents. Future Generation Comput. Syst. 21(1), 135–149 (2005)
Duan, R., Prodan, R., Fahringer, T.: Run-time optimisation of grid workflow applications, pp. 33–40 (2006)
Mandal, A., Kennedy, K., Koelbel, C., Marin, G., Mellor-Crummey, J., Liu, B., Johnsson, L.: Scheduling strategies for mapping application workflows onto the grid. In: Proc. of HPDC 2005, pp. 125–134 (2005)
Nino-Mora, J.: Stochastic scheduling. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 367–372 (2005) [Updated version]
O’Brien, A., Newhouse, S., Darlington, J.: Mapping of scientific workflow within the e-protein project to distributed resources. In: Proc. of UK e-Science all Hands Meeting, pp. 404–409 (2004)
Paranhos da Silva, D., Cirne, W., Vilar Brasileiro, F.: Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids. In: Proc. of the Euro-Par, pp. 169–180 (2003)
Patel, Y., Mcgough, A.S., Darlington, J.: QoS support for workflows in A volatile grid. In: Proc. of Gri 2006, pp. 64–71 (2006)
Spooner, D.P., Cao, J., Jarvis, S.A., He, L., Nudd, G.R.: Performance-Aware Workflow Management for Grid Computing. The Computer Journal 48, 347–357 (2005)
Vanderster, D.C., Dimopoulos, N.J., Sobie, R.J.: Metascheduling multiple resource types using the MMKP. In: Proc. of Grid 2006, pp. 231–237 (2006)
Weiss, G., Pinedo, M.: Scheduling Tasks with Exponential Service Times on Non-Identical Processors to Minimize Various Cost Functions. Journal of Applied Probability, 187–202 (1980)
Yu, J., Buyya, R., Chen, K.T.: Cost-based scheduling of scientific workflow applications on utility grids. In: Proc. of 2005.First International Conference on E-Science and Grid Computing, pp. 8–16 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hwang, SY., Tang, J., Lin, HY. (2008). A Probability-Based Framework for Dynamic Resource Scheduling in Grid Environment. In: Wu, S., Yang, L.T., Xu, T.L. (eds) Advances in Grid and Pervasive Computing. GPC 2008. Lecture Notes in Computer Science, vol 5036. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68083-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-68083-3_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68081-9
Online ISBN: 978-3-540-68083-3
eBook Packages: Computer ScienceComputer Science (R0)