[concurrency-interest] Garbage collection for parallel data struc

Kimo Crossman kimo at webnetic.net
Mon May 14 23:24:05 EDT 2012

People may find this upcoming paper interesting by a notable researcher and
from a multicore research group:

Can Parallel Data Structures Rely on Automatic Memory

Erez Petrank
Dept. of Computer Science
Technion, Israel
erez at cs.technion.ac.il

MSPC’12, June 16, 2012, Beijing, China.

The complexity of parallel data structures is often measured
by two major factors: the throughput they provide and the
progress they guarantee. Progress guarantees are particu-
larly important for systems that require responsiveness such
as real-time systems, operating systems, interactive systems,
etc. Notions of progress guarantees such as lock-freedom,
wait-freedom, and obstruction-freedom that provide di er-
ent levels of guarantees have been proposed in the literature
[4, 6]. Concurrent access (and furthermore, optimistic ac-
cess) to shared objects makes the management of memory
one of the more complex aspects of concurrent algorithms
design. The use of automatic memory management greatly
simpli es such algorithms [11, 3, 2, 9]. However, while the
existence of lock-free garbage collection has been demon-
strated [5], the existence of a practical automatic memory
manager that supports lock-free or wait-free algorithms is
still open. Furthermore, known schemes for manual recla-
mation of unused objects are di cult to use and impose a
signi cant overhead on the execution [10].

It turns out that the memory management community
is not fully aware of how dire the need is for memory man-
agers that support progress guarantees for the design of concurrent data

Likewise, designers of concurrent
data structures are not always aware of the fact that mem-
ory management with support for progress guarantees is not

Closing this gap between these two communities
is a major open problem for both communities.
In this talk we will examine the memory management
needs of concurrent algorithms.

Next, we will discuss how state-of-the-art research and practice deal with
the fact that
an important piece of technology is missing (e.g., [7, 1]). Fi-
nally, we will survey the currently available pieces in this
puzzle (e.g., [13, 12, 8]) and specify which pieces are miss-

This open problem is arguably the greatest challenge
facing the memory management community today.

Copyright 2012 ACM 978-1-4503-1219-6/12/06 ...$10.00.
Categories and Subject Descriptors
D.3.3 [Language Constructs and Features]: Dynamic
storage management, Concurrent programming structures;
D.3.4 [Processors]: Memory management (Garbage Collec-
tion); D.4.2 [Storage Management]: Garbage Collection
General Terms
Algorithms, Design, Performance, Reliability.

[1] D. F. Bacon, P. Cheng, and V. Rajan. A real-time
garbage collector with low overhead and consistent
utilization. In POPL, 2003.
[2] F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel.
Non-blocking binary search trees. In PODC , 2010.
[3] T. L. Harris. A pragmatic implementation of
non-blocking linked-lists. In DISC, 2001.
[4] M. Herlihy. Wait-free synchronization. ACM Trans.
Program. Lang. Syst., 13(1):124{149, 1991.
[5] M. Herlihy and J. E. B. Moss. Lock-free garbage
collection for multiprocessors. IEEE Trans. Parallel
Distrib. Syst., 3(3):304{311, 1992.
[6] M. Herlihy and N. Shavit. The Art of Multiprocessor
Programming. Morgan Kaufmann, 2008.
[7] R. L. Hudson and J. E. B. Moss. Sapphire: Copying
garbage collection without stopping the world.
Concurrency and Computation: Practice and
Experience, 15(3{5):223{261, 2003.
[8] G. Kliot, E. Petrank, and B. Steensgaard. A lock-free,
concurrent, and incremental stack scanning
mechanism for garbage collectors. Operating Systems
Review, 43(3):3{13, 2009.
[9] A. Kogan and E. Petrank. Wait-free queues with
multiple enqueuers and dequeuers. In PPOPP, 2011.
[10] M. M. Michael. Hazard pointers: Safe memory
reclamation for lock-free objects. IEEE Trans. Parallel
Distrib. Syst., 15(6):491{504, 2004.
[11] M. M. Michael and M. L. Scott. Simple, fast, and
practical non-blocking and blocking concurrent queue
algorithms. In PODC, 1996.
[12] E. Petrank, M. Musuvathi, and B. Steensgaard.
Progress guarantee for parallel programs via bounded
lock-freedom. In PLDI, 2009.
[13] F. Pizlo, E. Petrank, and B. Steensgaard. A study of
concurrent real-time garbage collectors. In PLDI 2008.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120514/f66b2008/attachment.html>

More information about the Concurrency-interest mailing list