CN113961348A

CN113961348A - A task scheduling method, apparatus, device and storage medium

Info

Publication number: CN113961348A
Application number: CN202111255116.6A
Authority: CN
Inventors: 王贇; 赵鑫鹏
Original assignee: Alibaba China Co Ltd; Alibaba Cloud Computing Ltd
Current assignee: Alibaba China Co Ltd; Alibaba Cloud Computing Ltd
Priority date: 2021-10-27
Filing date: 2021-10-27
Publication date: 2022-01-21
Anticipated expiration: 2041-10-27
Also published as: CN113961348B

Abstract

The present application provides a task scheduling method, apparatus, device and storage medium. The method can be applied to the first CPU among the at least two logical processor CPUs obtained based on the hyperthreading technology; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists They are respectively used to store tasks of different priorities executed by the first CPU. The method may include: acquiring a priority of a task being executed by a second CPU of the at least two logical processor CPUs other than the first CPU. In response to the priority of the task being executed by the second CPU being the highest priority, the task scheduler obtains, through the task scheduler, a task that satisfies the scheduling condition from the first task list corresponding to the highest priority and executes it at Task scheduling is done when task eviction is required.

Description

Task scheduling method, device, equipment and storage medium

Technical Field

The present application relates to the field of computer vision technologies, and in particular, to a task scheduling method, apparatus, device, and storage medium.

Background

The hyper-threading technology is a technology for providing at least two logic threads in a Central Processing Unit (CPU) so as to simulate the CPU into at least two logic CPUs. Tasks may be performed in the at least two CPUs, respectively.

The hybrid deployment means that tasks with different priorities are deployed on the same physical resource to achieve the purpose of sharing the resource. The priority of the task can be set according to the service requirement. In a hybrid deployment, the resources required by tasks of the same priority are the same, and the resources required by tasks of different priorities are different. If the at least two CPUs simultaneously execute tasks of different priorities, a phenomenon of resource contention may occur.

In order to avoid this phenomenon, when one of the at least two CPUs is executing the task with the highest priority, task eviction needs to be performed on the task in the other CPU, that is, the task with the other priority is evicted, and it is ensured that the other CPU must also execute the task with the highest priority. Therefore, not only can the resource competition be avoided, but also the highest priority task can be ensured to be executed preferentially.

At present, when task eviction occurs, other priority tasks can be temporarily migrated from a ready queue through a task scheduler carried by a CPU, so that the task scheduler is kept to schedule the highest priority task from the ready queue only. After the task is evicted, the migrated tasks with other priorities can be migrated back to the ready queue, so that the task scheduler can normally schedule the tasks. In this way, in the case of task eviction, high overhead operation may be brought by the task coming in and going out of the ready queue, thereby reducing task scheduling efficiency, and causing task delay and jitter.

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) in at least two logic processor CPUs obtained based on a hyper-threading technology; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks of different priorities executed by the first CPU;

the method comprises the following steps:

acquiring the priority of a task which is executed by a second CPU except the first CPU in the at least two logic processor CPUs;

in response to the priority of the task being executed by the second CPU being the highest priority, acquiring, by the task scheduler, a task satisfying a scheduling condition from a first task list corresponding to the highest priority for execution to complete task scheduling in a situation requiring task eviction.

In some embodiments, the method further comprises:

in response to the priority of the task being executed by the second CPU not being the highest priority, obtaining, by the task scheduler, a task satisfying the scheduling condition from the at least two task lists for execution to complete task scheduling without task eviction.

In some embodiments, the task scheduler is a full fair scheduler CFS; the first CPU maintains the virtual time lengths corresponding to the tasks with different priorities respectively; the scheduling condition comprises a minimum virtual duration;

the obtaining, by the task scheduler, a task that satisfies a scheduling condition from the first task list corresponding to the highest priority includes:

acquiring a task corresponding to the minimum virtual time length from the first task list through the CFS;

the obtaining, by the task scheduler, the task satisfying the scheduling condition from the at least two task lists includes:

and acquiring the task 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 include 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 and black tree maintains corresponding first minimum virtual time length in each task in the first task list; the second red and black tree maintains second minimum virtual time length 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 time length and the second minimum virtual time length before performing an eviction task; a second variable indicating a cumulative gap between the first minimum virtual time length and the second minimum virtual time length due to task eviction in case of at least one task eviction;

the method further comprises the following steps:

under the condition that task eviction is needed, before task scheduling is carried out, in response to the fact that the scheduling is first eviction scheduling, the first variable is updated according to the current first minimum virtual time, the current second minimum virtual time 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, in response to the fact that the scheduling is first non-eviction scheduling after the task eviction is carried out, the second variable is updated according to the current first minimum virtual time, the current second minimum virtual time and the current first variable.

In some embodiments, the obtaining, by the CFS, the task corresponding to the minimum virtual duration 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;

in response to that the sum of the second minimum virtual time and the updated second variable is smaller than the first minimum virtual time, acquiring a task corresponding to the second minimum virtual time from the second red-black tree through the CFS;

and in response to the fact that the sum of the second minimum virtual time and the updated second variable is larger than or equal to the first minimum virtual time, acquiring a task corresponding to the first minimum virtual time from the first red-black tree through the CFS.

In some embodiments, the method further comprises:

acquiring the priority of a task to be processed; the task to be processed comprises a task needing 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 and black tree;

and correspondingly processing the task to be processed aiming at the second red and black tree under the condition that the priority of the task to be processed is other priorities.

In some embodiments, before migrating into the task to be processed or after migrating out of the task to be processed, the method further comprises:

and in response to at least one of the first red-black tree and the second red-black tree not including any task and the first CPU not executing the task with the priority corresponding to the at least one red-black tree, updating the first minimum virtual duration and the second minimum virtual duration to be the maximum value of the first minimum virtual duration and the second minimum virtual duration.

In some embodiments, after updating the first variable, further comprising:

and setting the first variable to be a preset value for increasing the second minimum virtual time length in response to the updated first variable being less than or equal to 0.

The application also provides a task scheduling device which is applied to a first CPU (central processing unit) of at least two logic processor CPUs obtained based on the hyper-threading technology; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks of different priorities executed by the first CPU;

the device comprises:

the acquisition module is used for acquiring the priority of the task which is 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 condition 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 of task eviction.

In some embodiments, the apparatus further comprises:

and the second scheduling module is used for responding to the condition that the priority of the task being executed by the second CPU is not the highest priority, and acquiring the task meeting the scheduling condition from the at least two task lists to execute through the task scheduler so as to complete task scheduling without task eviction.

the first scheduling module is specifically configured to:

the second scheduling module is specifically configured to:

the device further comprises:

and the first variable updating module responds to the scheduling for the first time before the task scheduling under the condition of needing task eviction, and updates the first variable according to the current first minimum virtual time, the current second minimum virtual time and the current second variable.

In some embodiments, the apparatus further comprises:

and the second variable updating module responds to the scheduling before task scheduling and updates the second variable according to the current first minimum virtual time, the current second minimum virtual time and the current first variable in response to the first non-eviction scheduling after the task eviction.

In some embodiments, the second scheduling module is specifically configured to:

In some embodiments, the apparatus further comprises:

the task maintenance module is used for acquiring the priority of the tasks to be processed; the task to be processed comprises a task needing to be migrated into or out of the first CPU;

In some embodiments, the apparatus further comprises:

and the synchronization module is used for updating the first minimum virtual time length and the second minimum virtual time length to the maximum value in response to that at least one of the first red-black tree and the second 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 as a preset value to increase the second minimum virtual time length in response to the updated first variable being less than or equal to 0.

The present application further proposes an electronic device, comprising:

a processor;

a memory for storing processor-executable instructions;

wherein the processor implements the task scheduling method as shown in any one of the foregoing embodiments by executing the executable instructions.

The present application also proposes a computer-readable storage medium, which stores a computer program for causing a processor to execute a task scheduling method as shown in any of the preceding embodiments.

In the technical solution disclosed in the foregoing embodiment, at least two task lists are maintained by the task scheduler corresponding to the first CPU; the at least two task lists are respectively used for storing tasks with different priorities executed by the first CPU, so that the task with the highest priority can be directly obtained from the first task list corresponding to the level with the highest priority for execution under the condition of an expulsion phenomenon, high-overhead operation caused by queue entry and exit of the task is avoided, task scheduling efficiency is improved, and task delay and jitter are possibly avoided.

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.

Drawings

In order to more clearly illustrate one or more embodiments of the present application or technical solutions in the related art, the drawings needed to be used in the description of the embodiments or the related art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments described in one or more embodiments of the present application, and other drawings can be obtained by those skilled in the art without inventive exercise.

FIG. 1 is a flowchart illustrating a method for task scheduling according to the present application;

FIG. 2 is a method flow diagram of an image processing method shown in the present application;

