CN102567120B - Method and device for determining node scheduling priority - Google Patents

Abstract

An embodiment of the invention provides a node scheduling priority determining method and a node scheduling priority determining device. The method includes the steps: in a multi-core processor determining the node scheduling priority according to the task queue depth, on each assembly line, lowering the scheduling priority of a node n-1 before a node n with critical resource interlocking, reducing the scheduling possibility of the node n-1 in the light of the principle that cores select the node with the high scheduling priority for processing according to the scheduling priority of the current node waiting for multi-core scheduling, so that the preceding node is prevented from continuously inputting to-be-processed data tasks to the consequent node with a bottleneck, increase of the task queue depth of the node n is avoided, more cores can be prevented from being scheduled to the node n, possibility of multi-core competition of the node n is reduced, and performance of the multi-core processor is fully given play to.

Description

Method and device for determining node scheduling priority

technical field

The invention relates to the technical field of embedded computers, in particular to a method and device for determining node scheduling priorities.

Background technique

At present, relying on increasing the operating frequency of a single central processing unit (CPU) core in a single-core processor can no longer meet users' requirements for network device performance. In order to improve the processing speed of network equipment on data streams, multi-core processors emerge as the times require. Multi-core processors can solve the bottleneck problem of increasing the frequency of single-core processors. By using multiple CPU cores to work together at the same time, the time for task execution can be greatly shortened.

In order to efficiently utilize multi-core processors, system tasks can be divided into multiple threads (or multiple subtasks), and each thread can be divided into multiple phase execution points. A phase execution point is the smallest execution particle of the scheduling kernel, thus So that each core can be fully scheduled. Each core can only execute one phase execution point in one thread at the same time (that is, a minimum execution particle).

Time, stage execution point, kernel, these three variables have a one-to-one relationship and cannot overlap. Usually, the combination of time and phase execution point is defined as a minimum execution unit, and each core can freely obtain an idle execution unit and be scheduled. Specifically, a coordinate diagram as shown in FIG. 1 may be used to represent the relationship between them.

For a network device, how many threads should be divided into system tasks, how many phase execution points should be divided into each thread, and how to balance the load of these threads are the keys to determine the performance of the entire network device. At present, most network devices have only one thread, and multiple stages of execution points are divided on this thread, so the problem of load balancing is not involved. However, with the development of CPU technology, the concept of multi-core is no longer dual-core or 4-core, but more than ten or even dozens of cores can be integrated. So simply distributing multiple cores in one thread can no longer give full play to system performance, it is necessary to distribute multiple cores on multi-threaded multi-stage execution points, and then add load balancing.

The problem of critical resource contention that may arise in each stage execution point is especially prominent in multi-core processors. In a multi-core processor, multiple cores may execute the execution point of the same stage. If critical resources are operated at the execution point of this stage, these cores will queue up to obtain critical resources. Spin locks are usually used to protect the execution point of the phase with critical resources. If a certain core grabs the critical resource first, other cores will hang and wait until the critical resource is released. , resulting in a critical resource interlock. If multiple cores need to poll and wait for critical resources after entering a certain stage of execution, multi-core competition will occur, which will greatly reduce the performance of multi-core.

In a multi-core processor, a series of actions from the beginning to the end of data processing can be called a pipeline. A pipeline can be divided into multiple processing stages, and each processing stage is a node scheduled by the kernel (a node is a stage execution point). The smallest atomic operation scheduled and entered in parallel by the kernel.

Some multi-core processors judge the scheduling priority of a node according to the depth of the task queue of the node. When a core completes the processing task of a node, it needs to enter another node to obtain a new task for processing. At this time, the selection of the node is based on the current The scheduling priority of the node waiting for multi-core scheduling, and select the node with the highest scheduling priority for processing. If node n operates critical resources, and node n-1 (a node before node n) is still continuously transmitting the data to be processed to node n at this time, then the scheduling priority of node n will continue to increase . The system scheduling algorithm will allocate more cores to process node n. When these cores are executed to the critical resources of node n, they will compete for multi-core, and mutual exclusion will occur, resulting in performance degradation.

Contents of the invention

Embodiments of the present invention provide a node scheduling priority determination method and device, which are used to reduce multi-core competition in nodes and improve the performance of multi-core processors.

