Task scheduling method for dispatching tasks based on computing power of different processor cores in heterogeneous multi-core processor system and related non-transitory computer readable medium

A task scheduling method is applied to a heterogeneous multi-core processor system. The heterogeneous multi-core processor system has at least one first processor core and at least one second processor core. The task scheduling method includes: referring to task priorities of tasks of the heterogeneous processor cores to identify at least one first task of the tasks that belongs to a first priority task group, wherein each first task belonging to the first priority task group has a task priority not lower than task priorities of other tasks not belonging to the first priority task group; and dispatching at least one of the at least one first task to at least one run queue of at least one of the at least one first processor core.

BACKGROUND

The disclosed embodiments of the present invention relate to a task scheduling scheme, and more particularly, to a task scheduling method for dispatching tasks (e.g., real-time tasks) based on computing power of different processor cores in a heterogeneous multi-core processor system and a related non-transitory computer readable medium.

A multi-core system becomes popular nowadays due to increasing need of computing power. Hence, an operating system (OS) of the multi-core system may need to decide task scheduling for different processor cores to maintain good load balance and/or high system resource utilization. Regarding a heterogeneous multi-core system, it may have processor cores that are not identical to each other. For example, the heterogeneous multi-core system may include a first processor core and a second processor core, where the first processor core may have first processor architecture, and the second processor core may have second processor architecture that is different from the first processor architecture. Hence, if the same task is running on the first processor core and the second processor core, the processing time needed by the first processor core to finish execution of instructions of the task may be different from the processing time needed by the second processor core to finish execution of the same instructions of the task.

In general, the first processor core and the second processor core implemented in the heterogeneous multi-core system may have different computing power due to different processor architecture. For example, the first processor core may be a performance oriented processor core, while the second processor core may be a power-saving oriented processor core. Hence, the computing power/capability of the first processor core may be greater than that of the second processor core. However, a conventional task scheduling scheme is not aware of the different computing power of processor cores in the heterogeneous multi-core system. As a result, a task with the higher task priority may be dispatched to the second processor core with lower computing power for execution, and another task with the lower task priority may be dispatched to the first processor core with higher computing power for execution. This would lead to priority inversion. That is, the task with higher task priority may have longer latency and response time due to that execution of the task with lower task priority is accomplished/terminated before the execution of the task with higher task priority.

Thus, there is a need for an innovative task scheduling design which is capable of properly dispatching tasks to different processor cores of a heterogeneous multi-core system based on different computing power possessed by the processor cores.

SUMMARY

In accordance with exemplary embodiments of the present invention, a task scheduling method for dispatching tasks (e.g., real-time tasks) based on computing power of different processor cores in a heterogeneous multi-core processor system and a related computer readable medium are proposed to solve the above-mentioned problem.

According to a first aspect of the present invention, an exemplary task scheduling method for a heterogeneous multi-core processor system is disclosed. The heterogeneous multi-core processor system includes at least one first processor core each having first computing power and at least one second processor core each having second computing power lower than the first computing power. The exemplary task scheduling method includes: referring to task priorities of tasks of the heterogeneous processor cores to identify at least one first task of the tasks that belongs to a first priority task group, wherein each first task belonging to the first priority task group has a task priority not lower than task priorities of other tasks not belonging to the first priority task group; and dispatching at least one of the at least one first task to at least one run queue of at least one of the at least one first processor core.

According to a second aspect of the present invention, another exemplary task scheduling method for a heterogeneous multi-core processor system is disclosed. The heterogeneous multi-core processor system includes at least one first processor core each having first computing power and at least one second processor core each having second computing power lower than the first computing power. The exemplary task scheduling method includes: referring to task priorities of tasks of the heterogeneous processor cores to identify at least one first task of the tasks that belongs to a first priority task group and identify at least one second task of the tasks that belongs to a second priority task group, wherein each first task belonging to the first priority task group has a task priority not lower than task priorities of other tasks not belonging to the first priority task group, each second task belonging to the second priority task group has a task priority not lower than task priorities of other tasks not belonging to the first priority task group and the second priority task group; and dispatching at least one of the at least one second task to at least one run queue of at least one of the at least one second processor core.

