Epoch Based Reclamation
Epoch based reclamation is another way to free memory safely in lock free structures, trading the per access cost of hazard pointers for cheaper reads and coarser batching. It groups operations into numbered time periods called epochs.
There is a global epoch counter. When a thread begins an operation, it announces that it is active in the current epoch by recording that number. While active, it is said to be in a critical region where it may touch shared nodes. When it finishes, it marks itself inactive.
- Global epoch A counter that advances when all active threads have caught up.
- Announce A thread records the current epoch as it enters a critical region.
- Limbo lists Retired nodes are stored per epoch and freed two epochs later.
A thread can try to advance the global epoch only when every active thread is in the current epoch. Once the epoch moves forward, nodes retired two epochs ago are guaranteed unreachable, because every thread has since left the region where it could have held a reference, so they can be freed.
The advantage is very cheap reads, since announcing an epoch is a simple store rather than per node publishing. The danger is that a single thread stuck in a critical region prevents the epoch from advancing, stalling all reclamation and letting limbo lists grow without bound.
Key idea
Epoch based reclamation defers freeing until the global epoch advances past every active thread, giving cheap reads but stalling if one thread lingers in a critical region.