Lock free reference counting
US6993770B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 18, 2001 |
| Grant date | Jan 31, 2006 |
| Priority date | — |
| Expiry date | Jan 30, 2023 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99947
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.