CN103812949B - A kind of task scheduling towards real-time cloud platform and resource allocation methods and system - Google Patents

Abstract

The present invention relates to a kind of task scheduling towards real-time cloud platform and resource allocation methods and system, obtain the operation conditions of cloud platform including global state memory module, operation conditions is reported global state monitoring module；Global state monitoring module, according to operation conditions, utilizes task allocation matrix, task adjacency matrix and mask code matrix to formulate corresponding scheduling strategy；In real-time cloud platform, carry out according to scheduling strategy that node is driving and/or task-driven type task scheduling is distributed with resource, the present invention takes into full account the relation between task, the traffic reduced between node, reduces bandwidth pressure when distributing task, thus improves platform property；The various situations of cloud platform dynamic dispatching can be well adapted to, it is ensured that cloud platform moment in running keeps higher calculated performance and resource utilization；And time complexity is low, it is suitable in the cloud environment with extensive node and big task amount disposing using.

Description

Task scheduling and resource allocation method and system for real-time cloud platform

Technical Field

The invention relates to the field of real-time cloud computing, in particular to a task scheduling and resource allocation method and system for a real-time cloud platform.

Background

The volume of data in today's society is expanding and data is increasingly emerging in large, continuous streams. The value of data decreases over time, so it is desirable to process data as soon as they appear, rather than caching them for batch processing. For example, a search engine processes thousands of queries per second, each page containing multiple advertisements, requiring a low-latency, scalable, highly reliable processing engine for timely processing of user feedback. The traditional DBMS or the method for processing the real-time data stream by adopting the Map/Reduce is difficult to meet the application requirement.

For this reason, many stream computing platforms have appeared at home and abroad, such as the open source stream computing platform S4(Simple Scalable Streaming System) of Yahoo |, the stream developed by Twitter, the commercial platform StreamBase, the stream processing System Puma of Facebook, and the like; there are many similar systems in China, including Baidu next generation data stream system DStream, Taobao real-time stream data analysis platform Beatles, etc. The distributed systems can remarkably improve the data processing capacity and reduce the data processing delay.

The new requirement for low-delay mass data stream processing brings new challenges to scheduling and resource allocation between tasks and nodes, and the current mainstream real-time cloud platform has the following problems:

1. in the existing real-time cloud platform, such as Storm of Twitter, tasks are allocated as independent units, the interrelation among the tasks is not considered, and actually, from the viewpoint of improving the platform efficiency, the interrelated tasks should be allocated to the same or adjacent nodes;

2. the existing real-time cloud platform only considers the use conditions of a CPU and a memory of a task, and does not consider the communication traffic among the tasks and the upstream and downstream relations of the tasks;

3. the existing real-time cloud platform only considers the problem of initial or static allocation, ignores the important characteristics that the platform is open and tasks and nodes are dynamically changed, and the allocation strategy in the operation process of the platform becomes an important factor for limiting the efficiency of the platform;

4. the classic multi-core task allocation algorithm is high in complexity and has advantages under the conditions of few cores and few tasks, and the data volume, the task volume and the node scale of the cloud platform exceed the processing range of the traditional algorithm, so that the allocation algorithm of the real-time cloud platform is urgent and necessary.

In summary, a task scheduling and resource allocation algorithm with low time complexity, which can meet the conditions of dynamic computing of a real-time cloud platform, dynamic change of a cloud environment, and the like, is needed to improve the task allocation efficiency and the resource utilization rate of the cloud platform.

Disclosure of Invention

The invention aims to solve the technical problem of the prior art, and provides a task scheduling and resource allocation method and system for a real-time cloud platform, which have low time complexity, can meet the requirements of task scheduling and resource allocation under the conditions of dynamic computation of the real-time cloud platform, dynamic change of a cloud environment and the like, and can effectively improve the task allocation efficiency and the resource utilization rate of the cloud platform.

The technical scheme for solving the technical problems is as follows: a task scheduling and resource allocation method facing a real-time cloud platform comprises the following steps:

step 1: the global state storage module acquires the running state of the cloud platform and reports the running state to the global state monitoring module;

step 2: the global state monitoring module utilizes a task allocation matrix ST, a task adjacency matrix TT and a mask matrix TTM to formulate a corresponding scheduling strategy according to the running condition;

and step 3: and performing node-driven and/or task-driven task scheduling and resource allocation in the real-time cloud platform according to the scheduling strategy.

The invention has the beneficial effects that:

1. when the tasks are distributed, the relation among the tasks is fully considered, the communication traffic among the nodes is reduced, and the bandwidth pressure is reduced, so that the platform performance is improved;

2. the method is well suitable for various conditions of dynamic scheduling of the cloud platform, and ensures that the cloud platform keeps higher computing performance and resource utilization rate all the time in the operation process;

3. the method is low in computation complexity and suitable for being deployed and used in a cloud environment with large-scale nodes and large task amount.

On the basis of the technical scheme, the invention can be further improved as follows.

Further, the task allocation matrix ST is a matrix of n rows and m columns, the rows representing nodes, the columns representing tasks,

the task adjacency matrix TT is a matrix with m rows and m columns and represents the connection condition between tasks,

the mask matrix TTM is a matrix with m rows and m columns, represents the internal connection condition between tasks in a node, is multiplied by the task adjacent matrix TT, and the obtained result represents the external connection condition between the tasks,

further, in step 3, the node-driven task scheduling and resource allocation conditions include conditions of newly added nodes, node overload, node downtime, and node scheduled removal;

a1. aiming at the condition of a newly added node, specifically, a row is newly added in a task allocation matrix ST, and corresponding elements are set to be zero;

