Apparatus and method for minimizing lock contention in a multiple processor system with multiple run queues

• US 20030195920A1
• Filed: 06/05/2003
• Published: 10/16/2003
• Est. Priority Date: 05/25/2000
• Status: Active Grant

• Current Assignee: Larry Bert Brenner, Luke Mathew Browning
• Original Assignee: Larry Bert Brenner, Luke Mathew Browning
• Inventors: Brenner, Larry Bert, Browning, Luke Mathew
• Granted Patent: US 6,981,260 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• 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. 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.

2. The method of claim 1 wherein the step of determining includes the step of comparing information associated with the at least two run queues.

3. The method of claim 2 wherein the information compared includes priority status of threads.

4. The method of claim 3 wherein the at least two run queues include a local run queue and a global run queue, the local run queue being associated with one processor and the global run queue being associated with a group of processors.

5. The method of claim 4 wherein the group of processors includes the one processor.

6. The method of claim 5 wherein the thread with a higher priority is dispatched.

7. The method of claim 6 wherein if the thread in the local run queue and the thread in the global run queue have equal priority, the thread in the local run queue is dispatched.

8. The method of claim 7 wherein if one of the at least two run queues is empty, a thread from the non-empty run queue is dispatched.

9. The method of claim 8 wherein if both the local run queue and the global run queue are empty, a thread from a local run queue associated with another processor from the group of processors is dispatched.

10. The method of claim 5 wherein the thread with a lower priority is dispatched.

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.

12. The data processing system of claim 11 wherein the means for determining includes means for comparing information associated with the at least two run queues.

13. The data processing system of claim 12 wherein the information compared includes priority status of threads.

14. The data processing system of claim 13 wherein the at least two run queues include a local run queue and a global run queue, the local run queue being associated with one processor and the global run queue being associated with a group of processors.

15. The data processing system of claim 14 wherein the group of processors includes the one processor.

16. The data processing system of claim 15 wherein the thread with the higher priority is dispatched.

17. The data processing system of claim 16 wherein if the thread in the local run queue and the thread in the global run queue have equal priority, the thread in the local run queue is dispatched.

18. The data processing system of claim 17 wherein if either the local run queue or the global run queue is empty, a thread from the non-empty run queue is dispatched.

19. The data processing system of claim 18 wherein if both the local run queue and the global run queue are empty, a thread from a run queue associated with another processor is dispatched.

20. The data processing system of claim 15 wherein the thread with the lower priority is dispatched.

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.

22. The computer program product of claim 21 wherein the program code means for determining includes program code means for comparing information associated with the at least two run queues.

23. The computer program product of claim 22 wherein the information compared includes priority status of threads.

24. The computer program product of claim 23 wherein the at least two run queues include a local run queue and a global run queue, the local run queue being associated with one processor and the global run queue being associated with a group of processors.

25. The computer program product of claim 24 wherein the group of processors includes the one processor.

26. The computer program product of claim 25 wherein the thread with the higher priority is dispatched.

27. The computer program product of claim 26 wherein if the thread in the local run queue and the thread in the global run queue have equal priority, the thread in the local run queue is dispatched.

28. The computer program product of claim 27 wherein if either the local run queue or the global run queue is empty, a thread from the non-empty run queue is dispatched.

29. The computer program product of claim 28 wherein if both the local run queue and the global run queue are empty, a thread from a run queue associated with another processor is dispatched.

30. The computer program product of claim 25 wherein the thread with the lower priority is dispatched.

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.

32. The apparatus of claim 31, wherein the run queue selected for dispatch is the local run queue, selected as a result of a thread at the head a local run queue having higher priority than a thread at the head of the global run queue.

33. The apparatus of claim 31, wherein the run queue selected for dispatch is the global run queue as a result of a thread at the head a global run queue having higher priority than a thread at the head of the local run queue.

34. The apparatus of claim 31, wherein the run queue selected for dispatch is the local run queue as a result of the global run queue being empty and the local run queue not being empty.

35. The apparatus of claim 31, wherein the run queue selected for dispatch is the global run queue as a result of the local run queue being empty and the global run queue not being empty.

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

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

38. The apparatus of claim 37, wherein if an exclusive access request on a 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.

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

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.

41. The apparatus of claim 40, wherein if a first thread at the head of the global run queue has d higher priority than a second thread at the head of the local run queue have the same priority, then the global run queue is selected for dispatch.

42. The apparatus of claim 40, wherein if a first thread at the head of the global run queue does not have higher priority than a second thread at the head of the local run queue, then the local run queue is selected for dispatch.

43. The apparatus of claim 40, wherein if the local run queue is empty and the global run queue is not empty, then the global run queue is selected for dispatch.

44. The apparatus of claim 40, wherein if the global run queue is empty and the local run queue is not empty, then the local run queue is selected for dispatch.

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

46. The apparatus of claim 40 herein if the global run queue is empty and the local run queue is empty, then a thread for dispatch by a processor associated with the local run queue is selected from a 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.

47. The apparatus of claim 46 herein the local run queue, associated with the another processor, has the largest number of threads of all the local run queues run queue with the plurality of processors.

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

49. The apparatus of claim 46, 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.

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

51. The apparatus of claim 46, 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.

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

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.

54. The computer program product of claim 53, wherein the selected run queue is the local run queue as a result of a thread at the head a local run queue having higher priority than a thread at the head of the global run queue.

55. The computer program product of claim 53, wherein the selected run queue is the global run queue as a result of a thread at the head a global run queue having higher priority than a thread at the head of the local run queue.

56. The computer program product of claim 53, wherein the selected run queue is the local run queue as a result of the global run queue being empty and the local run queue not being empty.

57. The computer program product of claim 53, wherein the selected run queue is the global run queue as a result of the local run queue being empty and the global run queue not being empty.

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

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

60. The computer program product of claim 59, wherein if an exclusive access request on a 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.

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