Information Technology And Quantitative Management Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Quality of Service is an inevitable issue needing to be deal with in task scheduling of cloud computing. This paper proposes a task scheduling algorithm based on QoS-driven for cloud computing. Firstly, in order to reflect the precedence relation of tasks, the proposed algorithm computes the priority of tasks according to the special attributes of tasks, and then sorts tasks by priority. Secondly, the algorithm evaluates the completion time of each task on different services, and schedules each task onto a service which can complete the task as soon as possible according to the sorted task queue. The experimental results based on CloudSim show that the algorithm can achieve good performance and load balancing by QoS driving from both priority and completion time.

Keywords: Cloud computing; Task scheduling; Quality of service; Priority

Introduction

Cloud computing is a new mode of business computing, and it promises to provide reliable services through "Cloud" centers built on virtualized computing and storage technologies [1]. From a "Cloud" anywhere in the world, users can gain computing power, storage and a variety of software services by using a variety of applications, and pay based on what they use. It is a key issue how to dispatch efficiently and reasonably tasks of users to different resources according to the Quality of Service (QoS) requirements of both Cloud Computing Center and users, which belongs to task scheduling.

However, the scheduling of applications for parallel and distributed computing systems is one of the most challenging NP-complete problems [2]. Currently the NP-completeness of the scheduling problem has inspired researchers to propose numerous heuristic algorithms, such as Min-Min, GA, SA, A*, etc [3]. Many improved algorithms [4, 5] based on existed algorithms are proposed to meet the requirement of environments.

QoS is the collective effort of service performance, which determines the degree of satisfaction of a user for the service [6]. Commonly, QoS is expressed by the following qualitative measures, such as completion time, latency, execution price, packet loss rate, throughput and reliability.

In order to meet the QoS of cloud computing, the paper [7] proposed a job scheduling algorithm based on Berger model. The algorithm establishes dual fairness constraint. Firstly it classifies tasks by QoS preferences, and establishes the general expectation function in accordance with the classification of tasks. Secondly it defines resource fairness justice function to judge the fairness of the resources allocation. According to constraints, the algorithm always assigns tasks onto the optimal resources in order to satisfy the QoS requirements of users. In paper [8], a reliability-driven scheduling architecture was designed to meet task dependency applications' reliability requirements. A reliability priority rank (RRank) was introduced to estimate task's priority by considering reliability overheads. Furthermore, based on directed acyclic graph (DAG), a scheduling algorithm with duplication for precedence constrained tasks was proposed to achieve reliability for applications. Paper [9] presented slot selection algorithms in economic models for independent job batch scheduling in distributed computing with non-dedicated resources. It divided the scheduling of the job batch into two phases. With an eye to efficiency and economic policy, a scheduling scheme that features multi-variant search was built. In order to maximize resource utilization and acceptance of leases for the infrastructure as a Service (IaaS) clouds, paper [10] provided a scheduling algorithm to support deadline sensitive leases in Haizea to minimize request rejection rate while satisfying resource allocation policies offered by cloud provider.

This paper proposes a task scheduling algorithm based on QoS-driven in Cloud Computing (TS-QoS). The TS-QoS computes the task priority according to attributes of task such as user privilege, the priority expectation to be scheduled, task lengthen and the pending time of task in queue. Then tasks are sorted by the priority. And in the scheduling process, each task is assigned onto the service with the minimum completed time over all available services.

The rest of the paper is organized as follows: Section 2 gives related works. Section 3 gives detailed description of the TS-QoS. Section 4 describes the simulation experiment and experiment analysis. Section 5 gives the conclusions.

Task scheduling Model

In order to adapt to the parallel and distributed cloud computing environment and deal with QoS scheduling, we adopt the dynamic batching mode. In this mode, tasks are not mapped onto services as they arrive; instead they are collected in a set that is examined for mapping. And according to the collected information including the requirements of all tasks and the real-time state of all services, we can design more reasonable scheduling strategy to deal with QoS.

In this paper, we deal with QoS scheduling based on following strategies: (1) the task owned higher priority should be scheduled prior to tasks with lower priority; (2) a task should be completed as soon as possible.

The service description

In cloud computing, resources are encapsulated into services. Supposing a service set is denoted as Service(m), then, Service(m) = {S1, S2, S3,…, Sj, …, Sm}. Where, m∈N, N is a natural number, and Sj∈Service(m), j∈[1, m]. Then, we define a service Sj by a multi-tuple as follows:

