Task Staggering Peak Scheduling Policy for Cloud Mixed Workloads

Abstract

To address the issue of cloud mixed workloads scheduling which might lead to system load imbalance and efficiency degradation in cloud computing, a novel cloud task staggering peak scheduling policy based on the task types and the resource load status is proposed. First, based on different task characteristics, the task sequences submitted by the user are divided into queues of different types by the fuzzy clustering algorithm. Second, the Performance Counters (PMC) mechanism is introduced to dynamically monitor the load status of resource nodes and respectively sort the resources by the metrics of Central Processing Unit (CPU), memory, and input/output (I/O) load size, so as to reduce the candidate resources. Finally, the task sequences of specific type are scheduled for the corresponding light loaded resources, and the resources usage peak is staggered to achieve load balancing. The experimental results show that the proposed policy can balance loads and improve the system efficiency effectively and reduce the resource usage cost when the system is in the presence of mixed workloads.

1. Introduction

Cloud computing [1,2,3] is an emerging business application providing on-demand access, ubiquitous access characteristics, and elastically scalable information technology (IT) resource usage [4]. A variety of applications [5,6] have been deployed in cloud computing platforms, some application tasks have higher CPU requirements, and some require higher storage, while others require frequent I/O access or larger bandwidth resources. Different cloud tasks have great differences in resource requirements due to their own constraints, diversity, and complexity [7].

Recently, task scheduling for mixed workloads has attracted plenty of attention [8,9]. Mixed workloads typically include compute-intensive, memory-intensive and data-intensive tasks. Most of the compute-intensive tasks are used for CPU operations such as computation or logic judgment. Memory-intensive tasks take up a large number of storage resources. The main execution features of data-intensive tasks are large amounts of data transmission, processing, and I/O access. For the task sequences of massive mixed workloads submitted by user, it is Non-deterministic Polynomial Complete (NP-C) to reasonably allocate cloud resources and ensure the load balancing and performance efficiency of the whole system. The relevant research results of task scheduling have showed that: (1) Different types of tasks (compute-intensive, memory-intensive and data-intensive) have significant differences in resource requirements [10,11]. (2) Heterogeneity of node resources and dynamic nature of load. When scheduling tasks of different types, the load size of resources such as CPU, memory, and I/O on the node resources at the current time needs to be considered [12,13]. Unreasonable task scheduling policy might lead to a load imbalance of resources, which not only seriously affects node resource utilization and performance, but also increases task completion time and cost.

In this work, we propose a Staggering Peak Scheduling by Load-aware Model (SPSLAM) when researching the task scheduling problem of cloud mixed workloads. The SPSLAM mainly considers the task characteristics and resource load status, which aims to balance load, improve efficiency, and optimize resource usage cost. The main contributions of our work are as follows:

• The task sequences of mixed workloads are divided into multiple types of queues by the fuzzy clustering algorithm based on different task characteristics.
• We introduce the Performance Counters (PMC) mechanism to dynamically monitor the node resource load status and respectively sort the resources by CPU, memory, and I/O load size.
• We develop a policy SPSLAM from the perspective of task types and resource load for mixed workloads and by doing so, the system can realize load balancing and improve efficiency.

The rest of the paper is organized as follows. In Section 2, the related work is discussed. In Section 3, we introduce the system model and give the definition of related concepts. Section 4 presents the staggering peak scheduling policy. Experiment results and performance analysis are presented in Section 5. Section 6 concludes the paper.

2. Related Work

To address the issue of scheduling mixed workloads in cloud computing, Khorandi et al. [14] presented a high-performance technique for virtualization-unaware scheduling of compute-intensive synchronized tasks in virtualized high performance computing systems. Virtual machines (VMs) were in turn assigned/reassigned to clustered physical machines based on CPU load. In this way, it can minimize the performance and scalability degradation of high-performance computing applications. However, its performance was extremely unstable due to the large dynamic nature of the “intermediate data” generated during executing I/O-intensive tasks. In some test cases, there may even be a 30% reduction in system energy efficiency. To optimize system performance, Wang et al. [15] found that computation-intensive tasks and bandwidth-intensive tasks together created a severe bottleneck in cloud-based distributed interactive applications. They presented an interference-aware solution to smartly allocate workloads and dynamically assign capacities across VMs based on their arrival/departure patterns. However, the scalability of the solution required further verification when it came to the interference between the computation-intensive and bandwidth-intensive tasks. It can be seen that the task characteristics and resource load status have an important impact on the scheduling effect.

