Load balancer with starvation avoidance

Abstract

A method and apparatus for balancing processing loads to avoid starvation of threads is described. A method of load balancing evaluates the load and state of multiple processors. If at least one processor is in a source state and at least one processor is in a sink state, the processing load is balanced to avoid starvation. A thread is transferred from the heaviest loaded, source state processor to the least loaded, sink state processor. Each processor load and state is then reevaluated and, if needed, the load balancing with starvation avoidance repeated.

What is claimed is:  
     
         1 . A computer implemented method of load balancing a multiprocessor computer system, comprising the following steps: 
 determining the state of each of two or more processors, wherein the state includes at least one of a source and sink state; and    if at least one of the two or more processors is in a source state and at least one of the two or more processors is in a sink state, transferring at least one thread from a queue of a source state processor to a queue of a sink state processor.    
     
     
         2 . The method as claimed in  claim 1 , wherein the state further includes a neither state.  
     
     
         3 . The method as claimed in  claim 1 , wherein the method further comprises the following step: 
 repeating said steps.    
     
     
         4 . The method as claimed in  claim 1 , wherein the method is initiated once every second.  
     
     
         5 . The method as claimed in  claim 1 , wherein the method is performed indefinitely.  
     
     
         6 . The method as claimed in  claim 1 , wherein the method further includes the following step: 
 determining the load of each of the two or more processors.    
     
     
         7 . The method as claimed in  claim 6 , wherein the transferring step further includes: 
 transferring at least one thread from the highest loaded, source state processor to the lowest loaded, sink state processor.    
     
     
         8 . A computer implemented method of load balancing a multiprocessor computer system, comprising the following steps: 
 determining a score of each of two or more processors;    determining a best score processor and a worst score processor; and    transferring at least one thread from a queue of a worst score processor to a queue of a best score processor.    
     
     
         9 . The method as claimed in  claim 8 , wherein the score is a function of at least a processor state.  
     
     
         10 . The method as claimed in  claim 8 , wherein the score is a function of at least a processor state and a processor load.  
     
     
         11 . The method as claimed in  claim 10 , wherein the processor state is weighted more heavily than the processor load.  
     
     
         12 . A computer implemented method of load balancing a networked plurality of computer systems, comprising the following steps: 
 determining the state of each of the networked plurality of computer systems, wherein the state includes at least one of a source and sink state; and    if at least one of the plurality of computer systems is in a source state and at least one of the plurality of computer systems is in a sink state, transferring at least one thread from a source state processor to a sink state processor.    
     
     
         13 . A computer system for balancing load using starvation avoidance comprising: 
 one or more processors for receiving and transmitting data; and    a memory coupled to said one or more processors, said memory having stored therein sequences of instructions which, when executed by one of said one or more processors, cause one of said one or more processors to determine the state of each of said one or more processors, wherein the state includes at least one of a source and sink state, and, if at least one of the one or more processors is in a source state and at least one of the one or more processors is in a sink state, transfer at least one thread from a source state processor to a sink state processor.