In addition, a non-transitory computer readable medium storing a task scheduling program code is also provided, wherein when executed by the heterogeneous multi-core processor system, the task scheduling program code causes the heterogeneous multi-core processor system to perform any of the aforementioned task scheduling methods.

DETAILED DESCRIPTION

FIG. 1is a diagram illustrating a heterogeneous multi-core processor system according to an embodiment of the present invention. The heterogeneous multi-core processor system10may be implemented in a portable device, such as a mobile phone, a tablet, a wearable device, etc. However, this is not meant to be a limitation of the present invention. That is, any electronic device using the proposed task scheduling method falls within the scope of the present invention. In this embodiment, the heterogeneous multi-core processor system10may have a task scheduler100and a plurality of clusters including a first cluster112and a second cluster114. The task scheduler100may be coupled to the first cluster112and the second cluster114, and arranged to perform the proposed task scheduling method which is used to dispatch tasks to different processor cores based on computing power of the processor cores. In this embodiment, the task scheduler100may be part of an operating system (OS) such as a Linux-based OS or other OS kernel supporting multiprocessor task scheduling. Hence, the task scheduler100may be a software module running on the heterogeneous multi-core processor system10. As shown inFIG. 1, the heterogeneous multi-core processor system10may have a non-transitory computer readable medium12such as a memory device. The non-transitory computer readable medium12may store a program code (PROG)14. When the program code14is loaded and executed by the heterogeneous multi-core processor system10, the task scheduler100may perform the proposed task scheduling method which will be detailed later.

Regarding the first cluster112and the second cluster114, each cluster may be a group of processor cores. That is, the first cluster112may include one or more first processor cores113, each having the same first processor architecture with the same first computing power; and the second cluster114may include one or more second processor cores115, each having the same second processor architecture with the same second computing power. The second processor architecture may be different from the first processor architecture, and the second computing power may be lower than the first computing power. In one embodiment, each first processor core113may be regarded as a performance oriented processor core, and each second processor core115may be regarded as a power-saving oriented processor core. It should be noted that, based on the actual design consideration, the number of first processor cores113included in the first cluster112may be identical to or different from the number of second processor cores115included in the second cluster114. Therefore, the proposed task scheduling method may be applied to the heterogeneous multi-core processor system10with any combination of different processor cores.

It should be noted that the term “multi-core processor system” may mean a multi-core system or a multi-processor system, depending upon the actual design. In other words, the proposed task scheduling method may be employed by any of the multi-core system and the multi-processor system. For example, concerning the multi-core system, all of the processor cores113may be disposed in one processor. For another example, concerning the multi-processor system, each of the processor cores113may be disposed in one processor. Hence, each of the clusters and114may be a group of processors.

The task scheduler100may include an identifying unit102and a scheduling unit104. The identifying unit102may be configured to refer to task priorities of tasks of the heterogeneous multi-core processor system10to identify at least one first task of the tasks that belongs to a first priority task group and identify at least one second task of the tasks that belongs to a second priority task group. For example, the identifying unit102may be configured to compare task priorities of a plurality of tasks of the heterogeneous multi-core processor system10, including task(s) currently running, task(s) waiting to run, etc., to determine which task(s) belong to the first priority task group (e.g., which task(s) should run on the first processor core(s)113) and further determine which task(s) belong to the second priority task group (e.g., which task(s) should run on the second processor core(s)115). The size of the first priority task group may depend on the number of first processor cores113, and the size of the second priority task group may depend on the number of second processor cores115. For example, the size of the first priority task group may be equal to the number of first processor cores113, and the size of the second priority task group may be equal to the number of second processor cores115.

