Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-02-17
2003-12-02
Follansbee, John (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S241000, C709S241000, C709S241000, C709S201000, C709S226000
Reexamination Certificate
active
06658449
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention is directed to apparatus and methods for periodic load balancing in a multiple run queue system.
2. Description of Related Art
Multiple processor systems are generally known in the art. In a multiple processor system, a process may be shared by a plurality of processors. The process is broken up into threads which may be processed concurrently. However, the threads must be queued for each of the processors of the multiple processor system before they may be executed by a processor.
One known technique for queuing threads to be dispatched by a processor in a multiple processor system is to maintain a single centralized queue, or “run queue.” As processors become available, they take the next thread in the queue and process it. The drawback to this approach is that the centralized queue becomes a bottleneck for the threads and processing time may be lost due to processors spinning on a run queue lock, i.e. becoming idle, while waiting to take the next thread from the centralized queue.
Another known technique for queuing threads is to maintain separate queues for each processor. Thus, when a thread is created, it is assigned to a processor in a round robin fashion. With such a technique, some processors may become overloaded while other processors are relatively idle. Furthermore, some low priority threads may become starved, i.e. are not provided with any processing time, because higher priority threads are added to the run queue of the processor for which the low priority threads are waiting.
Thus, there is a need for new technology to provide apparatus and methods for balancing the workload of a multiple processor system while maintaining a high throughput in the multiple processor system.
SUMMARY OF THE INVENTION
The present invention provides apparatus and methods for periodic load balancing in a multiple run queue system. 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. Initial load balancing addresses to which run queue a new thread of a process should be assigned. Idle load balancing addresses how to shift threads from one run queue to another when a processor is becoming idle. Periodic load balancing addresses how to shift threads from the heaviest loaded run queue to the lightest loaded run queue in order to maintain a load balance. Starvation load balancing addresses how to requeue threads that are being starved of processor processing time.
These techniques make use of global and local run queues to perform load balancing. The global run queue is associated with a node of processors which service the global run queue. Each processor within the node also services a local run queue. Thus, each processor in a node services both the global run queue and a local run queue.
Initial load balancing makes use of the global run queue to place threads that are not able to be placed directly in the local run queue of an idle processor. Starvation load balancing makes use of the global run queue to place threads that have been starved for processor time in order to provide a greater likelihood that a less busy processor will dispatch the thread.
Idle load balancing and periodic load balancing attempt to shift threads from one local run queue to another in an effort to balance the workloads of the processors of the system.
REFERENCES:
patent: 4631674 (1986-12-01), Blandy
patent: 5031089 (1991-07-01), Liu et al.
patent: 5159686 (1992-10-01), Chastain et al.
patent: 5185861 (1993-02-01), Valencia
patent: 5193172 (1993-03-01), Arai et al.
patent: 5506987 (1996-04-01), Abramson et al.
patent: 5574939 (1996-11-01), Keckler et al.
patent: 5692193 (1997-11-01), Jagannathan et al.
patent: 5745778 (1998-04-01), Alfieri
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5784614 (1998-07-01), Davis
patent: 5826081 (1998-10-01), Zolnowsky
patent: 5872972 (1999-02-01), Boland et al.
patent: 5887143 (1999-03-01), Saito et al.
patent: 5924097 (1999-07-01), Hill et al.
patent: 5928322 (1999-07-01), Bitar et al.
patent: 5937187 (1999-08-01), Kosche et al.
patent: 5938723 (1999-08-01), Hales, II et al.
patent: 5978829 (1999-11-01), Chung et al.
patent: 5991808 (1999-11-01), Broder et al.
patent: 6026425 (2000-02-01), Suguri et al.
patent: 6094663 (2000-07-01), Snow et al.
patent: 6101524 (2000-08-01), Choi et al.
patent: 6105053 (2000-08-01), Kimmel et al.
patent: 6125363 (2000-09-01), Buzzeo et al.
patent: 6128642 (2000-10-01), Doraswamy et al.
patent: 6222822 (2001-04-01), Gerardin et al.
patent: 6247025 (2001-06-01), Bacon
patent: 6247044 (2001-06-01), Gosling et al.
patent: 6260057 (2001-07-01), Eykholt et al.
patent: 6266745 (2001-07-01), de Backer et al.
patent: 6269390 (2001-07-01), Boland
patent: 6279124 (2001-08-01), Brouwer et al.
patent: 6289369 (2001-09-01), Sundaresan
patent: 6292822 (2001-09-01), Hardwick
patent: 6298386 (2001-10-01), Vahalia et al.
patent: 6351775 (2002-02-01), Yu
patent: 6385638 (2002-05-01), Baker-Harvey
patent: 6389451 (2002-05-01), Hart
patent: 6418460 (2002-07-01), Bitar et al.
patent: 6434591 (2002-08-01), Watakabe et al.
patent: 6453356 (2002-09-01), Sheard et al.
patent: 6469991 (2002-10-01), Chuah
patent: 6490611 (2002-12-01), Shen et al.
Poindexter et al. “System for enterprise-wide work flow automation.” US Pat. application publication 2003/0093458 A1.*
DeBettencourt et al., Web service, U.S. patent application Publication 2002/0042823 A1.*
LiVecchi, Performance enhancements for threaded servers, U.S. patent application Publication 2001/0018701 A1.*
TechEncyclopedia Multithreading; www.techweb.com; pp. 1-2.
Boland, Vernon. “Method and Apparatus for Allocating Network Resources and Changing the Allocation Based on Dynamic Workload Changes”. U.S. patent application Publication 2001/0003831 A1.
Nemirovsky et al. “Interstream Control and Communications for Multi-Steaming Digital Processors”. U.S. patent application Publication 2002/0095565 A1.
Cota-Robles, Erik. “Priority Based Simultaneous Multi-Threading”. U.S. patent application Publication 2001/0056456 A1.
Brenner Larry Bert
Browning Luke Matthew
Emile Volel
Follansbee John
International Business Machines - Corporation
Vo Lilian
Walder, Jr. Stephen J.
LandOfFree
Apparatus and method for periodic load balancing in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for periodic load balancing in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for periodic load balancing in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115789