ALMOST FAIR BUSY LOCK

• US 20160139966A1
• Filed: 09/22/2015
• Published: 05/19/2016
• Est. Priority Date: 11/18/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Greco, Marco
• Granted Patent: US 9,697,055 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Managing exclusive control of a shareable resource includes publishing a claim non atomically to a lock by a thread that is next to own the lock in an ordered set of threads that have requested to own the lock. The claim includes a structure capable of being read and written only in a single memory access. A determination is made of whether the next owning thread has been pre-empted. Responsive to the determination, the next owning thread of the lock acquires the lock if the next owning thread has not been pre-empted and retries acquisition of the lock if the next owning thread has been pre-empted. Responsive to the next owning thread being pre-empted, a subsequent owning thread acquires the lock unfairly and atomically, consistently modifies the lock such that a next lock owner can determine that the next lock owner has been preempted.

Claims

1. A method for managing exclusive control of a shareable resource, the method comprising:

publishing a claim non atomically to a lock by a thread that is next to own the lock in an ordered set of threads that have requested to own the lock, the claim comprising a structure capable of being read and written only in a single memory access;

determining whether the next owning thread has been pre-empted;

responsive to the determination, the next owning thread of the lock acquiring the lock if the next owning thread has not been pre-empted and retrying acquisition of the lock if the next owning thread has been pre-empted; and

responsive to the next owning thread being pre-empted, a subsequent owning thread acquiring the lock unfairly and atomically, consistently modifying the lock such that a next lock owner can determine that the next lock owner has been preempted.

2. The method of claim 1, wherein:

the ordered set of threads comprises tickets, each thread requesting ownership of the lock obtaining a ticket; and

the claim comprises an identifier of the ticket obtained by the next owning thread, and an indication that the next owning thread is claiming the lock.

3. The method of claim 2, further comprising:

comparing the obtained next owning thread ticket with a current ticket and responsive to a match between the obtained next owning thread ticket and the current ticket, non-atomically acquiring the lock.

4. The method of claim 1, wherein the claim structure is a union.

5. The method of claim 1, wherein responsive to a determination that the next owning thread has been pre-empted, the next owning thread cancels requesting ownership of the lock.

6. A system for managing exclusive control of a shareable resource between a plurality of concurrently executing threads, comprising:

a lock for controlling access to the shareable resource, the lock maintaining an ordered set of threads requesting ownership of the lock;

a claim structure, capable of being read and written only in a single memory access, non-atomically published by a next owning thread, in the ordered set of threads, making a claim to the lock; and

one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage devices, and program instructions stored on at least one of the one or more storage devices for execution by at least one of the one or more processors via at least one of the one or more memories, wherein the system is capable of performing a method comprising;

the next owning thread of the lock, after publishing the claim, determining whether the next owning thread has been pre-empted;

responsive to determining whether the next owning thread has been pre-empted, the next owning thread of the lock acquiring the lock if the next owning thread has not been pre-empted and retrying acquisition of the lock if the next owning thread has been pre-empted; and

responsive to the next owning thread being pre-empted, a subsequent owning thread acquiring the lock unfairly and atomically, consistently modifying the lock such that a next lock owner can determine that the next lock owner has been preempted.

7. The system of claim 6, wherein:

the ordered set of threads comprises tickets, each thread requesting ownership of the lock obtaining a ticket; and

the claim comprises an identifier of the ticket obtained by the next owning thread, and an indication that the next owning thread is claiming the lock.

8. The system of claim 7, further comprising:

comparing the obtained next owning thread ticket with a current ticket and responsive to a match between the obtained next owning thread ticket and the current ticket, the next owning thread non-atomically acquiring the lock.

9. The system of claim 6, wherein responsive to the next owning thread being pre-empted, the next owning thread cancels requesting ownership of the lock.

10. The system as claimed in claim 6, wherein the claim structure is a union.

11. The computer program product for managing exclusive control of a shareable resource, the computer program product comprising:

one or more computer-readable storage devices and program instructions stored on at least one of the one or more tangible storage devices, the program instructions executable by a processor, the program instructions comprising;

program instructions to publish a claim non atomically to a lock by a thread that is next to own the lock in an ordered set of threads that have requested to own the lock, the claim comprising a structure capable of being read and written only in a single memory access;

program instructions to determine whether the next owning thread has been pre-empted;

responsive to the determination, program instructions to the next owning thread of the lock to acquire the lock if the next owning thread has not been pre-empted and to retry acquisition of the lock if the next owning thread has been pre-empted; and

responsive to the next owning thread being pre-empted, program instructions to a subsequent owning thread to acquire the lock unfairly and atomically, consistently modifying the lock such that a next lock owner can determine that the next lock owner has been preempted.

12. The computer program product of claim 11, wherein:

the ordered set of threads comprises tickets, each thread requesting ownership of the lock obtaining a ticket; and

the claim comprises an identifier of the ticket obtained by the next owning thread, and an indication that the next owning thread is claiming the lock.

13. The computer program product of claim 12, further comprising:

program instructions to compare the obtained next owning thread ticket with a current ticket and responsive to a match between the obtained next owning thread ticket and the current ticket, non-atomically acquiring the lock.

14. The computer program product of claim 11, wherein the claim structure is a union.

15. The computer program product of claim 11, further comprising:

wherein responsive to a determination that the next owning thread has been pre-empted, program instructions associated with the next owning thread to cancel requesting ownership of the lock.