Dynamic Fair Priority Optimization Task Scheduling Algorithm in Cloud Computing: Concepts and Implementations

Computational world is very broad and complex. In this respect, cloud computing has undertaken almost entire space. Basically, cloud is a collection of resources (hardware and software) distributed at worldwide datacenters. There are many servers available at various datacenters which are provided by service providers throughout the world. We are paying as per our demand for using those resources. There are many popular issues for research in cloud computing like virtualization, data security, license management, scalable storage management, mobile cloud, availability of services, task scheduling. But, scheduling of job is always a prime topic of research in cloud computing. There are heterogeneous resources available at various datacenters. So, traditional scheduling algorithms like FCFS, shortest job first, round-robin and priority etc, are not recommendable. The various challenges of task scheduling in cloud environment are:

• 1)    To allocate resources to task

• 2)    To decide in which order the cloud should execute the task

• 3)    To schedule overhead when VMs prepare, terminate or switch task, communication overhead should be minimum.

• 4)    It requires continuous VM status monitoring.

• 5)    Cost of using VMs, dispatching VMs to different tasks etc.

Since scheduling world is very dynamic, heterogeneous and complex in cloud computing, we require some efficient scheduling technique that can optimize and improve the overall performance of scheduling system. Scheduling technique should be such that can do well and provide complete satisfaction at user end, at service provider end and also load balancing at system end.

Fig.1. Scheduling in Cloud

In cloud computing, scheduling of task is done at two levels:

• 1)    Resource level scheduling, deployment of VMs at available physical nodes is done

• 2)    User level scheduling, tasks are assigned to VMs

Customer put QoS constraints like minimum cost and task done faster etc. CSP (Cloud Service Provider) requires maximum returns on investment. At system level, maximum resource utilization and load balancing is required. In cloud computing, Broker acts as an intermediator between user and CSP. Broker exists (as shown in fig.1) at system level, the broker decides where to map job or task submitted by user to the resource provided by CSP [2]. So, while designing any new scheduling algorithm all the changes are performed at DCB (Data Center Broker). Likewise, many researchers have provided many scheduling algorithms, which are working well in one or the other way.

But our proposed scheduling algorithm for task scheduling is highly improved and efficient which is based on concept of “Weighted Fair Queuing” technique to improve quality of service. It has removed the drawbacks of already existing priority based task scheduling algorithms, i.e. starvation of low priority queues (long waiting priority queue). Now, with our proposed algorithm, there occur no long waiting priority queues. It provides fairness at priority level by implementing combination of priority queue and roundrobin fashion scheduling at grouped cloudlet level. This improved algorithm proves to be beneficial to all, (resource manager and load balancing) and satisfying QoS constraints at each level. The remainder of the paper is sectioned as follows: section 2 discusses literature review, section 3 discusses proposed methodology for cloudlet scheduling, section 4 discusses proposed algorithm, section 5 shows experimental data and results and finally section 6 concludes the overall study.

• II.    Related Works

Grouping task for scheduling after prioritization effectively reduces processing time in comparison to task scheduling without grouping. Cost of task scheduling is further reduced, if VM is selected dynamically on basis of cost and processing power [1]. Average turnaround time and average cost of overall task scheduling is minimized, when turnaround time and cost of each job is minimize individually. As a result, number of tasks increases, which improves the performance [2]. This paper has focused on grouping task, prioritization and greedy resource allocation. Criteria for calculating cost of every task must not be same, as some tasks are simple, some tasks are complex. Different task have different CPU requirement, memory requirement etc. So, activity based costing is better way of calculating cost of each task, which measures cost of objects and performance of activities and computes cost more accurately [3].Task execution cost can be reduced and user required QoS is improved using load balancing at resource level scheduling [4].ERUA algorithm [5] satisfy user and cloud service provider through dynamic resource management where utilization ratio must fall under 1, leading to better resource utilization. This paper focus at resource level scheduling. Processing each job individually increases communication cost and time. Because of this communication overhead overall performance of task scheduling increases. But, job-grouping technique groups the small scaled user jobs in job groups which reduces overhead communication time [6].

