Efficient priority-aware thread scheduling

• US 10,606,653 B2
• Filed: 02/13/2017
• Issued: 03/31/2020
• Est. Priority Date: 05/31/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kishan, Arun Upadhyaya, Clift, Neill Michael, Iyigun, Mehmet, Bak, Yevgeniy, Raza, Syed Aunn Hasan
• Primary Examiner(s): Tang, Kenneth
• Application Number:
  US15/431,746
• Publication Number:
  US 20170228260A1
• Time in Patent Office: 1,142 Days
• Field of Search: None
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

A priority-based scheduling and execution of threads may enable the completion of higher-priority tasks above lower-priority tasks. Occasionally, a high-priority thread may request a resource that has already been reserved by a low-priority thread, and the higher-priority thread may be blocked until the low-priority thread relinquishes the reservation. Such prioritization may be acceptable if the low-priority thread is able to execute comparatively unimpeded, but in some scenarios, the low-priority thread may execute at a lower priority than a medium-priority thread that also has a lower priority than the high-priority thread. In this scenario, the medium-priority thread is effectively but incorrectly prioritized above the high-priority thread. Instead, upon detecting this scenario, the device may temporarily elevate the priority of the lower-priority thread over the priority of the medium-priority thread until the lower-priority thread relinquishes the resource, thereby reducing the waiting period of the high-priority thread for the requested resource.

Claims

1. A method of prioritizing a plurality of threads, including at least a first thread, a second thread, a third thread, and a fourth thread, each of which is owned by a process and available for being scheduled to be executed on a processor of a device and has a respective priority, the priority of the first thread being higher than the priority of the second thread, the priority of the second thread being higher than the priority of the third thread, and the priority of the third thread being higher than the priority of the fourth thread, the method comprising:

allocating a reservation of a first resource to the third thread;

during the reservation of the first resource by the third thread, receiving a request from the fourth thread for the first resource;

allocating a reservation of a second resource to the fourth thread;

during the reservation of the second resource to the fourth thread, receiving a request from the first thread for the second resource;

detecting a resource conflict comprising a delayed release of the reservation of the second resource by the execution of the fourth thread while the request for the second resource by the first thread is pending; and

addressing the resource conflict by;

temporarily elevating the priority of the third thread to a priority that is higher than the priority of the second thread, such that the third thread is scheduled to be executed prior to the second thread;

in response to the third thread relinquishing the first resource, temporarily elevating the priority of the fourth thread to a priority that is higher than the priority of the second thread, such that the fourth thread is scheduled to be executed prior to the second thread; and

in response to the fourth thread relinquishing the second resource, schedule the first thread to be executed prior to the second thread.

2. The method of claim 1, wherein:

the device further comprises a reservation record; and

the method further comprises;

detecting a reservation of a first or a second resource by a thread;

recording the reservation by the corresponding thread on the corresponding resource in the reservation record; and

identifying the resource reserved by the thread further comprises;

for respective threads, identifying at least one resource reserved by the thread according to the reservation record.

3. The method of claim 2, wherein recording the reservation in the reservation record further comprises:

recording the reservation of the first resource or the second resource in the reservation record before awarding the reservation of the corresponding resource to the thread.

4. The method of claim 2, wherein further comprises:

after detecting the thread relinquishing the reservation of the first or second resource, removing the reservation of the corresponding resource from the reservation record.

5. The method of claim 2, wherein recording the reservation further comprises:

recording the reservation by the thread on the corresponding resource only if at least one other thread has requested the corresponding resource.

6. The method of claim 2, wherein detecting the resource conflict comprising a delayed release of the reservation of the second resource by the execution of the fourth thread while the request for the second resource by the first thread comprises:

examining the reservation record store to detect the fourth thread having a reservation on the selected resource.

7. The method of claim 6, wherein:

the reservation record further comprises a forest of binary trees; and

the method further comprises;

detecting an imbalance in a binary tree comprising the reservation record; and

rebalancing the binary tree.

8. The method of claim 7, wherein the binary tree further comprises a partitioned red/black tree.

9. The method of claim 2, wherein the reservation record further comprises, for each of the first and second resources, a reservation list of threads using the respective resource.

10. The method of claim 2, wherein detecting the reservation of the corresponding resource by the thread further comprises:

recording the reservation by the thread on the corresponding resource in the reservation record upon context switching away from the thread.

11. The method of claim 1, wherein elevating the priority of the third thread further comprises, responsive to context-switching away from the first thread:

identifying the corresponding resource awaited by the first thread; and

