# US 10,310,915 B2 · Efficient sequencer for multiple concurrently-executing threads of execution > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,310,915 B2 - Document ID: US10310915B2 - Status: Granted - Kind: B2 - Application number: 15/401,422 - Filed: 2017-01-09 - Published: 2017-05-04 - Granted: 2019-06-04 - Earliest claimed: 2011-12-29 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: Oleksandr Otenko - Web page: https://patentgrep.com/patent/US10310915B2 ## CPC - G06F 9/526: {Mutual exclusion algorithms} - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system} - G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques are disclosed for efficiently sequencing operations performed in multiple threads of execution in a computer system. In one set of embodiments, sequencing is performed by receiving an instruction to advance a designated next ticket value, incrementing the designated next ticket value in response to receiving the instruction, searching a waiters list of tickets for an element having the designated next ticket value, wherein searching does not require searching the entire waiters list, and the waiters list is in a sorted order based on the values of the tickets, and removing the element having the designated next ticket value from the list using a single atomic operation. The element may be removed by setting a waiters list head element, in a single atomic operation, to refer to an element in the list having a value based upon the designated next ticket value. ## Claims ### Claim 1 A method comprising: receiving, by a computer system, an instruction to advance a designated next ticket value; incrementing, by the computer system, the designated next ticket value in response to receiving the instruction; inserting, by the computer system, a ticket into a waiters list of tickets stored in a memory of the computer system to preserve a sorted order of a plurality of tickets in the waiters list using a value of the ticket provided by a waiter associated with the ticket, wherein tickets having a greater ticket value are inserted into the waiters list before tickets having a lesser value, and wherein inserting the ticket into the waiters list comprises: inserting, by the computer system, a new list element in the waiters list such that an existing list element is a next element after the new list element; and in response to insertion of the new list element failing because of an unexpected value of a list element next field, searching, by the computer system, the waiters list starting at the waiters list head element for the existing list element associated with an existing ticket value, and retrying the insertion; searching, by the computer system, a part of the waiters list in the memory identifying the ticket as having the designated next ticket value without searching the entire waiters list; and removing, by the computer system, the ticket from the waiters list using a single atomic operation. ### Claim 2 (depends on 1) The method of claim 1, wherein removing the ticket comprises: setting, by the computer system, a waiters list head element, in a single atomic operation, to refer to another ticket in the waiters list. ### Claim 3 (depends on 1) The method of claim 1, wherein searching the part of the waiters list in the memory comprises: identifying, by the computer system, a threshold ticket value which is a greatest ticket value in the waiters list that is less than or equal to the designated next ticket value, wherein the searching starts at a waiters list head element; and wherein removing the ticket comprises setting, by the computer system, the waiters list head element, in a single atomic operation, to refer to a next element in the waiters list after a threshold element having the threshold ticket value. ### Claim 4 (depends on 1) The method of claim 1, wherein the tickets in the waiters list correspond to threads, the method further comprising: causing, by the computer system, a thread associated with the ticket to proceed. ### Claim 5 (depends on 1) The method of claim 1, further comprising: receiving, by the computer system, a request for a resource, the request including the value of the ticket provided by the waiter; and causing, by the computer system, the request to be blocked. ### Claim 6 (depends on 5) The method of claim 5, wherein inserting the ticket into the waiters list further comprises: before inserting the new list element in the waiters list, searching, by the computer system, the waiters list, starting at a waiters list head element, for the existing list element associated with an existing ticket value that is greater than the value of the ticket; associating, by the computer system, the value of the ticket with the new list element. ### Claim 7 (depends on 5) The method of claim 5, wherein the request is associated with a thread of execution, the method further comprising: associating, by the computer system, the thread of execution with the value of the ticket in the waiters list. ### Claim 8 (depends on 1) The method according to claim 1, wherein the designated next ticket value corresponds to a next thread allowed to access a shared resource. ### Claim 9 A system comprising: a memory storing a designated next ticket value and a waiters list of tickets; and a hardware processor configured to: receive, by a computer system, an instruction to advance a designated next ticket value; increment, by the computer system, the designated next ticket value in response to receiving the instruction; insert, by the computer system, a ticket into a waiters list of tickets stored in a memory of the computer system to preserve a sorted order of a plurality of tickets in the waiters list using a value of the ticket provided by a waiter associated with the ticket, wherein tickets having a greater ticket value are inserted into the waiters list before tickets having a lesser value, wherein inserting the ticket into the waiters list comprises: inserting, by the computer system, a new list element in the waiters list such that an existing list element is a next element after the new list element; and in response to insertion of the new list element failing because of an unexpected value of a list element next field, searching, by the computer system, the waiters list starting at the waiters list head element for the existing list element associated with an existing ticket value, and retrying the insertion; search, by the computer system, a part of the waiters list in the memory identifying the ticket as having the designated next ticket value without searching the entire waiters list; and remove, by the computer system, the ticket from the waiters list using a single atomic operation. ### Claim 10 (depends on 9) The system of claim 9, wherein searching the part of the waiters list in the memory comprises: identifying, by the computer system, a threshold ticket value which is a greatest ticket value in the waiters list that is less than or equal to the designated next ticket value, wherein the searching starts at a waiters list head element; and wherein removing the ticket comprises setting, by the computer system, the waiters list head element, in a single atomic operation, to refer to a next element in the waiters list after a threshold element having the threshold ticket value. ### Claim 11 (depends on 9) The system of claim 9, further comprising: receiving, by the computer system, a request for a resource, the request including the value of the ticket provided by the waiter; and causing, by the computer system, the request to be blocked. ### Claim 12 (depends on 9) The system of claim 9, wherein inserting the ticket into the waiters list comprises: before inserting the new list element in the waiters list, searching, by the computer system, the waiters list, starting at a waiters list head element, for the existing list element associated with an existing ticket value that is greater than the value of the ticket; and associating, by the computer system, the value of the ticket with the new list element. ### Claim 13 A non-transitory computer-readable memory storing instructions which, when executed by one or more processors, cause the one or more processors to: receive, by a computer system, an instruction to advance a designated next ticket value; increment, by the computer system, the designated next ticket value in response to receiving the instruction; insert, by the computer system, a ticket into a waiters list of tickets stored in a memory of the computer system to preserve a sorted order of a plurality of tickets in the waiters list using a value of the ticket provided by a waiter associated with the ticket, wherein tickets having a greater ticket value are inserted into the waiters list before tickets having a lesser value, wherein inserting the ticket into the waiters list comprises: inserting, by the computer system, a new list element in the waiters list such that an existing list element is a next element after the new list element; and in response to insertion of the new list element failing because of an unexpected value of a list element next field, searching, by the computer system, the waiters list starting at the waiters list head element for the existing list element associated with an existing ticket value, and retrying the insertion; search, by the computer system, a part of the waiters list in the memory identifying the ticket as having the designated next ticket value without searching the entire waiters list; and remove, by the computer system, the ticket from the waiters list using a single atomic operation. ### Claim 14 (depends on 13) The computer-readable memory of claim 13, wherein searching the part of the waiters list in the memory comprises: identifying, by the computer system, a threshold ticket value which is a greatest ticket value in the waiters list that is less than or equal to the designated next ticket value, wherein the searching starts at a waiters list head element; and wherein removing the ticket comprises setting, by the computer system, the waiters list head element, in a single atomic operation, to refer to a next element in the waiters list after a threshold element having the threshold ticket value. ### Claim 15 (depends on 13) The computer-readable memory of claim 13, further comprising: receiving, by the computer system, a request for a resource, the request including the value of the ticket provided by the waiter; and causing, by the computer system, the request to be blocked. ### Claim 16 (depends on 13) The computer-readable memory of claim 13, wherein inserting the ticket into the waiters list comprises: before inserting the new list element in the waiters list, searching, by the computer system, the waiters list, starting at a waiters list head element, for the existing list element associated with an existing ticket value that is greater than the value of the ticket; and associating, by the computer system, the value of the ticket with the new list element.