a2. aiming at the condition of node overload, the method specifically realizes that a target node is selected, a task to be migrated selected from the overloaded node is migrated to the target node, a task distribution matrix ST and a mask matrix TTM are correspondingly modified,

selecting a destination node to meet the condition that the destination node is not overloaded; the number of connections between the overload node and the destination node is maximum;

selecting a task to be migrated on the overload node to meet the condition that the value obtained by subtracting the number of the external connections generated by task migration from the number of the internal connections generated by the task migration is the minimum;

a3. aiming at the condition of node downtime, the specific implementation is that a target node is selected for each task on the downtime node, the tasks on the downtime node are sequentially migrated to the corresponding target nodes, and meanwhile, a task distribution matrix ST and a mask matrix TTM are correspondingly modified;

selecting a target node to meet the condition that the number of external connections between the task to be migrated and the corresponding target node is the largest;

a4. specifically, for the case of node plan removal, the task allocation flag of a node to be removed is set to be in a state that a new task cannot be allocated, then all tasks on the node are waited for to finish running, the node is removed, all elements of a corresponding row of the node in a task allocation matrix ST are 0, and the row is removed.

Further, for the node overload situation, the specific conditions for selecting the destination node are as follows,

A^T×M^sd×A+A^T×M^ds×A≥A^T×M^sk×A+A^T×M^ks×A

k∈[1，n]，A＝[1…1]^T

wherein M is^sdIndicating an overloaded node n_sTo the destination node n_dSituation of issuing a connection, M^dsRepresenting a destination node n_dTo the overload node n_sSituation of issuing a connection, M^skIndicating an overloaded node n_sTo node n_kSituation of issuing a connection, M^ksRepresenting a node n_kNode n_sCase of outgoing connection, node n_dAnd node n_kAre all non-overloaded nodes.

Further, for the case of node overload, an overloaded node n is selected_sThe specific conditions of the upper task to be migrated are as follows:

M^ss(p，：)×A+A^T×M^ss(：，p)-M^ds(：，p)×A-A^T×M^sd(p，：)

≤M^ss(k，：)×A+A^T×M^ss(：，k)-M^ds(：，k)×A-A^T×M^sd(k，：)

$\∀k{t}_k\∈n_s,A={[1...1]}^T$

