TASK PRIORITY PROCESSING METHOD AND PROCESSING DEVICE

• US 20200133724A1
• Filed: 12/24/2019
• Published: 04/30/2020
• Est. Priority Date: 06/27/2017
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Chen, Lingjun, Wang, Bin, Zhu, Liangliang, Zeng, Xu, Liu, Zilong, Cai, Junjie
• Granted Patent: US 11,321,125 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

In a multitask computing system, there are multiple tasks include a first task, a second task, and a third task, and the first task has a higher priority than that of the second task and the third task. A method including raising the priority of the second task that shares a first critical section with the first task and is accessing the first critical section when the first task is blocked due to failure to access the first critical section; determining whether there is a third task that shares a second critical section with the second task and is accessing the second critical section; and raising, when the third task is present, the priority of the third task. The techniques of the present disclosure prevent a low-priority third task from delaying the execution of a second task, thus avoiding the priority inversion caused by the delayed execution of a high-priority first task.

Claims

1. A method comprising:

determining that a first task is blocked due to failure to access a first critical section in a multitask computing system;

raising a priority of a second task that shares a first critical section with the first task and is accessing the first critical section, the first task having a higher priority than that of the second task and a third task;

determining that the third task is accessing a second critical section which is shared with the second task; and

raising a priority of the third task.

2. The method of claim 1, wherein the raising the priority of the second task comprises raising the priority of the second task to a priority of the first task.

3. The method of claim 1, wherein the raising the priority of the second task comprises raising the priority of the second task to a priority only lower than a priority of the first task.

4. The method of claim 1, wherein the raising the priority of the second task comprises raising the priority of the second task to be higher than the priority of the third task.

5. The method of claim 1, wherein the raising the priority of the third task comprises raising the priority of the third task to a priority of the first task.

6. The method of claim 1, wherein the first critical section and the second critical section are the same critical section.

7. The method of claim 1, wherein the first critical section and the second critical section are different critical sections.

8. The method of claim 1, wherein after the raising the priority of the third task, the method further comprises:

determining that there is a fourth task that shares a third critical section with the third task and is accessing the third critical section;

determining that a priority of the fourth task is lower than a priority of the first task; and

raising the priority of the fourth task.

9. The method of claim 8, wherein the raising the priority of the fourth task comprises raising the priority of the fourth task to the priority of the first task.

10. The method of claim 8, wherein after the raising the priority of the fourth task, the method further comprises:

determining that there is an (N+1)th task that shares a critical section with an Nth task having a raised priority and is accessing the critical section, N being a positive integer greater than or equal to 4;

determining that a priority of the (N+1)th task is lower than a priority of the first task; and

raising the priority of the (N+1)th task.

11. The method of claim 10, wherein the raising the priority of the (N+1)th task comprises raising the priority of the (N+1)th task to the priority of the first task.

12. A device comprising:

one or more processors; and

one or more memories storing computer readable instructions that, executable by the one or more processors, cause the one or more processors to perform acts comprising;

determining that a first task is blocked due to failure to access a first critical section;

raising a priority of a second task that shares a first critical section with the first task and is accessing the first critical section, the first task having a higher priority than that of the second task and a third task;

determining that there is the third task that shares a second critical section with the second task and is accessing the second critical section; and

raising a priority of the third task.

13. The device of claim 12, wherein the raising the priority of the second task comprises raising the priority of the second task to a priority of the first task.

14. The device of claim 12, wherein the raising the priority of the second task comprises raising the priority of the second task to a priority of the first task.

15. The device of claim 12, wherein the raising the priority of the second task comprises raising the priority of the second task to a priority only lower than a priority of the first task.

16. The device of claim 12, wherein the raising the priority of the second task comprises raising the priority of the second task to be higher than the priority of the third task.

17. The device of claim 12, wherein the raising the priority of the third task comprises raising the priority of the third task to a priority of the first task.

18. The device of claim 12, wherein the first critical section and the second critical section are the same critical section.

19. The device of claim 12, wherein the first critical section and the second critical section are different critical sections.

20. One or more memories storing computer readable instructions that, executable by one or more processors, cause the one or more processors to perform acts comprising:

determining that a first task is blocked due to failure to access a first critical section in a multitask computing system, a priority of the first task being higher than a priority of the second task, the priority of the second task being higher than a priority of the third task;

raising the priority of the second task that shares a first critical section with the first task and is accessing the first critical section up to the priority of the first task;

determining that there is the third task that shares a second critical section with the second task and is accessing the second critical section; and

raising the priority of the third task up to the priority of the first task.