US 5,506,987 A · Affinity scheduling of processes on symmetric multiprocessing systems

Abstract

A method of scheduling processes on a symmetric multiprocessing system that maintains process-to-CPU affinity without introducing excessive idle time is disclosed. When a new process is assigned, the process is identified as young and small, given a migtick value and assigned to a specific CPU. If the priority of a process placed on a run queue is above a threshold, the high priority count of the assigned CPU is incremented. At predetermined clock intervals, an interrupt occurs that causes the migtick value of running processes to be decremented. Then each CPU is tested to determine if its high priority count is greater than zero. CPUs having high priority counts greater than zero are tested to determine if any processes having a priority greater than the priority of the running process are assigned. If higher priority processes are assigned to a CPU having assigned processes lying above the threshold, a context switch takes place that results in the higher priority process being run. At regular intervals, a migration deamon is run to load balance the multiprocessor system. First, a large/small process threshold is determined. Then processes whose migtick values are below a migtick threshold (e.g., 0) are identified as old. Old processes then are identified as large or small processes based on their memory usage. Next, a determination is made of whether the small and large process load balances of the system can be improved. If either or both can be improved, the smallest small and/or the smallest large processes are migrated from their assigned CPU to the CPU with, as the case may be, the least large or the least small processes.

Claims24

Dependent claims

A method of affinity scheduling and context switching processes to be run on the CPUs of a multiprocessing system, said method comprising the steps of:

(a) assigning new processes to the CPUs of a multiprocessing system in accordance with a predetermined routine to create an initial affinity between said new processes and the CPUs to which said new processes are assigned, each of said processes having a priority value for context switching purposes whose magnitude is based on the nature of the process;
(b) interrupting the processes running on the CPUs of said multiprocessing system at regular clock intervals;
(c) during an interrupt, for each CPU interrupted, determining if any assigned processes having a priority value above a predetermined assigned process threshold are assigned to the CPU;
(d) during said interrupt or a subsequent interrupt, for each CPU interrupted having assigned processes with a priority value above said predetermined assigned process threshold, determining if any process assigned to the CPU has a priority value that is higher than said predetermined assigned process threshold and higher than the priority value of the process running when the CPU was interrupted;
and
(e) upon returning from said interrupt, switching the context of the process running on each CPU having an assigned process with a priority value above said predetermined assigned process threshold whose priority value is higher than said predetermined assigned process threshold and higher than the priority value of the process running when the CPU was interrupted to the process having the higher priority value.

3 more elements

A method of affinity scheduling and context switching process to be run on the CPUs of a multiprocessing system, said method comprising the steps of:

(a) assigning new processes to the CPUs of a multiprocessing system in accordance with a predetermined routine to create an initial affinity between said new processes and the CPUs to which said new processes are assigned, each of said processes having a priority value for context switching purposes whose magnitude is based on the nature of the process;
(b) assigning a comparable migtick value to each new process as it is assigned to a CPU;
(c) interrupting the process running on the CPUs of said multiprocessing system at regular clock intervals;
(d) during an interrupt for each CPU interrupted, determining if processes having a priority value above a predetermined threshold are assigned to the CPU;
(e) during said interrupt or a subsequent interrupt, for each CPU interrupted having assigned process with a priority value above said predetermined threshold, determining if any process assigned to the CPU has a priority value that is higher than said predetermined threshold and higher than the priority value of the process running when the CPU was interrupted;
(f) upon returning from said interrupt, switching the context of the process running on each CPU having an assigned process with a priority value above said predetermined threshold whose priority value is higher than said predetermined threshold and higher than the priority value of the process running when the CPU was interrupted to the process having the higher priority value;
(g) during said interrupt, decrementing the migtick value of the processes that were running on said interrupted CPUs when said interrupted occurred;
and
(h) after new processes have been assigned a migtick value, performing migration deamon steps at predetermined intervals to load balance said multiprocessing system, said migration deamon steps comprising:
(1) determining whether processes assigned to the CPUs of said multiprocessing system are young or old based on the migtick values of the processes when the migration deamon is run, wherein processes whose migtick values are below a predetermined migtick threshold are identified as old;
(2) determining if the load balance of the multiprocessing system is unbalanced based on a predetermined criterion;
and
(3) improving the load balance of said multiprocessing system if said multiprocessing system is unbalanced by migrating old processes from the CPUs having the most assigned old processes to the CPUs having the least assigned old processes.

10 more elements

A method of affinity scheduling and context switching processes to be run on the CPUs of a multiprocessing system, said method comprising the steps of:

(a) assigning new processes to the CPUS of a multiprocessing system in accordance with a round robin routine wherein the next new process is assigned to the next CPU in the round robin routine in a sequential manner to create an initial affinity between said new processes and the CPUs to which said new processes are assigned, each of said processes having a priority value for context switching purposes whose magnitude is based on the nature of the process;
(b) assigning a comparable migtick value to each new process as it is assigned to a CPU;
(c) interrupting the processes running on the CPUs of said multiprocessing system at regular clock intervals;
(d) during an interrupt, for each CPU interrupted, determining if processes having a priority value above a predetermined threshold are assigned to the CPU;
(e) during said interrupt or a subsequent interrupt, for each CPU interrupted having assigned processes with a priority value above said predetermined threshold, determining if any process assigned to the CPU has a priority value that is higher than said predetermined threshold and higher than the priority value of the process running when the CPU was interrupted;
(f) upon returning from said interrupt, switching the context of the process running on each CPU having an assigned process with a priority value above said predetermined threshold whose priority value is higher than said predetermined threshold and higher than the priority value of the process running when the CPU was interrupted to the process having the higher priority value;
(h) after new processes have been assigned a migtick value, performing migration deamon steps at predetermined intervals to load balance said multiprocessing system, said migration deamon steps comprising:
(1) determining whether processes assigned to the CPUs of said multiprocessing system are young or old based on the migtick values of the processes when the migration deamon is run, wherein processes whose migtick values are below a predetermined migtick threshold are identified as old;
(2) determining if the load balance of the multiprocessing system is unbalanced based on a predetermined criterion;
and
(3) improving the load balance of said multiprocessing system if said multiprocessing system is unbalanced by migrating old processes from the CPUs having the most assigned old processes to the CPUs having the least assigned old processes.

8 more elements

A method of affinity scheduling processes to be run on the CPUs of a multiprocessing system, said method comprising the steps of:

(a) assigning new processes to the CPUs of a multiprocessing system in accordance with a predetermined routine;
(b) assigning a comparable migtick value to each new process as it is assigned;
(c) interrupting the process running on the CPUs of said multiprocessing system at regular clock intervals;
(d) during an interrupt, decrementing the migtick values of the processes that were running on said interrupted CPUs when said interrupt occurred;
and
(e) after new processes have been assigned a migtick value, performing migration deamon steps at predetermined intervals to load balance said multiprocessing system, said migration deamon steps comprising:
(1) determining whether processes assigned to the CPUs of said system are young or old based on their migtick values when the migration deamon is run, wherein processes whose migtick values are below a predetermined migtick threshold are identified as old;
(2) determining if the load balance of the multiprocessing system is unbalanced based on a predetermined criterion;
and
(3) improving the load balance of said multiprocessing system if said multiprocessing system is unbalanced by migrating old processes from the CPUs having the most assigned old processes to the CPUs having the least assigned old processes.

7 more elements

Dependencies are inferred from the claim text.

Affinity scheduling of processes on symmetric multiprocessing systems

Life of this patent

Affinity scheduling of processes on symmetric multiprocessing systems

Life of this patent

Abstract

Claims24