CN103701886A - Hierarchic scheduling method for service and resources in cloud computation environment - Google Patents

Abstract

A hierarchical scheduling method for services and resources in a cloud computing environment; it includes submitting user requests, dividing task units, defining computing models, defining storage models, defining service resolution processes, service scheduling processes, resource scheduling processes, and evaluating scheduling Etc stage: the present invention defines the mathematical model of the service composition file and applies it to the cloud environment; firstly, the service composition file is parsed to determine the service priority; the resource pool is used to classify the tasks, and the service can use the appropriate Resource allocation methods execute; scheduling methods take into account data locality and relative service completion rates. It can be observed from simulation experiments that the hierarchical scheduling method proposed by the present invention can improve resource utilization, and achieve a higher service completion rate compared with the default FIFO scheduling of Hadoop. The method proposed by the invention satisfies the requirements of users and service providers through efficient scheduling and redistribution of priorities.

Description

A service and resource hierarchical scheduling method in cloud computing environment

technical field

The invention belongs to the technical field of computer network application and system structure, and in particular relates to a service and resource hierarchical scheduling method in a cloud computing environment.

Background technique

Cloud computing has changed the traditional way of using infrastructure. Among them, effective resource management and service scheduling can solve the problem of excessive consumption or underutilization of resources and improve user satisfaction. Due to the diversity of user needs and service attributes, it is very important to study scheduling algorithms for different applications and service models in cloud environments, and to perform service composition in cloud environments to achieve customization to user requests. To implement service composition in a cloud computing environment, it is important to service scheduling and resource allocation and to meet QoS requirements on this basis. Service composition is the process of creating new services by combining and connecting existing services in the cloud computing environment. Service scheduling should conform to the dynamic, distributed and shareable characteristics of cloud computing. The allocation of resources is to enable all services in the workflow to achieve their respective performance targets. In addition, in the cloud computing platform, the QoS-based resource allocation mechanism can perform differentiated scheduling on user requests.

Cloud computing services provide a three-tier architecture. The entire cloud architecture includes resource providers, service providers and users. Service providers lease resources and create virtual machine instances to provide services to users; resource providers are responsible for scheduling virtual machines to corresponding physical machines; users submit applications for individual services or service combinations. A service provider's services vary with factors such as time or cost.

Cloud computing is characterized by data-intensive and computing-intensive development. Many applications are based on the Map/Reduce model to improve performance. Map/Reduce is a distributed parallel computing programming model proposed by Google for parallel processing of large-scale data. Inspired by functional programming languages, the Map/Reduce model splits large-scale data processing jobs into several Map tasks that can run independently, assigns them to different machines for execution, and generates intermediate files in a certain format, and then several The Reduce task merges these intermediate files to obtain the final output file.

Previous research on service scheduling algorithms in the Map/Reduce model includes: FIFO scheduling algorithms will occupy system resources for a long time. After other jobs are submitted, they cannot be processed in time due to the lack of system resources, which affects the interactive capabilities of the system and users. The use experience; the fair share scheduling algorithm and the computing power scheduling algorithm need to be pre-configured, so whether the configuration is appropriate or not determines the performance of the system. Hershey's system performance has a large gap.

Contents of the invention

In order to solve the above problems, the object of the present invention is to provide a service and resource hierarchical scheduling method in a cloud computing environment.

In order to achieve the above object, the service and resource hierarchical scheduling method under the cloud computing environment provided by the present invention includes the following steps in order:

1) S01 stage of submitting user requests: users submit requests to service providers, including individual services or service combinations;

2) The S02 stage of dividing task units: the service provider receives user requests and divides them into tasks of smaller units, and the task units are scheduled after obtaining the priority;

3) The S03 stage of defining the computing model: define the computing resource model responsible for service execution from the service level, and the computing resource model is divided into a service layer and a virtual layer;

4) Define the S04 stage of the storage model: define the storage resource model responsible for data from the task level, which is divided into a service layer and a data access layer;

5) Define the S05 stage of the service analysis process: define the service analysis process, decompose the service requested by the user into a service composition model according to the defined scheduling model, and analyze the service files in the service composition model, including calculating service execution time, service Weight and data transfer weight, and rank services based on calculation results and service paths;

6) The S06 stage of the service scheduling process: three resource pools are predefined, and the resource pools measure and compare Map/Reduce services according to the Map/Consumption ratio, decompose the ranked services into tasks, and calculate whether the task completion rate is greater than the tasks in the resource pool The threshold defined by the slot, the tasks greater than the threshold are decomposed into three resource pools according to the resources required by the service. The services in different resource pools correspond to different resource allocation methods, and the tasks are executed in the distributed task slots in the resource pool. This is the service scheduling process;

