Apparatus, method and computer program product for converting simple locks in a multiprocessor system

• US 6,842,809 B2
• Filed: 04/12/2001
• Issued: 01/11/2005
• Est. Priority Date: 04/12/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Browning, Luke Matthew, Moody, James Bernard, Mathews, Thomas Stanley, McKenney, Paul Edward
• Primary Examiner(s): Dang, Khanh
• Assistant Examiner(s): KNOLL, CLIFFORD H
• Application Number:
  US09/833,417
• Publication Number:
  US 20020199045A1
• Time in Patent Office: 1,370 Days
• Field of Search: 710/200, 710/220, 710/240, 710/241, 710/242, 718/104, 711/147, 711/152
• US Class Current: 710/200
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

An apparatus, method and computer program product for minimizing the negative effects that occur when simple locks are highly contended among processors which may or may not have identical latencies to the memory that represents a given lock, are provided. The apparatus, method and computer program product minimize these effects by converting simple locks such that they act as standard simple locks when there is no contention and act as krlocks when there is contention for a lock. In this way, the number of processors spinning on a lock is limited to a single processor, thereby reducing the number of processors that are in a wait state and not performing any useful work.

Claims

1. A method of locking a system resource in a multiprocessor system, comprising:

attempting to obtain a lock on the system resource;

associating a hand-off lock with the lock on the system resource if the attempt to obtain the lock is unsuccessful, wherein the hand-off lock includes a plurality of pre-processor spin fields, each pre-processor spin field being associated with one processor in the multiprocessor system and identifying a memory location dedicated to that one processor, and wherein only the one processor may spin on the memory location identified by the processor'"'"'s corresponding dedicated per-processor spin field at any one time; and

obtaining the hand-off lock on the system resource if the attempt to obtain the lock on the system resource is unsuccessful, wherein obtaining the hand-off lock includes spinning on the memory location identified by the per-processor spin field for an associated processor.

2. The method of claim 1, wherein the lock is a simple lock.

3. The method of claim 1, wherein the hand-off lock is a krlock.

4. The method of claim 1, wherein the step of attempting to obtain a lock on the system resource is performed a predetermined number of times before associating a hand-off lock with the lock on the system resource.

5. The method of claim 1, wherein the hand-off lock is obtained from a pool of hand-off locks.

6. The method of claim 1, wherein associating a hand-off lock with the lock on the system resource includes storing an index of the hand-off lock in a lock word of the lock on the system resource.

7. The method of claim 1, wherein if the lock on the system resource is freed, the method further comprises:

obtaining the lock on the system resource;

releasing the hand-off lock; and

handing-off the hand-off lock to a next processor spinning on the hand-off lock.

8. The method of claim 1, wherein the method is implemented in a multiprocessor system having one or more nodes, and wherein the hand-off lock includes a per-node word which contains a state of the hand-off lock on each node of the multiprocessor system.

9. The method of claim 8, wherein when the lock on the system resource is released, the per-node word and per-processor spin fields of the hand-off lock are updated to reflect a next processor obtaining the lock on the system resource.

10. The method of claim 1, wherein the method is implemented in one of a SMP, a NUMA, and a ccNUMA system.

31. The method of claim 1, wherein the only processor in the multiprocessor system that may obtain the lock is a processor that currently owns the hand-off lock.

32. The method of claim 1, wherein a state structure associated with the hand-off lock identifies an order in which processors spinning on memory locations identified by the per-processor spin fields of the hand-off lock are to be given ownership of the hand-off lock.

33. The method of claim 32, wherein when a processor that owns the hand-off lock acquires the lock, the processor that owns the hand-off lock hands ownership of the hand-off lock to a next processor attempting to acquire the hand-off lock as determined by the state structure.

34. The method of claim 32, wherein the state structure identifies which processor of the multiprocessor system owns the hand-off lock and which processors of the multiprocessor system are trying to obtain the hand-off lock, if any.

35. The method of claim 1, wherein data in the memory locations identified by the per-processor spin fields is maintained in corresponding caches of the associated processors while the processors spin on their corresponding memory locations.

36. The method of claim 1, wherein the hand-off lock serializes handing off of ownership of the hand-off lock to processors in the multiprocessor system based on the per-processor spin fields.

11. A computer program product in a computer readable medium for locking a system resource in a multiprocessor system, comprising:

first instructions for attempting to obtain a lock on the system resource;

second instructions for associating a hand-off lock with the lock on the system resource if the attempt to obtain the lock is unsuccessful, wherein the hand-off lock includes a plurality of per-processor spin fields, each per-processor spin field being associated with one processor in the multiprocessor system and identifying a memory location dedicated to that one processor, and wherein only the one processor may spin on the memory location identified by the processor'"'"'s corresponding dedicated per-processor spin field at any one time; and

third instructions for obtaining the hand-off lock on the system resource if the attempt to obtain the lock on the system resource is unsuccessful, wherein obtaining the hand-off lock includes spinning on the memory location identified by the per-processor spin field for an associated processor.

12. The computer program product of claim 11, wherein the lock is a simple lock.

13. The computer program product of claim 11, wherein the hand-off lock is a krlock.

14. The computer program product of claim 11, further comprising instructions for executing the first instructions a predetermined number of times before executing the second instructions.

