Abstract
To deal with the problem of unbalanced load and ignoring task priority in previous task scheduling algorithms, this paper proposes a task scheduling algorithm named P-Min-Min-Max, which combines with priority and greedy strategy. Under the condition of considering the task priority, the algorithm leverages the execution time of tasks for greedy strategy, and binding large task and small task in the task list to form “task pair” to perform scheduling, so as to effectively solve the problem of unbalanced load. To reduce the average response time of tasks, the algorithm priority schedules the small task from the “task pair”. The experimental results show that, compared with the Min-Min and P-Min-Min algorithm, the proposed algorithm improves the system resource utilization and service quality of user, and saves the total execution time for tasks. Compared with Max-Min and P-Max-Min algorithm, the proposed algorithm improves the system resource utilization and service quality of user, and reduces the total completion time and average response time.
Introduction
Cloud computing [1, 2] has developed from technologies such as distributed computing and parallel computing. Its main idea is to automatically break down the large computing program into smaller subprograms via its network, and submit the tasks to multiple servers for processing and finally return the results to users. Cloud computing provides an on-demand service mode [3, 4], under which users do not need to purchase corresponding software and hardware resources and maintenance of software and hardware on a regular basis. Users can use the network to obtain the required software and hardware resources for the application and receive high-quality services at low prices as those of water and electricity. Depending on the type of service, the services provided by cloud computing can be classified into three types, namely, infrastructure as a service, platform as a service and software as a service [5, 6].
In cloud computing environment, the task scheduling is an important integral part of the cloud computing platform. Reasonable scheduling and optimized algorithm can significantly improve the quality of services provided to users, shorten the task completion time and improve resource utilization rate and load balance. In fact, task scheduling is to reasonably schedule multiple tasks to computer resources through certain strategy or algorithm under given conditions to meet users’ needs (which are usually defined as the quality of services provided to users).
In cloud computing environment, task scheduling is an NP-hard problem [7, 8] and its objective is to find the approximate optimal solution in the solution domain, and minimize the total task execution time and ensure load balance. In order to solve this problem, domestic and foreign researchers proposed many algorithms, including heuristic algorithms such as Min-Min [9], Max-Min [10] and Suffrage [11], intelligent task scheduling algorithms based on the bionics principle such as particle swarm optimization algorithm [12, 13], ant colony algorithm [14, 15], genetic algorithm [16, 17] and Tabu search algorithm [18, 19]. Traditional task scheduling algorithms deliver good performance in a certain aspect but have certain deficiencies in other aspects. When intelligent task scheduling algorithms are used to find the optimal solution for task scheduling problems, they tend to be trapped in the local optimal solution and are not ideal in terms of load balance and rate of convergence. Additionally, in practice, tasks are usually assigned different levels of priority depending on the level of urgency of task execution when they are generated. When finding the optimal solution for the task, these algorithms often neglect the task priority. For these reasons, this paper proposed a task scheduling algorithm integrated with priority and greedy strategy, namely, P-Min-Min-Max algorithm. Under the condition of considering the task priority, this algorithm leverages task execution time for greedy strategy, and binds the big tasks and small tasks from the task list together to form “task pairs”, and performs scheduling of the the “task pairs” for execution. Specifically, the main contributions of this paper are as follows:
(1) The formal definition of service quality has been presented;
(2) The proposed algorithm considers both task priority and service quality at the same time;
(3) A task scheduling algorithm integrated with priority and greedy strategy, namely, P-Min-Min-Max algorithm, has been proposed, which binds the big tasks and small tasks together to form “task pairs” and performs scheduling accordingly, thus effectively solving the problem of load unbalance;
(4) The correctness and effectiveness of the algorithm proposed in this paper have been verified through a series of experiments.
Task scheduling problems and objectives
Before the task scheduling problems and objectives are introduced, the following fundamental concepts are introduced firstly:
➀ Total task completion time: refers to the sum of the completion time of all tasks.
➁ Total task execution time: refers to the time period from the scheduling of the first task to the completion of the execution of the last task.
➂ System resource utilization rate: this indicator is used to measure the idle degree of resource in cloud datacenter and evaluate whether the system load is balanced.
➃ Task response time: refers to the time consumed from the entry of a task into the cloud computing system to the completion of task execution. In general, the shorter the task response time is, the better it will be.
The following common-used symbols and their definitions are listed in Table 1.
Related symbols and its definitions
Related symbols and its definitions
Task scheduling problems and objectives in the cloud computing environment are defined as follows:
Min-Min algorithm and P-Min-Min algorithm
The main idea of Min-Min algorithm can be summarized as follows: firstly, calculate the execution time of each task assigned to various computer resources (VMs), then find the minimum execution time of each task and finally select the task and corresponding resource with the minimum value of these minimum execution times. The idea of Min-Min algorithm can be generalized as two selections of the minimum value. Min-Min algorithm tends to schedule small tasks and neglect big tasks, leading to an increased total task execution time.
P-Min-Min algorithm is different from Min-Min algorithm in that P-Min-Min algorithm considers task priority while Min-Min algorithm does not consider task priority. In fact, different tasks have different orders of priority.
Max-Min algorithm and P-Max-Min algorithm
Considering the problem of the Min-Min algorithm prioritizes scheduling of small tasks, scholars proposed an improved algorithm named Max-Min. Unlike Min-Min algorithm, Max-Min algorithm prioritizes the scheduling of big tasks. The basic idea of Max-Min algorithm can be summarized as follows: firstly, calculate the execution time of each task assigned to various computer resources (VMs), then find the minimum execution time of each task and finally select the task and corresponding resource with the maximum value of these minimum execution times. The idea of Max-Min algorithm can be generalized as a selection of the minimum value and a selection of the maximum value. Max-Min algorithm tends to schedule big tasks and neglect small tasks, leading to an increased total task completion time and response time.
P-Max-Min algorithm is different from Max-Min algorithm in that P-Max-Min algorithm considers task priority while Max-Min algorithm does not consider task priority. In fact, different tasks have different orders of priority.
Heuristic P-Min-Min-Max algorithm
Main idea of P-Min-Min-Max algorithm
Min-Min algorithm and Max-Min algorithm are suitable for task assignment under ideal conditions. But in fact, the tasks in the data center are assigned different levels of priority depending on the level of importance, and the system needs to meet the task permission setting requirements when scheduling the tasks. In addition, the prioritized scheduling of small tasks by Min-Min algorithm or prioritized scheduling of big tasks by Max-Min algorithm also causes the problem of load unbalance. Based on intensive study of Min-Min algorithm and Max-Min algorithm, this paper proposed a task scheduling algorithm integrated with priority and greedy strategy, namely, P-Min-Min-Max algorithm.
The main idea of P-Min-Min-Max algorithm can be summarized as follows: firstly, it selects the task group with the highest level of priority; secondly, calculating the minimum completion times of the tasks in the task group executed on corresponding resources, and select two tasks respectively corresponding to the minimum value and maximum value of these minimum completion times to form a “task pair”, and then the P-Min-Min-Max algorithm leverages the execution time of tasks for greedy strategy; then assigning the task pair to the corresponding resource, and then deleting this task pair from the task set until the assignment of the task group with the highest level of priority is completed. After that, P-Min-Min-Max algorithm schedules the task group with the second highest level of priority, until the entire task set is empty. The wholly process is repeated until the entire task set is empty.
Unlike P-Min-Min algorithm and P-Max-Min algorithm, P-Min-Min-Max algorithm “binds” the big tasks and small tasks together and effectively solves the problem of load unbalance. The detailed process of this algorithm is as follows: Classify the tasks into different task groups depending on task priority, T = T1 ∪ T2, . . . , ∪ T
P
(1 ≤ P ≤ n), where P denotes the level of task priority; a larger P value indicates a higher level of priority; Determine whether the task groups in T are empty, if not, proceed to step (3), otherwise, skip to step (10); Treat T
j
(task group with the highest level of priority in T) as follows: Determine if T
j
is empty, if not, proceed to step (5), otherwise, return to step (2); Calculate the estimated minimum completion time of each task t
i
in task group T
j
assigned to m resources; Select the task corresponding to the minimum value of the minimum completion times, t
a
, and the task corresponding to the maximum value of the minim completion times, t
b
and assign them to the corresponding resources and mark the assignment as host (t
a
, t
b
); Delete tasks t
a
and t
b
from task group T
j
; Update the corresponding earliest completion times of other tasks in T on host (t
a
, t
b
); Return to step (2); Complete the entire task scheduling.
Pseudo-code and time complexity of P-Min-Min-Max algorithm
The definitions of variables related to P-Min-Min-Max algorithm are as follows:
T[]: refers to task set, and T[i] denotes the i-th task;
Flags[]: refers to task status, and Flag[i] = 1 means that this task has not been assigned to the resource, and Flag[i] = 0 means that this task has been assigned to the resource;
flags: denotes the overall status of the task set, flags = Flag [0] + Flag [1] + . . . + Flag [i], and when flags = 0, the assignment of all task sets in the task group has been completed;
S[]: refers to resource set, and S[j] denotes the j-th resource;
RT[]: refers to the ready time of the resource, and RT[j] denotes the ready time of the j-th resource;
ECT[][]: refers to the estimated completion time matrix, and ECT [i][j] denotes the estimated execution time of the i-th task on the j-th resource;
CT[][]: refers to the estimated completion time matrix, and CT[i][j] denotes the completion time of the i-th task on the j-th resource, where CT = [i] [j] = RT [j] + ECT [i] [j];
minmincomTime: refers to the minimum in the minimum completion time group;
maxmincomTime: refers to the maximum in the minimum completion time group;
P: refers to the current level of priority and its initial value is 1.
Figure 1 shows the pseudo-code of P-Min-Min-Max algorithm.
The marked status of the initialized tasks in rows 1-4 is one. When Flag[i] = 1, it means the i-th task has not been assigned to the resource. Rows 5-7 represent the ready times of initialized tasks on various resources and in the default status, no tasks are executed on such resources. Rows 8-18 represent the tasks corresponding to the minimum and maximum values of minimum completion times that are selected from the task group depending on their level of priority, and assigned to the corresponding resources. Rows 19-22 represent updated task assignment status, ready time and priority. According to the aforementioned pseudo-codes, the time complexity of P-Min-Min-Max algorithm is O (m • n), where parameter m denotes the number of VMs and parameter n denotes the number of tasks.
A case analysis
A case: assuming that there are 8 tasks (t1, t2, t3, t4, t5, t6, t7, t8) and two resources (S1, S2) in the cloud computing system, and the priority of each task and its expected completion time on the corresponding resource are as shown in Table 2:
The fist step
The fist step
Step 1: classify the levels of priority, the task group with the highest level of priority T1 = {t1, t2, t3, t4}. From Table 2, it shows that the minimum completion times in task group T1 are as follows:MCT (1) = 1, MCT (2) = 2, MCT (3) = 15, MCT (4) = 22 . 5. Apply greedy strategy on the completion time of task group T1, and find the tasks respectively corresponding to the minimum and maximum values of the minimum completion times. Assigning the task t1 (corresponding to MCT(1)), and the task t2 (corresponding to MCT(2)) to the corresponding resource S2. Then, updating the ready time on resource S2 to RT (2) = 23 . 5. After that, deleting tasks t1 and t4 and update the CT matrix, as shown in Table 3.
The second step
The second step: Table 3 illustrates that, it can be known that MCT(2) = 4, MCT(3) = 30. Assign tasks t2 and t3 (task pair t2 and t3) to resource S1 and update the CT matrix, as shown in Table 4.
The third step
At this point, the assignment of all tasks in task group T1 has been completed. Schedule the task group with a priority level of 1. From Table 4, it displays that MCT (5) = 53 . 5, MCT (6) = 63 . 5, MCT (7) = 73 . 5, MCT (8) = 123 . 5. Assign tasks t5 and t8 (t5task pair and t8) to resource S2 and update the CT matrix, as shown in Table 5.
The forth step
Final iteration: assign tasks t6 and t7 (task pair t6 and t7) to resource S1 and complete the entire task scheduling. According to P-Min-Min-Max algorithm, the sequential order for task scheduling is as follows: S2 (t1) - > S2 (t4) - > S1 (t2) - > S1 (t3) - > S2 (t5) - > S2 (t8) - > S1 (t6) - > S1 (t7), and the total task execution time is the time consumed on resource S1 and the value is 214, resource S1 utilization rate is 50%, resource S2 utilization rate is 50%, and average task response time is: [1 + (+22.5) + (1 + 22.5 + 30) + (1 + 22.5 + 30 + 100) +4 + (4 + 30) + (4 + 30 + 80) + (4 + 30 + 80 + 100)]/8 = 74.69
This paper achieves P-Min-Min-Max algorithm, P-Min-Min algorithm, P-Max-Min algorithm, Min-Min algorithm and Max-Min algorithm in the following hardware environment: Intel(R) Core(TM)i5, Dual-Core 3.4 GHz, 4GB memory, and windows 7 software operating environment. Due to its capability in modeling and simulating large infrastructure supporting cloud computing, this paper used CloudSim [20, 21] as the simulation tool to verify the following five indicators: Total task completion time; Total task execution time; System resource utilization rate; Average task response time; Quality of services provided to users.
During the experiments, the task size was generated randomly within the range of [1, 10000], and total numbers of task were set to 100, 500 and 1000 respectively. The priority of tasks was also generated randomly within the range of {1, 2, 3}. Two resources (VMs) with processing capacity of 4 and 8 were used for the experiments. The comparison algorithms used for the experiments were Min-Min [9], Max-Min [10], P-Min-Min and P-Max-Min algorithms. Among these algorithms, P-Min-Min algorithm considers priority on the basis of Min-Min algorithm, and P-Max-Min algorithm also considers priority on the basis of Max-Min algorithm.
Total task completion time
The first experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of total task completion time. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of total task completion time are as shown in Table 6:
Total task completion time for the five algorithms
Total task completion time for the five algorithms
Table 6 show that, in terms of total task completion time, Min-Min algorithm delivers the best performance, followed by P-Min-Min-Max algorithm, and Max-Min algorithm delivers the worst performance. The main reason can be interpreted as follows: as Min-Min algorithm always schedules tasks to the VM with the highest processing rate, this algorithm delivers the best performance in terms of total task completion time; Max-Min algorithm delivers the worst performance because this algorithm prioritizes the scheduling of big tasks; in terms of total task completion time, the performance of P-Min-Min-Max algorithm is between that of Min-Min algorithm and that of Max-Min algorithm because P-Min-Min-Max algorithm binds the small tasks and big tasks together for scheduling. In addition, both Min-Min algorithm and Max-Min algorithm have a deficiency, i.e. both algorithms do not consider task priority, while P-Min-Min algorithm and P-Max-Min algorithm compensate for this deficiency. Table 6 also shows that as the number of tasks increases, the total task completion time is prolonged significantly.
The second experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of total task execution time. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of total task execution time are as shown in Table 7.
Total task execution time for the five algorithms
Total task execution time for the five algorithms
Table 7 displays that, in terms of total task execution time, when task priority is not considered, Max-Min algorithm is superior to Min-Min algorithm. The reason is as follows: as Min-Min algorithm always schedules small tasks to the VM (resource) with the highest processing rate, which lead to the VMs (resources) with lower processing rate in idle state, while the VMs (resources) with higher processing rate to be excessively loaded. Therefore, Min-Min algorithm delivers the worst performance in terms of total task execution time. P-Min-Min-Max algorithm delivers the best performance in terms of total task execution time because this algorithm binds the small tasks and big tasks together for scheduling, which enables effective utilization of the VMs with both high processing rate and low processing rate. In addition, both Min-Min algorithm and Max-Min algorithm have a deficiency, i.e. both algorithms do not consider task priority, while P-Min-Min algorithm and P-Max-Min algorithm compensate for this deficiency. Table 7 also shows that as the number of tasks increases, the total task execution time grow significantly.
The third experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of resource utilization rate. As two resources marked as S1 and S2 were used for this experiment, the system resource utilization rate (marked as SU) is defined as follows:
System resource utilization rate for the five algorithms
System resource utilization rate for the five algorithms
Table 8 shows that in terms of system resource utilization rate, P-Min-Min-Max algorithm delivers the best performance (lower value indicates more balanced system load and better performance), followed by Max-Min algorithm, and Min-Min algorithm delivers the worst performance. The main reason can be explained as follows: as P-Min-Min-Max algorithm binds the small tasks and big tasks together for scheduling, which enables effective utilization of the VMs with both high processing rate and low processing rate. P-Min-Min-Max algorithm achieves optimal load balance. Min-Min algorithm always schedules small tasks to the VM with the highest processing rate, which causes the VMs with lower processing rate to have no tasks or few tasks to execute, resulting in load unbalance. P-Min-Min algorithm and P-Max-Min algorithm consider task priority on the basis of Min-Min algorithm and Max-Min algorithm respectively.
The third experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of average task response time. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of average task response time are as shown in Table 9.
Average task response time for the five algorithms
Average task response time for the five algorithms
The experiment results show that in terms of average task response time, Min-Min algorithm is the best, P-Min-Min-Max algorithm the second, and Max-Min algorithm delivers the worst performance. The reason is as follows: Min-Min algorithm prioritizes the scheduling of small tasks, which causes the wait time of big tasks to increase and the average task response time to decrease, while Max-Min algorithm prioritizes the scheduling of big tasks for execution, which is opposite to Min-Min algorithm. As P-Min-Min algorithm adopts the strategy of binding the small tasks and big tasks together for execution scheduling, and its performance is ranked between that of Max-Min algorithm and that of Min-Min algorithm. P-Min-Min algorithm and P-Max-Min algorithm consider task priority on the basis of Min-Min algorithm and Max-Min algorithm respectively. Table 9 also shows that as the number of tasks increases, the average task response time grow significantly.
Service qualify is also an important indicator for evaluating the merits and demerits of an algorithm. For different task scheduling algorithms, the definition of service quality varies. Both task response time and execution time can be used to measure the quality of services provided to users. In general, the higher the service quality is, the better the performance of an algorithm in certain aspect will be; and the lower the service quality is, the worse the performance of an algorithm in certain aspect will be. In this paper, service quality is defined as follows:
T1 denotes the total task execution time, and the larger the value of T1 is, the lower the quality of services provided by an algorithm will be; T2 denotes the average task response time, the larger the value of T2 is, the lower the quality of services provided by an algorithm will be; N denotes the number of inversions of tasks assigned to resources during task scheduling, and higher N value indicates lower service quality; for example: after certain task scheduling onto resource S1, when the task execution sequence is (t1 - > t2 - > t5 - > t6), the priority level of tasks t2 and t5 is 2, and the priority level of tasks t1 and t6 is 1, the number of inversions in this sequence N = 2.
Under the conditions of 100, 500 and 1000 tasks, the qualities of services provided by five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) are as shown in Table 10:
qualities of services provided by five algorithms
The experiment results from Table 10 show that among these five algorithms, P-Min-Min-Max algorithm delivers the best service quality, followed by P-Max-Min, P-Min-Min, Min-Min and Max-Min algorithms. The reason can be explained as follows: Min-Min algorithm and Max-Min algorithm deliver low service quality because both of them does not consider task priority when scheduling the tasks for execution. P-Min-Min-Max algorithm delivers the best service quality because on one side, this algorithm considers task priority and on the other side, this algorithm has certain advantages in terms of total task execution time and average task response time.
Under the consideration of task priority, this paper proposed a task scheduling algorithm P-Min-Min-Max by the combination of greedy strategy and binding strategy. The results from a series of experimental evaluations show that the P-Min-Min-Max algorithm is superior to other algorithms. The proposed algorithm can be used to carry out various practical task scheduling activities (such as vehicle scheduling and arrangement of work sequence in factories), improving the quality of services and saving cost, thus improving enterprises’ return on investment.
In cloud computing environment, a variety of factors, such as network wide band, and system’s energy consumption and resource price, may affect the performance of the task scheduling algorithm. Therefore, in the future research, a better algorithm will be designed taking into account multiple factors to meet users’ needs.
Footnotes
Acknowledgments
The authors acknowledge the National Natural Science Foundation of China (Grant: 61772088), China Postdoctoral Science Foundation (Grant: 2018M642974), the Natural Science Foundation of Hunan Province, China (Grant: 2019JJ50689), the scientific research project of education department of hunan province (Grant:18B412), and the Science and Technology Plan Project of Changsha city (Grant: k1705036).
