Job Scheduling on Grid Computing Using First Fit, Best Fit, and Worst Fit

Ardi Pujiyanta(1*), Fiftin Novianto(2),

(1) Universitas Ahmad Dahlan
(2) Universitas Ahmad Dahlan
(*) Corresponding Author
DOI: https://doi.org/10.23917/khif.v8i2.17069

Abstract

Grid computing can be considered large-scale distributed cluster computing and parallel distributed network processing. The two most important issues in managing user work are resource allocation and scheduling of required resources. When user jobs are submitted, they are managed by resource intermediaries who find and allocate the right resources. After the resource allocation stage, work scheduled on the existing resources according to the user's required resources. In most grid systems with traditional scheduling, jobs are submitted and placed in waiting room queues to wait for the required resources to become available. Each grid system can use a different scheduling algorithm to execute jobs based on other parameters, such as resources, delivery time, and execution duration. There is no guarantee that these traditional scheduling algorithms will get the job done. The First Come First Serve Left Right Hole Scheduling (FCFS-LRH) reservation strategy improves resource utilization in a grid system by using a local scheduler. Compared to traditional strategies. There are two objectives of this research. First, compare the first fit, best fit, and worst fit algorithms to find empty timeslots and place them in a virtual view. Second, reduce the idle time value. The results showed that the FCFS-LRH method could reduce the idle time value of the FCFS-EDF and FCFS methods. The overall execution time of the first fit with the FCFS-LRH strategy is better than the FCFS-EDF

Keywords

Grid computing, Scheduling, FCFS-LRH, FCFS-EDF

Full Text:

PDF

References

S. Kumari and G. Kumar, “Survey on Job Scheduling Algorithms in Grid Computing,” Int. J. Comput. Appl., vol. 115, no. 15, pp. 17–20, Apr. 2015, doi: 10.5120/20227-2511.

A. Sulistio, K. H. Kim, and R. Buyya, “On incorporating an on-line strip packing algorithm into elastic grid reservation-based systems,” Proc. Int. Conf. Parallel Distrib. Syst. - ICPADS, vol. 1, 2007, doi: 10.1109/ICPADS.2007.4447738.

A. Sulistio, U. Cibej, S. K. Prasad, and R. Buyya, “GarQ: An efficient scheduling data structure for advance reservations of grid resources,” Int. J. Parallel, Emergent Distrib. Syst., vol. 24, no. 1, pp. 1–19, 2009, doi: 10.1080/17445760801988979.

A. B.Patel, “Modeling and Simulation of Grid Resource Brokering Algorithms,” Int. J. Comput. Appl., vol. 42, no. 8, pp. 31–36, 2012, doi: 10.5120/5715-7774.

H. B. Prajapati and V. A. Shah, “Scheduling in Grid Computing Environment,” in 2014 Fourth International Conference on Advanced Computing & Communication Technologies, Feb. 2014, pp. 315–324, doi: https://doi.org/10.1109/ACCT.2014.32.

A. Sulis, “GRID computing approach for multireservoir operating rules with uncertainty,” Environ. Model. Softw., vol. 24, no. 7, pp. 859–864, Jul. 2009, doi: https://doi.org/10.1016/j.envsoft.2008.11.003.

C. Castillo, G. N. Rouskas, and K. Harfoush, “On the design of online scheduling algorithms for advance reservations and QoS in grids,” Proc. - 21st Int. Parallel Distrib. Process. Symp. IPDPS 2007; Abstr. CD-ROM, 2007, doi: 10.1109/IPDPS.2007.370226.

I. Foster and C. Kesselman, “The history of the grid,” Adv. Parallel Comput., vol. 20, pp. 3–30, 2011, doi: 10.3233/978-1-60750-803-8-3.

I. Foster, C. Kesselman, and S. Tuecke, “The Anatomy of the Grid,” Grid Comput., pp. 169–197, 2003, doi: 10.1002/0470867167.ch6.

A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke, “The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets,” J. Netw. Comput. Appl., vol. 23, no. 3, pp. 187–200, 2000, doi: 10.1006/jnca.2000.0110.

R. Buyya, D. Abramson, and J. Giddy, “Nimrod/G: An architecture for a resource management and scheduling system in a global computational grid,” Proc. - 4th Int. Conf. High Perform. Comput. Asia-Pacific Reg. HPC-Asia 2000, vol. 1, pp. 283–289, 2000, doi: 10.1109/HPC.2000.846563.