There are different levels of elasticity structures offered by different cases of data flow structures, operator characteristics and other parameters etc for data flow schedule optimization on cloud [7]. Multiple QoS constraints based scheduling strategy to address multiple workflows in a decentralized cloud computing environment including two level task scheduling mechanism based on load balancing in cloud computing[8].This task scheduling mechanism not only meet user’s requirements, but also get high resource utilization. Priority based dynamic resources allocation to tasks scheduling algorithm, which considers multiple SLA objective of job, by preempting best-effort job in cloud environment is described in [9].In paper [10], it has been discussed that hierarchical scheduler exploit the multicore architecture for effective scheduling They have used diversity of task priority at local and global level for proper load balancing across heterogeneous processors. TDP algorithm is there, where ‘T’ stands for task selection, ‘D’ for deadline and ‘P’ means priority in terms of cost, which selects task according to its constraints and requirements, finally scheduling is done using single priority queue [11].In heterogeneous environment of resources, the turnaround time of each job is minimized individually, to minimize the average turnaround time of all submitted jobs in a timeslot [12].

Though we have so many scheduling algorithms available, still some algorithm are better in one way or some are better in other way, none of them is completely efficient. Many algorithms make use of priority, but they all have disadvantage of long waiting queues. Generally, what happens in earlier proposed algorithms, they classify tasks as cost-based or deadline –based and then apply simple priority queues. In deadline-based grouping, task with higher deadline, having lower priority wait for longer duration for its execution, though it arrived so early. Also, in cost-based scheduling, the task with lesser execution cost (lower in priority) have to wait for longer duration for its execution. But, our proposed algorithm has included all good points of existing algorithms with new and enhanced version of priority that has surely remove the deficiency of all existing priority based task scheduling. We have added weighted fair queue to introduce priority of fairness in our proposed task scheduling algorithm.

The concept of “Weighted Fair Queue” is taken from the book William Stallings “High-Speed Networks and Internet, Performance and Quality of Service, Pearson education”, under the topic “Scheduling”, which is a Technique to improve QoS.

• III.    The Proposed Methodology

Our proposed scheduling method includes following concepts:

• (1)    Constraint-based grouping of tasks: - Grouping means collecting similar kind of tasks altogether in one dimension, all of them having same requirements. Task grouping can have many types like; grouping of tasks can be based on length of task, location of task, deadline of task, cost of task, complexity of task etc. Here, we have included twodimensional grouping of task. One dimension consist of constraint imposed by user i.e. Deadline based task grouping. Actually, almost every user wants his request to be met as earlier as possible, so applying deadline constraints over tasks will be quiet beneficial for user. Second dimension satisfy constraint of cloud service provider (CSP) which is, maximum resource utilization and earning maximum profit i.e. cost-based task grouping. From business point of view, applying cost-based constraint on tasks submitted by user will allow CSP to mend more money. As, CSP will his use minimum cost machine to execute maximum length task, so he is getting more money by utilizing benefit from minimum cost machine. Grouping of tasks certainly reduces communication overhead. For example, if 1000 tasks are given for execution, suppose 680 tasks are deadline-based and rests are cost-based. Then, to check for its constraint (deadline-based or cost-based) separately for each task at runtime would increase overhead for system. So, it is better to group them previously according to their constraints, before arranging them in different priority list.

• (2)    Weighted Fair Priority queue :- Among all the available scheduling methods, Weighted Fair Queue is best scheduling technique where tasks(cloudlets) are assign to different priority queues for scheduling. Weighted Fair Queue Model is shown in fig 2; in these queues are weighted based on priority of queue. Selected VM process task in each queue based on round-robin fashion where number of tasks selected for execution from each queue depends on its queue weight. For example, let weight assigned to high priority queue is 3, weight of mid queue is 2 and weight granted to low priority queue is 1.then at each cycle(round) 3 tasks are processed from high priority queue, 2 tasks from mid priority queue and 1 task is executed from low priority queue. In this way, tasks would be executed in round-robin fashion and priority fashion scheduling, both method goes together side-by-side. So, there will be no long waiting low priority queues.

• (3)    Greedy resource (VM) allocation : - This approach is greedy in respect that it selects resource, which