The first priority task group may be treated as a highest priority task group, and the second priority task group may be treated as a next highest priority task group. Hence, each first task belonging to the first priority task group may have a task priority not lower than task priorities of other tasks not belonging to the first priority task group, and each second task belonging to the second priority task group may have a task priority not lower than task priorities of other tasks not belonging to the first priority task group and the second priority task group. In other words, any second task belonging to the second priority task group does not have a task priority higher than a task priority of any first task belonging to the first priority task group.

Based on the task identification result informed by the identifying unit102, the scheduling unit104may set or adjust run queues of processor cores included in the heterogeneous multi-core processor system10. Each processor core of the heterogeneous multi-core processor system10may be given a run queue managed by the scheduling unit104. In this embodiment, one first processor core113in the first cluster112may be given a run queue105, and one second processor core115in the second cluster114may be given a run queue106. Hence, when there are multiple first processor cores113, the scheduling unit104can manage multiple run queues105created for the first processor cores113, respectively; and when there are multiple second processor cores115, the scheduling unit104can manage multiple run queues106created for the second processor cores115, respectively. The run queue may be a data structure which records a list of tasks, where the tasks may include a task that is currently running and other task(s) waiting to run. In some embodiments, a processor core may sequentially execute tasks included in a corresponding run queue according to task priorities of the tasks. In other words, the processor core may execute a task with higher task priority prior to executing a task with lower task priority. By way of example, but not limitation, the tasks may include programs, application program sub-components, or a combination thereof.

To reduce or avoid undesired priority inversion, the scheduling unit104may dispatch at least one of first task(s) belonging to the first priority task group (e.g., a highest priority task group) to at least one run queue of at least one of first processor core(s)113included in the first cluster112of the heterogeneous multi-core processor system10, and/or dispatch at least one of second task(s) belonging to the second priority task group (e.g., a next highest priority task group) to at least one run queue of at least one of second processor core(s)115included in the second cluster114of the heterogeneous multi-core processor system10. For better understanding of technical features of the present invention, several task scheduling operations performed by the scheduling unit104based the proposed task scheduling method are discussed as below.

For clarity and simplicity, the following assumes that the first cluster112includes two first processor cores113denoted by Core_11 and Core_12, and the second cluster114includes two second processor cores115denoted by Core_21 and Core_22. Hence, the scheduling unit104may assign two run queues105denoted by RQ11and RQ12to the first processor cores Core_11 and Core_12, respectively; and may assign two run queues106denoted by RQ21and RQ22for the second processor cores Core_21 and Core_22, respectively. The task priorities in a descending order is 0→1→2→3→4. Thus, a task with the task priority “0” is given the highest priority level among tasks executed by the heterogeneous multi-core processor system10.

FIG. 2is a diagram illustrating a first task scheduling operation which dispatches one first task belonging to the first priority task group to a run queue of one first processor core with higher computing power. In this example, before a task T0with the task priority “0” is required to be added to one of the run queues RQ11, RQ12, RQ21, RQ22for execution, the run queue RQ11may include a task T2with the task priority “2” and may further include other tasks with lower task priorities (not shown inFIG. 2); the run queue RQ12may include a task T1with the task priority “1” and may further include other tasks with lower task priorities (not shown inFIG. 2); the run queue RQ21may include a task T3with the task priority “3” and may further include other tasks with lower task priorities (not shown inFIG. 2); and the run queue RQ22may include a task T4with the task priority “4” and may further include other tasks with lower task priorities (not shown inFIG. 2). Before the task T0is added to one of the run queues RQ11, RQ12, RQ21, and RQ22, a task with the highest task priority in the run queue RQ11may be the task T2, a task with the highest task priority in the run queue RQ12may be the task T1, a task with the highest task priority in the run queue RQ21may be the task T3, and a task with the highest task priority in the run queue RQ22may be the task T4. Hence, the tasks T1, T2, T3, and T4may be currently running on the first processor core Core_12, the first processor core Core_11, the second processor core Core_21, and the second processor core Core_22, respectively.

