Types of Task Scheduling Algorithms in Cloud Computing Environment

Abstract

Cloud computing is one of the most important technologies used in recent times, it allows users (individuals and organizations) to access computing resources (software, hardware, and platform) as services remotely through the Internet. Cloud computing is distinguished from traditional computing paradigms by its scalability, adjustable costs, accessibility, reliability, and on-demand pay-as-you-go services. As cloud computing is serving millions of users simultaneously, it must have the ability to meet all users requests with high performance and guarantee of quality of service (QoS). Therefore, we need to implement an appropriate task scheduling algorithm to fairly and efficiently meet these requests. Task scheduling problem is the one of the most critical issues in cloud computing environment because cloud performance depends mainly on it. There are various types of scheduling algorithms; some of them are static scheduling algorithms that are considered suitable for small or medium scale cloud computing; and dynamic scheduling algorithms that are considered suitable for large scale cloud computing environments. In this research, we attempt to show the most popular three static task scheduling algorithms performance there are: first come first service (FCFS), short job first scheduling (SJF), MAX-MIN. The CloudSim simulator has been used to measure their impact on algorithm complexity, resource availability, total execution time (TET), total waiting time (TWT), and total finish time (TFT).

1. Introduction

Cloud computing is a new technology derived from grid computing and distributed computing and refers to using computing resources (hardware, software, and platforms) as a service and provided to beneficiaries on demand through the Internet [1]. It is the first technology that uses the concept of commercial implementation of computer science with public users [2]. It relies on sharing resources among users through the use of the virtualization technique. High performance can be provided by a cloud computing, based on distributing workloads across all resources fairly and effectively to get less waiting time, execution time, maximum throughput, and exploitation of resources effectively. Still, there are many challenges prevalent in cloud computing, Task scheduling and load balance are the biggest yet because it is considered the main factors that control other performance criteria such as availability, scalability, and power consumption.

2. Tasks scheduling algorithms overview

Tasks scheduling algorithms are defined as the mechanism used to select the resources to execute tasks to get less waiting and execution time.

2.1 Scheduling levels

In the cloud computing environment there are two levels of scheduling algorithms:

• First level: in host level where a set of policies to distribute VMs in host.

• Second level: in VM level where a set of policies to distribute tasks to VM.

In this research we focus on VM level to scheduling tasks, we selected task scheduling algorithms as a research field because it is the biggest challenge in cloud computing and the main factor that controls the performance criteria such as (execution time, response time, waiting time, network, bandwidth, services cost) for all tasks and controlling other factors that can affect performance such as power consumption, availability, scalability, storage capacity, buffer capacity, disk capacity, and number of users.

2.2 Tasks scheduling algorithms definition and advantages

Tasks scheduling algorithms are defined as a set of rules and policies used to assign tasks to the suitable resources (CPU, memory, and bandwidth) to get the highest level possible of performance and resources utilization.

2.2.1 Task scheduling algorithms advantages

• Manage cloud computing performance and QoS.

• Manage the memory and CPU.

• The good scheduling algorithms maximizing resources utilization while minimizing the total task execution time.

• Improving fairness for all tasks.

• Increasing the number of successfully completed tasks.

• Scheduling tasks on a real-time system.

• Achieving a high system throughput.

• Improving load balance.

2.3 Tasks scheduling algorithms classifications

Tasks scheduling algorithms classified as in Figure 1.

Figure 1.

Tasks scheduling classes.

2.3.1 Tasks scheduling algorithms can be classified as follows

• Immediate scheduling: when new tasks arrive, they are scheduled to VMs directly.

• Batch scheduling: tasks are grouped into a batch before being sent; this type is also called mapping events.

• Static scheduling: is considered very simple compared to dynamic scheduling; it is based on prior information of the global state of the system. It does not take into account the current state of VMs and then divides all traffic equivalently among all VMs in a similar manner such as round robin (RR) and random scheduling algorithms.

• Dynamic scheduling: takes into account the current state of VMs and does not require prior information of the global state of the system and distribute the tasks according to the capacity of all available VMs [4, 5, 6].

• Preemptive scheduling: each task is interrupted during execution and can be moved to another resource to complete execution [6].

• Non-preemptive scheduling: VMs are not re-allocated to new tasks until finishing execution of the scheduled task [6].

In this research, we focus on the static scheduling algorithms. Static scheduling algorithm such as first come first service (FCFS), shortest job first (SJF), and MAX-MAX scheduling algorithms in complexity and cost within a small or medium scale.

