Dynamic resource allocation scheme for distributed heterogeneous computer systems

• US 5,031,089 A
• Filed: 12/30/1988
• Issued: 07/09/1991
• Est. Priority Date: 12/30/1988
• Status: Expired due to Fees

• Current Assignee: National Aeronautics and Space Administration (Government of the United States of America), United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: The United States of America As Represented By The Secretary of Agriculture
• Inventors: Silvester, John A., Liu, Howard T.
• Primary Examiner(s): Popek, Joseph A.
• Assistant Examiner(s): Rudolph, Rebecca L.
• Application Number:
  US07/292,124
• Time in Patent Office: 921 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/281.3, 364/281, 364/281.6, 364/281.8, 364/975.5
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

In a distributed heterogeneous computer system having a plurality of computer nodes each operatively connected through a network interface to a network to provide for communications and transfers of data between the nodes and wherein the nodes each have a queue for containing jobs to be performed, an improvement for dynamically reallocating the system'"'"'s resources for optimized job performance. There is first logic at each node for dynamically and periodically calculating and saving a workload value as a function of the number of jobs on the node'"'"'s queue. Second logic is provided at each node for transfering the node'"'"'s workload value to other nodes on the network at the request of the other nodes. Finally, there is third logic at each node operable at the completion of each job. The third logic includes, logic for checking the node'"'"'s own workload value, logic for polling all the other nodes for their workload value if the checking node'"'"'s workload value is below a preestablished value indicating the node as being underutilized and available to do more jobs, logic for checking the workload values of the other nodes as received, and logic for transfering a job from the queue of the other of the nodes having the highest workload value over a preestablished value indicating the other of the nodes as being overburdened and requiring job relief to the que of the checking node. The third logic is also operable periodically when the node is idle.

Claims

1. In a distributed heterogeneous computer system having a plurality of computer nodes each operatively connected through a network interface to a network to provide for communications and transfers of data between the nodes and wherein the nodes each have a queue for containing jobs to be performed, the improvement for dynamically reallocating the system'"'"'s resources for optimized job performance comprising:

a) means at each node for dynamically and periodically calculating and saving a workload value as a function of the number of jobs on the node'"'"'s queue;

b) means at each node for transfering the node'"'"'s said workload value to other nodes on the network at the request of said other nodes; and

,

c) means at each node operable at the completion of each job,

c1) for checking the node'"'"'s own said workload value,

c2) for polling all the other nodes for their said workload value if the checking node'"'"'s said workload value is below a pre-established value indicating the node as being underutilized and available to do more jobs,

c3) for checking the said workload values of the other nodes as received, and

c4) for transfering a job from the queue of the other of the nodes having the highest said workload value over a pre-established value indicating said other of the nodes as being overburdened and requiring job relief to the queue of the checking node.

2. The improvement to a distributed heterogeneous computer system of claim 1 and additionally comprising means at each node periodically operable when the node is idle:

a) for checking the node'"'"'s own said workload value;

b) for polling all the other nodes for their said workload value if the checking node'"'"'s said workload value is below a pre-established value indicating the node as being underutilized and available to do more jobs;

c) for checking the said workload values of the other nodes as received; and

,

d) for transfering a job from the queue of the other of the nodes having the highest said workload value over a pre-established value indicating said other of the nodes as being overburdened and requiring job relief to the queue of the checking node.

3. The improvement to a distributed heterogeneous computer system of claim 1 wherein:

said means at each node for dynamically and periodically calculating and saving a workload value as a function of the number of jobs on the node'"'"'s queue comprises means for dividing the number of jobs on the node'"'"'s queue by the service rate of the node.

4. The improvement to a distributed heterogeneous computer system of claim 1 wherein:

a) the jobs to be performed by the nodes are assigned priority levels; and

,

b) said polling of all the other nodes for their said workload value by a node is accomplished by the node as a job at the highest priority level.

5. A distributed heterogeneous computer system having dynamic resource allocation comprising:

a) network means for providing a communications path for computer;

b) a plurality of computer nodes each operatively connected through a network interface to said network means whereby to communicate and transfer data between said nodes, said nodes each having a queue for containing jobs to be performed;

c) means at each said node for dynamically and periodically calculating and saving a workload value as a function of the number of jobs on said node'"'"'s queue;

d) means at each node for transfering said node'"'"'s said workload value to other nodes over said network at the request of said other nodes; and

,

e) means at each node operable at the completion of each job,

e1) for checking said node'"'"'s own said workload value,

e2) for polling all the other said nodes for their said workload value if the checking node'"'"'s said workload value is below a pre-established value indicating said node as being underutilized and available to do more jobs,

e3) for checking the said workload values of the other said nodes as received, and

e4) for transfering a job from said queue of the other of said nodes having the highest said workload value over a pre-established value indicating said other of said nodes as being overburdened and requiring job relief to said queue of the checking node.

