Scheduling Cloud internet based computing model it delivers Software

Scheduling Algorithms comparison in Cloud Environment

 

Muhammad Zohaib Nauman

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

 

Department of Computer Sciences, Capital University of Science and
Technology

Islamabad, Pakistan.

         [email protected]

 

Abstract – Cloud computing is widely used in large scale parallel
processing and distributed computing. The performance of cloud computing
depends on efficient usage of resources. Task scheduling plays an important
role in cloud for managing resources. This paper compares the performance of
four different scheduling algorithms. The algorithms considered are First Come
First Serve (FCFS), Shortest Job First (SJF), Min-min and Max-min. The
algorithms performance is evaluated using CloudSim simulator. The measures considered
for evaluation are throughput, total execution time and average resource
utilization.

 

Keywords – Cloud Computing, Task Scheduling, First Come First Serve (FCFS),
Shortest Job First (SJF), Min-min, Max-min.

 

1.     
Introduction

 

Cloud computing
1 is a collection of computing and communication resources located over
distributed datacentres that is shared by many different users. Task scheduling
1 and other constraints which have direct effect on user consumption of
resources are controlled by cloud infrastructure. In Cloud internet based
computing model it delivers Software as a Services (SaaS), Platform
as a Service (PaaS) and Infrastructure as a Service (IaaS) 1. In
SaaS, software application is software distribution model which is made
available by the cloud provider or vendor and services are provides to end user
over the internet. In PaaS development, tools and platforms are supplied by
provider to allow the developer to create and run the various web based
application. In IaaS virtualized hardware and software as computing components
are provided to the cloud user in the form of Virtual Machine (VM) to develop
the platform and software for the end user.

CloudSim 2 is
framework for simulation and modelling of cloud environment. By using CloudSim,
developers can focus on specific systems design issues that they want to
investigate, without getting concerned about details related to cloud-based
infrastructures and services.

 

In
CloudSim 2, resource provisioning 4 is a combination of both resource allocation
and task scheduling. Available resources in cloud must be setup in such a
manner that the computing power of the machines is utilized efficiently.

 

Task
Scheduling 1 refers to the strategy to control the work order to be performed
by a computing system. The main aim of scheduling algorithms in cloud computing
is to distributing the load on different processors in order to maximize
resource utilization while minimize the total execution time of tasks. Task
scheduling is one of the most important optimization problems, it plays an
important role to improve performance of clouds.

The
main purpose of task scheduling is to assign tasks to the allocated resources
in accordance with time. There have been various kinds of scheduling algorithms
existing in cloud computing system.

 

 

 

The
main benefit of task scheduling is to obtain a high performance from computing
system which leads to efficient system throughput. Scheduling regulates
availability of resources and a good scheduling policy provides maximum
utilization of computing resource.

 

There
are two modes of the task scheduling 2: 1) Space-shared, 2) Time-shared. The
performance of task scheduling depends upon the various parameters like
execution time, response time and completion time 4. The primary aim is to
focus on minimizing the overall execution time of tasks on machines.

This paper is
organized as follows: Section 2 shows the related work, Section 3 shows scheduling
algorithms, Section 4 shows experiment and discussion and Section 5 shows
conclusions.

 

2.     
Related
Work

 

There is a lots
of related work had done in task scheduling to achieve the minimum execution
time in cloud environment.

 

In 3,
authors presented that CloudSim 2 toolkit that allowed us to test and analyze
scheduling algorithms. This paper used CloudSim version 3.0 for testing and
analyzing the scheduling policies in cloud environment. This paper also
described that how we can allocate cloudlet to virtual machine. Brief study of
datacenter broker and hosts were also discussed.

 

In 6, authors
compared the performance of scheduling algorithms. The algorithms were Round
Robin (RR), Random Resource Selection (RRS), Opportunistic Load Balancing (OLB)
and Minimum Completion Time (MCT). Several experiments were carried out against
4 algorithms. They calculated the make span, average execution time and degree
of imbalance in scheduling algorithms.

 

In 4,
authors recommended Max-min algorithm for task scheduling to balance the load
of cloud. The recommended algorithm preserves a task position table to evaluate
the real time workload of VMs and predictable execution time of tasks. The
simulation outcomes express that Max-min algorithm increases the utilization of
resource and reduces the response time for task scheduling.

 

In 8,
authors proposed a new
scheduling algorithm SJF (shortest-job-first) to minimize the waiting time, make
span and maximize resource utilization in cloud environment. Experiment was carried out in CloudSim. Results are then compared with existing
algorithms 8. Results showed that as compared with existing task scheduling algorithms,
shortest job first algorithm waiting time and processing time was decreased.

 

In 12, authors presented the
First Come First Serve (FCFS) for improvement of time efficiency of cloud
environment. They examined the following parameters like task loss ratio and
cpu utilization. In this paper they presented an improved FCFS algorithm.
Experiments were carried out in FCFS and an improved FCFS algorithm. Results
showed that time efficiency of improved version of FCFS 12 was much better
than simple FCFS.

 

