Efficiency sequencer for multiple concurrently-executing threads of execution

摘要

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.

主权项

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 the ticket in the waiters list corresponds to a thread; 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 by identifying a threshold ticket value which is the 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; removing, by the computer system, the ticket from the waiters list using a single atomic operation by one of setting the waiters list head element to refer to a next element in the waiters list after a threshold element having the threshold ticket value, and setting the waiters list head element to refer to another ticket in the waiters list; and causing, by the computer system, a thread associated with the ticket to proceed.