A method for determining node scheduling priority, applied to a multi-core processor that determines node scheduling priority according to task queue depth, said method comprising:

Determine the node n where the critical resource interlock occurs;

On each pipeline where critical resource interlock occurs at node n, reduce the scheduling priority of node n-1 closest to node n and located before node n, where n is a positive integer greater than 1;

Among them, on pipeline A, reduce the scheduling priority of node n-1 closest to node n and located before node n, specifically including:

According to the proportional relationship between the scheduling priority of node n-1 and the fixed execution time of node n on each pipeline where critical resource interlock occurs at node n, and/or on each pipeline where critical resource interlock occurs at node n On the lock pipeline, the inverse relationship between the length of each lock of node n reduces the scheduling priority of node n-1.

A device for determining node scheduling priority is applied to a multi-core processor that determines node scheduling priority according to the depth of a task queue, and the device includes:

A determining module, configured to determine the node n where critical resource interlock occurs;

The adjustment module is used to be based on the proportional relationship between the scheduling priority of node n-1 and the fixed execution time of node n on each pipeline where critical resource interlocking occurs at node n, and/or on each pipeline at node n On the pipeline where interlocking of critical resources occurs, the inverse relationship between the length of each locking time of node n reduces the scheduling priority of node n-1, where n is a positive integer greater than 1.

According to the solution provided by the embodiment of the present invention, in the multi-core processor that determines the node scheduling priority according to the depth of the task queue, on each pipeline, reduce the scheduling priority of node n-1 before the node n where critical resource interlock occurs , according to the principle that the kernel selects a node with a high scheduling priority for processing according to the scheduling priority of the node currently waiting for multi-core scheduling, and reduces the possibility of node n-1 being scheduled, so as to avoid the forward node from continuously appearing to the back of the bottleneck Input the data tasks to be processed to the node, avoid the increase of the task queue depth in node n, thereby avoiding more kernel scheduling to node n, reduce the possibility of multi-core competition in node n, and give full play to the performance of multi-core processors.

Description of drawings

Fig. 1 is a schematic diagram of the relationship between time, stage execution point and kernel in the prior art;

FIG. 2 is a flow chart of the steps of the method for determining the node scheduling priority provided by Embodiment 1 of the present invention;

FIG. 3 is a schematic diagram of a pipeline provided by Embodiment 1 of the present invention;

FIG. 4 is a schematic structural diagram of an apparatus for determining a node scheduling priority provided by Embodiment 2 of the present invention.

Detailed ways

In the solution provided by the embodiment of the present invention, in the multi-core data processing system where critical resource interlocking occurs, the forward feedback reduces the multi-core scheduling priority of the forward node, and reduces the core's critical resource operation in the multi-core data processing system. Competition and collision make multi-core allocation and scheduling predictable, avoiding the occurrence of multiple cores competing for a certain critical resource in advance.

The solutions of the present invention will be described below in conjunction with the accompanying drawings and various embodiments.

Embodiment one,

Embodiment 1 of the present invention provides a method for determining node scheduling priority, which is applied to a multi-core processor that determines node scheduling priority according to the task queue depth. The steps of the method are shown in FIG. 2 , including:

Step 101, node n obtains the kernel schedule.

Wherein, n is a positive integer greater than 1.

Step 102, node n determines whether a critical resource interlock occurs in itself.

In this embodiment, the means for determining the node scheduling priority, such as the node scheduling priority determining means, needs to determine the node n where critical resource interlock occurs, and reduce the scheduling priority of node n-1. Specifically, it may be determined according to the received feedback information of the node that a critical resource interlock occurs on the node.

Therefore, in this step, after obtaining the kernel scheduling, the node n can determine whether critical resource interlocking occurs when the node n executes critical resources. If it is determined that critical resource interlocking occurs, the execution time of the critical resource may be calculated, and step 103 is performed to feed back the information. After node n obtains the kernel scheduling, if it determines that there is no critical resource interlock, it does not need to feed back information, that is, it does not need to trigger the execution of step 103, and node n-1 can maintain the original method (that is, determine the node according to the depth of the task queue). Scheduling priority method) determines its own scheduling priority.