For the heterogeneity of node resources and the dynamic nature of load in cloud computing, most of the research has focused on resources pre-process and static analysis of resources load status. Resources were clustered based on cloud computing resources set on the service level of user, which made tasks with different preferences to be selected in different clusters to reduce the task scheduling range [11]. However, the method assumed that the computing and communication capabilities of resources were stable for a certain period of time when the resources were clustered, and the changes in resource computing and communication capabilities were not considered. After a period of time, it was easy to cause load imbalance and efficiency reduced. To realize flexible management of multi-resource cloud task scheduling performance and energy, Mao et al. [16] proposed a multi-resource cloud task scheduling algorithm for Energy Performance Trade-Offs. The energy and performance of a cloud system can be flexibly managed and controlled by setting a parameter to reconfigure the weight of performance and energy consumption. But the factors influencing the performance and the energy consumption of VM, host, and data center were diversified. The way to realize better trade-offs was not only about tuning the static parameter but also designing an algorithm that dynamically changed the parameter based on the current workload situation. Therefore, for cloud task scheduling issues of mixed workloads, it is necessary to consider the dynamic nature of resource load to select the appropriate scheduling policy after analyzing the task characteristics. This requires further research in this paper.

The load balancing technology [17] in cloud computing has always been a research focus. Chen et al. [18] measured the load status by setting the number of task request connections for the node resources and assigned the task to the node with the smallest number of connections. However, this method did not reflect the real load of the node resources. When the load request increased rapidly, the scheduling efficiency decreased instantly and the load was easily imbalanced. In cloud computing, Zhao et al. [19] used the Software Workbench for Interactive, Time Critical and Highly self-adaptive Cloud applications (SWITCH) project to address the urgent industrial need for developing and executing time critical applications. Mobile edge computing (MEC) [20] was to push mobile computing, network control, and storage to the network edges (e.g., base stations and access points) so as to enable computation-intensive and latency-critical applications at the resource-limited mobile devices. To satisfy the quality of offloading service, Zhang et al. [21] proposed a hierarchical cloud-based Vehicular Edge Computing (VEC) offloading framework, where a backup computing server in the neighborhood was introduced to make up for the deficit computing resources of MEC servers. Offloading computation to a mobile cloud was a promising approach for enabling the use of computationally intensive applications by mobile devices. To address the allocation of cloud and wireless resources among mobile devices, Josilo et al. [22] provided a polynomial time algorithm to optimize the equilibrium cost and provide good system performance.

Based on the existing study, our work focuses on the diversity of tasks, the constraints of tasks themselves, and the relationship with the requirement of resources. When analyzing the resource load status, static performance indicators such as CPU computing ability, memory, and bandwidth are mostly used. However, in the dynamic environment such as cloud computing, these indicators are uncertain and atypical, and it is necessary to dynamically monitor the resources load status during task scheduling. This paper proposes the SPSLAM that mainly considers task characteristics and resources load status. The goal is to achieve load balancing, improve efficiency, and optimize resource usage cost.

3. Model Description

System Framework Model

The system framework of SPSLAM proposed in this paper is shown in Figure 1. It includes three parts: task sequences classification, resources load sorting, and scheduling scheme generation. For the task sequences submitted by the user, firstly, based on the characteristics of each task and the different requirements of resources, the Fuzzy C-Means (FCM) clustering algorithm is used to divide the task sequences of the mixed workloads into multiple types of queues. Secondly, the classification and sorting of resources load is achieved by introducing the PMC mechanism. Finally, the task execution queues and resource sorting information are taken as input, and the final scheduling scheme is generated based on SPSLAM.

The applications submitted by the user in this paper can be represented as the task sequences $V=\left\{V_{ij}|V_{ij}=\langle C_{ij},M_{ij},O_{ij}\rangle \right\}$, where $V_{ij}$ represents the $jth$ task of the $ith$ sequence, $C_{ij}$ represents the computational amount of $V_{ij}$ (unit: $MIPS$, the number of instructions), $M_{ij}$ is the memory resource required by $V_{ij}$, and $O_{ij}$ is the $I/O$ resource required by $V_{ij}$.

The node resources in cloud computing can be defined as mainly composed of CPU, memory, and $I/O$ resource. These resources are noted as $R=\left\{R_1,R_2,\dots ,R_m\right\}$, where $R_j=\langle C_j,M_j,O_j\rangle$. Three parameters of the resources respectively represent CPU utilization, available memory size, and $I/O$ latency wait time. The data transfer rate between the two node resources is noted as the matrix $B$, where the matrix element $b_{i,j}$ represents the data transfer rate between $R_i$ and $R_j$.

4. Staggering Peak Scheduling Policy

The SPSLAM proposed in this paper consists of three parts: task sequences classification, resources load sorting, and scheduling scheme generation.

4.1. Task Sequences Classification

