Loading patent…
AssigneeInternational Business Machines Corporation
InventorsLarry Bert Brenner, Luke Mathew Browning
Estimating the term…
Apparatus and methods are provided for selecting a thread to dispatch in a multiple processor system having a global run queue associated with each multiple processor node and having a local run queue associated with each processor. If the global run queue and the local run queue associated with the processor performing the dispatch are both not empty, then the highest priority queue is selected for dispatch, as determined by examining the queues without obtaining a lock. If one of the two queues is empty and the other queue is not empty, then the non-empty queue is selected for dispatch. If the global queue is selected for dispatch but a lock on the global queue cannot be obtained immediately, then the local queue is selected for dispatch. If both queues are empty, then an idle load balancing operation is performed. Local run queues for other processors at the same node are examining without obtaining a lock. If a candidate thread is found that satisfies a set of shift conditions, and if a lock can be obtained on both the non-local run queue and the candidate thread, then the thread is shifted for dispatch by the processor that is about to become idle.
A method of dispatching a thread from a run queue in a multiple processor system, the multiple processor system having a plurality of run queues, each processor being associated with at least one of the plurality of run queues, the method comprising:
A data processing system for dispatching a thread from a run queue in a multiple processor system, the multiple processor system having a plurality of run queues, each processor being associated with at least one of the plurality of run queues, the data processing system comprising:
A computer program product embedded in a medium, said computer program product having program code means for dispatching a thread from a run queue in a multiple processor system, the multiple processor system having a plurality of run queues, each processor being associated with at least one of the plurality of run queues, the computer program product further comprising:
An arbitration apparatus for arbitrating exclusive access contention in a multiple processor system having a plurality of processors, the multiple processor system having a plurality of local run queues and at least one global run queue, each of the plurality of processors being run queue with one of the plurality of local run queues, the method comprising:
A selection apparatus for selecting a run queue for dispatch in a multiple processor, system having a plurality of processors, comprising:
A computer program product in a computer readable medium for arbitrating exclusive access contention in a multiple processor system having a plurality of processors, the multiple processor system having a plurality of local run queues and at least one global run queue, each of the plurality of processors being run queue with one of the plurality of local run queues, the method comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Backward citations are indexed for grants only.
By program, e.g. task dispatcher, supervisor, operating system: scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
Techniques for rebalancing the load in a distributed system: involving task migration
Program synchronisation; Mutual exclusion, e.g. by means of semaphores: mutual exclusion algorithms
Indexing scheme relating to G06F9/48: multiproc
Term end not estimated
1. Technical Field
The invention is directed to apparatus and methods for minimizing lock contention in a multiple run queue system.
2. Description of Related Art
The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:
FIG. 1 is an exemplary block diagram of a multiple run queue system in which the present invention may be implemented;
FIG. 2 is an exemplary diagram of a multiple run queue system illustrating lock contention;
FIG. 1 is an exemplary diagram of a multiple run queue system 100 in which the present invention may be implemented. As shown in FIG. 1, the system 100 includes a multiple processor (MP) system 110, a plurality of CPUs 111-117 organized into nodes 120-140, and a dispatcher 150.
The MP system 110 may be any type of system having a plurality of processors, such as CPUs 111-117. The CPUs 111-117 are any type of processing device capable of processing assigned data processing jobs. The CPUs 111-117 are organized into nodes 120-140. The nodes 120-140 may not be actual devices in themselves, but may be considered representations of the partitioning of CPUs 111-117 into groups. Thus, for example, CPUs 111 and 112 are contained in node 120, CPUs 113 and 114 are contained in node 130, and CPUs 115-117 are contained in node 140.
The dispatcher 150 performs load balancing of the jobs among the nodes 120-140 and the CPUs 111-117. Although the dispatcher 150 is shown as a single centralized device; the dispatcher 150 may be distributed throughout the MP system 110. For example, the dispatcher 150 may be distributed such that a separate dispatcher 150 may be associated with each node 120-140 or a group of nodes 120-140. Furthermore, the dispatcher 150 may be implemented as software instructions run on each CPU 111-117 of the MP system 110.