FIG. 3 is a flowchart illustrating a non-eviction scheduling method according to the present application;

FIG. 4 is a flowchart illustrating a method for maintaining tasks in a red and black tree according to the present disclosure;

fig. 5 is a schematic structural diagram of a task scheduling device shown in the present application;

fig. 6 is a hardware structure schematic of an electronic device shown in the present application.

Detailed Description

Reference will now be made in detail to the exemplary embodiments, examples of which are illustrated in the accompanying drawings. When the following description refers to the accompanying drawings, like numbers in different drawings represent the same or similar elements unless otherwise indicated. The embodiments described in the following exemplary embodiments do not represent all embodiments consistent with the present application. Rather, they are merely examples of apparatus and methods consistent with certain aspects of the present application, as detailed in the appended 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 application 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 and all possible combinations of one or more of the associated listed items. It should also be understood that the word "if" as used herein may be interpreted as "at … …" or "at … …" or "in response to a determination," depending on the context.

The application provides a task scheduling method. According to the method, at least two task lists respectively storing tasks of different levels are maintained, so that the task with the highest priority can be directly obtained from the first task list corresponding to the level with the highest priority to be executed under the condition of an expulsion phenomenon, high-overhead operation caused by the fact that the task comes in and goes out of a queue is avoided, task scheduling efficiency is improved, and task delay and jitter are possibly avoided.

Referring to fig. 1, fig. 1 is a flowchart illustrating a method for task scheduling 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 a hyper-threading technology; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks of different priorities executed by the first CPU.

The first CPU may be any of the at least two logical CPUs. The first CPU corresponds to a task scheduler.

The task scheduler may be configured to schedule a task 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 (complete Fair Scheduler).

The task list may be configured to store the task 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 scheduler. In some embodiments, the task list may store tasks in a data storage format such as a linked list, binary tree, red-black tree, etc.

The task may refer to a service executed by the CPU. The services may have different names at different stages. For example, in the ready queue phase, a transaction may be referred to as an entity. In the CPU execution phase, the transaction may be referred to as a process. This application refers to the services collectively as tasks.

The priority may indicate an order of execution of the tasks. When two CPUs under the same hyper-thread execute tasks with different priorities, the execution of the high-priority tasks needs to be preferentially ensured. In the application, the priority can be allocated to the task according to the service requirement. The task priority 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 executed in the second CPU. The second CPU may monitor the priority of the task executed by itself, and if it is found that the 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 is found that the tasks of other priorities are being executed, send an instruction to the first CPU to set the task identifier as a second identifier.

In step 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, in executing S102, the first CPU may generate a task priority fetch 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.

And S104, responding to the fact that the priority of the task being executed by the second CPU is the highest priority, acquiring the task meeting the scheduling condition from the first task list corresponding to the highest priority through the task scheduler, and executing the task so as to complete task scheduling under the condition of task eviction.

And if the priority of the task being executed by the second CPU is the highest priority, task eviction is required in the first CPU. Task eviction may include two scenarios.

Scene one: the first CPU does not execute the task at present, and needs to acquire the next task to execute, and at this time, the highest priority task meeting the scheduling condition may be directly acquired from the first task list.

In a second scenario, the first CPU is currently executing other priority tasks, and at this time, the execution of other priority tasks needs to be suspended, and the highest priority task meeting the scheduling condition is obtained from the first task list.

The task scheduler generally has a task scheduling principle, and when the task is scheduled, the task meeting the scheduling condition is acquired based on a preset scheduling principle. The scheduling conditions shown in the present application are the scheduling conditions corresponding to the task scheduler.

In the foregoing solution, since the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks with different priorities executed by the first CPU, so that the task with the highest priority can be directly obtained from the first task list corresponding to the level with the highest priority for execution under the condition of an expulsion phenomenon, high-overhead operation caused by queue entry and exit of the task is avoided, task scheduling efficiency is improved, and task delay and jitter are possibly avoided.

In some embodiments, the task scheduler is a CFS. And the first CPU maintains the virtual time lengths corresponding to the tasks with different priorities. The scheduling condition includes a minimum virtual duration.

The CFS assigns a virtual duration to each task in the task list. If one task is scheduled to be executed, the corresponding virtual time length of the task is continuously increased, and the virtual time length of the task which is not executed is not changed. The higher the priority of the task, the smaller the initial virtual time length, and the slower the virtual time length increases when executing one task.

The scheduling condition corresponding to the CFS is a minimum virtual duration. That is, the CFS may select the task corresponding to the lowest virtual duration to execute.

