MARBANIANG, Jonathan and Peri, Sathya
(2018)
GCList: Garbage Collection in Concurrent Sets.
Masters thesis, Indian Institute of Technology Hyderabad.
Abstract
Garbage Collection in concurrent data structures, especially lock-free ones, pose multiple design and consistency
challenges. In this instance, we consider the case of concurrent sets. A set is a collection of elements,
where the elements are ordered and distinct. These two invariants are always maintained at every point in
time.
Sets are usually represented as a linked list of nodes, with each node denoting an element in the Set. Operations
on the set include adding elements to the set, removing elements from it and searching for elements in
it. Currently, multiple implementations of concurrent sets already exist. LazyList[1], Hand-over-hand List[2]
and Harris’ List[3] are some of the well-known implementations. However none of these implementations
employ, or are concerned with garbage collection of deleted nodes. Instead each implementation ignores
deleted nodes or depends on the language’s garbage collector to handle them.
Additionally, Garbage collection in concurrent lists, that use optimistic traversals or that are lock-free, is not
trivial.
For example, in Lazy List and Harris’ List, they allow a thread to traverse a node or a sequence of nodes after
these nodes have already been removed from the list, and hence possibly deleted. If deleted nodes are to be
reused, this will potentially lead to the ABA problem.[4]
Moreover, some languages like C++ do not have an in-built garbage collector. Some constructs like Shared
Pointers[5] provide a limited garbage collection facility, but it degrades performance by a large scale. Integrating
Shared Pointers into a concurrent code is also not a trivial task.
In this thesis, we propose a new representation of a concurrent set, GCList, which employs in-built garbage
collection. We propose a novel garbage collection scheme that implements in-built memory reclamation
whereby it reuses deleted nodes from the list. We propose both lock-based and lock-free implementations of
GCList. The garbage collection scheme works in parallel with the Set operations.
In our experiments with varying workloads and randomised Set operations, GCList shows comparable performance
to LazyList[1] & Harris’ List[3] while outperforming Shared Pointers[5], Hazard Pointers[6] and
Hand-over-hand List[2]. GCList also consumed 3-4 times less memory as compared to LazyList[1] and
Harris’ List[3] and is comparable to Shared Pointers[5] and Hazard Pointers[6].
Actions (login required)
 |
View Item |
Altmetric
Altmetric