wherein M is^ss(p,: indicates task t_pTo the overload node n_sThe other task issues an interconnect condition, Mss (: p) denotes node n_sTo task t by other tasks_pIssuing an in-connection condition, M^sd(p,: indicates task t_pTo node n_dThe upper task sends out the external connection condition; m^ds(p) represents a node n_dTask on overload node_pThe situation of the external connection is sent out,

M^ss(p，：)×A+A^T×M^ss(p) indicates a cause task t_pThe number of internal connections that occur by migration, M, becoming external connections^ds(：，p)×A+A^T×M^sd(p,: indicates a cause task t_pThe number of external connections that appear by migration becoming internal connections;

similarly, the right side of the inequality represents the cause migration task t_kAnd the occurrence of an internal connection becomes the difference between an external connection and an external connection becoming an internal connection.

Further, aiming at the condition that the node is down, the node n is the down node n_sOn each task selects a destination node n_dThe conditions specifically met are that,

M^sd(p，：)×A+A^T×M^ds(：，p)≥M^si(p，：)×A+A^T×M^is(：，p)

$\∀i\∈[1,n],A={[1...1]}^T$

wherein M is^sd(p,: indicates that a task t needs to be migrated_pTo the destination node n_dSending out external connection condition of the upper task; m^ds(p) denotes the destination node n_dTask t for upper task to need migration_pCase of outgoing connection, M^sd(p，：)×A+A^T×M^ds(p) is task t_pWith destination node n_dThe total number of external connections of the upper task; m^si(p,: indicates that a task t needs to be migrated_pTo node n_iSending out external connection condition of the upper task; m^is(p) represents a node n_iTask t for upper task to need migration_pCase of outgoing connection, M^si(p，：)×A+A^T×M^is(p) is task t_pAnd node n_iThe total number of external connections of the upper task;

selecting and migrating task t_pTaking the node with the largest number of connections as a task t_pDestination node of, will task t_pMigrating to destination node n_dRemoving t from the allocation matrix ST_pAnd forming a new matrix by corresponding column vectors.

Further, in step 3, the task-driven task scheduling and resource allocation conditions include a newly added task, normal task ending, abnormal task interruption and active task migration;

b1. aiming at the situation of the newly added task, the method specifically realizes that the node with the maximum total connection number of the newly added task is calculated by utilizing a task adjacency matrix TT and is used as a target node, the newly added task is distributed to the calculated target node, and meanwhile, a task distribution matrix ST, a task adjacency matrix TT and a mask matrix TTM are correspondingly modified;

b2. aiming at the condition that the task is normally finished, specifically realizing that a task allocation matrix ST removes a column corresponding to the normally finished task, removes a corresponding row and column in a task adjacent matrix TT, and modifies an element corresponding to a mask matrix TTM;

b3. specifically, the task is executed again firstly aiming at the condition of task abnormal interruption, if the task is still abnormally interrupted, the task is put into a task queue to wait for redistribution, and a task distribution matrix ST, a task adjacent matrix TT and a mask matrix TTM are correspondingly modified;

b4. specifically, the task to be migrated is directly migrated to a destination node designated by a user, and a task allocation matrix ST, a task adjacency matrix TT and a mask matrix TTM are correspondingly modified.

Further, aiming at the situation of the newly added task, the newly added task t is_newSelecting a destination node n_dThe specific conditions of (a) are,

$A^T\×{\left(M_{\mathrm{send}}^d\right)}^T+A^T\×M_{\mathrm{recv}}^d\≥A^T\×{\left(M_{\mathrm{send}}^i\right)}^T+A^T\×M_{\mathrm{recv}}^i$

$\∀i\∈[1,n],A={[1...1]}^T$

wherein,indicating a newly added task t_newTo the destination node n_dThe situation that the upper task sends out connection;representing a destination node n_dTo the newly added task t_newWhen connection is sent out, the sum of the two is the newly added task t_newAnd destination node n_dThe total number of connections between; representative newly added task t behind inequality_newAnd other nodes n_iTotal number of connections between, selection of and addition of tasks t_newTaking the node with the largest number of connections as a task t_newThe destination node of (1).

Another technical solution of the present invention for solving the above technical problems is as follows: a real-time cloud platform-oriented task scheduling and resource allocation system comprises a client, a global state monitoring module, a global state storage module and a plurality of working nodes;

the client is used for submitting the tasks to the corresponding paths of the global state storage module, so that each working node can obtain the corresponding tasks;

the global state storage module is used for acquiring the operating conditions of all the working nodes and reporting the operating conditions to the global state monitoring module;

the global state monitoring module is used for making a corresponding scheduling strategy by utilizing the task allocation matrix, the task adjacent matrix and the mask matrix according to the reported running state, and carrying out node-driven and task-driven task scheduling and resource allocation according to the scheduling strategy;

and the working node is used for acquiring and executing the corresponding task.

On the basis of the technical scheme, the invention can be further improved as follows.

Further, the global state monitoring module comprises a task allocation matrix unit, a task adjacent matrix unit and a mask matrix unit;

the task allocation matrix unit is used for establishing and modifying a task allocation matrix, and the task allocation matrix is used for expressing the corresponding relation between tasks and working nodes;

the task adjacency matrix unit is used for establishing and modifying a task adjacency matrix, and the task adjacency matrix is used for representing the connection relation between tasks;

the mask matrix unit is used for establishing and modifying a mask matrix, and the mask matrix is used for representing the internal connection relation between tasks on a single node.

Drawings

Fig. 1 is a block diagram of a task scheduling and resource allocation system for a real-time cloud platform according to the present invention;

FIG. 2 is a block diagram of the global status monitor module according to the present invention;

FIG. 3 is a flowchart of a task scheduling and resource allocation method for a real-time cloud platform according to the present invention;

fig. 4 is a schematic structural diagram of a task allocation matrix ST after nodes are newly added in embodiment 1 of the present invention;

FIG. 5a shows an overloaded node n according to embodiment 2 of the present invention_sThe task adjacency matrix structure schematic diagram with other nodes;

FIG. 5b shows an overloaded node n according to embodiment 2 of the present invention_sWith destination node n_dThe task adjacency matrix structure between the two is shown schematically;

FIG. 6 shows a down node n according to embodiment 3 of the present invention_sThe task adjacency matrix structure schematic diagram with other nodes;

FIG. 7 is a diagram illustrating a new task t after a new task is added in embodiment 4 of the present invention_newThe task adjacency matrix structure schematic diagram with other nodes;

FIG. 8 shows task t in embodiment 5 of the present invention_eAfter normal completion, the corresponding task adjacency matrix structure schematic diagram;

FIG. 9 shows an embodiment 6 of the present invention in which a task t is actively engaged_pFrom the source node n_sMigration to destination node n_dThe subsequent task allocation matrix structure schematic diagram;

FIGS. 10a-10g illustrate the operation of task scheduling and resource allocation according to embodiments of the present invention.

In the drawings, the components represented by the respective reference numerals are listed below:

100. the system comprises a client side, 200, a global state monitoring module, 300, a global state storage module, 400 work nodes, 201, a task allocation matrix unit, 202, a task adjacency matrix unit, 203 and a mask matrix unit.

Detailed Description

The principles and features of this invention are described below in conjunction with the following drawings, which are set forth by way of illustration only and are not intended to limit the scope of the invention.

Some of the concepts involved in the present invention are presented below.

And (3) node: namely a node, a physical machine or a virtual machine;

connecting: a process of data stream transmission between tasks;

internal connection: connecting tasks on the same node;

external connection: connections between nodes, including outgoing and incoming connections;

a task allocation matrix: the method comprises the following steps that (1) the assignment relationship between tasks and nodes is realized, a row represents a node, a column represents a task, and an element value of 1 represents that the task corresponding to the column is assigned to the node corresponding to the row;

task adjacency matrix: the connection relation between the tasks, wherein the rows and the columns both represent the tasks, if the element value is 1, the connection exists between the tasks corresponding to the rows and the columns and the connection is sent out by the tasks corresponding to the rows and the columns, otherwise, the connection in the direction does not exist between the tasks and the columns;

overload threshold value: and indicating whether the node is overloaded or not, and if the CPU or memory utilization rate of the node exceeds the value, the node is in an overload state, otherwise, the node is in a normal state.

FIG. 1 shows a topology environment of the present invention, in which a server is used as a Client for issuing commands to a cluster, submitting Job and executable programs; three servers are used as a global state storage module (Zookeeper node) and are responsible for global state storage and communication with other modules; two servers are used as a global state monitoring module (Master node), one server monitors the working state of the whole cluster and provides the functions of fault recovery and task migration, and the other server is used as a hot standby; using five servers as Supervisor working nodes and taking charge of monitoring and controlling the Worker process to work; and provide cluster network communication with the switch using a gigabit network card.

The task scheduling and resource allocation system facing the real-time cloud platform comprises a client 100, a global state monitoring module 200, a global state storage module 300 and a plurality of working nodes 400;

the client 100 is configured to submit a task to a corresponding path of the global state storage module, so that each working node obtains the corresponding task;

the global state storage module 200 is configured to obtain the operating conditions of each working node, and report the operating conditions to the global state monitoring module;

the global state monitoring module 300 is configured to formulate a corresponding scheduling policy according to the reported running condition by using the task allocation matrix, the task adjacency matrix and the mask matrix, and perform node-driven and task-driven task scheduling and resource allocation according to the scheduling policy;

the working node 400 is used for acquiring and executing the corresponding task.

As shown in fig. 2, the global status monitoring module 200 includes a task allocation matrix unit 201, a task adjacency matrix unit 202, and a mask matrix unit 203;

the task allocation matrix unit 201 is configured to establish and modify a task allocation matrix, where the task allocation matrix is used to represent a corresponding relationship between a task and a work node;

the task adjacency matrix unit 202 is used for establishing and modifying a task adjacency matrix, and the task adjacency matrix is used for representing the connection relation between tasks;

the mask matrix unit 203 is used for establishing and modifying a mask matrix, and the mask matrix is used for representing the inter-connection relation between tasks on a single node.

Based on the system, the task scheduling and resource allocation method facing the real-time cloud platform is as follows.

As shown in fig. 3, a task scheduling and resource allocation method for a real-time cloud platform includes the following steps:

step 1: the global state storage module acquires the running state of the cloud platform and reports the running state to the global state monitoring module;

step 2: the global state monitoring module utilizes the task allocation matrix, the task adjacency matrix and the mask matrix to formulate a corresponding scheduling strategy according to the running condition;

and step 3: and performing node-driven and task-driven task scheduling and resource allocation in the real-time cloud platform according to the scheduling strategy.

Wherein the task allocation matrix ST is a matrix with n rows and m columns, the rows represent nodes, the columns represent tasks,

the task adjacency matrix TT is a matrix with m rows and m columns and represents the connection condition between tasks,

the mask matrix TTM is a matrix with m rows and m columns, represents the internal connection condition between tasks on the nodes, and is multiplied by the task adjacency matrix TT to ensure that the element value corresponding to the internal connection is 0,

the element of the mask matrix TT is 1, which indicates that there is a connection relationship between 2 tasks corresponding to the row and column where the element is located, and the connection relationship may be external connection or internal connection, and the 2 tasks of the internal connection are located at the same node, and the flow of the internal connection does not pass through the switch, and can be ignored during optimization, so that the value of the element corresponding to the internal connection is set to 0 through the mask, and only the external connection is left.

The invention mainly aims at the problem of dynamic scheduling in a cloud platform, and the dynamic scheduling is divided into two types: node-driven and task-driven.

Aiming at a node driving type, a task allocation matrix ST is updated certainly, because the task allocation matrix ST represents the allocation condition of tasks on nodes; however, no matter how the nodes change, the connection relation between tasks is unchanged, and the connection relation is logical, so the task adjacency matrix TT is not modified; when the task allocation ST changes, the mask matrix TTM also changes, since the element values of TTM are determined by the element values of ST, since

A. A node drive type:

1. newly added node

When a node is newly added to the cloud platform, the number of the node is changed from n to n +1, the size of a corresponding task allocation matrix ST is changed from n × m to (n +1) × m, one row of ST represents the task allocation situation of the node corresponding to the row, the newly added node is represented in ST by adding one row in the matrix, since the node is not allocated with a task, all elements of the newly added node are 0, and the updated allocation matrix ST is as follows:

as shown in fig. 4, in embodiment 1 of the present invention, a node is newly added, and the first n rows are task allocation matrices ST before the cloud platform newly adds the node, and the size is n × m; after adding a node, the size of the task allocation matrix ST becomes (n +1) × m, the last row is an element corresponding to the newly added node, and since no task has been allocated, the element values are all 0.

2. Node overload

Node overload means that when the utilization rate of a CPU or a memory of a node exceeds an overload threshold value, part of tasks on the overload node need to be migrated to other nodes, so that the load of the overload node is recovered to be normal; and (3) processing node overload, comprising the following tasks of selecting a destination node and selecting a task needing migration:

a. selecting a destination node

Suppose node n_sOverload, need to hold n_sTo the destination node n_dThe above step (1);

target node n_dThe selection of (a) should satisfy 2 conditions:

1）n_dnot overloaded;

2) node n_sAnd destination node n_dThe number of connections between is maximum, i.e.

A^T×M^sd×A+A^T×M^ds×A≥A^T×M^sk×A+A^T×M^ks×A

k∈[1，n]，A＝[1…1]^T

Wherein M is^sdRefers to node n_sTask and node n_dTask adjacency matrix block of upper task, representing node n_sTo node n_dThe situation of the connection is issued and,representing a node n_sLast to node n_dTask j on sends out a connection, otherwise it means that there is no such connection; by the same theory, M is known^ds；

A^T×M^sd× A denotes node n_sUp task to node n_dTotal number of connections issued by upper task, A^T×M^ds× A denotes node n_dUp task to node n_sThe sum of the total number of connections sent by the upper task is the node n_sAnd n_dThe number of connections therebetween.

b. Selecting tasks that need migration

Selecting the task to be migrated as t_pThe following requirements are met:

M^ss(p，：)×A+A^T×M^ss(：，p)-M^ds(：，p)×A-A^T×M^sd(p，：)

≤M^ss(k，：)×A+A^T×M^ss(：，k)-M^ds(：，k)×A-A^T×M^sd(k，：)

$\∀k{t}_k\∈n_s,A={[1...1]}^T$

i.e. at the source node n_sUpper, with less selective interconnections and destination node n_dThe task with more external connections is migrated to the destination node n_d；

Wherein M is^ss(p,: indicates task t_pWith its node n_sThe task adjacency matrix of the other task above, which is a row vector, represents the task t_pTo the node n_sThe connection situation of the other tasks above,indicating the presence of a task t_pTo node n_sA connection issued by other tasks, otherwise no such connection exists; for the same reason M^ss(;, p) are similar column vectors; m^sd(p,: indicates task t_pTo node n_dThe upper task sends out the external connection condition; m^ds(;, p) denotes the node n_dTask on overload node_pSending out an external connection condition;

M^ss(p，：)×A+A^T×M^ss(p) indicates a cause task t_pThe number of internal connections that occur by migration, M, becoming external connections^ds(：，p)×A+A^T×M^sd(p,: indicates a cause task t_pThe appearance of external connections by migration becomes the number of internal connections.

FIG. 5a is a task adjacency matrix, n_sThe corresponding rows and columns represent overloaded nodes n_sConnection case of upper task, assuming destination node is n_d，n_sAnd n_dTwo matrix blocks formed by intersecting corresponding rows and columns are the connection condition of tasks on the two nodes, and the matrix block enclosed by a dotted line represents n_sTo n_dIn the case of connections, the matrix blocks enclosed by solid lines represent n_dTo n_sThe sum of the two elements is the total number of external connections between two nodes, n_dIs in all nodes with n_sThe node that is not overloaded with the largest total number of external connections.

FIG. 5b shows an overloaded node n_sAnd destination node n_dTask adjacency matrix between, n_sIs an overloaded node, n_dIs a destination node, t_pIs an overloaded node n_sThe two matrix blocks enclosed by the minus sign represent the task t before migration_pAnd node n_dExternal connection case of, after migration, task t_pOperating at node n_dThese external connections become internal connections, which reduces the total number of external connections; two matrix blocks circled by plus "+" represent task t_pAnd node n_sThe connection between other tasks is internal connection, and the task t is used after the migration_pNo longer belongs to node n_sThese internal connections will become external connections, increasing the total number of external connections.

3. Node downtime

The main reason for causing the node downtime is that the node is overloaded but fails to migrate tasks thereon in time to keep the load normal, all tasks on the downtime node need to be migrated to other nodes at the moment, and the key is to select a proper destination node n_d；

Suppose the downed node is n_sRequiring migrationTask is t_pThe following requirements are met:

$M^{\mathrm{sd}}(p,:)+M^{\mathrm{ds}}(:,p)\≥M^{\mathrm{si}}(p,:)+M^{\mathrm{is}}(:,p),\∀i\∈[1,n]$

i.e. task t_pWith destination node n_dMaximum external connections;

wherein M is^sd(p,: indicates that a task t needs to be migrated_pWith destination node n_dThe task of the upper task is adjacent to the matrix block, is a row vector,indicating the presence of a task t_pTo the destination node n_dA connection issued by a task, otherwise no such connection exists; in the same way, M^ds(: p) represents task t_pWith destination node n_dThe task adjacency matrix of the upper task, which is a column vector,indicating the presence of a destination node n_dLast task to task t needing to be migrated_pIssuing a connection, otherwise no such connection exists, M^sd(p,: and M)^dsThe sum of (p) is task t_pWith destination node n_dThe total number of connections of the upper task;

task t_pMigrating to destination node n_dRemoving t from the allocation matrix ST_pAnd forming a new matrix by corresponding column vectors.

Repeating the above process until the node n_sThere is no task on it.

As shown in FIG. 6, n_sThe part enclosed by the dotted line represents the down node and any task t on the part_k，n_iIs n_sAny node other than t_kCorresponding rows and columns and n_iTwo matrix blocks of intersecting rows and columns represent t_kAnd node n_iThe sum of the elements of the two matrix blocks is t_kAnd n_iThe node which is not overloaded and has the maximum total number of connections is the target node; repeating the above process for n_sFinding a target node for each task, and migrating to the target node until all tasks are migrated;

4. node plan removal

The node plan removal means that a new task is not distributed to the node any more, and the node is removed after all tasks on the node are executed; the specific implementation is that a flag bit is set for each node, the flag bit of a node to be removed is rewritten into an unallocated new task, then all tasks on the node are waited to finish running, all elements of a corresponding row of the node in a task allocation matrix ST are 0, and the row is removed.

B. The task driving type is as follows:

1. newly added task

Cloud platform newly-added task t_newThen, a suitable destination node n needs to be selected for it_dAnd satisfies the following conditions:

$A^T\×{\left(M_{\mathrm{send}}^d\right)}^T+A^T\×M_{\mathrm{recv}}^d\≥A^T\×{\left(M_{\mathrm{send}}^i\right)}^T+A^T\×M_{\mathrm{recv}}^i$

$\∀i\∈[1,n],A={[1...1]}^T$

representing a destination node n_dAnd newly added task t_newThe number of connections is the largest, and the number of external connections can be effectively reduced by distributing the nodes. Wherein,indicating a newly added task t_newWith destination node n_dThe task adjacency matrix between the upper tasks is a row vector, and the element of the row vector is 1 to indicate that the newly added task t exists_newTo the destination node n_dA task on sends out a connection, otherwise no such connection exists;

indicating a newly added task t_newTo the destination node n_dThe total number of connections that are sent out,representing a destination node n_dTask on to newly increase t_newThe sum of the total number of the issued connections is the newly added task t_newAnd destination node n_dThe total number of connections between.

As shown in FIG. 7, t_newIs a newly assigned task, n_dIs t_newDestination node to be migrated, t_newThe task adjacency matrix blocks between other tasks are arranged in the last row and the last column of the original task adjacency matrix, t_newCorresponding rows and n_dThe matrix block of intersecting corresponding columns is t_newTo n_dThe case of an outgoing connection, t_newCorresponding column sum n_dThe matrix block formed by intersecting corresponding rows represents n_dTo t_newThe sum of the two sent connection conditions is t_newAnd n_dThe node corresponding to the maximum total number of external connections is t_newA destination node of, will t_newAnd migrating to the node.

2. Task completion

When the task is normally finished, the column corresponding to the finished task in the distribution matrix ST needs to be removed, the corresponding row and column in the task adjacent matrix TT are removed, and the element corresponding to the mask matrix TTM is modified.

As shown in FIG. 8, task t_eAfter the execution is finished, the normal operation is finished, and the part in the dotted line is t_eIn the case of a connection in the task adjacency matrix TT, the row and column are removed; similarly, the corresponding column is removed from the task allocation matrix ST, and the column associated with t is deleted from the mask matrix TTM_eThe relevant elements.

3. Task exception interrupts

And re-executing the task, if the abnormal interruption still occurs, indicating that the task is not suitable for running on the node, re-putting the task into the task queue, and waiting for distribution.

4. Active migration of tasks

The active migration of the task means that a certain task is migrated to a certain node determined by a user, and in this case, the task can be directly migrated without algorithm intervention.

As in fig. 9, task t_pSlave node n_sMigrating to node n_dIn the distribution matrix ST, node n_sThe corresponding element changes from 1 to 0, and node n_dThe corresponding element is changed from 0 to 1.

And (3) operating results:

FIG. 10a is the original state of cloud platform nodes and tasks, with 4 nodes (nodes 1, 2, 3, 4) and 4 tasks (t)₁、t₂、t₃、t₄) The arrow indicates the connection between tasks, the connection is from the task where the arrow starting point is located to the task where the arrow ending point is located, and the corresponding task allocation matrix ST and the corresponding task adjacency matrix TT are arranged on the right side of the connection.

Fig. 10b is an operation result of the newly added node, the cloud platform newly added node 5 and the task allocation matrix ST newly added a row at the end, and since no task is allocated yet, all element values of the row are 0, and TT is unchanged.

On the basis of fig. 10b, assuming that the node 3 is overloaded, using the algorithm in the specific embodiment, the nodes except the node 3 are not overloaded, and a part of tasks on the overloaded node 3 need to be migrated at present, a destination node is selected for the task to be migrated first, the number of external connections between the nodes 2 and 4 and the node 3 is the largest and is 1, the number of connections between the nodes 1 and 5 and the node 3 is 0, and it is known that the load of the node 4 is lower than that of the node 2 according to other conditions, so the node 4 is selected as the destination node; second, it is used forChoosing the hypothesis to be migrated, assuming the migration task t₂After migration of t₂Is 2, assuming migration t₃After migration of t₃Is 1, is less than 2, so migration t is selected₃Will t₃And migrating to the node 4, rewriting the 3 rd row and 3 rd column elements into 0, rewriting the 4 th row and 3 rd column elements into 1 in the corresponding task allocation matrix ST, keeping the rest elements unchanged, and showing the migration operation result in fig. 10c, wherein TT is unchanged.

On the basis of fig. 10c, assuming that the node 2 is a down node, fig. 10d is an operation result of the node down, the node 2 in the dotted line box represents the down node, and according to the algorithm in the specific implementation, t needs to be calculated₁Migrate to other nodes, assume t₁After migration to nodes 1, 4, 5, t₁Assuming that t is 1 after migration to node 3₁Is 0 and less than 1, node 3 is selected as the destination node and task t on node 2 is taken₁The node moves to the node 3, and the element in the 2 nd row and the 1 ST column is rewritten to 0 and the element in the 3 rd row and the 1 ST column is rewritten to 1 in the corresponding task assignment matrix ST, and the task adjacency matrix TT is unchanged.

In FIG. 10e, a new task t is added based on the state of FIG. 10c₅According to the algorithm in the specific embodiment, t₅The number of connections to nodes 1, 2, 3, 4, and 5 is 0, 1, 0, and 0, respectively, and the number of connections to node 3 is the largest, so node 3 is selected as t₅The destination node of (1) adds a column t to the corresponding task allocation matrix ST₅The initial values of the elements are all 0, the element values of the 3 rd row and the 5 th column are rewritten to be 1, the task adjacency matrix TT is added by one row and one column, the initial values of the elements are all 0, then the 3 rd row and the 5 th column of the task adjacency matrix TT are rewritten to be 1, and the values of the rest elements are unchanged.

In FIG. 10f, task t₅Execution ends, indicated by the dashed oval block, with row 3 and column 5 elements rewritten to 0 in the corresponding task assignment matrix ST, and column 5 removed, with row 5 and column 5 removed in the corresponding task adjacency matrix TT.

In the context of figure 10g of the drawings,task t₁The data is actively migrated to the node 1, and the element in the 2 nd row and the 1 ST column is rewritten to 0, and the element in the 1 ST row and the 1 ST column is rewritten to 1 in the corresponding task assignment matrix ST, and the task adjacency matrix TT is unchanged.

The optimization effect is mainly evaluated according to the following indexes:

the task distribution average AVG represents the difference value of the number of tasks distributed on the node with the maximum number of tasks and the node with the minimum number of tasks:

$\mathrm{AVG}=\max \underset{j=1}{\overset{m}{\mathrm{\Σ}}}{\mathrm{st}}_{\mathrm{ij}}-\min \underset{j=1}{\overset{m}{\mathrm{\Σ}}}{\mathrm{st}}_{\mathrm{ij}}$

switch traffic COMM, number of external connections flowing through the switch:

A＝[1…1]^T

COMM=A^T×(TT*TTM)×A

wherein, TT is a task adjacency matrix representing the connection condition between tasks (including the total condition of internal connection and external connection), TTM is a mask matrix (representing the internal connection condition between tasks in a node), and the result obtained by multiplying TT and TTM is the external connection condition between tasks.

The above description is only for the purpose of illustrating the preferred embodiments of the present invention and is not to be construed as limiting the invention, and any modifications, equivalents, improvements and the like that fall within the spirit and principle of the present invention are intended to be included therein.

Claims (9)

1. A task scheduling and resource allocation method for a real-time cloud platform is characterized by comprising the following steps:

step 1: the global state storage module acquires the running state of the cloud platform and reports the running state to the global state monitoring module;

step 2: the global state monitoring module utilizes a task allocation matrix ST, a task adjacency matrix TT and a mask matrix TTM to formulate a corresponding scheduling strategy according to the running condition;

and step 3: performing node-driven and/or task-driven task scheduling and resource allocation in the real-time cloud platform according to the scheduling strategy;

the task allocation matrix ST is a matrix of n rows and m columns, the rows representing nodes, the columns representing tasks,

the task adjacency matrix TT is a matrix with m rows and m columns and represents the connection condition between tasks,

the mask matrix TTM is a matrix with m rows and m columns, represents the internal connection condition between tasks in a node, is multiplied by the task adjacent matrix TT, and the obtained result represents the external connection condition between the tasks,

2. the real-time cloud platform-oriented task scheduling and resource allocation method according to claim 1, wherein in step 3, the node-driven task scheduling and resource allocation conditions include conditions of adding a new node, overloading a node, downtime of a node, and removing a node plan;

a1. aiming at the condition of a newly added node, specifically, a row is newly added in a task allocation matrix ST, and corresponding elements are set to be zero;

a2. aiming at the condition of node overload, the method specifically realizes that a target node is selected, a task to be migrated selected from the overloaded node is migrated to the target node, a task distribution matrix ST and a mask matrix TTM are correspondingly modified,

selecting a destination node to meet the condition that the destination node is not overloaded; the number of connections between the overload node and the destination node is maximum;

selecting a task to be migrated on the overload node to meet the condition that the value obtained by subtracting the number of the external connections generated by task migration from the number of the internal connections generated by the task migration is the minimum;

a3. aiming at the condition of node downtime, the specific implementation is that a target node is selected for each task on the downtime node, the tasks on the downtime node are sequentially migrated to the corresponding target nodes, and meanwhile, a task distribution matrix ST and a mask matrix TTM are correspondingly modified;

selecting a target node to meet the condition that the number of external connections between the task to be migrated and the corresponding target node is the largest;

a4. specifically, for the case of node plan removal, the task allocation flag of a node to be removed is set to be in a state that a new task cannot be allocated, then all tasks on the node are waited for to finish running, the node is removed, all elements of a corresponding row of the node in a task allocation matrix ST are 0, and the row is removed.

3. The real-time cloud platform-oriented task scheduling and resource allocation method according to claim 2, wherein specific conditions for selecting the destination node for the node overload condition are as follows,

A^T×M^sd×A+A^T×M^ds×A≥A^T×M^sk×A+A^T×M^ks×A

k∈[1，n]，A＝[1 … 1]^T

wherein M is^sdIndicating an overloaded node n_sTo the destination node n_dSituation of issuing a connection, M^dsRepresenting a destination node n_dTo the overload node n_sSituation of issuing a connection, M^skIndicating an overloaded node n_sTo node n_kSituation of issuing a connection, M^ksRepresenting a node n_kTo node n_sCase of outgoing connection, node n_dAnd node n_kAre all non-overloaded nodes.

4. The real-time cloud platform-oriented task scheduling and resource allocation method according to claim 2, wherein the method comprisesCharacterised in that for the case of node overload, an overloaded node n is selected_sThe specific conditions of the upper task to be migrated are as follows:

$\begin{array}{c}{M}^{ss}\left(p,:\right)\×A+A^T\×M^{ss}\left(:,p\right)-M^{ds}\left(:,p\right)\×A-A^T\×M^{sd}\left(p,:\right)\\ \≤M^{ss}\left(k,:\right)\×A+A^T\×M^{ss}\left(:,k\right)-M^{ds}\left(:,k\right)\×A-A^T\×M^{sd}\left(k,:\right)\\ \∀k{t}_k\∈n_s,A={\left[\begin{array}{ccc}1& ...& 1\end{array}\right]}^T\end{array}$

wherein M is^ss(p,: indicates task t_pTo the overload node n_sThe other task issues an interconnect condition, M^ss(p) represents a node n_sTo task t by other tasks_pIssuing an in-connection condition, M^sd(p,: indicates task t_pTo node n_dThe upper task sends out the external connection condition; m^ds(p) represents a node n_dTask on overload node_pThe situation of the external connection is sent out,

M^ss(p，：)×A+A^T×M^ss(p) indicates a cause task t_pThe number of internal connections that occur by migration, M, becoming external connections^ds(：，p)×A+A^T×M^sd(p,: indicates a cause task t_pThe number of external connections that appear by migration becoming internal connections;

in the same wayThe right side of the inequality represents the cause migration task t_kAnd the occurrence of an internal connection becomes the difference between an external connection and an external connection becoming an internal connection.

5. The method for scheduling and allocating tasks and resources based on the real-time cloud platform as claimed in claim 1, wherein the node n is a down node n according to the condition that the node is down_sOn each task selects a destination node n_dThe conditions specifically met are that,

$\begin{array}{c}{M}^{sd}\left(p,:\right)\×A+A^T\×M^{ds}\left(:,p\right)\≥M^{si}\left(p,:\right)\×A+A^T\×M^{is}(:,p)\\ \∀i\∈\[1,n\],A={\left[\begin{array}{ccc}1& ...& 1\end{array}\right]}^T\end{array}$

wherein M is^sd(p,: indicates that a task t needs to be migrated_pTo the destination node n_dSending out external connection condition of the upper task; m^ds(p) denotes the destination node n_dTask t for upper task to need migration_pCase of outgoing connection, M^sd(p，：)×A+A^T×M^ds(p) is task t_pWith destination node n_dThe total number of external connections of the upper task; m^si(p,: indicates that a task t needs to be migrated_pTo node n_iSending out external connection condition of the upper task; m^is(p) represents a node n_iTask t for upper task to need migration_pSend out external connectionIn case of (1), M^si(p，：)×A+A^T×M^is(p) is task t_pAnd node n_iThe total number of external connections of the upper task;

selecting and migrating task t_pTaking the node with the largest number of connections as a task t_pDestination node of, will task t_pMigrating to destination node n_dRemoving t from the allocation matrix ST_pAnd forming a new matrix by corresponding column vectors.

6. The real-time cloud platform-oriented task scheduling and resource allocation method according to claim 1, wherein in step 3, the task-driven task scheduling and resource allocation conditions include newly added tasks, normal task termination, abnormal task interruption and active task migration;

b1. aiming at the situation of the newly added task, the method specifically realizes that the node with the maximum total connection number of the newly added task is calculated by utilizing a task adjacency matrix TT and is used as a target node, the newly added task is distributed to the calculated target node, and meanwhile, a task distribution matrix ST, a task adjacency matrix TT and a mask matrix TTM are correspondingly modified;

b2. aiming at the condition that the task is normally finished, specifically realizing that a task allocation matrix ST removes a column corresponding to the normally finished task, removes a corresponding row and column in a task adjacent matrix TT, and modifies an element corresponding to a mask matrix TTM;

b3. specifically, the task is executed again firstly aiming at the condition of task abnormal interruption, if the task is still abnormally interrupted, the task is put into a task queue to wait for redistribution, and a task distribution matrix ST, a task adjacent matrix TT and a mask matrix TTM are correspondingly modified;

b4. specifically, the task to be migrated is directly migrated to a destination node designated by a user, and a task allocation matrix ST, a task adjacency matrix TT and a mask matrix TTM are correspondingly modified.

7. The real-time cloud platform-oriented task scheduling and resource allocation formula of claim 1Method, characterized in that, for the case of a newly added task, it is the newly added task t_newSelecting a destination node n_dThe specific conditions of (a) are,

$\begin{array}{c}{A}^T\×{\left(M_{send}^d\right)}^T+A^T\×M_{recv}^d\≥A^T\×{\left(M_{send}^i\right)}^T+A^T\×M_{recv}^i\\ \∀i\∈\[1,n\],A={\left[\begin{array}{ccc}1& ...& 1\end{array}\right]}^T\end{array}$

wherein,indicating a newly added task t_newTo the destination node n_dThe situation that the upper task sends out connection;representing a destination node n_dTo the newly added task t_newWhen connection is sent out, the sum of the two is the newly added task t_newAnd destination node n_dThe total number of connections between; representative newly added task t behind inequality_newAnd other nodes n_iTotal number of connections between, selection of and addition of tasks t_newNumber of connectionsThe most nodes as tasks t_newThe destination node of (1).

8. A system for realizing any real-time cloud platform-oriented task scheduling and resource allocation method in claims 1-7 is characterized by comprising a client, a global state monitoring module, a global state storage module and a plurality of working nodes;

the client is used for submitting the tasks to the corresponding paths of the global state storage module, so that each working node can obtain the corresponding tasks;

the global state storage module is used for acquiring the operating conditions of all the working nodes and reporting the operating conditions to the global state monitoring module;

the global state monitoring module is used for making a corresponding scheduling strategy by utilizing the task allocation matrix, the task adjacent matrix and the mask matrix according to the reported running state, and carrying out node-driven and task-driven task scheduling and resource allocation according to the scheduling strategy;

and the working node is used for acquiring and executing the corresponding task.

9. The real-time cloud platform-oriented task scheduling and resource allocation system according to claim 8, wherein the global state monitoring module includes a task allocation matrix unit, a task adjacency matrix unit and a mask matrix unit;

the task allocation matrix unit is used for establishing and modifying a task allocation matrix, and the task allocation matrix is used for expressing the corresponding relation between tasks and working nodes;

the task adjacency matrix unit is used for establishing and modifying a task adjacency matrix, and the task adjacency matrix is used for representing the connection relation between tasks;

the mask matrix unit is used for establishing and modifying a mask matrix, and the mask matrix is used for representing the internal connection relation between tasks on a single node.