SCHEDULING THREADS IN MULTI-CORE SYSTEMS

• US 20090031317A1
• Filed: 07/24/2007
• Published: 01/29/2009
• Est. Priority Date: 07/24/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, Mark, Hsieh, Bor-ming, GOPALAN, YADHU
• Granted Patent: US 8,544,014 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

Scheduling of threads in a multi-core system is performed using per-processor queues for each core to hold threads with fixed affinity for each core. Cores are configured to pick the highest priority thread among the global run queue, which holds threads without affinity, and their respective per-processor queue. To select between two threads with same priority on both queues, the threads are assigned sequence numbers based on their time of arrival. The sequence numbers may be weighted for either queue to prioritize one over the other.

Claims

1. A method to be executed at least in part in a computing device for scheduling threads in a multi-core processor system, the method comprising:

receiving a thread to be scheduled for processing by the processor system;

determining an affinity status of the received thread;

assigning a sequence number to the thread based on a time of arrival of the thread; and

if the thread has a fixed affinity for a particular core, placing the thread in a per-processor queue for the particular core;

else

placing the thread in a global run queue for all available cores.

2. The method of claim 1, further comprising:

picking the thread from one of the per-processor queue and the global run queue based on a priority of the thread.

3. The method of claim 1, further comprising:

weighting the sequence number assigned to the thread by one of incrementing and decrementing the sequence number if the thread is placed in the per-processor queue.

4. The method of claim 3, further comprising:

if two threads with equal priority are available in the global run queue and the per-processor queue for the particular core, picking the thread with the smaller sequence number for processing.

5. The method of claim 3, wherein the sequence number is weighted based on one from a set of:

a predefined increment, a system condition, a number of currently running applications, an expected processing time of the thread, and a core type.

6. Tie method of claim 1, wherein the thread is received from one of an application and an operating system.

7. The method of claim 6, wherein the application is executed by one of:

the multi-core processing system locally and another processing system remotely.

8. The method of claim 1, further comprising:

providing a result of processing the thread to one of;

a submitting application and an operating system associated with the multi-core processing system.

9. The method of claim 1, wherein the thread is placed in one of the global run queue and the per-processor queue based on a priority assigned to the thread by a submitting application and a priority status of pending threads in the respective queues.

10. A system for scheduling threads in a multi-core processor environment, the system comprising:

a memory;

a processor coupled to the memory, comprising a plurality of distinct processing cores, the processor configured to;

receive a thread to be processed;

determine an affinity status of the received thread;

assign a sequence number to the thread based on a time of arrival of the thread;

weight the sequence number assigned to the thread;

if the thread has a fixed affinity for one of the plurality of cores, place the thread in a per-processor queue for the core; and

if the thread has no affinity, place the thread in a global run queue for all available cores of the plurality of cores.

12. The system of claim 10, wherein the sequence number is weighted by assigning an incremented sequence number to the thread if the thread is to be placed in a per-processor queue compared to a sequence number to be assigned to a thread to be placed to the global run queue.

15. The system of claim 10, wherein a distinct per-processor queue is reserved for each processing core.

16. The system of claim 10, wherein a distinct per-processor queue is reserved for a group of processing cores.

11. The system of claim 11, wherein the sequence number is weighted by assigning a decremented sequence number to the thread if the thread is to be placed in a per-processor queue compared to a sequence number to be assigned to a thread to be placed to the global run queue.

13. The system of claim 11, wherein the processor is further configured to:

pick a thread from one of the per-processor queue and the global run queue based on a priority of the thread and the sequence number of the thread.

14. The system of claim 13, wherein the processor is configured to pick the thread based on its sequence number only if two threads in the global run queue and the per-processor queue have equal priorities.

17. A computer-readable storage medium with instructions encoded thereon for scheduling threads in a multi-core processor system, the instructions comprising:

receiving a thread to be scheduled for processing by the processor system;

determining an affinity status of the received thread;

assigning a sequence number to the thread based on a time of arrival of the thread;

weighting the sequence number assigned to the thread based on one from a set of;

a predefined increment, a system condition, a number of currently running applications, an expected processing time of the thread, and a core type;

if the thread has a fixed affinity for a particular core, placing the thread in a per-processor queue for the particular core based on a priority and the sequence number of the thread; and

if the thread has no affinity, placing the thread in a global run queue for all available cores based on the priority and the sequence number of the thread.

18. The computer-readable storage medium of claim 17, wherein the instructions further comprise:

picking the thread with the smaller sequence number for processing if two threads with equal priority are available in the global run queue and the per-processor queue for the particular core.

19. The computer-readable storage medium of claim 17, wherein the priority of the thread is assigned by a submitting application.

20. The computer-readable storage medium of claim 17, wherein the thread is received from one from a set of:

a local application, a local operating system, a remote application, and a distributed operating system.