Loading...
Please wait, while we are loading the content...
Similar Documents
Dynamic-sized lockfree data structures
| Content Provider | Semantic Scholar |
|---|---|
| Author | Herlihy, Maurice Luchangco, Victor Martin, Paul Antoine Moir, Mark S. |
| Copyright Year | 2002 |
| Abstract | We address the problem of integrating lockfree shared data structures with standard dynamic allocation mechanisms (such as malloc and free). We have two main contributions. The first is the design and experimental analysis of two dynamic-sized lockfree FIFO queue implementations, which extend Michael and Scott's previous implementation by allowing unused memory to be freed. We compare our dynamic-sized implementations to the original on 16-processor and 64-processor multiprocessors. Our experimental results indicate that the performance penalty for making the queue dynamic-sized is modest, and is negligible when contention is not too high. These results were achieved by applying a solution to the Repeat Offender Problem (ROP), which we recently posed and solved. Our second contribution is another application of ROP solutions. Specifically, we show how to use any ROP solution to achieve a general methodology for transforming lockfree data structures that rely on garbage collection into ones that use explicit storage reclamation. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://research.sun.com/techrep/2002/smli_tr-2002-110.pdf |
| Alternate Webpage(s) | http://www.sunlabs.com/techrep/2002/smli_tr-2002-110.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
