# US 8,544,014 B2 · Scheduling threads in multi-core systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,544,014 B2 - Document ID: US8544014B2 - Status: Granted - Kind: B2 - Application number: 11/782,000 - Filed: 2007-07-24 - Published: 2009-01-29 - Granted: 2013-09-24 - Earliest claimed: 2007-07-24 - Assignees: Microsoft Corporation - Applicants: Yadhu Gopalan; Bor-ming Hsieh; Mark Miller - Inventors: Yadhu Gopalan; Bor-ming Hsieh; Mark Miller - Web page: https://patentgrep.com/patent/US8544014B2 ## CPC - G06F 9/5033: {considering data affinity} - G06F 2209/5021: Priority - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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 multi-core processor system; determining whether the received thread has a fixed affinity for a particular core of the multi-core processor system; assigning a sequence number to the received thread based on time of arrival of the thread when the thread is determined to not have a fixed affinity for the particular core and assigning a sequence number to the received thread based on time of arrival plus an offset when the thread is determined to have a fixed affinity; placing the thread in a per-processor queue for the particular core when the thread is determined to have a fixed affinity for the particular core; placing the thread in a global run queue for all available cores of the multi-core processor system when the thread is determined to not have a fixed affinity for the particular core; and processing the threads from the global run queue and the per-processor queue according to the assigned sequence number. ### Claim 2 (depends on 1) The method of claim 1, wherein the assigning the sequence number to the received thread based on time of arrival plus the offset when the thread is determined to have a fixed affinity comprises incrementing and decrementing the sequence number by a pre-defined fixed amount relative to the threads placed in the global run queue when the thread is placed in the per-processor queue. ### Claim 3 (depends on 2) The method of claim 2, 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 a smaller weighted sequence number for processing. ### Claim 4 (depends on 2) The method of claim 2, wherein the assigning the sequence number to the received thread based on time of arrival plus the offset when the thread is determined to have a fixed affinity further comprises adding the offset based on one from a system condition, a number of currently running applications, an expected processing time of the thread, and a core type. ### Claim 5 (depends on 1) The method of claim 1, wherein the thread is received from one of an application and an operating system. ### Claim 6 (depends on 5) The method of claim 5, wherein the application is executed by one of the multi-core processor system locally and another processing system remotely. ### Claim 7 (depends on 1) 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 processor system. ### Claim 8 A system for scheduling threads in a multi-core processor environment, the system comprising: a memory; a multi-core processor coupled to the memory, comprising a plurality of distinct processing cores, the multi-core processor configured to: receive a thread to be to be scheduled for processing by the multi-core processor; determine whether the received thread has a fixed affinity for a particular core of the multi-core processor; assign a sequence number to the received thread based on time of arrival of the thread when the thread is determined to not have a fixed affinity for the particular core and assigning a sequence number to the received thread based on time of arrival plus an offset when the thread is determined to have a fixed affinity; place the thread in a per-processor queue for the particular core when the thread has a fixed affinity for the particular core of the multi-core processor; and place the thread in a global run queue for all available cores of the plurality of cores of the multi-core processor when the thread is determined to not have a fixed affinity for the particular core; and processing the threads from the global run queue and the per-processor queue according to the assigned sequence number. ### Claim 9 (depends on 8) The system of claim 8, wherein the assigning the sequence number to the received thread based on time of arrival plus the offset when the thread is determined to have a fixed affinity comprises incrementing and decrementing the sequence number by a pre-defined fixed amount relative to the threads placed in the global run queue when the thread is placed in the per-processor queue. ### Claim 10 (depends on 8) The system of claim 8, wherein the processor is configured to pick the thread based on the sequence number when two threads in the global run queue and the pre-processor queue have equal priorities. ### Claim 11 (depends on 8) The system of claim 8, wherein a distinct per-processor queue is reserved for each processing core. ### Claim 12 (depends on 8) The system of claim 8, wherein a distinct per-processor queue is reserved for a group of processing cores. ### Claim 13 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 multi-core processor system; determining whether the received thread has a fixed affinity for a particular core of the multi-core processor system; assigning a sequence number to the received thread based on time of arrival of the thread when the thread is determined to not have a fixed affinity for the particular core and assigning a sequence number to the received thread based on time of arrival plus an offset when the thread is determined to have a fixed affinity; placing the thread in a per-processor queue for the particular core when the thread is determined to have a fixed affinity for the particular core; placing the thread in a global run queue for all available cores based on the when the thread is determined to not have a fixed affinity for the particular core; and processing the threads from the global run queue and the per-processor queue according to assigned sequence number. ### Claim 14 (depends on 13) The computer-readable storage medium of claim 13, wherein the assigning the sequence number to the received thread based on time of arrival plus the offset when the thread is determined to have a fixed affinity further comprises adding the offset based on one from a set of: a system condition, a number of currently running applications, an expected processing time of the thread, and a core type. ### Claim 15 (depends on 13) The computer-readable storage medium of claim 13, 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.