TIERED LOCKING OF RESOURCES

• US 20140115213A1
• Filed: 03/14/2013
• Published: 04/24/2014
• Est. Priority Date: 10/19/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jacobs, Stuart Z., Larson, David A.
• Granted Patent: US 9,250,976 B2
• Time in Patent Office: Days
• US Class Current: 710/200
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

In an embodiment, a lock command is received from a thread that specifies a resource. If tier status in a nodal lock indicates the nodal lock is currently owned, an identifier of the thread is added to a nodal waiters list, and if the thread'"'"'s lock wait indicator indicates that the thread owns the nodal lock, then a successful completion status is returned for the lock command to the thread after waiting until a next tier wait indicator in the nodal lock indicates that any thread owns a global lock on the resource. If the tier status indicates no thread holds the nodal lock, the tier status is changed to indicate the nodal lock is owned, and if a global waiters and holder list is empty, an identifier of a node at which the thread executes is added to the global waiters and holder list.

Claims

1. A method comprising:

receiving, from a first thread, a lock command that specifies a resource;

if tier status in a nodal lock indicates the nodal lock is currently owned on global data, adding an identifier of the first thread to a nodal waiters list in the nodal lock, and if a lock wait indicator in the first thread indicates that the first thread owns the nodal lock on the global data, waiting until a next tier wait indicator in the nodal lock indicates that any thread owns a global lock on the resource and then returning a successful completion status for the lock command to the first thread;

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if a global waiters and holder list in the global data is empty, adding an identifier of a first node at which the first thread executes to the global waiters and holder list, and returning the successful completion status for the lock command to the first thread;

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the identifier of the first node at which the first thread executes is in the global waiters and holder list, adding the identifier of the first node at which the first thread executes to a global pending waiters list in the global data, and returning the successful completion status for the lock command to the first thread; and

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the identifier of the first node at which the first thread executes is not in the global waiters and holder list, adding the identifier of the first node at which the first thread executes to the global waiters and holder list, and returning the successful completion status for the lock command to the first thread.

2. The method of claim 1, further comprising:

If the tier status indicates that no thread owns the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the global waiters and holder list is not empty and the lock command is a try lock attempt command and the nodal waiters list is empty, changing the tier status in the nodal lock to indicate that no thread owns the nodal lock and returning a failure completion status for the lock command to the first thread.

3. The method of claim 2, further comprising:

if the tier status indicates that no thread owns the nodal on the global data, changing the tier status to indicate that the nodal lock is owned, and if the global waiters and holder list is not empty and the lock command is a try lock attempt command and the nodal waiters list is not empty, determining a next ordered nodal thread in a thread order to which to hand off the nodal lock, removing an identifier of the next ordered nodal thread from the nodal waiters list, setting a lock wait indicator in the next ordered nodal thread to indicate the next ordered nodal thread obtained the nodal lock from the first thread that issued the try lock attempt command, and returning a failure completion status for the lock command to the first thread.

4. The method of claim 2, further comprising:

receiving, from the first thread, an unlock command that specifies the resource; and

if the nodal waiters list is empty, changing the tier status to indicate the nodal lock is not held, removing the identifier of the first thread from the global waiters and holder list and if the global pending waiters list and the global waiters and holder list are empty, returning a successful completion status for the unlock command to the first thread.

5. The method of claim 4, further comprising:

if the global pending waiters list is not empty, moving identifiers of nodes from the global pending waiters list to the global waiters and holder list;

if any node other than the first node is identified in the global waiters and holder list, determined a next ordered node to which to hand off the global lock, setting a nodal next tier wait indicator at the next ordered node receiving the global lock to indicate the next ordered node owns the global lock, and returning a successful completion status for the unlock command to the first thread; and

if only the first node at which the first thread executes is identified in the global waiters and holder list, clearing the global pending waiters list.

6. The method of claim 4, further comprising:

if the nodal waiters list is not empty, determining a next ordered nodal thread to which to hand off the nodal lock, removing the next ordered nodal thread from the nodal waiters list, and if the next ordered nodal thread is after the first thread in the thread order, setting a lock wait indicator in the next ordered nodal thread to indicate that the next ordered nodal thread owns the nodal lock and the global lock and returning a successful completion status for the unlock command to the first thread; and

if the next ordered nodal thread is before the first thread in the thread order, setting the lock wait indicator in the next ordered nodal thread to indicate that the next ordered nodal thread owns the nodal lock, and if the global pending waiters list is empty, setting the next tier wait indicator for the first thread to indicate that the first thread owns the global lock and returning the successful completion status for the unlock command to the first thread.