It is possible that the system may create a new task, or a task may be added to a wait queue to wait for requested system resource(s) and then resumed when the requested system resource(s) is available. In this example, the task T0may be a new task or a resumed task (e.g., a waking task currently being woken up) that is not included in run queues RQ11, RQ12, RQ21, RQ22of the heterogeneous multi-core processor system10, and the scheduling unit104needs to select one of the run queues RQ11, RQ12, RQ21, RQ22and then dispatch the task T0to the selected run queue to thereby add the task T0to one of the run queues RQ11, RQ12, RQ21, RQ22for execution.

As mentioned above, the identifying unit102may be configured to perform task identification to determine the first priority task group (e.g., a highest priority task group) and the second priority task group (e.g., a next highest priority task group), where the size of the first priority task group may depend on the number of first processor cores with the first computing power, and the size of the second priority task group may depend on the number of second processor cores with the second computing power lower than the first computing power. In this example, there are two first processor cores Core_11 and Core_12 and two second processor cores Core_21 and Core_22. Consider a case where the size of the first priority task group is set to be equal to the number of first processor cores, and the size of the second priority task group is set to be equal to the number of second processor cores. Hence, because task priorities of two tasks T0and T1are not lower than task priorities of other tasks T2, T3and T4, and task priorities of two tasks T2and T3are not higher than task priorities of tasks T0and T1and not lower than task priorities of other tasks (e.g., T4), the identifying unit102may identify tasks T0and T1as tasks belonging to the first priority task group, and may identify tasks T2and T3as tasks belonging to the second priority task group. The task T0to be scheduled has the task priority “0” higher than task priorities “1” and “2” of tasks T1and T2currently running on the first processor cores Core_12 and Core_11 with higher computing power. Hence, the scheduling unit104may push the task T0(which is identified as a task belonging to the first priority task group) into one of the run queues RQ11and RQ12to reduce or avoid undesired priority inversion.

The scheduling unit104may select a specific run queue from run queues RQ11and RQ12of the first processor cores Core_11 and Core_12, and then add the task T0to the specific run queue. In one exemplary design, the highest task priority possessed by one task in the specific run queue is a lowest one of the highest task priorities possessed by tasks in the run queues RQ11and RQ12. In this example, since the highest task priority “2” possessed by the task T2in the run queue RQ11is lower than the highest task priority “1” possessed by the task T1in the run queue RQ12, the scheduling unit104may select the run queue RQ11as the specific run queue to which the task T0will be added.

After the task scheduling of the task T0is accomplished/terminated, the run queue RQ11may include at least the tasks T0and T2, the run queue RQ12may include at least the task T1, the run queue RQ21may include at least the task T3, and the run queue RQ22may include at least the task T4. By way of example, but not limitation, the scheduling unit104may further ensure that each first task belonging to the first priority task group is included in a run queue of one first processor core. As shown inFIG. 2, all of the tasks T0and T1belonging to the first priority task group are included in run queues RQ11and RQ12of the first processor cores Core_11 and Core_12.

It should be noted that the task priority “0” of the task T0is higher than the task priority “2” of the task T2. Hence, after the task T0is added to the run queue RQ11, the task T0may become a task currently running on the first processor core Core_11, and the task T2may become a task waiting to run on the first processor core Core_11.

FIG. 3is a diagram illustrating a second task scheduling operation which dispatches one second task belonging to the second priority task group to a run queue of one second processor core with lower computing power. In this example, before a task T32with the task priority “3” is required to be added to one of the run queues RQ11, RQ12, RQ21, RQ22for execution, the run queue RQ11may include a task T2with the task priority “2” and may further include other tasks with lower task priorities (not shown inFIG. 3); the run queue RQ12may include a task T1with the task priority “1” and may further include other tasks with lower task priorities (not shown inFIG. 3); the run queue RQ21may include a task T31with the task priority “3” and may further include other tasks with lower task priorities (not shown inFIG. 3); and the run queue RQ22may include a task T4with the task priority “4” and may further include other tasks with lower task priorities (not shown inFIG. 3). A task with the highest task priority in the run queue RQ11may be the task T2, a task with the highest task priority in the run queue RQ12may be the task T1, a task with the highest task priority in the run queue RQ21may be the task T31, and a task with the highest task priority in the run queue RQ22may be the task T4. Hence, the tasks T1, T2, T31, and T4may be currently running on the first processor core Core_12, the first processor core Core_11, the second processor core Core_21, and the second processor core Core_22, respectively.

