Almost fair busy lock

• US 10,169,107 B2
• Filed: 06/05/2017
• Issued: 01/01/2019
• Est. Priority Date: 11/18/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Greco, Marco
• Primary Examiner(s): Swift, Charles M
• Application Number:
  US15/613,673
• Publication Number:
  US 20170269973A1
• Time in Patent Office: 575 Days
• 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

The present invention provides a method, a system, and a computer program product of preventing thread monitoring preemptions in an almost fair busy lock. In an exemplary embodiment, the method, the system, and the computer program product include (1) publishing a current state of a lock and a claim non-atomically to the lock by a next owning thread, the claim comprising a structure capable of being read and written only in a single memory access, (2) obtaining a ticket, where the claim comprises an identifier of a ticket obtained by the next owning thread, and an indication that the next owning thread is claiming the lock; (3) comparing the ticket obtained by the next owning thread with a current ticket; (4) preventing thread monitoring preemptions; and (5) responsive to a match between the ticket obtained by the next owning thread and the current ticket, non-atomically acquiring the lock.

Claims

1. A method comprising:

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

obtaining, by each thread in the ordered set of threads, a ticket,

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

comparing the ticket obtained by the next owning thread with a current ticket;

responsive to a match between the ticket obtained by the next owning thread and the current ticket, preventing thread monitoring preemptions; and

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

2. The method of claim 1, further comprising waiting, by the next owning thread, for the lock to be released.

3. The method of claim 2, wherein the comparing is performed during the waiting.

4. The method of claim 2, wherein the waiting occurs at the same time as a scribbling of the lock.

5. The method of claim 2 further comprising:

in response to the waiting, entering, by the next owning thread, a tight loop during the waiting; and

in response to the entering, inspecting, by the thread, the lock until the lock is free.

6. The method of claim 2, in response to the waiting, queuing, by the next owning thread, the next owning thread in a linked list of waiting threads.

7. The method of claim 6, in response to the queuing, waiting, by the next owning thread, for the next owning thread to be woken up by a lock owner once the lock is available,

wherein the waiting comprises, suspending, by the next owning thread, execution of the next owning thread.

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

9. The method of claim 1, wherein each thread in an ordered set of threads has requested to own the lock.

10. A system comprising:

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

a claim, 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,

obtaining, by each thread in the ordered set of threads, a ticket,

wherein the claim comprises an identifier of a ticket obtained by the next owning thread, and an indication that the next owning thread is claiming 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 computer-readable tangible 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,

after publishing a current state of the lock and the claim, comparing the ticket obtained by the next owning thread with a current ticket,

responsive to a match between the ticket obtained by the next owning thread and the current ticket, preventing thread monitoring preemptions, and

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

11. The system as claimed in claim 10, further comprising waiting, by the next owning thread, for the lock to be released.

12. The system as claimed in claim 11, wherein the comparing is performed during the waiting.

13. The system as claimed in claim 11, wherein the waiting occurs at the same time as a scribbling of the lock.

14. A computer program product, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:

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

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

comparing the ticket obtained by the next owning thread with a current ticket;

responsive to a match between the ticket obtained by the next owning thread and the current ticket, preventing thread monitoring preemptions; and

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

15. The computer program product of claim 14, further comprising waiting, by the next owning thread, for the lock to be released.

16. The computer program product of claim 15, wherein the comparing is performed during the waiting.

17. The computer program product of claim 15, wherein the waiting occurs at the same time as a scribbling of the lock.