7. The method of claim 4, further comprising:

If the global pending waiters list is not empty, moving node identifiers from the global pending waiters list to the global waiters and holders list, and if only an identifier of the first node at which the first node executes is present in the global pending waiters list, clearing the global pending waiters list, setting the next tier wait indicator for the first node at which the first thread executes to indicate that the first thread owns the global lock, and returning the successful completion status for the unlock command to the first thread.

8. A computer-readable storage medium encoded with instructions, wherein the instructions when executed comprise:

receiving, from a first thread, a lock command that specifies a resource;

if tier status in a nodal lock indicates the nodal lock is currently owned on global data, adding an identifier of the first thread to a nodal waiters list in the nodal lock, and if a lock wait indicator in the first thread indicates that the first thread owns the nodal lock on the global data, waiting until a next tier wait indicator in the nodal lock indicates that any thread owns a global lock on the resource and then returning a successful completion status for the lock command to the first thread;

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if a global waiters and holder list in the global data is empty, adding an identifier of a first node at which the first thread executes to the global waiters and holder list, and returning the successful completion status for the lock command to the first thread;

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the identifier of the first node at which the first thread executes is in the global waiters and holder list, adding the identifier of the first node at which the first thread executes to a global pending waiters list in the global data, and returning the successful completion status for the lock command to the first thread; and

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the identifier of the first node at which the first thread executes is not in the global waiters and holder list, adding the identifier of the first node at which the first thread executes to the global waiters and holder list, and returning the successful completion status for the lock command to the first thread.

9. The computer-readable storage medium of claim 8, further comprising:

if the tier status indicates that no thread owns the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the global waiters and holder list is not empty and the lock command is a try lock attempt command and the nodal waiters list is empty, changing the tier status in the nodal lock to indicate that no thread owns the nodal lock and returning a failure completion status for the lock command to the first thread.

10. The computer-readable storage medium of claim 9, further comprising:

if the tier status indicates that no thread owns the nodal on the global data, changing the tier status to indicate that the nodal lock is owned, and if the global waiters and holder list is not empty and the lock command is a try lock attempt command and the nodal waiters list is not empty, determining a next ordered nodal thread in a thread order to which to hand off the nodal lock, removing an identifier of the next ordered nodal thread from the nodal waiters list, setting a lock wait indicator in the next ordered nodal thread to indicate the next ordered nodal thread obtained the nodal lock from the first thread that issued the try lock attempt command, and returning a failure completion status for the lock command to the first thread.

11. The computer-readable storage medium of claim 9, further comprising:

receiving, from the first thread, an unlock command that specifies the resource; and

if the nodal waiters list is empty, changing the tier status to indicate the nodal lock is not held, removing the identifier of the first thread from the global waiters and holder list and if the global pending waiters list and the global waiters and holder list are empty, returning a successful completion status for the unlock command to the first thread.

12. The computer-readable storage medium of claim 11, further comprising:

if the global pending waiters list is not empty, moving identifiers of nodes from the global pending waiters list to the global waiters and holder list;

if any node other than the first node is identified in the global waiters and holder list, determined a next ordered node to which to hand off the global lock, setting a nodal next tier wait indicator at the next ordered node receiving the global lock to indicate the next ordered node owns the global lock, and returning a successful completion status for the unlock command to the first thread; and

if only the first node at which the first thread executes is identified in the global waiters and holder list, clearing the global pending waiters list.

13. The computer-readable storage medium of claim 11, further comprising:

if the nodal waiters list is not empty, determining a next ordered nodal thread to which to hand off the nodal lock, removing the next ordered nodal thread from the nodal waiters list, and if the next ordered nodal thread is after the first thread in the thread order, setting a lock wait indicator in the next ordered nodal thread to indicate that the next ordered nodal thread owns the nodal lock and the global lock and returning a successful completion status for the unlock command to the first thread; and

if the next ordered nodal thread is before the first thread in the thread order, setting the lock wait indicator in the next ordered nodal thread to indicate that the next ordered nodal thread owns the nodal lock, and if the global pending waiters list is empty, setting the next tier wait indicator for the first thread to indicate that the first thread owns the global lock and returning the successful completion status for the unlock command to the first thread.

14. The computer-readable storage medium of claim 11, further comprising:

If the global pending waiters list is not empty, moving node identifiers from the global pending waiters list to the global waiters and holders list, and if only an identifier of the first node at which the first node executes is present in the global pending waiters list, clearing the global pending waiters list, setting the next tier wait indicator for the first node at which the first thread executes to indicate that the first thread owns the global lock, and returning the successful completion status for the unlock command to the first thread.

15. A computer comprising:

a processor; and

memory communicatively coupled to the processor, wherein the memory is encoded with instructions, wherein the instructions when executed by the processor comprise

receiving, from a first thread, a lock command that specifies a resource,

if tier status in a nodal lock indicates the nodal lock is currently owned on global data, adding an identifier of the first thread to a nodal waiters list in the nodal lock, and if a lock wait indicator in the first thread indicates that the first thread owns the nodal lock on the global data, waiting until a next tier wait indicator in the nodal lock indicates that any thread owns a global lock on the resource and then returning a successful completion status for the lock command to the first thread,

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if a global waiters and holder list in the global data is empty, adding an identifier of a first node at which the first thread executes to the global waiters and holder list, and returning the successful completion status for the lock command to the first thread,

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the identifier of the first node at which the first thread executes is in the global waiters and holder list, adding the identifier of the first node at which the first thread executes to a global pending waiters list in the global data, and returning the successful completion status for the lock command to the first thread,

if the tier status indicates no thread holds the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the identifier of the first node at which the first thread executes is not in the global waiters and holder list, adding the identifier of the first node at which the first thread executes to the global waiters and holder list, and returning the successful completion status for the lock command to the first thread, and

if the tier status indicates that no thread owns the nodal lock on the global data, changing the tier status to indicate the nodal lock is owned, and if the global waiters and holder list is not empty and the lock command is a try lock attempt command and the nodal waiters list is empty, changing the tier status in the nodal lock to indicate that no thread owns the nodal lock and returning a failure completion status for the lock command to the first thread.

16. The computer of claim 15, wherein the instructions further comprise:

if the tier status indicates that no thread owns the nodal on the global data, changing the tier status to indicate that the nodal lock is owned, and if the global waiters and holder list is not empty and the lock command is a try lock attempt command and the nodal waiters list is not empty, determining a next ordered nodal thread in a thread order to which to hand off the nodal lock, removing an identifier of the next ordered nodal thread from the nodal waiters list, setting a lock wait indicator in the next ordered nodal thread to indicate the next ordered nodal thread obtained the nodal lock from the first thread that issued the try lock attempt command, and returning a failure completion status for the lock command to the first thread.

17. The computer of claim 15, wherein the instructions further comprise:

receiving, from the first thread, an unlock command that specifies the resource; and

if the nodal waiters list is empty, changing the tier status to indicate the nodal lock is not held, removing the identifier of the first thread from the global waiters and holder list and if the global pending waiters list and the global waiters and holder list are empty, returning a successful completion status for the unlock command to the first thread.

18. The computer of claim 17, wherein the instructions further comprise:

if the global pending waiters list is not empty, moving identifiers of nodes from the global pending waiters list to the global waiters and holder list;

if any node other than the first node is identified in the global waiters and holder list, determined a next ordered node to which to hand off the global lock, setting a nodal next tier wait indicator at the next ordered node receiving the global lock to indicate the next ordered node owns the global lock, and returning a successful completion status for the unlock command to the first thread; and

if only the first node at which the first thread executes is identified in the global waiters and holder list, clearing the global pending waiters list.

19. The computer of claim 17, wherein the instructions further comprise:

if the nodal waiters list is not empty, determining a next ordered nodal thread to which to hand off the nodal lock, removing the next ordered nodal thread from the nodal waiters list, and if the next ordered nodal thread is after the first thread in the thread order, setting a lock wait indicator in the next ordered nodal thread to indicate that the next ordered nodal thread owns the nodal lock and the global lock and returning a successful completion status for the unlock command to the first thread; and

if the next ordered nodal thread is before the first thread in the thread order, setting the lock wait indicator in the next ordered nodal thread to indicate that the next ordered nodal thread owns the nodal lock, and if the global pending waiters list is empty, setting the next tier wait indicator for the first thread to indicate that the first thread owns the global lock and returning the successful completion status for the unlock command to the first thread.

20. The computer of claim 17, wherein the instructions further comprise:

If the global pending waiters list is not empty, moving node identifiers from the global pending waiters list to the global waiters and holders list, and if only an identifier of the first node at which the first node executes is present in the global pending waiters list, clearing the global pending waiters list, setting the next tier wait indicator for the first node at which the first thread executes to indicate that the first thread owns the global lock, and returning the successful completion status for the unlock command to the first thread.