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

Claim 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.

Claim 7

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.

Claim 8

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.