LIPIcs.DISC.2020.51.pdf
- Filesize: 363 kB
- 3 pages
Document
Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time
Authors
Guy E. Blelloch 
,
Yuanhao Wei
-
Part of:
Volume:
34th International Symposium on Distributed Computing (DISC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-10-07
File
Document Identifiers
Author Details
Cite AsGet BibTex
Guy E. Blelloch and Yuanhao Wei. Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.51
https://doi.org/10.4230/LIPIcs.DISC.2020.51
Abstract
We describe an algorithm for supporting allocation and free for fixed-sized blocks, for p asynchronous processors, with O(1) worst-case time per operation, Θ(p²) additive space overhead, and using only single-word read, write, and CAS. While many algorithms rely on having constant-time fixed-size allocate and free, we present the first implementation of these two operations that is constant time with reasonable space overhead.
Subject Classification
ACM Subject Classification
- Computing methodologies → Concurrent algorithms
Keywords
- malloc
- free
- fixed-size
- concurrent
- constant time
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Zahra Aghazadeh and Philipp Woelfel. Upper bounds for boundless tagging with bounded objects. In International Symposium on Distributed Computing (DISC), pages 442-457, 2016.
- Guy E. Blelloch and Yuanhao Wei. Concurrent reference counting and resource management in wait-free constant time, 2020. URL: http://arxiv.org/abs/2002.07053.
-
Guy E Blelloch and Yuanhao Wei. LL/SC and atomic copy: Constant time, space efficient implementations using only pointer-width CAS. In International Symposium on Distributed Computing (DISC), 2020.
-
Panagiota Fatourou and Nikolaos D Kallimanis. A highly-efficient wait-free universal construction. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 325-334, 2011.
-
Anders Gidenstam, Marina Papatriantafilou, and Philippas Tsigas. NBmalloc: Allocating memory in a lock-free manner. Algorithmica, 58(2):304-338, 2010.
-
Maged M Michael. Scalable lock-free dynamic memory allocation. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 35-46, 2004.
-
Ruslan Nikolaev and Binoy Ravindran. Universal wait-free memory reclamation. In ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), page 130–143, 2020.
-
Sangmin Seo, Junghyun Kim, and Jaejin Lee. SFMalloc: A lock-free and mostly synchronization-free dynamic memory allocator for manycores. In International Conference on Parallel Architecture and Compilation Techniques (PACT), pages 253-263, 2011.
-
Håkan Sundell. Wait-free reference counting and memory management. In International Parallel and Distributed Processing Symposium (IPDPS), 2005.