Method and system for managing the execution of threads and the processing of data

• US 7,246,353 B2
• Filed: 06/12/2002
• Issued: 07/17/2007
• Est. Priority Date: 06/12/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Forin, Alessandro, Helander, Johannes V., Pham, Paul T.
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Tang; Kenneth
• Application Number:
  US10/167,559
• Publication Number:
  US 20030233392A1
• Time in Patent Office: 1,861 Days
• Field of Search: 718/100, 718/102
• US Class Current: 718/100
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method and system for managing the execution of threads uses a single scheduler for both threads and work items. Objects representing the threads and the work items are either maintained in separate queues or are stored together in a single queue. Each thread object or work item object may contain information that allows the scheduler to determine what order to execute the corresponding threads or to process the corresponding work items.

Claims

1. A method for managing the execution of threads and the processing of data, the method comprising:

on a computing system comprising one or more processors;

representing each of a plurality of threads by a respective thread object, wherein each thread of the plurality is a point of execution of a program on a processor of the one or more processors;

representing each of a plurality of work items by a respective work item object, wherein each work item comprises data that is to be used by a processor of the one or more processors to execute a block of computer executable code;

inserting each thread object into a first queue;

inserting each work item object into a second queue;

reordering both the thread objects of the first queue and the work item objects of the second queue using a single scheduler; and

wherein the reordering step comprises using the single scheduler for querying each of the plurality of thread objects and each of the plurality of work item objects to determine how each of the plurality of thread objects and each of the plurality of work item objects is supposed to be ordered in the respective first and second queues.

2. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1.

3. The method of claim 1, wherein the reordering step further comprises:

the single scheduler referencing a pointer in each of the plurality of thread objects or in each of the plurality of work item objects to determine how the thread objects and work item objects are to be sorted in the respective first and second queues.

4. The method of claim 1 wherein the reordering step further comprises:

the single scheduler determining the points in the first queue at which each of the plurality of thread objects is to be placed; and

the single scheduler determining the points in the second queue at which each of the plurality of work item objects is to be placed,

wherein the inserting steps are performed based on the results of the determining steps.

5. The method of claim 1, wherein the reordering step further comprises:

the single scheduler referencing a scheduling value for each of the thread objects in the first queue;

the single scheduler comparing the scheduling values of each of the thread objects to one another;

based on the comparing step, the single scheduler sorting the thread objects.

6. The method of claim 1, wherein the reordering step further comprises:

the single scheduler referencing a scheduling value for each of the work item objects in the second queue;

the single scheduler comparing the scheduling values of each of the work item objects to one another; and

based on the comparing step, the scheduler sorting the work item objects.

7. A method for managing the execution of threads and the processing of data, the method comprising:

on a computing system comprising one or more processors;

representing each of a plurality of threads by a thread object, wherein each thread of the plurality of threads is a point of execution of a program on a processor of the one or more processors;

representing each of a plurality of work items with a work item object, wherein each work item of the plurality of work items comprises a logical grouping of data that is to be used by a processor of the one or more processors to execute a block of computer-executable code;

inserting each thread object and each work item object into a queue, the queue being the same for both the thread objects and the work item objects; and

ordering the thread objects and the work item objects in the queue by sorting the thread objects and work item objects as they are being inserted into the queue.

8. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 7.

9. The method of claim 7, wherein the ordering step further comprises sorting the thread objects and work item objects as they are being extracted from the queue.

10. The method of claim 7, wherein the ordering step further comprises querying each of the thread objects and work item object to determine an ordering criteria for ordering each of the thread objects and work item objects.

11. The method of claim 7, wherein the ordering step further comprises determining the priority level of at least one of the thread or work item objects and assigning a position in the queue to the thread or work item object based on the determining step.

12. The method of claim 7, wherein the ordering step further comprises determining an execution time of at least one of the thread objects or work item object and assigning a position in the queue to the thread or work item object based on the determining step.

13. A computer-readable storage medium having stored thereon data comprising:

one or more queues;

a plurality of thread objects, each thread object representing a thread of execution of a computer program; and

a plurality of work item objects, each work item object representing a logical grouping of data that is to be operated on by one or more code sections of one, or more computer programs;

wherein the plurality of thread objects and the plurality work item objects are stored together in the same queue of the one or more queues;

wherein at least one of the thread objects has an execution time value that indicates when the thread obiect should be removed from the queue; and

wherein at least one of the work item objects has an execution time value that indicates when the work item obiect should be removed from the queue.

14. The computer readable medium of claim 13, wherein each of the thread objects has a scheduling value that indicates the order in which the thread object is to be removed from the queue.

15. The computer-readable medium of claim 13, wherein each of the work item objects has a scheduling value that indicates the order in which the work item object is to be removed from the queue.

16. The computer readable medium of claim 13, wherein at least one of the thread objects has a priority value that, when compared to the priority value of at least one other thread object indicates the order in which the thread object should be removed from the queue.

17. The computer readable medium of claim 13, wherein at least one of the work item objects has a disk block identifier that, when compared to the disk block number of at least one other work item object, indicates the order in which the work item object should be removed from the queue.

18. The computer readable medium of claim 13, wherein each of the work item objects include a reference to a computational block of executable code that receives the logical grouping of data represented by the work item object as an input.

19. The computer readable medium of claim 13, wherein each of the thread objects includes a reference to a function that enables a computer processor to switch context to the thread represented by the thread object.

20. A system for managing the execution of threads and the processing of data, the system comprising:

a means for executing a sequence of instructions of one or more computer programs, wherein when the instructions of a particular program are being executed, there is, at any given time, a thread of execution of the program representing the point in the sequence of instructions at which the executing means is executing an instruction, wherein at least one of the one or more programs is divided into computational blocks in which each computational block;

receives a logical grouping of data as input;

performs operations on the data contained in the logical grouping; and

passes the results of the operations in the form of another logical grouping of data to the next computational block or outputs the results;

a computer-readable storage medium having stored thereon a queue comprising;

a thread object representing a saved state of the thread of execution, wherein the thread object waits in the queue until a processor becomes available to resume the thread of execution from the saved state;

a work item object representing the logical grouping of data, wherein the work item object waits in the queue until a processor becomes available to execute the computational block that is to receive the logical grouping of data as input;

wherein the work item obiect and the thread obiect are among a plurality of objects in the queue; and

a means for ordering the plurality of objects according to an ordering criteria.

21. The system of claim 20, wherein the executing means comprises a processor of a computer.

22. The system of claim 20, further comprising a computer-readable disk for holding data for use by the executing means, wherein the ordering criteria is based, at least in part, on the amount of movement required on the part of the computer-readable disk.

23. The system of claim 20, wherein the ordering criteria is based, at least in part, on time constraints associated with at least some of the plurality of objects.

24. The system of claim 20, wherein the ordering criteria is based, at least in part, on priority scores associated with at least some of the plurality of objects.

25. The system of claim 20, further comprising a computer-readable medium having stored thereon at least one data-centric program that includes the computational blocks.

26. The system of claim 20, further comprising a computer-readable medium having stored thereon at least one thread-centric program that includes the sequence of instructions.