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.
Cited By
- Solomon D and Morrison A Efficiently reclaiming memory in concurrent search data structures while bounding wasted memory Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (191-204)
- Boehm H An almost non-blocking stack Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, (40-49)
- Hendler D and Shavit N Work dealing Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, (164-172)
Recommendations
Software transactional memory for dynamic-sized data structures
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computingWe propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is ...
Nonblocking memory management support for dynamic-sized data structures
Conventional dynamic memory management methods interact poorly with lock-free synchronization. In this article, we introduce novel techniques that allow lock-free data structures to allocate and free memory dynamically using any thread-safe memory ...
Wait-free Dynamic Transactions for Linked Data Structures
PMAM'19: Proceedings of the 10th International Workshop on Programming Models and Applications for Multicores and ManycoresTransactional data structures support threads executing a sequence of operations atomically. Dynamic transactions allow operands to be generated on the fly and allows threads to execute code in between the operations of a transaction, in contrast to ...