appears best at instant. It means scheduler or broker selects VM with minimum turnaround time for each individual task for deadline-based task scheduling. Minimizing turnaround time for each job will definitely reduce overall turnaround time and increase response time for all task taken together. This is a great enhancement regarding system performance, providing benefit at system level. For cost-based tasks, it selects VM with minimum cost and accurate processing power for cost-based tasks. The task with highest cost (which is decided based on task length) is assign to VM with minimum possible cost. This reduces cost of execution of each task. Here, cost refers to CSP‘s minimum cost machine is best utilized to execute the maximum length task of the user and providing maximum money benefit to him. So, he is spending less and earning more. During dynamic optimization, Greedy allocation of resource searches local optima and finally reaches global optima.

Continuous VM-status monitoring is done by calculating waiting time and then updating turnaround time of respective VM at each VM selection. Here, figure 3 is depicting the model of proposed algorithm, which is making use of weighted fair queue i.e. shown in figure 2.

Fig.2. Weighted Fair Queue Model

Making use of this best scheduling technique surely enhances the degree of multiprogramming by making each VM busy executing at least one task at a time, definitely CPU utilization increases and response time decreases for each task in particular. Hence, it is three way optimization technique, as user is getting his task executed faster and Cloud Service Provider is getting maximum benefit at cost of machine level. Also resource utilization i.e. VM utilization is at best promising level.

Fig.3. Proposed Algorithm Model

• IV.    Proposed Algorithm

Our proposed algorithm includes following steps:

User will submit number of cloudlets to DCB (Datacenter Broker), then random generator number will decide type of constraint for each task, so constraints are decided dynamically at runtime (they are not prefixed). Also, each task has different length which is changing by certain amount (for example, if length of previous task is 1000, then for next task it can be 1000 + 100* random generator number), length of task is also changing dynamically during execution. Deadline for each task is also decided using random generator number, so deadline is also not static. So, overall setup of experiment is truly dynamic which gives real view of practical situation in cloud computing:

• (1)    Make groups of tasks based on constraints (deadline or cost-based) classification.

• (2)    For deadline based task group, do:

• (i) . Arrange deadline based task in 3 priority queues – high, mid, low.

• (ii) . Take one task at a time from each priority queue, using weighted fair queue.

• (iii) . For each VM compute minimum turnaround time as, Turnaround time=waiting time + (task length/processing power). Also, calculate cost of task using formula cost of VM *(task length/

processing power). And update its waiting time accordingly.

• (iv) . For each task, select VM with minimum turnaround time, so that computation time of each task is reduced individually.

• (3)    For cost based task group, do:

• (i) . Arrange task in high, mid, low priority queues according to descending order of task length.

• (ii) . Apply weighted fair queue, and take one job at a time.

• (iii) . Compute total execution time of task execution using (start time of task execution – end time of task execution) Also, Compute cost of each VM using formula:

Cost = resource cost * (task length/processing power) and sort VM in descending order.

• (iv) . Assign task to minimum cost VM and task length<= MIPS of VM (so optimization is done at cost level).

Finally, to get combined results, sum up total execution cost of all task based on cost-based and deadline-based constraint together. Similarly, sum up total execution time of all task from both the groups.

Fig.4. Flowchart of Proposed Algorithm

• A. Pseudo code for our proposed algorithm is as follows:

It consists of three different modules namely, Schedule (), Deadline () and Cost ().

Schedule ()

For each task T i

If priority: = deadline

Then invoke Deadline (T i )

Else

If priority: = cost

Then invoke Cost (T i )

End

Deadline (A)

Add A to priority queue P

Sort P in ascending order of deadline

Divide the tasks into three priority queues High, Mid and Low

Select a task using Weighted Fair Queuing approach

Assign the task to the VM having minimum turnaround time.

Calculate time of execution and cost of execution of task.

Update the selected VM status

Cost (B)

Add B to priority queue Q

Sort Q in descending order of profit

Divide the tasks into three priority queues High, Mid and Low

Select a task using Weighted Fair Queuing approach

Assign the task to the VM having minimum cost of execution and length of task<= MIPS of VM. Calculate time of execution and cost of execution.

Update the selected VM status

At last, compute total cost and total time of execution of all task in both groupings together.

• V.    Experimental Data Analysis

The CloudSim toolkit is used demonstrate the simulation. The simulation results are verified using CloudSim (2.1.1) to check the correctness of proposed algorithm [2]. The simulation results of proposed algorithm are compared with the Sequential assignment, which is in-build in CloudSim and Dynamic Optimization Algorithm for Task scheduling [2].

The configuration of Datacenter created is as shown below,