7) The S07 stage of the resource scheduling process: schedule and deploy tasks when there are available task slots in the resource pool, and predefine three resource pool allocation methods. When the TaskTracker in Map/Reduce has available task slots, according to data locality The principle is to select the appropriate task from the resource pool for execution. If the locality of the top three task data matches, assign the highest-ranked task into the task slot. If not, continue to wait; finally complete the overall process of service scheduling and resource scheduling;

8) S08 stage of evaluating scheduling: evaluating scheduling from the aspects of total service completion time and resource utilization.

In the S03 stage, the computing resource model defines three types of tasks: TM-Map tasks, TR-Reduce tasks and non-Map-Reduce tasks.

In the S03 stage, the data blocks defined in the computing resource model are reproducible.

In step 6), three data access levels are set according to the Map/Consumption ratio: Map data input, Map-Reduce intermediate data, and Reduce data output.

The steps 5) to 7) together constitute a hierarchical scheduling model, which improves the service combination execution rate from two aspects of service scheduling and resource scheduling.

The service and resource hierarchical scheduling method under the cloud computing environment provided by the present invention defines the mathematical model of the service combination file and applies it to the cloud environment; firstly, the service combination file is analyzed to determine the service priority; the resource pool is used By classifying tasks, services can be executed using appropriate resource allocation methods based on operational characteristics; scheduling methods take into account data locality and relative service completion rates. It can be observed from simulation experiments that the hierarchical scheduling method proposed by the present invention can improve resource utilization, and achieve a higher service completion rate compared with the default FIFO scheduling of Hadoop. In addition, in order to satisfy both users and service providers, an efficient service scheduling method is needed. The method proposed by the invention satisfies the requirements of users and service providers through efficient scheduling and redistribution of priorities.

Description of drawings

Fig. 1 is a flow chart of the service and resource hierarchical scheduling method under the cloud computing environment provided by the present invention;

FIG. 2 is a schematic diagram of a computing resource model responsible for service execution;

Fig. 3 is a schematic diagram of a storage resource model responsible for data;

4 is a block diagram of the operation process of the service and resource hierarchical scheduling method in the cloud computing environment provided by the present invention;

Figure 5 is a comparison between this method and the total service completion time of FIFO;

Figure 6 is a comparison of resource occupation between this method and FIFO;

Fig. 7 is the completion time of the service in different resource pools in this method;

Detailed ways

The service and resource layered scheduling method under the cloud computing environment provided by the present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments.

As shown in Figure 1, the service and resource hierarchical scheduling method under the cloud computing environment provided by the present invention includes the following steps carried out in order:

1) S01 stage of submitting user requests: users submit requests to service providers, including individual services or service combinations;

2) The S02 stage of dividing task units: the service provider receives user requests and divides them into tasks of smaller units, and the task units are scheduled after obtaining the priority;

3) Defining the S03 stage of the computing model: defining the computing resource model responsible for service execution from the service level. Figure 2 shows the computing resource model, which is divided into a service layer and a virtual layer;

4) Define the S04 stage of the storage model: define the storage resource model responsible for data from the task level. Figure 3 shows the storage resource model, which is divided into a service layer and a data access layer;

5) Define the S05 stage of the service resolution process: define the service resolution process. Decompose the service requested by the user into a service composition pattern (SCP) according to the defined scheduling model, analyze the service files in the service composition pattern, including calculating the service execution time, service weight and data transmission weight, and according to the calculation results and service The path ranks the services;

6) The S06 stage of the service scheduling process: three resource pools are predefined, and the resource pools measure and compare Map/Reduce services according to the Map/Consumption ratio, decompose the ranked services into tasks, and calculate whether the task completion rate is greater than the tasks in the resource pool The threshold defined by the slot, the tasks greater than the threshold are decomposed into three resource pools according to the resources required by the service. The services in different resource pools correspond to different resource allocation methods, and the tasks are executed in the distributed task slots in the resource pool. This is the service scheduling process;

7) The S07 stage of the resource scheduling process: schedule and deploy tasks when there are available task slots in the resource pool, and predefine three resource pool allocation methods. When the TaskTracker in Map/Reduce has available task slots, according to data locality The principle is to select the appropriate task from the resource pool for execution. If the data locality of the top three tasks matches, assign the highest-ranked task to the task slot. If not, continue to wait; finally complete the overall process of service scheduling and resource scheduling.

