Multiprocessing systems employing hierarchical back-off locks

• US 6,985,984 B2
• Filed: 11/07/2002
• Issued: 01/10/2006
• Est. Priority Date: 11/07/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Radovic, Zoran, Hagersten, Erik
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US10/289,822
• Publication Number:
  US 20040098723A1
• Time in Patent Office: 1,160 Days
• Field of Search: 709/214, 709/216, 710/200, 710/240, 711/150, 711/152, 711/163
• US Class Current: 710/200
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A multiprocessing system including multiple processing nodes employs various implementations of hierarchical back-off locks. A thread attempting to obtain a software lock may determine whether the lock is currently owned by a different node than the node in which the thread is executing. If the lock is not owned by a different node, the thread executes code to perform a fast spin operation. On the other hand, if the lock is owned by a different node, the thread executes code to perform a slow spin operation. In this manner, node locality may result wherein a thread that is executing within the same node in which a lock has already been obtained will be more likely to subsequently acquire the lock when it is freed in relation to other contending threads executing in other nodes.

Claims

1. A method for performing spin-lock operations in a computer system comprising:

a first thread determining a node id of an owner of a software lock;

the first thread spinning on the software lock at a first initial rate in response to determining the node id identifies the same node in which the first thread is executing; and

the first thread spinning on the software lock at a slower initial rate in response to determining the node id identifies a different node than the node in which the first thread is executing.

2. The method as recited in claim 1 further comprising a second thread storing said node id within a storage location associated with said software lock, wherein said node id corresponds to a particular node in which said second thread is executing.

3. The method as recited in claim 2 further comprising the second thread acquiring said software lock upon a determination that the software lock is in a free state and storing said node id within said storage location.

4. The method as recited in claim 2 wherein said first thread is executed by a first processor, and wherein said second thread is executed by a second processor.

5. The method as recited in claim 4 wherein the second processor executes a compare and swap instruction to cause said storage of said node id within said storage location.

6. The method as recited in claim 5 wherein said first processor executes a compare and swap instruction in a software loop while spinning on the software lock.

7. The method as recited in claim 1 further comprising said first thread setting a local variable with a predetermined value in response to determining the node id identifies that the software lock is owned by a different node than the node in which said first thread is executing.

8. The method as recited in claim 7 wherein setting the local variable prevents other threads executing within the same node as the first thread from spinning on said software lock.

9. The method as recited in claim 8 further comprising the first thread changing the local variable to a different value in response to obtaining said software lock.

10. The method as recited in claim 9 wherein changing the local variable results in a third thread executing within the same node as the first thread to begin spinning on the software lock.

11. The method as recited in claim 1 further comprising:

determining whether the first thread has spun on the software lock at said slower initial rate for a predetermined limit; and

if the first thread has spun on the software lock for said predetermined limit, said first thread performing a fast spin operation to acquire said software lock that is faster than said slower initial rate.

12. The method as recited in claim 11 further comprising the first thread performing an operation to prevent threads in other nodes from initiating lock acquisition requests to the software lock.

13. A multiprocessing computer system comprising:

a plurality of nodes including a plurality of processors; and

a storage medium including instructions executable by one or more of the plurality of processors to implement a method of performing spin-lock operations in a computer system comprising;

a first thread determining a node id of an owner of a software lock;

the first thread spinning on the software lock at a first initial rate in response to determining the node id identifies the same node in which the first thread is executing; and

the first thread spinning on the software lock at a slower initial rate in response to determining the node id identifies a different node than the node in which the first thread is executing.

14. The multiprocessing computer system as recited in claim 13 wherein the method further comprises a second thread storing said node id within a storage location associated with said software lock, wherein said node id corresponds to a particular node in which said second thread is executing.

15. The multiprocessing computer system as recited in claim 14 wherein the method further comprises the second thread acquiring said software lock upon a determination that the software lock is in a free state and storing said node id within said storage location.

16. The multiprocessing computer system as recited in claim 14 wherein said first thread is executed by a first processor, and wherein said second thread is executed by a second processor.

