Priority inheritance in multithreaded systems

• US 8,479,207 B2
• Filed: 02/25/2011
• Issued: 07/02/2013
• Est. Priority Date: 02/25/2011
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Plondke, Erich J.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Sun, Charlie
• Application Number:
  US13/035,184
• Publication Number:
  US 20120222035A1
• Time in Patent Office: 858 Days
• Field of Search: 718/103
• 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 hardware-multithreaded processor, determining that a first task is blocked from execution by a second task, the first task having a first priority and the second task having a second priority that is lower than the first priority;

setting a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that when the second task has the temporary priority and is preempted from execution at the hardware-multithreaded processor by another task, the second task is rescheduled for execution based on the temporary priority and when the second task has the temporary priority and is not preempted from execution at the hardware-multithreaded processor, the second task will be executed based on the second priority; and

clearing the temporary priority of the second task in response to the second task releasing a synchronization object blocking the first task from execution.

2. The method of claim 1, further comprising:

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

maintaining a run list that identifies tasks that are scheduled for execution at the hardware-multithreaded processor,

wherein the temporary priority of the second task is set to the first priority without modifying 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 2, further comprising:

determining that a third task has a third priority higher than the second priority, wherein the third priority is lower than the elevated priority, wherein the third task is in the ready queue, and wherein the second task is in the run queue; and

in response to determining that the third task has the third priority, inserting the second task into the ready queue according to the temporary priority and inserting the third task into the run queue according to the third priority.

5. The method of claim 4, wherein inserting the third task into the run queue comprises scheduling the third task for execution at a second hardware thread.

6. The method of claim 1, further comprising:

while executing the second task based on the second priority, determining that the second task is preempted from execution by a third task; and

after the second task has been preempted by execution of the third task, executing the second task based on the temporary priority.

7. The method of claim 1, wherein the first task is scheduled to execute at a first hardware thread of the hardware-multithreaded processor, and wherein the second task is scheduled to execute at a second hardware thread of the hardware-multithreaded processor.

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

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

10. 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.

11. 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.

12. The method of claim 11, wherein the synchronization object comprises a mutex or a semaphore.

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

14. 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.

15. An apparatus, comprising:

a hardware-multithreaded processor;

a memory; and

an operating system executable by the hardware-multithreaded processor to;

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

set a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that when the second task has the temporary priority and is preempted from execution at the hardware-multithreaded processor by another task, the second task is rescheduled for execution based on the temporary priority and when the second task has the temporary priority and is not preempted from execution at the hardware-multithreaded processor, the second task will be executed based on the second priority; and

clear the temporary priority of the second task in response to the second task releasing a synchronization object blocking the first task from execution.

16. The apparatus of claim 15, further comprising one or more additional hardware-multithreaded processors.

17. The apparatus of claim 15, further comprising:

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

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

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

18. The apparatus of claim 17, 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.

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

20. An electronic device, comprising:

means for scheduling tasks for execution at a plurality of hardware threads;

means for storing scheduling data associated with the scheduled tasks;

means for determining that a first task is blocked from execution by a second task, the first task having a first priority and the 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 when the second task has the temporary priority and is 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 and when the second task has the temporary priority and is not preempted from execution, the second task will be executed based on the second priority; and

means for clearing the temporary priority of the second task in response to the second task releasing a synchronization object blocking the first task from execution.

21. The electronic device of claim 20, further comprising means for executing the scheduled tasks, wherein the means for executing the scheduled tasks includes the plurality of hardware threads.

22. The electronic device of claim 21, wherein the scheduling data comprises:

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

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

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

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

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

set a temporary priority of the second task to be equal to an elevated priority that is higher than the second priority, such that when the second task has the temporary priority and is preempted from execution at the hardware-multithreaded processor by another task, the second task is rescheduled for execution based on the temporary priority and when the second task has the temporary priority and is not preempted from execution at the hardware-multithreaded processor, the second task will be executed based on the second priority; and

clear the temporary priority of the second task in response to the second task releasing a synchronization object blocking the first task from execution.

25. The computer-readable non-transitory storage medium of claim 24, further comprising instructions that, when executed by the hardware-multithreaded processor, cause the hardware-multithreaded processor to:

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

maintain a run list that identifies tasks that are scheduled for execution at the hardware-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.

26. The computer-readable non-transitory storage medium of claim 25, 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.

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

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