In 7, authors presented six rule based
heuristic algorithms 12 that were implemented and used to schedule tasks in homogeneous
and heterogeneous environment. First Come First Serve (FCFS), Minimum
Completion Time (MCT), Minimum Execution Time (MET), Max-min, Min-min and
Sufferage were the heuristic algorithms considered for analysis and comparison of
performance of task scheduling in cloud computing. They compared performance in
terms of cost, degree of imbalance, makespan and throughput.

 

3.     
Scheduling
Algorithms

 

The main motive
of task scheduling algorithms in cloud computing 1 system is distributing the
load on processors and maximizing resource utilization while minimizing time.

 

 

Task Scheduling 1 in cloud computing has three steps –

 

1.     
Resource Information:  Broker in CloudSim 2 selects the resources
availability in the cloud computing environment and also collects the
status information of resources.

 

2.     
Resource allocation:  Required resource is allocated on the basis of the parameters of Cloudlet
and resource.

3.     
Task submission: Finally,
Cloudlet 2 is assigned to allocated resource.

 

In this study we
are discussing four scheduling algorithms. These algorithms are used to
schedule tasks in cloud environment. Each algorithm has its own benefits in task
scheduling. The aim of scheduling algorithms is to maximize resource
utilization and minimize execution time of tasks.

For more
understanding of scheduling algorithms, below is the brief description of each
algorithm.

 

FCFS 5 algorithm uses set of
un-scheduled cloudlets. FCFS 5 executes tasks by the order of their arrival. FCFS
5 will assign task to VMs on the basis of their arrival. It is based on FIFO
mechanism. By default CloudSim 2 has FCFS algorithm for scheduling the
cloudlets on virtual machines.

 

Min-min 5 algorithm uses a set of
un-scheduled cloudlets and then calculate the minimum completion times for each
cloudlet on all virtual machines 2. The cloudlet with minimum completion time
5 is chosen and scheduled on virtual machine which gives minimum completion time. The
scheduled cloudlet is then removed from cloudlet list and the procedure is
repeated until the all un-scheduled cloudlets are not scheduled.

 

Similar to the Min-min algorithm, after
determining the completion times for each cloudlet on all virtual machines, the
cloudlet with maximum completion time 5 is scheduled on virtual machine which
gives minimum completion time. In case of max-min 5, the process is repeated
until all the cloudlets 2 are scheduled. In Min-min algorithm 5, the
purpose is that tasks are scheduled on machine that execute them earliest and
fastest so that smaller execution time will be obtained. Max-min 5 algorithm
is usually used in a situation where there are fewer longer and shorter
cloudlets. It will enable the longer cloudlets to be scheduled along with shorter
cloudlets.

 

Another approach of scheduling is the shortest job first (SJF) 5
scheduling algorithm. Shortest job first will select the smaller job first.  Shortest job first associates with each
process (length of the cloudlet). It will choose the shortest length cloudlet
2 and then scheduled on virtual machine. If lengths of two cloudlets are same,
FCFS 12
scheduling is used.

 

 

 

4.     
Experiments
and Discussions

 

Section 4.1 represents experimental setup like hardware, software
and environment related information used to compare the throughput 11, total
execution time 6 and average resource utilization 1 of scheduling
algorithms. Throughput 11 can be defined as number of jobs per second. Total
execution time 6 can be defined as completion time of all the cloudlets.
Average resource utilization 1 can be defined as how much resources are
utilized in execution process of all cloudlets.

 

 4.1. Experimental Setup

 

Table 1 represents
the hardware and software related information. Software related information
includes operating system (Windows 8.1), system type (64 bits) and CloudSim api
version (3.0). Hardware includes CPU (intel i3) and RAM (4 GB).

                                                                                                             

 

                                                            Table 1: Machine information.

 

            CPU

                   
Intel i3

            RAM

                   
4 GB

            Operating System

                Windows
8.1

            System type

                   
64 bits

            CloudSim Api

3.0 version

 

 

                                   

           

Table 2 represents the environmental setup
used in this experiment. Environmental setup includes number of virtual
machines (50) , number of cloudlets (1000), number of datacenters (1), number
of hosts (2) ,ram required for each VM (512 MB), MI of cloudlets and MIPS of
VMs.

 

                             

   Table
2: Environmental Setup

            Number of VMs

                   50

            Number of Cloudlets

                   1000

            Number of Datacenters

                    1

            Number of Hosts

                    2

            RAM required for VM