Sj = {SID, SProvider, SServicename, SAbility}

Where, each attribute of service Sj is described as follows:

(1) SID is ID of Sj;

(2) SProvider is the provider of Sj;

(3) SServicename exposes name of service and method of service, etc;

(4) SAbility is service ability of Sj, which mainly includes computing power, communication bandwidth and storage capacity. We set SAbility = {processor, bandwidth, storage}.

The task description

Task is medium or container that expresses or holds requirements of users. Generally task has been classified into the independent meta-task and the dependent task. Here, we only discuss meta-task. Supposing a meta-task set is denoted as Task(n), then, Task(n) = {T1 , T2 , T3 ,…, Ti,…, Tn}. Where, n∈N, N is a natural number, and Ti∈Task(n), i∈[1, n]. Then, we define a meta-task Ti by a multi-tuple as follows:

Ti={TID, TUserType, TServType, TPriorExp, TAbilReq, TL, TArriTime, TState, TData}

Next is a detailed account of meta-task Ti.

(1) TID is ID of meta-task Ti;

(2) TUserType stands by the privilege class of owner of Ti. Referring to the commercial mode, we set TUserType∈{A, B, C};

(3) TServType denotes the expected services of task Ti;

(4) TPriorExp is the expected scheduled priority of Ti, which shows the urgency of task Ti to be scheduled. Expected scheduled priority includes urgent priority, high priority, middle priority and low priority. So, we set TPriorExp∈{urgent, high, mid, low};

(5) TAbilReq denotes the service ability expectation to execute task Ti. Responding to the service definition, we set TAbilReq = {processor, bandwidth, storage};

(6) TL is the task length of task Ti. Here we assume TL is the number of instructions that the loop unrolled contained in task Ti. And it shows the computing workload of the task;

(7) TArriTime is the submitted time of task Ti;

(8) TState is the current state of task Ti, including idle, suspending, mapping, executing and completed;

(9) TData is the input data and output data, which would be stored into files.

From the definition of task, we can see that tasks maybe focus on computing, or communication, or storage, or their combination. In next section, we only discuss the computing task.

The priority computation of tasks

The priority is a comprehensive concept. Here, we estimate and calculate priority of tasks through user privileges, the urgency that tasks are scheduled, and the latency time queuing up and the task workload.

According to the task description, the user privilege corresponds to TUserType, the urgency that tasks are scheduled matches TPriorExp. Here, we just discuss the computing workload about task workload, so we denote the task workload as TL. And the latency time (LT) queuing up can be calculated by the current time and TArriTime. After introducing LT into priority of the task, the priority can change dynamically and increase continuously. This can solve "starving to death" issue, and follow the "first come first served" principle.

The priority is a hybrid concept which involves many attributes of task. In order to merge attributes into priority, we apply a normalization concept. Normalization can speed up data convergence by converting and mapping data within a certain range, and convert a dimensional data into a non-dimensional data. And it can dispel the adverse effect on the hybrid priority because of a wide difference among values of different attributes. Here, we use linear conversion, the formula is as follows.

(1)

where,Yi is the normalization result of special attribute of task Ti; xi is the value of special attribute of task Ti; MaxValue and MinValue are the maximum and minimum value of special attribute from all tasks waiting to be scheduled respectively.

According to the above normalized attributes of tasks, we calculate the priority of tasks as follows.

(2)

Where, P(i) is the priority of task Ti.are weights of priority, and . Of course, it would have different impact on task priority by adjusting weights. NTUi, NTPi NTLi, NLTi are the normalization for TUserType, TPriorExp, TL, LT of task Ti respectively.

The service selection for completion time

It can reduce the completion time of tasks to complete tasks as soon as possible. Of course, to reduce the completion time of a task would shorten latency of the remainder tasks in queue. In order to carry out the strategy, we need to compute the completion time of each task on different services in the scheduling process. And some terminologies about the completion time are described as follows [10].

Definition 1. The expected execution time of task Ti is the amount of time taken by service Sj to execute Ti given that Sj has no load when Ti is assigned.

Definition 2. The expected time to computed (ETC) matrix is a matrix that is stored on the scheduling system where the mapping is stored, and contains the estimates for the expected execution times of all tasks on all services. In an ETC matrix, the elements along a row indicate the estimates of the expected execution times of a given task on different services, and those along a column give the estimates of the expected execution times of different tasks on a given service. Where the entry(i,j) is the expected execution time of task Ti on service Sj, and we can denotes it as ETC(i,j).