Table I shows the configuration of hosts and Table II depicts the configuration of virtual machines used in this simulation framework.

Here,

Number of processing element - 1

Number of hosts – 2

Table 1. Configuration of Host

RAM (MB)	10240
Processing Power (MIPS)	110000
VM Scheduling	Time shared

Table 2. Configuration of Vms

Virtual Machine	VM1	VM2
RAM (MB)	5024	5024
Processing Powe (MIPS)	22000	11000
Processing Elements (CPU)	1	1

The configuration of the system on which these results are obtained is as shown below:

Table 3. System Configuration

Processor	Pentium® Dual-core CPU T4400@2.20GHz, 2.20GHz
RAM	3.00GB
System types	32bit operating system
Operating System	Windows 7 Ultimate

Performance with Time: - The experimental results show the remarkable improvement in time over the sequential approach as well as Dynamic Optimization Algorithm [2].

Table 4. Results of Proposed Algorithm and Existing Algorithm

No. of cloudlets	Sequential algorithm	Dynamic optimization without fair priority	Proposed algorithm with Fair Priority
20	98.6154	67.6984	45.3135
40	417.5499	283.441	235.2001
60	1041.3430	539.131	485.3890
80	1953.1897	885.0639	716.0989
100	3103.9777	1486.6538	1166.1269

Comparing proposed algorithm with sequential i.e. FCFS scheduling algorithm and Dynamic optimization scheduling algorithm [2] shows the tremendous improvement in results. As the number of cloudlets are increasing definitely, the total execution time has decreased together for both deadline and cost based tasks. The result shown above are the average of total execution time obtained after several number of execution for each number of cloudlet ( e.g. we have run the implementation 20 times for 100 cloudlets and calculated its average).

Performance with Cost: - The experimental results show the enhanced performance of proposed algorithm over existing algorithms.

Table 5. Results of Proposed Algorithm and Existing Algorithm

No. of cloudlets	Sequential algorithm	Dynamic optimization without fair priority	Proposed algorithm with Fair Priority
20	76.0	75.377	73.300
40	168.0	145.109	140.001
60	273.0	220.500	206.690
80	396.0	300.036	281.904
100	534	369.877	310.554

As the number of cloudlets are increasing the total execution cost has decreased together for both deadline and cost based tasks. The results shown above are the average of total execution cost obtained after several number of execution for each number of cloudlet (e.g. we have run the implementation 15 times for 100 cloudlets and calculated its average).

Fig.5. Traditional V/S Proposed Algorithm With Respect To Time

The above bar graph showing task completion time and comparison of traditional algorithm and proposed algorithm.

Fig.6. Cost Comparison Traditional V/S Proposed Algorithm With Respect To Cost

The above figure 6 depicts the information of task scheduling cost comparison of traditional algorithm with proposed algorithm.

The experimental results vary every time on running the simulation as the priorities of the incoming user tasks are not fixed, they are random for example, for 100 cloudlets, suppose at first execution, 40 tasks are cost based and rest are deadline-based, may be at next run of 100 task, 68 task are cost-based and rest are deadlinebased, so somewhat results vary, but each time results are improved as compared to sequential or dynamic optimized algorithm without fair priority. Also, simulation result varies depending upon the system configuration (for example, system type, RAM, processor version, and different OS) on which the simulation is running.

• VI.    Conclusions and Future Work

Scheduling of task in cloud environment is a highly researched and challenging issue in cloud computing. To meet thousand of service requests while making best possible use of available resources and simultaneously satisfying both user as well as service provider , is the challenge for task scheduler. Traditional methods of scheduling lead to overpricing and slow processing for bulk of tasks. Some task scheduling algorithm is cost based, some are deadline based and many algorithms make use of priority based scheduling. But they suffer from long waiting priority queues .Our proposed algorithm definitely meet all the challenges, along with constraint based optimization scheduling. We have also, introduced fair-priority scheduling concept i.e. combination of priority with round-robin scheduling scheme. This brings fairness at priority level and increases utilization of resources at system level and thereby providing much more efficient results than that can be provided by any other existing task scheduling algorithm.

In future, more pragmatic algorithm can be devised using several other combination of scheduling schemes like, Shortest Job First (SJF) with priority or SJF with weighted fair queue, or round-robin with SJF etc. Grouping of tasks can be done based on complexity of task, or group by location etc., before resource allocation.