Disclosure of Invention
The technical problem to be solved by the invention is as follows: because the key nodes on the key paths are key factors influencing the execution time of the calculation tasks of the whole AOE network, the scheduling execution time of the key nodes must be optimized in a targeted manner, so that the execution time of the calculation tasks of the whole AOE network is ensured to be shorter.
Aiming at the technical problems in the prior art, the invention provides the scheduling method and the scheduling system for the calculation tasks of the AOE network in the Linux system, which optimize the scheduling of the key node tasks in the AOE network and can reduce the completion time of the calculation tasks of the whole AOE network.
In order to solve the technical problems, the technical scheme provided by the invention is as follows:
a scheduling method of AOE network computing tasks in a Linux system comprises the following steps:
s101) acquiring calculation tasks represented by an AOE network, determining the scheduling sequence of nodes in the AOE network according to the degree of node incidence, and dividing the nodes in the AOE network into key nodes and non-key nodes;
s102) when the nodes in the AOE network are sequentially scheduled according to the scheduling sequence, real-time scheduling is respectively carried out on the key nodes, and common scheduling is respectively carried out on the non-key nodes.
Further, the step S102 specifically includes the following steps:
if the current batch node to be dispatched comprises at least two nodes, traversing the current batch node to be dispatched;
if the current node is a key node, scheduling the current node to a corresponding processor or processing core for execution by using a real-time scheduler, wherein the processor or processing core corresponds to the key node one by one;
and if the current node is a non-critical node, scheduling the current node to a processor or a processing core with the minimum load for execution by using a full fairness scheduler.
Further, the step S102 specifically includes the following steps:
if the current batch node to be dispatched comprises a node which is a key node, dispatching the node to a processor or a processing core with the minimum load by using a real-time dispatcher for execution;
if the current batch node to be dispatched comprises a node and the node is a non-critical node, dispatching the node to a processor or a processing core with the minimum load for execution by using a full fairness scheduler.
Optionally, the real-time scheduler adopts a FIFO real-time scheduling algorithm, and the full-fairness scheduler adopts a sched_normal scheduling algorithm, and before step S102, the method further includes:
setting scheduling strategies of all key nodes as a FIFO real-time scheduling algorithm, and setting process priorities of all key nodes as a first value;
and setting the scheduling policy of all non-critical nodes as a sched_normal scheduling algorithm, and setting the process priority of all non-critical nodes as a second value.
Optionally, the first value is a maximum value of a process priority range of the real-time task, and the second value is a middle value of a priority range of the common process.
Further, in step S101, when determining the scheduling sequence of the nodes in the AOE network according to the node entering degree, the method includes:
s201), counting nodes with the degree of entry of 0 in the AOE network, and adding the counted nodes into a dependence scheduling set of nodes to be scheduled of the current batch;
s202) deleting nodes in the dependency dispatching set of the nodes to be dispatched of the current batch in the AOE network, taking the dependency dispatching set of the nodes to be dispatched of the next batch as the dependency dispatching set of the nodes to be dispatched of the current batch, and jumping to execute the step S201 until the nodes in the AOE network are deleted.
Further, in step S101, when dividing the nodes in the AOE network into the critical nodes and the non-critical nodes, the method includes:
s301) calculating the earliest occurrence time of each node in a positive sequence, and then calculating the latest occurrence time of each node in a reverse sequence;
s302) taking the earliest occurrence time of the precursor node of each side as the earliest occurrence time of each side, and calculating the difference between the latest occurrence time of the subsequent node of each side and the weight value of each side to obtain the latest occurrence time of each side;
s303) takes the edge with the same earliest occurrence time and the latest occurrence time as a key edge, the predecessor node and the successor node of the key edge as key nodes, and the rest nodes as non-key nodes.
Further, when the positive sequence calculates the earliest occurrence time of each node, the method includes:
setting the earliest occurrence time of the node of the source point to 0;
and for each node, calculating the sum of the earliest starting time of all the precursor nodes of the node and the weight of the corresponding edge respectively, and taking the maximum value of the sum of the earliest starting time of all the precursor nodes and the weight of the corresponding edge as the earliest occurrence time of the node.
Further, when calculating the latest occurrence time of each node in reverse order, the method includes:
taking the earliest occurrence time of the node of the terminal as the latest occurrence time;
for each node, calculating the difference between the latest starting time of all the subsequent nodes of the node and the weight of the corresponding edge, and taking the minimum value of the difference between the latest starting time of all the subsequent nodes and the weight of the corresponding edge as the latest occurrence time of the node.
The invention also provides a dispatching system of the AOE network computing task in the Linux system, which comprises a microprocessor and a computer readable storage medium which are connected with each other, wherein the microprocessor is programmed or configured to execute the dispatching method of the AOE network computing task in any Linux system.
Compared with the prior art, the invention has the advantages that:
aiming at the calculation task represented by the AOE table, the invention determines the scheduling sequence of the nodes in the AOE network according to the node incidence, divides the nodes in the AOE network into key nodes and non-key nodes, and performs real-time scheduling on the key nodes and common scheduling on the non-key nodes when the nodes in the AOE network are sequentially scheduled according to the scheduling sequence. The key nodes in the AOE network are created into real-time tasks through real-time scheduling, so that the real-time tasks have higher priority, and the key nodes can be guaranteed to have the fastest execution time no matter which processor or processing core is scheduled to execute during scheduling, so that the whole AOE network calculation task can be completed in the fastest time.
Detailed Description
The invention is further described below in connection with the drawings and the specific preferred embodiments, but the scope of protection of the invention is not limited thereby.
The execution time of the key nodes in the AOE network is a key factor influencing the whole AOE calculation task, and the completion time of the whole AOE calculation task can be improved by optimizing the scheduling execution time of the key nodes.
In the Linux system, a full fairness scheduler CFS (Completely Fair Scheduler) is adopted as a default for a common user process, a fairness scheduling principle is reflected, and a sched_normal scheduling algorithm is adopted.
Meanwhile, the Linux system also provides a real-time scheduler RT_scheduled, which embodies a preemption mechanism and is mainly used for scheduling real-time tasks, and two scheduling algorithms exist; FIFO and RR, wherein the FIFO scheduling algorithm idea is: the processes schedule according to the order of priority, and the high priority tasks can preempt the low priority tasks. When a process executes, unless preempted, it executes in unison until itself is blocked or the CPU is actively relinquished. The calculation task adopting the FIFO real-time scheduling algorithm has higher priority, and can preempt the calculation task adopting the SCHED_NORMAL common scheduling algorithm.
Therefore, this embodiment proposes a scheduling method for an AOE network computing task in a Linux system, by creating a key node in the AOE network as a real-time task, so that the key node has a higher priority, and when scheduling, no matter to which processor or processing core the key node is scheduled to execute, the key node can be guaranteed to have the fastest execution time, so that the whole AOE network computing task can be guaranteed to complete execution in the fastest time. As shown in fig. 3, the method comprises the following steps:
s101) acquiring calculation tasks represented by an AOE network, determining the scheduling sequence of nodes in the AOE network according to the degree of node incidence, and dividing the nodes in the AOE network into key nodes and non-key nodes;
s102) when the nodes in the AOE network are sequentially scheduled according to the scheduling sequence, real-time scheduling is respectively carried out on the key nodes, and common scheduling is respectively carried out on the non-key nodes.
Each step is specifically explained below.
In step S101, the calculation task represented by the AOE network is specifically a calculation task for modeling an AOE network by using a pointer, for example, in a Linux system, a system boot process based on a system md mechanism may be represented as an AOE network, a dependency relationship between all units may be obtained through Requires, wants fields in all unit definitions, and at the same time, the boot time of each unit may be obtained through measurement, so as to finally obtain an AOE network, including a node set v= { V of the AOE network1 ,v2 ,…,vn An ingress set d= { D } for each node1 ,d2 ,…,dn Edge set E= { E of AOE network1 ,e2 ,…,em Edge ek =(vi , vj ) Wherein v isi For edge ek Precursor node v of (v)j For edge ek Subsequent nodes of (a); due to the precursor node vi There will be a plurality of successor nodes vj The method comprises the steps of carrying out a first treatment on the surface of the Weight set w= { W of each edge1 ,w2 ,…,wm -w isk For edge ek =(vi , vj ) The weights of (2) may also be expressed as: w (w)k =w(vi ,vj )。
In step S101, when determining the scheduling sequence of the nodes in the AOE network according to the node' S ingress, the node is determined from the source point v according to the ingress table BFS1 Initially, all nodes with 0 degree are gradually counted, and all nodes with 0 degree form a subset Vdx (hereinafter referred to as a dependency schedule set), and nodes in the subset have no dependency relationship and can execute in parallel. Then delete the subset V in the AOE networkdx Intermediate nodes, and then continuing to count all nodes with 0 degree to form another node with 0 degreeNode subset Vd(x+1) . It can be seen that the latter node subset V with an ingress of 0d(x+1) Node subset V dependent on the previous degree of entry 0dx . Finally, a process of executing all subtasks in the AOE network can be obtained, which comprises the following steps:
s201), counting nodes with the degree of entry of 0 in the AOE network, and adding the counted nodes into a dependence scheduling set of nodes to be scheduled of the current batch;
s202) deleting nodes in the dependency dispatching set of the nodes to be dispatched of the current batch in the AOE network, taking the dependency dispatching set of the nodes to be dispatched of the next batch as the dependency dispatching set of the nodes to be dispatched of the current batch, and jumping to execute the step S201 until the nodes in the AOE network are deleted.
According to the method of the ingress table (BFS algorithm), when a task is scheduled, only subtasks with ingress degree of 0 are scheduled each time, for example, the scheduling steps of all subtasks in FIG. 1 according to the dependency relationship are:
1) V in AOE network1 As for the vertex, the ingress is 0 initially, so that the execution is scheduled first, and a dependent scheduling set V is definedd1 ={v1 }；
2) Deletion of v in AOE network1 After that, v2 And v3 The penetration degree is 0, v2 And v3 The execution may be scheduled and may be performed in parallel because v2 And v3 No precedence dependence exists between the two, and a dependence scheduling set V is definedd2 ={v2 ，v3 }；
3) Deletion of v in AOE network2 And v3 After that, v4 And v5 The penetration degree is 0, v4 And v5 The execution may be scheduled and may be performed in parallel because v4 And v5 No precedence dependence exists between the two, and a dependence scheduling set V is definedd3 ={v4 ,v5 }；
4) Deletion of v in AOE network4 And v5 After that, v6 And v7 The penetration degree is 0, v6 And v7 The execution may be scheduled and may be performed in parallel because v6 And v7 There is no precedence dependence relationship between them, defining dependenceScheduling set Vd4 ={v6 ,v7 }；
5) Deletion of v in AOE network6 And v7 After that, v8 The penetration degree is 0, v8 Can schedule execution, define a dependent scheduling set Vd5 ={v8 }。
Finally, the set of dependent schedules for each step of statistics in FIG. 2 is as follows:
①Vd1 ={v1 }
②Vd2 ={v2 ,v3 }
③Vd3 ={v4 ,v5 }
④Vd4 ={v6 ,v7 }
⑤Vd5 ={v8 }
in step S101, when dividing a critical node and a non-critical node for a node in the AOE network, a critical path method is used. The critical path and critical nodes in the AOE network can be calculated through a critical path algorithm.
First, define:
1) ve (i) represents: the earliest time of occurrence of node i;
2) vl (i) represents: the latest occurrence time of node i;
3) e (j) represents: edge ej Is the earliest start time of (2);
4) l (j) represents: edge ej Is the latest start time of (c).
The key path calculation steps are as follows:
1) Let ve (source) =0 from the source, find the earliest occurrence time ve (i) of the remaining points in the positive order of the topological order.
2) Starting from the endpoint, let vl (endpoint) =ve (endpoint), find the latest occurrence time vl (i) of the remaining points in reverse order of topological order.
3) The earliest start time e (j) of all edges is found from the ve (i) values of each vertex.
4) The latest start time l (j) of all edges is calculated from the vl (i) value of each vertex.
5) Selecting the edge with the same earliest starting time e (j) and latest starting time l (j),if e (j) =l (j), the edge e is representedj The key edges are the key nodes, and all the key edges form a key path.
Therefore, in this embodiment, when dividing the nodes in the AOE network into the critical nodes and the non-critical nodes, the method includes the following steps:
s301) calculating the earliest occurrence time ve (i) of each node in a positive sequence, and then calculating the latest occurrence time vl (i) of each node in a reverse sequence;
the positive sequence for calculating the earliest time of occurrence for each node includes:
setting the earliest occurrence time of a node of a source point to 0, ve (source point) =0, i.e., ve (1) =0;
and for each node, calculating the sum of the earliest starting time of all the precursor nodes of the node and the weight of the corresponding edge respectively, and taking the maximum value of the sum of the earliest starting time of all the precursor nodes and the weight of the corresponding edge as the earliest occurrence time of the node. Taking fig. 2 as an example, the earliest occurrence times for all nodes are shown in the following table:
table 1 node earliest occurrence schedule
When calculating the latest occurrence time of each node in reverse order, the method comprises the following steps:
taking the earliest occurrence time of the node of the terminal as the latest occurrence time;
for each node, calculating the difference between the latest starting time of all the subsequent nodes of the node and the weight of the corresponding edge, and taking the minimum value of the difference between the latest starting time of all the subsequent nodes and the weight of the corresponding edge as the latest occurrence time of the node. Taking fig. 2 as an example, vl (8) =ve (8) =14, and the node latest occurrence schedule is shown in the following table:
table 2 node latest occurrence schedule
S302) taking the earliest occurrence time of the precursor node of each side as the earliest occurrence time e (j) of each side, and calculating the difference between the latest occurrence time of the subsequent node of each side and the weight value of each side to obtain the latest occurrence time l (j) of each side;
suppose edge ej =(vt ,vw ) Edge ej The precursor node is vt The successor node is vw Edge ej Is equal to the earliest start time e (j) of the precursor node vt E (j) =ve (t). Finally, an earliest occurrence schedule of all edges is formed, taking fig. 2 as an example, and the earliest occurrence schedule of all edges is shown in the following table:
TABLE 3 earliest occurrence schedule
Also assume edge ej =(vt ,vw ) The precursor node is vt The successor node is vw Edge ej Is equal to the successor node vw And edge ej Weight wj I.e. l (j) =vl (w) -wj . Finally, a latest occurrence schedule of all edges is formed, and taking fig. 2 as an example, the earliest occurrence schedule of all edges is shown in the following table:
table 4 edge latest occurrence timetable
S303) taking the edge with the same earliest occurrence time and the latest occurrence time as a key edge, taking a predecessor node and a successor node of the key edge as key nodes, and adding the key nodes into a key node set Vcp And the rest nodes are used as non-critical nodes and added into the non-critical node set Vncp 。
Specifically, taking fig. 2 as an example, according to tables 3 and 4, the values of the earliest start time e (j) and the latest start time l (j) of all sides are compared, as shown in the following table:
table 5 critical path computation table
In table 5, the edges of e (j) -l (j) equal to 0 constitute key edges, and all key edges constitute key paths, which are as follows from table 5 and fig. 3: (e)1 ,e5 ,e11 ) Wherein edge e1 =(v1 , v2 )，e5 =(v2 , v6 )，e11 =(v6 , v8 ) The method comprises the steps of carrying out a first treatment on the surface of the The key nodes are as follows: { v1 ,v2 ,v6 ,v8 And the length of the whole critical path is edge e1 ,e5 ,e11 The sum of the respective weights, i.e. w1 +w5 +w11 =14。
In the implementation, when the task is scheduled, different scheduling algorithms are adopted for scheduling sub-tasks in the key node set and the non-key node set. For non-critical node tasks, a sched_normal scheduling algorithm is adopted, and for critical node tasks, a FIFO real-time scheduling algorithm is adopted. Therefore, before step S102, the following steps are further included:
aggregating key nodes Vcp Setting the scheduling strategy of all key nodes as a FIFO real-time scheduling algorithm, and setting the process priority of all key nodes as a first value;
set of non-critical nodes Vncp The scheduling policy of all non-critical nodes is set as a sched_normal scheduling algorithm, and the process priority of all non-critical nodes is set as a second value.
In this embodiment, the first value is the maximum value of the process priority range of the real-time task, the second value is the middle value of the priority range of the normal process, specifically, the process priority range of the real-time task is 0-99, the larger the set value is, the higher the priority is, the first value is set to 99, the priority value can be adjusted according to the needs, meanwhile, in Linux, the range of the priority of the normal process is 100-139, the smaller the set value is, the higher the priority is, the second value is set to 120, and the priority value can be adjusted according to the needs.
In this embodiment, the step S102 specifically includes the following steps:
if the current batch node to be dispatched comprises at least two nodes, the sub-tasks represented by the plurality of nodes have no dependency relationship and can be executed in parallel, so that the current batch node to be dispatched is traversed;
if the current node is a key node, scheduling the current node to a corresponding processor or processing core for execution by using a real-time scheduler, wherein according to the foregoing, in the embodiment, the real-time scheduler adopts a FIFO real-time scheduling algorithm, and the processor or processing core corresponds to the key node one by one, so that preemption of computing resources among a plurality of key tasks is avoided;
if the current node is a non-critical node, using a full fairness scheduler to schedule the current node to a processor or a processing core with the smallest load for execution, and according to the foregoing, in this embodiment, the full fairness scheduler adopts a sched_normal scheduling algorithm;
if the current batch node to be dispatched only comprises one node, the node is dispatched to a processor or a processing core with the smallest load no matter whether the node is a key node or a non-key node, and when the node is a key node, a real-time dispatcher is used for dispatching the node to the processor or the processing core with the smallest load for execution; and when the node is a non-critical node, scheduling the node to a least loaded processor or processing core for execution by using a full fairness scheduler.
Taking fig. 2 as an example, the task set v= { V in fig. 21 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 ,v8 Scheduling execution in the following order:
1) Scheduling subtask set Vd1 ={v1 }，v1 As a key node, the real-time scheduler adopts a FIFO real-time scheduling algorithm to schedule the node v1 Scheduling to the corresponding processor 1 or processing core 1 for execution;
2) Rescheduling subtask set Vd2 ={v2 ,v3 }，v2 Is a key node, and { v2 ,v3 The node v can be scheduled in parallel, and the real-time scheduler adopts a FIFO real-time scheduling algorithm to schedule the node v2 Dispatch to corresponding processor 2 or processing core 2, while full fairness scheduler uses sched_normal scheduling algorithm to schedule node v3 Scheduling to be executed on the least loaded processor or processing core;
3) Rescheduling subtask set Vd3 ={v4 ,v5 }，{v4 ,v5 The node v can be scheduled in parallel, and the full fairness scheduler adopts the SCHED_NORMAL scheduling algorithm4 And v5 Simultaneously scheduling to be executed on the processor or the processing core with the minimum load;
4) Rescheduling subtask set Vd4 ={v6 ,v7 }，v6 Is a key node, and { v6 ,v7 The node v can be scheduled in parallel, and the real-time scheduler adopts a FIFO real-time scheduling algorithm to schedule the node v6 Dispatch to corresponding processor 3 or processing core 3, while full fairness scheduler uses sched_normal scheduling algorithm to schedule node v7 Scheduling to be executed on the least loaded processor or processing core;
5) Rescheduling subtask set Vd5 ={v8 }，v8 As a key node, the real-time scheduler adopts a FIFO real-time scheduling algorithm to schedule the node v8 Scheduled to execute on a corresponding processor 4 or processing core 4
Based on the foregoing, the main pseudo code of the scheduling method of the AOE network computing task in the Linux system according to the present embodiment is described as follows:
the embodiment also provides a scheduling system of the AOE network computing task in the Linux system, which comprises a microprocessor and a computer readable storage medium which are connected with each other, wherein the microprocessor is programmed or configured to execute the scheduling method of the AOE network computing task in the Linux system.
In summary, the invention provides an efficient task scheduling technology for computing tasks based on AOE network modeling in a Linux system, and by identifying critical paths in the AOE network, the critical tasks on the critical paths are scheduled in real time, while other non-critical tasks are scheduled in common, so that the critical tasks can be scheduled preferentially, the whole AOE network computing task can be executed in the shortest time, and finally the purpose of efficient scheduling is achieved.
The foregoing is merely a preferred embodiment of the present invention and is not intended to limit the present invention in any way. While the invention has been described with reference to preferred embodiments, it is not intended to be limiting. Therefore, any simple modification, equivalent variation and modification of the above embodiments according to the technical substance of the present invention shall fall within the scope of the technical solution of the present invention.