C. T. Yang, W. C. Shih, and C. H. Hsu, “On utilization of the grid computing technology for video conversion and 3D rendering,” Comput. Stand. Interfaces, vol. 32, no. 1–2, pp. 29–37, 2010, doi: 10.1016/j.csi.2009.06.003.

K. Al Tabash, A. Barradah, and R. Al Shaikh, “Empirical Utilization Analysis for High Performance and Grid Computing,” in 2014 UKSim-AMSS 16th International Conference on Computer Modelling and Simulation, Mar. 2014, pp. 392–398, doi: https://doi.org/10.1109/UKSim.2014.47.

S. Sahhaf, M. Barshan, W. Tavernier, H. Moens, D. Colle, and M. Pickavet, “Resilient algorithms for advance bandwidth reservation in media production networks,” Proc. 2016 12th Int. Conf. Des. Reliab. Commun. Networks, DRCN 2016, no. Drcn, pp. 130–137, 2016, doi: 10.1109/DRCN.2016.7470847.

A. A. Haruna, B. Z. Nordin, and H. Narleeni, “Grid Resource Allocation: A Review,” Res. J. Inf. Technol., vol. 4, no. 2, pp. 38–55, 2012, [Online]. Available: http://www.maxwellsci.com/print/rjit/v4-38-55.pdf.

M. B. Qureshi, M. A. Alqahtani, and N. Min-Allah, “Grid resource allocation for real-time data-intensive tasks,” IEEE Access, vol. 5, pp. 22724–22734, 2017, doi: 10.1109/ACCESS.2017.2760801.

Kai Hwang and Zhiwei Xu, “Scalable parallel computers for real-time signal processing,” IEEE Signal Process. Mag., vol. 13, no. 4, pp. 50–66, Jul. 1996, doi: https://doi.org/10.1109/79.526898.

M. P. Tiemeyer and J. S. K. Wong, “A task migration algorithm for heterogeneous distributed computing systems,” J. Syst. Softw., vol. 41, no. 3, pp. 175–188, Jun. 1998, doi: https://doi.org/10.1016/S0164-1212(97)10018-8.

R. Umar, A. Agarwal, and C. R. Rao, “Advance Planning and Reservation in a Grid System,” Commun. Comput. Inf. Sci., vol. 293 PART 1, pp. 161–173, 2012, doi: 10.1007/978-3-642-30507-8_15.

A. Pujiyanta, L. E. Nugroho, and Widyawan, “Resource allocation model for grid computing environment,” Int. J. Adv. Intell. Informatics, vol. 6, no. 2, pp. 185–196, 2020, doi: https://doi.org/10.26555/ijain.v6i2.496.

A. Iosup, D. H. J. Epema, J. Maassen, and R. Van Nieuwpoort, “Synthetic grid workloads with Ibis, KOALA, and GRENCHMARK,” in Integrated Research in GRID Computing - CoreGRID Integration Workshop 2005, Selected Papers, 2007, pp. 271–283, doi: 10.1007/978-0-387-47658-2_20.

A. Sulistio, K. H. Kim, and R. Buyya, “Using revenue management to determine pricing of reservations,” in Third IEEE International Conference on e-Science and Grid Computing (e-Science 2007), 2007, pp. 396–404, doi: 10.1109/E-SCIENCE.2007.83.

M. Carvalho and F. Brasileiro, “A user-based model of grid computing workloads,” in 2012 ACM/IEEE 13th International Conference on Grid Computing, 2012, pp. 40–48, doi: 10.1109/Grid.2012.13.

A. Pujiyanta, L. E. Nugroho, and Widyawan, “Planning and Scheduling Jobs on Grid Computing,” Proceeding - 2018 Int. Symp. Adv. Intell. Informatics Revolutionize Intell. Informatics Spectr. Humanit. SAIN 2018, pp. 162–166, 2019, doi: https://doi.org/10.1109/SAIN.2018.8673372.

A. Pujiyanta, L. E. Nugroho, and Widyawan, “Advance Reservation for Parametric Job on Grid Computing,” Proc. 2019 4th Int. Conf. Informatics Comput. ICIC 2019, pp. 0–4, 2019, doi: https://doi.org/10.1109/ICIC47613.2019.8985978

Article Metrics

Abstract view(s): 410 time(s)
PDF: 280 time(s)

Refbacks

  • There are currently no refbacks.