초록 ▼

An apparatus and methods for periodic load balancing in a multiple run queue system are provided. 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 initi

An apparatus and methods for periodic load balancing in a multiple run queue system are provided. 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.

대표청구항 ▼

What is claimed is: 1. A multiple processor system, comprising: a plurality of processors; and a dispatcher, wherein each of the plurality of processors has an associated local run queue and wherein the dispatcher identifies a heaviest local run queue and a lightest local run queue, the heaviest lo

What is claimed is: 1. A multiple processor system, comprising: a plurality of processors; and a dispatcher, wherein each of the plurality of processors has an associated local run queue and wherein the dispatcher identifies a heaviest local run queue and a lightest local run queue, the heaviest local run queue being a local run queue with a highest load average and the lightest local run queue being a local run queue with a lowest load average, calculates a difference in load average between the heaviest local run queue and the lightest local run queue, and performs periodic load balancing if the difference exceeds a threshold amount, wherein if processor associated with the lightest local run queue has benefited from idle processor load balancing within a determine period of time, the dispatcher does not perform periodic load balancing, and wherein the dispatcher performs idle processor load balancing by identifying a local run queue that satisfies idle processor load balancing criteria. 2. The system of claim 1, wherein the dispatcher performs periodic load balancing by: identifying an unbound thread assigned to the heaviest local run queue; and reassigning the unbound thread to the lightest local run queue. 3. The system of claim 2, wherein the dispatcher reassigns the unbound thread by: obtaining a lock for the unbound thread; and changing a run queue pointer of the thread to identify the lightest local run queue. 4. The system of claim 2, wherein the dispatcher identifies the unbound thread by: obtaining a lock for the heaviest local run queue; and scanning the heaviest local run queue for the unbound thread, wherein the scanning of the heaviest local run queue starts with threads having an intermediate priority. 5. The system of claim 3, wherein the dispatcher holds the thread in a temporary queue prior to changing the run queue pointer of the thread to identify the lightest local run queue. 6. The system of claim 1, wherein the threshold amount is 1.5. 7. The system of claim 1, wherein the dispatcher performs idle processor load balancing by: identifying an idle local run queue; scanning the plurality of local run queues for a local run queue that satisfies idle processor load balancing criteria; and responsive to finding the local run queue of the purality of local run queues that satisfies the idle processor load balancing criteria, stealing a thread from the local run queue satisfying the idle processor load balancing criteria. 8. The system of claim 7, wherein the dispatcher scans the plurality of local run queues for the local run queue of the plurality of local run queues that satisfies idle processor load balancing criteria by identifying a local run queue that has a largest number of threads, contains more threads than a selected threshold, and contains at least one unbound thread. 9. The system of claim 8, wherein the selected threshold is a function of a smoothed average load factor of the plurality of local run queues.