In the step of 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 retrieve the task satisfying the scheduling condition from the at least two task lists to normally retrieve the task for execution.

Referring to fig. 2, fig. 2 is a flowchart illustrating a method of image processing 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, responding to the fact that the priority of the task being executed by the second CPU is not the highest priority, acquiring the task meeting the scheduling condition from the at least two task lists through the task scheduler to execute so as to complete task scheduling under the condition that task eviction is not needed.

If the priority of the task being executed by the second CPU is not the highest priority, no task eviction is required in the first CPU. Therefore, when task eviction is not needed, the first CPU can acquire the tasks meeting the scheduling conditions from the at least two task lists for execution so as to normally acquire the tasks meeting the scheduling conditions for execution.

In the step of S106, S1061 may be performed, and a task corresponding to the minimum virtual duration is obtained from the at least two task lists through the CFS. Therefore, the first CPU can acquire the tasks corresponding to the minimum virtual time length from the tasks of all the priorities to execute.

In some embodiments, the at least two task lists that may correspond with a task scheduler (CFS) may include red and black trees. The red-black tree is a self-balancing binary search tree. The red and 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 placed at a preset position, so that query is facilitated.

In the application, the key values of the nodes included in the red and black trees can be determined based on the virtual duration of the task. The information stored by the node may be determined based on the task information. The red and black trees can maintain the current minimum virtual time length when tasks are migrated in and out and when the CPU finishes the executed tasks, so that the task corresponding to the minimum virtual time length is conveniently obtained.

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 maintained by the red-black tree 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 trees corresponding to the tasks with other priorities is also kept unchanged. In doing so, it is possible to increase the priority of other priority tasks by evicting. This is not allowed.

For example, assume that the first CPU needs to execute the high priority task A, B and the low priority tasks 1, 2. Due to the eviction in the first CPU, the high priority task AB is continuously executed, which results in the virtual duration for the low priority tasks 1 and 2 possibly being much smaller than for the task AB. When eviction disappears, it is likely that low priority tasks 1 and 2 will be executed for a long period of time. This is equivalent to increasing the priority of the low priority task through eviction. This situation is not allowed.

In order to solve the foregoing problem, a first variable and a second variable are added in the present application for recording a difference between minimum virtual durations maintained by a red-black tree corresponding to a highest priority and red-black trees corresponding to other priorities due to the occurrence of eviction, so as to compensate virtual durations of other priority tasks to offset the difference caused by the eviction. In some embodiments, the compensated real virtual duration may be obtained by adding the difference to the virtual durations of other priority tasks.

The following describes a method for updating the first variable and the second variable with reference to an embodiment.

In some embodiments, the at least two task lists further include 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 and black tree maintains corresponding first minimum virtual time length in each task in the first task list; and the second red and black tree maintains second minimum virtual time length 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 time length and the second minimum virtual time length before performing an eviction task; a second variable indicates a cumulative gap between the first minimum virtual time length and the second minimum virtual time length due to task eviction in a case where at least one task eviction is performed. In the present application, the first variable may be denoted as start, and the second variable may be denoted as spread.

The first variable may be updated in the present application through step S21.

S21, under the condition of needing task eviction, before the task scheduling, in response to the scheduling being the first eviction scheduling, updating the first variable according to the current first minimum virtual time, the current second minimum virtual time and the current second variable.

First eviction scheduling refers to the first scheduling by the CFS in situations where task eviction is required.

Thereby, the difference between the first minimum virtual time length and the second minimum virtual time length before the eviction occurs can be accurately recorded, so that after the eviction is completed, the accumulated difference (i.e., the second variable) between the first minimum virtual time length and the second minimum virtual time length caused by the eviction of the task is determined, and the virtual time length difference caused by the eviction is compensated for.

In some embodiments, when performing S21, S211-S212 may be performed.

S211, in case that it is determined that the task eviction is required, determining whether the present schedule is a first eviction schedule by determining whether the first variable is an initial value (which may be 0, for example).

In one aspect, the first variable is set to the initial value in the following two cases.

First, in response to at least one of the first red-black tree and the second red-black tree not including any task and the first CPU not executing a task of a priority corresponding to the at least one red-black tree, a first variable is set to an initial value. This may be understood as an initialization of the first variable.

Second, upon completion of the eviction into a non-eviction condition, the first variable may be set to the initial value after the second variable is updated (the method of updating the second variable is described later).

On the other hand, the present application updates the first variable to another value (possibly a non-initial value) prior to the first eviction of the schedule.

