# US 11,442,730 B2 · Ticket locks with enhanced waiting > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,730 B2 - Document ID: US11442730B2 - Status: Granted - Kind: B2 - Application number: 16/572,532 - Filed: 2019-09-16 - Published: 2020-03-26 - Granted: 2022-09-13 - Earliest claimed: 2018-09-21 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: David Dice; Alex Kogan - Web page: https://patentgrep.com/patent/US11442730B2 ## CPC - G06F 9/3009: {Thread control instructions} - G06F 9/3802: {Instruction prefetching} - G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores - G06F 9/526: {Mutual exclusion algorithms} - G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches - G06F 13/1663: {Access to shared memory} - G06F 13/1689: {Synchronisation and timing concerns (synchronisation on a memory bus G06F13/4234)} - G06F 2212/60: Details of cache memory - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computer comprising one or more processors and memory may implement multiple threads that perform a lock operation using a data structure comprising an allocation field and a grant field. Upon entry to a lock operation, a thread allocates a ticket by atomically copying a ticket value contained in the allocation field and incrementing the allocation field. The thread compares the allocated ticket to the grant field. If they are unequal, the thread determines 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 indicate that the lock is allocated. ## Claims ### Claim 1 A method comprising: performing, by a thread of a plurality of threads executed on one or more processors, an operation to allocate a lock for exclusive access to a resource, comprising: allocating a ticket representing a position for allocating the lock; determining a number of threads of the plurality of threads waiting to allocate the lock; and responsive to the determined number of threads waiting to allocate the lock exceeding a threshold: selecting a location of a long term wait value, wherein the location of the long term wait value is different from a location of a grant value indicating a value of a ticket currently holding the lock; performing a long term wait operation comprising waiting for the long term wait value at the selected location to indicate that the number of threads waiting on the lock no longer exceeds the threshold; and performing a wait operation comprising waiting for the grant value to equal a value of the allocated ticket. ### Claim 2 (depends on 1) The method of claim 1, the allocating the ticket representing the position for allocating the lock comprising executing an atomic fetch-and-add instruction on a next ticket field, wherein the atomic fetch-and-add instruction comprises atomically setting a value of the allocated ticket to a value fetched from the next ticket field and subsequently incrementing the next ticket field. ### Claim 3 (depends on 1) The method of claim 1, the determining the number of threads of the plurality of threads waiting to allocate the lock further comprising computing a difference between the grant value and the value of the allocated ticket. ### Claim 4 (depends on 1) The method of claim 1, the selecting the location of the long term wait value comprising selecting a long term grant location associated with the lock. ### Claim 5 (depends on 1) The method of claim 1, the selecting the location of the long term wait value comprising selecting a location from a plurality of wait locations based at least in part on a result of a hash operation performed on the value of the allocated ticket. ### Claim 6 (depends on 5) The method of claim 5, wherein the one or more processors comprise one or more memory caches, and wherein the hash operation performed on the value of the allocated ticket comprises distributing consecutive values of tickets to respective wait locations associated with respective different cache lines. ### Claim 7 (depends on 1) The method of claim 1, further comprising: performing, by the thread of the plurality of threads executed on the one or more processors, an operation to release the lock for exclusive access to the resource, comprising incrementing the grant value. ### Claim 8 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: executing, by a thread of a plurality of threads, an operation to allocate a lock for exclusive access to a resource, comprising: allocating a ticket representing a position for allocating the lock; determining a number of threads of the plurality of threads waiting to allocate the lock; and responsive to the determined number of threads waiting to allocate the lock exceeding a threshold: selecting a location of a long term wait value, wherein the location of the long term wait value is different from a location of a grant value indicating a ticket value currently holding the lock; performing a long term wait operation comprising waiting for the long term wait value at the selected location to indicate that the number of threads waiting on the lock no longer exceeds the threshold; and performing a wait operation comprising waiting for the grant value to equal a value of the allocated ticket. ### Claim 9 (depends on 8) The one or more non-transitory computer-accessible storage media of claim 8, the allocating the ticket representing the position for allocating the lock comprising executing an atomic fetch-and-add instruction on a next ticket field, wherein the atomic fetch-and-add instruction comprises atomically setting a value of the ticket to a value fetched from the next ticket field and subsequently incrementing the next ticket field. ### Claim 10 (depends on 8) The one or more non-transitory computer-accessible storage media of claim 8, the determining the number of threads of the plurality of threads waiting to allocate the lock further comprising computing a difference between the grant value and the value of the allocated ticket. ### Claim 11 (depends on 8) The one or more non-transitory computer-accessible storage media of claim 8, the selecting the location of the long term wait value comprising selecting a long term grant location associated with the lock. ### Claim 12 (depends on 8) The one or more non-transitory computer-accessible storage media of claim 8, the selecting the location of the long term wait value comprising selecting a location from a plurality of wait locations based at least in part on a result of a hash operation performed on the value of the allocated ticket. ### Claim 13 (depends on 12) The one or more non-transitory computer-accessible storage media of claim 12, wherein the one or more processors comprise one or more memory caches, and wherein the hash operation performed on the value of the allocated ticket comprises distributing consecutive values of tickets to respective wait locations associated with respective different cache lines. ### Claim 14 (depends on 8) The one or more non-transitory computer-accessible storage media of claim 8, the program instructions that when executed on or across one or more processors cause the one or more processors to further perform: executing, by the thread of the plurality of threads, an operation to release the lock for exclusive access to the resource, comprising incrementing the grant value. ### Claim 15 A system, comprising: one or more processors and a memory, the memory comprising program instructions executable by the one or more processors to perform, by a thread of a plurality of threads, an operation to allocate a lock, the operation to allocate the lock configured to: allocate a ticket representing a position for allocating the lock; determine a number of threads of the plurality of threads waiting to allocate the lock; and responsive to the determined number of threads waiting to allocate the lock exceeding a threshold: select a location of a long term wait value, wherein the location of the long term wait value is different from a location of a grant value indicating a ticket value currently holding the lock; perform a long term wait operation comprising waiting for the long term wait value at the selected location to indicate that the number of threads waiting on the lock no longer exceeds the threshold; and perform a wait operation comprising waiting for the grant value to equal a value of the allocated ticket. ### Claim 16 (depends on 15) The system of claim 15, wherein to allocate the ticket representing the position for allocating the lock, the operation to allocate the lock configured to execute an atomic fetch-and-add instruction on a next ticket field, the atomic fetch-and-add instruction configured to set the ticket value to a value fetched from the next ticket field and subsequently increment the next ticket field. ### Claim 17 (depends on 15) The system of claim 15, wherein to determine the number of threads of the plurality of threads waiting to allocate the lock, the operation to allocate the lock configured to compute the difference between the grant value and the value of the allocated ticket. ### Claim 18 (depends on 15) The system of claim 15, wherein to select the location of the long term wait value, the operation to allocate the lock configured to select a long term grant location associated with the lock. ### Claim 19 (depends on 15) The system of claim 15, wherein to select the location of the long term wait value, the operation to allocate the lock configured to select a location from a plurality of wait locations based at least in part on a result of a hash operation performed on the value of the allocated ticket. ### Claim 20 (depends on 19) The system of claim 19, wherein the one or more processors comprise one or more memory caches, and wherein the hash operation is configured to distribute consecutive values of tickets to respective wait locations associated with respective different cache lines.