8) S08 stage of evaluating scheduling: evaluating scheduling from the aspects of total service completion time, resource utilization rate, etc.

In the S03 stage, the computing resource model defines three types of tasks: TM-Map tasks, TR-Reduce tasks and non-Map-Reduce tasks.

In the S03 stage, the data blocks defined in the computing resource model are reproducible.

In step 6), three data access levels are set according to the Map/Consumption ratio: Map data input, Map-Reduce intermediate data, and Reduce data output. Because different deployment methods and services will get different results, resulting in service failure, so MRCT (Map/Reduce consumption time ratio) is used for service classification. The detailed description of the resource pool is reflected in Table 2; Table 3 shows the classification methods of the three resource pools.

In the S07 stage, the configuration of the task slots described in is variable and can dynamically adjust the load nodes.

Step 5-Step 7 together constitute a hierarchical scheduling model, which improves the service combination execution rate from two aspects of service scheduling and resource scheduling.

As shown in Figure 2, in the S03 stage, the steps of the method for defining the computing resource model responsible for service execution are as follows:

From the service layer perspective:

1) Service files. SP=<ID,Start Time,End Time,L-route,C-route,MA>A configuration file describing service attributes. ID indicates the name of the cloud service, and Start Time and End Time indicate the start and end time of service execution, respectively. L-route represents the longest path from the starting service to the current service. C-route represents the longest path (task weight) from the current service to the final service.

2) Operation. MA=<Depend, D _i , D ₀ >, Depend indicates the service that must be executed before executing a certain service, D _i and D ₀ are the data types of service input and output, indicating the resources required by the service.

3) Service combination mode. SCP=<D _i , D ₀ , S _x , BW _x > means service combination mode. D _i and D ₀ represent input data and output data, and S represents a service set. BW _x represents the bandwidth between two nodes. p and q respectively represent the services in the service file, namely S _q ∈ S _x , S _q .D _i =S _p .D ₀ , e represents the bandwidth index between two services.

From the perspective of the virtual layer:

4) Clusters. C=<VM,D> represents a cluster in the cloud. A cluster is a group of loosely coupled computers working together. The cluster consists of virtual machines (VM) and disk files (D). VM represents computing resources, and D represents storage resources.

5) VMs. A VM (Virtual Machine) is a set of computing resources based on physical machines. Each VM contains one or more task slots, which is the smallest execution unit in this method. The number of virtual machines required for a service depends on the application type. In the system model, different types of VMs are scheduled according to user demands.

6) Data blocks. D={d} represents a collection of storage resources, and d=<filename,B> represents a distributed file set in the file system. Each file is divided into data blocks of size 64MB or 128MB, and these data blocks form the dataset. Data blocks in this method are replicable.

As shown in Figure 3, in the S04 stage, the definition method of the storage resource model responsible for data is as follows:

Defined from a task perspective:

Task T={ID, TM|TR|TN|, T _d , D _i , D ₀ , T _r , T _s , T _w , T _ω , T _e , C _r } defines three task types: TM-Map tasks, TR-Reduce tasks and other non-Map-Reduce tasks. Non-Map-Reduce services will be split into TN types. Log task parameters as tasks execute and transfer tasks from TaskTracker to JobTracker. The model is divided into service layer and data access layer; data blocks are distributed in the cloud and managed by the file system; each service in the service file uses access arrows to point to the necessary data blocks; data blocks B3 and B6 in the figure represent the same data ; The dotted arrow indicates that the concurrent execution of S ₂ and S ₃ will cause competition for data block B3; since B6 is a copy of B3, S ₃ may visit B6, and the next service S ₄ will directly enter data block B5.

As shown in Figure 4, the specific operation steps of the service and resource hierarchical scheduling method under the cloud computing environment provided by the present invention are as follows:

1) Decompose the service requested by the user into a service composition pattern (SCP) according to the defined system model, and analyze the service files in the service composition pattern. The action includes calculating the service execution time, service weight and data transmission weight, and according to the calculation Results and service paths rank services; the order in which services are executed is determined by comparing services in the SCP. In service scheduling, consider service dependencies and execution times. The calculation equation for evaluating data transfer time and service execution time is:

