Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-07-13
2004-05-11
Banankhah, Majid A. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S102000, C718S103000, C711S133000
Reexamination Certificate
active
06735769
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention is directed to apparatus and methods for initial 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. Furthermore, there is a need for new technology to provide an initial load balancing of workloads amongst a plurality of run queues.
SUMMARY OF THE INVENTION
The present invention provides apparatus and methods for performing initial load balancing, idle load balancing, periodic load balancing and starvation load balancing, to ensure that the workloads for the processors of a 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: 5745778 (1998-04-01), Alfieri
patent: 5872972 (1999-02-01), Boland et al.
patent: 5889989 (1999-03-01), Robertazzi et al.
patent: 6292822 (2001-09-01), Hardwick
Brenner Larry Bert
Browning Luke Matthew
Srinivas Mysore Sathyanarayana
VanFleet James William
Banankhah Majid A.
Emile Volel
Walder, Jr. Stephen J.
Yee Duke W.
LandOfFree
Apparatus and method for initial 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 initial 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 initial load balancing in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3210609