Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-02-17
2004-06-08
Lee, Thomas (Department: 2137)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S102000, C718S103000, C718S106000, C709S223000
Reexamination Certificate
active
06748593
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention is directed to apparatus and methods for starvation load balancing using a global run queue 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. Furthermore, there is a need for new technology to prevent unfair starvation of low priority threads.
SUMMARY OF THE INVENTION
The present invention provides apparatus and methods for starvation load balancing by using a global run queue in a multiple run queue system. Starvation load balancing is a method for ensuring fair treatment of low priority threads on a multiple run queue system. Low priority threads may not be serviced for potentially very long periods of time, which may be normal expected behavior for such threads competing on a busy system. However, it is undesirable for similar low priority threads to be treated differently as a side-effect of having multiple run queues. The present invention provides a mechanism to ensure equitable treatment of the low priority threads system-wide.
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 address 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: 5796954 (1998-08-01), Hanif et al.
patent: 5826081 (1998-10-01), Zolnowsky
patent: 5872972 (1999-02-01), Boland et al.
patent: 5887143 (1999-03-01), Saito et al.
patent: 5928322 (1999-07-01), Bitar et al.
patent: 5930465 (1999-07-01), Bellucco 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: 6128657 (2000-10-01), Okanoya et al.
patent: 6160875 (2000-12-01), Park 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.
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/00955656 A1.
Cota-Robles, Erik. “Priority Based Simultaneous Multi-Threading”. U.S. patent application Publication 2001/0056456 A1.
LiVecchi, Patrick. “Performance Enhancements for Threaded Servers”. U.S. patent application Publication 2001/0018701 A1.
DeBettencourt, Jason. “Web Service”. U.S. patent application Publication 2002/0042823 A1.
Brenner Larry Bert
Browning Luke Matthew
Emile Volel
Lee Thomas
Vo Lilian
Walder, Jr. Stephen J.
Yee Duke W.
LandOfFree
Apparatus and method for starvation load balancing using 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 starvation load balancing using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for starvation load balancing using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3365982