As mentioned above, it is possible that the system may create a new task, or a task may be added to a wait queue to wait for requested system resource(s) and then resumed when the requested system resource(s) is available. In this example, the task T32may be a new task or a resumed task (e.g., a waking task currently being woken up) that is not included in run queues RQ11, RQ12, RQ21, RQ22of the heterogeneous multi-core processor system10, and the scheduling unit104may need to select one of the run queues RQ11, RQ12, RQ21, RQ22and then dispatch the task T32to the selected run queue to thereby add the task T32to one of the run queues RQ11, RQ12, RQ21, RQ22for execution.

In this example, there are two first processor cores Core_11 and Core_12 and two second processor cores Core_21 and Core_22. Consider a case where the size of the first priority task group is set to be equal to the number of first processor cores, and the size of the second priority task group is set to be equal to the number of second processor cores. Hence, because task priorities of two tasks T1and T2are not lower than task priorities of other tasks (e.g., T31, T32and T4), and task priorities of two tasks T31and T32are not higher than task priorities of the tasks T1and T2and not lower than task priorities of other tasks (e.g., T4), the identifying unit102may identify tasks T1and T2as tasks belonging to the first priority task group, and may identify tasks T31and T32as tasks belonging to the second priority task group.

The task T32to be scheduled has the task priority “3” lower than task priorities “1” and “2” of tasks T1and T2, where the tasks T1and T2are identified as tasks belonging to the first priority task group and currently running on the first processor cores Core_12 and Core_11 with higher computing power. Hence, the scheduling unit104may push the task T32(which is identified as a task belonging to the second priority task group) into one of the run queues RQ21and RQ22to reduce or avoid undesired priority inversion.

The scheduling unit104may select a specific run queue from run queues RQ21and RQ22of the second processor cores Core_21 and Core_22, and add the task T32to the specific run queue. For example, the highest task priority possessed by one task in the specific run queue may have a lowest one of the highest task priorities possessed by tasks in the run queues RQ21and RQ22. Since the highest task priority “4” possessed by the task T4in the run queue RQ22is lower than the highest task priority “3” possessed by the task T31in the run queue RQ21, the scheduling unit104may select the run queue RQ22as the specific run queue to which the task T32will be added.

After the task scheduling of the task T32is accomplished/terminated, the run queue RQ11may include at least the task T2, the run queue RQ12may include at least the task T1, the run queue RQ21may include at least the task T31, and the run queue RQ22may include at least the tasks T32and T4. It should be noted that the task priority “3” of the task T32is higher than the task priority “4” of the task T4. Hence, after the task T32is added to the run queue RQ22, the task T32may become a task currently running on the second processor core Core_22, and the task T4may become a task waiting to run on the second processor core Core_22.

FIG. 4is a diagram illustrating a third task scheduling operation which dispatches one second task belonging to the second priority task group to a run queue of one second processor core with lower computing power. In this example, before a task T12with the task priority “1” is removed from the run queue RQ22, the run queue RQ11may include a task T01with the task priority “0” and may further include other tasks with lower task priorities (e.g., a task T31with the task priority “3” and a task T41with the task priority “4”); the run queue RQ12may include a task T02with the task priority “0” and may further include other tasks with lower task priorities (e.g., a task T2with the task priority “2”); the run queue RQ21may include a task T11with the task priority “1” and may further include other tasks with lower task priorities (e.g., a task T32with the task priority “3”); and the run queue RQ22may include the task T12with the task priority “1” and may further include other tasks with lower task priorities (e.g., a task T42with the task priority “4”). Before removal of the task T12in the run queue RQ22occurs, a task with the highest task priority in the run queue RQ11may be the task T01, a task with the highest task priority in the run queue RQ12may be the task T02, a task with the highest task priority in the run queue RQ21may be the task T11, and a task with the highest task priority in the run queue RQ22may be the task T12. Hence, before removal of the task T12in the run queue RQ22occurs, the tasks T01, T02, T11, and T12may be currently running on the first processor core Core_11, the first processor core Core_12, the second processor core Core_21, and the second processor core Core_22, respectively.