2.4 Task scheduling system in cloud computing

The task scheduling system in cloud computing passes through three levels [7].

• The first task level: is a set of tasks (Cloudlets) that is sent by cloud users, which are required for execution.

• The second scheduling level: is responsible for mapping tasks to suitable resources to get highest resource utilization with minimum makespan. The makespan is the overall completion time for all tasks from the beginning to the end [7].

• The third VMs level: is a set of (VMs) which are used to execute the tasks as in Figure 2.

Figure 2.

Task scheduling system.

2.5 This level passes through two steps

• The first step is discovering and filtering all the VMs that are presented in the system and collecting status information related to them by using a datacenter broker [8].

• In the second step a suitable VM is selected based on task properties [8].

3. Static tasks scheduling algorithms in cloud computing environment

3.1 FCFS

FCFS: the order of tasks in task list is based on their arriving time then assigned to VMs [3].

3.1.1 Advantages

• Most popular and simplest scheduling algorithm.

• Fairer than other simple scheduling algorithms.

• Depend on FIFO rule in scheduling task.

• Less complexity than other scheduling algorithms.

3.1.2 Disadvantages

• Tasks have high waiting time.

• Not give any priority to tasks. That means when we have large tasks in the begin tasks list, all tasks must wait a long time until the large tasks to finish.

• Resources are not consumed in an optimal manner.

• In order to measure the performance achieved by this method, we will be testing them and then measuring its impact on (fairness, ET, TWT, and TFT).

3.1.3 Assumptions

Some of the assumptions must be taken into account when scheduling tasks to VMs in the cloud computing environment.

• Number of tasks should be more than the number of VMs, which means that each VM must execute more than one task.

• Each task is assigned to only one VM resource.

• Lengths of tasks varying from small, medium, and large.

• Tasks are not interrupted once their executions start.

• VMs are independent in terms of resources and control.

• The available VMs are of exclusive usage and cannot be shared among different tasks. It means that the VMs cannot consider other tasks until the completion of the current tasks is in progress [3].

Tasks lengths: assume we have 15 tasks with their lengths as in Table 1.

Table 1.

Set of tasks with different length orders depends on the arrival time for each task.

3.1.4 VM properties

Assume we have six VMs with different properties based on tasks size:

$$\mathrm{VM}\text{list}=\left\{\text{VM1},\text{VM2},\text{VM3},\text{VM4},\text{VM5},\text{VM6}\right\}.$$

$$\text{MIPS of}\mathrm{VM}\text{list}=\left\{500,500,1500,1500,2500,2500\right\}.$$

We selected a set of VMs with different properties to make each category have VMs with appropriate ability to serve a specific class of tasks, to improve the load balance. Because when we use VMs with same properties with all categories it leads to load imbalance, where each class is different from other classes in terms of tasks lengths.

3.1.5 When applying FCFS, work mechanism will be as following

Figure 3 shows FCFS tasks scheduling algorithm working mechanism and how tasks are executed based on their arrival time.

Figure 3.

FCFS work mechanism.

Dot arrows refer to first set of tasks scheduling based on their arrival time.

Dash arrows refer to second set of tasks scheduling based on their arrival time.

Solid arrows refer to third set of tasks scheduling based on their arrival time.

And here it is clear to us that t1 is too large compared with t7 and t12. However, t7 and t12 must wait for t1, which leads to an increase in the TWT, ET, TFT, and a decrease in fairness.

$$\text{VM1}=\left\{\mathrm{t}1⟶\mathrm{t}7⟶\mathrm{t}12\right\}.$$

$$\text{VM2}=\left\{\mathrm{t}2⟶\text{t8}⟶\mathrm{t}14\right\}.$$

$$\text{VM3}=\left\{\mathrm{t}3⟶\mathrm{t}9⟶\mathrm{t}15\right\}.$$

$$\text{VM4}=\left\{\mathrm{t}4⟶\mathrm{t}10\right\}.$$

$$\text{VM5}=\left\{\mathrm{t}5⟶\mathrm{t}11\right\}.$$

$$\text{VM6}=\left\{\mathrm{t}6⟶\mathrm{t}13\right\}.$$

Table 2 shows how FCFS scheduling algorithm increases waiting time for all tasks.

Table 2.

Waiting times of tasks in FCFS.

3.2 SJF

Tasks are sorted based on their priority. Priority is given to tasks based on tasks lengths and begins from (smallest task ≡ highest priority).

3.2.1 Advantages

• Wait time is lower than FCFS.

• SJF has minimum average waiting time among all tasks scheduling algorithms.

