US 2026/0219962 A1 · Ticket-Based Semaphores with Enhanced Waiting

Abstract

A computer comprising one or more processors and memory may implement multiple threads that perform synchronization operations using a semaphore comprising an allocation field and a grant field. Upon entry to a semaphore wait operation, a thread allocates a ticket by atomically copying a ticket value contained in the allocation field and incrementing the allocation field. The thread computes a difference between the allocated ticket to the grant field representing a number of waiting threads. If the number is above the threshold, the thread enters a long term wait operation comprising determining a location for long term wait value and waiting on changes to that value. If the number is below the threshold or the long term wait operation is complete, the thread waits for the grant value to equal the ticket to complete waiting on the semaphore.

Claims20

Dependent claims

A computer-implemented method, comprising:

waiting for a semaphore, by a thread of a plurality of threads executing on one or more processors, comprising:
executing an atomic fetch-and-add operation to allocate a waiting position for the semaphore;
and
waiting until a difference value indicates that waiting for the semaphore is complete, the difference value determined as a difference between the waiting position and a grant value of the semaphore.

1 more element

One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors cause the one or more processors to perform:

waiting for a semaphore, by a thread of a plurality of threads executing on one or more processors, comprising:
executing an atomic fetch-and-add operation to allocate a waiting position for the semaphore;
and
waiting until a difference value indicates that waiting for the semaphore is complete, the difference value determined as a difference between the waiting position and a grant value of the semaphore.

1 more element

A system, comprising:

one or more processors and a memory, the memory comprising program instructions executable by the one or more processors to wait for a semaphore by a thread of a plurality of threads, wherein to wait for the semaphore the thread is configured to:
execute an atomic fetch-and-add operation to allocate a waiting position for the semaphore;
and
wait until a difference value indicates that waiting for the semaphore is complete, the difference value determined as a difference between the waiting position and a grant value of the semaphore.

1 more element

Dependencies are inferred from the claim text.

Ticket-Based Semaphores with Enhanced Waiting

Life of this patent

Ticket-Based Semaphores with Enhanced Waiting

Life of this patent

Abstract

Claims20