Priority Inheritance in Multithreaded Systems

• US 20120222035A1
• Filed: 02/25/2011
• Published: 08/30/2012
• Est. Priority Date: 02/25/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Plondke, Erich J.
• Granted Patent: US 8,479,207 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method includes determining that a first task having a first priority is blocked from execution at a multithreaded processor by a second task having a second priority that is lower than the first priority. A temporary priority of the second task is set to be equal to an elevated priority, such that in response to the second task being preempted from execution by another task, the second task is rescheduled for execution based on the elevated priority identified by the temporary priority.

Claims

1. A method, comprising:

at a multithreaded processor, determining that a first task having a first priority is blocked from execution by a second task having a second priority that is lower than the first priority; and

setting a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that in response to the second task being preempted from execution at the multithreaded processor by another task, the second task is rescheduled for execution based on the elevated priority identified by the temporary priority.

2. The method of claim 1, further comprising:

maintaining a ready list identifying tasks that are ready to be executed at the multithreaded processor; and

maintaining a run list identifying tasks that are scheduled for execution at the in processor,

wherein the temporary priority of the second task is set to the first priority without modifying the contents of the ready list or the run list.

3. The method of claim 2, wherein rescheduling the second task for execution comprises:

inserting the second task into the ready list at the temporary priority;

detecting that the run list includes a third task having a lower priority than the temporary priority; and

replacing the third task in the run list with the second task.

4. The method of claim 1, further comprising:

when the second task is not preempted from execution at the multithreaded processor, executing the second task in accordance with the second priority; and

clearing the temporary priority of the second task.

5. The method of claim 1, wherein the first task and the second task are executed by a real-time operating system executed by the multithreaded processor.

6. The method of claim 1, wherein the first task comprises a device task, a critical system task, or any combination thereof.

7. The method of claim 1, wherein the second task comprises a maintenance task, a background task, a profiling task, a user interface task, or any combination thereof.

8. The method of claim 1, wherein determining that the first task is blocked from execution by the second task comprises:

receiving a request from the first task for a computing resource; and

determining that the second task holds a synchronization object associated with the computing resource.

9. The method of claim 8, wherein the synchronization object comprises a mutex or a semaphore.

10. The method of claim of 1, wherein the elevated priority is equal to the first priority.

11. The method of claim 1, further comprising:

determining that a third task having a third priority is blocked, from execution by the second task, wherein the third priority is higher than the first priority and the second priority; and

setting the temporary priority of the second task to be greater than or equal to the third priority.

12. An apparatus, comprising:

a multithreaded processor;

a memory; and

an operating system executable by the multithreaded processor to;

determine that a first task having a first priority is blocked from execution at the multithreaded processor by a second task having a second priority that is lower than the first priority; and

set a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that in response to the second task being preempted from execution at the multithreaded processor by another task, the second task is rescheduled for execution based on the elevated priority identified by the temporary priority.

13. The apparatus of claim 12, further comprising one or more additional multithreaded processors.

14. The apparatus of claim 12, further comprising:

a ready list stored, at the memory, wherein the ready list identifies tasks that are ready to be executed at the multithreaded processor; and

a run list stored at the memory, wherein the run list identifies tasks that are scheduled for execution at the multithreaded processor;

wherein the operating system is further executable by the multithreaded processor to set the temporary priority of the second task to the first priority without modifying the contents of the ready list or the run list.

15. The apparatus of claim 14, wherein rescheduling the second task for execution comprises:

inserting the second task into the ready list at the temporary priority;

detecting that the run list includes a task having a lower priority than the temporary priority; and

replacing the task in the run list with the second task.

16. The apparatus of claim 12, wherein the memory comprises a random access memory (RAM), a cache memory, a register-based memory, or any combination thereof.

17. An electronic device, comprising:

means for scheduling tasks for execution;

means for storing scheduling data associated with the scheduled tasks;

means for determining that a first task having a first priority is blocked from execution by a second task having a second priority that is lower than the first priority; and

means for setting a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that in response to the second task being preempted from execution by another task, the means for scheduling tasks reschedules the second task for execution based on the elevated priority identified by the temporary priority.

18. The electronic device of claim 17, further comprising means for executing the scheduled tasks.

19. The electronic device of claim 18, wherein the scheduling data comprises:

a ready list identifying tasks that are ready to be executed at the means for executing; and

a run list identifying tasks that are scheduled for execution at the means for executing.

20. The electronic device of claim 19, wherein the temporary priority of the second task is set to the first priority without modifying the contents of the ready list or the run list.

21. A computer-readable non-transitory storage medium comprising instructions that, when executed by a computer, cause the computer to:

determine that a first task having a first priority is blocked from execution at a multithreaded processor by a second task having a second priority that is lower than the first priority; and

set a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that in response to the second task being preempted from execution at the multithreaded processor by another task, the second task is rescheduled for execution based on the elevated priority identified by the temporary priority.

22. The computer-readable non-transitory storage medium of claim 21, further comprising instructions that, when executed by the computer, cause the computer to:

maintain a ready list identifying tasks that are ready to be executed at the multithreaded processor; and

maintain a run list identifying tasks that are scheduled for execution at the multithreaded processor,

wherein the temporary priority of the second task is set to the elevated priority without modifying the ready list or the run list.

23. The computer-readable non-transitory storage medium of claim 22, wherein rescheduling the second task for execution comprises:

inserting the second task into the ready list at the temporary priority;

detecting that the run list includes a third task having a lower priority than the temporary priority; and

replacing the third task in the run list with the second task.

24. The computer-readable non-transitory storage medium of claim 21, wherein the elevated priority is a highest task priority at the multithreaded processor.

25. The computer-readable non-transitory storage medium of claim 21, wherein the elevated priority is equal to the first priority.