Due to the foregoing two aspects, if the first variable is an initial value in a situation where it is determined that task eviction is required, the present schedule is interpreted as a first eviction schedule. If the first variable is not the initial value, then the current schedule is not a first eviction schedule.

S212, responding to the first-time eviction scheduling of the current scheduling, and updating the first variable according to the current first minimum virtual time, the current second minimum virtual time 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 S212 is executed, a real second minimum virtual time length compensated for the previous eviction may be obtained by a sum of the current second minimum virtual time length and the current second variable; updating to the first variable by determining a difference between a real second minimum virtual time duration and a current first virtual time duration.

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, it can be stated that this task eviction is the first task eviction, and then the update of the start variable can be performed according to the following formula (1).

start＝min_vrt_under-min_vrt_high+spread................1；

Where start represents the first variable, spread represents the second variable, min _ vrt_underRepresents the second minimum virtual duration, min _ vrt_highRepresenting a first minimum virtual time duration. Wherein, min _ vrt_under+ spread may get the true second minimum virtual duration compensated for the previous eviction, and then reconcile min _ vrt with min _ vrt_highSubtracting, a real difference between the first minimum virtual time length and the second minimum virtual time length before the first eviction scheduling, that is, a start at this moment, may be obtained.

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, in response to the scheduling being the first non-eviction scheduling after task eviction, updating the second variable according to the current first minimum virtual time, the current second minimum virtual time and the current first variable.

The first non-eviction schedule refers to a first schedule performed by the CFS in a case where no task eviction is required after eviction.

Therefore, after the eviction is completed, the accumulated difference (namely, the second variable) between the first minimum virtual time length and the second minimum virtual time length caused by the task eviction can be accurately recorded, and the virtual time length difference caused by the eviction can be conveniently compensated.

In some embodiments, when performing S22, S221-S222 may be performed.

S221, in case that it is determined that task eviction is not required, it is determined whether the present schedule is a first non-eviction schedule by determining whether the first variable is an initial value (which may be 0, for example).

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, the present schedule is indicated as the first non-eviction schedule after eviction occurs. And if the first variable is an initial value, the scheduling is not the first non-eviction scheduling.

S222, responding to the first non-eviction scheduling after the current scheduling is performed, and updating the second variable according to the current first minimum virtual time, the current second minimum virtual time and the current first variable.

The second variable may be understood as a cumulative gap between the first minimum virtual time length and the second minimum virtual time length after eviction.

The first variable may be understood as the difference existing between the first minimum virtual time length and the second minimum virtual time length before the last eviction occurs.

In S222, a difference between the second minimum virtual time length and the first minimum virtual time length after the last eviction is determined according to a difference between the second minimum virtual time length and the first minimum virtual time length. The newly added gap is added to the gap (i.e., the first variable) that existed before the last eviction, and 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, the task eviction can be stated as a first non-task eviction, and then the update of the spread variable can be performed according to the following equation (2).

spread＝min-vrt_high-min-vrt_under+start................2；

Where start represents the first variable, spread represents the second variable, min-vrt_underRepresents the second minimum virtual duration, min _ vrt_highRepresenting a first minimum virtual time duration. Wherein, min _ vrt_high-min_vrt_underThe second minimal virtual may be obtained after the last evictionThe difference between the planned time length and the newly increased first minimum virtual time length is added with the start, namely the difference existing before the last eviction is carried out, and the accumulated difference brought by the task eviction, namely the spread, is obtained. The start may also be set to 0 after that, so that the read may not be updated in the next non-eviction task.

After updating the second variable, a cumulative gap between the first minimum virtual time length and the second minimum virtual time length due to eviction may be recorded, and thus the second minimum virtual time length may be compensated based on the cumulative gap to offset a virtual time length gap caused by eviction.

In some embodiments, the first variable obtained by performing S21 may be less than or equal to 0, in which case, the second variable updated by performing S22 may also 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 decreased instead, and the priority of other priority tasks is raised, which is not allowed.

In this 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 time length. In this application, it may be said that said preset value is marked as e.

The preset value epsilon is a preset positive number. Setting the first variable to a preset value can ensure that the updated second variable of S22 is a certain 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 raising the priority of other priority tasks.

In some embodiments, in performing S1061, the CFS may perform a non-eviction schedule based on the compensated real second virtual duration. Non-eviction scheduling refers to scheduling of tasks by the CFS without requiring task eviction.

