Disclosure of Invention
In view of the above, the present application discloses a task scheduling method. The method is applied to a first CPU (Central processing Unit) of at least two logic processor CPUs obtained based on a hyper-threading technology, wherein a task scheduler corresponding to the first CPU maintains at least two task lists, and the at least two task lists are respectively used for storing tasks with different priorities executed by the first CPU;
the method comprises the following steps:
acquiring the priority of a task being executed by a second CPU except the first CPU in the at least two logic processor CPUs;
And responding to the priority of the task being executed by the second CPU as the highest priority, acquiring the task meeting the scheduling condition from the first task list corresponding to the highest priority by the task scheduler to execute so as to complete task scheduling under the condition that task expelling is needed.
In some embodiments, the method further comprises:
And in response to the priority of the task being executed by the second CPU being not the highest priority, acquiring the task meeting the scheduling condition from the at least two task lists by the task scheduler for execution so as to complete task scheduling without task eviction.
In some embodiments, the task scheduler is a full fair scheduler CFS, the first CPU maintains virtual time durations respectively corresponding to the tasks with different priorities, and the scheduling conditions comprise a minimum virtual time duration;
the task obtaining, by the task scheduler, a task meeting a scheduling condition from a first task list corresponding to the highest priority, including:
Acquiring a task corresponding to the minimum virtual duration from the first task list through the CFS;
the task obtaining, by the task scheduler, the task satisfying the scheduling condition from the at least two task lists includes:
and acquiring tasks corresponding to the minimum virtual time length from the at least two task lists through the CFS.
In some embodiments, the at least two task lists further comprise a second task list corresponding to other priorities, the first task list comprises a first red-black tree, the second task list comprises a second red-black tree, the first red-black tree maintains a first minimum virtual duration corresponding to each task in the first task list, and the second red-black tree maintains a second minimum virtual duration corresponding to each task in the second task list;
the first CPU also maintains a first variable and a second variable; the first variable indicates a gap between the first minimum virtual duration and the second minimum virtual duration before performing the task for eviction, and the second variable indicates an accumulated gap between the first minimum virtual duration and the second minimum virtual duration due to task eviction in the case of performing at least one task for eviction;
The method further comprises the steps of:
Under the condition that task eviction is needed, before task scheduling is carried out, responding to the current scheduling as first-time eviction scheduling, and updating the first variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current second variable.
In some embodiments, the method further comprises:
Under the condition that task eviction is not needed, before task scheduling is carried out, responding to the first non-eviction scheduling after the task eviction is carried out in the current scheduling, and updating the second variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current first variable.
In some embodiments, the obtaining, by the CFS, the task corresponding to the minimum virtual time length from the at least two task lists includes:
comparing the sum of the second minimum virtual time length and the updated second variable with the size of the first minimum virtual time length;
responding to the fact that the sum of the second minimum virtual time length and the updated second variable is smaller than the first minimum virtual time length, and acquiring a task corresponding to the second minimum virtual time length from the second red black tree through the CFS;
And responding to the sum of the second minimum virtual time length and the updated second variable, wherein the sum is larger than or equal to the first minimum virtual time length, and acquiring a task corresponding to the first minimum virtual time length from the first red-black tree through the CFS.
In some embodiments, the method further comprises:
The method comprises the steps of acquiring the priority of a task to be processed, wherein the task to be processed comprises a task needing to be migrated into or migrated out of a first CPU;
Under the condition that the priority of the task to be processed is the highest priority, correspondingly processing the task to be processed aiming at the first red-black tree;
and under the condition that the priority of the task to be processed is other priorities, correspondingly processing the task to be processed aiming at the second red-black tree.
In some embodiments, before or after migrating the task to be processed, the method further comprises:
And updating the first minimum virtual duration and the second minimum virtual duration to the maximum value of the first red black tree and the second red black tree in response to at least one red black tree of the first red black tree and the second red black tree not including any tasks and the first CPU not executing the tasks of the priorities corresponding to the at least one red black tree.
In some embodiments, after updating the first variable, further comprising:
and in response to the updated first variable being less than or equal to 0, setting the first variable to a preset value for increasing the second minimum virtual duration.
The application also provides a task scheduling device which is applied to a first CPU in at least two logic processor CPUs obtained based on the hyper-threading technology, wherein a task scheduler corresponding to the first CPU maintains at least two task lists;
the device comprises:
The acquisition module acquires the priority of a task being executed by a second CPU except the first CPU in the at least two logic processor CPUs;
And the first scheduling module is used for responding to the fact that the priority of the task being executed by the second CPU is the highest priority, and acquiring the task meeting the scheduling condition from the first task list corresponding to the highest priority through the task scheduler to execute so as to complete task scheduling under the condition that task expelling is needed.
In some embodiments, the apparatus further comprises:
And the second scheduling module is used for acquiring tasks meeting the scheduling conditions from the at least two task lists through the task scheduler to execute so as to complete task scheduling without task eviction in response to the priority of the task being executed by the second CPU being not the highest priority.
In some embodiments, the task scheduler is a full fair scheduler CFS, the first CPU maintains virtual time durations respectively corresponding to the tasks with different priorities, and the scheduling conditions comprise a minimum virtual time duration;
the first scheduling module is specifically configured to:
Acquiring a task corresponding to the minimum virtual duration from the first task list through the CFS;
the second scheduling module is specifically configured to:
and acquiring tasks corresponding to the minimum virtual time length from the at least two task lists through the CFS.
In some embodiments, the at least two task lists further comprise a second task list corresponding to other priorities, the first task list comprises a first red-black tree, the second task list comprises a second red-black tree, the first red-black tree maintains a first minimum virtual duration corresponding to each task in the first task list, and the second red-black tree maintains a second minimum virtual duration corresponding to each task in the second task list;
the first CPU also maintains a first variable and a second variable; the first variable indicates a gap between the first minimum virtual duration and the second minimum virtual duration before performing the task for eviction, and the second variable indicates an accumulated gap between the first minimum virtual duration and the second minimum virtual duration due to task eviction in the case of performing at least one task for eviction;
the apparatus further comprises:
And the first variable updating module is used for responding to the current scheduling as the first eviction scheduling before performing task scheduling under the condition that task eviction is needed, and updating the first variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current second variable.
In some embodiments, the apparatus further comprises:
And the second variable updating module is used for responding to the first non-eviction scheduling after the task eviction for the current scheduling before the task scheduling under the condition that the task eviction is not needed, and updating the second variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current first variable.
In some embodiments, the second scheduling module is specifically configured to:
comparing the sum of the second minimum virtual time length and the updated second variable with the size of the first minimum virtual time length;
responding to the fact that the sum of the second minimum virtual time length and the updated second variable is smaller than the first minimum virtual time length, and acquiring a task corresponding to the second minimum virtual time length from the second red black tree through the CFS;
And responding to the sum of the second minimum virtual time length and the updated second variable, wherein the sum is larger than or equal to the first minimum virtual time length, and acquiring a task corresponding to the first minimum virtual time length from the first red-black tree through the CFS.
In some embodiments, the apparatus further comprises:
The task maintenance module is used for acquiring the priority of a task to be processed, wherein the task to be processed comprises a task which needs to be migrated into or out of the first CPU;
Under the condition that the priority of the task to be processed is the highest priority, correspondingly processing the task to be processed aiming at the first red-black tree;
and under the condition that the priority of the task to be processed is other priorities, correspondingly processing the task to be processed aiming at the second red-black tree.
In some embodiments, the apparatus further comprises:
and the synchronization module is used for updating the first minimum virtual duration and the second minimum virtual duration to the maximum value of the first red-black tree and the second red-black tree in response to the fact that at least one red-black tree does not comprise any task and the first CPU does not execute the task with the priority corresponding to the at least one red-black tree.
In some embodiments, the apparatus further comprises:
And the setting module is used for setting the first variable to a preset value for increasing the second minimum virtual duration in response to the updated first variable being smaller than or equal to 0.
The application also proposes an electronic device comprising:
a processor;
a memory for storing processor-executable instructions;
wherein the processor implements a task scheduling method as illustrated in any of the embodiments described above by executing the executable instructions.
The present application also proposes a computer readable storage medium storing a computer program for causing a processor to execute a task scheduling method as shown in any one of the embodiments described above.
In the technical scheme disclosed in the foregoing embodiment, since the task scheduler corresponding to the first CPU maintains at least two task lists, where the at least two task lists are respectively used to store tasks with different priorities executed by the first CPU, in the case of an eviction phenomenon, a task with a highest priority may be directly obtained from the first task list corresponding to a level with a highest priority to execute, so as to avoid high overhead operation caused by task queuing in and out, and improve task scheduling efficiency, thereby possibly avoiding task delay and jitter.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the application as claimed.
Detailed Description
Reference will now be made in detail to exemplary embodiments, examples of which are illustrated in the accompanying drawings. When the following description refers to the accompanying drawings, the same numbers in different drawings refer to the same or similar elements, unless otherwise indicated. The implementations described in the following exemplary examples do not represent all implementations consistent with the application. Rather, they are merely examples of apparatus and methods consistent with aspects of the application as detailed in the accompanying claims.
The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the application. As used in this specification and the appended claims, the singular forms "a," "an," and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It should also be understood that the term "and/or" as used herein refers to and encompasses any or all possible combinations of one or more of the associated listed items. It will also be understood that the word "if," as used herein, depending on the context, may be interpreted as "at the time of an..once-all" or "when an..once-all" or "in response to a determination.
The application provides a task scheduling method. According to the method, at least two task lists respectively storing tasks of different grades are maintained, so that under the condition that an eviction phenomenon occurs, tasks with the highest priority can be directly obtained from the first task list corresponding to the grade with the highest priority to be executed, high-overhead operation caused by task queuing in and out is avoided, task scheduling efficiency is improved, and task delay and jitter are possibly avoided.
Referring to fig. 1, fig. 1 is a flowchart of a task scheduling method according to the present application. As shown in FIG. 1, the method may include S102-S104.
The method can be applied to a first CPU of at least two logic processor CPUs obtained based on the hyper-threading technology, a task scheduler corresponding to the first CPU maintains at least two task lists, and the at least two task lists are respectively used for storing tasks with different priorities executed by the first CPU.
The first CPU may be any CPU of the at least two logical CPUs. The first CPU is correspondingly provided with a task scheduler.
The task scheduler may be configured to schedule tasks from a task list for execution by the first CPU. The task scheduler may be any type of scheduler. In some embodiments, the task scheduler may be a CFS (Completely Fair Scheduler, full-fair task scheduler).
The task list may be used to store tasks assigned to the first CPU in a preset data storage format. In the present application, the at least two task lists may correspond to ready queues (queues storing tasks) corresponding to the task schedulers. In some embodiments the task list may store tasks in a linked list, binary tree, red-black tree, or like data storage format.
The task may refer to a service executed by the CPU. The services may have different names at different stages. For example, during the ready queue phase, traffic may be referred to as an entity. During the CPU execution phase, traffic may be referred to as processes. The present application refers to services collectively as tasks.
The priority may indicate an order of execution of the tasks. When two CPUs under the same hyper-threading execute tasks with different priorities, the execution of the tasks with high priorities needs to be guaranteed preferentially. In the application, the tasks can be assigned with priority according to the service requirements. Task priorities may include at least two levels.
S102, acquiring the priority of the task being executed by a second CPU except the first CPU in the at least two logic processor CPUs.
The second CPU may be at least one CPU.
In some embodiments, a task identifier may be set in the first CPU. The identification may indicate a priority of the task being performed in the second CPU. The second CPU may monitor the priorities of tasks executed by itself, and if it finds that a task of the highest priority is being executed, send an instruction to the first CPU to set the task identifier as a first identifier, and if it finds that a task of another priority is being executed, send an instruction to the first CPU to set the task identifier as a second identifier.
When executing S102, the first CPU may obtain the priority of the task being executed by the second CPU by obtaining the current task identifier.
In some embodiments, upon execution of S102, the first CPU may generate a task priority acquisition instruction to the second CPU, and the second CPU may send the task priority being executed to the first CPU in response to the instruction.
S104, responding to the priority of the task being executed by the second CPU as the highest priority, and acquiring the task meeting the scheduling condition from the first task list corresponding to the highest priority by the task scheduler to execute so as to complete task scheduling under the condition that task expelling is needed.
If the priority of the task being executed by the second CPU is the highest priority, task eviction is needed in the first CPU. Task evictions may include two scenarios.
In the first scenario, the first CPU does not currently execute the task and needs to acquire the next task for execution, and at this time, the task with the highest priority meeting the scheduling condition can be directly acquired from the first task list.
In a second scenario, the first CPU is currently executing other priority tasks, and needs to suspend executing the other priority tasks, and acquire the task with the highest priority meeting the scheduling condition from the first task list.
Task schedulers generally have a task scheduling principle, and when scheduling tasks, tasks meeting scheduling conditions can be obtained based on a preset scheduling principle. The scheduling conditions shown in the application are the scheduling conditions corresponding to the task scheduler.
In the scheme, the task scheduler corresponding to the first CPU maintains at least two task lists, and the at least two task lists are respectively used for storing tasks with different priorities executed by the first CPU, so that under the condition of an eviction phenomenon, the task with the highest priority can be directly acquired from the first task list corresponding to the level with the highest priority to be executed, high overhead operation caused by task queuing in and out is avoided, task scheduling efficiency is improved, and task delay and jitter can be possibly avoided.
In some embodiments, the task scheduler is a CFS. And the first CPU maintains virtual time lengths respectively corresponding to the tasks with different priorities. The scheduling condition includes a minimum virtual time length.
The CFS assigns a virtual duration to each task in the task list. If a task is scheduled to be executed, the corresponding virtual time length is increased continuously, and the virtual time length of the task which is not executed is unchanged. The higher the priority task, the smaller the initial virtual time length, and the slower the virtual time length increases when executing a task.
The scheduling condition corresponding to the CFS is the minimum virtual duration. I.e., the CFS may select the task execution corresponding to the lowest virtual duration.
When executing S104, S1041 may be executed, and a task corresponding to the minimum virtual duration is obtained from the first task list through the CFS. Therefore, the first CPU can acquire the task corresponding to the minimum virtual time length from the tasks with the highest priority to execute.
In some embodiments, when the eviction is not required, the first CPU may acquire the task satisfying the scheduling condition from the at least two task lists, so as to normally acquire the task for execution.
Referring to fig. 2, fig. 2 is a flowchart of an image processing method according to the present application. As shown in FIG. 2, the method includes S106 in parallel with S104 in addition to S102-S104.
And S106, acquiring tasks meeting the scheduling conditions from the at least two task lists by the task scheduler to execute so as to complete task scheduling without task eviction, wherein the priorities of the tasks being executed by the second CPU are not the highest priorities.
If the priority of the task being executed by the second CPU is not the highest priority, task eviction is not needed in the first CPU. When the task is not required to be evicted, the first CPU can acquire the task meeting the scheduling condition from the at least two task lists to execute so as to normally acquire the task meeting the scheduling condition.
In some embodiments, the task scheduler is a CFS. And the first CPU maintains virtual time lengths respectively corresponding to the tasks with different priorities. The scheduling condition includes a minimum virtual time length.
When executing S106, S1061 may be executed, and a task corresponding to the minimum virtual duration is acquired from the at least two task lists through the CFS. Therefore, the first CPU can acquire tasks with all priorities, and the task corresponding to the minimum virtual duration can be executed.
In some embodiments, at least two task lists that may be corresponding with a task scheduler (CFS) may include a red-black tree. The red-black tree is a self-balancing binary search tree. The red-black tree can automatically maintain the minimum key value, namely, the node corresponding to the minimum key value in each node can be determined, and the node is placed at a preset position, so that the query is facilitated.
In the application, the key value of the node included in the red black tree can be determined based on the virtual time length of the task. The information stored by the node may be determined based on the task information. The red-black tree can maintain the current minimum virtual time length when the task is migrated in and migrated out and the CPU completes the task being executed, so that the task corresponding to the minimum virtual time length can be conveniently acquired.
In the case of eviction, the virtual duration of the highest priority task will gradually increase as the task is executed, so that the minimum virtual duration of the red-black tree maintenance corresponding to the highest priority task will also increase. The virtual time length of the tasks with other priorities is kept unchanged because the tasks are not executed, and the minimum virtual time length maintained by the red-black tree corresponding to the tasks with other priorities is also kept unchanged. In so doing, it is possible to increase the priority of other priority tasks by evicting. This is not allowed.
For example, assume that a first CPU needs to execute high priority task A, B and low priority tasks 1, 2. As an eviction occurs in the first CPU, this results in a higher priority task AB being continuously executed, which will result in the virtual time duration corresponding to the lower priority tasks 1 and 2 being potentially much smaller than task AB. When eviction disappears, it is likely that both low priority tasks 1 and 2 will be performed for a long period of time. This is equivalent to increasing the priority of low priority tasks by eviction. This situation is not allowed.
In order to solve the foregoing problems, in the present application, a first variable and a second variable are added to record a gap between a mangrove corresponding to a highest priority and a minimum virtual duration maintained by a mangrove corresponding to other priorities due to an eviction, so as to facilitate compensation for virtual durations of tasks of other priorities, so as to offset the gap caused by the eviction. In some embodiments, the compensated real virtual duration may be obtained by adding the gap to the virtual durations of other priority tasks.
The method for updating the first variable and the second variable will be described below with reference to the embodiments.
In some embodiments, the at least two task lists further include a second task list corresponding to other priorities, the first task list includes a first red-black tree, the second task list includes a second red-black tree, the first red-black tree maintains a first minimum virtual duration corresponding to each task in the first task list, and the second red-black tree maintains a second minimum virtual duration corresponding to each task in the second task list.
The first CPU also maintains a first variable and a second variable, wherein the first variable indicates a difference between the first minimum virtual duration and the second minimum virtual duration before performing the task for eviction, and the second variable indicates an accumulated difference between the first minimum virtual duration and the second minimum virtual duration due to the task for eviction in the case of performing at least one task for eviction. In the application, the first variable can be recorded as start, and the second variable can be recorded as spin.
The first variable may be updated in the present application by step S21.
S21, under the condition that task eviction is needed, before task scheduling is carried out, responding to the current scheduling as first-time eviction scheduling, and updating the first variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current second variable.
First-time eviction schedule refers to the first-time schedule by the CFS in the case of a task eviction being required.
Therefore, the difference between the first minimum virtual time length and the second minimum virtual time length before the eviction can be accurately recorded, the accumulated difference (namely the second variable) between the first minimum virtual time length and the second minimum virtual time length caused by task eviction can be conveniently determined after the eviction is completed, and the virtual time length difference caused by the eviction can be conveniently compensated.
In some embodiments, when S21 is performed, S211-S212 may be performed.
S211, in the case that the task eviction is determined to be needed, judging whether the current scheduling is the first eviction scheduling or not by judging whether the first variable is an initial value (for example, 0).
In one aspect, the present application sets the first variable to an initial value in the following two cases.
First, a first variable is set to an initial value in response to at least one of the first red-black tree and the second red-black tree not including any tasks, and the first CPU does not perform tasks of the at least one red-black tree corresponding priority. This can be understood as an initialization of the first variable.
Second, the first variable may be set to the initial value after the second variable is updated when the eviction into the non-eviction situation is completed (the method of updating the second variable is described later).
In another aspect, the present application updates the first variable to another value (possibly a non-initial value) prior to the first eviction schedule.
Due to the foregoing two aspects, if the first variable is an initial value in a case where it is determined that task eviction is required, it is explained that the present schedule is the first eviction schedule. And if the first variable is not the initial value, indicating that the scheduling is not the first eviction scheduling.
And S212, in response to the current scheduling being the first eviction scheduling, updating the first variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current second variable.
The first variable may be understood as a real gap between the first minimum virtual time length and the second minimum virtual time length before the first eviction schedule.
When executing S212, the real second minimum virtual time length after the previous eviction is compensated can be obtained through the sum of the current second minimum virtual time length and the current second variable, and the difference between the real second minimum virtual time length and the current first virtual time length is determined to update the first variable.
For example, assume that the preset initial value is 0. In the case where it is determined that task eviction is required, it may be determined whether the value of the current first variable start is 0. If so, this task eviction may be interpreted as a first task eviction, and then the update of the start variable may be performed according to equation (1) below.
start=min_vrtunder-min_vrthigh+spread................1;
Where start represents a first variable, tap represents a second variable, min_vrtunder represents a second minimum virtual duration, and min_vrthigh represents a first minimum virtual duration. The min_vrtunder +spin can obtain a real second minimum virtual duration after the previous eviction is compensated, and then subtracted from the min_vrthigh, so as to obtain a real difference between the first minimum virtual duration and the second minimum virtual duration before the first eviction schedule, i.e. the start at the moment.
The second variable may be updated in the present application by step S22.
S22, under the condition that task eviction is not needed, before task scheduling is carried out, responding to the first non-eviction scheduling after the task eviction for the current scheduling, and updating the second variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current first variable.
The first non-eviction schedule refers to a first schedule by the CFS in the case where no task eviction is required after eviction.
Therefore, after the completion of the eviction, the accumulated difference (namely the second variable) between the first minimum virtual duration and the second minimum virtual duration caused by the task eviction can be accurately recorded, and the virtual duration difference caused by the eviction can be conveniently compensated.
In some embodiments, when S22 is performed, S221-S222 may be performed.
S221, in the case that the task eviction is not required, judging whether the current scheduling is the first non-eviction scheduling or not by judging whether the first variable is an initial value (for example, 0).
Based on a similar principle as in S211, if the first variable is other value in the case where it is determined that task eviction is not required, this schedule is illustrated as the first non-eviction schedule after the occurrence of eviction. And if the first variable is an initial value, the current scheduling is not the first non-eviction scheduling.
S222, in response to the fact that the current scheduling is the first non-eviction scheduling after task eviction, updating the second variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current first variable.
The second variable may be understood as an accumulated gap between the first minimum virtual time period and the second minimum virtual time period after the eviction.
The first variable may be understood as the existing gap between the first minimum virtual time period and the second minimum virtual time period before the last eviction occurs.
When executing S222, a difference between the current second minimum virtual duration and the current first minimum virtual duration may be determined, where the second minimum virtual duration and the first minimum virtual duration are newly increased after the last eviction is performed. Adding the newly added gap to the gap that existed before the last eviction was made (i.e., the first variable), the accumulated gap is obtained to update the second variable.
For example, assume that the preset initial value is 0. In the case where it is determined that task eviction is not required, it may be determined whether the value of the current first variable start is 0. If not, this task eviction may be interpreted as a first non-task eviction, and then the update of the thread variable may be performed according to equation (2) below.
spread=min_vrthigh-min_vrtunder+start................2;
Where start represents a first variable, tap represents a second variable, min_vrtunder represents a second minimum virtual duration, and min_vrthigh represents a first minimum virtual duration. The min_vrthigh-min_vrtunder may obtain a difference between the second minimum virtual duration and the first minimum virtual duration after the last eviction, and then add the difference with the start, that is, add the difference with the difference existing before the last eviction, to obtain an accumulated difference, that is, a spin, caused by task eviction. The start may also be set to 0 afterwards so that the spin may not be updated in the next non-eviction task.
After updating the second variable, an accumulated difference between the first minimum virtual duration and the second minimum virtual duration due to the eviction may be recorded, so that the second minimum virtual duration may be compensated based on the accumulated difference to offset the virtual duration difference caused by the eviction.
In some embodiments, the first variable obtained in the step S21 may be less than or equal to 0, in which case the second variable obtained in the step S22 may be less than or equal to 0, and when the second virtual duration is compensated based on the second variable, the value of the second virtual duration may be reduced, so as to raise the priority of other priority tasks, which is not allowed.
In the present application, in response to the updated first variable being less than or equal to 0, the first variable may be set to a preset value for increasing the second minimum virtual duration. In the application, the preset value can be marked as epsilon.
The preset number epsilon is a preset positive number. Setting the first variable to a preset value can ensure that the second variable updated in S22 is a number greater than 0, thereby ensuring that the second minimum virtual duration is increased without decreasing the second minimum virtual duration when the second minimum virtual duration is compensated by the second variable, and further avoiding the priority of other priority tasks from being improved.
In some embodiments, upon execution of S1061, the CFS may perform a non-eviction schedule based on the compensated real second virtual duration. Non-eviction schedule refers to task scheduling by the CFS in situations where task eviction is not required.
Referring to fig. 3, fig. 3 is a flow chart illustrating a non-eviction scheduling method according to the present application. The steps shown in fig. 3 are detailed description of S1061. As shown in fig. 3, the method may include S301-S303 when performing S1061.
S301, comparing the sum of the second minimum virtual time length and the updated second variable with the size of the first minimum virtual time length.
And the sum of the second minimum virtual time length and the updated second variable is the real second minimum virtual time length obtained after compensating the difference caused by the eviction.
S302, responding to the fact that the sum of the second minimum virtual time length and the updated second variable is smaller than the first minimum virtual time length, and acquiring tasks corresponding to the second minimum virtual time length from the second red and black tree through the CFS.
S303, responding to the sum of the second minimum virtual time length and the updated second variable, wherein the sum is larger than or equal to the first minimum virtual time length, and acquiring a task corresponding to the first minimum virtual time length from the first red black tree through the CFS.
According to the CFS scheduling principle, if the sum of the second minimum virtual time length and the updated second variable is smaller than the first minimum virtual time length, the task in the second red black tree is required to be executed currently, and therefore tasks with other priorities corresponding to the second minimum virtual time length can be acquired from the second red black tree. And if the sum of the second minimum virtual time length and the updated second variable is greater than or equal to the first minimum virtual time length, indicating that the task in the first red-black tree should be executed currently, and acquiring the task with the highest priority corresponding to the second minimum virtual time length from the second red-black tree.
For example, when selecting a non-eviction task, the second minimum virtual time length may be compared to the updated sum of the second variable and the size of the first minimum virtual time length.
And if the sum of the second minimum virtual time length and the updated second variable and the first minimum virtual time length meet the formula 3, selecting the task from the second red-black tree according to the CFS scheduling principle, and if the sum of the second minimum virtual time length and the updated second variable does not meet the formula 3, selecting the task from the first red-black tree.
min_vrtunder+spread＜min_vrthigh................3;
Where min_vrtunder represents a second minimum virtual time length, min_vrthigh represents a first minimum virtual time length, and spin represents a second variable, i.e., the cumulative gap between the first minimum virtual time length and the second minimum virtual time length due to task eviction. The real min_vrtunder obtained by compensating the difference caused by the eviction can be obtained through the min_vrtunder +spin, if the min_vrtunder+spread＜min_vrthigh can indicate that the minimum virtual time length of the first red black tree is longer than the real minimum virtual time length of the second red black tree, the task is required to be selected from the total second red black tree according to the CFS scheduling rule.
In some embodiments, a method of maintaining tasks in a red-black tree is also included.
Referring to fig. 4, fig. 4 is a flow chart of a method for maintaining tasks in a red-black tree according to the present application. As shown in fig. 4, the illustrated method may include S401-S403.
S401, acquiring the priority of a task to be processed, wherein the task to be processed comprises a task which needs to be migrated in or out of the first CPU.
In the application, a priority identification is allocated to the task. The priority of the task to be processed can be determined through the identification.
S402, under the condition that the priority of the task to be processed is the highest priority, correspondingly processing the task to be processed aiming at the first red-black tree.
In some embodiments, the virtual time length of the task maintained in the red-black tree has a conversion relationship with the virtual time length of the task maintained by the CFS, which requires reliance on the minimum virtual time length maintained by the red-black tree. That is, when the task is migrated in and out, virtual time length conversion is required according to the current minimum virtual time length of the red-black tree.
If the task is the migration task, the first minimum virtual duration maintained by the first red-black tree can be updated according to the virtual duration of the task currently being scheduled, then the virtual duration of the task to be processed maintained by the red-black tree is determined based on the first minimum virtual duration, and the task to be processed is added into the first red-black tree as a node based on the virtual duration, so that task migration is completed. If the task is a migration task, the first minimum virtual duration maintained by the first red black tree can be updated according to the virtual duration of the task currently being scheduled, then the virtual duration of the task to be processed maintained by the CFS is determined based on the first minimum virtual duration, and the node corresponding to the task to be processed is deleted in the first red black tree, so that task migration is completed.
The task being scheduled is denoted as curr, and the virtual duration of the task is denoted as vruntimecurr. Regardless of whether the task is migrated or migrated, vruntimecurr of the curr may be updated according to the CFS rules and the minimum virtual duration of the red-black tree corresponding to the curr may be updated. If curr is a task in the first red black tree, the first minimum virtual duration min_vrthigh of the first red black tree is updated, and if curr is a task in the second red black tree, the second minimum virtual duration min_vrtunder of the second red black tree is updated.
If the task is a task to be processed with high priority, the virtual duration of the task to be processed can be obtained based on the min_vrthigh and inserted into the first red-black treehigh as a node.
If the task to be processed with high priority is migrated, the virtual duration of the task to be processed can be obtained based on the min_vrtunder, and the corresponding node in the second red-black treeunder is deleted.
S403, under the condition that the priority of the task to be processed is other priorities, correspondingly processing the task to be processed aiming at the second red-black tree.
The corresponding processing of the task to be processed of other priorities may refer to S402, and will not be described in detail herein.
The tasks can be accurately maintained in the first red black tree and the second red black tree through S401-S403, and follow-up accurate task scheduling is facilitated.
In some embodiments, during maintenance tasks, in response to at least one of the first red-black tree and the second red-black tree not including any tasks, and the first CPU does not perform tasks of the at least one red-black tree corresponding priority, the first minimum virtual duration and the second minimum virtual duration are updated to a maximum of the two.
Therefore, after the tasks with any priority are executed, the minimum virtual time lengths maintained by the two red-black trees are synchronized, so that the virtual time lengths corresponding to the tasks maintained by the two red-black trees are synchronized. In some embodiments, after synchronization of the two red-black tree virtual durations may also be completed, a first variable maintained by the first CPU indicating a gap between the two red-black tree virtual durations and a second variable indicating an accumulated gap between the two red-black tree virtual durations due to eviction may be set to an initial value (e.g., 0).
An embodiment will be described below taking a scenario in which an online task and an offline task are mixed and deployed as an example.
The CPU executing the task can simulate the first CPU and the second CPU through the hyper-threading. The following takes the first CPU as an execution subject.
The first CPU can perform task scheduling in a CFS mode. The CFS may maintain a first red-black tree storing online tasks and a second red-black tree storing offline tasks. The online tasks are high-priority tasks, and the offline tasks are low-priority tasks.
The first CPU may maintain the first variable start and the second variable thread, and the maintenance methods thereof may refer to S21 and S22 respectively. By adding the first variable start and the second variable tap, the gap between the minimum virtual time length maintained by the red black tree corresponding to the online task and the red black tree corresponding to the offline task due to the occurrence of the eviction can be recorded, so that the virtual time length of the evicted offline task can be conveniently compensated, and the gap caused by the eviction can be offset.
The second CPU can send an instruction to the first CPU under the condition of executing the online task by the second CPU, so that the indication task identifier maintained in the first CPU is set as a first identifier, and the second CPU is indicated to be executing the online task currently.
The second CPU can send an instruction to the first CPU under the condition of executing the offline task by the second CPU, so that the indication task identifier maintained in the first CPU is set as a second identifier to indicate that the second CPU is currently executing the offline task.
The first CPU may determine the priority of the task being performed by the second CPU via the task identification.
If the task identifier is the first identifier, task eviction needs to occur, and the first CPU can acquire an online task corresponding to the minimum virtual duration from the first red black tree through CFS.
If the task identifier is the second identifier, task eviction is not needed, and the second CPU can add the second minimum virtual duration maintained in the second red-black tree with the second variable to obtain a real second minimum virtual duration after the eviction compensation, and then compare the real second minimum virtual duration with the first minimum virtual duration maintained in the first red-black tree. And if the real second minimum virtual time length and the first minimum virtual time length meet the formula 3, acquiring the offline task from the second red-black tree. If the real second minimum virtual time length and the first minimum virtual time length do not meet the formula 3, acquiring an online task from the first red-black tree.
In the embodiment, the CFS corresponding to the first CPU maintains two red black trees respectively storing the online task and the offline task, so that the online task can be directly obtained from the first red black tree under the condition of the expelling phenomenon, high overhead operation caused by the task queuing in and out in the prior art is avoided, the task scheduling efficiency is improved, and task delay and jitter are possibly avoided.
In this example, the virtual duration corresponding to the evicted offline task may be compensated by the first variable and the second variable, so as to ensure that the task may be normally acquired in the non-eviction schedule.
In accordance with the foregoing embodiments, the present application proposes a task scheduling device 50. The device can be applied to a first CPU in at least two logic processor CPUs obtained based on the hyper-threading technology, a task scheduler corresponding to the first CPU maintains at least two task lists, and the at least two task lists are respectively used for storing tasks with different priorities executed by the first CPU.
Referring to fig. 5, fig. 5 is a schematic structural diagram of a task scheduling device according to the present application.
As shown in fig. 5, the apparatus 50 may include:
An acquisition module 51 that acquires priorities of tasks being executed by a second CPU other than the first CPU among the at least two logical processor CPUs;
The first scheduling module 52, in response to the priority of the task being executed by the second CPU being the highest priority, obtains, by the task scheduler, a task meeting a scheduling condition from a first task list corresponding to the highest priority, and executes the task to complete task scheduling in a case where task eviction is required.
In some embodiments, the apparatus 50 further comprises:
And the second scheduling module is used for acquiring tasks meeting the scheduling conditions from the at least two task lists through the task scheduler to execute so as to complete task scheduling without task eviction in response to the priority of the task being executed by the second CPU being not the highest priority.
In some embodiments, the task scheduler is a full fair scheduler CFS, the first CPU maintains virtual time durations respectively corresponding to the tasks with different priorities, and the scheduling conditions comprise a minimum virtual time duration;
the first scheduling module 52 is specifically configured to:
Acquiring a task corresponding to the minimum virtual duration from the first task list through the CFS;
the second scheduling module is specifically configured to:
and acquiring tasks corresponding to the minimum virtual time length from the at least two task lists through the CFS.
In some embodiments, the at least two task lists further comprise a second task list corresponding to other priorities, the first task list comprises a first red-black tree, the second task list comprises a second red-black tree, the first red-black tree maintains a first minimum virtual duration corresponding to each task in the first task list, and the second red-black tree maintains a second minimum virtual duration corresponding to each task in the second task list;
the first CPU also maintains a first variable and a second variable; the first variable indicates a gap between the first minimum virtual duration and the second minimum virtual duration before performing the task for eviction, and the second variable indicates an accumulated gap between the first minimum virtual duration and the second minimum virtual duration due to task eviction in the case of performing at least one task for eviction;
The apparatus 50 further comprises:
And the first variable updating module is used for responding to the current scheduling as the first eviction scheduling before performing task scheduling under the condition that task eviction is needed, and updating the first variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current second variable.
In some embodiments, the apparatus 50 further comprises:
And the second variable updating module is used for responding to the first non-eviction scheduling after the task eviction for the current scheduling before the task scheduling under the condition that the task eviction is not needed, and updating the second variable according to the current first minimum virtual duration, the current second minimum virtual duration and the current first variable.
In some embodiments, the second scheduling module is specifically configured to:
comparing the sum of the second minimum virtual time length and the updated second variable with the size of the first minimum virtual time length;
responding to the fact that the sum of the second minimum virtual time length and the updated second variable is smaller than the first minimum virtual time length, and acquiring a task corresponding to the second minimum virtual time length from the second red black tree through the CFS;
And responding to the sum of the second minimum virtual time length and the updated second variable, wherein the sum is larger than or equal to the first minimum virtual time length, and acquiring a task corresponding to the first minimum virtual time length from the first red-black tree through the CFS.
In some embodiments, the apparatus 50 further comprises:
The task maintenance module is used for acquiring the priority of a task to be processed, wherein the task to be processed comprises a task which needs to be migrated into or out of the first CPU;
Under the condition that the priority of the task to be processed is the highest priority, correspondingly processing the task to be processed aiming at the first red-black tree;
and under the condition that the priority of the task to be processed is other priorities, correspondingly processing the task to be processed aiming at the second red-black tree.
In some embodiments, the apparatus 50 further comprises:
and the synchronization module is used for updating the first minimum virtual duration and the second minimum virtual duration to the maximum value of the first red-black tree and the second red-black tree in response to the fact that at least one red-black tree does not comprise any task and the first CPU does not execute the task with the priority corresponding to the at least one red-black tree.
In some embodiments, the apparatus 50 further comprises:
And the setting module is used for setting the first variable to a preset value for increasing the second minimum virtual duration in response to the updated first variable being smaller than or equal to 0.
The embodiment of the task scheduling device disclosed by the application can be applied to electronic equipment. Accordingly, an electronic device is disclosed that may include a processor.
A memory for storing processor-executable instructions.
The processor is configured to call the executable instructions stored in the memory to implement the task scheduling method shown in any of the foregoing embodiments.
Referring to fig. 6, fig. 6 is a schematic diagram of a hardware structure of an electronic device according to the present application.
As shown in fig. 6, the electronic device may include a processor for executing instructions, a network interface for making a network connection, a memory for storing operating data for the processor, and a non-volatile memory for storing instructions corresponding to the task scheduler.
The embodiment of the device may be implemented by software, or may be implemented by hardware or a combination of hardware and software. Taking software implementation as an example, the device in a logic sense is formed by reading corresponding computer program instructions in a nonvolatile memory into a memory by a processor of an electronic device where the device is located for operation. In terms of hardware, in addition to the processor, the memory, the network interface, and the nonvolatile memory shown in fig. 6, the electronic device in which the apparatus is located in the embodiment generally includes other hardware according to the actual function of the electronic device, which will not be described herein.
It will be appreciated that, in order to increase the processing speed, the device corresponding instructions may also be stored directly in the memory, which is not limited herein.
The present application proposes a computer readable storage medium storing a computer program that can be used to cause a processor to execute the task scheduling method shown in any of the foregoing embodiments.
One skilled in the relevant art will recognize that one or more embodiments of the application may be provided as a method, system, or computer program product. Accordingly, one or more embodiments of the application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, one or more embodiments of the application may take the form of a computer program product on one or more computer-usable storage media (including, but not limited to, disk storage, optical storage, etc.) having computer-usable program code embodied therein.
The term "and/or" as used herein means at least one of the two, for example, "A and/or B" includes three schemes A, B, and "A and B".
The embodiments of the present application are described in a progressive manner, and the same and similar parts of the embodiments are all referred to each other, and each embodiment is mainly described in the differences from the other embodiments. In particular, for data processing apparatus embodiments, the description is relatively simple, as it is substantially similar to method embodiments, with reference to the description of method embodiments in part.
Specific embodiments of the present application have been described. Other embodiments are within the scope of the following claims. In some cases, the acts or steps recited in the claims may be performed in a different order than in the embodiments and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some embodiments, multitasking and parallel processing are also possible or may be advantageous.
Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly embodied computer software or firmware, in computer hardware including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible, non-transitory program carrier for execution by, or to control the operation of, data processing apparatus. Alternatively or additionally, the program instructions may be encoded on a manually-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode and transmit information to suitable receiver apparatus for execution by data processing apparatus. The computer storage medium may be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them.
The processes and logic flows described in this application can be performed by one or more programmable computers executing one or more computer programs to perform corresponding functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).
Computers suitable for executing computer programs include, for example, general purpose and/or special purpose microprocessors, or any other type of central processing system. Typically, the central processing system will receive instructions and data from a read only memory and/or a random access memory. The essential elements of a computer include a central processing system for carrying out or executing instructions and one or more memory devices for storing instructions and data. Typically, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks, etc. However, a computer does not have to have such a device. Furthermore, the computer may be embedded in another device, such as a mobile phone, a Personal Digital Assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device such as a Universal Serial Bus (USB) flash drive, to name a few.
Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices including, for example, semiconductor memory devices (e.g., EPROM, EEPROM, and flash memory devices), magnetic disks (e.g., internal hard disk or removable disks), magneto-optical disks, and 0xcd_00rom and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.
While the application contains many specific implementation details, these should not be construed as limiting the scope of any disclosure or the scope of the claims, but rather as primarily describing features of particular embodiments of the particular disclosure. Certain features that are described in this application in the context of separate embodiments can also be implemented in combination in a single embodiment. On the other hand, the various features described in the individual embodiments may also be implemented separately in the various embodiments or in any suitable subcombination. Furthermore, although features may be acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.
Similarly, although operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In some cases, multitasking and parallel processing may be advantageous. Moreover, the separation of various system modules and components in the embodiments described should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.
Thus, particular embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. In some cases, the actions recited in the claims can be performed in a different order and still achieve desirable results. Furthermore, the processes depicted in the accompanying drawings are not necessarily required to be in the particular order shown, or sequential order, to achieve desirable results. In some implementations, multitasking and parallel processing may be advantageous.
The foregoing description of the preferred embodiment(s) of the application is not intended to limit the embodiment(s) of the application, but is to be accorded the widest scope consistent with the principles and spirit of the embodiment(s) of the application.