Method and apparatus to perform task scheduling

• US 7,594,228 B2
• Filed: 09/23/2003
• Issued: 09/22/2009
• Est. Priority Date: 09/23/2003
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Numonyx BV (Micron Technology, Inc.)
• Inventors: Lam, Siu H.
• Primary Examiner(s): Nguyen; Van H
• Assistant Examiner(s): To; Jennifer N
• Application Number:
  US10/669,309
• Publication Number:
  US 20050066328A1
• Time in Patent Office: 2,191 Days
• Field of Search: 718100-108, 370/431, 370229-230, 709201-226
• US Class Current: 718/102
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method and apparatus to perform task scheduling are described. Tasks are assigned by receiving a request to execute a task on one of multiprocessors. The type of task is determined for the task. A processor task value is used to select the proper processor and the task is assigned.

Claims

1. A method to assign tasks, comprising:

receiving a request to execute a task on one of a plurality of processors;

determining a task type for said task;

retrieving a processor task value of said task type for each processor, said processor task value representing a number of other task types affected by assigning said task to a processor;

selecting a processor from said plurality of processors based on said processor task values; and

assigning said task to said selected processor; and

updating said processor task values for each task type and each processor, wherein said updating comprises;

retrieving a first resource cost value for a first task type;

retrieving a second resource cost value for a second task type;

generating a modulo of said first resource cost value divided by said second resource cost value to form a first relative resource value for said first task type relative to said second task type;

determining a remaining resource value for said processor;

generating a modulo of said remaining resource value divided by said second resource cost value to form a second spare resource value for said second task type;

comparing said first relative resource value to said second spare resource value; and

updating said processor task value for said first task type in accordance with said comparison.

2. The method of claim 1, wherein said processor task value for said first task type is incremented by one if said first relative resource value is less than said second spare resource value.

3. The method of claim 1,

wherein said processor task value for said second task type is incremented if said second relative resource value is greater than said first spare resource value.

4. The method of claim 1, wherein said selecting comprises:

comparing said processor task values for said processors; and

selecting a processor having a highest processor task value.

5. A method to assign tasks, comprising:

receiving a request to execute a task on one of a plurality of processors;

determining a task type for said task;

retrieving a processor task value of said task type for each processor, said processor task value representing a number of other task types affected by assigning said task to a processor;

selecting a processor from said plurality of processors based on said processor task values; and

assigning said task to said selected processor; and

updating said processor task values for each task type and each processor, wherein said updating comprises;

retrieving a first resource cost value for a first task type;

retrieving a second resource cost value for a second task type;

generating a modulo of said second resource cost value divided by said first resource cost value to form a second relative resource value for said second task type relative to said first task type;

determining a remaining resource value for said processor;

generating a modulo of said remaining resource value divided by said first resource cost value to form a first spare resource value for said first task type;

comparing said second relative resource value to said first spare resource value; and

updating said processor task value for said second task type in accordance with said comparison.

6. The method of claim 5, wherein said processor task value for said second task type is incremented by one if said second relative resource value is less than said first spare resource value.

7. An article, comprising:

a storage medium;

said storage medium including stored instructions that, when executed by a processor, result in assigning tasks by receiving a request to execute a task on one of a plurality of processors, determining a task type for said task, retrieving a processor task value of said task type for each processor, selecting a processor from said plurality of processors based on said processor task values, assigning said task to said selected processor, said processor task value representing a number of other task types affected by assigning said task to said processor and updating said processor task values for each task type and each processor,

wherein the stored instructions, when executed by a processor, further result in said updating by retrieving a first resource cost value for a first task type, retrieving a second resource cost value for a second task type, generating a modulo of said first resource cost value divided by said second resource cost value to form a first relative resource value for said first task type relative to said second task type, determining a remaining resource value for said processor, generating a modulo of said remaining resource value divided by said second resource cost value to form a second spare resource value for said second task type, comparing said first relative resource value to said second spare resource value, and updating said processor task value for said first task type in accordance with said comparison.

8. The article of claim 7, wherein the stored instructions, when executed by a processor, further result in said updating by incrementing said processor task value for said second task type if said second relative resource value is greater than said first spare resource value.

9. The article of claim 7, wherein the stored instructions, when executed by a processor, further result in said selecting by comparing said processor task values for said processors, and selecting a processor having a highest processor task value.