Step 103, node n feeds back the execution time length of the critical resource.

Specifically, the time length of critical resource execution can be fed back to the node scheduling priority determination device (this device can be integrated in the previous node n-1, that is, a node scheduling priority determination device can be integrated in each node, therefore, In this embodiment, the forward feedback method can be used to inform the previous node of the bottleneck information of this node, and reduce the multi-core scheduling priority of the previous node, thereby preventing the forward node from inputting a large amount of data to the backward node and causing Tasks are piled up on the backward node where the bottleneck occurs. Of course, the device can also be independent of the node). The node scheduling priority determining device may determine that critical resource interlock occurs on node n when receiving information fed back by node n.

Step 104, lowering the scheduling priority of node n-1.

This step includes, on each pipeline where critical resource interlock occurs at node n, lowering the scheduling priority of node n-1 closest to node n and located in front of node n.

There are multiple data processing pipelines in a multi-core processor, each pipeline has multiple nodes, and the processing process of the nodes on each pipeline is the same. The schematic diagram of the pipeline can be shown in Figure 3. When the node scheduling priority determination device is integrated in the node, when critical resource interlock occurs at node n, for each pipeline where critical resource interlock occurs at node n, node n can be Feedback information to the node scheduling priority determination device in node n-1, and notify node n-1 that critical resource interlock occurs at node n. At this time, the node scheduling priority determining device may re-determine the scheduling priority of node n-1.

In this embodiment, according to the proportional relationship between the scheduling priority of node n-1 and the fixed execution time of node n on each pipeline where critical resource interlock occurs at node n, and/or on each pipeline On the pipeline where critical resource interlock occurs at node n, the inverse relationship between the length of each locking time of node n reduces the scheduling priority of node n-1. Specifically, according to the number of pipelines where critical resource interlocking occurs at node n, on each pipeline where critical resource interlocking occurs at node n, the length of each locking time of node n, on each pipeline at node n On the pipeline where critical resource interlock occurs, the fixed execution time of node n, the fixed execution time of node n-1 on pipeline A, and the task queue depth of node n-1 on pipeline A (which can be understood as the number of tasks), determine the pipeline The scheduling priority of node n-1 on A.

Preferably, the scheduling priority H _A,n-1 of node n-1 on pipeline A can be determined by the following formula:

${\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; *</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; )</span>$

in,

K is the number of pipeline lines where critical resource interlock occurs at node n;

W _{i, n} is the length of each locking time of node n on the ith pipeline where critical resource interlock occurs at node n;

T _i,n is the fixed execution time of node n on the pipeline where critical resource interlock occurs at node n;

Q _A,n-1 is the task queue depth of node n-1 on pipeline A;

T _A,n-1 is the fixed execution time of node n-1 on pipeline A.

视为调整前流水线A上节点n-1的调度优先级H’_A,n-1，由于W_i,n必然小于T_i,n，因此，

必然大于0且小于1，

也必然小于1，由此，确定出的调度优先级H_A,n-1相对于H’_A,n-1必然是降低的。can

As the scheduling priority H' _A,n-1 of node n-1 on pipeline A before adjustment, since W _i,n must be smaller than T _i,n , therefore,

Must be greater than 0 and less than 1,

It must also be less than 1. Therefore, the determined scheduling priority H _A,n-1 must be lower than H' _A,n-1 .

Of course, since the scheduling priority H _A,n-1 is directly proportional to T _i,n and inversely proportional to W _i,n , the scheduling priority H _A, n-1 of node n-1 on pipeline A can also be determined by the following formula ₁ :