In a case where the execution of the task T12is accomplished/terminated by the second processor core Core_22 (i.e., the second processor core Core_22 is at a time point to schedule), the scheduling unit104may remove the accomplished/terminated task T12from the run queue RQ22due to that the task T12is a terminated task now. In another case where the system resource(s) requested by the task T12currently running on the second processor core Core_22 is not available yet, the execution of the task T12may be stopped, and the scheduling unit104may remove the task T12from the run queue RQ22and add the task T12to a wait queue since the task T12needs to wait for the requested system resource(s). In either of these cases, the scheduling unit104may pull a task that is identified as a task belonging to the second priority task group and included in a run queue of one of the first processor cores Core_11 and Core_12 and the second processor cores Core_21 and Core_22 to the run queue RQ22in response to removal of the task T12having the highest task priority in the run queue RQ22.

As mentioned above, the identifying unit102may be configured to perform task identification to determine the first priority task group (e.g., a highest priority task group) and the second priority task group (e.g., a next highest priority task group), where the size of the first priority task group may depend on the number of first processor cores with the first computing power, and the size of the second priority task group may depend on the number of second processor cores with the second computing power lower than the first computing power. In this example, there are two first processor cores Core_11 and Core_12 and two second processor cores Core_21 and Core_22. Consider a case where the size of the first priority task group is set to be equal to the number of first processor cores, and the size of the second priority task group is set to be equal to the number of second processor cores. After the task T12is removed from the run queue RQ22, task priorities of two tasks T01and T02are not lower than task priorities of other tasks (e.g., T11, T2, T31, T32, T41, and T42), and task priorities of two tasks T11and T2are not higher than task priorities of tasks T01and T02and not lower than task priorities of other tasks (e.g., T31, T32, T41and T42). Hence, the identifying unit102may identify tasks T01and T02as tasks belonging to the first priority task group, and may identify tasks T11and T2as tasks belonging to the second priority task group.

After the task T12is removed from the run queue RQ22, the task T42waiting to run on the second processor core Core_22 becomes a task with the highest task priority in the run queue RQ22. The task priorities of tasks T11and T2belonging to the second priority task group are higher than the task priority of the task T42, where the task T2belonging to the second priority task group is included in the run queue RQ12of the first processor core Core_12. Hence, the scheduling unit104may pull the task T2from the run queue RQ12to the run queue RQ22to reduce or avoid undesired priority inversion. For example, after the task T12is removed from the run queue RQ22, the scheduling unit104may pull the task T2belonging to the second priority task group from the run queue RQ12of the first processor core Core_12 to the run queue RQ22of the second processor core Core_22 when the task T2has the task priority that is the next highest task priority possessed by the run queue RQ12(i.e., the task T2in the run queue RQ12is a task waiting to run on the first processor core Core_12). For another example, after the task T12is removed from the run queue RQ22, the scheduling unit104may pull the task T2belonging to the second priority task group from the run queue RQ12of the first processor core Core_12 to the run queue RQ22of the second processor core Core_22 when the task T2has the task priority that is next to the task priority of the removed task T12. For yet another example, after the task T12is removed from the run queue RQ22, the scheduling unit104may pull the task T2belonging to the second priority task group from the run queue RQ12of the first processor core Core_12 to the run queue RQ22of the second processor core Core_22 when the task T2has the task priority that is higher than the highest task priority possessed by one task (e.g., T42) in the run queue RQ22that is waiting to run.