In cloud computing, the requirements of tasks are difficult to describe accurately, and the dynamic nature of cloud resources makes it impossible to correctly describe the load status in a specific time period. Therefore, the matching scheduling of tasks and resources also has some ambiguity.

Due to the different characteristics of tasks, the demand for resources is different. For example, compute-intensive tasks require strong CPU computing ability, memory-intensive tasks require large amounts of memory, and data-intensive tasks require frequent $I/O$ access and bandwidth resources. In this paper, the FCM algorithm is used to divide the task sequences into three queues: CPU-intensive, memory-intensive, and I/O-intensive based on the diversity requirements of tasks. The FCM algorithm is an improved scheme of K-means by applying fuzzy theory. It belongs to the soft clustering algorithm and promotes the hard membership to soft membership, which makes the iteration of the central point easier to achieve global optimization. At the same time, the FCM algorithm is superior to the traditional hard clustering algorithm in clustering time and accuracy. The specific clustering process based on FCM algorithm is described as follows:

Step 1. Form an initialization sample matrix ${\mathrm{T}}_{\mathrm{n}\times 3}$ based on attribute values ${\mathrm{V}}_{\mathrm{ij}}=\langle {\mathrm{C}}_{\mathrm{ij}},{\mathrm{M}}_{\mathrm{ij}},{\mathrm{O}}_{\mathrm{ij}}\rangle$ of $\mathrm{n}$ tasks, where ${\mathrm{T}}_{\mathrm{ij}}$ represents the $\mathrm{jth}$ dimension attribute of the $\mathrm{ith}$ task. Since the three parameter units of ${\mathrm{V}}_{\mathrm{ij}}$ are not on the same scale, the attribute values need to be respectively standardized and normalized when classifying the task sequences. We standardize ${\mathrm{T}}_{\mathrm{ij}}$ to get ${\mathrm{T}}_{\mathrm{ij}}^{\prime }$ by Equation (1),

$$T_{ij}^{\prime }=\frac{T_{ij}-\overline{T_j}}{S_j}$$

(1)

where $\overline{{\mathrm{T}}_{\mathrm{j}}}=\frac{1}{\mathrm{n}}{\sum }_{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{T}}_{\mathrm{ij}}$, and ${\mathrm{S}}_{\mathrm{j}}$ is the standard deviation of ${\mathrm{V}}_{\mathrm{ij}}$ in the $\mathrm{jth}$ dimension attribute. Then we normalize ${\mathrm{T}}_{\mathrm{ij}}^{\prime }$ to compress the data between $[0,1]$ by Equation (2),

$${\mathrm{T}}_{\mathrm{ij}}^{″}=\frac{{\mathrm{T}}_{\mathrm{ij}}^{\prime }-{\mathrm{T}}_{\mathrm{jmin}}^{\prime }}{{\mathrm{T}}_{\mathrm{jmax}}^{\prime }-{\mathrm{T}}_{\mathrm{jmin}}^{\prime }}$$

(2)

where ${\mathrm{T}}_{\mathrm{jmax}}^{\prime }$ and ${\mathrm{T}}_{\mathrm{jmin}}^{\prime }$ represent the maximum and minimum values in $\left\{{\mathrm{T}}_{1\mathrm{j}}^{\prime },{\mathrm{T}}_{2\mathrm{j}}^{\prime },\dots ,{\mathrm{T}}_{\mathrm{nj}}^{\prime }\right\}$, respectively.

Step 2. Set the number of task clusters to 3 and initialize the membership matrix ($\mathrm{U}$) with a random number whose value is between $[0,1].$ The initialization condition can be formally presented as Equation (3), where ${\mathrm{u}}_{\mathrm{ij}}$ indicates the degree to which ${\mathrm{V}}_{\mathrm{ij}}$ belongs to the fuzzy group (${\mathrm{c}}_{\mathrm{j}}$). The larger the ${\mathrm{u}}_{\mathrm{ij}}$ is, the higher the probability the ${\mathrm{V}}_{\mathrm{ij}}$ belongs to ${\mathrm{c}}_{\mathrm{j}}$.

$${\displaystyle \sum }_{\mathrm{i}=1}^{\mathrm{c}}{\mathrm{u}}_{\mathrm{ij}}=1,\forall \mathrm{j}=1,2,\dots ,\mathrm{n}$$

(3)

Step 3. In order to ensure the minimum dissimilarity between the cloud task and its cluster center in each cluster, we use the weighted exponential product of ${\mathrm{u}}_{\mathrm{ij}}$ and each task to the Euclidean distance $\left({\mathrm{d}}_{\mathrm{ij}}\right)$ of each class center as the optimization objective function. The function is defined as

