Multiprocessing systems employing hierarchical spin locks

• US 7,529,844 B2
• Filed: 04/24/2003
• Issued: 05/05/2009
• Est. Priority Date: 04/26/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Radovic, Zoran, Hagersten, Erik E.
• Primary Examiner(s): Lin; Kenny S
• Assistant Examiner(s): TRUONG, LAN DAI T
• Application Number:
  US10/422,454
• Publication Number:
  US 20030236817A1
• Time in Patent Office: 2,203 Days
• Field of Search: 709/203, 709/248, 709/213, 709/217, 709/229, 717/149, 711/100
• US Class Current: 709/229
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for controlling a software lock acquirable by processors in a plurality of nodes of a multiprocessing system is disclosed. The method comprises a first processor of a first node of the plurality of nodes acquiring the lock, and the first processor selectively releasing the lock in a first state that allows other processors within the first node to acquire the lock but that prevents processors in a remote node of the plurality of nodes from obtaining the lock. In another embodiment, a method comprises a first processor of a first node attempting to acquire the lock, the first processor determining whether another processor within the same node is remotely spinning on the lock, and the first processor remotely spinning on the lock in response to determining that another processor in the same node is not remotely spinning on the software lock.

Claims

1. A method for controlling a software lock to a shared memory resource that is acquirable by processors in a plurality of nodes of a multiprocessing system, the method comprising:

a first processor of a first node of the plurality of nodes acquiring the software lock;

the first processor selectively releasing the software lock in a local free state by writing to a local software lock that allows another processor within the first node to acquire the software lock but that prevents processors in a remote node of the plurality of nodes from obtaining the software lock in response to a fairness value being in a false state and in response to an indication that the another processor in the same node attempted to acquire the software lock;

the first processor releasing the software lock in a free state that allows all processors within any of the plurality of nodes to attempt to acquire the software lock in response to the fairness value being in a false state and in response to an indication that no other processor in the same node attempted to acquire the software lock; and

the first processor also releasing the software lock in the free state in response to the fairness value being in a true state regardless of an indication that the another processor in the same node attempted to acquire the software lock.

2. The method as recited in claim 1 further comprising the first processor determining that another processor within the first node attempted to acquire the software lock.

3. The method as recited in claim 1, wherein the first processor acquiring the software lock further comprises:

the first processor checking the state of a remote lock;

the first processor determining that the state of the remote lock is free; and

the first processor changing the state of the remote lock to remote.

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

a second processor of a second node of the plurality of nodes attempting to acquire the software lock;

the second processor determining whether another processor within the second node is remotely spinning on the software lock; and

the second processor remotely spinning on the software lock in response to determining that another processor in the second node is not remotely spinning on the software lock.

5. The method as recited in claim 1 further comprising the first processor acquiring the software lock comprises writing within the local lock of the first node a thread ID of the thread executing on the first processor.

6. The method as recited in claim 1, further comprising generating a state of the fairness value each time a given processor attempts to acquire the software lock and the software lock is either held by another processor in the same node, or the software lock is held by a processor in the remote node and another processor in the same node is spinning on the software lock.

7. The method as recited in claim 5 wherein the first processor executes a swap instruction to write the thread id and to determine the state of the software lock.

8. The method as recited in claim 6, further comprising generating a state of the fairness value randomly.

9. A multiprocessing computer system comprising:

a plurality of nodes including a plurality of processors;

wherein a first processor of a first node of the plurality of nodes is configured to acquire a software lock to a shared memory resource;

wherein the first processor is configured to selectively release the software lock in a local free state by writing to a local lock that allows another processor within the first node to acquire the software lock but that prevents processors in a remote node of the plurality of nodes from obtaining the software lock in response to a the fairness value being in a false state and in response to an indication that the another processor in the same node attempted to acquire the software lock;

wherein the first processor is further configured to release the software lock in a free state that allows all processors within any of the plurality of nodes to attempt to acquire the software lock in response to the fairness value being in a false state and in response to an indication that no other processor in the same node attempted to acquire the software lock; and

wherein the first processor is further configured to release the software lock in the free state in response to the fairness value being in a true state regardless of an indication that any other processor in the same node attempted to acquire the software lock.

10. The multiprocessing computer system as recited in claim 9 wherein the first processor is configured to acquire the software lock by checking the state of a remote lock and changing the state of the remote lock to remote.

11. The multiprocessing computer system as recited in claim 9 further comprising:

a second processor of a second node of the plurality of nodes;

wherein the second processor is configured to attempt to acquire the software lock;

wherein the second processor is further configured to determine whether another processor within the second node is remotely spinning on the software lock; and

wherein the second processor is configured to remotely spin on the software lock in response to determining that another processor in the second node is not remotely spinning on the software lock.

12. The multiprocessing computer system as recited in claim 9, wherein a given processor attempting to acquire the software lock is configured to generate a state of the fairness value each time the given processor attempts to acquire the software lock and the software lock is either held by another processor in the same node, or the software lock is held by a processor in the remote node and another processor in the same node is spinning on the software lock.

13. The multiprocessing computer system as recited in claim 12, wherein the given processor is configured to generate the state of the fairness value randomly.

14. A computer readable storage including program instructions executable to implement a method for controlling a software lock to a shared memory resource, the software lock being acquirable by processors in a plurality of nodes of a multiprocessing system, wherein the method comprises:

a first processor of a first node of the plurality of nodes acquiring the software lock;

the first processor selectively releasing the software lock in a local free state that allows another processor within the first node to acquire the software lock but that prevents processors in a remote node of the plurality of nodes from obtaining the software lock in response to a fairness value being in a false state and in response to an indication that the another processor in the same node attempted to acquire the software lock;

the first processor releasing the software lock in a free state that allows all processors within in any of the plurality of nodes to attempt to acquire the software lock in response to the fairness value being in a false state and in response to an indication that no other processor in the same node attempted to acquire the software lock; and

the first processor releasing the software lock in the free state in response to the fairness value being in a true state regardless of an indication that any other processor in the same node attempted to acquire the software lock.

15. The computer readable storage recited in claim 14 wherein the first processor acquiring the software lock further comprises:

the first processor checking the state of a remote lock;

the first processor determining that the state of the remote lock is free; and

the first processor changing the state of the remote lock to remote.

16. The computer readable storage recited in claim 14 wherein the method further comprises:

a second processor of a second node of the plurality of nodes attempting to acquire the software lock;

the second processor determining whether another processor within the second node is remotely spinning on the software lock; and

the second processor remotely spinning on the software lock in response to determining that another processor in the second node is not remotely spinning on the software lock.

17. The computer readable storage recited in claim 14, wherein a given processor attempting to acquire the software lock generating a state of the fairness value each time the given processor attempts to acquire the software lock and the software lock is either held by another processor in the same node, or the software lock is held by a processor in the remote node and another processor in the same node is spinning on the software lock.

18. The computer readable storage recited in claim 17, wherein the given processor generating the state of the fairness value randomly.