Referring to fig. 3, fig. 3 is a flowchart illustrating a non-eviction scheduling method according to the present application. The step shown in fig. 3 is a detailed description of S1061. As shown in fig. 3, in performing S1061, the method may include S301-S303.

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 gap caused by the eviction.

S302, in response to that the sum of the second minimum virtual time and the updated second variable is smaller than the first minimum virtual time, acquiring a task corresponding to the second minimum virtual time from the second red-black tree through the CFS.

S303, in response to the fact that the sum of the second minimum virtual time and the updated second variable is larger than or equal to the first minimum virtual time, obtaining a task corresponding to the first minimum virtual time from the first red and black tree through the CFS.

According to a 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, it indicates that the task in the second red-black tree should be executed currently, so that tasks of other priorities corresponding to the second minimum virtual time length can be obtained from the second red-black tree. 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, it indicates that the task in the first red-black tree should be executed currently, so that the highest priority task corresponding to the second minimum virtual time length can be obtained from the second red-black tree.

For example, when selecting the non-eviction task, the sum of the second minimum virtual duration and the updated second variable may be compared with the size of the first minimum virtual duration.

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 a task from the second red-black tree according to a CFS (computational fluid dynamics) 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 a task from the first red-black tree.

min_vrt_under+spread＜min_vrt_high................3；

Wherein, min-vrt_underRepresents the second minimum virtual duration, min _ vrt_highA first minimum virtual duration is represented and spread represents a second variable, i.e., the cumulative gap between the first minimum virtual duration and the second minimum virtual duration due to task eviction. By min _ vrt_under+ spread may get the true min _ vrt compensated for the gap caused by eviction_underIf min _ vrt_under+spread＜min_vrt_highIt can be stated that the minimum virtual duration of the first red-black tree is greater than the real minimum virtual duration of the second red-black tree, and according to the CFS scheduling rule, a task needs to be selected from the second red-black tree.

In some embodiments, a method of maintaining tasks in a red and black tree is also included.

Referring to fig. 4, fig. 4 is a flowchart illustrating 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; the tasks to be processed comprise tasks which need to be migrated into or out of the first CPU.

In this application, a task is assigned a priority identification. 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, the task to be processed is correspondingly processed aiming at the first red and black tree.

In some embodiments, the virtual durations of the tasks maintained in the red and black trees have a translation relationship with the virtual durations of the tasks maintained by the CFS, such a translation relationship requiring a minimum virtual duration maintained by the red and black trees. That is, when the task is migrated in and out, the virtual time length conversion is required according to the current minimum virtual time length of the red and black trees.

If the task is a task to be migrated, the first minimum virtual time length maintained by the first red-black tree can be updated according to the virtual time length of the task currently being scheduled, then the virtual time length of the task to be processed maintained by the red-black tree is determined based on the first minimum virtual time length, the task to be processed is added to the first red-black tree as a node based on the virtual time length, and the task migration is completed. If the task is a task to be migrated, the first minimum virtual time maintained by the first red-black tree may be updated according to the virtual time of the task currently being scheduled, then the virtual time of the task to be processed maintained by the CFS is determined based on the first minimum virtual time, and the node corresponding to the task to be processed is deleted in the first red-black tree, so that the task migration is completed.

In the present application, a task being scheduled is recorded as curr, and a virtual duration of the task is recorded as vruntime_curr. Whether the task is an immigration task or an immigration task, the vruntime of curr can be updated according to the CFS rule_currAnd the minimum virtual duration of the red-black tree corresponding to curr is updated. If curr is a task in the first red-black tree, then the first minimum virtual duration min _ vrt of the first red-black tree is updated_highIf curr is a task in the second red-black tree, then update the second minimum virtual duration min _ vrt of the second red-black tree_under。

If the task to be processed with high priority is migrated, the task to be processed can be based on min _ vrt_highObtaining the virtual time length of the task to be processed, and inserting the virtual time length as a node into a first red-black tree_highIn (1).

If the task to be processed with high priority is migrated, the task to be processed can be based on min _ vrt_underObtaining the virtual time length of the task to be processed, and deleting the second red-black tree_underTo the corresponding node in (1).

And S403, performing corresponding processing on the task to be processed aiming at the second red and black tree under the condition that the priority of the task to be processed is other priorities.

The corresponding processing of the pending task of other priority can refer to S402, which is not described in detail herein.

Through S401-S403, tasks can be accurately maintained in the first red-black tree and the second red-black tree, and subsequent accurate task scheduling is facilitated.

