Method for load balancing a per processor affinity scheduler wherein processes are strictly affinitized to processors and the migration of a process from an affinitized processor to another available processor is limited

• US 5,872,972 A
• Filed: 07/05/1996
• Issued: 02/16/1999
• Est. Priority Date: 07/05/1996
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Smith, Kenneth A., Brasche, Kevin R., Boland, Vernon K.
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/676,046
• Time in Patent Office: 956 Days
• Field of Search: 395/680, 395/675, 395/670, 395/672, 395/671
• US Class Current: 718/102
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

An improved affinity process scheduling method for a multiprocessor computer system, wherein a process previously executed on a processor within the computer system is affined to the processor on which it previously executed, and will be scheduled for execution by the affined processor during subsequent requests for execution of the affined process. The improved affinity process scheduling method monitors the length of time the affined process resides on the system run queue awaiting execution by its affined processor; and schedules the affined process for execution with another available processor when the length of time the affined process has been waiting for execution exceeds a predetermined "steal-age" threshold. The improved affinity process scheduling method also monitors the processing load borne by the affined processor, determines therefrom a headroom parameter for the affined processor, the headroom parameter indicating the remaining load capacity of the affined processor; and schedules the affined process for execution with another available processor when the headroom of the affined processor is less than a predetermined "low-headroom" threshold.

Claims

1. An improved affinity process scheduling method for a multiprocessor computer system, whereby a process previously executed on a first processor within said computer system is affined to said first processor and will be scheduled for execution by said first processor during a subsequent request for execution of said affined process, the improvement comprising the steps of:

receiving a request from a second processor for a process to run, said second processor having no currently runnable process which is affined with said second processor;

monitoring the length of time said affined process has been waiting for execution by said first processor when said affined process has been scheduled for execution; and

scheduling said affined process for execution with said second processor when said length of time said affined process has been waiting for execution by said first processor exceeds a predetermined "steal-age" threshold.

2. An improved affinity process scheduling method for a multiprocessor computer system, said affinity process scheduler for scheduling a process previously executed on a first processor to said first processor during a subsequent requests for execution of said process, the improvement comprising the steps of:

receiving a request from a second processor for a process to run, said second processor having no currently runnable process which is affined with said second processor;

monitoring the processing load borne by said first processor and determining therefrom a headroom parameter for said first processor, said headroom parameter indicating the remaining load capacity of said first processor; and

scheduling said affined process for execution with said second processor when the headroom of said first processor is less than a first predetermined "low-headroom" threshold.

3. An improved affinity process scheduling method for a multiprocessor computer system, said affinity process scheduler for scheduling a process previously executed on a specific processor to said specific processor during a subsequent requests for execution of said process, the improvement comprising the steps of:

monitoring the processing load borne by said affined processor and determining therefrom a headroom parameter for said affined processor, said headroom parameter indicating the remaining load capacity of said affined processor; and

scheduling said affined process for execution with another available processor when the headroom of said affined processor is less than a first predetermined "low-headroom" threshold

wherein said step of scheduling said affined process for execution with another available processor occurs when said available processor has headroom greater than a second predetermined "low-headroom" threshold, said second low-headroom threshold being greater than said first low-headroom threshold.

4. A method for scheduling the execution of processes within a multi-processor computer system, the method comprising the steps of:

A. enqueuing processes received by said computer system into a run queue;

B. maintaining a record of previously executed processes and the processors on which said previously executed processes were run;

C. monitoring the length of time each process resides on said run queue;

D. examining the first process in said run queue upon a request from an available processor for a process to run, said available processor having no currently runnable process which is affined with said available processor;

E. examining said record of previously executed processes to determine if said first process has been previously executed on a processor other than said available processor;

F. assigning said first process to said available processor for execution if said first process has not been previously executed on a processor other than said available processor;

G. assigning said first process to said available processor for execution if said first process has been previously executed on a processor other than said available processor and the length of time said first process has been enqueued within said run queue exceeds a predetermined "steal-age" threshold;

H. assigning said first process to said available processor for execution if said first process has been previously executed on a processor other than said available processor and said other processor has headroom below a predetermined "low-headroom" threshold; and

I. repeating steps D through H for a second process in said run queue.

5. The method for scheduling the execution of processes within a multi-processor computer system according to claim 4, wherein:

each process within said run queue has a priority level associated therewith; and

said processes are arranged in said run queue in order of their priority levels.

6. The method for scheduling the execution of processes within a multi-processor computer system according to claim 5, wherein:

said processes having the same priority level are arranged in said run queue in a first-in-time order within said same priority level.

7. In a computer system including a plurality of processor nodes, each processor node including a plurality of tightly-coupled processors and cache memories associated therewith, an improved affinity process scheduling method whereby a process previously executed on a first processor node within said computer system is affined to said first processor node and will be scheduled for execution by said first processor node during a subsequent request for execution of said affined process, the improvement comprising the steps of:

receiving a request from a processor on a second processor node for a process to run, said second processor node having no currently runnable process which is affined with said second processor node;

monitoring the length of time said affined process has been waiting for execution by said first processor node when said affined process has been scheduled for execution; and

scheduling said affined process for execution with said second processor node when said length of time said affined process has been waiting for execution exceeds a predetermined "steal-age" threshold.

8. An improved affinity process scheduling method for a multiprocessor computer system, said affinity process scheduler for scheduling a process previously executed on a first processor node to said first processor node during a subsequent requests for execution of said process, the improvement comprising the steps of:

receiving a request from a processor on a second processor node for a process to run, said second processor node having no currently runnable process which is affined with said second processor node;

monitoring the processing load borne by said first processor node and determining therefrom a headroom parameter for said first processor node, said headroom parameter indicating the remaining load capacity of said first processor node; and

scheduling said affined process for execution with said second processor node when the headroom of said first processor node is less than a first predetermined "low-headroom" threshold.

9. An improved affinity process scheduling method for a multiprocessor computer system, said affinity process scheduler for scheduling a process previously executed on a specific processor node to said specific processor node during a subsequent requests for execution of said process, the improvement comprising the steps of:

monitoring the processing load borne by said affined processor node and determining therefrom a headroom parameter for said affined processor node, said headroom parameter indicating the remaining load capacity of said affined processor node; and

scheduling said affined process for execution with another available processor node when the headroom of said affined processor node is less than a first predetermined "low-headroom" threshold

wherein said step of scheduling said affined process for execution with another available processor node occurs when said available processor node has headroom greater than a second predetermined "low-headroom" threshold, said second low-headroom threshold being greater than said first low-headroom threshold.