arXiv Open Access 2020

Concurrent Fixed-Size Allocation and Free in Constant Time

Guy E. Blelloch Yuanhao Wei

Lihat Sumber

Abstrak

Our goal is to efficiently solve the dynamic memory allocation problem in a concurrent setting where processes run asynchronously. On $p$ processes, we can support allocation and free for fixed-sized blocks with $O(1)$ worst-case time per operation, $Θ(p^2)$ 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.

Topik & Kata Kunci

cs.DC

Penulis (2)

Guy E. Blelloch

Yuanhao Wei

Format Sitasi

APA MLA BibTeX

Blelloch, G.E., Wei, Y. (2020). Concurrent Fixed-Size Allocation and Free in Constant Time. https://arxiv.org/abs/2008.04296

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