In some embodiments, in the process of maintaining the task, in response to at least one of the first red-black tree and the second red-black tree not including any task and the first CPU not executing the task of the priority corresponding to the at least one red-black tree, the first minimum virtual duration and the second minimum virtual duration are updated to be the maximum of the two.

Therefore, after the task of any priority is executed, the minimum virtual time length maintained by the two red and black trees is synchronized, so that the virtual time lengths corresponding to the tasks maintained after the two red and black trees are synchronized. In some embodiments, after the synchronization of the two red and black tree virtual time lengths is completed, a first variable indicating a difference between the two red and black tree virtual time lengths maintained by the first CPU and a second variable indicating an accumulated difference between the two red and black tree virtual time lengths due to the eviction are set to initial values (e.g., 0).

The following description is made by taking a scenario in which an online task and an offline task are deployed in a mixed manner as an example.

The CPU executing the task can simulate the first CPU and the second CPU through the hyper-thread. The first CPU is used as an execution subject in the following.

The first CPU may perform task scheduling in a CFS manner. The CFS may maintain a first red-black tree that stores online tasks and a second red-black tree that stores offline tasks. The online task is a high-priority task, and the offline task is a low-priority task.

The first CPU may maintain the first variable start and the second variable spread, and the maintaining method may be referred to as S21 and S22, respectively. By adding the first variable start and the second variable spread, the difference between the minimum virtual time lengths maintained by the red-black tree corresponding to the online task and the red-black tree corresponding to the offline task due to the eviction can be recorded, so that the virtual time length of the evicted offline task can be compensated to offset the difference caused by the eviction.

The second CPU may send an instruction to the first CPU under a condition that the second CPU executes the online task, so that the indication task identifier maintained in the first CPU is set as the first identifier, and indicates that the second CPU is currently executing the online task.

The second CPU may send an instruction to the first CPU under a condition that the second CPU executes the offline task, so that the indication task identifier maintained in the first CPU is set as the second identifier, and indicates that the second CPU is currently executing the offline task.

The first CPU can determine the task priority of the second CPU through the task identification.

And if the task identifier is the first identifier, task eviction needs to occur, and the first CPU can acquire the online task corresponding to the minimum virtual time length from the first red-black tree through the CFS.

If the task identifier is the second identifier, the task eviction is not required, and the second CPU may add a second minimum virtual duration maintained in the second red-black tree to the second variable to obtain a real second minimum virtual duration compensated for eviction, 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. And if the real second minimum virtual time length and the real first minimum virtual time length do not satisfy the formula 3, acquiring the online task from the first red-black tree.

In this example, the CFS corresponding to the first CPU maintains two red and black trees that store the online task and the offline task, respectively; therefore, under the condition that the eviction phenomenon occurs, the online task can be directly obtained from the first red-black tree, high-overhead operation caused by the fact that the task comes in and goes out of the queue in the prior art is avoided, task scheduling efficiency is improved, and task delay and jitter are possibly avoided.

In addition, in this example, the virtual time length corresponding to the evicted offline task may be compensated through the first variable and the second variable, so that it is ensured that the task may be normally obtained in the non-eviction scheduling.

In accordance with the foregoing embodiments, the present application provides 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; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks of different priorities executed by the first CPU.

Referring to fig. 5, fig. 5 is a schematic structural diagram of a task scheduling device shown in the present application.

As shown in fig. 5, the apparatus 50 may include:

an obtaining module 51, configured to obtain a priority of a task being executed by a second CPU, except the first CPU, of the at least two logical processor CPUs;

and the first scheduling module 51, in response to that the priority of the task being executed by the second CPU is the highest priority, acquiring, by the task scheduler, a task meeting a scheduling condition from the first task list corresponding to the highest priority to execute so as to complete task scheduling in a situation that task eviction is required.

In some embodiments, the apparatus 50 further comprises:

the first scheduling module 51 is specifically configured to:

the second scheduling module is specifically configured to:

the apparatus 50 further comprises:

In some embodiments, the apparatus 50 further comprises:

The embodiment of the task scheduling device shown in the application can be applied to electronic equipment. Accordingly, the present application discloses an electronic device, which may comprise: a processor.

A memory for storing processor-executable instructions.

Wherein 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 shown in the present application.

As shown in fig. 6, the electronic device may include a processor for executing instructions, a network interface for making network connections, a memory for storing operation data for the processor, and a non-volatile memory for storing instructions corresponding to the task scheduling device.