$$\mathrm{J}\left(\mathrm{U},{\mathrm{c}}_1,{\mathrm{c}}_2,\dots ,{\mathrm{c}}_{\mathrm{n}}\right)={\displaystyle \sum }_{\mathrm{i}=1}^{\mathrm{c}}{\mathrm{J}}_{\mathrm{i}}={\displaystyle \sum }_{\mathrm{i}=1}^{\mathrm{c}}{\displaystyle \sum }_{\mathrm{j}}^{\mathrm{n}}{\mathrm{u}}_{\mathrm{ij}}^{\mathrm{m}}{\mathrm{d}}_{\mathrm{ij}}^2$$

(4)

where ${\mathrm{d}}_{\mathrm{ij}}=\Vert {\mathrm{V}}_{\mathrm{ij}}-{\mathrm{c}}_{\mathrm{j}}\Vert ,$ and $\mathrm{m}=2$ which is a weighted index in this paper. To get the optimal extreme value of the clustering function, the lattice multiplier method can be used to derive the iterative formula of ${\mathrm{c}}_{\mathrm{k}}$ and $\mathrm{U}$.

$${\mathrm{c}}_{\mathrm{k}}=\frac{{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{u}}_{\mathrm{ki}}^{\mathrm{m}}{\mathrm{V}}_{\mathrm{ii}}}{{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{u}}_{\mathrm{ki}}^{\mathrm{m}}},\mathrm{k}=\left\{1,2,3\right\}$$

(5)

$${\mathrm{u}}_{\mathrm{ki}}=\frac{1}{{\sum }_{\mathrm{p}=1}^{\mathrm{c}}{\left(\frac{{\mathrm{d}}_{\mathrm{ki}}}{{\mathrm{d}}_{\mathrm{pi}}}\right)}^{\raisebox{1ex}{$2$}\!\left/ \!\raisebox{-1ex}{$\left(\mathrm{m}-1\right)$}\right.}}$$

(6)

Step 4. Calculate ${\mathrm{c}}_{\mathrm{k}}$ and $\mathrm{J}\left(\mathrm{U},{\mathrm{c}}_1,{\mathrm{c}}_2,\dots ,{\mathrm{c}}_{\mathrm{n}}\right)$ by Equations (4) and (5) respectively. If $\mathrm{J}<\epsilon$ ($\mathsf{\epsilon }$ is the threshold), it indicates that the cluster ends. Otherwise, update $\mathrm{U}$ by Equation (6) and return to step 3.

In this paper, the algorithm of task sequences classification based on FCM is listed in Algorithm 1.

Algorithm 1: The algorithm of task sequences classification

Input:$\mathrm{c}=3,{\mathrm{task}}_{\mathrm{list}},\mathsf{\epsilon }$ Output:${\mathrm{Q}}_{\mathrm{VCPU}},{\mathrm{Q}}_{\mathrm{VMem}},{\mathrm{Q}}_{\mathrm{VIO}}$   1: Initialize the sample matrix $T_{n\times 3}$ through the task attribute values $C_{ii},M_{ii }and O_{ii}$;   2: for $T_{ij} ϵ T_{n\times 3}$ do   3:       Standardize and normalize $T_{ij}$ to get $T_{ij}^{\prime }$;   4: End for   5: Initialize the membership matrix $U$;   6: Do calculate three cluster centers;   7:        Calculate the value function $\mathrm{J}\left(\mathrm{U},{\mathrm{c}}_1,{\mathrm{c}}_2,\dots ,{\mathrm{c}}_{\mathrm{n}}\right)$;   8:        Recalculate the membership matrix $U$;   9: Until $\mathrm{J}\left(\mathrm{U},{\mathrm{c}}_1,{\mathrm{c}}_2,\dots ,{\mathrm{c}}_{\mathrm{n}}\right)<\epsilon$ 10: Return $Q_{VCPU},Q_{VMem},Q_{VIO}$;

After clustering the task sequences, these sequences have been divided into three queues: CPU-intensive queue $({\mathrm{Q}}_{\mathrm{VCPU}})$, memory-intensive queue $\left({\mathrm{Q}}_{\mathrm{VMem}}\right)$, and I/O-intensive queue $\left({\mathrm{Q}}_{\mathrm{VIO}}\right)$, which are defined as