17. The multiprocessing computer system as recited in claim 16 wherein the method further comprises the second processor executing a compare and swap instruction to cause said storage of said node id within said storage location.

18. The multiprocessing computer system as recited in claim 17 wherein the method further comprises said first processor executing a compare and swap instruction in a software loop while spinning on the software lock.

19. The multiprocessing computer system as recited in claim 13 wherein the method further comprises said first thread setting a local variable with a predetermined value in response to determining the node id identifies that the software lock is owned by a different node than the node in which said first thread is executing.

20. The multiprocessing computer system as recited in claim 19 wherein setting the local variable prevents other threads executing within the same node as the first thread from spinning on said software lock.

21. The multiprocessing computer system as recited in claim 20 wherein the method further comprises the first thread changing the local variable to a different value in response to obtaining said software lock.

22. The multiprocessing computer system as recited in claim 21 wherein changing the local variable results in a third thread executing within the same node as the first thread to begin spinning on the software lock.

23. The multiprocessing computer system as recited in claim 13 wherein the method further comprises:

determining whether the first thread has spun on the software lock at said slower initial rate for a predetermined limit; and

if the first thread has spun on the software lock for said predetermined limit, said first thread performing a fast spin operation to acquire said software lock that is faster than said slower initial rate.

24. The multiprocessing computer system as recited in claim 23 wherein the method further comprises the first thread performing an operation to prevent threads in other nodes from initiating lock acquisition requests to the software lock.

25. The multiprocessing computer system as recited in claim 13 wherein the plurality of nodes form a non-uniform memory architecture.

26. The multiprocessing computer system as recited in claim 25 wherein each of the plurality of nodes includes at least one cache memory forming a non-uniform communication architecture.

27. A computer readable medium including program instructions executable to implement a method of performing spin-lock operations in a computer system comprising:

a first thread determining a node id of an owner of a software lock;

the first thread spinning on the software lock at a first initial rate in response to determining the node id identifies the same node in which the first thread is executing; and

the first thread spinning on the software lock at a slower initial rate in response to determining the node id identifies a different node than the node in which the first thread is executing.

28. The computer readable medium as recited in claim 27 wherein the method further comprises a second thread storing said node id within a storage location associated with said software lock, wherein said node id corresponds to a particular node in which said second thread is executing.

29. The computer readable medium as recited in claim 28 wherein the method further comprises the second thread acquiring said software lock upon a determination that the software lock is in a free state and storing said node id within said storage location.

30. The computer readable medium as recited in claim 28 wherein said first thread is executed by a first processor, and wherein said second thread is executed by a second processor.

31. The computer readable medium as recited in claim 30 wherein the method further comprises the second processor executing a compare and swap instruction to cause said storage of said node id within said storage location.

32. The computer readable medium as recited in claim 31 wherein the method further comprises said first processor executing a compare and swap instruction in a software loop while spinning on the software lock.

33. The computer readable medium as recited in claim 27 wherein the method further comprises said first thread setting a local variable with a predetermined value in response to determining the node id identifies that the software lock is owned by a different node than the node in which said first thread is executing.

34. The computer readable medium as recited in claim 33 wherein setting the local variable prevents other threads executing within the same node as the first thread from spinning on said software lock.

35. The computer readable medium as recited in claim 34 wherein the method further comprises the first thread changing the local variable to a different value in response to obtaining said software lock.

36. The computer readable medium as recited in claim 35 wherein changing the local variable results in a third thread executing within the same node as the first thread to begin spinning on the software lock.

37. The computer readable medium as recited in claim 27 wherein the method further comprises:

determining whether the first thread has spun on the software lock at said slower initial rate for a predetermined limit; and

if the first thread has spun on the software lock for said predetermined limit, said first thread performing a fast spin operation to acquire said software lock that is faster than said slower initial rate.

38. The computer readable medium as recited in claim 37 wherein the method further comprises the first thread performing an operation to prevent threads in other nodes from initiating lock acquisition requests to the software lock.