The embodiments of the apparatus may be implemented by software, or by hardware, or by a combination of hardware and software. Taking a software implementation as an example, as a logical device, the device is formed by reading, by a processor of the electronic device where the device is located, a corresponding computer program instruction in the nonvolatile memory into the memory 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 may also include other hardware according to an actual function of the electronic device, which is not described again.

It is to be understood that, in order to increase the processing speed, the device-corresponding instruction may also be directly stored in the memory, which is not limited herein.

The present application proposes a computer-readable storage medium, which stores a computer program, which can be used to cause a processor to execute the task scheduling method shown in any of the foregoing embodiments.

One skilled in the art will recognize that one or more embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, one or more embodiments of the present 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 present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, optical storage, and the like) having computer-usable program code embodied therein.

"and/or" as recited herein means having at least one of two, for example, "a and/or B" includes three scenarios: A. b, and "A and B".

The embodiments in the present application are described in a progressive manner, and the same and similar parts among the embodiments can be referred to each other, and each embodiment focuses on the differences from the other embodiments. In particular, for the data processing apparatus embodiment, since it is substantially similar to the method embodiment, the description is relatively simple, and for the relevant points, reference may be made to part of the description of the method embodiment.

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 may also be possible or may be advantageous.

Embodiments of the subject matter and functional operations described in this application may be implemented in the following: digital electronic circuitry, tangibly embodied computer software or firmware, computer hardware including the structures disclosed in this application and their structural equivalents, or a combination of one or more of them. Embodiments of the subject matter described in this application 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 an artificially 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 the 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 and/or special purpose microprocessors, or any other type of central processing system. Generally, a central processing system will receive instructions and data from a read-only memory and/or a random access memory. The essential components of a computer include a central processing system for implementing or executing instructions and one or more memory devices for storing instructions and data. Generally, 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. However, a computer does not necessarily have such a device. Moreover, a computer may be embedded in another device, e.g., a mobile telephone, 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 by way of example semiconductor memory devices (e.g., EPROM, EEPROM, and flash memory devices), magnetic disks (e.g., an internal hard disk or a removable disk), 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.

Although this application contains many specific implementation details, these should not be construed as limiting the scope of any disclosure or of what may be claimed, but rather as merely describing features of particular disclosed embodiments. Certain features that are described in this application in the context of separate embodiments can also be implemented in combination in a single embodiment. In other instances, features described in connection with one embodiment may be implemented as discrete components or in any suitable subcombination. Moreover, although features may be described above as 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, while 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 described embodiments is not to be understood as requiring such separation in all embodiments, and it is to 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. Further, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some implementations, multitasking and parallel processing may be advantageous.

The above description is only for the purpose of illustrating the preferred embodiments of the present application and is not intended to limit the present application to the particular embodiments of the present application, and any modifications, equivalents, improvements and the like that are within the spirit and principle of the present application and are intended to be included within the scope of the present application.

Claims

1. A task scheduling method is applied to a first CPU (central processing unit) of at least two logic processor CPUs obtained based on a hyper-threading technology; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks of different priorities executed by the first CPU;

the method comprises the following steps:

2. The method of claim 1, further comprising:

3. The method of claim 2, the task scheduler being a full fair scheduler, CFS; the first CPU maintains the virtual time lengths corresponding to the tasks with different priorities respectively; the scheduling condition comprises a minimum virtual duration;

4. The method of claim 3, the at least two task lists further comprising 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 and black tree maintains corresponding first minimum virtual time length in each task in the first task list; the second red and black tree maintains second minimum virtual time length corresponding to each task in the second task list;

the method further comprises the following steps:

5. The method of claim 4, further comprising:

6. The method according to claim 5, wherein the obtaining, through the CFS, the task corresponding to the minimum virtual duration from the at least two task lists comprises:

7. The method of claim 4, further comprising:

8. The method of claim 7, further comprising, prior to migrating the pending task or after migrating the pending task, either:

9. The method of claim 4, after updating the first variable, further comprising:

10. A task scheduling device is applied to a first CPU (central processing unit) of at least two logic processor CPUs obtained based on a hyper-threading technology; the task scheduler corresponding to the first CPU maintains at least two task lists; the at least two task lists are respectively used for storing tasks of different priorities executed by the first CPU;

the device comprises:

11. An electronic device, comprising:

a processor;

a memory for storing processor-executable instructions;

wherein the processor implements the task scheduling method according to any one of claims 1 to 9 by executing the executable instructions.

12. A computer-readable storage medium, which stores a computer program for causing a processor to execute the task scheduling method according to any one of claims 1 to 9.