Patent US1517549A successfully refreshed from Google Patents.
US5506987A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Affinity scheduling of processes on symmetric multiprocessing systems
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-03-24
•
Granted: 1996-04-09
•
Expires: 2014-03-24
Abstract
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.
Inventors
- 👤 Kenneth D. Abramson
- 👤 H. Bruce Butts, Jr.
- 👤 David A. Orbits
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 20:31
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5027; G06F9/5033
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
253 words
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.
Claim 2
Independent Claim
253 words
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.
Claim 3
Independent Claim
408 words
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.
Claim 4
Independent Claim
408 words
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.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
38 words
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.
Claim 7
Dependent Claim
116 words
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.
Claim 8
Dependent Claim
41 words
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.
Claim 9
Dependent Claim
47 words
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.
Claim 10
Independent Claim
406 words
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.
Claim 11
Independent Claim
406 words
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.
Claim 12
Dependent Claim
27 words
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.
Claim 13
Dependent Claim
38 words
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.
Claim 14
Dependent Claim
116 words
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.
Claim 15
Dependent Claim
41 words
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.
Claim 16
Independent Claim
216 words
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.
Claim 17
Independent Claim
216 words
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.
Claim 18
Dependent Claim
27 words
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.
Claim 19
Dependent Claim
38 words
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.
Claim 20
Dependent Claim
116 words
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.
Claim 21
Dependent Claim
41 words
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.
Claim 22
Dependent Claim
47 words
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.
Claim 23
Dependent Claim
27 words
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.
Claim 24
Dependent Claim
38 words
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.
Claim 25
Dependent Claim
116 words
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.
Claim 26
Dependent Claim
41 words
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.
Claim 27
Dependent Claim
43 words
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.
Claim 28
Dependent Claim
43 words
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.
References Cited (Backward Citations)
US3702006A
Cited
US4432051A
Cited
US4318174A
Cited
US4387427A
Cited
US4394727A
Cited
US4638427A
Cited
US4809157A
Cited
US4868739A
Cited
US4914570A
Cited
US5109512A
Cited
US5185861A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-09 | 1999-10-09 | 2000-04-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-09 | 2003-10-09 | 2004-04-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-09 | 2007-10-09 | 2008-04-09 | $7700.00 | Window Closed / Lapsed |