identifying the corresponding thread that has reserved the corresponding resource;

identifying the second thread having a priority that is below the priority of the first thread and above the priority of the third thread; and

elevating the priority of the third thread above the second thread.

12. The method of claim 1, wherein elevating the priority of the third thread further comprises:

setting the priority of the third thread at least as high as the priority of the first thread.

13. The method of claim 1, wherein elevating the priority of the third thread further comprises:

detecting an adjustment of the priority of the first thread after elevating the priority of the third thread; and

adjusting the priority of the third thread according to the adjustment of the priority of the first thread.

14. The method of claim 1, wherein elevating the priority of the third thread further comprises:

detecting the third thread relinquishing the reservation of the resource; and

reducing the priority of the third thread.

15. The method of claim 1, wherein:

respective resources are accessed according to a resource access type;

respective threads further comprise at least two resource access type priorities respectively identifying a priority of the thread for accessing resources according to a resource access type; and

elevating the priority of the thread further comprises;

elevating for the thread the resource access type priority for the resource access type of the corresponding resource.

16. The method of claim 15, wherein elevating the priority of the thread further comprises:

elevating for the thread for a second resource access type priority for a second resource access type that is not associated with the selected resource.

17. The method of claim 1, wherein elevating the priority of the third thread further comprises:

identifying that the third thread is awaiting the second resource that is reserved by the fourth thread having a priority below the priority of the second thread; and

elevating the priority of the fourth thread above the priority of the second thread.

18. The method of claim 1, wherein elevating the priority of the third thread further comprises:

elevating the priority of a first operation of the third thread that involves the first resource; and

refraining from elevating the priority of a second operation of the third thread that does not involve the first resource.

19. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are structured such that, when executed by one or more processors of a computing system, the computer-executable instructions cause the computing system to prioritize a plurality of threads, including at least a first thread, a second thread, a third thread, and a fourth thread, each of which is owned by a process and available for being scheduled to be executed on the processor of the computing system and has a respective priority, the priority of the first thread being higher than the priority of the second thread, the priority of the second thread being higher than the priority of the third thread, and the priority of the third thread being higher than the priority of the fourth thread, the instructions comprising instructions that are executable to cause the computing system to perform at least the following:

allocate a reservation of a first resource to the third thread;

during the reservation of the first resource by the third thread, receive a request from the fourth thread for the first resource;

allocate a reservation of a second resource to the fourth thread;

during the reservation of the second resource to the fourth thread, receive a request from the first thread for the second resource;

detect a resource conflict comprising a delayed release of the reservation of the second resource by the execution of the fourth thread while the request for the second resource by the first thread is pending; and

address the resource conflict by;

temporarily elevating the priority of the third thread to a priority that is higher than the priority of the second thread, such that the third thread is scheduled to be executed prior to the second thread;

in response to the third thread relinquishing the first resource, temporarily elevating the priority of the fourth thread to a priority that is higher than the priority of the second thread, such that the fourth thread is scheduled to be executed prior to the second thread; and

in response to the fourth thread relinquishing the second resource, scheduling the first thread to be executed prior to the second thread.

20. A computing system that executes a plurality threads, including at least a first thread, a second thread, a third thread, and a fourth thread, each of which is owned by a process and available for being scheduled to be executed by the computing system and has a respective priority, the priority of the first thread being higher than the priority of the second thread, the priority of the second thread being higher than the priority of the third thread, and the priority of the third thread being higher than the priority of the fourth thread, comprising:

a processor; and

a memory having stored thereon computer-executable instructions that are executable by the processor to cause the computing system to prioritize the first thread, the second thread, the third thread, and the fourth thread, the instructions including instructions that are executable to cause the computing system to perform at least the following;

allocate a reservation of a first resource to the third thread;

during the reservation of the first resource by the third thread, receive a request from the fourth thread for the first resource;

allocate a reservation of a second resource to the fourth thread;

during the reservation of the second resource to the fourth thread, receive a request from the first thread for the second resource;

detect a resource conflict comprising a delayed release of the reservation of the second resource by the execution of the fourth thread while the request for the resource by the first thread is pending; and

address the resource conflict by;

temporarily elevating the priority of the third thread to a priority that is higher than the priority of the second thread, such that the third thread is scheduled to be executed prior to the second thread;

in response to the third thread relinquishing the first resource, temporarily elevating the priority of the fourth thread to a priority that is higher than the priority of the second thread, such that the fourth thread is scheduled to be executed prior to the second thread; and

in response to the fourth thread relinquishing the second resource, scheduling the first thread to be executed prior to the second thread.