$$\{\begin{array}{c}{Q}_{VCPU}=\left\{V_1,V_2,\dots ,V_a\right\}\\ Q_{VMem}=\left\{V_{a+1},V_{a+2},\dots ,V_{a+b}\right\}\\ Q_{VIO}=\left\{V_{a+b+1},V_{a+b+2},\dots ,V_n\right\}\end{array}$$

(7)

Among them, ${\mathrm{Q}}_{\mathrm{VCPU}}$ contains $\mathrm{a}$ task, the length of the ${\mathrm{Q}}_{\mathrm{VMem}}$ is $\mathrm{b}$, and the length of ${\mathrm{Q}}_{\mathrm{IO}}$ is $\mathrm{n}-\mathrm{a}-\mathrm{b}$. The total length of the three queues is $\mathrm{n}$.

4.2. Resources Load Sorting

For the load status of node resources, we have introduced different types of PMC [23] mechanisms to evaluate it. Recent research results have shown that the PMC mechanism can accurately and intuitively reflect the use of hardware components during system operation. By reading PMC data, it can accurately measure system energy consumption and monitor resource activity with little overhead [23,24].

In general, VMs deployed on each node resource trigger various types of PMC events during execution. From the hardware perspective, PMC events represent that some node resources are active. Based on the PMC mechanism, this paper monitors the number of resources activity events such as CPU ($P^{CPU})$, Mem $\left(P^{Mem}\right)$, Disk $(P^{Disk}$), and Net $(P^{Net}$) triggered by the execution of VMs, and respectively records the PMC event set associated with the specific resource device. Combining the proportion of various events in the overall PMC event of the system can sort the load status of the node resources in a specific period of time, and can be formulated as

$$f_i^x={\displaystyle \sum }_{Xϵ\left\{CPU,Mem,IO\right\}}\frac{P_i^X\left(t_{1,}{t}_2\right)}{P^X\left(t_{1,}{t}_2\right)},i=\left\{1,2,\dots ,n\right\}$$

(8)

where $P_i^X\left(t_{1,}{t}_2\right)$ represents the PMC event related to resource $X$ triggered by the execution of $V{M}_i$ during the time period $\left[t_{1,}{t}_2\right]$, and $P^X\left(t_{1,}{t}_2\right)$ represents the total PMC event related to the resource $X$. Using the proportional relationship between the two, we indicate three indicators ($f_i^{CPU}$, $f_i^{Mem}$, and $f_i^{io}$) respectively represent the CPU usage, memory usage, and I/O latency wait time when $V{M}_i$ is executed. Since the I/O access process during task scheduling is closely related to disk and network bandwidth activity events, $P_i^{IO}$ can be used to represent these two sets of PMC events. $P_i^{IO}$ is formulated as

$$P_i^{IO}=P_i^{Disk}+P_i^{Net}$$

(9)

Therefore, the resources load sorting based on the PMC mechanism is described by the proportion of PMC events triggered by VM to the total PMC events. The relevant data can be obtained through the PMC programming interface. The three indexes of $f_i^{CPU}$, $f_i^{Mem}$, and $f_i^{io}$ are respectively sorted from small to large for all resources. The three queues are formulated as

$$\{\begin{array}{c}{Q}_{CPU}=\left\{C_{1CPU},C_{2CPU},\dots ,C_{mCPU}\right\}\\ Q_{Mem}=\left\{C_{1Mem},C_{2Mem},\dots ,C_{mMem}\right\}\\ Q_{IO}=\left\{C_{1IO},C_{2IO},\dots ,C_{mIO}\right\}\end{array}$$

(10)

It should be noted that cloud resources are only sorted without static classification after the resources load status is distinguished due to the dynamic nature. All the resources are included in the three queues, unlike the task scheduling queues.

4.3. Staggering Peak Policy

Based on the diversity requirements of cloud tasks, mixed workloads are generally divided into three types: compute-intensive, memory-intensive, and data-intensive tasks. Most of compute-intensive tasks include calculations, logical judgments, and other CPU actions that consume CPU resources, resulting in high CPU usage peak. Memory-intensive tasks mainly take up a large number of storage resources. Data-intensive tasks involve frequent network transfers and large data reading and writing of I/O devices such as disks. This type of task consumes very little CPU and spends most of its time on I/O processing of data and operations waiting for I/O operations to complete, because I/O operations are much slower than CPU and memory.

When scheduling the task sequences, it is necessary to consider the different characteristics and the diversity requirements. During the execution of cloud tasks, the use of CPU, memory, and I/O resources do not conflict with each other. For example, when the cloud platform performs a task requesting a large number of CPU computing resources, the memory and I/O resources are generally in an idle state, and the non-CPU-intensive task can be scheduled for the resource to balance the load, improve scheduling efficiency, and optimize cost. This paper proposes the SPSLAM algorithm based on the analyzed task sequences classification and resources load sorting to make full use of these idle resources in cloud computing. The SPSLAM is presented in Algorithm 2.

Algorithm 2: SPSLAM

Input:$Lis{t}_{schedule},\left\{Q_{VCPU},Q_{VMem},Q_{VIO}\right\},\left\{Q_{CPU},Q_{Mem},Q_{IO}\right\}$ Output:$bestSchedule$   1: for$V_{ii}\in Lis{t}_{schedule}$   2:        if$prec(V_{ii})$ has been scheduled then   3:             if $V_{ii}\in Q_{VCPU}$ then   4:                 Schedule $V_{ii}$ into $Q_{CPU}$;   5:             End if   6:             if $V_{ii}\in Q_{VMem}$ then   7:                 Schedule $V_{ii}$ into $Q_{Mem}$;   8:             End if   9:             if $V_{ii}\in Q_{VIO}$ then 10:                 Schedule $V_{ii}$ into $Q_{IO}$; 11:             End if 12:        End if 13: End for

The SPSLAM algorithm proposed in this paper distinguishes the types of tasks and the load status of node resources during task scheduling. If $V_{ii}$ is a data-intensive task, it should be scheduled to $Q_{IO}$.

The complexity of the SPSLAM algorithm is composed of three parts: task sequences classification, resources load sorting, and staggering peak policy. The time complexity of the task sequences classification algorithm based on FCM is $\mathrm{O}\left(\mathrm{t}\times \mathrm{N}\right)$, where $\mathrm{t}$ is the number of iterations, and $\mathrm{N}$ is the number of tasks. The resources load sorting complexity is $\mathrm{O}\left(\mathrm{MlogM}\right)$, where $\mathrm{M}$ is the number of the resources. The time complexity of the staggering peak policy is $\mathrm{O}\left(\mathrm{N}\right)$. Therefore, the complexity of the SPSLAM is $\mathrm{O}\left(\mathrm{t}\times \mathrm{N}+\mathrm{MlogM}\right)$. Due to the fact that the task sequences classification and the resources load sorting can be executed at the same time, it will not cause too much extra time overhead for the system. Actually, the SPSLAM complexity is less than $\mathrm{O}\left(\mathrm{t}\times \mathrm{N}+\mathrm{MlogM}\right).$

5. Experiments and Evaluation

In this section, we discuss the experimental results to evaluate the performance of SPSLAM. We used a workflow simulator (WorkflowSim [25]) and performed simulation scheduling experiments on the simulator. The task sequences with a different number of tasks were generated by the generator (WorkflowGenerator [26]). The simulator and generator were the open source software developed by the Pegasus group at the University of Southern California. The experimental results were compared with fuzzy clustering and two level based task scheduling (FCTLBS) [11], multi-queue interlacing peak scheduling method (MIPSM) [13], and least connection (LC) [18].

5.1. Workloads and Setup

In this paper, to address the issue of scheduling mixed workloads in cloud computing, three scientific workflow task sequences (Montage [27], CyberShake [28], and Epigenomics [29]) were selected for the experiments, which were respectively derived from astronomy, seismology and human genetics.

We used the above three scientific workflows to generate task sequences combinations with a different number of tasks. The combinations formed three sets of test workloads (Montage-25, CyberShake-30, Epigenomics-24), (Montage-50, CyberShake-50, Epigenomics-50), (Montage-100, CyberShake-100, Epigenomics-100), which were respectively recorded as WL#1, WL#2, and WL#3. The characteristics of some of the tasks in these three scientific workflows are shown in

Table 1. Scientific workflow characteristics.

Name	Category	Type-intensive	Count	Runtime (s)	Inputs (MB)	Outputs (MB)
mConcaFit	Montage	CPU	1	13.60	0.03	0.02
mAdd	Montage	CPU	1	30.34	357.28	330.86
extract_agt	CyberShark	I/O	19	355.31	38786.64	441.97
fastqSplit	Epigenomics	Mem	2	41.78	462.20	462.20
map	Epigenomics	I/O	146	9635.01	2964.24	0.58

. For example, the task fastqSplit in the workflow Epigenomics is a memory-intensive task, which requires plenty of storage resources.

All experiments were run on Dell machines with the Inter(R) Core(TM) i5-6500 processor, 3.20 GHZ, 4 GB memory, and Windows7 64-bit operating system. We used the WorkflowSim to generate a data center with 600 hosts, each with 10 VMs. The features of VM referred to the type of Amazon EC2 VM [27]. The specific parameters of the five types of VMs are shown in

Table 2. Five kinds of virtual machine (VM) types.

VM	CPU (MIPS)	RAM (GB)	BW (M/S)	Price ($/h)
1	2500	0.85	750	4.65
2	2000	3.75	500	4.03
3	1000	1.70	980	3.71
4	750	1.25	1043	3.67
5	500	0.61	558	3.24

.

5.2. Experiment Metrics

The experiment metrics of the cloud staggering peak scheduling policy for mixed workloads proposed in this paper mainly include load balancing, efficiency, and cost optimization. The efficiency is mainly represented by the total completion time of the execution task sequences and the task success rate.

Load balancing ($\mathrm{LB}$) can be expressed by the mean square error of each resource load in this paper, which refers to the degree of load balancing between resources. The $\mathrm{LB}$ is formulated as

$$\mathrm{LB}=\frac{1}{\mathrm{m}}{\displaystyle \sum }_{\mathrm{j}=1}^{\mathrm{m}}{\left({\mathrm{Load}}_{\mathrm{j}}-{\mathrm{Load}}_{\mathrm{avg}}\right)}^2$$

(11)

where ${\mathrm{Load}}_{\mathrm{j}}$ represents the load of ${\mathrm{R}}_{\mathrm{j}}$, and ${\mathrm{Load}}_{\mathrm{avg}}$ represents the average load of each resource. The smaller the $\mathrm{LB}$ is, the more balanced the system load system gets in cloud computing.

The task completion time ($\mathrm{Makespan})$ is the total execution time of all task sequences submitted by the user. The $\mathrm{Makespan}$ is formulated as

$$\mathrm{Makespan}=\underset{\mathrm{i}\in \mathrm{N}}{\max }\left\{{\mathrm{Makespan}}_{\mathrm{i}}\right\}$$

(12)

where $\mathrm{N}$ represents the number of task sequences, and ${\mathrm{Makespan}}_{\mathrm{i}}$ represents the completion time of the $\mathrm{ith}$ task sequence.

The task success rate (${\mathrm{V}}_{\mathrm{s}}$). If the completion time of ${\mathrm{V}}_{\mathrm{ij}}$ is less than the deadline, ${\mathrm{V}}_{\mathrm{ij}}$ will be considered to be successfully executed under the deadline constraint. The ${\mathrm{V}}_{\mathrm{s}}$ can be formulated as

$${\mathrm{V}}_{\mathrm{s}}=\frac{{\mathrm{n}}_{\mathrm{s}}}{\mathrm{N}}\times 100\%$$

(13)

where ${\mathrm{n}}_{\mathrm{s}}$ is the number of successfully executed tasks in $\mathrm{N}$ tasks.

Resource usage cost ($\mathrm{SumCost}$). This paper introduced the time-based charging method in the Amazon EC2 cloud environment [30], which was charged in hours. Therefore, the execution cost of each task sequence is the sum of the cost of each VM. The $\mathrm{SumCost}$ can be formulated as

$$\mathrm{SumCost}={\displaystyle \sum }_{\mathrm{i}=1}^{\mathrm{n}}{\displaystyle \sum }_{\mathrm{j}=\mathrm{i}}^{\mathrm{k}}\mathrm{Cos}\mathrm{t}\left({\mathrm{VM}}_{\mathrm{i},\mathrm{j}}\right)$$

(14)

where $Cost\left(V{M}_{i,j}\right)=\left[EFT\left(V_{end},V{M}_{i,j}\right)-EST\left(V_{start},V{M}_{i,j}\right)\right] \times P(V{M}_{i,j})$. Among them, $V{M}_{i,j}$ represents the $jth$ VM on the $ith$ node resource, $P(V{M}_{i,j})$ represents the cost per unit time, $EFT\left(V_{end},V{M}_{i,j}\right)$ represents the completion time of the last executed task on $V{M}_{i,j}$, and $EST\left(V_{start},V{M}_{i,j}\right)$ represents the starting time of the earliest execution of the task on $V{M}_{i,j}$. $k$ represents the number of VMs on each node resource.

5.2.1. Load Balancing

Figure 2 shows the performance of the four algorithms in load balancing by LB where the total number of tasks is different in all task sequences. The smaller the LB is, the more balanced the load between cloud resources gets. As is shown in Figure 2, as the number of tasks increases, the load of each VM resource also increases, causing the host to be overloaded and a decrease in LB. The LB of the SPSLAM algorithm has been relatively small and has little change, and the MIPSM algorithm is second. The FCTLBS algorithm performed the worst because it only statically clustered resources, and did not consider the dynamic nature of resources load, which led to imbalanced distribution of node load. The LC algorithm got better load balancing effect because it always prioritized the resources with lighter load during scheduling. However, when the number of tasks was too much, the effect became worse. The experimental results showed the advantages of the staggering peak scheduling policy based on task diversity and the dynamic nature of resources.

5.2.2. Scheduling Completion Time

Figure 3 shows the scheduling completion time of the four algorithms in the case where the number of workflows is increased from 3 to 15. When the number of workflows is 3, the makespan of the four algorithms is not much different. With the increase of the number of workflows, the makespan of SPSLAM is significantly lower than FCTLBS, MIPSM, and LC. The reason was that SPSLAM staggered the resource usage peak and reduced the delay waiting time of the task when scheduling the workflow task sequences. In this way, it reduced the scheduling completion time and finally improved the task scheduling efficiency.

5.2.3. Task Success Rate

Figure 4 shows the scheduling effect by ${\mathrm{V}}_{\mathrm{s}}$. The abscissa is the total number of tasks in all task sequences, and the ordinate represents the success rate of different algorithms. As is shown in Figure 4, as the number of tasks increases, the resource competition occurs, and the ${\mathrm{V}}_{\mathrm{s}}$ of tasks decreases correspondingly. The LC algorithm did not consider task characteristics and its diversity when scheduling mixed workloads, and the performance was worse. The FCTLBS algorithm only pre-processed and statically clustered resources, which led to poor performance. The MIPSM algorithm only performed hard clustering on tasks, and did not consider the fuzziness of matching scheduling between task and resource, which had certain limitations. The SPSLAM algorithm had a task success rate of 90%, which was within an acceptable range. The experimental results showed that this policy had obvious advantages for mixed workloads.

We finished two sets of experiments to show scalability of the proposed framework by using system efficiency metrics. The first experiment verified the scheduling completion time of the four algorithms in the case where the number of workflows was increased from 3 to 15. When the number of workflows was 3, the makespan of the four algorithms was not much different. With the increase of the number of workflows, the makespan of SPSLAM was significantly lower than FCTLBS, MIPSM, and LC. This proved that the proposed framework reduced the delay time of task scheduling and the scheduling completion time. The second experiment verified the scheduling effect by ${\mathrm{V}}_{\mathrm{s}}$. As the number of tasks submitted by users increased, the resource competition occurred, and the ${\mathrm{V}}_{\mathrm{s}}$ of tasks decreased correspondingly. However, the proposed framework still had a task success rate of 90%, which was within an acceptable range. It can be concluded that the SPSLAM algorithm had relatively high ${\mathrm{V}}_{\mathrm{s}}$ and throughput when the task workloads submitted by users were increased. It improved the system efficiency effectively and was of good scalability.

5.2.4. Resource Usage Cost

Figure 5 shows the scheduling cost of the four algorithms under different deadline constraints. The experiment was divided into three groups, and each group executed different test workloads (WL#1, WL#2, and WL#3). We selected the five values in the minimum and maximum completion time intervals as the deadline constraints, $\mathrm{deadline}={\mathrm{t}}_{\min }+\mathrm{W}\times \left({\mathrm{t}}_{\max }-{\mathrm{t}}_{\min }\right)$, where $\mathrm{W}$ was the weight parameter, and $\mathrm{W}\in \left\{0.17,0.34,0.51,0.68,0.85\right\}.$ As is shown in Figure 5, when the constraint on the deadline is reduced, the scheduling scheme that satisfies the time constraint is gradually increased and the cost of the four scheduling algorithms is reduced. Among the four algorithms, the resource usage cost generated by SPSLAM was the lowest. The reason was that the SPSLAM algorithm considered the characteristics of each task for mixed workloads and used the FCM algorithm to divide the task sequences into three categories according to the resources requirements such as CPU, memory, and I/O, which reduced the blindness of tasks scheduling. The resources were sorted by CPU size, memory, and I/O load size by monitoring the load status to narrow the resource selection range. SPSLAM considered the task characteristics and resources load status when scheduling multiple task sequences, which improved the task scheduling efficiency and reduced the resource usage cost.

6. Conclusions

To address the issue of scheduling mixed workloads in cloud computing, a novel cloud task staggering peak scheduling policy SPSLAM based on task characteristics and resource load status was proposed. This policy consisted of three parts: task sequences classification, resources load sorting and scheduling scheme generation. First, based on different task characteristics, the task sequences were divided into queues of different types by the fuzzy clustering algorithm. Second, PMC mechanism was introduced to dynamically monitor the load status of resource nodes and respectively sort the resources by the metrics of CPU, memory, and I/O load size. Finally, the task sequences of specific type were scheduled for the corresponding light loaded resources, and the resources usage peak was staggered to achieve load balancing. The experimental results showed that the proposed policy was superior to other algorithms in terms of load balancing and system efficiency, and reduced resource usage cost.

In the future, there are still many open issues that can be further explored in this new-born system. First, we will research for better task clustering and resource state monitoring methods in cloud computing. In addition to research strategies for system efficiency and load balancing, energy efficiency optimization can also be studied. Second, the computation-intensive and bandwidth-intensive tasks may seriously interfere with each other in cloud computing. We will present an interference prediction model from the proposed SPSLAM framework that mitigates the interference effects and greatly improves the system performance. Finally, we will apply the SPSLAM framework to more practical applications such as the field of mobile edge computing. We will further prove its superiority and application value in MEC. These are problems that are worth taking further study.