What to do When no Thread is Watching
Memory reclamation in concurrent programs is difficult. Hazard pointers, which for C++ are currently progressing through the Standard Committee, are a scalable technique for solving the reclamation problem. Another library-level approach is epoch-based algorithms, which offer very different run-time characteristics. This talk provides an introduction to the epoch-based approach, some qualitative comparisons to hazard pointers, and suggestions for further reading.
In single-thread applications, memory reclamation (making memory available for reuse) after logical deletion is always safe. In concurrent programs, memory must not be reused while other threads might still access the memory. For example, consider deleting the first node in a singly-linked list. While the node may be removed from the list immediately (ignoring ABA), other threads may still attempt to access the node. Until these attempts complete, the node’s memory must not be reused.
In its simplest form, an epoch-based reclamation algorithm tracks how many threads have access to a data structure’s nodes. This count is maintained in an active epoch and one or more waiting-until-empty epochs. Each epoch has an associated list of logically deleted nodes. A thread, prior to accessing any nodes, increments the active epoch count. When the thread completes accessing nodes, the thread decrements the count it previously incremented (not necessarily the active epoch count). Memory logically deleted is always added to the list associated with the active epoch. Periodically, a new active epoch is started and the current one, along with its associated list of logically deleted nodes, is now considered a waiting-until-empty epoch. When the number of threads in a waiting-until-empty epoch goes to zero, the associated logically deleted nodes are reclaimed.
A key theoretical issue with epoch-based reclamation is that an unbounded amount of memory may be held for reclamation. A potential benefit is performance. These and other characteristics are qualitatively explored, with references to prior work.
Advertisement
