Apparatus for minimizing lock contention in a multiple processor system with multiple run queues when determining the threads priorities
First Claim
1. 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 a first global run queue, wherein each of the plurality of processors has an associated local run queue that is one of the plurality of local run queues, the arbitration apparatus comprising:
- determining means for determining a priority of a thread at a head of the first global run queue without obtaining exclusive access;
determining means for determining a priority of a thread at a head of a local run queue associated with a given processor without obtaining exclusive access;
comparing means for comparing the priority of the thread at the head of the first global run queue and the priority of the thread at the head of the local run queue associated with the given processor;
determining means for determining if the priority of the thread at the head of the first global run queue and the priority of the thread at the head of the local run queue associated with the given processor are the same;
selecting means for selecting a run queue for dispatch by the given processor from the plurality of processors, wherein the run queue is selected from the local run queue associated with the given processor, and the first global run queue run queue associated with the given processor in response to the priorities being different, as determined by comparing the run queues without obtaining exclusive access;
selecting means for selecting the local run queue associated with the given processor in response to the priorities being the same; and
dispatching means for dispatching by the selected run queue.
0 Assignments
0 Petitions
Accused Products
Abstract
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.
-
Citations
34 Claims
-
1. 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 a first global run queue, wherein each of the plurality of processors has an associated local run queue that is one of the plurality of local run queues, the arbitration apparatus comprising:
-
determining means for determining a priority of a thread at a head of the first global run queue without obtaining exclusive access; determining means for determining a priority of a thread at a head of a local run queue associated with a given processor without obtaining exclusive access; comparing means for comparing the priority of the thread at the head of the first global run queue and the priority of the thread at the head of the local run queue associated with the given processor; determining means for determining if the priority of the thread at the head of the first global run queue and the priority of the thread at the head of the local run queue associated with the given processor are the same; selecting means for selecting a run queue for dispatch by the given processor from the plurality of processors, wherein the run queue is selected from the local run queue associated with the given processor, and the first global run queue run queue associated with the given processor in response to the priorities being different, as determined by comparing the run queues without obtaining exclusive access; selecting means for selecting the local run queue associated with the given processor in response to the priorities being the same; and dispatching means for dispatching by the selected run queue. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A selection apparatus for selecting a run queue for dispatch in a multiple processor system having a plurality of processors, the selection apparatus comprising:
-
a local memory for each processor in the plurality of processors for storing a local run queue; and a global memory coupled to the plurality of processors for storing a global run queue, a shift threshold value, and a maximum shift threshold value, wherein each processor in the plurality of processors; examines the global run queue without obtaining exclusive access; determines a priority of a thread at a head of the global run queue; examines its own local run queue without obtaining exclusive access; determines a priority of a thread at a head of its own local run queue; compares the priority of the thread at the head of the global run queue and the priority of the thread at the head of its own local run queue; determines if the priority of the thread at the head of the global run queue and the priority of the thread at the head of the local run queue associated with the given processor are the same; examines the local run queues of other processors in the plurality of processors without obtaining exclusive accesses if the global run queue and its own local run queue are empty; selects a run queue from the global run queue and the local run queue for the plurality of processors for dispatch in response to the priorities being different; selects the local run queue associated with the given processor in response to the priorities being the same; requests an exclusive access on the selected run queue; and attempts to dispatch the thread from the selected run queue if the exclusive access is obtained. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A computer program product stored in a tangible 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 a first global run queue, wherein each of the plurality of processors has an associated local run queue that is one of the plurality of local run queues, the computer program product comprising:
-
instructions for determining a priority of a thread at a head of the first global run queue without obtaining exclusive access; instructions for determining a priority of a thread at a head of a local run queue associated with a given processor without obtaining exclusive access; instructions for comparing the priority of the thread at the head of the first global run queue and the priority of the thread at the head of the local run queue associated with the given processor; instructions for determining if the priority of the thread at the head of the first global run queue and the priority of the thread at the head of the local run queue associated with the given processor are the same; instructions for selecting a run queue for dispatch by the given processor from the plurality of processors, wherein the run queue is selected from the local run queue associated with the given processor, and the first global run queue run queue associated with the given processor in response to the priorities being different, as determined by comparing the run queues without obtaining exclusive access; instructions for selecting the local run queue associated with the given processor in response to the priorities being the same; and instructions for dispatching by the selected run queue. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34)
-
Specification