6. The distributed heterogeneous computer system of claim 5 and additionally comprising means at each said node periodically operable when said node is idle:

a) for checking said node'"'"'s own said workload value;

b) for polling all the other said nodes for their said workload value if the checking node'"'"'s said workload value is below a pre-established value indicating said node as being underutilized and available to do more jobs;

c) for checking the said workload values of the other said nodes as received; and

,

d) for transfering a job from said queue of the other of said nodes having the highest said workload value over a pre-established value indicating said other of said nodes as being overburdened and requiring job relief to said queue of the checking node.

7. The distributed heterogeneous computer system of claim 5 wherein:

said means at each node for dynamically and periodically calculating and saving a workload value as a function of the number of jobs on said node'"'"'s queue comprises means for dividing the number of jobs on said node'"'"'s queue by the service rate of said node.

8. The improvement to a distributed heterogeneous computer system of claim 5 wherein:

a) the jobs to be performed by said nodes are assigned priority levels; and

,

b) said polling of all the other nodes for their said workload value by a node is accomplished by said node as a job at the highest priority level.

9. In a distributed heterogeneous computer system having a plurality of computer nodes each operatively connected through a network interface to a network to provide for communications and transfers of data between the nodes and wherein the nodes each have a queue for containing jobs to be performed, the method of operation for dynamically reallocating the system'"'"'s resources for optimized job performance comprising the steps of:

a) at each node, dynamically and periodically calculating and saving a workload value as a function of the number of jobs on the node'"'"'s queue;

b) transfering the node'"'"'s workload value to other nodes on the network at the request of the other nodes; and

,

c) at each node at the completion of each job,

c1) checking the node'"'"'s own workload value,

c2) polling all the other nodes for their workload value if the checking node'"'"'s workload value is below a pre-established value indicating the node as being underutilized and available to do more jobs,

c3) checking the workload values of the other nodes as received, and

c4) transfering a job from the queue of the other of the nodes having the highest the workload value over a pre-established value indicating the other of the nodes as being overburdened and requiring job relief to the queue of the checking node.

10. The method of operating a distributed heterogeneous computer system of claim 9 and when the node is idle additionally comprising the steps of:

checking the node'"'"'s own workload value;

b) polling all the other nodes for their workload value if the checking node'"'"'s the workload value is below a pre-established value indicating the node as being underutilized and available to do more jobs;

c) checking the workload values of the other nodes as received; and

,

d) transfering a job from the queue of the other of the nodes having the highest workload value over a pre-established value indicating the other of the nodes as being overburdened and requiring job relief to the queue of the checking node.

11. The method of operating a distributed heterogeneous computer system of claim 9 wherein said step of dynamically and periodically calculating and saving a workload value as a function of the number of jobs on the node'"'"'s queue comprises the step of:

dividing the number of jobs on the node'"'"'s queue by the service rate of the node.

12. The method of operating a distributed heterogeneous computer system of claim 9 wherein the jobs to be performed by the nodes are assigned priority levels and:

said step of polling of all the other nodes for their workload value by a node is accomplished by the node as a job at the highest priority level.

13. In a distributed heterogeneous computer system having a plurality of computer nodes each operatively connected through a network interface to a network to provide for communications and transfers of data between the nodes and wherein the nodes each have a queue for containing jobs to be performed, the improvement for dynamically reallocating the system'"'"'s resources for optimized job performance comprising:

a) first logic means at each node for dynamically and periodically calculating and saving a workload value as a function of the number of jobs on the node'"'"'s queue;

b) second logic means at each node for transfering the node'"'"'s said workload value to other nodes on the network at the request of said other nodes; and

,

c) third logic means at each node operable at the completion of each job, said third logic means including,

c1) means for checking the node'"'"'s own said workload value,

c2) means for polling all the other nodes for their said workload value if the checking node'"'"'s said workload value is below a pre-established value indicating the node as being underutilized and available to do more jobs,

c3) means for checking the said workload values of the other nodes as received, and

c4) means for transfering a job from the queue of the other of the nodes having the highest said workload value over a pre-established value indicating said other of the nodes as being overburdened and requiring job relief to the queue of the checking node.

14. The improvement to a distributed heterogeneous computer system of claim 13 wherein:

said third logic means is also operable periodically when the node is idle.

15. The improvement to a distributed heterogeneous computer system of claim 13 wherein:

said first logic means at each node comprises means for dividing the number of jobs on the node'"'"'s queue by the service rate of the node.

16. The improvement to a distributed heterogeneous computer system of claim 13 wherein the jobs to be performed by the nodes are assigned priority levels and wherein additionally:

said means for polling of all the other nodes for their said workload value by a node of said third logic means includes means for accomplishing said polling as a job at the highest priority level.