${\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; *</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>$

Among them, M is a constant greater than 0 and less than 1, and greater than 0 and less than 1.

Preferably, in this embodiment, each node can save and maintain a node status information table, and the node's scheduling priority, task queue depth and fixed execution time can be saved in the information table. After the scheduling priority is re-determined, the scheduling priority stored in the node state information table may be updated.

Based on the same inventive concept as Embodiment 1 of the present invention, the following devices are provided.

Embodiment two,

Embodiment 2 of the present invention provides a device for determining node scheduling priority, which is applied to a multi-core processor that determines node scheduling priority according to the depth of the task queue. The structure of the device is shown in Figure 4, including:

The determination module 11 is used to determine the node n where critical resource interlock occurs; the adjustment module 12 is used to reduce the node n closest to node n and located before node n on each pipeline where critical resource interlock occurs at node n The scheduling priority of -1, where n is a positive integer greater than 1.

The adjustment module 12 is specifically configured to be based on the proportional relationship between the scheduling priority of node n-1 and the fixed execution time of node n on each pipeline where critical resource interlock occurs at node n, and/or on each pipeline On the pipeline where critical resource interlock occurs at node n, the inverse relationship between the length of each locking time of node n reduces the scheduling priority of node n-1.

The adjustment module 12 is specifically configured to: according to the number of pipelines where critical resource interlocking occurs at node n, on each pipeline where critical resource interlocking occurs at node n, the length of each locking time of node n, in each On a pipeline where critical resource interlock occurs at node n, the fixed execution time of node n, the fixed execution time of node n-1 on pipeline A, and the task queue depth of node n-1 on pipeline A determine the node on pipeline A The scheduling priority of n-1.

The adjustment module 12 is specifically configured to determine the scheduling priority H _{A,n-1 of node n-} 1 on the pipeline A through the following formula:

${\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; *</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; )</span>$

in,

K is the number of pipeline lines where critical resource interlock occurs at node n;

W _{i, n} is the length of each locking time of node n on the ith pipeline where critical resource interlock occurs at node n;

T _i,n is the fixed execution time of node n on the i-th pipeline where critical resource interlock occurs at node n;

Q _A,n-1 is the task queue depth of node n-1 on pipeline A;

T _A,n-1 is the fixed execution time of node n-1 on pipeline A.

The adjustment module 12 is specifically configured to determine the scheduling priority H _{A,n-1 of node n-} 1 on the pipeline A through the following formula:

${\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; A</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; *</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>$

in,

K is the number of pipeline lines where critical resource interlock occurs at node n;

W _{i, n} is the length of each locking time of node n on the ith pipeline where critical resource interlock occurs at node n;

T _i,n is the fixed execution time of node n on the i-th pipeline where critical resource interlock occurs at node n;

Q _A,n-1 is the task queue depth of node n-1 on pipeline A;

T _A,n-1 is the fixed execution time of node n-1 on pipeline A;

M is a constant greater than 0 and less than 1, and The value is greater than 0 and less than 1.

According to the solutions provided by Embodiment 1 to Embodiment 2 of the present invention, it can not only reduce the possibility of multi-core competition in nodes, but also improve the performance of multi-core processors, and if node n operates critical resources, and at this time node n-1 (a node before node n) is still continuously transmitting the data to be processed to node n. At this time, data congestion will occur, which will delay the data processing time, and may cause the cache queue to overflow at node n. The solutions provided by Embodiments 1 to 2 of the invention can further avoid data congestion, reduce data processing time delay, and avoid problems of buffer queue overflow.

Obviously, those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and their equivalent technologies, the present invention also intends to include these modifications and variations.

Claims (4)

1. A node scheduling priority determining method is applied to a multi-core processor for determining node scheduling priority according to task queue depth, and is characterized by comprising the following steps:

determining a node n with critical resource interlocking;

on each pipeline with critical resource interlocking at a node n, reducing the scheduling priority of a node n-1 which is closest to the node n and is positioned in front of the node n, wherein n is a positive integer greater than 1;

wherein, on the assembly line A, the scheduling priority of the node n-1 which is nearest to the node n and is positioned before the node n is reduced, and the method specifically comprises the following steps:

and reducing the scheduling priority of the node n-1 according to the direct proportion relation between the scheduling priority of the node n-1 and the fixed execution time length of the node n on each pipeline with critical resource interlocking at the node n and/or the inverse proportion relation between the locking time length of the node n at each time on each pipeline with critical resource interlocking at the node n.

2. The method of claim 1, wherein reducing the scheduling priority of a node n-1 closest to and before the node n in the pipeline a comprises:

determining the scheduling priority of the node n-1 on the pipeline A according to the number of pipelines in which critical resource interlocking occurs at the node n, the length of each locking time of the node n on each pipeline in which critical resource interlocking occurs at the node n, the fixed execution time of the node n-1 on the pipeline A and the task queue depth of the node n-1 on the pipeline A;

determining the scheduling priority H of a node n-1 on a pipeline A by the following formula_A,n-1：

<math> <mrow> <msub> <mi>H</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mfrac> <msub> <mi>Q</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mrow> <mi>K</mi> <mo>*</mo> <msub> <mi>T</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mrow> </mfrac> <mo>*</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mi>K</mi> </munderover> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <mfrac> <msub> <mi>W</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> <msub> <mi>T</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> </mfrac> <mo>)</mo> </mrow> <mo>,</mo> </mrow> </math> Or <math> <mrow> <msub> <mi>H</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mfrac> <msub> <mi>Q</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mrow> <mi>K</mi> <mo>*</mo> <msub> <mi>T</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mrow> </mfrac> <mo>*</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mi>K</mi> </munderover> <mrow> <mo>(</mo> <mfrac> <msub> <mi>T</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> <msub> <mi>W</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> </mfrac> <mo>*</mo> <mi>M</mi> <mo>)</mo> </mrow> <mo>;</mo> </mrow> </math>

K is the number of pipelines with critical resource interlocking at the node n;

W_i,neach locking time length of the node n on the ith pipeline with the critical resource interlock at the node n;

T_i,na fixed execution duration for node n on the ith pipeline with critical resource interlock at node n;

Q_A,n-1is the task queue depth of the node n-1 on the pipeline A;

T_A,n-1a fixed execution duration for node n-1 on pipeline A;

m is a constant greater than 0 and less than 1, andis greater than 0 and less than 1.

3. A node scheduling priority determining device is applied to a multi-core processor for determining node scheduling priority according to the depth of a task queue, and is characterized by comprising the following steps:

the determining module is used for determining the node n with the critical resource interlocking;

and the adjusting module is used for reducing the scheduling priority of the node n-1 according to the direct proportion relation between the scheduling priority of the node n-1 and the fixed execution time length of the node n on each pipeline with critical resource interlocking at the node n, and/or the inverse proportion relation between the locking time length of the node n at each time on each pipeline with critical resource interlocking at the node n, wherein n is a positive integer greater than 1.

4. The apparatus of claim 3, wherein the adjustment module is specifically configured to adjust the number of pipelines in which the critical resource interlock occurs at node n, the length of each lock time of node n on each pipeline in which the critical resource interlock occurs at node n, the fixed execution time of node n on pipeline A, the fixed execution time of node n-1 on pipeline A, and the task queue depth of node n-1 on pipeline ADetermining the scheduling priority of the node n-1 on the assembly line A; and determining the scheduling priority H of the node n-1 on the pipeline A by the following formula_A,n-1：

<math> <mrow> <msub> <mi>H</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mfrac> <msub> <mi>Q</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mrow> <mi>K</mi> <mo>*</mo> <msub> <mi>T</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mrow> </mfrac> <mo>*</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mi>K</mi> </munderover> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <mfrac> <msub> <mi>W</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> <msub> <mi>T</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> </mfrac> <mo>)</mo> </mrow> <mo>,</mo> </mrow> </math> Or <math> <mrow> <msub> <mi>H</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mfrac> <msub> <mi>Q</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mrow> <mi>K</mi> <mo>*</mo> <msub> <mi>T</mi> <mrow> <mi>A</mi> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mrow> </mfrac> <mo>*</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mi>K</mi> </munderover> <mrow> <mo>(</mo> <mfrac> <msub> <mi>T</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> <msub> <mi>W</mi> <mrow> <mi>i</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> </mfrac> <mo>*</mo> <mi>M</mi> <mo>)</mo> </mrow> <mo>;</mo> </mrow> </math> K is the number of pipelines with critical resource interlocking at the node n; w_i,nEach locking time length of the node n on the ith pipeline with the critical resource interlock at the node n; t is_i,nA fixed execution duration for node n on the ith pipeline with critical resource interlock at node n; q_A,n-1Is the task queue depth of the node n-1 on the pipeline A; t is_A,n-1A fixed execution duration for node n-1 on pipeline A; m is a constant greater than 0 and less than 1, and

is greater than 0 and less than 1.

Images