Apparatus and method for starvation load balancing using a global run queue in a multiple run queue system
AssigneeInternational Business Machines Corporation
InventorsLarry Bert Brenner, Luke Matthew Browning
Life of this patent
Estimating the term…
Abstract
Apparatus and methods for starvation load balancing using a global run queue in a multiple run queue system. The apparatus includes a controller, memory, initial load balancing device, idle load balancing device, periodic load balancing device, and starvation load balancing device. The apparatus performs initial load balancing, idle load balancing, periodic load balancing and starvation load balancing to ensure that the workloads for the processors of the system are optimally balanced.
Claims36
A method of balancing workload among a plurality of processors in a multiple processor system, the multiple processor system having a plurality of local run queues, each of the plurality of processors being associated with at least one of the plurality of local run queues, the method comprising:
- assigning a thread to one of the plurality of local run queues;
- time stamping the thread to produce a time stamp;
- determining if a local run queue of the plurality of local run queues to which the thread is assigned has a threshold number of threads present in the local run queue;
- determining whether a difference between a current time and the time stamp is larger than a threshold amount, if it is determined that the local run queue has the threshold number of threads present in the local run queue;
- and
- reassigning the thread to a global run queue if the difference between the current time and the time stamp is larger than the threshold amount.
A computer program product in a computer readable medium for balancing workload amoung a plurality of processors in a multiple processor system, the multiple processor system having a plurality of local run queues, each of the plurality of processors being associated with at least one of the plurality of local run queues, the computer program product comprising:
- first instructions for assigning a thread to one of the plurality of local run queues;
- second instructions for time stamping the thread to produce a time stamp;
- third instructions for determining if a local run queue of the plurality of local run queues to which the thread is assigned has a threshold number of threads present in the local run queue;
- forth instructions for determining whether a difference between a current time and the time stamp is larger than a threshold amount, if it is determined that the local run queue has the threshold number of threads present in the local run queue;
- and
- fifth instructions for reassigning the thread to a global run queue if the difference between the current time and the time stamp is larger than the threshold amount.
A method of balancing workload amoung a plurality of processors in a multiple processor system, the multiple processor system including a plurality of local run queues and at least one global run queue comprising:
- assigning threads to the plurality of local run queues;
- determining if a local run queue of the plurality of local run queues has a threshold number of threads present in the local run queues;
- determining if one or more threads in the local run queue have not been dispatched within a predetermined period of time, if it is determined that the local run queue has the threshold number of threads present in the local run queue;
- and
- moving the one or more threads from the local run queues to the at least one global run queue, if it is determined that the one or more threads have not been dispatched within the predetermined period of time.
A workload balancing apparatus for balancing workload amoung a plurality of processors in a multiple processor system, the multiple processor system having a plurality of local run queues, each of the plurality of processors being associated with at least one of the plurality of local run queues, the apparatus comprising:
- an initial load balancing device;
- and
- a starvation load balancing device, wherein the initial load balancing device assigns a thread to one of the plurality of local run queues, and wherein the starvation load balancing device determines if a local run queue of the plurality of local run queues to which the thread is assigned has a threshold number of threads present in the local run queue, determines whether the thread has not been dispatched within a determined period of time, if it is determined that the local run queue has the threshold number of threads present in the local run queue, and reassigns the thread to a global run queue if the thread has not been dispatched within the determined period of time.
A multiple processor system, comprising:
- a plurality of processors;
- and
- a dispatcher, wherein the plurality of processors are organized into at least one node, and wherein the at last one node has an associated global run queue and each of the plurality of processors has an associated local run queue, and wherein the dispatcher assigns threads to the plurality of local run queue, determines if local run queues of the plurality of local run queues to which threads are assigned have a threshold number of threads present, determines whether threads in the local run queues have not been dispatched within a determined period of time, if it is determined that the local run queues have the threshold number of threads present, and reassigns the threads to a global run queue if the threads have not been dispatched within the determined period of time.
Dependencies are inferred from the claim text.