• SID AHMED MAKHLOUF Dept. of Computer Science, University of Oran
  • BELABBAS YAGOUBI Dept. of Computer Science, University of Oran


Computational  grids  have  the  potential  for  solving  large-scale  scientific  problems  using  heterogeneous  and  geographically
distributed resources. However, a number of major technical hurdles must overcome before this potential can be realized. One
problem that is critical to effective utilization of computational grids and gives a certain Quality of Service (QoS) for grid users
is  the  efficient  co-allocation  of  jobs.  The  advance  reservation  technique  has  been widely  applied  in many  grid  systems  to
provide QoS, however, it will result in low resource utilization rate and high rejection rate when the reservation rate is high.
This work  addresses  those  problems  by  describing  and  evaluating  a  grid  resources  co-allocation  algorithm  using  resources
providers offers and planning  the advance  reservations.  In our algorithm, a Metascheduler performs  job scheduling based on
resources offers and use advance  reservation planning mechanism  to  reserves  the best  offers. Offers act as a mechanism  in
which  resource  providers  expose  their  interest  in  executing  an  entire  job  or  only  part  of  it.  The  Metascheduler  selects
computational resources based on best offers provided by  the resources; Meta-schedulers can distribute a  job among various
clusters that are usually heterogeneous in order to speed up the job execution.  
The main aims of our algorithm is to minimize the total time to execute all jobs (Makespen), minimize the waiting time in the
global queue, maximize  the resources utilization rate and balance  the  load among the resources. The proposed algorithm has
been compared with other scheduling schemes such as First Come First Served (FCFS), easy backfilling (EBF), Fit Processor
First Served (FPFS) and a simple co-allocation algorithm without offers support (SCOAL). The proposed algorithm has been
verified  through  an  extension  of GridSim  simulation  toolkit  and  the  simulation  results  confirm  that  the  proposed  algorithm
allow us to achieve our goals by minimizing the Makespan and the waiting time, maximizing the resources utilization rate and
load the balance among the resources.


Co-allocation in grid computing using resources offers and advance reservation planning
[11] Foster I., Kesseleman C., Tuecke S., "The Anatomy of the
Grid: Enabling Scalable virtual Organizations", International
Journal of Super Computer Applications 15, 3, 2001.
[12] Foster I., Iamnitchia A., "On Death, Taxes, and the
Convergence of Peer-to-Peer and Grid Computing", In
Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003, LNCS, vol.
2735, Springer, Heidelberg, 2003.
[13] Foster I., Roy A., Sander V., "A quality of service
architecture that combines resource reservation and
application adaptation", Proceedings of the 8th International
Workshop on Quality of Service (IWQoS’00), Jun 5-7, 2000,
Pittsburgh, PA, USA. Los Alamitos, CA, USA,IEEE
Computer Society, 181-188, 2000.
[14] He L. G., Jarvis S. A., Spooner D. P., "Allocating non-real-
time and soft real-time jobs in multiclusters", IEEE Trans on
Parallel and Distributed Systems, 17(2), 99−112, 2006.
[15] Herroelen W., De Reyck B., Demeulemeester E, "Resource
constrained project scheduling: A survey of recent
developments", Computers and Operations Research 25,
279–302, 1998.
[16] Leinberger W., Karypis G., Kumar V., "Job scheduling in
the presence of multiple resource requirements", Proceedings
of ACM/IEEE Conf on Supercomputing, Portland IEEE
Computer Society Press, 1999.

[17] Mohamed H. H., Epema D. H. J., "An evaluation of the
close-to-files processor and data co-allocation policy in
multiclusters", Proceedings of Inter Conf on Cluster
Computing, San Diego IEEE Computer Society Press,
287−298, 2004.
[18] Nisan N., London S., Regev O. "Globally distributed
computation over the internet: The POPCORN project",
Proceedings of Inter Conf on Distributed Computing
Systems, Amsterdam, IEEE Computer Society Press,
592−601, 1998.
[19] Roy A., Sander V., "Advance reservation API", Technical
Report GFD-E.5, Scheduling Working Group, Global Grid
Forum, 2002.
[20] Snell Q., Clement M., Jackson D., et al, "The performance
impact of advance reservation metascheduling", Proceedings
of Job Scheduling Strategies for Parallel Processing
(JSSPP’00), May 1-5, 2000, Cancun, Mexico. Los Alamitos,
CA, USA, IEEE Computer Society, 137-153, 2000.
[21] Waldspurger C. A., Hogg T., Huberman B. A., et al,
"Spawn: A distributed computational economy", IEEE Trans
on Software Engineering, 18(2), 103−117, 1992.
[22] Wolski R., Brevik J., Obertelli G., Spring N., "Writing
programs that run EveryWare on the computational grid",
IEEE Trans on Parallel and Distributed Systems, 12(10),
1066−1080, 2001.[1] Abramson D., Giddy J., Foster I. "High performance
parametric modeling with nimrod/G: killer application for
the global grid?", Proceedings of Inter Symp on Parallel and
Distributed Processing, Chicago, IEEE Computer Society
Press, 2000.
[2] Bal H., Bhoedjang R. R., Hofman R., "The distributed ASCI
supercomputer project", ACM Operating Systems Review,
34(4), 76−96, 2000.
[3] Bucur A. I. D., Epema D. H. J., "The performance of
processor co-allocation in multicluster systems", Proceedings
of IEEE/ACM Inter Symp on Cluster Computing and the
Grid, Tokyo, IEEE Computer Society Press, 302−309, 2003.
[4] Bucur A. I. D., Epema D. H. J., "Scheduling policies for
processor co-allocation in multicluster system", IEEE Trans
on Parallel and Distributed Systems, 18(7), 958−962, 2007.
[5] Buyya R., "Economic-based distributed resource
management and scheduling for grid computing",
Melbourne, Monash University, 2002.
[6] Buyya R., Abramson D., Venugopal S., "The grid economy",
Proceeding of the IEEE, 93(3), 698−714, 2005.
[7] Buyya R., Murshed M., "GridSim : A Toolkit for the
Modeling and Simulation of Distributed Resource
Management and Scheduling for Grid Computing", The
Journal of Concurrency and Computation, Practice and
Experience (CCPE), Volume 14, Issue 13-15, Wiley Press,
[8] Czajkowski K., Foster I., Kesselman C., "Resource
coallocation in computational grids", Proceedings of Inter
Symp on High Performance Distributed Computing,
California IEEE Computer Society Press, 219−228, 1999.
[9] Feitelson D. G., Rudolph R., "Parallel Job Scheduling: Issues
and Approaches", In Feitelson, D.G., Rudolph, L. (eds.)
IPPS-WS 1995 and JSSPP 1995. LNCS, vol. 949, pp. 1–18.
Springer, Heidelberg, 1995.
[10] Foster I., Kesselman C., Lee C., et al, "A distributed resource
management architecture that supports advance reservation
and co-allocation", Proceedings of the 7th International
Workshop on Quality of Service (IWQoS’99), Jun 1-4, 1999,
London, UK. Los Alamitos, CA, USA, IEEE Computer
Society, 27-36, 1999.
Comment citer
AHMED MAKHLOUF, SID; YAGOUBI, BELABBAS. CO-ALLOCATION IN GRID COMPUTING USING RESOURCES OFFERS AND ADVANCE RESERVATION PLANNING. Courrier du Savoir, [S.l.], v. 14, mai 2014. ISSN 1112-3338. Disponible à l'adresse : >>. Date de consultation : 15 jui. 2020