15. The computer program product of claim 11, wherein the hand-off lock is obtained from a pool of hand-off locks.

16. The computer program product of claim 11, wherein the second instructions include instructions for storing an index of the hand-off lock in a lock word of the lock on the system resource.

17. The computer program product of claim 11, wherein the computer program product further comprises:

fourth instructions for obtaining the lock on the system resource, if the lock on the system resource is freed;

fifth instructions for releasing the hand-off lock; and

sixth instructions for handing-off the hand-off lock to a next processor spinning on the hand-off lock.

18. The computer program product claim 11, wherein the hand-off lock includes a per-node word which contains a state of the hand-off lock on each node of a multiprocessor system.

19. The computer program product of claim 18, further comprising fourth instructions for updating the per-node word and per-processor spin fields of the hand-off lock to reflect a next processor obtaining the lock on the system resource, when the lock on the system resource is released.

20. The computer program product of claim 11, wherein the first, second and third instructions are formatted for use with one of an SMP, a NUMA, and a ccNUMA system.

37. The computer program product of claim 11, wherein the only processor in the multiprocessor system that may obtain the lock is a processor that currently owns the hand-off lock.

38. The computer program product of claim 11, wherein the hand-off lock serializes handing off of ownership of the hand-off lock to processors in the multiprocessor system based on the per-processor spin fields.

39. The computer program product of claim 11, wherein a state structure associated with the hand-off lock identifies an order in which processors spinning on memory locations identified by the per-processor spin fields of the hand-off lock are to be given ownership of the hand-off lock.

40. The computer program product of claim 39, wherein when a processor that owns the hand-off lock acquires the lock, the processor that owns the hand-off lock hands ownership of the hand-off lock to a next processor attempting to acquire the hand-off lock as determined by the state structure.

41. The computer program product of claim 39, wherein the state structure identifies which processor of the multiprocessor system owns the hand-off lock and which processors of the multiprocessor system are trying to obtain the hand-off lock, if any.

21. An apparatus for locking a system resource in a multiprocessor system, comprising:

means for attempting to obtain a lock on the system resource;

means for associating a hand-off lock with the lock on the system resource if the attempt to obtain the lock is unsuccessful, wherein the hand-off lock includes a plurality of per-processor spin fields, each per-processor spin field being associated with one processor in the multiprocessor system and identifying a memory location dedicated to that one processor, and wherein only the one processor may spin on the memory location identified by the processor'"'"'s corresponding dedicated per-processor spin field at any one time; and

means for obtaining the hand-off lock on the system resource if the attempt to obtain the lock on the system resource is unsuccessful, wherein obtaining the hand-off lock includes spinning on the memory location identified by the per-processor spin field for an associated processor.

22. The apparatus of claim 21, wherein the lock is a simple lock.

23. The apparatus of claim 21, wherein the hand-off lock is a krlock.

24. The apparatus of claim 21, wherein the means for attempting to obtain the lock on the system resource operates a predetermined number of times before the means for associating the hand-off lock operates.

25. The apparatus of claim 21, wherein the hand-off lock is obtained from a pool of hand-off locks.

26. The apparatus of claim 21, wherein the means for associating the hand-off lock includes means for storing an index of the hand-off lock in a lock word of the lock on the system resource.

27. The apparatus of claim 21, wherein the apparatus further comprises:

means for obtaining the lock on the system resource, if the lock on the system resource is freed;

means for releasing the hand-off lock; and

means for handing-off the hand-off lock to a next processor spinning on the hand-off lock.

28. The apparatus claim 21, wherein the apparatus is part of a multiprocessor system having one or more nodes, and wherein the hand-off lock includes a per-node word which contains a state of the hand-off lock on each node of the multiprocessor system.

29. The apparatus of claim 28, further comprising means for updating the per-node word and per-processor spin fields of the hand-off lock to reflect a next processor obtaining the lock on the system resource, when the lock on the system resource is released.

30. The apparatus of claim 21, wherein the apparatus is part of one of a SMP, a NUMA, and a ccNUMA system.

42. The apparatus of claim 21, wherein data in the memory locations identified by the per-processor spin fields is maintained in corresponding caches of the associated processors while the processors spin on their corresponding memory locations.

43. The apparatus of claim 21, wherein the only processor in the multiprocessor system that may obtain the lock is a processor that currently owns the hand-off lock.

44. The apparatus of claim 21, wherein the hand-off lock serializes handing off of ownership of the hand-off lock to processors in the multiprocessor system based on the per-processor spin fields.

45. The apparatus of claim 21, wherein a state structure associated with the hand-off lock identifies an order in which processors spinning on memory locations identified by the per-processor spin fields of the hand-off lock are to be given ownership of the hand-off lock.

46. The apparatus of claim 45, wherein when a processor that owns the hand-off lock acquires the lock, the processor that owns the hand-off lock hands ownership of the hand-off lock to a next processor attempting to acquire the hand-off lock as determined by the state structure.

47. The apparatus of claim 45, wherein the state structure identifies which processor of the multiprocessor system owns the hand-off lock and which processors of the multiprocessor system are trying to obtain the hand-off lock, if any.

48. The apparatus of claim 21, wherein data in the memory locations identified by the per-processor spin fields is maintained in corresponding caches of the associated processors while the processors spin on their corresponding memory locations.