Apparatus for minimizing lock contention in a multiple processor system with multiple run queues when determining the threads priorities

• US 6,981,260 B2
• Filed: 06/05/2003
• Issued: 12/27/2005
• Est. Priority Date: 05/25/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Browning, Luke Mathew, Brenner, Larry Bert
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Vo, Lilian
• Application Number:
  US10/455,108
• Publication Number:
  US 20030195920A1
• Time in Patent Office: 936 Days
• Field of Search: 718/100, 718/102, 718/103, 718/104, 718/107, 718/105
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

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.

2. The apparatus of claim 1, wherein the run queue selected for dispatch is the local run queue associated with the given processor, selected as a result of the thread at the head the local run queue associated with the given processor having higher priority than of the thread at the head of the first global run queue.

3. The apparatus of claim 1, wherein the run queue selected for dispatch is the first global run queue as a result of the thread at the head of the first global run queue having higher priority than the thread at the head of the local run queue associated with the given processor.

4. The apparatus of claim 1, wherein the run queue selected for dispatch is the local run queue associated with the given processor as a result of the first global run queue being empty and the local run queue associated with the given processor not being empty.

5. The apparatus of claim 1, wherein the run queue selected for dispatch is the first global run queue as a result of the local run queue associated with the given processor being empty and the first global run queue not being empty.

6. The apparatus of claim 1, wherein if an exclusive access request on the first global run queue for dispatching the thread in the first global run queue is not obtained immediately, then the exclusive access request is not repeated.

7. The apparatus of claim 1, wherein a thread for dispatch by the given processor from the plurality of processors, when the local run queue associated with the given processor, and the first global run queue associated with the given processor, are both empty, is selected from the local run queue associated with another processor from the plurality of processors, as determined by comparing the local run queues for all processors without obtaining exclusive access.

8. The apparatus of claim 7, wherein if an exclusive access request on the local run queue associated with the another processor, for dispatching a thread in the local run queue associated with the another processor is not obtained immediately, then the exclusive access request is not repeated.

9. The apparatus of claim 7, wherein if an exclusive access request on the thread selected for dispatch from the local run queue associated with the another processor is not obtained immediately, then the exclusive access request on the thread is not repeated.

10. The apparatus of claim 1, wherein, if the selecting means for selecting the local run queue associated with the given processor in response to the priorities being the same, results in the local run queue associated with the given processor being chosen twice consecutively, then the first global run queue associated with the given processor is selected.

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.

12. The apparatus of claim 11, wherein if the thread at the head of the global run queue has a higher priority than the thread at the head of the local run queue associated with a given processor, then the global run queue is selected for dispatch.

13. The apparatus of claim 11, wherein if the thread at the head of the global run queue does not have higher priority than the thread at the head of the local run queue associated with a given processor, then the local run queue associated with the given processor is selected for dispatch.

14. The apparatus of claim 11, wherein if the local run queue associated with a given processor is empty and the global run queue is not empty, then the global run queue is selected for dispatch.

15. The apparatus of claim 11, wherein if the global run queue is empty and the local run queue associated with a given processor is not empty, then the local run queue associated with the given processor is selected for dispatch.

16. The apparatus of claim 11, wherein if an exclusive access request on the global run queue for dispatching the thread in the global run queue is not obtained immediately, then the exclusive access request is not repeated.

17. The apparatus of claim 11, wherein if the global run queue is empty and the local run queue associated with a given processor is empty, then the thread for dispatch by the given processor associated with the local run queue is selected from the local run queue associated with another processor from the plurality of processors, as determined by examining the local run queues for all processors in the plurality of processors without obtaining exclusive accesses.

18. The apparatus of claim 17, wherein the local run queue associated with the another processor, has a larger number of threads than all the local run queues associated with the plurality of processors.

19. The apparatus of claim 17, wherein the local run queue associated with the another processor, contains more threads than the shift threshold value associated with the plurality of processors.

20. The apparatus of claim 17, wherein the local run queue associated with the another processor, contains at least one thread that is not bound to a processor from the plurality of processors.

21. The apparatus of claim 17, wherein the local run queue associated with the another processor, has not had more threads shifted from the local run queue associated with the another processor for a current clock cycle than the maximum shift threshold value associated with the plurality of processors.

22. The apparatus of claim 17, wherein if an exclusive access request on the local run queue associated with the another processor, is not obtained immediately, then the exclusive access request is not repeated.

23. The apparatus of claim 17, wherein if an exclusive access request on the thread selected for dispatch from the local run queue associated with the another processor is not obtained immediately, then the exclusive access request on the thread is not repeated.

24. The apparatus of claim 11, wherein, if each processor in the plurality of processors selection of the local run queue associated with the given processor in response to the priorities being the same, results in the local run queue associated with the given processor being chosen twice consecutively, then the global run queue associated with the given processor is selected.

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.

26. The computer program product of claim 25, wherein the selected run queue is the local run queue associated with the given processor as a result of the thread at the head of the local run queue associated with the given processor having higher priority than the thread at the head of the first global run queue.

27. The computer program product of claim 25, wherein the selected run queue is the global run queue as a result of the thread at the head of the first global run queue having higher priority than the thread at the head of the local run queue associated with the given processor.

28. The computer program product of claim 25, wherein the selected run queue is the local run queue associated with the given processor as a result of the first global run queue being empty and the local run queue associated with the given processor not being empty.

29. The computer program product of claim 25, wherein the selected run queue is the first global run queue as a result of the local run queue associated with the given processor being empty and the first global run queue not being empty.

30. The computer program product of claim 25, wherein if an exclusive access request on the first global run queue for dispatching the thread in the first global run queue is not obtained immediately, then the exclusive access request is not repeated.

31. The computer program product of claim 25, wherein a thread for dispatch by the given processor from the plurality of processors, when the local run queue associated with the given processor, and the first global run queue associated with the given processor, are both empty, is selected from the local run queue associated with another processor from the plurality of processors, as determined by comparing the local run queues for all processors without obtaining exclusive access.

32. The computer program product of claim 31, wherein if an exclusive access request on the local run queue associated with the another processor, for dispatching a thread in the local run queue associated with the another processor is not obtained immediately, then the exclusive access request is not repeated.

33. The computer program product of claim 31, wherein if an exclusive access request on the thread selected for dispatch from the local run queue associated with the another processor is not obtained immediately, then the exclusive access request on the thread is not repeated.

34. The computer program product of claim 25, wherein, if the instructions for selecting the local run queue associated with the given processor in response to the priorities being the same, results in the local run queue associated with the given processor being chosen twice consecutively, then the first global run queue associated with the given processor is selected.