Definition 3. The start time (ST) matrix is a matrix that is stored on the scheduling system, and it contains the estimates for the earliest time that can be used for services after these services have executed and completed tasks allocated on. Where the entry(j) is the start time of service Sj, and we can denotes it as ST(j).

Definition 4. The minimum completion time (MCT) matrix is a matrix that is stored on the scheduling system where the mapping is stored, and contains the estimates for the expected completion times of all tasks on all services. In an MCT matrix, the elements along a row indicate the estimates of the expected completion times of a given task on different services, and those along a column give the estimates of the expected completion times of different tasks on a given service. Where the entry(i,j) is the expected completion time of task Ti on service Sj, and we can denotes it as MCT(i,j). And the formulation of MCT(i,j) is as follows:

(3)

From the above terminologies, we can see that the element MCT(i,j) in an MCT matrix records the total expected completion times of different tasks on a given service Sj. In fact, the total completion time of each service is the computing load of the service. That is to say, the greater the value for the element MCT(i,j), the heavier the load of service Sj. Load balancing is a very important metric of task scheduling, which impacts on fairness and efficiency of the system.

To schedule each task onto a service which has the minimum value of MCT(i,j), in that way, tasks would be completed as soon as possible. That is to say, it can help to reduce the completion time of tasks and achieve well load balancing.

The TS-QoS scheduling algorithm

Based on the above definitions and methods, the idea of TS-QoS algorithm is as follows: firstly, to compute the priority of tasks based on their normalized attributes in order to reveal the difference of tasks; then, to sort and schedule tasks by their priority; in order to reduce the completion time, in the scheduling process, to set and update MCT matrix by computing the completion time of each task on different services, and search the minimum element value for each task in the row of updating MCT matrix, then, record the special service relating to the minimum element value in the matrix; finally, to schedule the task onto the special service. The process of TS-QoS algorithm is shown as follows.

Algorithm 1: the TS-QoS algorithm

Input: Task(n), Service(m);

Output: the scheduled list.

Begin

for task set Task(n)

{ quantify the value of special attributes for task Ti;

normalize the value of special attributes for task Ti according to the formula (1);

compute the priority of task Ti according to the formula (2);

}

sort task set Task(n) by the priority of tasks;

initialize ETC matrix and MCT matrix;

initialize the mapping list;

for the sorted task set Task(n)

{ for service set Service(m)

{ lookup for the minimum MCT(i,j) for task Ti;

record service Sj; // service Sj has minimum completion time

}

create a new mapping pairing (Ti, Sj) in the mapping list;

update MCT matrix;

delete task Ti from task set Task(n);

}

for the mapping list

{ schedule task Ti on service Sj according to the mapping pairing (Ti, Sj); }

End

Experimental Evaluation

Cloud computing is an open platform. And it consists of multiple distributed Data Centres. Data Centre constructs all kinds of resource pools by virtualizing physical resources, and encapsulates resources into services. Cloud users submit their requests through a variety of cloud applications established by cloud service providers. Subsequently user requests are formed tasks and are submitted to the Data Centre. And according to the scheduling strategies and the monitored state of resources, Data Centre schedules each task into the appropriate service.

To evaluate the proposed algorithm, we developed an extensive simulation platform based on CloudSim 2.1 to simulate cloud environment by creating Data Centre and many cloud users. We created Virtual Machines (VM) to provide cloud services by Data Centre, and create many cloud tasks based on the requests of users. Then, tasks are scheduled based on the scheduled algorithms. Here, we implement three task scheduling algorithms: the TS-QoS algorithm, the Min-Min algorithm [3] and the Berger model [7]. The machine running CloudSim is configured with Intel Pentium dual-core processor 2.66GHz, 4GB memory.

The evaluating metrics

In the experiments, we tested the above three algorithm using following common metrics: execution time span (Makespan), the average waiting time of long task (AverageLatency) and load balancing indexing (). The concepts of these metrics are as follows.

(1) Makespan is the length of the time interval beginning with the processing of the initial task and ending with the completion of the last required task. The Makespan is a characteristic of the scheduling algorithm. The smaller Makespan is, the better the performance of algorithm is.

(2) AverageLatency is measured by the ratio of the total waiting time of all long tasks and the number of all long tasks.

(3) is a metric that measures whether a system is well load balancing. is measured by the standard deviation of load of all nodes. The smaller is, the better load balancing is. The formula of is as follows:

