Apparatus and method for minimizing lock contention in a multiple processor system with multiple run queues
First Claim
1. 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:
- determining, from at least two run queues, which thread to dispatch without obtaining exclusive access to the run queues; and
dispatching the determined thread.
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
61 Claims
-
1. 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:
-
determining, from at least two run queues, which thread to dispatch without obtaining exclusive access to the run queues; and
dispatching the determined thread. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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:
-
means for determining which thread to dispatch from at least two run queues without obtaining exclusive access to the run queues; and
means for dispatching the determined thread. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. 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:
-
program code means for determining which thread to dispatch from at least two run queues without obtaining exclusive access to the run queues; and
program code means for dispatching the determined thread. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. 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 selecting means for selecting a run queue for dispatch by a processor from the plurality of processors, wherein the run queue is selected from a local run queue, associated with the processor, a global run queue, associated with the processor, and a local run queue, associated with another processor, as determined by examining run queues without obtaining exclusive access. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39)
-
40. A selection apparatus for selecting a run queue for dispatch in a multiple processor, system having a plurality of processors, comprising:
-
a local memory for each processor in the plurality of processors for storing a local run queue; and
a global memory coupled to a plurality of processors for storing a global run queue, a shift threshold value, and a maximum shift threshold value; and
wherein each processor in the plurality of processors;
examines the global run queue without obtaining exclusive access, examines its own local run queue without obtaining exclusive access, examines the local run queues of other processors without obtaining exclusive accesses if the global run queue and its own local run queue are empty, selects a run queue for dispatch, requests an exclusive access on the selected run queue, and attempts to dispatch a thread from the selected run queue if the exclusive access is obtained. - View Dependent Claims (41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52)
-
-
53. 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:
instructions for selecting a run queue for dispatch by a processor from the plurality of processors, wherein the run queue is selected from a local run queue, associated with the processor, a global run queue, associated with the processor, and a local run queue, associated with another processor, as determined by examining run queues without obtaining exclusive access. - View Dependent Claims (54, 55, 56, 57, 58, 59, 60, 61)
Specification