Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive
US7539849B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 11, 2000 |
| Grant date | May 26, 2009 |
| Priority date | — |
| Expiry date | Apr 11, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/544
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An array-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.