3.2.2 Disadvantages

• Unfairness to some tasks when tasks are assigned to VM, due to the long tasks tending to be left waiting in the task list while small tasks are assigned to VM.

• Taking long execution time and TFT.

3.2.3 SJF work mechanism

When applying SJF, work mechanism will be as follows:

Assume we have 15 tasks as in Table 1 above. We will be sorting tasks in the task list, as in Table 3. Tasks are sorted from smallest task to largest task based on their lengths as in Table 3, then assigned to VMs list sequential.

Table 3.

A set of tasks sorted based on SJF scheduling algorithm.

3.2.4 Execute tasks will be

$$\text{VM1}=\left\{\mathrm{t}4⟶\text{t6}⟶\text{t7}\right\}.$$

$$\text{VM2}=\left\{\mathrm{t}10⟶\text{t9}⟶\text{t1}\right\}.$$

$$\text{VM3}=\left\{\mathrm{t}11⟶\mathrm{t}13⟶\text{t8}\right\}.$$

$$\text{VM4}=\left\{\mathrm{t}5⟶\mathrm{t}14\right\}.$$

$$\text{VM5}=\left\{\mathrm{t}12⟶\text{t2}\right\}.$$

$$\text{VM6}=\left\{\mathrm{t}3⟶\mathrm{t}15\right\}.$$

Table 4 shows that the large tasks must be waiting in the task list until the smallest tasks finish execution.

Table 4.

Waiting times of tasks in SJF.

3.3 MAX-MIN

In MAX-MIN tasks are sorted based on the completion time of tasks; long tasks that take more completion time have the highest priority. Then assigned to the VM with minimum overall execution time in VMs list.

3.3.1. Advantages

• Working to exploit the available resources in an efficient manner.

• This algorithm has better performance than the FCFS, SJF, and MIN-MIN algorithm.

3.3.2 Disadvantages

• Increase waiting time to small and medium tasks; if we have six long tasks, in MAX-MIN scheduling algorithm they will take priority in six VMs in VM list, and short tasks must be waiting until the large tasks finish.

Unfairness to some or most small and medium tasks when tasks are assigned to VM.

• When applying MAX-MIN, Work Mechanism will be as follows.

Assume we have 15 tasks as in Table 1 above. We will be sorting tasks in task list as in Table 5. Tasks sorted from largest task to smallest task based on highest completion time. They are then assigned to the VMs with minimum overall execution time in VMs list.

Table 5.

A set of tasks sorted based on MAX-MIN scheduling algorithm.

3.3.3 Execute tasks will be

$$\text{VM6}=\left\{\mathrm{t}1⟶\mathrm{t}13⟶\mathrm{t}11\right\}.$$

$$\text{VM5}=\left\{\mathrm{t}8⟶\text{t9}⟶\mathrm{t}10\right\}.$$

$$\text{VM4}=\left\{\mathrm{t}7⟶\mathrm{t}6⟶\text{t4}\right\}.$$

$$\text{VM3}=\left\{\mathrm{t}15⟶\text{t3}\right\}.$$

$$\text{VM2}=\left\{\mathrm{t}2⟶\mathrm{t}12\right\}.$$

$$\text{VM1}=\left\{\mathrm{t}14⟶\text{t5}\right\}.$$

Tables 6 and 7 shows that the small and medium tasks must be waiting in the task list until the large tasks finish execution.

Table 6.

Waiting time of tasks in MIX-MIN scheduling algorithm.

	FCFS	SJF	MAX-MIN
TWT	739.19	79.59	404
TFT	1969.69	678.69	968.698

Table 7.

Comparison between FCFS tasks scheduling algorithm, SJF, and MAX-MIN in terms of TWT and TFT.

Figure 4 shows the TWT and TFT for the three tasks scheduling algorithms FCFS, SJF, and MAX-MIN. SJF tasks scheduling algorithm is the best in term of TWT and TFT.

Figure 4.

Comparison between FCFS tasks scheduling algorithm, SJF, and MAX-MIN in terms of TWT and TFT.

4. Conclusion

This chapter introduces the meaning of the tasks scheduling algorithms and types of static and dynamic scheduling algorithms in cloud computing environment. This chapter also introduces a comparative study between the static task scheduling algorithms in a cloud computing environment such as FCFS, SJF, and MAX-MIN, in terms of TWT, TFT, fairness between tasks, and when becoming suitable to use?

Experimentation was executed on CloudSim, which is used for modeling the different tasks scheduling algorithms.