Affinity scheduling of processes on symmetric multiprocessing systems

• US 5,506,987 A
• Filed: 03/24/1994
• Issued: 04/09/1996
• Est. Priority Date: 02/01/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Orbits, David A., Butts, H. Bruce Jr., Abramson, Kenneth D.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US08/217,127
• Time in Patent Office: 747 Days
• Field of Search: 395/200, 395/650, 395/230, 395/230.3, 395/700, 395/650
• US Class Current: 718/103
• CPC Class Codes: G06F 9/5033 considering data affinity

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.

Claims

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

7. The method claimed in claim 1 wherein the predetermined routine used to assign new processes to the CPUs of a multiprocessing system is a round robin routine wherein the next new process is assigned to the next CPU in the round robin routine in a sequential manner.

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

3. The method claimed in claim 2 wherein said predetermined criterion is based on the memory requirements of the processes assigned to the CPUs of said multiprocessing system.

4. The method claimed in claim 3 wherein said old processes are sorted into large and small processes based on the memory requirements of said processes prior to determining if the load balance of the multiprocessing system is unbalanced.

5. The method claimed in claim 4 wherein the step of determining if the load balance of the multiprocessing system is unbalanced comprises the substeps of determining if the small process load balance of the multiprocessing system can be improved and if the large process load balance of the multiprocessing system can be improved;

and wherein the step of improving the load balance of the multiprocessing system comprises migrating old small processes from the CPUs having the most assigned old small processes to the CPUs having the least assigned old small processes and migrating old large processes from the CPUs having the most assigned old large processes to the CPUs having the least assigned old large processes.

6. The method claimed in claim 5 wherein the smallest old small process is the first of the old small processes to be migrated and wherein the smallest old large process is the first of the old large processes to be migrated.

23. The method in claim 2, wherein when said old processes are migrated, the migtick values of said migrated old processes are reassigned to values above said predetermined migtick threshold so that said migrated old processes become young based on their reassigned migtick values.

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

9. The method claimed in claim 8 wherein said predetermined criterion is based on the memory requirements of the processes assigned to the CPUs of said multiprocessing system.

10. The method claimed in claim 9 wherein said old processes are sorted into large and small processes based on the memory requirements of said processes prior to determining if the load balance of the multiprocessing system is unbalanced.

11. The method claimed in claim 10 wherein the step of determining if the load balance of the multiprocessing system is unbalanced comprises the steps of determining if the small process load balance of the multiprocessing system can be improved and if the large process load balance of the multiprocessing system can be improved;

and wherein the step of improving the load balance of the multiprocessing system comprises migrating old small processes from the CPUs having the most assigned old small processes to the CPUs having the least assigned old small processes and migrating old large processes from the CPUs having the most assigned old large processes to the CPUs having the least assigned old large processes.

12. The method claimed in claim 11 wherein the smallest old small process is the first of the old small processes to be migrated and wherein the smallest old large process is the first of the old large processes to be migrated.

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

14. The method claimed in claim 13 wherein said predetermined criterion is based on the memory requirements of the processes assigned to the CPUs of said multiprocessing system.

15. The method claimed in claim 14 wherein said old processes are sorted into large and small processes based on the memory requirements of said processes prior to determining if the load balance of the multiprocessing system is unbalanced.

16. The method claimed in claim 15 wherein the step of determining if the load balance of the multiprocessing system is unbalanced comprises the steps of determining if the small process load balance of the multiprocessing system can be improved and if the large process load balance of the multiprocessing system can be improved;

and wherein the step of improving the load balance of the multiprocessing system comprises migrating old small processes from the CPUs having the most assigned old small processes to the CPUs having the least assigned old small processes and migrating old large processes from the CPUs having the most assigned old large processes to the CPUs having the least assigned old large processes.

17. The method claimed in claim 16 wherein the smallest old small process is the first of the old small processes to be migrated and wherein the smallest old large process is the first of the old large processes to be migrated.

18. The method claimed in claim 13 wherein the predetermined routine used to assign new processes to the CPUs of a multiprocessing system is a round robin routine wherein the next new process is assigned to the next CPU in the round robin routine in a sequential manner.

19. The method claimed in claim 18 wherein said predetermined criterion is based on the memory requirements of the processes assigned to the CPUs of said multiprocessing system.

20. The method claimed in claim 19 wherein said old processes are sorted into large and small processes based on the memory requirements of said processes prior to determining if the load balance of the multiprocessing system is unbalanced.

21. The method claimed in claim 20 wherein the step of determining if the load balance of the multiprocessing system is unbalanced comprises the steps of determining if the small process load balance of the multiprocessing system can be improved and if the large process load balance of the multiprocessing system can be improved;

and wherein the step of improving the load balance of the multiprocessing system comprises migrating old small processes from the CPUs having the most assigned old small processes to the CPUs having the least assigned old small processes and migrating old large processes from the CPUs having the most assigned old large processes to the CPUs having the least assigned old large processes.

22. The method claimed in claim 21 wherein the smallest old small process is the first of the old small processes to be migrated and wherein the smallest old large process is the first of the old large processes to be migrated.

24. The method of claim 13, wherein when said old processes are migrated, the migtick values of said migrated old processes are reassigned to values above said predetermined migtick threshold so that said migrated old processes become young based on their reassigned migtick values.