After the task scheduling of the task T2is accomplished/terminated, the run queue RQ11may include at least the tasks T01, T31, and T41, the run queue RQ12may include at least the task T02, the run queue RQ21may include at least the tasks T11and T32, and the run queue RQ22may include at least the tasks T2and T42. It should be noted that the task priority “2” of the task T2is higher than the task priority “4” of the task T42. Hence, after the task T2is pulled from the run queue RQ12to the run queue RQ22, the task T2may become a task currently running on the second processor core Core_22, and the task T42is still a task waiting to run on the second processor core Core_22.

In above example inFIG. 4, the task T2is pulled from the run queue RQ12to the run queue RQ22. However, this is for illustrative purposes only, and is not meant to be a limitation of the present invention. In another case, the same task scheduling policy mentioned above may be followed to pull the task T2with the task priority “2” from a different run queue to the run queue RQ22with the task T12 removed therefrom. For example, when the task T2with the task priority “2” is included in the run queue RQ11rather than the run queue RQ12, the task T2belonging to the second priority task group may be pulled from the run queue RQ11to the run queue RQ22after the task T12is removed from the run queue RQ22. For another example, when the task T2with the task priority “2” is included in the run queue RQ21rather than the run queue RQ12, the task T2belonging to the second priority task group may be pulled from the run queue RQ21to the run queue RQ22after the task T12is removed from the run queue RQ22.

FIG. 5is a diagram illustrating a fourth task scheduling operation which dispatches one first task belonging to the first priority task group to a run queue of one first processor core with higher computing power. In this example, before a task T01with the task priority “0” is removed from the run queue RQ11, the run queue RQ11may include a task T01with the task priority “0” and may further include other tasks with lower task priorities (e.g., a task T3with the task priority “3” and a task T41with the task priority “4”); the run queue RQ12may include a task T02with the task priority “0” and may further include other tasks with lower task priorities (e.g., a task T21with the task priority “2”); the run queue RQ21may include a task T1with the task priority “1” and may further include other tasks with lower task priorities (e.g., a task T22with the task priority “2”); and the run queue RQ22may include a task T23with the task priority “2” and may further include other tasks with lower task priorities (e.g., a task T42with the task priority “4”). Before removal of the task T01in the run queue RQ11occurs, a task with the highest task priority in the run queue RQ11may be the task T01, a task with the highest task priority in the run queue RQ12may be the task T02, a task with the highest task priority in the run queue RQ21may be the task T1, and a task with the highest task priority in the run queue RQ22may be the task T23. In addition, before removal of the task T01in the run queue RQ11occurs, the tasks T01, T02, T1, and T23may be currently running on the first processor core Core_11, the first processor core Core_12, the second processor core Core_21, and the second processor core Core_22, respectively.

As mentioned above, a task may be removed from a run queue when execution of the task is accomplished/terminated or system resource(s) requested by the task is not available yet. In this example, the scheduling unit104may remove the task T01from the run queue RQ11due to any of above reasons. In addition, the scheduling unit104may pull a task that is identified as a task belonging to the first priority task group and included in a run queue of one of the second processor cores Core_21 and Core_22 and the first processor core Core_12 to the run queue RQ11in response to removal of the task T01having the highest task priority in the run queue RQ11. Alternatively, the task T1may be a task waiting to run on the first processor core Core_11 at the time the task T01is removed from the run queue RQ11. This also falls within the scope of the present invention.

