CN106610866A - Service value constrained task scheduling algorithm in cloud storage environment - Google Patents
Service value constrained task scheduling algorithm in cloud storage environment Download PDFInfo
- Publication number
- CN106610866A CN106610866A CN201610444598.2A CN201610444598A CN106610866A CN 106610866 A CN106610866 A CN 106610866A CN 201610444598 A CN201610444598 A CN 201610444598A CN 106610866 A CN106610866 A CN 106610866A
- Authority
- CN
- China
- Prior art keywords
- nodes
- qos
- task
- cloud storage
- node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 239000011159 matrix material Substances 0.000 claims abstract description 27
- 239000002245 particle Substances 0.000 claims abstract description 4
- 230000001133 acceleration Effects 0.000 claims description 2
- 230000003247 decreasing effect Effects 0.000 claims description 2
- 238000005259 measurement Methods 0.000 claims description 2
- 230000001172 regenerating effect Effects 0.000 claims description 2
- 230000035945 sensitivity Effects 0.000 claims description 2
- 238000004883 computer application Methods 0.000 claims 1
- 238000004364 calculation method Methods 0.000 abstract description 2
- 238000012804 iterative process Methods 0.000 abstract description 2
- 238000005457 optimization Methods 0.000 abstract description 2
- 238000005516 engineering process Methods 0.000 description 4
- 238000000034 method Methods 0.000 description 4
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000013523 data management Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000012384 transportation and delivery Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/48—Program initiating; Program switching, e.g. by interrupt
- G06F9/4806—Task transfer initiation or dispatching
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention provides a service value constrained task scheduling algorithm in a cloud storage environment. On the basis of a particle swarm optimization (PSO), an existence matrix (EM) is defined and introduced to indicate the corresponding relationship between a task and a resource node; due to the EM, an initial solution and a solution have meanings in space; furthermore, for special requirements of the cloud environment, a network Qos parameter is defined and introduced; the state of a current network can be reflected dynamically in real time; therefore, an influence parameter can be dynamically adjusted according to the Qos parameter and the corresponding fitness function in a calculation iterative process; therefore, the purpose of optimizing the algorithm is achieved; and furthermore, a fitness function can be re-defined according to the Qos. By means of the service value constrained task scheduling algorithm in the cloud storage environment provided by the invention, the disadvantage that the solution generated by the traditional algorithm does not exist in a task can be solved; the operation efficiency of the system is increased; and, due to introduction of a network service parameter, users can intuitively feel a scheduling policy by taking the service quality as the centre.
Description
Technical Field
The invention relates to the field of application of a cloud storage computer and task scheduling in a cloud environment.
Background
In recent years, with the rapid increase of various types of information and the development of internet technology, more and more services are provided to users in a cloud form. Cloud computing is an advanced computing technology which is rapidly developed along with computer technology and network technology in recent years, in a traditional computing mode, computing tasks are distributed on individual computers and limited by the individual computing performance of each computer, computing with large task amount is difficult to realize on a single computer, and therefore the appearance of cloud computing solves the computing problem of a large amount of data. Cloud computing is classified into narrow cloud computing and generalized cloud computing. The narrow-sense cloud computing refers to establishing an IT infrastructure, delivering and using the IT infrastructure, and obtaining required resources including hardware resources, an operation platform, software resources and the like on the basis of a network in an on-demand and easily-extensible mode. The generalized cloud computing means that service delivery and use of a user terminal are achieved on the basis of the internet, and required services are obtained in a mode of respectively taking required services and respectively expanding the required services on the basis of network services.
In the aspect of data management, when a user sends a data request to a server, a system provides a relatively optimal data copy and path selection for the user according to a corresponding scheduling strategy, the quality of the scheduling strategy determines the operation processing efficiency of the system to a great extent, and the cloud storage is different from the traditional cloud computing in the aspect of task scheduling. In the existing research on the task scheduling algorithm of the cloud storage, compared with the cloud computing task, the cloud computing task can be provided by any node in the cloud, but the situation that the node does not have data required by the task, namely the situation that an initial solution and an iterative solution obtained after the solving process of the algorithm are useless, can occur in the cloud storage. Meanwhile, the scheduling of the cloud task is influenced due to the change of the network environment.
Disclosure of Invention
The invention provides a task scheduling algorithm with service value constraint in a cloud storage environment aiming at the task scheduling problem in the cloud storage.
The technical scheme of the invention is as follows: the method comprises the steps of defining and introducing an Existence Matrix (EM) to indicate the corresponding relation between tasks and resource nodes on the basis of a Particle Swarm Optimization (PSO), making an initial solution and a solution meaningful in space through the existence matrix, defining and introducing a network quality of service (Qos) according to special requirements of a cloud environment, and dynamically reflecting the state of a current network in real time, so that influence parameters of the Qos can be dynamically adjusted according to the Qos parameters and corresponding fitness functions in the iterative process of calculation, the purpose of optimizing the algorithm is achieved, and the fitness functions are redefined according to the Qos.
The invention has the beneficial effects that: the method overcomes the defect that the solution generated by the traditional algorithm does not exist in the task, improves the operation efficiency of the system, and enables the user to intuitively feel the scheduling strategy taking the service quality as the center by introducing the network service parameters.
Detailed Description
Aiming at the task scheduling problem under cloud storage, the invention elaborates the specific computing process in detail, and the specific implementation steps are as follows:
step 1: a presence matrix is generated.
Step 2: setting of Qos conditions and condition selection.
And step 3: and establishing a fitness function according to the constraint conditions.
And 4, step 4: and generating an initial solution, and iteratively generating a solution set of the data nodes.
And 5: the solution matches the presence matrix and constraint conditions.
The parameter functions and definitions involved in the above steps are described in detail as follows:
step 1: generating presence matrices
Because the nodes of the cloud storage system cannot necessarily provide the data requested by the user, a function describing the corresponding relationship between the scheduling tasks and the resource nodes is defined by the number of tasks to be scheduled, the resource nodes and the number of nodes, and the solution generated from the existence matrix has a spatial meaning, that is, the nodes must contain the required resources.
Let T denote the task to be scheduled, T ═ T1，T2，...，Ti，...Tn]N denotes the number of scheduled tasks, where 1 ≦ i ≦ n, V denotes a node, V ≦ V1，V2，...，Vj，...Vm]And m represents the number of nodes, wherein j is more than or equal to 1 and less than or equal to n, a matrix U of n × m is constructed:
wherein
In a matrix, eijRepresenting a task scheduling vector, the same data may exist on multiple nodes, so eijWhen 1, the task T is expressediAt node VjIs present, eijWhen 0 indicates a taskTiAt node VjIs not present.
Step 2: setting of Qos conditions and condition selection
The Qos constraint is a minimum cost rule selection path which meets the requirements of users or application scenes according to different user or application scenes on the multi-Qos sensitivity, and the Qos parameter is used as the measurement of the current network state and is used forRepresents a node VaTo node VbQos status information in between, which contains three components, i.e., delay (D), jitter (J), bandwidth (B). Building a set of network nodes in the cloud storage into an undirected weighted graph model G (V, E), wherein V represents the nodes, E represents all edges of physically or logically connected nodes, each group of links comprises three components of state information, and the links between task nodes and data nodes are represented by P (s, d),to indicate that: dP(s，d)、JP(s，M)、BP(s，M)(ii) a And M is a link between the task node and the cloud storage node, and if the link is the shortest set, the values of three parameters are calculated as follows:
in the Qos vector, the total delay on link P (s, d) is defined as the minimum from the start point to the end point on the path, so:
jitter is defined as the difference in the mean value of the delay on the path from the source node to the end node
The bottleneck bandwidth of a link is defined as the minimum bandwidth of the link in T:
BP(s，M)＝min{b(i，j)|(i，j)∈P(s，M)
in the above parameters, P (S, d) is the shortest path of the task node with the data node, S is the source node requesting the task, and all nodes V are constrained by the existence matrix.
And step 3: establishing a fitness function according to the constraint conditions
Scheduling under the Qos constraint, wherein each iteration is based on a fitness function which is evaluated by reducing the cost of the link more specifically, so that the fitness function is defined as:
f(P(s，M))＝Cost(P(s，M))
+k1{max DP(s，M)-(DP(s，M)，0)}
+k2{max JP(s，M)-(DP(s，M)，0)}
in the formula, k1、k2For the penalty coefficient, the degree of penalty is determined.
And 4, step 4: generating an initial solution, iteratively generating a solution set of data nodes
First, an initial solution V is randomly generated from a presence matrix0Due to V0Is randomly generated from a presence matrix, so that the presence matrix has physical and spatial significance, and then f (P (s, M)) is calculated in a fitness function f according to a Qos constraint condition to obtain fiWhen f isiWhen the threshold value is not reached, outputting the corresponding Vi。
Iteration is performed according to a standard PSO algorithm:
Vid＝ω·vid+c1rand()·(pbesti-Xi)+c2rand()·(gbesti-Xi)
Xi＝Xi+Vi
where ω is the inertial weight, representing the inertial behavior of the particle, c1、c2For an acceleration constant, rand () is a random value, the value of each parameter being defined according to a linear decreasing weight policy (LDW).
After one iteration is obtained according to the PSO algorithm
And 5: matching solutions to presence matrices and constraints
Iterating each roundMatch with the presence matrix ifNot in the presence matrix, i.e. meaningless interpretation, the next iteration is performed, regenerating a new oneKnowing that there is a matrix match; then the obtained data nodeComparing with Qos constraint conditions, if the Qos constraint condition proposed by the user is not met, performing the next iteration, and continuing to generate a new Qos constraint conditionAnd if no solution meeting the constraint condition is generated after n times of continuous iterations, selecting a solution closer to the Qos constraint condition from the n solutions and outputting the solution as the optimal solution of the scheduling. n is generally set to about 10, and if the number of tasks is large, the value of n can be increased appropriately. But too large a value of n increases the time overhead for system operation.
Claims (6)
1. A task scheduling algorithm constrained by service value in a cloud storage environment relates to the field of task scheduling in a cloud storage computer application and cloud environment, and is characterized by comprising the following steps:
step 1: generating presence matrices
Step 2: setting of Qos conditions and condition selection
And step 3: establishing a fitness function according to the constraint conditions
And 4, step 4: generating an initial solution, iteratively generating a solution set of data nodes
And 5: the solution matches the presence matrix and constraint conditions.
2. The task scheduling algorithm for a service value constraint in a cloud storage environment as claimed in claim 1, wherein the parameter functions and definitions involved in the step 1 are calculated as follows:
step 1: generating presence matrices
Because the nodes of the cloud storage system can not necessarily provide the data requested by the user, a function for describing the corresponding relation between the scheduling tasks and the resource nodes is defined by the number of tasks, resource nodes and the number of nodes waiting for scheduling, and a solution generated from an existence matrix has spatial significance, namely, the nodes necessarily contain required resources
Let T denote the task to be scheduled,n denotes the number of scheduled tasks, whereinAnd V represents a node of the group,m represents the number of nodes, whereinTo construct aThe matrix U of (a):
wherein
Are present in the matrix and are,representing a task scheduling vector, the same data may exist on multiple nodes, soRepresenting tasks by timeAt a nodeIs presentThen the task is representedAt a nodeIs not present.
3. The task scheduling algorithm for a service value constraint in a cloud storage environment as claimed in claim 1, wherein the parameter function and definition involved in the step 2 are calculated as follows:
step 2: setting of Qos conditions and condition selection
The Qos constraint is a minimum cost rule selection path which meets the requirements of users or application scenes according to different user or application scenes on the multi-Qos sensitivity, and the Qos parameter is used as the measurement of the current network state and is used forRepresenting nodesTo the nodeThe Qos status information between comprises three components, namely time delay (D), jitter (J) and bandwidth (B), a set of network nodes in cloud storage is constructed into an undirected weighted graph model G (V, E), V represents the nodes, E represents all edges of physically or logically linked nodes, each group of links comprises three components of the status information, and the links between task nodes and data nodes are represented by P (s, D),to indicate that: (ii) a And M is a link between the task node and the cloud storage node, and if the link is the shortest set, the values of three parameters are calculated as follows:
in the Qos vector, the total delay on link P (s, d) is defined as the minimum from the start point to the end point on the path, so:
jitter is defined as the difference in the mean value of the delay on the path from the source node to the end node
The bottleneck bandwidth of a link is defined as the minimum bandwidth of the link in T:
in the above parameters, P (S, d) is the shortest path of the task node with the data node, S is the source node requesting the task, and all nodes V are constrained by the existence matrix.
4. The task scheduling algorithm for a service value constraint in a cloud storage environment as claimed in claim 1, wherein the parameter function and definition involved in the step 3 are calculated as follows:
and step 3: establishing a fitness function according to the constraint conditions
Scheduling under the Qos constraint, wherein each iteration is based on a fitness function which is evaluated by reducing the cost of the link more specifically, so that the fitness function is defined as:
in the formula,、for the penalty coefficient, the degree of penalty is determined.
5. The task scheduling algorithm for a service value constraint in a cloud storage environment as claimed in claim 1, wherein the parameter functions and definitions involved in the step 4 are calculated as follows:
and 4, step 4: generating an initial solution, iteratively generating a solution set of data nodes
First, an initial solution is randomly generated from a presence matrixDue to the fact thatIs randomly generated from the existing matrix, so that the existing matrix has physical and spatial significance, and then the existing matrix is subjected to fitness function according to Qos constraint conditionsIs calculated to obtainWhen is coming into contact withWhen the threshold value is not reached, outputting the corresponding
Iteration is performed according to a standard PSO algorithm:
wherein,is the inertial weight, representing the inertial behavior of the particle,in order to accelerate the constant amount of the acceleration,for random values, the values of the individual parameters are defined according to a linear decreasing weight strategy (LDW)
After one iteration is obtained according to the PSO algorithm。
6. The task scheduling algorithm for a service value constraint in a cloud storage environment as claimed in claim 1, wherein the parameter function and definition involved in the step 5 are calculated as follows:
and 5: matching solutions to presence matrices and constraints
Iterating each roundMatch with the presence matrix ifNot in the presence matrix, i.e. meaningless interpretation, the next iteration is performed, regenerating a new oneKnowing that there is a matrix match; then the obtained data nodeComparing with Qos constraint conditions, if the Qos constraint condition proposed by the user is not met, performing the next iteration, and continuing to generate a new Qos constraint conditionIf no solution meeting the constraint condition is generated after n times of continuous iterations, a solution closer to the Qos constraint condition is selected from the n solutions and output as the optimal solution of the scheduling, and n is generally set asAbout 10, if the number of tasks is larger, the value of n can be increased appropriately, but an excessively large value of n increases the time overhead of system operation.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610444598.2A CN106610866A (en) | 2016-06-17 | 2016-06-17 | Service value constrained task scheduling algorithm in cloud storage environment |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610444598.2A CN106610866A (en) | 2016-06-17 | 2016-06-17 | Service value constrained task scheduling algorithm in cloud storage environment |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN106610866A true CN106610866A (en) | 2017-05-03 |
Family
ID=58614883
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610444598.2A Pending CN106610866A (en) | 2016-06-17 | 2016-06-17 | Service value constrained task scheduling algorithm in cloud storage environment |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106610866A (en) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108769105A (en) * | 2018-04-12 | 2018-11-06 | 昆明理工大学 | A kind of scheduling system of knowledge services multi-task scheduling optimization method and its structure under cloud environment |
| WO2019179250A1 (en) * | 2018-03-23 | 2019-09-26 | 华为技术有限公司 | Scheduling method, scheduler, storage medium, and system |
| CN112231081A (en) * | 2020-10-14 | 2021-01-15 | 山东大学 | PSO-AHP-based monotonic rate resource scheduling method and system in cloud environment |
| CN116795517A (en) * | 2023-08-25 | 2023-09-22 | 中国人民解放军国防科技大学 | Multi-strategy self-adaptive asynchronous task scheduling method, system and device |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105141697A (en) * | 2015-09-16 | 2015-12-09 | 国云科技股份有限公司 | Multi-QoS constrained cloud computing task scheduling method |
| CN105262843A (en) * | 2015-11-12 | 2016-01-20 | 武汉理工大学 | Data anti-leakage protection method for cloud storage environment |
-
2016
- 2016-06-17 CN CN201610444598.2A patent/CN106610866A/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105141697A (en) * | 2015-09-16 | 2015-12-09 | 国云科技股份有限公司 | Multi-QoS constrained cloud computing task scheduling method |
| CN105262843A (en) * | 2015-11-12 | 2016-01-20 | 武汉理工大学 | Data anti-leakage protection method for cloud storage environment |
Non-Patent Citations (1)
| Title |
|---|
| 王娟等: "PSO应用于QoS偏好感知的云存储任务调度", 《通信学报》 * |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2019179250A1 (en) * | 2018-03-23 | 2019-09-26 | 华为技术有限公司 | Scheduling method, scheduler, storage medium, and system |
| US11190618B2 (en) | 2018-03-23 | 2021-11-30 | Huawei Technologies Co., Ltd. | Scheduling method, scheduler, storage medium, and system |
| CN108769105A (en) * | 2018-04-12 | 2018-11-06 | 昆明理工大学 | A kind of scheduling system of knowledge services multi-task scheduling optimization method and its structure under cloud environment |
| CN112231081A (en) * | 2020-10-14 | 2021-01-15 | 山东大学 | PSO-AHP-based monotonic rate resource scheduling method and system in cloud environment |
| CN112231081B (en) * | 2020-10-14 | 2022-08-16 | 山东大学 | PSO-AHP-based monotonic rate resource scheduling method and system in cloud environment |
| CN116795517A (en) * | 2023-08-25 | 2023-09-22 | 中国人民解放军国防科技大学 | Multi-strategy self-adaptive asynchronous task scheduling method, system and device |
| CN116795517B (en) * | 2023-08-25 | 2023-11-07 | 中国人民解放军国防科技大学 | Multi-strategy self-adaptive asynchronous task scheduling method, system and device |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN107911478B (en) | Multi-user calculation unloading method and device based on chemical reaction optimization algorithm | |
| CN110134495B (en) | Container cross-host online migration method, storage medium and terminal equipment | |
| CN114116198A (en) | Asynchronous federal learning method, system, equipment and terminal for mobile vehicle | |
| US20220417156A1 (en) | Network burst load evacuation method for edge servers | |
| CN108416465B (en) | Workflow optimization method in mobile cloud environment | |
| CN110069341B (en) | Method for scheduling tasks with dependency relationship configured according to needs by combining functions in edge computing | |
| CN110798517B (en) | Decentralized cluster load balancing method and system, mobile terminal and storage medium | |
| CN112650581A (en) | Cloud-side cooperative task scheduling method for intelligent building | |
| CN106610866A (en) | Service value constrained task scheduling algorithm in cloud storage environment | |
| CN106101196A (en) | A kind of cloud rendering platform task scheduling system based on probabilistic model and method | |
| CN105426228B (en) | A kind of OpenStack virtual machine placement methods towards live streaming media and video code conversion | |
| Ji et al. | Adaptive workflow scheduling for diverse objectives in cloud environments | |
| CN115357351A (en) | Computing power network scheduling method, device, system, equipment and medium | |
| CN114785692A (en) | Virtual power plant aggregation regulation and control communication network flow balancing method and device | |
| El Gaily et al. | Constrained quantum optimization for resource distribution management | |
| Krishna Priya et al. | Crossover-based improved sine cosine algorithm for multimedia content distribution in cloud environment | |
| CN116582407A (en) | Containerized micro-service arrangement system and method based on deep reinforcement learning | |
| Wang et al. | Virtual network embedding with pre‐transformation and incentive convergence mechanism | |
| Yang et al. | Replica placement in content delivery networks with stochastic demands and M/M/1 servers | |
| CN112906745B (en) | Integrity intelligent network training method based on edge cooperation | |
| Ludwig | Mapreduce-based optimization of overlay networks using particle swarm optimization | |
| Ruby et al. | RenderSelect: a cloud broker framework for cloud renderfarm services | |
| Mattia et al. | Online Decentralized Scheduling in Fog Computing for Smart Cities Based On Reinforcement Learning | |
| CN111784029A (en) | Fog node resource allocation method | |
| Mou et al. | Joint Task Scheduling and Container Image Caching in Edge Computing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20170503 |
|
| WD01 | Invention patent application deemed withdrawn after publication |