TASK-LEVEL THREAD SCHEDULING AND RESOURCE ALLOCATION

• US 20090165007A1
• Filed: 12/19/2007
• Published: 06/25/2009
• Est. Priority Date: 12/19/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aghajanyan, Souren
• Application Number:
  US11/959,464
• Publication Number:
  US 20090165007A1
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Task schedulers endeavor to share computing resources, such as the CPU, among many threads. However, the task scheduler may be unable to identify the resources that will be utilized by a thread, and may allocate resources inefficiently due to incorrect predictions of resource utility. Task scheduling may be improved by identifying the rate determining factors for various thread tasks comprising a thread, e.g., a first task that is rate-limited by a communications bus, a second task that is rate-limited by the CPU, and a third task that is rate-limited by a communications network. If the instructions are so identified, the operating system may be able to schedule tasks and to allocate resources based on the resources to be utilized by the threads, which may improve efficiency and computing performance.

Claims

1. A method of indicating a rate determinant of a thread task, the method comprising:

identifying at least one rate determinant of the thread task, and

associating with the thread task at least one rate determinant indicator representing one of the rate determinants of the thread task.

2. The method of claim 1, the at least one rate determinant comprising at least one of a central processing unit, a graphics processing unit, a communications bus, a communications network, a device, and a second thread task.

3. The method of claim 1, the identifying comprising:

identifying at least one rate determinant attribute associated with an instruction block of the thread task.

4. The method of claim 3, the instruction block comprising a source code block comprising at least one of a function, a portion of a function, a function delegate, a lambda expression, and a portion of an expression tree.

5. The method of claim 3, the rate determinant attribute specified for the instruction block by at least one of a software developer, an integrated development environment, and a compiler.

6. The method of claim 3, the rate determinant attribute comprising a request for a share of a resource comprising the rate determinant.

7. The method of claim 1, the identifying comprising:

profiling at least one instruction of the thread task to identify at least one rate determinant of the thread task.

8. The method of claim 1, the identifying comprising:

monitoring resources utilized during performance of the thread task.

9. The method of claim 1, comprising:

determining at least one rate determinant during a first performance a thread task, and

storing at least one rate determinant indicator associated with the thread task and determined during the first performance of the thread task; and

the identifying comprising;

retrieving at least one stored rate determinant indicator associated with the thread task.

10. A computer-readable medium comprising processor-executable instructions configured to perform a method of indicating a rate determinant of a thread task, the method comprising:

identifying at least one rate determinant of the thread task, and

associating with the thread task at least one rate determinant indicator representing one of the rate determinants of the thread task.

11. A method of assigning a scheduling priority to a thread task in a thread executing on a computer system, the method comprising:

identifying at least one rate determinant represented by at least one rate determinant indicator associated with the thread task,

detecting availability of the at least one rate determinant of the thread task, and

assigning the scheduling priority to the thread proportional to the availability of the at least one rate determinant.

12. The method of claim 11, the at least one rate determinant comprising at least one of a central processing unit, a graphics processing unit, a communications bus, a communications network, a device, and a second thread task.

13. The method of claim 11, comprising:

determining at least one rate determinant during a first performance a thread task, and

storing at least one rate determinant indicator associated with the thread task and determined during the first performance of the thread task; and

the identifying comprising;

retrieving at least one stored rate determinant indicator associated with the thread task.

14. The method of claim 13, comprising:

seeking an unallocated resource share of a resource comprising the rate determinant associated with the thread task; and

upon identifying an unallocated resource share, allocating the resource share to the thread task.

15. The method of claim 14, comprising:

upon identifying an unallocated resource share of a processor for a thread task having a processor rate determinant, assigning an affinity of a processor for the thread task.

16. The method of claim 14, comprising:

upon identifying an unallocated resource share of a processor comprising the rate determinant for a thread task, allocating at least two contiguous shares of the processor to the thread task.

17. The method of claim 14, comprising:

upon detecting at least one of a completion, a failure, and a user termination of the thread task, deallocating the resource share allocated to the thread task.

18. The method of claim 14, comprising:

upon failing to identify an unallocated resource share of the resource, suspending the thread task; and

upon detecting availability of an unallocated resource share of the resource;

unsuspending a suspended thread task having a rate determinant associated with the resource, and

allocating the unallocated resource share to the unsuspended thread task.

19. The method of claim 18, comprising:

upon suspending a thread task, placing the thread task in a suspended thread task queue associated with the resource;

and the unsuspending comprising;

upon detecting availability of an unallocated resource share of the resource;

unsuspending a suspended thread task in the suspended thread task queue associated with the resource, and

removing the unsuspended thread task from the suspended thread task queue.

20. The method of claim 19, the thread tasks having an ordered priority indicator, and the suspended thread task queue comprising a priority queue based on the ordered priority indicator of the suspended thread tasks.