There are two first processor cores Core_11 and Core_12 and two second processor cores Core_21 and Core_22. Consider a case where the size of the first priority task group is set to be equal to the number of first processor cores, and the size of the second priority task group is set to be equal to the number of second processor cores. After the task T01is removed from the run queue RQ11, task priorities of two tasks T02and T1are not lower than task priorities of other tasks (e.g., T21, T22, T23, T3, T41, and T42), and task priorities of two tasks T22and T23are not higher than task priorities of tasks T02and T1and not lower than task priorities of other tasks (e.g., T21, T3, T41and T42). Hence, the identifying unit102may identify tasks T02and T1as tasks belonging to the first priority task group, and may identify tasks T22and T23as tasks belonging to the second priority task group. It should be noted that identifying the tasks T22and T23as tasks belonging to the second priority task group is for illustrative purposes only. For example, any two of the tasks T21, T22and T23having the same task priority “2” may be identified as tasks belonging to the second priority task group.

After the task T01is removed from the run queue RQ11, the task T3waiting to run on the first processor core Core_11 becomes a task with the highest task priority in the run queue RQ11. The task priorities of tasks T02and T1belonging to the first priority task group are higher than the task priority of the task T3, where the task T1belonging to the first priority task group is included in the run queue RQ21of the second processor core Core_21. Hence, the scheduling unit104may instruct the run queue RQ21to release the task T1currently running on the second processor core Core_21, and grant the task T22in the run queue RQ21to be selected for running on the second processor core Core_21. And the scheduling unit104may pull the released task T1from the run queue RQ21to the run queue RQ11to reduce or avoid undesired priority inversion. For example, the scheduling unit104may pull the task T1belonging to the first priority task group from the run queue RQ21of the second processor core Core_21 to the run queue RQ11of the first processor core Core_11 when the highest task priority possessed by one task (e.g., T1) in the run queue RQ21is the highest one of highest task priorities possessed by tasks (e.g., T1and T23) in run queues of the second processor cores Core_21 and Core_22 and the task (e.g., T1) with the highest task priority in the run queue RQ21has a task priority higher than the highest task priority possessed by one task (e.g., T3) in the run queue RQ11that is waiting to run. For another example, the scheduling unit104may pull the task T1belonging to the first priority task group from the run queue RQ21of the second processor core Core_21 to the run queue RQ11of the first processor core Core_11 when the task T1has the task priority that is next to the task priority of the removed task T01and higher than the highest task priority possessed by one task (e.g., T3) in the run queue RQ11that is waiting to run.

After the task scheduling of the task T1is accomplished/terminated, the run queue RQ11may include at least the tasks T1, T3and T41, the run queue RQ12may include at least the tasks T02and T21, the run queue RQ21may include at least the task T22, and the run queue RQ22may include at least the tasks T23and T42. In this example, the scheduling unit104may further ensure that each first task belonging to the first priority task group is included in a run queue of one first processor core. As shown inFIG. 5, all of the tasks T1and T02belonging to the first priority task group are included in run queues RQ11and RQ12of the first processor cores Core_11 and Core_12.

It should be noted that the task priority “1” of the task T1is higher than the task priority “3” of the task T3. Hence, after the task T1is pulled from the run queue RQ21to the run queue RQ11, the task T1becomes a task currently running on the first processor core Core_11, and the task T3is still a task waiting to run on the first processor core Core_11.

All tasks to be executed on the heterogeneous multi-core processor10may be divided into real-time tasks and normal tasks based on the task priorities. Compared to the normal tasks, the real-time tasks have higher task priorities. For example, each of the real-time tasks may be given a task priority falling within a first priority range such as [0, 99], and each of the normal tasks may be given a task priority falling within a second priority range such as [100, 139]. In above embodiments, the proposed task scheduling method performed by the task scheduler100may be used for real-time task scheduling. Hence, the tasks scheduled using the proposed task scheduling method may be real-time tasks only. However, this is not meant to be a limitation of the present invention. In an alternative design, the proposed task scheduling method performed by the task scheduler100may be used for normal task scheduling. Hence, the tasks scheduled using the proposed task scheduling method may be normal tasks only. In another alternative design, the tasks scheduled using the proposed task scheduling method may include real-time task(s) and normal task(s). To put it simply, any task scheduler of an OS kernel that uses the proposed task scheduling method falls within the scope of the present invention.