Boosting user thread priorities to resolve priority inversions

• US 10,579,417 B2
• Filed: 04/26/2017
• Issued: 03/03/2020
• Est. Priority Date: 04/26/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bak, Yevgeniy M., Iyigun, Mehmet, Kleynhans, Christopher Peter, Raza, Syed A.
• Primary Examiner(s): Cao, Diem K
• Application Number:
  US15/497,482
• Publication Number:
  US 20180314547A1
• Time in Patent Office: 1,042 Days
• Field of Search: None
• CPC Class Codes: G06F 9/4831 with variable priority
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The threads of a user mode process can access various different resources of a computing device, and such access can be serialized. To access a serialized resource, a thread acquires a lock for the resource. For each context switch in the computing device, a module of the operating system kernel checks for priority inversions, which is a situation in which a higher priority thread of the user mode process is waiting for (blocking on) a resource for which a lower priority thread has acquired a lock. In response to detecting such a priority inversion, the priority of the lower priority thread is boosted to allow the priority thread to execute and eventually release the lock that the higher priority thread is waiting for.

Claims

1. A method implemented in a computing device, the method comprising:

in response to determining to switch contexts in the computing device, retrieving lock data from a lock buffer of a user-mode thread being switched out, the lock data including an identifier identifying one or more resources that the user-mode thread has locked;

adding the retrieved lock data to a lock record that is associated with a process that includes the user-mode thread;

determining, based on the lock record and the lock data, whether the user-mode thread is in a priority inversion; and

increasing a priority of the user-mode thread in response to determining that the user-mode thread is in a priority inversion.

2. The method as recited in claim 1, the lock data further including an indication that the user-mode thread being switched out is blocked on the resource identified by the identifier.

3. The method as recited in claim 1, wherein the resource remains locked by the user-mode thread at at time of switching contexts.

4. The method as recited in claim 1, the lock record comprising a lock record that maintains lock data for only the process and contains no lock data for any other processes running on the computing device.

5. The method as recited in claim 1, further comprising maintaining additional lock data for multiple processes running on the computing device, the lock data and the additional lock data being keyed based on an identifier of both the resource and the process.

6. The method as recited in claim 1, wherein the determining that the user-mode thread is in a priority inversion is based on another resource identifier in the lock record and is based on the identifier in the lock data added to the lock record.

7. The method as recited in claim 6, the increasing the priority of the user-mode thread comprising setting the priority of the user-mode thread to be a same priority as another user-mode thread that has been determined, according to the lock record, to be waiting on the resource that has been locked by the user-mode thread.

8. The method as recited in claim 1, the priority of the user-mode thread comprising a processor priority of the user-mode thread.

9. The method as recited in claim 1, the priority of the user-mode thread comprising an I/O priority of the user-mode thread.

10. The method as recited in claim 1, further comprising returning, based on the resource having been released by the user-mode thread, the user-mode thread to a same priority that the user-mode thread had prior to the increasing of its priority.

11. The method as recited in claim 10, the returning the user-mode thread to the same priority that the user-mode thread had prior to being updated comprising lowering the priority of the user-mode at the time the lock record is released.

12. A computing device comprising:

one or more processors; and

a computer-readable storage media having stored thereon multiple instructions that, when executed by the one or more processors, cause the one or more processors to;

retrieve, in response to a context switch in the computing device, lock data from a lock buffer of a user-mode thread being switched out, the lock data including an identifier of one or more resources that the user-mode thread has locked;

add the lock data, including the identifier, to a lock record that is associated with a process that includes the user-mode thread;

determine, based on the identifier in the lock record, whether there is a priority inversion involving the user-mode thread; and

based on the determining step determining that there is a priority inversion involving the user-mode thread, increasing a priority of the user-mode thread.

13. The computing device as recited in claim 12, the identifier being an identifier of one or more resources that remain locked by the user-mode thread at the time of the context switch.

14. The computing device as recited in claim 12, wherein to determine whether the priority of the user-mode thread is to be increased comprises determining that the priority of the user-mode thread is to be increased in response to determining, based on the lock record, that the user-mode thread has locked a resource that a higher priority user-mode thread of the process is blocking on.

15. The computing device as recited in claim 14, wherein increasing the priority of the user-mode thread comprises increasing the priority of the user-mode thread to be a same priority as the higher priority user-mode thread blocking on the resource that has been locked by the user-mode thread.

16. The computing device as recited in claim 12, wherein the multiple instructions further cause the one or more processors to return, in response to the resource being released by the user-mode thread, the user-mode thread to a same priority that the user-mode thread had before the priority increase.

17. Computer-readable storage hardware storing instructions configured to cause a computing device to perform a process, the process comprising:

maintaining thread-lock buffers for respective threads of a process, the threads having respective priorities, the maintaining comprising, for each thread;

when requesting a lock on a resource, adding an identifier of the resource to its respective thread-lock buffer; and

when releasing a lock on a resource, removing an identifier of the resource from its respective thread-lock buffer;

each time one of the threads is context-switched out of the processor;

maintaining a lock-tracking record corresponding to the thread being context-switched out by (i) determining that the lock-tracking record lacks an entry for a resource that is in the corresponding thread-lock, and (ii) based thereon, adding an identifier of the resource to the lock-tracking record; and

determining whether any of the threads are in a priority inversion based on the identifiers of resources in the lock-tracking record, and when a thread is determined to be in a priority inversion, increasing the priority of the determined thread.

18. Computer-readable storage hardware according to claim 17, wherein the determining whether any of the threads are in a priority inversion comprises searching for, in the lock-tracking record, duplicate identifiers of locks.

19. Computer-readable storage hardware according to claim 17, wherein the determining whether any of the threads are in a priority inversion is performed responsive to scheduling the thread to be context-switched out and after the maintaining has been performed.

20. Computer-readable storage hardware according to claim 17, wherein the maintaining the lock-tracking record corresponding to the thread being context-switched out further comprises (i) determining that the lock-tracking record contains an entry for a resource that is not in the corresponding thread-lock, and (ii) based thereon, removing an identifier of the resource to the lock-tracking record.