(4)

Where, nN is the number of computing nodes, N is a natural number; Xi is the load of the node i, and is the average load of all nodes. In next experiments, a node is a virtual machine.

Simulation setup

In simulation experiments, we test above metrics for three algorithms with 200~2000 tasks in 50 or 100 virtual machines respectively. The simulated parameters are set as follows.

(1) To set virtual machines according to the description in section 2.1. Where, processor is limited in [500, 600]; bandwidth is limited in [5, 10]; storage is limited in [500, 1000];

(2) To create tasks according to the description in section 2.2. Where, long tasks account for 10% of all tasks. And the size of long tasks is limited in [40000, 60000], the size of common tasks is limited in [10000, 20000]. In all tasks, the A class task account for 10%, the B class task is 20%, the C class task is 70%. And we set the expectation of tasks as follows: processor is limited in [400, 800], bandwidth is limited in [4, 8], storage is limited in [400, 800].

(3) To quantify attributes TUserType and TPriorExp of task as follows, set TUserType∈{1.2, 1.1, 1.0}; TPriorExp∈{1.3, 1.2, 1.1, 1.0}.

(4) To set priority weights as follows: =0.4, =0.3, =0.2, =0.1.

Experiments and results analysis

3.3.1 Effect of Makespan

Under the same environment, the tested averages of Makespan of three algorithms for 10 times with 200~2400 tasks in 50 or 100 virtual machines are illustrated in Fig 1.

Fig. 1. (a) The tested averages of Makespan using 50VM (b) The tested averages of Makespan using 100VM

Fig 1 shows that, the Makespan in the Berger model is higher than that of the TS-QoS and the Min-Min. It is because the Berger model always assigns tasks onto the optimal resources in order to satisfy the user requirements for QoS absolutely. This leads that all the tasks were accumulated on few optimal resources. It makes Makespan greater. The Makespan in the TS-QoS is similar as that of the Min-Min algorithm, because both have same time complexity of O(n2Ã-m) if there are n tasks and m resources. Also, it can be shown that the Makespan is reducing with the increase of virtual machines (VM) for the same number of tasks.

3.3.2 Effect of AverageLatency

Under the same environment, the tested averages of AverageLatency of three algorithms for 10 times with 200~2400 tasks in 50 or 100 virtual machines are shown in Fig 2.

Fig. 2. (a) The tested averages of AverageLatency using 50VM (b) The tested averages of AverageLatency using 100VM

Fig 2 shows that, the AverageLatency in the Berger model is the highest because of its scheduling strategy and lacking of consideration for long tasks. Compared with the Min-Min, the TS-QoS has lower AverageLatency. This is because that the length of task has been introduced into the priority, and then long tasks have higher priority and are scheduled earlier. Lower AverageLatency helps to reduce Makespan.

3.3.3 Effect of load balancing indexing

Under the same environment, the tested averages of of three algorithms for 10 times with 200~2400 tasks in 50 or 100 virtual machines are illustrated in Fig 3.

Fig. 3. (a) The tested averages of load balancing using 50VM (b) The tested averages of load balancing using 100VM

Fig 3 shows that in the Berger model is the highest because all the tasks were accumulated on the few optimal resources according to its scheduling strategy. This cause the few optimal resources had the highest load, and the system is load imbalance. And in the TS-QoS is lower than that of the Min-Min algorithm. This is because that the TS-QoS algorithm assigns each task onto services which have the minimum completion time in the process of scheduling. In additional, the long tasks have higher priority and are scheduled earlier, which avoids worsening load balancing. Also, it shows that is reducing with the increase of virtual machines (VM) for the same number of tasks.

Conclusions

In this paper, we propose a task scheduling algorithm based on QoS-driven in Cloud Computing. The proposed algorithm blends many task attributes including user privilege, expectation, task length and the pending time in queue to compute the priority and sorts tasks by the priority. And the algorithm schedules each task onto a service which has minimum completion time. The experimental results show that the algorithm achieves well performance and load balancing by QoS driving from both priority and completion time.

Acknowledgements

The authors would like to thank the support by the Foundation of Science and Technology on Communication Security Laboratory (9140C110404110C1106), the GuangXi National Natural Science Foundation of China (2012GXNSFAA053224), the Guangxi Graduate Education Innovation project of China (2010105950810M18), and the Foundation of Guangxi Department of Education (201010LX156,CD10066X).

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.