Almost fair busy lock

Patent metadata

Field	Value
Publication number	US-10169107-B2
Application number	US-201715613673-A
Country	US
Kind code	B2
Filing date	Jun 5, 2017
Priority date	Nov 18, 2014
Publication date	Jan 1, 2019
Grant date	Jan 1, 2019

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.

First claim

What is claimed is:

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.

Assignees

• IBM

Inventors

• Greco Marco

Classifications

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/526 Primary

  Mutual exclusion algorithms · CPC title

• G06F9/4843

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F9/485

  Task life-cycle, e.g. stopping, restarting, resuming execution (G06F9/4881 takes precedence) · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title