$\mathrm{<span\; class="notranslate">\; DT</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}^{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; *</span>\frac{{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{{\mathrm{<span\; class="notranslate">\; BW</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; DataChunkSize</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; TaskSlotsPerVM</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

The parameter α calculates the execution rate of the task, indicating how many virtual machines the service needs to execute at the same time. The data block setting defaults to 64MB or 128MB depending on Hadoop. The parameter TaskSlotPerVM is set to 4 by default.

After the service execution time is calculated, the service execution priority ranking is given. Consider first the L-route. This parameter is used to determine whether the service Sx in the SCP should be executed preferentially. Another parameter used in the ranking represents the pre-execution time of each service. The earliest execution time of Sx can be estimated by this parameter. Finally, the addition of two terms describes parameter ranking and pushes the service ranking list to the next level.

${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; ra</span>}}^{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}}^{\mathrm{<span\; class="notranslate">\; x</span>}}}{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; let\text{'}s\; go</span>}}^{\mathrm{<span\; class="notranslate">\; x</span>}}}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}^{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; depends</span>}}^{\mathrm{<span\; class="notranslate">\; x</span>}}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; e</span>}}^{\mathrm{<span\; class="notranslate">\; the\; y</span>}}}{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}^{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}^{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; SCP</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; e</span>}}^{\mathrm{<span\; class="notranslate">\; the\; y</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

The system needs to set multiple QoS parameter values for tasks and resources to meet user needs. Create a resource matrix and task matrix for resources and tasks, respectively. The equation for user satisfaction is as follows:

$\mathrm{<span\; class="notranslate">\; Sa</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{c}\frac{{\mathrm{<span\; class="notranslate">\; QUR</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}{{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; QUR</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}\\ \mathrm{<span\; class="notranslate">\; else</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; QUR</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ></span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

Task matrix T _n,k with required QoS parameter values to schedule tasks.

Resource matrix R _m,k with required QoS parameter values to set available resources.

Further set the threshold of the QoS parameter of the resource to meet the QoS standard required by the user.

2) Service scheduling process. The present invention defines a collection of three resource pools. The resource pool measures and compares Map/Reduce services according to the Map/Consumption ratio. We set up three data access levels: Map data input, Map-Reduce intermediate data, and Reduce data output. Different deployment methods and services will have different results. So MRCT (Map/Reduce Consumption Time Ratio) is used for service classification. The next step includes decomposing the ranked services into tasks, and calculating whether the task completion rate is greater than the threshold defined in the task slot in the resource pool. If yes, put the highest-ranked service into the resource pool. If not, continue to wait; actions include The tasks greater than the threshold are decomposed into three resource pools according to the resources required by the service. Each resource pool has different resource demand characteristics, and the services in different resource pools correspond to different resource allocation methods. Each service is decomposed into one or more tasks to be executed in distributed task slots. Jobs are split into tasks and assigned to the corresponding resource pools for execution.

Within each resource pool, divide the highest-ranked service into one or more tasks. Task priorities are determined as follows:

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}}}{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; let\text{'}s\; go</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

First, the task weight C-route is calculated by the formula. At this layer, tasks with smaller C-route values will be executed last. The data transmission weight is determined by the data transmission between T _i and T _j , as shown in formula (8). The parameter T _i in equation (9) describes the sum of data transfers. Use this parameter to decide whether task T _i should be scheduled to wait.

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; DataSize</span>}}_{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; rank</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{{\mathrm{<span\; class="notranslate">\; T</span>}}^{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; depends\; on</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}{\mathrm{<span\; class="notranslate">\; max</span>}}{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

3) Resource scheduling process. When there are available task slots in the resource pool, tasks are scheduled and deployed. Three resource pool allocation methods are predefined. The action includes when the TaskTracker in Map/Reduce has available task slots, select the appropriate one from the resource pool according to data locality. Task execution, if the data locality of the top three tasks meets the requirements, assign the highest-ranked task into the task slot, if not, continue to wait; finally complete the overall process of service scheduling and resource scheduling; by default, in Hadoop In the configuration of , the number of Map tasks is usually determined by the total size of the input, and the total number of blocks of the input file is NS _i . The number of Reduce tasks is 0.95 or 1.75 multiplied by the number of Reduce task slots, that is, the total number of virtual machines multiplied by the number of task slots allocated by the system to each virtual machine.

After the initial allocation, when the TaskTracker has available task slots, it will pick a suitable task to execute from the queue in the resource pool. Therefore the distance weight in formula (10) is used to solve the data locality problem. Assuming that there is an available task slot Slot _m , it is necessary to calculate the task T _i , and the related tasks T _i , T _j in it. The formula is used to calculate the average data locality and the completion rate of the candidate task T _i dependent tasks, the smaller the T _i value, the better.

${\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; w</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; depends</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}\frac{{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; d</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; *</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; c</span>}}^{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; bw</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Slots</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; Slots</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; )</span>}}{\mathrm{<span\; class="notranslate">\; count</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; depends</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

Use CPU utilization to estimate the workload on each node. CPU information is an important indicator of the processing capability of heterogeneous multi-core processors. Memory management is very important to the I/O performance of Map/Reduce jobs. When the disk cache available to memory increases, performance increases accordingly. So first make sure there is enough memory space for the nodes. If there is enough memory and the CPU utilization is normal, increase the number of slots to allocate and execute more tasks to make full use of resources. Conversely, due to lack of memory, the number of slots decreases accordingly. The initial task allocation strategy only considers slot availability. When the TaskTracker contains empty slots, it will get the tasks assigned by the JobTracker regardless of the current load of the node. If the slot is configured with an inappropriate task allocation strategy, it may lead to underutilization of resources or system overload. Therefore, in the best case, the socket should be adapted to the configuration of the hardware and the real-time workload of each node. In the present invention, the slot configuration is variable, and the load nodes can be dynamically adjusted. The workload should consider the utilization of CPU, network bandwidth, I/O and other computing resources. The task scheduling plan proposed by the invention takes into account the implementation workload of each node and maximizes the utilization of resources.

Figures 5 to 7 are the simulations of the proposed strategies, the simulation environment focuses on resource competition under different scenarios. It can be seen from the simulation results that using the service and resource hierarchical scheduling method in the cloud computing environment, the total completion time of the service is shorter than that of FIFO, which can effectively avoid resource waste and in I/O-intensive computing mode, the hierarchical scheduling method has better performance than FIFO increased by about 30%. That is, the method of the present invention can effectively improve the resource utilization rate, and achieve a higher service completion rate compared with the default FIFO scheduling in Hadoop.

Table 1 is the division method of three kinds of resource pools proposed by the present invention;

Table 2 shows the resource allocation method proposed by the present invention.

Table 1

Table 2

Claims (5)

1. A service and resource hierarchical scheduling method under a cloud computing environment, characterized in that: it comprises the following steps carried out in order: 1) S01 stage of submitting user requests: users submit requests to service providers, including individual services or service combinations; 2) The S02 stage of dividing task units: the service provider receives user requests and divides them into tasks of smaller units, and the task units are scheduled after obtaining the priority; 3) The S03 stage of defining the computing model: define the computing resource model responsible for service execution from the service level, and the computing resource model is divided into a service layer and a virtual layer; 4) Define the S04 stage of the storage model: define the storage resource model responsible for data from the task level, which is divided into a service layer and a data access layer; 5) Define the S05 stage of the service analysis process: define the service analysis process, decompose the service requested by the user into a service composition model according to the defined scheduling model, and analyze the service files in the service composition model, including calculating service execution time, service Weight and data transfer weight, and rank services based on calculation results and service paths; 6) The S06 stage of the service scheduling process: three resource pools are predefined, and the resource pools measure and compare Map/Reduce services according to the Map/Consumption ratio, decompose the ranked services into tasks, and calculate whether the task completion rate is greater than the tasks in the resource pool The threshold defined by the slot, the tasks greater than the threshold are decomposed into three resource pools according to the resources required by the service. The services in different resource pools correspond to different resource allocation methods, and the tasks are executed in the distributed task slots in the resource pool. This is the service scheduling process; 7) The S07 stage of the resource scheduling process: schedule and deploy tasks when there are available task slots in the resource pool, and predefine three resource pool allocation methods. When the TaskTracker in Map/Reduce has available task slots, according to data locality The principle is to select the appropriate task from the resource pool for execution. If the locality of the top three task data matches, assign the highest-ranked task into the task slot. If not, continue to wait; finally complete the overall process of service scheduling and resource scheduling; 8) S08 stage of evaluating scheduling: evaluating scheduling from the aspects of total service completion time and resource utilization. 2. The service and resource hierarchical scheduling method under the cloud computing environment according to claim 1, characterized in that: in the S03 stage, the computing resource model defines three task types: TM-Map task, TR -Reduce tasks and non-Map-Reduce tasks. 3. The hierarchical scheduling method for services and resources in a cloud computing environment according to claim 1, characterized in that: in the stage S03, the data blocks defined in the computing resource model are reproducible. 4. The service and resource layered scheduling method under the cloud computing environment according to claim 1, characterized in that: in the step 6), three data access levels are set according to the Map/Consumption ratio: Map data input, Map -Reduce intermediate data, reduce data output. 5. The method for hierarchical scheduling of services and resources in a cloud computing environment according to claim 1, characterized in that: the steps 5)-7) together constitute a hierarchical scheduling model, from both service scheduling and resource scheduling Improve service portfolio execution rate.

Images