Patent ID: 8838944

Claim:
A method for concurrent operation in a multithreaded computing environment, the method comprising: fetching a counter and comparing the counter to a boundary, by one or more of a plurality of synchronization primitives, wherein the plurality of synchronization primitives comprise at least: FetchAndIncrementBounded, the FetchAndIncrementBounded outputting the counter and then incrementing the counter if the counter is less than the boundary, the FetchAndIncrementBounded outputting an indication of reaching a bound of a data structure if the counter is not less than the boundary; FetchAndDecrementBounded, the FetchAndDecrementBounded outputting the counter and then decrementing the counter if the counter is greater than the boundary, the FetchAndDecrementBounded outputting an indication of reaching a bound of a data structure if the counter is not greater than the boundary; and StoreOnTwin, the StoreOnTwin setting the counter and the boundary to a given value if a value of the counter and a value of the boundary are equivalent to each other, said StoreOnTwin not changing the value of the counter or the value of the boundary if the value of the counter and the value of the boundary are not equivalent; constructing a concurrent array-based data structure, each element of the concurrent array-based data structure having a ticket lock for granting an access to the element of the concurrent array-based data structure if a thread has a corresponding ticket; and concurrently operating said concurrent array-based data structure using at least one of the plurality of synchronization primitives, the at least one of the plurality of synchronization primitives being one of the FetchAndIncrementBounded and the FetchAndDecrementBounded, wherein said concurrent array-based data structure is a double-ended queue (deque), and said step of concurrently operating comprises obtaining an index to an element for putting an object on a top of the deque by executing the FetchAndIncrementBounded, obtaining an index to an element for taking an object on the top of the deque by executing the FetchAndDecrementBounded, obtaining an index to an element for putting an object on a bottom of the deque by executing the FetchAndDecrementBounded and obtaining an index to an element for taking an element on the bottom of the deque by executing the FetchAndIncrementBounded; and wherein the StoreOnTwin resets a first pointer referencing a top of said deque and a second pointer referencing a bottom of said deque to reference a middle of the deque if the first pointer equals the second pointer.