512 (MB)

            MI of cloudlets

      small, medium, large

            MIPS of VMs

                    <5000                                             4.2. Dataset   Figure 1 represents the dataset information related to cloudlet. In Figure 1, small represents cloudlet length range 0-250 MI, medium represents cloudlet length 250-5000 MI and large represents cloudlet length range 5000-15000 MI.                                                                 Figure 1: Dataset Information       4.3. Experimental Results   This paper compares performance of FCFS, SJF, Min-min and Max-min. The main purpose of this experiment is to evaluate and compare throughput, total execution time and average resource utilization 1 in FCFS, SJF, Min-min and Max-min algorithm 12.   In this experiment the length of cloudlets is heterogeneous, Millions of Instructions Per second (MIPS) of virtual machines is also heterogeneous. The parameters of this experiments are listed in Table 2.     4.3.1.      Throughput                                                                          Figure 2: Throughput analysis.   Figure 2 shows throughput related results of FCFS, SJF, Min-min and Max-min algorithm. Shortest job first algorithm has throughput (45.9) which is 25% higher than FCFS throughput (34.36), 29% higher than Min-min throughput (32.72) and 30% higher than Max-min throughput (31.67). The results clearly indicate that Max-min algorithm has minimum throughput than FCFS, SJF, Min-min and Max-min.                                     4.3.2.      Total Execution Time                                                                                                                                     Figure 3: Total Execution Time analysis     Figure 3 shows total execution time related results of all cloudlets on FCFS, SJF, Min-min and Max-min algorithm. Total Execution Time can be defined as total of completion time of all cloudlets.  Max-min algorithm takes 25% less total execution time than SJF, 5% less execution time than FCFS and 1 % less execution time than Min-min algorithm. The results clearly indicate that Max-min algorithm has good scheduling policy than FCFS, SJF, Min-min and Max-min.                       4.3.3.      Average Resource Utilization                                                     Figure 4: Average Resource Utilization   Figure 4 shows results related to average resource utilization 1 while executing all cloudlets on FCFS, SJF, Min-min and Max-min algorithm 12. Average resource utilization 1 can be defined as total resources utilized while execution of all cloudlets 2. Shortest job first algorithm has 10.4% higher average resource utilization than FCFS, 10.19% higher average resource utilization than Min-min and 13% higher average resource utilization than Min-min algorithm. SJF algorithm in term of average resource utilization is better than FCFS, Min-min and Max-min.                                                                                                  5.      Conclusions   Scheduling is one of the most important aspect in cloud computing environment. The aim of task scheduling is to respond millions of service requests and make efficient use of available resources and also satisfying both users as well as service providers. In this paper total execution time, throughput and average resource utilization are calculated against FCFS, SJF, Min-min and Max-min task scheduling algorithms. Experimental results are concluded from a set of 1000 cloudlets and 50 virtual machines. Efficient algorithm have three qualities (1 minimum execution time (2 minimum throughput (3 maximum resource utilization. From above results we conclude that in terms of throughput and total execution time, Max-min algorithm performs better than FCFS, SJF, Min-min algorithm. If we see in terms of average resource utilization, SJF algorithm performs better than FCFS, Min-min and Max-min algorithm. From above study we recommend that if we want minimum execution time and minimum throughput, Max-min algorithm will perform well.             References   1 Beloglazov, Anton, Jemal Abawajy, and Rajkumar Buyya. "Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing." Future generation computer systems 28.5 (2012): 755-768.R. Buyya, C.S. Yeo, S. Venugopal, J. Broberg, I. Brandic, Cloud Computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility. Future Generation Computer System.25, 599–616; 2009. 2 Calheiros, Rodrigo N., et al. "CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms." Software: Practice and experience 41.1 (2011): 23-50. 3 Chen, Quan, and Qian-ni Deng. "Cloud computing and its key techniques J." Journal of Computer Applications 9 (2009): 2563-2566. 4 Etminani, Kobra, and M. Naghibzadeh. "A min-min max-min selective algorihtm for grid task scheduling." Internet, 2007. ICI 2007. 3rd IEEE/IFIP International Conference in Central Asia on. IEEE, 2007. 5 Islam, Mir Salim Ul, and Bhawana Rana. "Task Scheduling in Cloud Computing."   International Journal of Advance Research, Ideas and Innovations in Technology 3.4 (2017): 642-646. 6 Mohialdeen, Isam Azawi. "Comparative study of scheduling al-gorithms in cloud computing environment." Journal of Computer Science 9.2 (2013): 252-263. 7 Madni, Syed Hamid Hussain, et al. "Performance comparison of heuristic algorithms for task scheduling in IaaS cloud computing environment." PloS one 12.5 (2017): e0176321. 8 Ru, Jia, and Jacky Keung. "An empirical investigation on the simulation of priority and shortest-job-first scheduling for cloud-based software systems." Software Engineering Conference (ASWEC), 2013 22nd Australian. IEEE, 2013. 9 Show, Durbar. Creation and Allocation of Virtual Machines for Execution of Cloudlets in Cloud Environment. Diss. 2014. 10 Salot, Pinal. "A survey of various scheduling algorithm in cloud computing environment."     International Journal of Research in Engineering and Technology 2.2 (2013): 131-135. 11 Topcuoglu, Haluk, Salim Hariri, and Min-you Wu. "Performance-effective and low-complexity task scheduling for heterogeneous computing." IEEE transactions on parallel and distributed systems 13.3 (2002): 260-274. 12 Zhao, Wei, and John A. Stankovic. "Performance analysis of FCFS and improved FCFS scheduling algorithms for dynamic real-time computer systems." Real Time Systems Symposium, 1989, Proceedings.. IEEE, 1989.